skiplist

一、跳表简介

　　跳表（Skiplist）是一个特殊的链表，相比一般的链表，有更高的查找效率，可比拟二叉查找树，平均期望的查找、插入、删除时间复杂度都是O(logn)，许多知名的开源软件（库）中的数据结构均采用了跳表这种数据结构。

Redis中的有序集合zset
LevelDB、RocksDB、HBase中Memtable
ApacheLucene中的TermDictionary、Posting List

下面记录一个跳表实现：

  1 #include "list.h"
  2 #include <stdio.h>
  3 #include <stdlib.h>
  4 #include <string.h>
  5 
  6 #define SKIPLIST_MAXLEVEL 32 /* Should be enough for 2^32 elements */
  7 #define SKIPLIST_P 0.25      /* Skiplist P = 1/4 */
  8 
  9 typedef struct skiplist
 10 {
 11     int              level;
 12     int              count;
 13     struct list_head head[SKIPLIST_MAXLEVEL];
 14 } skipList;
 15 
 16 typedef struct skipnode
 17 {
 18     int              key;
 19     int              value;
 20     struct list_head forward[0];
 21 } skipNode;
 22 
 23 #define skiplist_foreach(pos, end) 
 24         for (; pos != end; pos = pos->next)
 25 
 26 #define skiplist_foreach_safe(pos, n, end) 
 27         for (n = pos->next; pos != end; pos = n, n = pos->next)
 28 
 29 static int find_count = 0;
 30 
 31 skipNode* skipnode_new(int level, int key, int value)
 32 {
 33     skipNode* node = NULL;
 34 
 35     node = malloc(sizeof(skipNode) + level * sizeof(skipList));
 36     if (NULL == node) {
 37         return NULL;
 38     }
 39     node->key   = key;
 40     node->value = value;
 41 
 42     return node;
 43 }
 44 
 45 void skipnode_delete(skipNode* node)
 46 {
 47     if (node) {
 48         free(node);
 49         node = NULL;
 50     }
 51 }
 52 
 53 skipList* skiplist_new(void)
 54 {
 55     int       i    = 0;
 56     skipList* list = NULL;
 57 
 58     list = malloc(sizeof(skipList));
 59     if (NULL == list) {
 60         return NULL;
 61     }
 62 
 63     list->level = 1;
 64     list->count = 0;
 65     for (i = 0; i < SKIPLIST_MAXLEVEL; i++) {
 66         INIT_LIST_HEAD(&list->head[i]);
 67     }
 68     return list;
 69 }
 70 
 71 void skiplist_destory(skipList* list)
 72 {
 73     struct list_head* start = NULL;
 74     struct list_head* n     = NULL;
 75     skipNode*         pNode = NULL;
 76 
 77     if (list) {
 78         start = list->head[0].next;
 79 
 80         skiplist_foreach_safe(start, n, &list->head[0])
 81         {
 82             pNode = list_entry(start, skipNode, forward[0]);
 83             skipnode_delete(pNode);
 84         }
 85         free(list);
 86         list = NULL;
 87     }
 88 }
 89 
 90 int random_level(void)
 91 {
 92     int level = 1;
 93     while ((random() & 0xFFFF) < (SKIPLIST_P * 0xFFFF)) {
 94         level += 1;
 95     }
 96 
 97     return (level < SKIPLIST_MAXLEVEL) ? level : SKIPLIST_MAXLEVEL;
 98 }
 99 
