What does the skiplistnode variable “span” mean in redis.h?

Question

In redis.h, the skipnode is defined as below:

typedef struct zskiplistNode {
    robj *obj;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned int span;
    } level[];
} zskiplistNode;

What does the var span mean? What does this var store?

Answer 1

span at a particular node stores the number of nodes between the current node and node->forward at the current level. span is used to calculate the 1-based rank of element in the skip list.

For example, consider the following skip list :

Consider the head node. The span at all levels will be 1.

Consider node 1. At level 0, the span is 1, because you will span 1 element if you follow the forward pointer. At level 1, span is 2 because you will span 2 elements (node 2 and node 3) if you follow the forward pointer.

Take a look at the function zslGetRank in t_zet.c. You can see how the rank is calculated from the value of span at each level.