“This is my 33rd day of participating in the First Challenge 2022. For details: First Challenge 2022.”

Integer set (intSet)

Intset is a redis data type used to store a set of integers as 16, 32, or 64, and ensure that there are no duplicate elements in the set.

/* Note that these encodings are ordered, so: * INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64. */
#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;
}
Copy the code

The inset.h/intset structure represents a collection of integers:

// uint32_t encoding; // Uint32_t length; Int8_t contents[]; } intset;Copy the code

A set of integers containing five integer values of type INT16_t:

Data manipulation

1. Data search

Intset search (intsetSearch) is a half-split search with time order (logN).

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; }}Copy the code

2. Insert and upgrade

When an inserted element is larger than the current intSET type, it is upgraded to prevent overflow. For example, adding an integer value of type INT64_t to a set of integers whose underlying value is int_16_t converts all existing genera of the set to int64_t.

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

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

    _intsetSet(is,pos,value);
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}
Copy the code

Upgrade and add a new element to intSet. The code looks like this:

/* 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);
    int prepend = value < 0 ? 1 : 0;
    
    /* First set new encoding and resize */
    is->encoding = intrev32ifbe(newenc);
    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;
}
Copy the code

There are three steps to upgrade the collection of integers and add new elements:

1) According to the type of the new element, expand the space size of the underlying array of the integer set, and allocate space for the new element.

2) Convert all the existing elements of the underlying array to the same type of the new original, and place the converted elements in the correct bit. In the process of placing elements, the ordered nature of the array shall remain unchanged.

3) Add new elements to the underlying array.

Advantages of intSet operation

  1. Increased flexibility

The underlying array can be automatically upgraded to accommodate new elements, so arbitrary types can be added to the collection without having to indulge in type errors

  1. To save memory

Different types use different types of space to store them to avoid space waste

  • Demotion: Demotion is not supported
  • Add and remove

All require realLOc operations, so use with caution.