typedef struct zskiplist {
    //表头的头指针header和尾指针tail
    struct zskiplistNode *header, *tail;
    //一共有多少个节点length
    unsigned long length;
    // 所有节点最大的层级level
   int level;
} zskiplist;

//跳表的具体节点 
typedef struct zskiplistNode {
    sds ele; //具体的数据，对应张三
    double score;//分数，对应70
    struct zskiplistNode *backward;//后退指针backward
     //层级数组    struct zskiplistLevel {
        struct zskiplistNode *forward;//前进指针forward
        unsigned int span;//跨度span
    } level[];
} zskiplistNode; 

//创建一个空表头的跳跃表
zskiplist *zslCreate(void) {
    int j;
    zskiplist *zsl;
    //尝试分配内存空间
    zsl = zmalloc(sizeof(*zsl));
    //初始化level和length
    zsl->level = 1;
    zsl->length = 0;
    //调用下面的方法zslCreateNode,传入的参数有数组长度ZSKIPLIST_MAXLEVEL 32
    //分数0，对象值NuLL
    //这一步就是创建管理所有节点的数组
    //并且设置表头的头头指针为此对象的地址
    zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
    //为这32个数组赋值前指针forward和跨度span
    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;
}
zskiplistNode *zslCreateNode(int level, double score, sds ele) {
    zskiplistNode *zn =
        zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
    zn->score = score;
    zn->ele = ele;
    return zn;
}

//插入节点，输入参数为
//zsl:表头
//score:插入元素的分数score
//ele:插入元素的具体数据ele
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
    //使用update数组记录每层待插入元素的前一个元素
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    //记录前置节点与第一个节点之间的跨度，即元素在列表中的排名-1
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    int i, level;

    serverAssert(!isnan(score));
    x = zsl->header;
    //从最大的level开始遍历，从顶到底，找到每一层待插入的位置
    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];
    //直接找到第一个分数比该元素大的位置
    //或者分数与该元素相同但是对象的ASSICC码比该元素大的位置
        while (x->level[i].forward &&
                (x->level[i].forward->score < score ||
                    (x->level[i].forward->score == score &&
                    sdscmp(x->level[i].forward->ele,ele) < 0)))
        {
            //将已走过元素的跨越元素进行计数，得到元素在列表中排名，或者是已搜寻的路径长度
            rank[i] += x->level[i].span;
            x = x->level[i].forward;
        }
    //记录待插入位置
        update[i] = x;
    }
     //随机产生一个层数，在1到32之间，层数越高，生成的概率越低
    level = zslRandomLevel();
    //如果产生的层数大于现有的最高层数，则超出层数都需要初始化
    if (level > zsl->level) {
        //开始循环
        for (i = zsl->level; i < level; i++) {
            rank[i] = 0;
            //该元素作为这些层的第一个节点，前节点就是header
            update[i] = zsl->header;
            //初始化后这些层每层有两个元素，走一步就是跨越所有元素
            update[i]->level[i].span = zsl->length;
        }
        zsl->level = level;
    }
    //创建节点
    x = zslCreateNode(level,score,ele);
    for (i = 0; i < level; i++) {
        //将新节点插入到各层链表中
        x->level[i].forward = update[i]->level[i].forward;
        update[i]->level[i].forward = x;

        // rank[0]是第0层的前置节点P1（也就是底层插入节点前面那个节点）与第一个节点的跨度
        // rank[i]是第i层的前置节点P2（这一层里在插入节点前面那个节点）与第一个节点的跨度
        // 插入节点X与后置节点Y的跨度f(X,Y)可由以下公式计算
        // 关键在于f(P1,0)-f(P2,0)+1等于新节点与P2的跨度，这是因为跨度呈扇形形向下延伸到最底层
        // 记录节点各层跨越元素情况span, 由层与层之间的跨越元素总和rank相减而得
        x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
               // 插入位置前一个节点的span在原基础上加1即可(新节点在rank[0]的后一个位置)

 update[i]->level[i].span = (rank[0] - rank[i]) + 1;
    }

    /* increment span for untouched levels */
    for (i = level; i < zsl->level; i++) {
        update[i]->level[i].span++;
    }
    // 第0层是双向链表, 便于redis常支持逆序类查找
    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;
}

int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

//得到节点的排名
//输入参数为表头结构zsl，分数score，真正的数据ele
unsigned long zslGetRank(zskiplist *zsl, double score, sds ele) {
    zskiplistNode *x;
    unsigned long rank = 0;
    int i;
    //先获取表头的头指针，即找到管理所有节点的level数组
    x = zsl->header;
     //从表头的level，即最大值开始循环遍历
    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 &&
                sdscmp(x->level[i].forward->ele,ele) <= 0))) {
            rank += x->level[i].span;
            x = x->level[i].forward;
        }

        //确保在第i层找到分值相同，且对象相同时才会返回排位值
        if (x->ele && sdscmp(x->ele,ele) == 0) {
            return rank;
        }
    }
    return 0;
}