整数集合

适用范围

整数集合提供了这样一个抽象：

1. 集合可以保存 int_16 、 int_32t 和 int_64 三种不同长度的整数。
2. 对集合保存值所使用的字长是由程序自动调整的，这个过程被称为“升级”。
3. 所有整数在集合中都是独一无二的，各个整数以从小到达的顺序在集合中排序，所以程序在集合中查找元素的复杂度为 。

整数集合的详细信息和操作 API 可以参考 《Redis 设计与实现》 的相关章节。

准备步骤

1. 从 Redis 源码中复制 endianconv.c 、 endianconv.h 、 intset.c 、 intset.h 、 zmalloc.c 和 zmalloc.h 到目标文件夹。
2. 将 #include "config.h" 从 zmalloc.c 中删除。
3. 将 #include <stddef.h> 加入到 intset.h ，解决 size_t 未定义的问题。

测试驱动程序

以下程序对整数集合进行了三项测试：

1. 创建并删除一个空集合
2. 对集合进行添加、删除和查找操作
3. 检查整数集合的升级状态

// main.c

#include <stdlib.h> // 载入 NULL
#include <assert.h>

#include "intset.h"
#include "endianconv.h"

// Redis 将以下常量定义在了 intset.c
// 所以我们需要重新定义一次
// 如果将 intset.c 中的这些定义移动到 intset.h 
// 那么这里的定义就可以省去了
#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

void test_create_and_destroy_intset(void)
{
    intset *is = intsetNew();
    
    assert(
        is != NULL
    );

    assert(
        intsetLen(is) == 0
    );

    zfree(is);
}

void test_add_remove_and_find_element_in_intset(void)
{
    intset *is = intsetNew();

    assert(
        is != NULL
    );

    uint8_t success = 0;

    // add element
    is = intsetAdd(is, 1, &success);
    assert(
        success == 1 &&
        intsetLen(is) == 1
    );

    // add another element
    is = intsetAdd(is, 2, &success);
    assert(
        success == 1 &&
        intsetLen(is) == 2
    );

    // existsed element won't be add again
    is = intsetAdd(is, 2, &success);
    assert(
        success == 0 &&
        intsetLen(is) == 2
    );

    // remove 2 from is
    int int_success = 0;
    is = intsetRemove(is, 2, &int_success);
    assert(
        int_success == 1 &&
        intsetLen(is) == 1 &&
        intsetFind(is, 2) == 0
    );

    zfree(is);
}

void test_intset_upgrade(void)
{
    intset *is = intsetNew();

    is = intsetAdd(is, 32, NULL);
    assert(
        intrev32ifbe(is->encoding) == INTSET_ENC_INT16
    );

    is = intsetAdd(is, 65535, NULL);
    assert(
        intrev32ifbe(is->encoding) == INTSET_ENC_INT32
    );

    is = intsetAdd(is, 4294967295u, NULL);
    assert(
        intrev32ifbe(is->encoding) == INTSET_ENC_INT64
    );

    zfree(is);
}

void main(void)
{

    test_create_and_destroy_intset();

    test_add_remove_and_find_element_in_intset();

    test_intset_upgrade();

}

完成源码

测试程序的完整源码可以在 这里 的 intset 文件夹找到。

留言

comments powered by Disqus