Redis源码阅读(五) 整数集合

发表于 | 分类于

Redis中当一个集合键只包含整数值元素，并且数量不是很多时，使用整数集合作为底层实现。

1. 定义

  • 整数集合
    • encoding 集合采用的编码方式：int16_t, int32_t, int64_t
    • length contents中包含整数的个数
    • contents 用于存储整数集合，通过encding来确定每个数字需要多少byte，如：int16_t, 表示每个数字占16位，若集合有3个元素，那么 contents的长度就位48 。
1
2
3
4
5
6
7
8
typedef struct intset {                                                                                
    // 编码方式                                                                                        
    uint32_t encoding;                                                                                 
    // 集合包含的元素个数                                                                              
    uint32_t length;                                                                                   
    // 保存元素的数组，所有的整数都保存在该数组里，利用encoding来确定其边界                                                                                  
    int8_t contents[];                                                                                 
} intset;

2. 升级

由于intset的结构方式，当添加的整数类型大于当前集合的编码方式时，需要对集合进行升级。

  1. 根据新元素的类型，重新计算需要的内存空间大小，并对整数集合的contents进行扩展。
  2. 将contents内原有的数据，放到新的位置，从后边开始，这样不会导致前面的数据不可用。
  3. 将新元素添加到集合中。

假设：

集合中有4个元素12, 27, 35, 68，而目前采用的编码方式为int16_t，contents的大小为4x2=8字节，现在要添加一个 66666，超过了int16_t所能表示的范围，所以需要int32_t来存储，此时需要对集合进行升级，重新计算所需要的空间(4+1)x4 = 20字节，所以先扩展内存空间，再移动68,35,27,12到指定位置，然后添加新元素。

3. 源码剖析

  • 升级并添加
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// intrev32ifbe 用于大小端转换
/**                                                                                                    
 * 升级整数集合的编码为value适合的编码, 并添加value                                                    
 */                                                                                                    
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的编码方式与当前不同，所以应该位于当前集合的最前面或最后面                                 
    int prepend = value < 0 ? 1 : 0;                                                                   
                                                                                                       
    /* First set new encoding and resize */                                                            
    // 更新编码方式                                                                                    
    is->encoding = intrev32ifbe(newenc);                                                               
    // 根据新编码大小和元素个数，扩展contents的大小                                                    
    is = intsetResize(is,intrev32ifbe(is->length)+1);                                                  
                                                                                                       
    /* 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)                                                                                       
        _intsetSet(is,0,value);                                                                        
    else                                                                                               
        _intsetSet(is,intrev32ifbe(is->length),value);                                                 
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);                                             
    return is;                                                                                         
}
  • 添加元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**                                                                                                 
 * 将value添加到集合中                                                                              
 * 添加成功 *success = 1， 失败 *success = 0                                                        
 */                                                                                                 
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;                                                              
            return is;                                                                              
        }                                                                                           
                                                                                                    
        // 分配空间，并移动出空余位置                                                               
        is = intsetResize(is,intrev32ifbe(is->length)+1);                                           
        if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);                           
    }                                                                                               
                                                                                                    
    // 插入value                                                                                    
    _intsetSet(is,pos,value);                                                                       
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);                                          
    return is;                                                                                      
}
  • 删除元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
intset *intsetRemove(intset *is, int64_t value, int *success) {                                     
                                                                                                    
    // 计算编码                                                                                     
    uint8_t valenc = _intsetValueEncoding(value);                                                   
    uint32_t pos;                                                                                   
    if (success) *success = 0;                                                                      
                                                                                                    
    // 编码小于当前编码, 说明可能在集合中                                                           
    if (valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,&pos)) {                      
        uint32_t len = intrev32ifbe(is->length);                                                    
                                                                                                    
        /* We know we can delete */                                                                 
        if (success) *success = 1;                                                                  
                                                                                                    
        /* 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);                                                           
    }                                                                                               
    return is;                                                                                      
}