Small collection of integers in Redis

Integer set (intset) is one of the underlying implementations of the set key: When a set only contains integer-valued elements, and the number of elements in the set is not large, Redis will use the integer set as the underlying implementation of the set key.

127.0.0.1:6379> sadd numbers 1 2 3 4 5
(integer) 5
127.0.0.1:6379> object encoding numbers
"intset"

The advantage of this is that when there are only a small number of integer elements in the collection, using other data structures introduced before, such as sds, will occupy a relatively large amount of memory, but if it is only saved as an integer collection, It will be more economical.

Integer array data structure

The definition of integer array is located in intset.h, as follows:

typedef struct intset {
    uint32_t encoding;  // 编码方式
    uint32_t length;   // 保存的元素个数
    int8_t contents[];  // 保存元素的数组
 } 
    intset;

Although the intset structure declares the contents attribute as an array of type int8_t, In fact, the contents array does not store any values ​​of type int8_t - the real type of the contents array depends on the value of the encoding attribute:

#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_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;
}

You can see that there are three types in total, corresponding to int_16, int_32, and int_64.

All elements in the integer array are arranged in order from small to large in the array, and the array does not contain any duplicates.

Integer set operation

Create an integer set

// 初始化空的整数集合intset *intsetNew(void) {
    intset *is = zmalloc(sizeof(intset));    
    is->encoding = intrev32ifbe(INTSET_ENC_INT16); // 默认创建int_16的编码格式
    is->length = 0;    
    return is;
}

Insert an element

/* 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 < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
    }

    _intsetSet(is,pos,value); // 添加数据到第pos位
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1); // 调整元素个数
    return is;
}

When inserting an element, it needs to be re-determined based on the size of the new element The encoding used. If the new element exceeds the representation range of the original encoding, the encoding needs to be adjusted, and the encoding format of all other elements in the collection needs to be adjusted. Adjusting the encoding is an irreversible process, which means that it can only be adjusted from a small encoding to a large encoding, and can only be upgraded but not downgraded.

Upgrade process

To upgrade the integer set and add a new element, the intsetUpgradeAndAdd function is called, which is divided into three steps:

• According to the new element Type that extends the space size of the underlying array of integer collections and allocates space for new elements.

• Convert all existing elements of the underlying array to the same type as the new elements, and place the type-converted elements in the correct positions, and during the process of placing elements , it is necessary to continue to maintain the ordered nature of the underlying array unchanged.

• Add new elements to the underlying array.

/* 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 < 0 ? 1 : 0;    
    
    /* First set new encoding and resize */
    // 重新设置整数集合的编码
    is->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;
}

The current approach to integer collections allows the collection to store three different types of values ​​at the same time, and ensures that the upgrade operation will only be performed when necessary. This can be done as much as possible. Save memory.

Search for elements

When searching, you need to first determine whether the element you want to find is within the valid range of the current encoding. If it is not within the current range, you can return it directly.

In addition, because the integer set is an ordered set, binary search can be used,

uint8_t intsetFind(intset *is, int64_t value) {    // 获得目标值的编码
    uint8_t valenc = _intsetValueEncoding(value);    // 只有目标值的编码比当前编码小，才继续执行查找过程
    return valenc <= intrev32ifbe(is->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 < _intsetGet(is,0)) {            
        // 如果目标址小于当前最小值，返回0， 同时待插入的位置pos为0
            if (pos) *pos = 0;            
            return 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;
        } else {            
        break;
        }
    }    if (value == cur) {        
    if (pos) *pos = mid;        
    return 1;
    } else {        
    if (pos) *pos = min;        
    return 0;
    }
}

The above is the detailed content of Small collection of integers in Redis. For more information, please follow other related articles on the PHP Chinese website!