Kleine Sammlung von Ganzzahlen in Redis

Integer-Set (Intset) ist eine der zugrunde liegenden Implementierungen von Set-Schlüsseln: Wenn ein Set nur ganzzahlige Elemente enthält und die Anzahl der Elemente in diesem Set nicht groß ist, verwendet Redis Integer-Sets als zugrunde liegende Implementierung von Schlüssel festlegen.

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

Der Vorteil davon besteht darin, dass die Verwendung anderer zuvor eingeführter Datenstrukturen wie SDS relativ viel Speicher belegt, wenn die Menge nur eine kleine Anzahl ganzzahliger Elemente enthält wenn es nur als Ganzzahlsatz gespeichert wird Wenn ja, ist es wirtschaftlicher.

Integer-Array-Datenstruktur

Die Definition des Integer-Arrays befindet sich in intset.h wie folgt:

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

Obwohl die Intset-Struktur das Inhaltsattribut als an deklariert Array vom Typ int8_t , aber tatsächlich speichert das Inhaltsarray keinen Wert vom Typ int8_t – der tatsächliche Typ des Inhaltsarrays hängt vom Wert des Codierungsattributs ab:

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

Sie können sehen, dass es welche gibt Insgesamt drei Typen, entsprechend int_16, int_32, int_64.

Alle Elemente im Ganzzahl-Array sind in der Reihenfolge von klein nach groß im Array angeordnet, und das Array enthält keine Duplikate.

Operationen mit Ganzzahlmengen

Erstellen Sie eine Ganzzahlmenge

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

Ein Element einfügen

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

Beim Einfügen eines Elements müssen Sie entsprechend vorgehen die Größe des neuen Elements, um die verwendete Kodierung neu zu bestimmen. Wenn das neue Element den Darstellungsbereich der ursprünglichen Kodierung überschreitet, muss die Kodierung angepasst werden und das Kodierungsformat aller anderen Elemente in der Sammlung muss angepasst werden. Das Anpassen der Kodierung ist ein irreversibler Vorgang, der nur von einer kleinen Kodierung auf eine große Kodierung angepasst werden kann und nur hochgestuft, aber nicht herabgestuft werden kann.

Upgrade-Prozess

Das Aktualisieren des Ganzzahlsatzes und das Hinzufügen neuer Elemente ruft die Funktion intsetUpgradeAndAdd auf, die in drei Schritte unterteilt ist:

• Entsprechend dem Neuen Elementtyp, der die Speicherplatzgröße des zugrunde liegenden Arrays von Ganzzahlsammlungen erweitert und Platz für neue Elemente zuweist.

• Konvertieren Sie alle vorhandenen Elemente des zugrunde liegenden Arrays in denselben Typ wie die neuen Elemente und platzieren Sie die typkonvertierten Elemente in den richtigen Bits und während des Vorgangs der Platzierung von Elementen ist notwendig, um die geordnete Natur des zugrunde liegenden Arrays weiterhin unverändert beizubehalten.

• Fügt dem zugrunde liegenden Array neue Elemente hinzu.

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

Der aktuelle Ansatz der Ganzzahlsammlung ermöglicht es der Sammlung, drei verschiedene Arten von Werten gleichzeitig zu speichern, und stellt außerdem sicher, dass der Aktualisierungsvorgang nur ausgeführt wird Bei Bedarf können Sie versuchen, so viel Speicher wie möglich zu sparen.

Element suchen

Bei der Suche müssen Sie zunächst feststellen, ob das gesuchte Element im gültigen Bereich der aktuellen Kodierung liegt. Wenn es nicht im aktuellen Bereich liegt, können Sie dies tun direkt zurückschicken.

Da es sich bei der Ganzzahlmenge um eine geordnete Menge handelt, kann außerdem die binäre Suche verwendet werden,

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

Das obige ist der detaillierte Inhalt vonKleine Sammlung von Ganzzahlen in Redis. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!