What does the skiplistnode variable "span" mean in redis.h?
algorithm, data-structures, redis, skip-lists
Solution
`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.
Problem
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?