1 |
/* ====================================================================== |
---|
2 |
* Copyright (c) 2000 Theo Schlossnagle |
---|
3 |
* All rights reserved. |
---|
4 |
* The following code was written by Theo Schlossnagle for use in the |
---|
5 |
* Backhand project at The Center for Networking and Distributed Systems |
---|
6 |
* at The Johns Hopkins University. |
---|
7 |
* |
---|
8 |
* This is a skiplist implementation to be used for abstract structures |
---|
9 |
* and is release under the LGPL license version 2.1 or later. A copy |
---|
10 |
* of this license can be found at http://www.gnu.org/copyleft/lesser.html |
---|
11 |
* ====================================================================== |
---|
12 |
*/ |
---|
13 |
|
---|
14 |
#include <stdio.h> |
---|
15 |
#include <stdlib.h> |
---|
16 |
#include <assert.h> |
---|
17 |
|
---|
18 |
#include "skiplist.h" |
---|
19 |
|
---|
20 |
#ifndef MIN |
---|
21 |
#define MIN(a,b) ((a<b)?(a):(b)) |
---|
22 |
#endif |
---|
23 |
|
---|
24 |
static int get_b_rand(void) { |
---|
25 |
static int ph=32; /* More bits than we will ever use */ |
---|
26 |
static unsigned long randseq; |
---|
27 |
if(ph > 31) { /* Num bits in return of lrand48() */ |
---|
28 |
ph=0; |
---|
29 |
randseq = lrand48(); |
---|
30 |
} |
---|
31 |
ph++; |
---|
32 |
return ((randseq & (1 << (ph-1))) >> (ph-1)); |
---|
33 |
} |
---|
34 |
|
---|
35 |
void sli_init(Skiplist *sl) { |
---|
36 |
sl->compare = (SkiplistComparator)NULL; |
---|
37 |
sl->comparek = (SkiplistComparator)NULL; |
---|
38 |
sl->height=0; |
---|
39 |
sl->preheight=0; |
---|
40 |
sl->size=0; |
---|
41 |
sl->top = NULL; |
---|
42 |
sl->bottom = NULL; |
---|
43 |
sl->index = NULL; |
---|
44 |
} |
---|
45 |
|
---|
46 |
static int indexing_comp(void *a, void *b) { |
---|
47 |
assert(a); |
---|
48 |
assert(b); |
---|
49 |
return (void *)(((Skiplist *)a)->compare)>(void *)(((Skiplist *)b)->compare); |
---|
50 |
} |
---|
51 |
static int indexing_compk(void *a, void *b) { |
---|
52 |
assert(b); |
---|
53 |
return a>(void *)(((Skiplist *)b)->compare); |
---|
54 |
} |
---|
55 |
|
---|
56 |
void sl_init(Skiplist *sl) { |
---|
57 |
sli_init(sl); |
---|
58 |
sl->index = (Skiplist *)malloc(sizeof(Skiplist)); |
---|
59 |
sli_init(sl->index); |
---|
60 |
sl_set_compare(sl->index, indexing_comp, indexing_compk); |
---|
61 |
} |
---|
62 |
|
---|
63 |
void sl_set_compare(Skiplist *sl, |
---|
64 |
SkiplistComparator comp, |
---|
65 |
SkiplistComparator compk) { |
---|
66 |
if(sl->compare && sl->comparek) { |
---|
67 |
sl_add_index(sl, comp, compk); |
---|
68 |
} else { |
---|
69 |
sl->compare = comp; |
---|
70 |
sl->comparek = compk; |
---|
71 |
} |
---|
72 |
} |
---|
73 |
|
---|
74 |
void sl_add_index(Skiplist *sl, |
---|
75 |
SkiplistComparator comp, |
---|
76 |
SkiplistComparator compk) { |
---|
77 |
struct skiplistnode *m; |
---|
78 |
Skiplist *ni; |
---|
79 |
int icount=0; |
---|
80 |
#ifdef SLDEBUG |
---|
81 |
fprintf(stderr, "Adding index to %p\n", sl); |
---|
82 |
#endif |
---|
83 |
sl_find(sl->index, (void *)comp, &m); |
---|
84 |
if(m) return; /* Index already there! */ |
---|
85 |
ni = (Skiplist *)malloc(sizeof(Skiplist)); |
---|
86 |
sli_init(ni); |
---|
87 |
sl_set_compare(ni, comp, compk); |
---|
88 |
/* Build the new index... This can be expensive! */ |
---|
89 |
m = sl_insert(sl->index, ni); |
---|
90 |
while(m->prev) m=m->prev, icount++; |
---|
91 |
for(m=sl_getlist(sl); m; sl_next(sl, &m)) { |
---|
92 |
int j=icount-1; |
---|
93 |
struct skiplistnode *nsln; |
---|
94 |
nsln = sl_insert(ni, m->data); |
---|
95 |
/* skip from main index down list */ |
---|
96 |
while(j>0) m=m->nextindex, j--; |
---|
97 |
/* insert this node in the indexlist after m */ |
---|
98 |
nsln->nextindex = m->nextindex; |
---|
99 |
if(m->nextindex) m->nextindex->previndex = nsln; |
---|
100 |
nsln->previndex = m; |
---|
101 |
m->nextindex = nsln; |
---|
102 |
} |
---|
103 |
} |
---|
104 |
|
---|
105 |
struct skiplistnode *sl_getlist(Skiplist *sl) { |
---|
106 |
if(!sl->bottom) return NULL; |
---|
107 |
return sl->bottom->next; |
---|
108 |
} |
---|
109 |
|
---|
110 |
void *sl_find(Skiplist *sl, |
---|
111 |
void *data, |
---|
112 |
struct skiplistnode **iter) { |
---|
113 |
void *ret; |
---|
114 |
struct skiplistnode *aiter; |
---|
115 |
if(!sl->compare) return 0; |
---|
116 |
if(iter) |
---|
117 |
ret = sl_find_compare(sl, data, iter, sl->compare); |
---|
118 |
else |
---|
119 |
ret = sl_find_compare(sl, data, &aiter, sl->compare); |
---|
120 |
return ret; |
---|
121 |
} |
---|
122 |
void *sl_find_compare(Skiplist *sli, |
---|
123 |
void *data, |
---|
124 |
struct skiplistnode **iter, |
---|
125 |
SkiplistComparator comp) { |
---|
126 |
struct skiplistnode *m = NULL; |
---|
127 |
Skiplist *sl; |
---|
128 |
if(comp==sli->compare || !sli->index) { |
---|
129 |
sl = sli; |
---|
130 |
} else { |
---|
131 |
sl_find(sli->index, (void *)comp, &m); |
---|
132 |
assert(m); |
---|
133 |
sl=m->data; |
---|
134 |
} |
---|
135 |
sli_find_compare(sl, data, iter, sl->comparek); |
---|
136 |
return (*iter)?((*iter)->data):(*iter); |
---|
137 |
} |
---|
138 |
int sli_find_compare(Skiplist *sl, |
---|
139 |
void *data, |
---|
140 |
struct skiplistnode **ret, |
---|
141 |
SkiplistComparator comp) { |
---|
142 |
struct skiplistnode *m = NULL; |
---|
143 |
int count=0; |
---|
144 |
m = sl->top; |
---|
145 |
while(m) { |
---|
146 |
int compared; |
---|
147 |
if(m->next) compared=comp(data, m->next->data); |
---|
148 |
if(compared == 0) { |
---|
149 |
#ifdef SL_DEBUG |
---|
150 |
printf("Looking -- found in %d steps\n", count); |
---|
151 |
#endif |
---|
152 |
m=m->next; |
---|
153 |
while(m->down) m=m->down; |
---|
154 |
*ret = m; |
---|
155 |
return count; |
---|
156 |
} |
---|
157 |
if((m->next == NULL) || (compared<0)) |
---|
158 |
m = m->down, count++; |
---|
159 |
else |
---|
160 |
m = m->next, count++; |
---|
161 |
} |
---|
162 |
#ifdef SL_DEBUG |
---|
163 |
printf("Looking -- not found in %d steps\n", count); |
---|
164 |
#endif |
---|
165 |
*ret = NULL; |
---|
166 |
return count; |
---|
167 |
} |
---|
168 |
void *sl_next(Skiplist *sl, struct skiplistnode **iter) { |
---|
169 |
if(!*iter) return NULL; |
---|
170 |
*iter = (*iter)->next; |
---|
171 |
return (*iter)?((*iter)->data):NULL; |
---|
172 |
} |
---|
173 |
void *sl_previous(Skiplist *sl, struct skiplistnode **iter) { |
---|
174 |
if(!*iter) return NULL; |
---|
175 |
*iter = (*iter)->prev; |
---|
176 |
return (*iter)?((*iter)->data):NULL; |
---|
177 |
} |
---|
178 |
struct skiplistnode *sl_insert(Skiplist *sl, |
---|
179 |
void *data) { |
---|
180 |
if(!sl->compare) return 0; |
---|
181 |
return sl_insert_compare(sl, data, sl->compare); |
---|
182 |
} |
---|
183 |
|
---|
184 |
struct skiplistnode *sl_insert_compare(Skiplist *sl, |
---|
185 |
void *data, |
---|
186 |
SkiplistComparator comp) { |
---|
187 |
struct skiplistnode *m, *p, *tmp, *ret, **stack; |
---|
188 |
int nh=1, ch, stacki; |
---|
189 |
#ifdef SLDEBUG |
---|
190 |
sl_print_struct(sl, "BI: "); |
---|
191 |
#endif |
---|
192 |
if(!sl->top) { |
---|
193 |
sl->height = 1; |
---|
194 |
sl->topend = sl->bottomend = sl->top = sl->bottom = |
---|
195 |
(struct skiplistnode *)malloc(sizeof(struct skiplistnode)); |
---|
196 |
assert(sl->top); |
---|
197 |
sl->top->next = sl->top->data = sl->top->prev = |
---|
198 |
sl->top->up = sl->top->down = |
---|
199 |
sl->top->nextindex = sl->top->previndex = NULL; |
---|
200 |
sl->top->sl = sl; |
---|
201 |
} |
---|
202 |
if(sl->preheight) { |
---|
203 |
while(nh < sl->preheight && get_b_rand()) nh++; |
---|
204 |
} else { |
---|
205 |
while(nh <= sl->height && get_b_rand()) nh++; |
---|
206 |
} |
---|
207 |
/* Now we have the new hieght at which we wish to insert our new node */ |
---|
208 |
/* Let us make sure that our tree is a least that tall (grow if necessary)*/ |
---|
209 |
for(;sl->height<nh;sl->height++) { |
---|
210 |
sl->top->up = |
---|
211 |
(struct skiplistnode *)malloc(sizeof(struct skiplistnode)); |
---|
212 |
assert(sl->top); |
---|
213 |
sl->top->up->down = sl->top; |
---|
214 |
sl->top = sl->topend = sl->top->up; |
---|
215 |
sl->top->prev = sl->top->next = sl->top->nextindex = |
---|
216 |
sl->top->previndex = NULL; |
---|
217 |
sl->top->data = NULL; |
---|
218 |
sl->top->sl = sl; |
---|
219 |
} |
---|
220 |
ch = sl->height; |
---|
221 |
/* Find the node (or node after which we would insert) */ |
---|
222 |
/* Keep a stack to pop back through for insertion */ |
---|
223 |
m = sl->top; |
---|
224 |
stack = (struct skiplistnode **)malloc(sizeof(struct skiplistnode *)*(nh)); |
---|
225 |
stacki=0; |
---|
226 |
while(m) { |
---|
227 |
int compared=-1; |
---|
228 |
if(m->next) compared=comp(data, m->next->data); |
---|
229 |
if(compared == 0) { |
---|
230 |
free(stack); |
---|
231 |
return 0; |
---|
232 |
} |
---|
233 |
if((m->next == NULL) || (compared<0)) { |
---|
234 |
if(ch<=nh) { |
---|
235 |
/* push on stack */ |
---|
236 |
stack[stacki++] = m; |
---|
237 |
} |
---|
238 |
m = m->down; |
---|
239 |
ch--; |
---|
240 |
} else { |
---|
241 |
m = m->next; |
---|
242 |
} |
---|
243 |
} |
---|
244 |
/* Pop the stack and insert nodes */ |
---|
245 |
p = NULL; |
---|
246 |
for(;stacki>0;stacki--) { |
---|
247 |
m = stack[stacki-1]; |
---|
248 |
tmp = (struct skiplistnode *)malloc(sizeof(struct skiplistnode)); |
---|
249 |
tmp->next = m->next; |
---|
250 |
if(m->next) m->next->prev=tmp; |
---|
251 |
tmp->prev = m; |
---|
252 |
tmp->up = NULL; |
---|
253 |
tmp->nextindex = tmp->previndex = NULL; |
---|
254 |
tmp->down = p; |
---|
255 |
if(p) p->up=tmp; |
---|
256 |
tmp->data = data; |
---|
257 |
tmp->sl = sl; |
---|
258 |
m->next = tmp; |
---|
259 |
/* This sets ret to the bottom-most node we are inserting */ |
---|
260 |
if(!p) ret=tmp; |
---|
261 |
p = tmp; |
---|
262 |
} |
---|
263 |
free(stack); |
---|
264 |
if(sl->index != NULL) { |
---|
265 |
/* this is a external insertion, we must insert into each index as well */ |
---|
266 |
struct skiplistnode *p, *ni, *li; |
---|
267 |
li=ret; |
---|
268 |
for(p = sl_getlist(sl->index); p; sl_next(sl->index, &p)) { |
---|
269 |
ni = sl_insert((Skiplist *)p->data, ret->data); |
---|
270 |
assert(ni); |
---|
271 |
#ifdef SLDEBUG |
---|
272 |
fprintf(stderr, "Adding %p to index %p\n", ret->data, p->data); |
---|
273 |
#endif |
---|
274 |
li->nextindex = ni; |
---|
275 |
ni->previndex = li; |
---|
276 |
li = ni; |
---|
277 |
} |
---|
278 |
} else { |
---|
279 |
sl->size++; |
---|
280 |
} |
---|
281 |
#ifdef SLDEBUG |
---|
282 |
sl_print_struct(sl, "AI: "); |
---|
283 |
#endif |
---|
284 |
return ret; |
---|
285 |
} |
---|
286 |
struct skiplistnode *sl_append(Skiplist *sl, void *data) { |
---|
287 |
int nh=1, ch, compared; |
---|
288 |
struct skiplistnode *lastnode, *nodeago; |
---|
289 |
if(sl->bottomend != sl->bottom) { |
---|
290 |
compared=sl->compare(data, sl->bottomend->prev->data); |
---|
291 |
/* If it doesn't belong at the end, then fail */ |
---|
292 |
if(compared<=0) return NULL; |
---|
293 |
} |
---|
294 |
if(sl->preheight) { |
---|
295 |
while(nh < sl->preheight && get_b_rand()) nh++; |
---|
296 |
} else { |
---|
297 |
while(nh <= sl->height && get_b_rand()) nh++; |
---|
298 |
} |
---|
299 |
/* Now we have the new hieght at which we wish to insert our new node */ |
---|
300 |
/* Let us make sure that our tree is a least that tall (grow if necessary)*/ |
---|
301 |
lastnode = sl->bottomend; |
---|
302 |
nodeago = NULL; |
---|
303 |
|
---|
304 |
if(!lastnode) return sl_insert(sl, data); |
---|
305 |
|
---|
306 |
for(;sl->height<nh;sl->height++) { |
---|
307 |
sl->top->up = |
---|
308 |
(struct skiplistnode *)malloc(sizeof(struct skiplistnode)); |
---|
309 |
assert(sl->top); |
---|
310 |
sl->top->up->down = sl->top; |
---|
311 |
sl->top = sl->top->up; |
---|
312 |
sl->top->prev = sl->top->next = sl->top->nextindex = |
---|
313 |
sl->top->previndex = NULL; |
---|
314 |
sl->top->data = NULL; |
---|
315 |
sl->top->sl = sl; |
---|
316 |
} |
---|
317 |
ch = sl->height; |
---|
318 |
while(nh) { |
---|
319 |
struct skiplistnode *anode; |
---|
320 |
anode = |
---|
321 |
(struct skiplistnode *)malloc(sizeof(struct skiplistnode)); |
---|
322 |
anode->next = lastnode; |
---|
323 |
anode->prev = lastnode->prev; |
---|
324 |
anode->up = NULL; |
---|
325 |
anode->down = nodeago; |
---|
326 |
if(lastnode->prev) { |
---|
327 |
if(lastnode == sl->bottom) |
---|
328 |
sl->bottom = anode; |
---|
329 |
else if (lastnode == sl->top) |
---|
330 |
sl->top = anode; |
---|
331 |
} |
---|
332 |
nodeago = anode; |
---|
333 |
lastnode = lastnode->up; |
---|
334 |
nh--; |
---|
335 |
} |
---|
336 |
sl->size++; |
---|
337 |
return sl->bottomend; |
---|
338 |
} |
---|
339 |
Skiplist *sl_concat(Skiplist *sl1, Skiplist *sl2) { |
---|
340 |
/* Check integrity! */ |
---|
341 |
int compared, eheight; |
---|
342 |
Skiplist temp; |
---|
343 |
struct skiplistnode *lbottom, *lbottomend, *b1, *e1, *b2, *e2; |
---|
344 |
if(sl1->bottomend == NULL || sl1->bottomend->prev == NULL) { |
---|
345 |
sl_remove_all(sl1, free); |
---|
346 |
temp = *sl1; |
---|
347 |
*sl1 = *sl2; |
---|
348 |
*sl2 = temp; |
---|
349 |
/* swap them so that sl2 can be freed normally upon return. */ |
---|
350 |
return sl1; |
---|
351 |
} |
---|
352 |
if(sl2->bottom == NULL || sl2->bottom->next == NULL) { |
---|
353 |
sl_remove_all(sl2, free); |
---|
354 |
return sl1; |
---|
355 |
} |
---|
356 |
compared = sl1->compare(sl1->bottomend->prev->data, sl2->bottom->data); |
---|
357 |
/* If it doesn't belong at the end, then fail */ |
---|
358 |
if(compared<=0) return NULL; |
---|
359 |
|
---|
360 |
/* OK now append sl2 onto sl1 */ |
---|
361 |
lbottom = lbottomend = NULL; |
---|
362 |
eheight = MIN(sl1->height, sl2->height); |
---|
363 |
b1 = sl1->bottom; e1 = sl1->bottomend; |
---|
364 |
b2 = sl2->bottom; e2 = sl2->bottomend; |
---|
365 |
while(eheight) { |
---|
366 |
e1->prev->next = b2; |
---|
367 |
b2->prev = e1->prev->next; |
---|
368 |
e2->prev->next = e1; |
---|
369 |
e1->prev = e2->prev; |
---|
370 |
e2->prev = NULL; |
---|
371 |
b2 = e2; |
---|
372 |
b1->down = lbottom; |
---|
373 |
e1->down = lbottomend; |
---|
374 |
if(lbottom) lbottom->up = b1; |
---|
375 |
if(lbottomend) lbottomend->up = e1; |
---|
376 |
|
---|
377 |
lbottom = b1; |
---|
378 |
lbottomend = e1; |
---|
379 |
} |
---|
380 |
/* Take the top of the longer one (if it is sl2) and make it sl1's */ |
---|
381 |
if(sl2->height > sl1->height) { |
---|
382 |
b1->up = b2->up; |
---|
383 |
e1->up = e2->up; |
---|
384 |
b1->up->down = b1; |
---|
385 |
e1->up->down = e1; |
---|
386 |
sl1->height = sl2->height; |
---|
387 |
sl1->top = sl2->top; |
---|
388 |
sl1->topend = sl2->topend; |
---|
389 |
} |
---|
390 |
|
---|
391 |
/* move the top pointer to here if it isn't there already */ |
---|
392 |
sl2->top = sl2->topend = b2; |
---|
393 |
sl2->top->up = NULL; /* If it isn't already */ |
---|
394 |
sl1->size += sl2->size; |
---|
395 |
sl_remove_all(sl2, free); |
---|
396 |
return sl1; |
---|
397 |
} |
---|
398 |
int sl_remove(Skiplist *sl, |
---|
399 |
void *data, FreeFunc myfree) { |
---|
400 |
if(!sl->compare) return 0; |
---|
401 |
return sl_remove_compare(sl, data, myfree, sl->comparek); |
---|
402 |
} |
---|
403 |
void sl_print_struct(Skiplist *sl, char *prefix) { |
---|
404 |
struct skiplistnode *p, *q; |
---|
405 |
fprintf(stderr, "Skiplist Structure (height: %d)\n", sl->height); |
---|
406 |
p = sl->bottom; |
---|
407 |
while(p) { |
---|
408 |
q = p; |
---|
409 |
fprintf(stderr, prefix); |
---|
410 |
while(q) { |
---|
411 |
fprintf(stderr, "%p ", q->data); |
---|
412 |
q=q->up; |
---|
413 |
} |
---|
414 |
fprintf(stderr, "\n"); |
---|
415 |
p=p->next; |
---|
416 |
} |
---|
417 |
} |
---|
418 |
int sli_remove(Skiplist *sl, struct skiplistnode *m, FreeFunc myfree) { |
---|
419 |
struct skiplistnode *p; |
---|
420 |
if(!m) return 0; |
---|
421 |
if(m->nextindex) sli_remove(m->nextindex->sl, m->nextindex, NULL); |
---|
422 |
else sl->size--; |
---|
423 |
#ifdef SLDEBUG |
---|
424 |
sl_print_struct(sl, "BR:"); |
---|
425 |
#endif |
---|
426 |
while(m->up) m=m->up; |
---|
427 |
while(m) { |
---|
428 |
p=m; |
---|
429 |
p->prev->next = p->next; /* take me out of the list */ |
---|
430 |
if(p->next) p->next->prev = p->prev; /* take me out of the list */ |
---|
431 |
m=m->down; |
---|
432 |
/* This only frees the actual data in the bottom one */ |
---|
433 |
if(!m && myfree && p->data) myfree(p->data); |
---|
434 |
free(p); |
---|
435 |
} |
---|
436 |
while(sl->top && sl->top->next == NULL) { |
---|
437 |
/* While the row is empty and we are not on the bottom row */ |
---|
438 |
p = sl->top; |
---|
439 |
sl->top = sl->top->down; /* Move top down one */ |
---|
440 |
if(sl->top) sl->top->up = NULL; /* Make it think its the top */ |
---|
441 |
free(p); |
---|
442 |
sl->height--; |
---|
443 |
} |
---|
444 |
if(!sl->top) sl->bottom = NULL; |
---|
445 |
assert(sl->height>=0); |
---|
446 |
#ifdef SLDEBUG |
---|
447 |
sl_print_struct(sl, "AR: "); |
---|
448 |
#endif |
---|
449 |
return sl->height; |
---|
450 |
} |
---|
451 |
int sl_remove_compare(Skiplist *sli, |
---|
452 |
void *data, |
---|
453 |
FreeFunc myfree, SkiplistComparator comp) { |
---|
454 |
struct skiplistnode *m; |
---|
455 |
Skiplist *sl; |
---|
456 |
if(comp==sli->comparek || !sli->index) { |
---|
457 |
sl = sli; |
---|
458 |
} else { |
---|
459 |
sl_find(sli->index, (void *)comp, &m); |
---|
460 |
assert(m); |
---|
461 |
sl=m->data; |
---|
462 |
} |
---|
463 |
sli_find_compare(sl, data, &m, comp); |
---|
464 |
while(m->previndex) m=m->previndex; |
---|
465 |
return sli_remove(sl, m, myfree); |
---|
466 |
} |
---|
467 |
void sl_remove_all(Skiplist *sl, FreeFunc myfree) { |
---|
468 |
/* This must remove even the place holder nodes (bottom though top) |
---|
469 |
because we specify in the API that one can free the Skiplist after |
---|
470 |
making this call without memory leaks */ |
---|
471 |
struct skiplistnode *m, *p, *u; |
---|
472 |
m=sl->bottom; |
---|
473 |
while(m) { |
---|
474 |
p = m->next; |
---|
475 |
if(myfree && p->data) myfree(p->data); |
---|
476 |
while(m) { |
---|
477 |
u = m->up; |
---|
478 |
free(m); |
---|
479 |
m=u; |
---|
480 |
} |
---|
481 |
m = p; |
---|
482 |
} |
---|
483 |
sl->top = sl->bottom = NULL; |
---|
484 |
sl->height = 0; |
---|
485 |
sl->size = 0; |
---|
486 |
} |
---|