root/src/utils/noit_skiplist.c

Revision 8db74608357ad19392f13c74030de9553237baeb, 12.5 kB (checked in by Theo Schlossnagle <jesus@omniti.com>, 4 years ago)

bug causing improperly maintained size attribute

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