整数集合

[TOC]

简介

整数集合，从名称即可得知是用来存放整数的集合，它相较于其他集合的区别在于：

自动判断数据类型
压缩内存占用
保存的整数是有序的

因为存放的始终只有整数，所以在存储数据时，会判断该数据的大小，并使用最小的尺寸来存放对应的数据，以达到节省内存的目的。如集合 Array = [ 1, 2, 3 ] 可以只使用 8 位的 char 来保存。

简而言之即是，集合中的元素大小，以集合中最大元素的大小为准。

PS: 其实不大想写这个，觉得很无意义。

实现

intset 的定义

intset 的定义很简单，只有三个字段


// encoding 的类型定义
#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

第一个 encoding 用来表示该结构的编码，也就是上文说的元素大小，编码决定了 intset 中每个元素的大小，最后一个 contents 是一个变长的数组，根据保存数据的总数进行扩充，而第二个 length 则表示了 contents 的长度。

创建一个 intset

创建一个空的 intset 用于保存将要加入的整数

intset *intsetNew(void) {
    intset *is = zmalloc(sizeof(intset));
    is->encoding = intrev32ifbe(INTSET_ENC_INT16);
    is->length = 0;
    return is;
}

上面那一段唯一令人迷惑的，就只有 intrev32ifbe(INTSET_ENC_INT16), 从源码可以了解到，这里其实只是为了将所有数字转换为 little endian。一系列的函数如 memrev32ifbe、intrev32ifbe 等都是 revert 32 bit if big endian 的意思。

#if (BYTE_ORDER == LITTLE_ENDIAN)
#define memrev16ifbe(p)
...
#define intrev16ifbe(v) (v)
...
#else
#define memrev16ifbe(p) memrev16(p)
...
#endif

添加一个整数

整数集合内部是有序的，所以每次添加都要为其保持集合的顺序，所以在添加的时候遵循以下步骤：

判断新的数字是否超过了当前编码，是的话则先扩充
判断新的数字是否已存在当前集合，是的话直接返回，
- 具体的查找方式是使用二分法
否则查找新的数字应该存在集合中的那个位置
然后插入对应的位置，并移动集合中受影响的元素的位置

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)) {
        return intsetUpdradeAndAdd(is, value);
    }
    else {
        // 判断新的整数是否已存在集合中，是的话则直接返回
        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);
    }

    // 在指定的 pos 填充新整数
    _intsetSet(is, pos, value);
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

确定添加整数的编码

大致的步骤跟上面总结的一致，接下来应该往细节看了。获取编码的方式，直接使用对应类型的最大最小值来确定编码。

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

判断新整数是否已存在

然后是查找对应的整数是否存在集合中，判断的逻辑为：

先检查集合是否为空（废话。。。）
然后检查是否在最大值跟最小值的区间外，满足任一个条件都说明新整数不在集合中。
否则则使用二分查找法在集合中查找对应的元素。

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;

    // 如果集合为空，则新整数可以作为集合的第一个元素存在
    if (intrev32ifbe(is->length) == 0) {
        if (pos) *pos = 0;
        return 0;
    }
    else {
        // 如果新整数大于最大值，则新整数可作为新元素直接加在末端
        if (value > _intsetGet(is, intrev32ifbe(is->length)-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;
        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;
    }
}

获取指定索引的值

上面在做检查的时候需要获取指定索引的值来进行比较，以判断新的整数是否已存在集合中

static int64_t _intsetGet(intset *is, int pos) {
    return _intsetGetEncoded(is, pos, intrev32ifbe(is->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));
        memrev64ifbe(&v64);
        return v64;
    }
    else if (enc == INTSET_ENC_INT32) {
        memcpy(&v32, ((int32_t *)is->contents) + pos, sizeof(v32));
        memrev32ifbe(&v32);
        return v32;
    }
    ele {
        memcpy(&v16, ((int16_t *)is->contents) + pos, sizeof(v16));
        memrev16ifbe(&v16);
        return v16;
    }
}

