redis源码从main开始14

同样的zset类型对象也有两种编码方式,一种是压缩列表,一种是跳表

#define REDIS_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
#define REDIS_ENCODING_SKIPLIST 7  /* Encoded as skiplist */


// 有序集合的定义结构体
typedef struct zset {
    // 字典，键为成员，值为分值
    // 用于支持 O(1) 复杂度的按成员取分值操作
    dict *dict;
    // 跳跃表，按分值排序成员
    // 用于支持平均复杂度为 O(log N) 的按分值定位成员操作以及范围操作
    zskiplist *zsl;
} zset;


以下为两种编码方式的zset对象的创建方式

// 创建跳表的有序集合
robj *createZsetObject(void) {
    zset *zs = zmalloc(sizeof(*zs));
    robj *o;
    zs->dict = dictCreate(&zsetDictType,NULL);
    zs->zsl = zslCreate();
    o = createObject(REDIS_ZSET,zs);
    o->encoding = REDIS_ENCODING_SKIPLIST;
    return o;
}

// 创建压缩列表的有序集合
robj *createZsetZiplistObject(void) {
    unsigned char *zl = ziplistNew();
    robj *o = createObject(REDIS_ZSET,zl);
    o->encoding = REDIS_ENCODING_ZIPLIST;
    return o;
}



// 下面先来看编码方式为跳表的zset对象的创建过程

//第一步 创建字典,与set的不同是传入的字典类型不一样
zs->dict = dictCreate(&zsetDictType,NULL);


//第二步, 创建跳表结构
 zs->zsl = zslCreate();

// 创建跳跃表
zskiplist *zslCreate(void) {
    int j;
    zskiplist *zsl;

    // 分配空间
    zsl = zmalloc(sizeof(*zsl));
    zsl->level = 1; 
    zsl->length = 0;

    // 初始化表头节点
    zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
    for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
        zsl->header->level[j].forward = NULL;
        zsl->header->level[j].span = 0;
    }
    zsl->header->backward = NULL;
    zsl->tail = NULL;
    return zsl;
}

//跳表的结构体
typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 头结点和尾节点
    unsigned long length;     // 表中节点的数量
    int level;     // 表中层数最大的节点的层数
} zskiplist;


//跳表节点的结构体
typedef struct zskiplistNode {
    robj *obj;     // 成员对象
    double score;      // 分值
    struct zskiplistNode *backward;     // 后退指针
    struct zskiplistLevel {     // 层
        struct zskiplistNode *forward;         // 前进指针
        unsigned int span;         // 跨度
    } level[];
} zskiplistNode;

//第三步 创建zset对象
    o = createObject(REDIS_ZSET,zs);
//第四部 设置编码为REDIS_ENCODING_SKIPLIST


//下面我们看压缩列表方式的有序集合

//第一步 创建压缩列表 相关内容在列表对象中讲过了
unsigned char *zl = ziplistNew();

//第二步 创建zset对象
robj *o = createObject(REDIS_ZSET,zl);

// 第三步 设置编码方式为压缩列表
o->encoding = REDIS_ENCODING_ZIPLIST;

基于版本3.0.0版本,点击下载https://download.redis.io/releases/redis-3.0.0.tar.gz

本文地址，https://www.ccagml.com/?p=420