100 skipNode* skiplist_search(skipList* list, int key)
101 {
102     struct list_head* start = NULL;
103     struct list_head* end   = NULL;
104     skipNode*         pNode = NULL;
105     int               i     = 0;
106 
107     if (NULL == list) {
108         return NULL;
109     }
110 
111     i     = list->level - 1;
112     start = &list->head[i];
113     end   = &list->head[i];
114     for (; i >= 0; i--) {
115         start = start->next;
116         skiplist_foreach(start, end)
117         {
118             find_count++;
119             pNode = list_entry(start, skipNode, forward[i]);
120             if (pNode->key >= key) {
121                 end = &pNode->forward[i];
122                 break;
123             }
124         }
125         if (pNode->key == key) {
126             return pNode;
127         }
128         start = end->prev;
129         start--;
130         end--;
131     }
132     return NULL;
133 }
134 
135 skipNode* skiplist_insert(skipList* list, int key, int value)
136 {
137     int               i       = 0;
138     int               level   = 0;
139     skipNode*         newNode = NULL;
140     skipNode*         pNode   = NULL;
141     struct list_head* start   = NULL;
142     struct list_head* end     = NULL;
143 
144     if (NULL == list) {
145         return NULL;
146     }
147 
148     level = random_level();
149     if (level > list->level) {
150         list->level = level;
151     }
152 
153     newNode = skipnode_new(level, key, value);
154     if (NULL == newNode) {
155         return NULL;
156     }
157 
158     i     = list->level - 1;
159     start = &list->head[i];
160     end   = &list->head[i];
161     for (; i >= 0; i--) {
162         start = start->next;
163         skiplist_foreach(start, end)
164         {
165             pNode = list_entry(start, skipNode, forward[i]);
166             if (pNode->key >= key) {
167                 end = &pNode->forward[i];
168                 break;
169             }
170         }
171         start = end->prev;
172         if (i < level) {
173             list_add_tail(&newNode->forward[i], end);
174         }
175         end--;
176         start--;
177     }
178     list->count++;
179 
180     return newNode;
181 }
182 
183 static void _remove(skipList* list, skipNode* node, int level)
184 {
185     int i = 0;
186     for (i = 0; i < level; i++) {
187         list_del(&node->forward[i]);
188         if (list_empty(&list->head[i])) {
189             list->level--;
190         }
191     }
192     skipnode_delete(node);
193     list->count--;
194 }
195 
196 void skiplist_remove(skipList* list, int key)
197 {
198     int               i     = 0;
199     struct list_head* start = NULL;
200     struct list_head* end   = NULL;
201     struct list_head* n     = NULL;
202     skipNode*         pNode = NULL;
203 
204     if (NULL == list) {
205         return;
206     }
207 
208     i     = list->level - 1;
209     start = &list->head[i];
210     end   = &list->head[i];
211     for (; i >= 0; i--) {
212         start = start->next;
213         skiplist_foreach_safe(start, n, end)
214         {
215             pNode = list_entry(start, skipNode, forward[i]);
216             if (pNode->key > key) {
217                 end = &pNode->forward[i];
218                 break;
219             }
220             else if (pNode->key == key) {
221                 _remove(list, pNode, i + 1);
222             }
223         }
224         start = end->prev;
225         start--;
226         end--;
227     }
228 }
229 
230 void skiplist_dump(skipList* list)
231 {
232     int               i     = 0;
233     struct list_head* start = NULL;
234     struct list_head* end   = NULL;
235     skipNode*         pNode = NULL;
236 
237     if (NULL == list) {
238         return;
239     }
240 
241     i     = list->level - 1;
242     start = &list->head[i];
243     end   = &list->head[i];
244     for (; i >= 0; i--) {
245         start = start->next;
246         skiplist_foreach(start, end)
247         {
248             pNode = list_entry(start, skipNode, forward[i]);
249             printf("%5d ", pNode->key);
250         }
251         start = &list->head[i];
252         start--;
253         end--;
254         printf("
");
255     }
256 }
257 
258 int main(int argc, char** argv)
259 {
260     int       i        = 0;
261     skipList* skiplist = NULL;
262     skipNode* pNode    = NULL;
263     int       key      = 0;
264 
265     skiplist = skiplist_new();
266     if (NULL == skiplist) {
267         printf("skiplist is null");
268         return -1;
269     }
270 
271     for (i = 0; i < 10000; i++) {
272         skiplist_insert(skiplist, i, i);
273     }
274 
275     key   = 5000;
276     pNode = skiplist_search(skiplist, key);
277     if (pNode) {
278         printf("key: %d found, find times: %d
", key, find_count);
279     }
280     else {
281         printf("key:%d, not found
", key);
282     }
283 
284     key   = 9999;
285     pNode = skiplist_search(skiplist, key);
286     if (pNode) {
287         printf("key: %d found, find times: %d
", key, find_count);
288     }
289     else {
290         printf("key:%d, not found
", key);
291     }
292 
293     skiplist_destory(skiplist);
294 
295     return 0;
296 }

可以看出，跳表在查找、插入、删除时性能更好

/*
[zhangwj@xxx skiplist]$ ./a.out 
key: 5000 found, find times: 20
key: 9999 found, find times: 31
[zhangwj@xxx skiplist]$ 
*/