root/src/utils/noit_skiplist.c

Revision 4cdbcdb30a697d3227b7be9d7deed71656552d22, 13.0 kB (checked in by Theo Schlossnagle <jesus@omniti.com>, 7 years ago)

partial match works. apply command works, needs range expansion which I'll lean on pcre for. Didn't have pcre on the plain -- so here we are.

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