root/trunk/skiplist.c

Revision 17, 13.1 kB (checked in by jesus, 13 years ago)

uninitialized variable. And type in #else

  • Property svn:eol-style set to native
  • Property svn:executable set to *
  • Property svn:keywords set to Author Date Id Revision
Line 
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 = 1;
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=NULL, **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 }
Note: See TracBrowser for help on using the browser.