[redis設計與實作][5]基本資料結構——整數集合

整數集合（intset）用于集合鍵。當一個集合隻包含整數值元素，并且數量不多的時候，會使用整數集合作為集合鍵的底層實作。相對于直接儲存字元串，整數集合能夠很好地節約記憶體，但是由于是數組儲存，需要特别關注數組長度。

定義：（intset.h）

[cce lang=”c”]

typedef struct intset {

//編碼方式

uint32_t encoding;

//集合包含的元素數量

uint32_t length;

//儲存元素的數組

int8_t contents[];

} intset;

[/cce]

encoding：

intsetencint16：content數組每一項都是一個int16_t類型的數值（有符号）

intsetencint32：content數組每一項都是一個int32_t類型的數值

intsetencint64：content數組每一項都是一個int64_t類型的數值

整數集合支援長度更新，但是不支援長度降級。當插入的最大長度超過目前編碼方式容納的最大值的時候，會對編碼類型進行更新。但是如果删除了一個大數字，整體整數集合不會再進行降級。

intset *intsetnew(void);（建立一個新的整數集合）

intset *intsetnew(void) {

intset *is = zmalloc(sizeof(intset));

//對于x86架構采用小端序，#define intrev32ifbe(v) (v)

// 初始化的時候編碼為intset_enc_int16

is->encoding = intrev32ifbe(intset_enc_int16);

is->length = 0;

return is;

}

intset *intsetadd(intset *is, int64t value, uint8t *success);（添加到整數集合）

intset *intsetadd(intset *is, int64_t value, uint8_t *success) {

//判斷目前值需要的編碼類型

uint8_t valenc = _intsetvalueencoding(value);

uint32_t pos;

if (success) *success = 1;

/* upgrade encoding if necessary. if we need to upgrade, we know that

* this value should be either appended (if > 0) or prepended (if < 0),

* because it lies outside the range of existing values. */

//如果目前值的編碼類型大于目前整數集合的編碼，需要進行更新

if (valenc > intrev32ifbe(is->encoding)) {

/* this always succeeds, so we don’t need to curry *success. */

return intsetupgradeandadd(is,value);

} else {

/* abort if the value is already present in the set.

* this call will populate “pos” with the right position to insert

* the value when it cannot be found. */

//查找目前數值是否已經存在

if (intsetsearch(is,value,&pos)) {

if (success) *success = 0;

is = intsetresize(is,intrev32ifbe(is->length)+1);

//移動插入點以後的元素，空出插入位置

if (pos < intrev32ifbe(is->length)) intsetmovetail(is,pos,pos+1);

_intsetset(is,pos,value);

is->length = intrev32ifbe(intrev32ifbe(is->length)+1);

static uint8_t _intsetvalueencoding(int64_t v) {

if (v < int32_min || v > int32_max)

return intset_enc_int64;

else if (v < int16_min || v > int16_max)

return intset_enc_int32;

else

return intset_enc_int16;

//更新整數集合

static intset *intsetupgradeandadd(intset *is, int64_t value) {

uint8_t curenc = intrev32ifbe(is->encoding);

uint8_t newenc = _intsetvalueencoding(value);

int length = intrev32ifbe(is->length);

int prepend = value < 0 ? 1 : 0;

/* first set new encoding and resize */

//設定新的編碼

is->encoding = intrev32ifbe(newenc);

//重新配置設定整數集合大小

/* upgrade back-to-front so we don’t overwrite values.

* note that the “prepend” variable is used to make sure we have an empty

* space at either the beginning or the end of the intset. */

//倒着重新設定值，防止記憶體覆寫

while(length–)

_intsetset(is,length+prepend,_intsetgetencoded(is,length,curenc));

/* set the value at the beginning or the end. */

if (prepend)

//插入的值小于0，放到最前面

_intsetset(is,0,value);

//插入的值大于0，放到最後面

_intsetset(is,intrev32ifbe(is->length),value);

//修改整數集合長度

static intset *intsetresize(intset *is, uint32_t len) {

uint32_t size = len*intrev32ifbe(is->encoding);

is = zrealloc(is,sizeof(intset)+size);

//擷取指定位置的值

static int64_t _intsetgetencoded(intset *is, int pos, uint8_t enc) {

int64_t v64;

int32_t v32;

int16_t v16;

if (enc == intset_enc_int64) {

memcpy(&v64,((int64_t*)is->contents)+pos,sizeof(v64));

memrev64ifbe(&v64);

return v64;

} else if (enc == intset_enc_int32) {

memcpy(&v32,((int32_t*)is->contents)+pos,sizeof(v32));

memrev32ifbe(&v32);

return v32;

memcpy(&v16,((int16_t*)is->contents)+pos,sizeof(v16));

memrev16ifbe(&v16);

return v16;

//插入到指定位置

static void _intsetset(intset *is, int pos, int64_t value) {

uint32_t encoding = intrev32ifbe(is->encoding);

if (encoding == intset_enc_int64) {

((int64_t*)is->contents)[pos] = value;

memrev64ifbe(((int64_t*)is->contents)+pos);

} else if (encoding == intset_enc_int32) {

((int32_t*)is->contents)[pos] = value;

memrev32ifbe(((int32_t*)is->contents)+pos);

((int16_t*)is->contents)[pos] = value;

memrev16ifbe(((int16_t*)is->contents)+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 */

//為空直接退出

if (intrev32ifbe(is->length) == 0) {

if (pos) *pos = 0;

return 0;

/* check for the case where we know we cannot find the value,

* but do know the insert position. */

//如果插入數值比最大的大或者比最小的小，直接退出，設定pos

if (value > _intsetget(is,intrev32ifbe(is->length)-1)) {

if (pos) *pos = intrev32ifbe(is->length);

} else if (value < _intsetget(is,0)) {

//折半查找

while(max >= min) {

mid = ((unsigned int)min + (unsigned int)max) >> 1;

cur = _intsetget(is,mid);

if (value > cur) {

min = mid+1;

} else if (value < cur) {

max = mid-1;

break;

if (value == cur) {

if (pos) *pos = mid;

return 1;

if (pos) *pos = min;

//從指定位置開始移動到最尾

static void intsetmovetail(intset *is, uint32_t from, uint32_t to) {

void *src, *dst;

uint32_t bytes = intrev32ifbe(is->length)-from;

src = (int64_t*)is->contents+from;

dst = (int64_t*)is->contents+to;

bytes *= sizeof(int64_t);

src = (int32_t*)is->contents+from;

dst = (int32_t*)is->contents+to;

bytes *= sizeof(int32_t);

src = (int16_t*)is->contents+from;

dst = (int16_t*)is->contents+to;

bytes *= sizeof(int16_t);

memmove(dst,src,bytes);

intset *intsetremove(intset *is, int64_t value, int *success);（移除元素）

intset *intsetremove(intset *is, int64_t value, int *success) {

//比對目前編碼并查找元素

if (valenc <= intrev32ifbe(is->encoding) && intsetsearch(is,value,&pos)) {

uint32_t len = intrev32ifbe(is->length);

/* we know we can delete */

/* overwrite value with tail and update length */

//找到後，向前移動數組

if (pos < (len-1)) intsetmovetail(is,pos+1,pos);

//收縮數組

is = intsetresize(is,len-1);

is->length = intrev32ifbe(len-1);

轉載自：https://coolex.info/blog/452.html