root/src/utils/noit_skiplist.c

Revision e5a6938770c59733bb77648e60db9e6991006355, 10.7 kB (checked in by Theo Schlossnagle <jesus@omniti.com>, 6 years ago)

not tracking size correctly

  • Property mode set to 100644
Line 
1 /* ======================================================================
2  * Copyright (c) 2000,2006 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 file LGPL.
11  *
12  * Alternatively, this file may be licensed under the new BSD license.
13  * A copy of this license can be found file BSD.
14  *
15  * ======================================================================
16 */
17
18 #include <stdio.h>
19 #include <stdlib.h>
20 #include <assert.h>
21
22 #include "noit_skiplist.h"
23
24 #ifndef MIN
25 #define MIN(a,b) ((a<b)?(a):(b))
26 #endif
27
28 int noit_compare_voidptr(void *a, void *b) {
29   if(a < b) return -1;
30   if(a == b) return 0;
31   return 1;
32 }
33
34 static int get_b_rand(void) {
35   static int ph=32; /* More bits than we will ever use */
36   static unsigned long randseq;
37   if(ph > 31) { /* Num bits in return of lrand48() */
38     ph=0;
39     randseq = lrand48();
40   }
41   ph++;
42   return ((randseq & (1 << (ph-1))) >> (ph-1));
43 }
44
45 void noit_skiplisti_init(noit_skiplist *sl) {
46   sl->compare = (noit_skiplist_comparator_t)NULL;
47   sl->comparek = (noit_skiplist_comparator_t)NULL;
48   sl->height=0;
49   sl->preheight=0;
50   sl->size=0;
51   sl->top = NULL;
52   sl->bottom = NULL;
53   sl->index = NULL;
54 }
55
56 static int indexing_comp(void *a, void *b) {
57   assert(a);
58   assert(b);
59   return (void *)(((noit_skiplist *)a)->compare)>(void *)(((noit_skiplist *)b)->compare);
60 }
61 static int indexing_compk(void *a, void *b) {
62   assert(b);
63   return a>(void *)(((noit_skiplist *)b)->compare);
64 }
65
66 void noit_skiplist_init(noit_skiplist *sl) {
67   noit_skiplisti_init(sl);
68   sl->index = (noit_skiplist *)malloc(sizeof(noit_skiplist));
69   noit_skiplisti_init(sl->index);
70   noit_skiplist_set_compare(sl->index, indexing_comp, indexing_compk);
71 }
72
73 void noit_skiplist_set_compare(noit_skiplist *sl,
74                     noit_skiplist_comparator_t comp,
75                     noit_skiplist_comparator_t compk) {
76   if(sl->compare && sl->comparek) {
77     noit_skiplist_add_index(sl, comp, compk);
78   } else {
79     sl->compare = comp;
80     sl->comparek = compk;
81   }
82 }
83
84 void noit_skiplist_add_index(noit_skiplist *sl,
85                   noit_skiplist_comparator_t comp,
86                   noit_skiplist_comparator_t compk) {
87   noit_skiplist_node *m;
88   noit_skiplist *ni;
89   int icount=0;
90   noit_skiplist_find(sl->index, (void *)comp, &m);
91   if(m) return; /* Index already there! */
92   ni = (noit_skiplist *)malloc(sizeof(noit_skiplist));
93   noit_skiplisti_init(ni);
94   noit_skiplist_set_compare(ni, comp, compk);
95   /* Build the new index... This can be expensive! */
96   m = noit_skiplist_insert(sl->index, ni);
97   while(m->prev) m=m->prev, icount++;
98   for(m=noit_skiplist_getlist(sl); m; noit_skiplist_next(sl, &m)) {
99     int j=icount-1;
100     noit_skiplist_node *nsln;
101     nsln = noit_skiplist_insert(ni, m->data);
102     /* skip from main index down list */
103     while(j>0) m=m->nextindex, j--;
104     /* insert this node in the indexlist after m */
105     nsln->nextindex = m->nextindex;
106     if(m->nextindex) m->nextindex->previndex = nsln;
107     nsln->previndex = m;
108     m->nextindex = nsln;
109   }
110 }
111
112 noit_skiplist_node *noit_skiplist_getlist(noit_skiplist *sl) {
113   if(!sl->bottom) return NULL;
114   return sl->bottom->next;
115 }
116
117 void *noit_skiplist_find(noit_skiplist *sl,
118               void *data,
119               noit_skiplist_node **iter) {
120   void *ret;
121   noit_skiplist_node *aiter;
122   if(!sl->compare) return 0;
123   if(iter)
124     ret = noit_skiplist_find_compare(sl, data, iter, sl->compare);
125   else
126     ret = noit_skiplist_find_compare(sl, data, &aiter, sl->compare);
127   return ret;
128
129 void *noit_skiplist_find_compare(noit_skiplist *sli,
130                       void *data,
131                       noit_skiplist_node **iter,
132                       noit_skiplist_comparator_t comp) {
133   noit_skiplist_node *m = NULL;
134   noit_skiplist *sl;
135   if(comp==sli->compare || !sli->index) {
136     sl = sli;
137   } else {
138     noit_skiplist_find(sli->index, (void *)comp, &m);
139     assert(m);
140     sl= (noit_skiplist *) m->data;
141   }
142   noit_skiplisti_find_compare(sl, data, iter, sl->comparek);
143   return (*iter)?((*iter)->data):(*iter);
144 }
145 int noit_skiplisti_find_compare(noit_skiplist *sl,
146                      void *data,
147                      noit_skiplist_node **ret,
148                      noit_skiplist_comparator_t comp) {
149   noit_skiplist_node *m = NULL;
150   int count=0;
151   m = sl->top;
152   while(m) {
153     int compared = -1;
154     if(m->next) compared=comp(data, m->next->data);
155     if(compared == 0) {
156 #ifdef SL_DEBUG
157       printf("Looking -- found in %d steps\n", count);
158 #endif
159       m=m->next;
160       while(m->down) m=m->down;
161       *ret = m;
162       return count;
163     }
164     if((m->next == NULL) || (compared<0))
165       m = m->down, count++;
166     else
167       m = m->next, count++;
168   }
169 #ifdef SL_DEBUG
170   printf("Looking -- not found in %d steps\n", count);
171 #endif
172   *ret = NULL;
173   return count;
174 }
175 void *noit_skiplist_next(noit_skiplist *sl, noit_skiplist_node **iter) {
176   if(!*iter) return NULL;
177   *iter = (*iter)->next;
178   return (*iter)?((*iter)->data):NULL;
179 }
180 void *noit_skiplist_previous(noit_skiplist *sl, noit_skiplist_node **iter) {
181   if(!*iter) return NULL;
182   *iter = (*iter)->prev;
183   return (*iter)?((*iter)->data):NULL;
184 }
185 noit_skiplist_node *noit_skiplist_insert(noit_skiplist *sl,
186                                void *data) {
187   if(!sl->compare) return 0;
188   return noit_skiplist_insert_compare(sl, data, sl->compare);
189 }
190
191 noit_skiplist_node *noit_skiplist_insert_compare(noit_skiplist *sl,
192                                        void *data,
193                                        noit_skiplist_comparator_t comp) {
194   noit_skiplist_node *m, *p, *tmp, *ret = NULL, **stack;
195   int nh=1, ch, stacki;
196   if(!sl->top) {
197     sl->height = 1;
198     sl->topend = sl->bottomend = sl->top = sl->bottom =
199       (noit_skiplist_node *)malloc(sizeof(noit_skiplist_node));
200     assert(sl->top);
201     sl->top->next = (noit_skiplist_node *) NULL;
202     sl->top->data = (noit_skiplist_node *) NULL;
203     sl->top->prev =(noit_skiplist_node *) NULL;
204         sl->top->up = (noit_skiplist_node *) NULL;
205     sl->top->down = (noit_skiplist_node *) NULL;
206         sl->top->nextindex=  (noit_skiplist_node *) NULL;
207     sl->top->previndex = (noit_skiplist_node *) NULL;
208     sl->top->sl = sl;
209   }
210   if(sl->preheight) {
211     while(nh < sl->preheight && get_b_rand()) nh++;
212   } else {
213     while(nh <= sl->height && get_b_rand()) nh++;
214   }
215   /* Now we have the new height at which we wish to insert our new node */
216   /* Let us make sure that our tree is a least that tall (grow if necessary)*/
217   for(;sl->height<nh;sl->height++) {
218     sl->top->up =
219       (noit_skiplist_node *)malloc(sizeof(noit_skiplist_node));
220     assert(sl->top->up);
221     sl->top->up->down = sl->top;
222     sl->top = sl->topend = sl->top->up;
223     sl->top->prev = sl->top->next = sl->top->nextindex =
224       sl->top->previndex = sl->top->up = NULL;
225     sl->top->data = NULL;
226     sl->top->sl = sl;
227   }
228   ch = sl->height;
229   /* Find the node (or node after which we would insert) */
230   /* Keep a stack to pop back through for insertion */
231   m = sl->top;
232   stack = (noit_skiplist_node **)malloc(sizeof(noit_skiplist_node *)*(nh));
233   stacki=0;
234   while(m) {
235     int compared=-1;
236     if(m->next) compared=comp(data, m->next->data);
237     if(compared == 0) {
238       free(stack);
239       return 0;
240     }
241     if((m->next == NULL) || (compared<0)) {
242       if(ch<=nh) {
243         /* push on stack */
244         stack[stacki++] = m;
245       }
246       m = m->down;
247       ch--;
248     } else {
249       m = m->next;
250     }
251   }
252   /* Pop the stack and insert nodes */
253   p = NULL;
254   for(;stacki>0;stacki--) {
255     m = stack[stacki-1];
256     tmp = (noit_skiplist_node *)malloc(sizeof(noit_skiplist_node));
257     tmp->next = m->next;
258     if(m->next) m->next->prev=tmp;
259     tmp->prev = m;
260     tmp->up = NULL;
261     tmp->nextindex = tmp->previndex = NULL;
262     tmp->down = p;
263     if(p) p->up=tmp;
264     tmp->data = data;
265     tmp->sl = sl;
266     m->next = tmp;
267     /* This sets ret to the bottom-most node we are inserting */
268     if(!p) ret=tmp;
269     p = tmp;
270   }
271   free(stack);
272   if(sl->index != NULL) {
273     /* this is a external insertion, we must insert into each index as well */
274     noit_skiplist_node *p, *ni, *li;
275     li=ret;
276     for(p = noit_skiplist_getlist(sl->index); p; noit_skiplist_next(sl->index, &p)) {
277       ni = noit_skiplist_insert((noit_skiplist *)p->data, ret->data);
278       assert(ni);
279       li->nextindex = ni;
280       ni->previndex = li;
281       li = ni;
282     }
283   }
284   sl->size++;
285   return ret;
286 }
287 int noit_skiplist_remove(noit_skiplist *sl,
288               void *data, noit_freefunc_t myfree) {
289   if(!sl->compare) return 0;
290   return noit_skiplist_remove_compare(sl, data, myfree, sl->comparek);
291 }
292 int noit_skiplisti_remove(noit_skiplist *sl, noit_skiplist_node *m, noit_freefunc_t myfree) {
293   noit_skiplist_node *p;
294   if(!m) return 0;
295   if(m->nextindex) noit_skiplisti_remove(m->nextindex->sl, m->nextindex, NULL);
296   while(m->up) m=m->up;
297   while(m) {
298     p=m;
299     p->prev->next = p->next; /* take me out of the list */
300     if(p->next) p->next->prev = p->prev; /* take me out of the list */
301     m=m->down;
302     /* This only frees the actual data in the bottom one */
303     if(!m && myfree && p->data) myfree(p->data);
304     free(p);
305   }
306   sl->size--;
307   while(sl->top && sl->top->next == NULL) {
308     /* While the row is empty and we are not on the bottom row */
309     p = sl->top;
310     sl->top = sl->top->down; /* Move top down one */
311     if(sl->top) sl->top->up = NULL;      /* Make it think its the top */
312     free(p);
313     sl->height--;
314   }
315   if(!sl->top) sl->bottom = NULL;
316   assert(sl->height>=0);
317   return sl->height;
318 }
319 int noit_skiplist_remove_compare(noit_skiplist *sli,
320                       void *data,
321                       noit_freefunc_t myfree, noit_skiplist_comparator_t comp) {
322   noit_skiplist_node *m;
323   noit_skiplist *sl;
324   if(comp==sli->comparek || !sli->index) {
325     sl = sli;
326   } else {
327     noit_skiplist_find(sli->index, (void *)comp, &m);
328     assert(m);
329     sl= (noit_skiplist *) m->data;
330   }
331   noit_skiplisti_find_compare(sl, data, &m, comp);
332   if(!m) return 0;
333   while(m->previndex) m=m->previndex;
334   return noit_skiplisti_remove(sl, m, myfree);
335 }
336 void noit_skiplist_remove_all(noit_skiplist *sl, noit_freefunc_t myfree) {
337   /* This must remove even the place holder nodes (bottom though top)
338      because we specify in the API that one can free the noit_skiplist after
339      making this call without memory leaks */
340   noit_skiplist_node *m, *p, *u;
341   m=sl->bottom;
342   while(m) {
343     p = m->next;
344     if(myfree && p->data) myfree(p->data);
345     while(m) {
346       u = m->up;
347       free(m);
348       m=u;
349     }
350     m = p;
351   }
352   sl->top = sl->bottom = NULL;
353   sl->height = 0;
354   sl->size = 0;
355 }
356
357 void *noit_skiplist_pop(noit_skiplist * a, noit_freefunc_t myfree)
358 {
359   noit_skiplist_node *sln;
360   void *data = NULL;
361   sln = noit_skiplist_getlist(a);
362   if (sln) {
363     data = sln->data;
364     noit_skiplisti_remove(a, sln, myfree);
365   }
366   return data;
367 }
368 void *noit_skiplist_peek(noit_skiplist * a)
369 {
370   noit_skiplist_node *sln;
371   sln = noit_skiplist_getlist(a);
372   if (sln) {
373     return sln->data;
374   }
375   return NULL;
376 }
Note: See TracBrowser for help on using the browser.