redis源码学习_整数集合

 1 typedef struct intset {
 2 
 3     /*
 4  虽然 intset 结构将 contents 属性声明为 int8_t 类型的数组， 但实际上 contents 数组的真正类型取决于 encoding 属性的值：
 5 如果 encoding 属性的值为 INTSET_ENC_INT16 ， 那么 contents 就是一个 int16_t 类型的数组， 数组里的每个项都是一个 int16_t类型的整数值 （最小值为 -32,768 ，最大值为 32,767 ）。
 6 如果 encoding 属性的值为 INTSET_ENC_INT32 ， 那么 contents 就是一个 int32_t 类型的数组， 数组里的每个项都是一个 int32_t类型的整数值 （最小值为 -2,147,483,648 ，最大值为 2,147,483,647 ）。
 7 如果 encoding 属性的值为 INTSET_ENC_INT64 ， 那么 contents 就是一个 int64_t 类型的数组， 数组里的每个项都是一个 int64_t类型的整数值 （最小值为 -9,223,372,036,854,775,808 ，最大值为9,223,372,036,854,775,807 ）。
 8  */
 9     // 编码方式
10     uint32_t encoding;
11     // 集合包含的元素数量
12     uint32_t length;
13     // 保存元素的数组
14     int8_t contents[];
15 } intset;

 1 /* Return the required encoding for the provided value. 
 2  *
 3  * 返回适用于传入值 v 的编码方式
 4  *
 5  * T = O(1)
 6  */
 7 static uint8_t _intsetValueEncoding(int64_t v) {
 8     if (v < INT32_MIN || v > INT32_MAX)
 9         return INTSET_ENC_INT64;
10     else if (v < INT16_MIN || v > INT16_MAX)
11         return INTSET_ENC_INT32;
12     else
13         return INTSET_ENC_INT16;
14 }

 1 /* Set the value at pos, using the configured encoding. 
 2  *
 3  * 根据集合的编码方式，将底层数组在 pos 位置上的值设为 value 。
 4  *
 5  * T = O(1)
 6  */
 7 static void _intsetSet(intset *is, int pos, int64_t value) {
 8 
 9     // 取出集合的编码方式
10     uint32_t encoding = intrev32ifbe(is->encoding);
11 
12     // 根据编码 ((Enc_t*)is->contents) 将数组转换回正确的类型
13     // 然后 ((Enc_t*)is->contents)[pos] 定位到数组索引上
14     // 接着 ((Enc_t*)is->contents)[pos] = value 将值赋给数组
15     // 最后， ((Enc_t*)is->contents)+pos 定位到刚刚设置的新值上 
16     // 如果有需要的话， memrevEncifbe 将对值进行大小端转换
17     if (encoding == INTSET_ENC_INT64) {
18         ((int64_t*)is->contents)[pos] = value;
19         memrev64ifbe(((int64_t*)is->contents)+pos);
20     } else if (encoding == INTSET_ENC_INT32) {
21         ((int32_t*)is->contents)[pos] = value;
22         memrev32ifbe(((int32_t*)is->contents)+pos);
23     } else {
24         ((int16_t*)is->contents)[pos] = value;
25         memrev16ifbe(((int16_t*)is->contents)+pos);
26     }
27 }

1 #if (BYTE_ORDER == LITTLE_ENDIAN)
2 #define memrev16ifbe(p)
3 #define memrev32ifbe(p)
4 #define memrev64ifbe(p)
5 #else
6 #define memrev16ifbe(p) memrev16(p) //高低位对换
7 #define memrev32ifbe(p) memrev32(p) //高低位对换
8 #define memrev64ifbe(p) memrev64(p) //高低位对换
9 #endif

 1 #include <stdlib.h>
 2 #include <stdio.h>
 3 int main(int argc, char **argv)
 4 {
 5     union {
 6         short s;
 7         char c[sizeof(short)];
 8     } un;
 9     un.s = 0x0102;
10     if(sizeof(short)==2) {
11         if(un.c[0]==1 && un.c[1] == 2)
12             printf("big-endian\n");
13         else if (un.c[0] == 2 && un.c[1] == 1)
14             printf("little-endian\n");
15         else
16             printf("unknown\n");
17     } else
18         printf("sizeof(short)= %d\n",sizeof(short));
19     exit(0);
20 }

 1 /* Upgrades the intset to a larger encoding and inserts the given integer. 
 2  *
 3  * 根据值 value 所使用的编码方式，对整数集合的编码进行升级，
 4  * 并将值 value 添加到升级后的整数集合中。
 5  *
 6  * 返回值：添加新元素之后的整数集合
 7  *
 8  * T = O(N)
 9  */
