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
18extern "C"
19{
20#include <stdio.h>
21#include <stdlib.h>
22#include <assert.h>
23
24#include "skiplist.h"
25}
26
27#ifdef USE_DMALLOC
28#    include <dmalloc.h>
29#endif
30
31#ifndef MIN
32#define MIN(a,b) ((a<b)?(a):(b))
33#endif
34
35static int get_b_rand(void) {
36  static int ph=32; /* More bits than we will ever use */
37  static unsigned long randseq;
38  if(ph > 31) { /* Num bits in return of lrand48() */
39    ph=0;
40    randseq = lrand48();
41  }
42  ph++;
43  return ((randseq & (1 << (ph-1))) >> (ph-1));
44}
45
46void skiplisti_init(Skiplist *sl) {
47  sl->compare = (SkiplistComparator)NULL;
48  sl->comparek = (SkiplistComparator)NULL;
49  sl->height=0;
50  sl->preheight=0;
51  sl->size=0;
52  sl->top = NULL;
53  sl->bottom = NULL;
54  sl->index = NULL;
55}
56
57static int indexing_comp(void *a, void *b) {
58  assert(a);
59  assert(b);
60  return (void *)(((Skiplist *)a)->compare)>(void *)(((Skiplist *)b)->compare);
61}
62static int indexing_compk(void *a, void *b) {
63  assert(b);
64  return a>(void *)(((Skiplist *)b)->compare);
65}
66
67void skiplist_init(Skiplist *sl) {
68  skiplisti_init(sl);
69  sl->index = (Skiplist *)malloc(sizeof(Skiplist));
70  skiplisti_init(sl->index);
71  skiplist_set_compare(sl->index, indexing_comp, indexing_compk);
72}
73
74void skiplist_set_compare(Skiplist *sl,
75		    SkiplistComparator comp,
76		    SkiplistComparator compk) {
77  if(sl->compare && sl->comparek) {
78    skiplist_add_index(sl, comp, compk);
79  } else {
80    sl->compare = comp;
81    sl->comparek = compk;
82  }
83}
84
85void skiplist_add_index(Skiplist *sl,
86		  SkiplistComparator comp,
87		  SkiplistComparator compk) {
88  struct skiplistnode *m;
89  Skiplist *ni;
90  int icount=0;
91#ifdef SLDEBUG
92  fprintf(stderr, "Adding index to %p\n", sl);
93#endif
94  skiplist_find(sl->index, (void *)comp, &m);
95  if(m) return; /* Index already there! */
96  ni = (Skiplist *)malloc(sizeof(Skiplist));
97  skiplisti_init(ni);
98  skiplist_set_compare(ni, comp, compk);
99  /* Build the new index... This can be expensive! */
100  m = skiplist_insert(sl->index, ni);
101  while(m->prev) m=m->prev, icount++;
102  for(m=skiplist_getlist(sl); m; skiplist_next(sl, &m)) {
103    int j=icount-1;
104    struct skiplistnode *nsln;
105    nsln = 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
116struct skiplistnode *skiplist_getlist(Skiplist *sl) {
117  if(!sl->bottom) return NULL;
118  return sl->bottom->next;
119}
120
121void *skiplist_find(Skiplist *sl,
122	      void *data,
123	      struct skiplistnode **iter) {
124  void *ret;
125  struct skiplistnode *aiter;
126  if(!sl->compare) return 0;
127  if(iter)
128    ret = skiplist_find_compare(sl, data, iter, sl->compare);
129  else
130    ret = skiplist_find_compare(sl, data, &aiter, sl->compare);
131  return ret;
132}
133void *skiplist_find_compare(Skiplist *sli,
134		      void *data,
135		      struct skiplistnode **iter,
136		      SkiplistComparator comp) {
137  struct skiplistnode *m = NULL;
138  Skiplist *sl;
139  if(comp==sli->compare || !sli->index) {
140    sl = sli;
141  } else {
142    skiplist_find(sli->index, (void *)comp, &m);
143    assert(m);
144    sl= (Skiplist *) m->data;
145  }
146  skiplisti_find_compare(sl, data, iter, sl->comparek);
147  return (*iter)?((*iter)->data):(*iter);
148}
149int skiplisti_find_compare(Skiplist *sl,
150		     void *data,
151		     struct skiplistnode **ret,
152		     SkiplistComparator comp) {
153  struct skiplistnode *m = NULL;
154  int count=0;
155  m = sl->top;
156  while(m) {
157    int compared;
158    if(m->next) compared=comp(data, m->next->data);
159    if(compared == 0) {
160#ifdef SL_DEBUG
161      printf("Looking -- found in %d steps\n", count);
162#endif
163      m=m->next;
164      while(m->down) m=m->down;
165      *ret = m;
166      return count;
167    }
168    if((m->next == NULL) || (compared<0))
169      m = m->down, count++;
170    else
171      m = m->next, count++;
172  }
173#ifdef SL_DEBUG
174  printf("Looking -- not found in %d steps\n", count);
175#endif
176  *ret = NULL;
177  return count;
178}
179void *skiplist_next(Skiplist *sl, struct skiplistnode **iter) {
180  if(!*iter) return NULL;
181  *iter = (*iter)->next;
182  return (*iter)?((*iter)->data):NULL;
183}
184void *skiplist_previous(Skiplist *sl, struct skiplistnode **iter) {
185  if(!*iter) return NULL;
186  *iter = (*iter)->prev;
187  return (*iter)?((*iter)->data):NULL;
188}
189struct skiplistnode *skiplist_insert(Skiplist *sl,
190			       void *data) {
191  if(!sl->compare) return 0;
192  return skiplist_insert_compare(sl, data, sl->compare);
193}
194
195struct skiplistnode *skiplist_insert_compare(Skiplist *sl,
196				       void *data,
197				       SkiplistComparator comp) {
198  struct skiplistnode *m, *p, *tmp, *ret, **stack;
199  int nh=1, ch, stacki;
200#ifdef SLDEBUG
201  skiplist_print_struct(sl, "BI: ");
202#endif
203  if(!sl->top) {
204    sl->height = 1;
205    sl->topend = sl->bottomend = sl->top = sl->bottom =
206      (struct skiplistnode *)malloc(sizeof(struct skiplistnode));
207    assert(sl->top);
208    sl->top->next = (struct skiplistnode *) NULL;
209    sl->top->data = (struct skiplistnode *) NULL;
210    sl->top->prev =(struct skiplistnode *) NULL;
211	sl->top->up = (struct skiplistnode *) NULL;
212    sl->top->down = (struct skiplistnode *) NULL;
213	sl->top->nextindex=  (struct skiplistnode *) NULL;
214    sl->top->previndex = (struct skiplistnode *) NULL;
215    sl->top->sl = sl;
216  }
217  if(sl->preheight) {
218    while(nh < sl->preheight && get_b_rand()) nh++;
219  } else {
220    while(nh <= sl->height && get_b_rand()) nh++;
221  }
222  /* Now we have the new height at which we wish to insert our new node */
223  /* Let us make sure that our tree is a least that tall (grow if necessary)*/
224  for(;sl->height<nh;sl->height++) {
225    sl->top->up =
226      (struct skiplistnode *)malloc(sizeof(struct skiplistnode));
227    assert(sl->top->up);
228    sl->top->up->down = sl->top;
229    sl->top = sl->topend = sl->top->up;
230    sl->top->prev = sl->top->next = sl->top->nextindex =
231      sl->top->previndex = sl->top->up = NULL;
232    sl->top->data = NULL;
233    sl->top->sl = sl;
234  }
235  ch = sl->height;
236  /* Find the node (or node after which we would insert) */
237  /* Keep a stack to pop back through for insertion */
238  m = sl->top;
239  stack = (struct skiplistnode **)malloc(sizeof(struct skiplistnode *)*(nh));
240  stacki=0;
241  while(m) {
242    int compared=-1;
243    if(m->next) compared=comp(data, m->next->data);
244    if(compared == 0) {
245      free(stack);
246      return 0;
247    }
248    if((m->next == NULL) || (compared<0)) {
249      if(ch<=nh) {
250	/* push on stack */
251	stack[stacki++] = m;
252      }
253      m = m->down;
254      ch--;
255    } else {
256      m = m->next;
257    }
258  }
259  /* Pop the stack and insert nodes */
260  p = NULL;
261  for(;stacki>0;stacki--) {
262    m = stack[stacki-1];
263    tmp = (struct skiplistnode *)malloc(sizeof(struct skiplistnode));
264    tmp->next = m->next;
265    if(m->next) m->next->prev=tmp;
266    tmp->prev = m;
267    tmp->up = NULL;
268    tmp->nextindex = tmp->previndex = NULL;
269    tmp->down = p;
270    if(p) p->up=tmp;
271    tmp->data = data;
272    tmp->sl = sl;
273    m->next = tmp;
274    /* This sets ret to the bottom-most node we are inserting */
275    if(!p) ret=tmp;
276    p = tmp;
277  }
278  free(stack);
279  if(sl->index != NULL) {
280    /* this is a external insertion, we must insert into each index as well */
281    struct skiplistnode *p, *ni, *li;
282    li=ret;
283    for(p = skiplist_getlist(sl->index); p; skiplist_next(sl->index, &p)) {
284      ni = skiplist_insert((Skiplist *)p->data, ret->data);
285      assert(ni);
286#ifdef SLDEBUG
287      fprintf(stderr, "Adding %p to index %p\n", ret->data, p->data);
288#endif
289      li->nextindex = ni;
290      ni->previndex = li;
291      li = ni;
292    }
293  } else {
294    sl->size++;
295  }
296#ifdef SLDEBUG
297  skiplist_print_struct(sl, "AI: ");
298#endif
299  return ret;
300}
301struct skiplistnode *skiplist_append(Skiplist *sl, void *data) {
302  int nh=1, ch, compared;
303  struct skiplistnode *lastnode, *nodeago;
304  if(sl->bottomend != sl->bottom) {
305    compared=sl->compare(data, sl->bottomend->prev->data);
306    /* If it doesn't belong at the end, then fail */
307    if(compared<=0) return NULL;
308  }
309  if(sl->preheight) {
310    while(nh < sl->preheight && get_b_rand()) nh++;
311  } else {
312    while(nh <= sl->height && get_b_rand()) nh++;
313  }
314  /* Now we have the new height at which we wish to insert our new node */
315  /* Let us make sure that our tree is a least that tall (grow if necessary)*/
316  lastnode = sl->bottomend;
317  nodeago = NULL;
318
319  if(!lastnode) return skiplist_insert(sl, data);
320
321  for(;sl->height<nh;sl->height++) {
322    sl->top->up =
323      (struct skiplistnode *)malloc(sizeof(struct skiplistnode));
324    assert(sl->top);
325    sl->top->up->down = sl->top;
326    sl->top = sl->top->up;
327    sl->top->prev = sl->top->next = sl->top->nextindex =
328      sl->top->previndex = NULL;
329    sl->top->data = NULL;
330    sl->top->sl = sl;
331  }
332  ch = sl->height;
333  while(nh) {
334    struct skiplistnode *anode;
335    anode =
336      (struct skiplistnode *)malloc(sizeof(struct skiplistnode));
337    anode->next = lastnode;
338    anode->prev = lastnode->prev;
339    anode->up = NULL;
340    anode->down = nodeago;
341    if(lastnode->prev) {
342      if(lastnode == sl->bottom)
343	sl->bottom = anode;
344      else if (lastnode == sl->top)
345	sl->top = anode;
346    }
347    nodeago = anode;
348    lastnode = lastnode->up;
349    nh--;
350  }
351  sl->size++;
352  return sl->bottomend;
353}
354Skiplist *skiplist_concat(Skiplist *sl1, Skiplist *sl2) {
355  /* Check integrity! */
356  int compared, eheight;
357  Skiplist temp;
358  struct skiplistnode *lbottom, *lbottomend, *b1, *e1, *b2, *e2;
359  if(sl1->bottomend == NULL || sl1->bottomend->prev == NULL) {
360    skiplist_remove_all(sl1, free);
361    temp = *sl1;
362    *sl1 = *sl2;
363    *sl2 = temp;
364    /* swap them so that sl2 can be freed normally upon return. */
365    return sl1;
366  }
367  if(sl2->bottom == NULL || sl2->bottom->next == NULL) {
368    skiplist_remove_all(sl2, free);
369    return sl1;
370  }
371  compared = sl1->compare(sl1->bottomend->prev->data, sl2->bottom->data);
372  /* If it doesn't belong at the end, then fail */
373  if(compared<=0) return NULL;
374
375  /* OK now append sl2 onto sl1 */
376  lbottom = lbottomend = NULL;
377  eheight = MIN(sl1->height, sl2->height);
378  b1 = sl1->bottom; e1 = sl1->bottomend;
379  b2 = sl2->bottom; e2 = sl2->bottomend;
380  while(eheight) {
381    e1->prev->next = b2;
382    b2->prev = e1->prev->next;
383    e2->prev->next = e1;
384    e1->prev = e2->prev;
385    e2->prev = NULL;
386    b2 = e2;
387    b1->down = lbottom;
388    e1->down = lbottomend;
389    if(lbottom) lbottom->up = b1;
390    if(lbottomend) lbottomend->up = e1;
391
392    lbottom = b1;
393    lbottomend = e1;
394  }
395  /* Take the top of the longer one (if it is sl2) and make it sl1's */
396  if(sl2->height > sl1->height) {
397    b1->up = b2->up;
398    e1->up = e2->up;
399    b1->up->down = b1;
400    e1->up->down = e1;
401    sl1->height = sl2->height;
402    sl1->top = sl2->top;
403    sl1->topend = sl2->topend;
404  }
405
406  /* move the top pointer to here if it isn't there already */
407  sl2->top = sl2->topend = b2;
408  sl2->top->up = NULL; /* If it isn't already */
409  sl1->size += sl2->size;
410  skiplist_remove_all(sl2, free);
411  return sl1;
412}
413int skiplist_remove(Skiplist *sl,
414	      void *data, FreeFunc myfree) {
415  if(!sl->compare) return 0;
416  return skiplist_remove_compare(sl, data, myfree, sl->comparek);
417}
418void skiplist_print_struct(Skiplist *sl, char *prefix) {
419  struct skiplistnode *p, *q;
420  fprintf(stderr, "Skiplist Structure (height: %d)\n", sl->height);
421  p = sl->bottom;
422  while(p) {
423    q = p;
424    fprintf(stderr, prefix);
425    while(q) {
426      fprintf(stderr, "%p ", q->data);
427      q=q->up;
428    }
429    fprintf(stderr, "\n");
430    p=p->next;
431  }
432}
433int skiplisti_remove(Skiplist *sl, struct skiplistnode *m, FreeFunc myfree) {
434  struct skiplistnode *p;
435  if(!m) return 0;
436  if(m->nextindex) skiplisti_remove(m->nextindex->sl, m->nextindex, NULL);
437  else sl->size--;
438#ifdef SLDEBUG
439  skiplist_print_struct(sl, "BR:");
440#endif
441  while(m->up) m=m->up;
442  while(m) {
443    p=m;
444    p->prev->next = p->next; /* take me out of the list */
445    if(p->next) p->next->prev = p->prev; /* take me out of the list */
446    m=m->down;
447    /* This only frees the actual data in the bottom one */
448    if(!m && myfree && p->data) myfree(p->data);
449    free(p);
450  }
451  while(sl->top && sl->top->next == NULL) {
452    /* While the row is empty and we are not on the bottom row */
453    p = sl->top;
454    sl->top = sl->top->down; /* Move top down one */
455    if(sl->top) sl->top->up = NULL;      /* Make it think its the top */
456    free(p);
457    sl->height--;
458  }
459  if(!sl->top) sl->bottom = NULL;
460  assert(sl->height>=0);
461#ifdef SLDEBUG
462  skiplist_print_struct(sl, "AR: ");
463#endif
464  return sl->height;
465}
466int skiplist_remove_compare(Skiplist *sli,
467		      void *data,
468		      FreeFunc myfree, SkiplistComparator comp) {
469  struct skiplistnode *m;
470  Skiplist *sl;
471  if(comp==sli->comparek || !sli->index) {
472    sl = sli;
473  } else {
474    skiplist_find(sli->index, (void *)comp, &m);
475    assert(m);
476    sl= (Skiplist *) m->data;
477  }
478  skiplisti_find_compare(sl, data, &m, comp);
479  if(!m) return 0;
480  while(m->previndex) m=m->previndex;
481  return skiplisti_remove(sl, m, myfree);
482}
483void skiplist_remove_all(Skiplist *sl, FreeFunc myfree) {
484  /* This must remove even the place holder nodes (bottom though top)
485     because we specify in the API that one can free the Skiplist after
486     making this call without memory leaks */
487  struct skiplistnode *m, *p, *u;
488  m=sl->bottom;
489  while(m) {
490    p = m->next;
491    if(myfree && p->data) myfree(p->data);
492    while(m) {
493      u = m->up;
494      free(m);
495      m=u;
496    }
497    m = p;
498  }
499  sl->top = sl->bottom = NULL;
500  sl->height = 0;
501  sl->size = 0;
502}
503
504void *skiplist_pop(Skiplist * a, FreeFunc myfree)
505{
506  struct skiplistnode *sln;
507  void *data = NULL;
508  sln = skiplist_getlist(a);
509  if (sln) {
510    data = sln->data;
511    skiplisti_remove(a, sln, myfree);
512  }
513  return data;
514}
515