root/tags/2.0.0/skiplist.c

Revision 42, 15.3 kB (checked in by jesus, 8 years ago)

function updates and libevent logging

  • 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  * Copyright (c) 2001-2004 OmniTI, Inc. All rights reserved
4  *
5  * The following code was written by Theo Schlossnagle for use in the
6  * Backhand project at The Center for Networking and Distributed Systems
7  * at The Johns Hopkins University.
8  *
9  */
10
11 #include "sld_config.h"
12 #include "skiplist.h"
13
14 #define MAXHEIGHT 32
15
16 #ifndef MIN
17 #define MIN(a,b) ((a<b)?(a):(b))
18 #endif
19
20 #ifndef MAX
21 #define MAX(a,b) ((a>b)?(a):(b))
22 #endif
23
24 static int get_b_rand(void)
25 {
26   static int ph = 32;           /* More bits than we will ever use */
27   static unsigned long randseq;
28   if (ph > 31) {                /* Num bits in return of lrand48() */
29     ph = 0;
30     randseq = lrand48();
31   }
32   ph++;
33   return ((randseq & (1 << (ph - 1))) >> (ph - 1));
34 }
35
36 void sli_init(Skiplist * sl)
37 {
38   memset(sl, 0, sizeof(Skiplist));
39   sl->compare = (SkiplistComparator) NULL;
40   sl->comparek = (SkiplistComparator) NULL;
41   sl->height = 0;
42   sl->preheight = 0;
43   sl->size = 0;
44   sl->bottom = NULL;
45   sl->index = NULL;
46   sl->agg = NULL;
47 }
48
49 #define indexing_comp(a,b) \
50   ((((Skiplist *) a)->compare) < (((Skiplist *) b)->compare))?-1: \
51     ((((Skiplist *) a)->compare) == (((Skiplist *) b)->compare))?0:1;
52
53 #define indexing_compk(a,b) \
54   ((SkiplistComparator)(a) < (((Skiplist *) b)->compare))?-1: \
55     ((SkiplistComparator)(a) == (((Skiplist *) b)->compare))?0:1;
56
57 void sl_init_full(Skiplist * sl)
58 {
59   sli_init(sl);
60
61   sl->index = (Skiplist *) malloc(sizeof(*sl->index));
62   assert(sl->index);
63   memset(sl->index, 0, sizeof(Skiplist));
64   sli_init(sl->index);
65   sl_set_compare(sl->index, SL_index_compare, SL_index_compare_key);
66
67   sl->agg = (Skiplist *) malloc(sizeof(*sl->agg));
68   assert(sl->agg);
69   memset(sl->agg, 0, sizeof(Skiplist));
70   sli_init(sl->agg);
71   sl_set_compare(sl->agg, SL_index_compare, SL_index_compare_key);
72 }
73
74 void sl_init(Skiplist * sl)
75 {
76   sl_init_full(sl);
77 }
78 void sl_set_compare(Skiplist * sl,
79                     SkiplistComparator comp, SkiplistComparator compk)
80 {
81   if (sl->compare && sl->comparek) {
82     sl_add_index(sl, comp, compk);
83   }
84   else {
85     sl->compare = comp;
86     sl->comparek = compk;
87   }
88 }
89
90 void sl_add_internal(Skiplist * sl, Skiplist *sli, Skiplist *ni)
91 {
92   struct skiplistnode *m;
93   int icount = 0;
94 #ifdef SLDEBUG
95   fprintf(stderr, "Adding index to %p\n", sl);
96 #endif
97   /* Build the new index... This can be expensive! */
98   m = sl_insert(sli, ni);
99   while (m->level[0].prev)
100     m = m->level[0].prev, icount++;
101   for (m = sl_getlist(sl); m; sl_next(&m)) {
102     int j = icount - 1;
103     struct skiplistnode *nsln;
104     nsln = sl_insert(ni, m->data);
105     /* skip from main index down list */
106     while (j > 0)
107       m = m->nextindex, j--;
108     /* insert this node in the indexlist after m */
109     nsln->nextindex = m->nextindex;
110     if (m->nextindex)
111       m->nextindex->previndex = nsln;
112     nsln->previndex = m;
113     m->nextindex = nsln;
114   }
115 }
116 void sl_attach_aggregate(Skiplist *sl, Skiplist *agg)
117 {
118   sl_add_internal(sl, sl->agg, agg);
119 }
120 void sl_add_index(Skiplist * sl,
121                   SkiplistComparator comp, SkiplistComparator compk)
122 {
123   struct skiplistnode *m;
124   Skiplist *ni;
125   sl_find(sl->index, (void *) comp, &m);
126   if (m)
127     return;                     /* Index already there! */
128   ni = (Skiplist *) malloc(sizeof(*ni));
129   assert(ni);
130   memset(ni, 0, sizeof(Skiplist));
131   sli_init(ni);
132   sl_set_compare(ni, comp, compk);
133
134   sl_add_internal(sl, sl->index, ni);
135 }
136
137 struct skiplistnode *sl_getlist(Skiplist * sl)
138 {
139   if (!sl->bottom)
140     return NULL;
141   return sl->bottom->level[0].next;
142 }
143
144 void sl_node_dataswap(Skiplist *sl, struct skiplistnode *node, void *data)
145 {
146   while(node->previndex) node = node->previndex;
147   while(node) {
148     node->data = data;
149     node = node->nextindex;
150   }
151 }
152 void *sl_find(const Skiplist * sl, const void *data, struct skiplistnode **iter)
153 {
154   void *ret;
155   struct skiplistnode *aiter;
156   if (!sl->compare)
157     return 0;
158   if (iter)
159     ret = sl_find_compare(sl, data, iter, sl->compare);
160   else
161     ret = sl_find_compare(sl, data, &aiter, sl->compare);
162   return ret;
163 }
164 void *sl_find_neighbors(const Skiplist * sl, const void *data,
165                         struct skiplistnode **iter,
166                         struct skiplistnode **prev,
167                         struct skiplistnode **next)
168 {
169   struct skiplistnode *aiter, *aprev, *anext;
170   if (!sl->compare)
171     return 0;
172   return sl_find_compare_neighbors(sl, data,
173                          iter?iter:&aiter, prev?prev:&aprev, next?next:&anext,
174                          sl->compare);
175 }
176 void *sl_find_compare(const Skiplist * sli,
177                       const void *data,
178                       struct skiplistnode **iter, SkiplistComparator comp)
179 {
180   struct skiplistnode *m = NULL;
181   struct skiplistnode *i1, *i2;
182   const Skiplist *sl;
183   if (comp == sli->compare || !sli->index) {
184     sl = sli;
185   }
186   else {
187     sl_find(sli->index, (void *) comp, &m);
188     assert(m);
189     sl = m->data;
190   }
191   sli_find_compare(sl, data, iter, &i1, &i2, sl->comparek);
192   return (*iter) ? ((*iter)->data) : (*iter);
193 }
194 void *sl_find_compare_neighbors(const Skiplist * sli,
195                       const void *data,
196                       struct skiplistnode **iter,
197                       struct skiplistnode **prev,
198                       struct skiplistnode **next,
199                       SkiplistComparator comp)
200 {
201   struct skiplistnode *m = NULL;
202   const Skiplist *sl;
203   if (comp == sli->compare || !sli->index) {
204     sl = sli;
205   }
206   else {
207     sl_find(sli->index, (void *) comp, &m);
208     assert(m);
209     sl = m->data;
210   }
211   sli_find_compare(sl, data, iter, prev, next, sl->comparek);
212   return (*iter) ? ((*iter)->data) : (*iter);
213 }
214 int sli_find_compare(const Skiplist * sl,
215                      const void *data,
216                      struct skiplistnode **ret,
217                      struct skiplistnode **ret_prev,
218                      struct skiplistnode **ret_next,
219                      SkiplistComparator comp)
220 {
221   struct skiplistnode *m;
222   register struct skiplistnode *t;
223   register int compared;
224   int count = 0;
225   int level = 0;
226   m = sl->bottom;
227   if(m) level = m->height - 1;
228   *ret = *ret_prev = *ret_next = NULL;
229   while (m && level >= 0) {
230     compared = 1;
231     if ((t = m->level[level].next) != NULL) {
232       if(comp < SL_INLINE_MAX) {
233         if(comp == SL_index_compare) {
234           compared = indexing_comp(data, t->data);
235         } else if(comp == SL_index_compare_key) {
236           compared = indexing_compk(data, t->data);
237         } else {
238           compared = comp(data, t->data);
239         }
240       } else {
241         compared = comp(data, t->data);
242       }
243     }
244     if (compared == 0) {
245 #ifdef SL_DEBUG
246       printf("Looking -- found in %d steps\n", count);
247 #endif
248       m = t;
249       *ret = m;
250       *ret_prev = (m->level[0].prev && m->level[0].prev != sl->bottom)?m->level[0].prev:NULL;
251       *ret_next = m->level[0].next?m->level[0].next:NULL;
252       return count;
253     }
254     if ((t == NULL) || (compared < 0)) {
255       if(level == 0) {
256         /* mark our left and right... we missed! */
257         *ret_prev = (m != sl->bottom)?m:NULL;
258         *ret_next = t;
259       }
260       level--;
261       count++;
262     } else
263       m = t, count++;
264   }
265 #ifdef SL_DEBUG
266   printf("Looking -- not found in %d steps\n", count);
267 #endif
268   *ret = NULL;
269   return count;
270 }
271 void *sl_next(struct skiplistnode **iter)
272 {
273   if (!*iter)
274     return NULL;
275   *iter = (*iter)->level[0].next;
276   return (*iter) ? ((*iter)->data) : NULL;
277 }
278 void *sl_previous(struct skiplistnode **iter)
279 {
280   if (!*iter)
281     return NULL;
282   *iter = (*iter)->level[0].prev;
283   if((*iter) && !(*iter)->level[0].prev) *iter = NULL;
284   return (*iter) ? ((*iter)->data) : NULL;
285 }
286 struct skiplistnode *sl_insert(Skiplist * sl, void *data)
287 {
288   if (!sl->compare)
289     return 0;
290   return sl_insert_compare(sl, data, sl->compare);
291 }
292
293 static void sli_insert_multi(Skiplist *slsl, struct skiplistnode *ret) {
294   if (slsl != NULL) {
295     /* this is a external insertion, we must insert into each index as well */
296     struct skiplistnode *p, *ni, *li;
297     li = ret;
298     for (p = sl_getlist(slsl); p; sl_next(&p)) {
299       ni = sl_insert((Skiplist *) p->data, ret->data);
300       assert(ni);
301 #ifdef SLDEBUG
302       fprintf(stderr, "Adding %p to index %p\n", ret->data, p->data);
303 #endif
304       li->nextindex = ni;
305       ni->previndex = li;
306       li = ni;
307     }
308   }
309 }
310 struct skiplistnode *sl_insert_compare(Skiplist * sl,
311                                        void *data, SkiplistComparator comp)
312 {
313   struct skiplistnode *m, *ret, *stack[MAXHEIGHT] = { NULL };
314   int level, i, nh = 1, ch;
315   int compared = -1;
316
317   ret = NULL;
318 #ifdef SLDEBUG
319   sl_print_struct(sl, "BI: ");
320 #endif
321   if (!sl->bottom) {
322     sl->height = 0;
323     sl->bottom =
324       (struct skiplistnode *) malloc(SLNODESIZE(1));
325     assert(sl->bottom);
326     memset(sl->bottom, 0, SLNODESIZE(1));
327     sl->bottom->height = 0;
328     sl->bottom->sl = sl;
329   }
330   if (sl->preheight) {
331     while (nh < sl->preheight && get_b_rand())
332       nh++;
333   }
334   else {
335     while (nh <= sl->height && get_b_rand())
336       nh++;
337   }
338   nh = MIN(MAXHEIGHT, nh);      /* Never allow new height to get out of control */
339
340   /* Now we have the new height at which we wish to insert our new node */
341   /* Let us make sure that our tree is a least that tall (grow if necessary) */
342   if(sl->height == 0) sl->height = sl->bottom->height = 1;
343   ch = sl->height;
344   if(ch < nh) {
345     if(SLNODESIZE(ch) != SLNODESIZE(nh)) {
346       m = (struct skiplistnode *) malloc(SLNODESIZE(nh));
347       memcpy(m, sl->bottom, SLNODESIZE(ch));
348       free(sl->bottom);
349       sl->bottom = m;
350       for(i=0;i<m->height;i++)
351         if(m->level[i].next) m->level[i].next->level[i].prev = m;
352     }
353     for(i=sl->bottom->height; i<nh; i++) {
354       sl->bottom->level[i].prev = sl->bottom->level[i].next = NULL;
355     }
356   }
357   ch = sl->bottom->height = sl->height = MAX(nh,ch);
358   level = ch - 1;
359   /* Find the node (or node after which we would insert) */
360   /* Keep a stack to pop back through for insertion */
361   m = sl->bottom;
362   while (m && level >= 0) {
363     if (m->level[level].next) {
364       if(comp < SL_INLINE_MAX) {
365         if(comp == SL_index_compare) {
366           compared = indexing_comp(data, m->level[level].next->data);
367         } else if(comp == SL_index_compare_key) {
368           compared = indexing_compk(data, m->level[level].next->data);
369         } else {
370           compared = comp(data, m->level[level].next->data);
371         }
372       } else {
373         compared = comp(data, m->level[level].next->data);
374       }
375     }
376     if (compared == 0) {
377       return 0;
378     }
379     if ((m->level[level].next == NULL) || (compared < 0)) {
380       if (ch <= nh) {
381         /* push on stack */
382         stack[level] = m;
383       }
384       level--;
385       ch--;
386     }
387     else {
388       m = m->level[level].next;
389     }
390   }
391   /* Pop the stack and insert nodes */
392   ret = (struct skiplistnode *) malloc(SLNODESIZE(nh));
393   memset(ret, 0, SLNODESIZE(nh));
394   ret->height = nh;
395   ret->data = data;
396   ret->sl = sl;
397   for (i=0; i<nh; i++) {
398     if(!stack[i]) abort();
399     ret->level[i].next = stack[i]->level[i].next;
400     stack[i]->level[i].next = ret;
401     ret->level[i].prev = stack[i];
402     if(ret->level[i].next) ret->level[i].next->level[i].prev = ret;
403     ret->nextindex = ret->previndex = NULL;
404   }
405   sl->size++;
406
407   if (sl->index != NULL)
408     sli_insert_multi(sl->index, ret);
409   if (sl->agg != NULL)
410     sli_insert_multi(sl->agg, ret);
411 #ifdef SLDEBUG
412   sl_print_struct(sl, "AI: ");
413 #endif
414   return ret;
415 }
416 struct skiplistnode *sl_append(Skiplist * sl, void *data)
417 {
418   return sl_insert(sl, data);
419 }
420
421 int sl_remove(Skiplist * sl, void *data, FreeFunc myfree)
422 {
423   if (!sl->compare)
424     return 0;
425   return sl_remove_compare(sl, data, myfree, sl->comparek);
426 }
427 int sli_remove_node(Skiplist * sl, struct skiplistnode *m, FreeFunc myfree)
428 {
429   int i;
430   struct skiplistnode *p;
431   if (!m)
432     return 0;
433   if (m->sl != sl) {
434     fprintf(stderr, "removing element from skiplist it is not in!!!\n");
435     *((int *) 0) = 0;
436   }
437   if (m->nextindex)
438     sli_remove_node(m->nextindex->sl, m->nextindex, NULL);
439   if (myfree && m->data)
440     myfree(m->data);
441   sl->size--;
442 #ifdef SLDEBUG
443   sl_print_struct(sl, "BR:");
444 #endif
445   for (i=0; i<m->height; i++) {
446     p = m->level[i].prev;
447     if(m->level[i].next) m->level[i].next->level[i].prev = p;
448     if(p) p->level[i].next = m->level[i].next;
449   }
450   free(m);
451   while (sl->bottom->height &&
452          sl->bottom->level[sl->bottom->height-1].next == NULL)
453     sl->bottom->height--;
454   if(sl->bottom->height == 0) {
455     free(sl->bottom);
456     sl->bottom = NULL;
457     sl->height = 0;
458   } else if(sl->height > sl->bottom->height &&
459      SLNODESIZE(sl->height) != SLNODESIZE(sl->bottom->height)) {
460     p = (struct skiplistnode *) malloc(SLNODESIZE(sl->bottom->height));
461     memcpy(p, sl->bottom, SLNODESIZE(sl->bottom->height));
462     free(sl->bottom);
463     sl->bottom = p;
464     for(i=0; i<p->height; i++)
465       if(p->level[i].next) p->level[i].next->level[i].prev = p;
466     sl->height = sl->bottom->height;
467   }
468 #ifdef SLDEBUG
469   sl_print_struct(sl, "AR: ");
470 #endif
471   return MAX(sl->height,1);
472 }
473 int sli_remove(Skiplist * sl, struct skiplistnode *m, FreeFunc myfree)
474 {
475   assert(m->sl == sl);
476   while(m->previndex) m = m->previndex;
477   return sli_remove_node(m->sl, m, myfree);
478 }
479 int sl_remove_compare(Skiplist * sli,
480                       void *data, FreeFunc myfree, SkiplistComparator comp)
481 {
482   struct skiplistnode *m, *i1, *i2;
483   Skiplist *sl;
484   if (comp == sli->comparek || !sli->index) {
485     sl = sli;
486   }
487   else {
488     sl_find(sli->index, (void *) comp, &m);
489     assert(m);
490     sl = m->data;
491   }
492   sli_find_compare(sl, data, &m, &i1, &i2, comp);
493   if (!m)
494     return 0;
495   while (m->previndex)
496     m = m->previndex;
497   return sli_remove(m->sl, m, myfree);
498 }
499
500 void sli_remove_all(Skiplist * sl, FreeFunc myfree)
501 {
502   /* This must remove even the place holder nodes (bottom though top)
503      because we specify in the API that one can free the Skiplist after
504      making this call without memory leaks */
505   struct skiplistnode *m, *p;
506   if(sl->bottom) {
507     m = sl->bottom->level[0].next;
508     while (m) {
509       p = m->level[0].next;
510       if (myfree && m && m->data)
511         myfree(m->data);
512       free(m);
513       m = p;
514     }
515     free(sl->bottom);
516   }
517   sl->bottom = NULL;
518   sl->height = 0;
519   sl->size = 0;
520 }
521
522 void sl_destruct(Skiplist *sl, FreeFunc myfree) {
523   if(sl->index) {
524     sli_remove_all(sl->index, (FreeFunc)sli_destruct_free);
525     free(sl->index);
526   }
527   if(sl->agg) {
528     sli_remove_all(sl->agg, NULL);
529     free(sl->agg);
530   }
531   sli_remove_all(sl, myfree);
532 }
533 void sli_destruct_free(Skiplist *sl, FreeFunc myfree) {
534   sli_remove_all(sl, NULL);
535   free(sl);
536 }
537
538 void sl_level_order_apply(Skiplist *sl, ApplyFunc myfunc)
539 {
540   struct skiplistnode *p;
541   int level;
542   if(sl->size == 0) return;
543   for(level = sl->bottom->height-1; level >= 0; level--) {
544     p = sl->bottom->level[level].next;
545     while(p) {
546       if(myfunc && p->height == (level+1))
547         if(myfunc(p->data)) return;
548       p = p->level[level].next;
549     }
550   }
551 }
552
553 struct skiplistnode *sl_getlist_end(Skiplist *sl)
554 {
555   /* Q: Why do we do all this work, instead of calling a native
556         skiplist function?
557      A: We need to get to the _end_ of the list.  By iterating across
558         the top level of the skiplist we as far as possible, then drop
559         one level and repeat, we simulate a search for a key that is
560         greater than the largest in the set.  This is O(lg n).
561   */
562   struct skiplistnode *p;
563   int level;
564   if(!sl->bottom) return NULL;
565   level = sl->bottom->height-1;
566   p = sl->bottom->level[level].next;
567   while(level >= 0) {
568     while(p->level[level].next) p = p->level[level].next;
569     level--;
570   }
571   if (!p)
572     return NULL;
573   return p;
574 }
Note: See TracBrowser for help on using the browser.