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