// 基于本地 Redis 仓 (unstable), src/intset.h + src/intset.c
typedef struct intset {
    uint32_t encoding;  // 当前元素宽度（2/4/8 字节），全体元素统一宽度，不搞变长
    uint32_t length;    // 元素个数
    int8_t contents[];  // 柔性数组：升序存放，没有任何 entry 头，元素之间零间隙
} intset;
// contents 声明成 int8_t 只是"按字节看"的占位，读写时按 encoding 强转成 int16/32/64 指针再定位

/* Note that these encodings are ordered, so:
 * INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64. */
#define INTSET_ENC_INT16 (sizeof(int16_t))  // 编码值直接用字节宽度 2/4/8：天然有序，比大小即比宽窄，还能直接参与乘法算偏移
#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;
}

/* Return the value at pos, given an encoding. */
static int64_t _intsetGetEncoded(intset *is, int pos, uint8_t enc) {
    int64_t v64;
    int32_t v32;
    int16_t v16;

    if (enc == INTSET_ENC_INT64) {
        memcpy(&v64,((int64_t*)is->contents)+pos,sizeof(v64));  // 强转指针只为算步长，取值走 memcpy：某些平台未对齐访问会直接崩
        memrev64ifbe(&v64);     // ifbe = if big endian：内存里统一按小端存，大端机读写时翻转，小端机上是空操作
        return v64;
    } else if (enc == INTSET_ENC_INT32) {
        memcpy(&v32,((int32_t*)is->contents)+pos,sizeof(v32));
        memrev32ifbe(&v32);
        return v32;
    } else {
        // ... int16 分支同构
    }
}
// _intsetGet(is,pos) 就是 _intsetGetEncoded(is,pos,当前encoding)；_intsetSet(is,pos,value) 反向写入同一套宽度分发，略

/* Create an empty intset. */
intset *intsetNew(void) {
    intset *is = zmalloc(sizeof(intset));
    is->encoding = intrev32ifbe(INTSET_ENC_INT16);  // 从最窄的 int16 起步，之后只升不降
    is->length = 0;
    return is;
}

/* Resize the intset */
static intset *intsetResize(intset *is, uint32_t len) {
    uint64_t size = (uint64_t)len*intrev32ifbe(is->encoding);   // 先提升到 64 位再乘，防 32 位溢出
    assert(size <= SIZE_MAX - sizeof(intset));
    is = zrealloc(is,sizeof(intset)+size);  // 精确分配，不预留冗余容量（对比 Java ArrayList 的 1.5 倍扩容）
    return is;
}

// 基于本地 Redis 仓 (unstable), src/intset.c
/* Search for the position of "value". Return 1 when the value was found and
 * sets "pos" to the position of the value within the intset. Return 0 when
 * the value is not present in the intset and sets "pos" to the position
 * where "value" can be inserted. */
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 */
    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. */
        if (value > _intsetGet(is,max)) {   // 比最大还大直接尾插：SADD 递增 ID 是最常见模式，把它从 O(logN) 压到 O(1)
            if (pos) *pos = intrev32ifbe(is->length);
            return 0;
        } else if (value < _intsetGet(is,0)) {
            if (pos) *pos = 0;
            return 0;
        }
    }

    while(max >= min) {
        mid = ((unsigned int)min + (unsigned int)max) >> 1; // 转 unsigned 再移位，防 min+max 溢出成负数（JDK 二分用 >>> 修的同一个坑）
        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;    // 没找到时 min 恰好是插入点，intsetAdd 拿它直接落位，不用二次定位
        return 0;
    }
}

/* 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);   // 原地 realloc 到新宽度，此刻旧数据还按窄宽度挤在缓冲区前段

    /* 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); // prepend=1 时上面搬运整体右移了一格，下标 0 正好空出来
    else
        _intsetSet(is,intrev32ifbe(is->length),value);
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

static void intsetMoveTail(intset *is, uint32_t from, uint32_t to) {
    void *src, *dst;
    uint32_t bytes = intrev32ifbe(is->length)-from;
    uint32_t encoding = intrev32ifbe(is->encoding);

    if (encoding == INTSET_ENC_INT64) {
        src = (int64_t*)is->contents+from;
        dst = (int64_t*)is->contents+to;
        bytes *= sizeof(int64_t);
    } else if (encoding == INTSET_ENC_INT32) {
        // ... int32 / int16 分支同构，只是步长不同
    }
    memmove(dst,src,bytes);     // 源与目标区间重叠，必须 memmove；memcpy 在重叠时是未定义行为
}

/* 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;  // Set 的去重就发生在这里：先查后插
            return is;
        }

        is = intsetResize(is,intrev32ifbe(is->length)+1);
        if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);   // pos 起的尾段整体右移一格腾位，O(N) 是有序数组的代价
    }

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

/* Delete integer from intset */
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);    // 内存立刻收缩，但 encoding 永不降级：删光大数也回不到 int16
        is->length = intrev32ifbe(len-1);
    }
    return is;
}

/* Determine whether a value belongs to this set */
uint8_t intsetFind(intset *is, int64_t value) {
    uint8_t valenc = _intsetValueEncoding(value);
    return valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,NULL);  // 同样先按编码剪枝，剪掉时连 contents 都不用碰
}