10 static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
11     
12     // 当前的编码方式
13     uint8_t curenc = intrev32ifbe(is->encoding);
14 
15     // 新值所需的编码方式
16     uint8_t newenc = _intsetValueEncoding(value);
17 
18     // 当前集合的元素数量
19     int length = intrev32ifbe(is->length);
20 
21     // 根据 value 的值，决定是将它添加到底层数组的最前端还是最后端
22     // 注意，因为 value 的编码比集合原有的其他元素的编码都要大
23     // 所以 value 要么大于集合中的所有元素，要么小于集合中的所有元素
24     // 因此，value 只能添加到底层数组的最前端或最后端
25     int prepend = value < 0 ? 1 : 0;
26 
27     /* First set new encoding and resize */
28     is->encoding = intrev32ifbe(newenc);
29 
30     is = intsetResize(is,intrev32ifbe(is->length)+1);
31 
32     /* Upgrade back-to-front so we don‘t overwrite values.
33      * Note that the "prepend" variable is used to make sure we have an empty
34      * space at either the beginning or the end of the intset. */
35     while(length--)
36         _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));
37 
38     /* Set the value at the beginning or the end. */
39     // 设置新值，根据 prepend 的值来决定是添加到数组头还是数组尾
40     if (prepend)
41         _intsetSet(is,0,value);
42     else
43         _intsetSet(is,intrev32ifbe(is->length),value);
44 
45     // 更新整数集合的元素数量
46     is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
47 
48     return is;
49 }

 1 static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
 2     int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
 3     int64_t cur = -1;
 4 
 5     /* The value can never be found when the set is empty */
 6     if (intrev32ifbe(is->length) == 0) {
 7         if (pos) *pos = 0;
 8         return 0;
 9     } else {
10         /* Check for the case where we know we cannot find the value,
11          * but do know the insert position. */
12         // 因为底层数组是有序的，如果 value 比数组中最后一个值都要大
13         // 那么 value 肯定不存在于集合中，
14         // 并且应该将 value 添加到底层数组的最末端
15         if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {
16             if (pos) *pos = intrev32ifbe(is->length);
17             return 0;
18         // 因为底层数组是有序的，如果 value 比数组中最前一个值都要小
19         // 那么 value 肯定不存在于集合中，
20         // 并且应该将它添加到底层数组的最前端
21         } else if (value < _intsetGet(is,0)) {
22             if (pos) *pos = 0;
23             return 0;
24         }
25     }
26 
27     // 在有序数组中进行二分查找
28     while(max >= min) {
29         mid = (min+max)/2;
30         cur = _intsetGet(is,mid);
31         if (value > cur) {
32             min = mid+1;
33         } else if (value < cur) {
34             max = mid-1;
35         } else {
36             break;
37         }
38     }
39 
40     // 检查是否已经找到了 value
41     if (value == cur) {
42         if (pos) *pos = mid;
43         return 1;
44     } else {
45         if (pos) *pos = min;
46         return 0;
47     }
48 }

 1 static void intsetMoveTail(intset *is, uint32_t from, uint32_t to) {
 2 
 3     void *src, *dst;
 4 
 5     uint32_t bytes = intrev32ifbe(is->length)-from;
 6 
 7     uint32_t encoding = intrev32ifbe(is->encoding);
 8 
 9     //这里的移动可就是批量移动的了，见后面的memmove
10     if (encoding == INTSET_ENC_INT64) {
11         src = (int64_t*)is->contents+from;
12         dst = (int64_t*)is->contents+to;
13         bytes *= sizeof(int64_t);
14     } else if (encoding == INTSET_ENC_INT32) {
15         src = (int32_t*)is->contents+from;
16         dst = (int32_t*)is->contents+to;
17         bytes *= sizeof(int32_t);
18     } else {
19         src = (int16_t*)is->contents+from;
20         dst = (int16_t*)is->contents+to;
21         bytes *= sizeof(int16_t);
22     }
23 
24     memmove(dst,src,bytes);
25 }

 1 intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
 2 
 3     // 计算编码 value 所需的长度
 4     uint8_t valenc = _intsetValueEncoding(value);
 5     uint32_t pos;
 6 
 7     // 默认设置插入为成功
 8     if (success) *success = 1;
 9 
10     /* Upgrade encoding if necessary. If we need to upgrade, we know that
11      * this value should be either appended (if > 0) or prepended (if < 0),
12      * because it lies outside the range of existing values. */
13     if (valenc > intrev32ifbe(is->encoding)) {
14         /* This always succeeds, so we don‘t need to curry *success. */
15         return intsetUpgradeAndAdd(is,value);
16     } else {
17         /* Abort if the value is already present in the set.
18          * This call will populate "pos" with the right position to insert
19          * the value when it cannot be found. */
20         if (intsetSearch(is,value,&pos)) {
21             if (success) *success = 0;
22             return is;
23         }
24 
25         //将 value 添加到整数集合中并为 value 在集合中分配空间
26         is = intsetResize(is,intrev32ifbe(is->length)+1);
27         
28         if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
29     }
30 
31     // 将新值设置到底层数组的指定位置中
32     _intsetSet(is,pos,value);
33 
34     // 增一集合元素数量的计数器
35     is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
36 
37     // 返回添加新元素后的整数集合
38     return is;
39 }

 1 intset *intsetRemove(intset *is, int64_t value, int *success) {
 2     uint8_t valenc = _intsetValueEncoding(value);
 3     uint32_t pos;
 4     if (success) *success = 0;
 5 
 6 
 7     if (valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,&pos)) {
 8         uint32_t len = intrev32ifbe(is->length);
 9 
10         /* We know we can delete */
11         if (success) *success = 1;
12 
13         /* Overwrite value with tail and update length */
14         if (pos < (len-1)) intsetMoveTail(is,pos+1,pos);
15         
16         is = intsetResize(is,len-1);
17         
18         is->length = intrev32ifbe(len-1);
19     }
20 
21     return is;
22 }

1 size_t intsetBlobLen(intset *is) {
2     return sizeof(intset)+intrev32ifbe(is->length)*intrev32ifbe(is->encoding);
3 }