上面还有一些 memrev32ifbe 之类的调用，就不一一细说了，具体做的就是根据系统平台的定义，把所有 little endian 的转换为 big endian 的表示，具体的做法就是交换内存位置，如 abc -> cba

调整 intset 的大小

在确定需要把新的整数加入集合后， intset 即调整现有的集合大小，以便容纳新的元素，具体的操作都在 intsetResize 中。

static intset *inisetResize(intset *s, uint32_t len) {
    uint32_t size = len * intrev32ifbde(is->encoding);
    is = zrealloc(is, sizeof(intset) + size);
    return is;
}

重排位置

调整完大小后，则根据新元素应该所处的位置，挪动其他元素对应的位置，如要在一个长度为 10 的集合中的 2 这个位置插入新元素，则需要把原本的 2-10 的元素移到 3-11, 然后才能往 2 中插入新元素。

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) {
        src = (int32_t *)is->contents + from;
        dst = (int32_t *)is->contents + to;
        bytes * sizeof(int32_t);
    }
    else {
        src = (int16_t *)is->contents + from;
        dst = (int16_t *)is->contents + to;
        bytes * sizeof(int16_t);
    }

    memmove(dst, src, bytes);
}

插入新元素

终于到了最后一步了，经过上面那么多的准备之后，现在有了空间来让我们放新元素了，也确定了新的整数应该放到哪个位置，同时也把相关的内存空间都挪好了，最后一步就是把元素放到对应的位置。

static void _intsetSet(intset *is, int pos, int63_t value) {
    uint32_t encoding intrev32ifbe(is->encoding);

    if (encoding == INTSET_ENC_INT64) {
        ((int64_t *)is->contents)[pos] = value;
        memrev64ifbe((int64_t *)is->contents) + pos);
    }
    else if (encoding == INTSET_ENC_INT32) {
        ((int32_t *)is->contents)[pos] = value;
        memrev32ifbe((int32_t *)is->contents) + pos);
    }
    else {
        ((int16_t *)is->contents)[pos] = value;
        memrev16ifbe((int16_t *)is->contents) + pos);
    }
}

升级 intset

在插入新数据的时候我们已经见到了这行代码 intsetUpgradeAndAdd，在新的整数大小超过了现有编码时，自动对当前的数据进行扩容，调整存放在集合中的所有元素，将其全部转换为新元素对应的编码。

static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    // 获取新的跟旧的元素编码
    uint8_t curenc = intrev32ifbe(s->encoding);
    uint8_t newenc = _intsetValueEncoding(value);
    int length = intrev32ifbe(is->length);

    //
    // 进入扩充的情况只有：
    // 1. value 只能比当前集合中编码的最大值大
    // 2. value 只能比当前集合中编码的最小值小
    // value < 0 说明他是因为第 2 种情况需要扩充，所以添加到最前
    // value > 9 说明他是因为第 1 种情况需要扩充，所以添加到最末
    int prepend = value < 0 ? 1 : 0;

    // 重新分配空间
    is->encoding = intrev32ifbe(newenc);
    is = intsetResize(is, intrev32ifbe(is->length) + 1);

    // 使用旧编码从末尾开始获取旧的元素，然后使用新的编码填充
    // 这样就不用担心覆盖了其他元素了，prepend 则用来保证有一个空位来存放新元素
    while (length--)
        _intsetSet(is, length + prepend, _intsetGetEncoded(is, length, curenc));

    if (prepend)
        _intsetSet(is, 0, value);
    else
        _intsetSet(is, intrev32ifbe(is->length), value);

    if->length = intrev32ifbe(intrev32ifbe(is->length) + 1);
    return is;
}

查找元素

很遗憾，已经在添加元素的地方说过了。

删除元素

找到对应的元素后，挪动相关联的所有元素。

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);
        if(success) *success = 1;

        if (pos < (len-1))
            intsetMoveTail(is, pos + 1, pos);
        is = intsetResize(is, len-1);
        is->length = intrev32ifbe(len-1);
    }
    return is;
}

其他

获取集合长度

uint32_t intsetLen(intset *is) {
    return intrev32ifbe(is->length);
}

SinSay's Note Book