下面进入跳表的具体实现，以下代码位于z_set.c

先忽略插入与删除中对span相关的调整操作，下一篇会专门对span进行解释后再继续跳表的后续剖析

以下是两个基本的创建函数

image.png
1557066756673388.png

创建一个跳表节点，不多说

image.png
1557066868184478.png

创建整个跳表。设置跳表的初始最大层高为1，长度为0。创建一个score为0，sds字符串数据域为NULL的头结点，同时该头节点的的高度应设为高度最大值，因为要保证未来无论出现多高的节点都不应高过头节点。最后把头节点的backward指针指向NULL，又因为当前跳表中还没有元素，故尾节点tail填充为NULL。

以下是两个基本的销毁函数

image.png
1557067552157438.png

销毁一个节点。先销毁节点上的sds字符串，再销毁节点本身。

image.png
1557067642919475.png

销毁整个跳表。头节点直接调用zfree而不是zslFreeNode，因为头节点并不需要释放节点本身，其上没有需要主动释放的sds字符串。在其他节点一一被zslFreeNode释放后释放整个跳表结构。

image.png
1557067878784755.png

随机一个层数，不多说

在创建与释放后我们来看插入与删除的基本操作

插入分为两步

1、搜索更新点

2、通过更新点进行插入

以下为搜索更新点的逻辑

image.png
1557145067904406.png

以下为实际插入的逻辑

image.png
1557145050441256.png

以下是基本的删除操作

image.png
1557143997839121.png

删除一个元素

接下来是删除一个节点的实现，这只一个跳表的内部函数，被跳表的其它函数调用

image.png
1557301139112662.png

image.png
1557228062323264.png

关于zrangespec结构有必要再具体说一下，其中min，max表示范围的区间断点很显然，至于minex与maxex则是表示是否取端点min、max，当minex被设置为非0时不取min端点，maxex被设置为非0时不取max端点，例如当判断一个score是否在某个区间内会通过如下两个函数进行判断

image.png
1557228513321741.png

如下利用这两个函数实现判断整个跳表至少与一个区间有一部分交集

image.png
1557228685343386.png

  • 若是跳表本身中还无元素，说明跳表与区间不会有交集

  • 若跳表尾端的score小于（或小于等于）区间的左端，说明跳表与区间不会有交集

  • 若跳表中第一个节点大于（或大于等于）区间的右端，说明跳表与区间不会有交集

利用该函数实现返回跳表中第一个在range区间中的节点

image.png
1557230851885389.png

类似的实现，返回跳表中最后一个在区间range中的节点

image.png
1557231260248015.png

删除score在range区间内的所有节点

image.png
1557232998892086.png

剩下的一些实现与span有关，在下一篇详细讲解