整數集合（intset）是集合鍵的底層實現之一： 當一個集合只包含整數值元素， 并且這個集合的元素數量不多時， redis 就會使用整數集合作為集合鍵的底層實現。
127.0.0.1:6379>?sadd?numbers?1?2?3?4?5 (integer)?5 127.0.0.1:6379>?object?encoding?numbers "intset"
這么做的好處是當集合中只有少量的整數元素的時候，采用之前介紹的其他數據結構，比如sds，都會占用比較大的內存，但如果僅保存為整數集合的話，則會更加經濟。
整數數組數據結構
整數數組的定義位于intset.h中，具體如下：
typedef?struct?intset?{ ????uint32_t?encoding;??//?編碼方式 ????uint32_t?length;???//?保存的元素個數 ????int8_t?contents[];??//?保存元素的數組 ?}? ????intset;
雖然 intset 結構將 contents 屬性聲明為 int8_t 類型的數組， 但實際上 contents 數組并不保存任何 int8_t 類型的值 —— contents 數組的真正類型取決于 encoding 屬性的值：
#define?INTSET_ENC_INT16?(sizeof(int16_t)) #define?INTSET_ENC_INT32?(sizeof(int32_t)) #define?INTSET_ENC_INT64?(sizeof(int64_t)) /*?Return?the?required?encoding?for?the?provided?value.?*/ static?uint8_t?_intsetValueEncoding(int64_t?v)?{???? ????if?(v??INT32_MAX)???????? ????????return?INTSET_ENC_INT64;???? ????else?if?(v??INT16_MAX)???????? ????????return?INTSET_ENC_INT32;???? ????else ??????return?INTSET_ENC_INT16; }
可以看到一共會有三種類型，分別對應int_16, int_32, int_64。
整數數組中所有的元素在數組中按值的大小從小到大有序地排列， 并且數組中不包含任何重復項。
整數集合操作
創建整數集合
//?初始化空的整數集合intset?*intsetNew(void)?{ ????intset?*is?=?zmalloc(sizeof(intset));???? ????is->encoding?=?intrev32ifbe(INTSET_ENC_INT16);?//?默認創建int_16的編碼格式 ????is->length?=?0;???? ????return?is; }
插入一個元素
/*?Insert?an?integer?in?the?intset?*/intset?*intsetAdd(intset?*is,?int64_t?value,?uint8_t?*success)?{ ????uint8_t?valenc?=?_intsetValueEncoding(value); ????uint32_t?pos;???? ????if?(success)?*success?=?1;????//?如果超出了當前編碼格式所能表示的范圍，則升級整數集合并添加元素 ????if?(valenc?>?intrev32ifbe(is->encoding))?{???????? ????/*?This?always?succeeds,?so?we?don't?need?to?curry?*success.?*/ ????????return?intsetUpgradeAndAdd(is,value); ????}?else?{????????//?如果元素已經存在于集合，success返回0 ????????//?如果不存在的話，?這個函數會返回元素應該插入的位置pos ????????if?(intsetSearch(is,value,&pos))?{???????????? ????????if?(success)?*success?=?0;???????????? ????????return?is; ????????}????????//?否則，需要重新調整集合的大小 ????????is?=?intsetResize(is,intrev32ifbe(is->length)+1);????????//?將pos之后的數據全都向后挪動一個位子 ????????if?(pos?length))?intsetMoveTail(is,pos,pos+1); ????} ????_intsetSet(is,pos,value);?//?添加數據到第pos位 ????is->length?=?intrev32ifbe(intrev32ifbe(is->length)+1);?//?調整元素個數 ????return?is; }
在插入元素的時候，需要根據新元素的大小來重新確定所采用的編碼。如果新元素超出了原有編碼的表示范圍，就需要調整編碼，同時調整集合中所有其他元素的編碼格式。調整編碼是一個不可逆的過程，就是說只能從小的編碼調整到大的編碼，只能升級不能降級。
升級過程
升級整數集合并添加新元素調用的是intsetUpgradeAndAdd函數，共分為三步進行：
-
根據新元素的類型， 擴展整數集合底層數組的空間大小， 并為新元素分配空間。
-
將底層數組現有的所有元素都轉換成與新元素相同的類型， 并將類型轉換后的元素放置到正確的位上， 而且在放置元素的過程中， 需要繼續維持底層數組的有序性質不變。
-
將新元素添加到底層數組里面。
/*?Upgrades?the?intset?to?a?larger?encoding?and?inserts?the?given?integer.?*/static?intset?*intsetUpgradeAndAdd(intset?*is,?int64_t?value)?{????//?當前的編碼 ????uint8_t?curenc?=?intrev32ifbe(is->encoding);????//?根據新元素的值獲得新的編碼 ????uint8_t?newenc?=?_intsetValueEncoding(value);???? ????int?length?=?intrev32ifbe(is->length);???? ????//?由于整數集合是一個有序集合，所以新的這個超出范圍的元素，要不插入頭部，要不插入尾部 ????//?當value大于0的時候，就是插入到尾部，否則插入到頭部，用參數prepend來標記 ????int?prepend?=?value?encoding?=?intrev32ifbe(newenc);????//?根據新編碼調整整數集合的大小 ????is?=?intsetResize(is,intrev32ifbe(is->length)+1);????//?從尾部向頭部進行升級，這樣在挪動其中的元素的時候，不會覆蓋原來的值 ????while(length--)???????? ??????????//?如果新元素是插入到尾部，prepend==0，?所以原來最后的元素是挪動到length位置 ????????//?如果新元素是插入到頭部，prepend==1，所有的元素都要向后挪動一個位置，將頭部空出來 ????????_intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));???? ???????? ????????/*?Set?the?value?at?the?beginning?or?the?end.?*/ ????if?(prepend)???????? ????//?如果prepend==1，?插入到頭部 ????????_intsetSet(is,0,value);???? ???????else ????????//?否則，設置最后一個位置的元素為value ????????_intsetSet(is,intrev32ifbe(is->length),value);????//?元素個數加1 ????is->length?=?intrev32ifbe(intrev32ifbe(is->length)+1);???? ????return?is; }
而整數集合現在的做法既可以讓集合能同時保存三種不同類型的值， 又可以確保升級操作只會在有需要的時候進行， 這可以盡量節省內存。
查找元素
查找的時候，需要先判斷要查找的元素是否在當前編碼的有效范圍內，如果不在當前范圍內，可以直接返回。
另外因為整數集合是一個有序集合，可以采用二分查找的辦法，
uint8_t?intsetFind(intset?*is,?int64_t?value)?{????//?獲得目標值的編碼 ????uint8_t?valenc?=?_intsetValueEncoding(value);????//?只有目標值的編碼比當前編碼小，才繼續執行查找過程 ????return?valenc?encoding)?&&?intsetSearch(is,value,NULL); }//?如果找到這個元素，返回1，同時pos表示這個值在整數集合里邊的位置 //?如果沒有找到這個元素，返回0，?同時pos表示這個值可以插入的位置 static?uint8_t?intsetSearch(intset?*is,?int64_t?value,?uint32_t?*pos)?{???? int?min?=?0,?max?=?intrev32ifbe(is->length)-1,?mid?=?-1; ????int64_t?cur?=?-1;???? ???? ????/*?The?value?can?never?be?found?when?the?set?is?empty?*/ ????//?如果集合的長度為0，?直接返回0 ????if?(intrev32ifbe(is->length)?==?0)?{???????? ????if?(pos)?*pos?=?0;???????? ????return?0; ????}?else?{???????? ????/*?Check?for?the?case?where?we?know?we?cannot?find?the?value, ?????????*?but?do?know?the?insert?position.?*/ ????????//?如果目標值大于當前最大值，肯定找不到，返回0，?同時待插入的位置pos為length ????????if?(value?>?_intsetGet(is,intrev32ifbe(is->length)-1))?{???????????? ????????if?(pos)?*pos?=?intrev32ifbe(is->length);???????????? ????????return?0; ????????}?else?if?(value?=?min)?{????????//?得到中間位置 ????????mid?=?((unsigned?int)min?+?(unsigned?int)max)?>>?1;????????//?得到中間位置的值 ????????cur?=?_intsetGet(is,mid);???????? ????????if?(value?>?cur)?{ ????????????min?=?mid+1; ????????}?else?if?(value?<div></div>
? 版權聲明
文章版權歸作者所有，未經允許請勿轉載。
THE END
