Petite collection d'entiers dans Redis

L'ensemble d'entiers (intset) est l'une des implémentations sous-jacentes des clés d'ensemble : lorsqu'un ensemble ne contient que des éléments de valeur entière et que le nombre d'éléments dans cet ensemble n'est pas grand, Redis utilisera des ensembles d'entiers comme implémentation sous-jacente de définir les clés.

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

L'avantage est que lorsqu'il n'y a qu'un petit nombre d'éléments entiers dans l'ensemble, l'utilisation d'autres structures de données introduites auparavant, telles que sds, occupera une quantité de mémoire relativement importante, mais s'il n'est enregistré que sous forme d'ensemble entier. Si tel est le cas, ce sera plus économique.

Structure de données de tableau d'entiers

La définition du tableau d'entiers se trouve dans intset.h, comme suit :

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

Bien que la structure d'intset déclare l'attribut de contenu comme un tableau de type int8_t , mais en fait le tableau contents ne stocke aucune valeur de type int8_t - le type réel du tableau contents dépend de la valeur de l'attribut d'encodage :

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

Vous pouvez voir qu'il y a trois types au total, correspondant à int_16, int_32, int_64.

Tous les éléments du tableau d'entiers sont classés du plus petit au plus grand dans le tableau, et le tableau ne contient aucun doublon.

Opérations sur les ensembles d'entiers

Créer un ensemble d'entiers

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

Insérer un élément

/* 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;
}

Lors de l'insertion d'un élément, vous devez selon la taille du nouvel élément pour re-déterminer l'encodage utilisé. Si le nouvel élément dépasse la plage de représentation de l'encodage d'origine, l'encodage doit être ajusté et le format d'encodage de tous les autres éléments de la collection doit être ajusté. L'ajustement de l'encodage est un processus irréversible, ce qui signifie qu'il ne peut être ajusté que d'un petit encodage à un grand encodage, et ne peut être que mis à niveau mais pas rétrogradé.

Processus de mise à niveau

La mise à niveau de l'ensemble d'entiers et l'ajout de nouveaux éléments appellent la fonction intsetUpgradeAndAdd, qui est divisée en trois étapes :

• Selon le nouveau element Type qui étend la taille de l'espace du tableau sous-jacent de collections d'entiers et alloue de l'espace pour les nouveaux éléments.

• Convertissez tous les éléments existants du tableau sous-jacent au même type que les nouveaux éléments, et placez les éléments convertis en type dans les bits corrects, et pendant le processus de placement des éléments, il est nécessaire de continuer à maintenir inchangée la nature ordonnée du tableau sous-jacent.

• Ajoute de nouveaux éléments au tableau sous-jacent.

/* 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;
}

L'approche actuelle de la collection d'entiers permet à la collection de sauvegarder trois types de valeurs différents en même temps, et garantit également que l'opération de mise à niveau ne sera effectuée que lorsque cela est nécessaire. Vous pouvez essayer d'économiser de la mémoire autant que possible.

Élément de recherche

Lors de la recherche, vous devez d'abord déterminer si l'élément que vous souhaitez trouver se trouve dans la plage valide de l'encodage actuel. S'il n'est pas dans la plage actuelle, vous pouvez le faire. renvoyez-le directement.

De plus, comme l'ensemble entier est un ensemble ordonné, la recherche binaire peut être utilisée,

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!