redis源码从main开始16

本章来看跳跃表

#define ZSKIPLIST_MAXLEVEL 32 // 跳跃表最大层数

// 跳表结构体
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;

// 创建一个跳表 // 最坏 O(1)
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;
}

//创建一个跳跃表的结点 //最坏 O(1)
zskiplistNode *zslCreateNode(int level, double score, robj *obj)
{
    // 分配空间
    zskiplistNode *zn = zmalloc(sizeof(*zn) + level * sizeof(struct zskiplistLevel));

    // 设置属性
    zn->score = score;
    zn->obj = obj;

    return zn;
}

// 插入一个节点 //最坏 O(N) 平均 O(logN)
zskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj)
{
    // update 每一层要更新的位置的节点
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    int i, level;
    redisAssert(!isnan(score));
    x = zsl->header;
    for (i = zsl->level - 1; i >= 0; i--)
    {
        /* store rank that is crossed to reach the insert position */
        rank[i] = i == (zsl->level - 1) ? 0 : rank[i + 1];
        // 沿着前进指针遍历跳跃表
        while (x->level[i].forward && (x->level[i].forward->score < score || (x->level[i].forward->score == score && compareStringObjects(x->level[i].forward->obj, obj) < 0)))
        {
            // 记录沿途跨越了多少个节点
            rank[i] += x->level[i].span;
            x = x->level[i].forward;
        }
        // 记录将要和新节点相连接的节点
        update[i] = x;
    }
    // 获取一个随机值作为新节点的层数
    level = zslRandomLevel();

    // 如果新节点的层数比表中其他节点的层数都要大
    // 那么初始化表头节点中未使用的层，并将它们记录到 update 数组中
    // 将来也指向新节点
    if (level > zsl->level)
    {

        // 初始化未使用层
        for (i = zsl->level; i < level; i++)
        {
            rank[i] = 0;
            update[i] = zsl->header;
            update[i]->level[i].span = zsl->length;
        }

        // 更新表中节点最大层数
        zsl->level = level;
    }

    // 创建新节点
    x = zslCreateNode(level, score, obj);

    // 将前面记录的指针指向新节点，并做相应的设置
    for (i = 0; i < level; i++)
    {
        // 设置新节点的 forward 指针
        x->level[i].forward = update[i]->level[i].forward;

        // 将沿途记录的各个节点的 forward 指针指向新节点
        update[i]->level[i].forward = x;

        /* update span covered by update[i] as x is inserted here */
        // 计算新节点跨越的节点数量
        x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);

        // 更新新节点插入之后，沿途节点的 span 值
        // 其中的 +1 计算的是新节点
        update[i]->level[i].span = (rank[0] - rank[i]) + 1;
    }

    /* increment span for untouched levels */
    // 未接触的节点的 span 值也需要增一，这些节点直接从表头指向新节点
    for (i = level; i < zsl->level; i++)
    {
        update[i]->level[i].span++;
    }

    // 设置新节点的后退指针
    x->backward = (update[0] == zsl->header) ? NULL : update[0];
    if (x->level[0].forward)
        x->level[0].forward->backward = x;
    else
        zsl->tail = x;

    // 跳跃表的节点计数增一
    zsl->length++;

    return x;
}

// 删除给定的跳跃表节点   最坏 O(N)
void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update)
{
    int i;

    // 更新所有和被删除节点 x 有关的节点的指针，解除它们之间的关系
    for (i = 0; i < zsl->level; i++)
    {
        if (update[i]->level[i].forward == x)
        {
            update[i]->level[i].span += x->level[i].span - 1;
            update[i]->level[i].forward = x->level[i].forward;
        }
        else
        {
            update[i]->level[i].span -= 1;
        }
    }

    // 更新被删除节点 x 的前进和后退指针
    if (x->level[0].forward)
    {
        x->level[0].forward->backward = x->backward;
    }
    else
    {
        zsl->tail = x->backward;
    }

    // 更新跳跃表最大层数（只在被删除节点是跳跃表中最高的节点时才执行）
    while (zsl->level > 1 && zsl->header->level[zsl->level - 1].forward == NULL)
        zsl->level--;

    // 跳跃表节点计数器减一
    zsl->length--;
}

/* Find the rank for an element by both score and key.
 * Returns 0 when the element cannot be found, rank otherwise.
 * Note that the rank is 1-based due to the span of zsl->header to the
 * first element. 
 *
 * T_wrost = O(N), T_avg = O(log N)
 */
unsigned long zslGetRank(zskiplist *zsl, double score, robj *o)
{
    zskiplistNode *x;
    unsigned long rank = 0;
    int i;

    // 遍历整个跳跃表
    x = zsl->header;
    for (i = zsl->level - 1; i >= 0; i--)
    {

        // 遍历节点并对比元素
        while (x->level[i].forward &&
               (x->level[i].forward->score < score ||
                // 比对分值
                (x->level[i].forward->score == score &&
                 // 比对成员对象
                 compareStringObjects(x->level[i].forward->obj, o) <= 0)))
        {

            // 累积跨越的节点数量
            rank += x->level[i].span;

            // 沿着前进指针遍历跳跃表
            x = x->level[i].forward;
        }

        /* x might be equal to zsl->header, so test if obj is non-NULL */
        // 必须确保不仅分值相等，而且成员对象也要相等
        // T = O(N)
        if (x->obj && equalStringObjects(x->obj, o))
        {
            return rank;
        }
    }

    // 没找到
    return 0;
}

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

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