root/src/utils/noit_skiplist.c

/* ======================================================================
 * Copyright (c) 2000,2006 Theo Schlossnagle
 * All rights reserved.
 * The following code was written by Theo Schlossnagle for use in the
 * Backhand project at The Center for Networking and Distributed Systems
 * at The Johns Hopkins University.
 *
 * This is a skiplist implementation to be used for abstract structures
 * and is release under the LGPL license version 2.1 or later.  A copy
 * of this license can be found file LGPL.
 *
 * Alternatively, this file may be licensed under the new BSD license.
 * A copy of this license can be found file BSD.
 * 
 * ======================================================================
*/

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#include "noit_skiplist.h"

#ifndef MIN
#define MIN(a,b) ((a<b)?(a):(b))
#endif

int noit_compare_voidptr(void *a, void *b) {
  if(a < b) return -1;
  if(a == b) return 0;
  return 1;
}

static int get_b_rand(void) {
  static int ph=32; /* More bits than we will ever use */
  static unsigned long randseq;
  if(ph > 31) { /* Num bits in return of lrand48() */
    ph=0;
    randseq = lrand48();
  }
  ph++;
  return ((randseq & (1 << (ph-1))) >> (ph-1));
}

void noit_skiplisti_init(noit_skiplist *sl) {
  sl->compare = (noit_skiplist_comparator_t)NULL;
  sl->comparek = (noit_skiplist_comparator_t)NULL;
  sl->height=0;
  sl->preheight=0;
  sl->size=0;
  sl->top = NULL;
  sl->bottom = NULL;
  sl->index = NULL;
}

static int indexing_comp(void *a, void *b) {
  assert(a);
  assert(b);
  return (void *)(((noit_skiplist *)a)->compare)>(void *)(((noit_skiplist *)b)->compare);
}
static int indexing_compk(void *a, void *b) {
  assert(b);
  return a>(void *)(((noit_skiplist *)b)->compare);
}

void noit_skiplist_init(noit_skiplist *sl) {
  noit_skiplisti_init(sl);
  sl->index = (noit_skiplist *)malloc(sizeof(noit_skiplist));
  noit_skiplisti_init(sl->index);
  noit_skiplist_set_compare(sl->index, indexing_comp, indexing_compk);
}

void noit_skiplist_set_compare(noit_skiplist *sl,
                    noit_skiplist_comparator_t comp,
                    noit_skiplist_comparator_t compk) {
  if(sl->compare && sl->comparek) {
    noit_skiplist_add_index(sl, comp, compk);
  } else {
    sl->compare = comp;
    sl->comparek = compk;
  }
}

void noit_skiplist_add_index(noit_skiplist *sl,
                  noit_skiplist_comparator_t comp,
                  noit_skiplist_comparator_t compk) {
  noit_skiplist_node *m;
  noit_skiplist *ni;
  int icount=0;
  noit_skiplist_find(sl->index, (void *)comp, &m);
  if(m) return; /* Index already there! */
  ni = (noit_skiplist *)malloc(sizeof(noit_skiplist));
  noit_skiplisti_init(ni);
  noit_skiplist_set_compare(ni, comp, compk);
  /* Build the new index... This can be expensive! */
  m = noit_skiplist_insert(sl->index, ni);
  while(m->prev) m=m->prev, icount++;
  for(m=noit_skiplist_getlist(sl); m; noit_skiplist_next(sl, &m)) {
    int j=icount-1;
    noit_skiplist_node *nsln;
    nsln = noit_skiplist_insert(ni, m->data);
    /* skip from main index down list */
    while(j>0) m=m->nextindex, j--;
    /* insert this node in the indexlist after m */
    nsln->nextindex = m->nextindex;
    if(m->nextindex) m->nextindex->previndex = nsln;
    nsln->previndex = m;
    m->nextindex = nsln;
  } 
}

noit_skiplist_node *noit_skiplist_getlist(noit_skiplist *sl) {
  if(!sl->bottom) return NULL;
  return sl->bottom->next;
}

void *noit_skiplist_find(noit_skiplist *sl,
              void *data,
              noit_skiplist_node **iter) {
  void *ret;
  noit_skiplist_node *aiter;
  if(!sl->compare) return 0;
  if(iter)
    ret = noit_skiplist_find_compare(sl, data, iter, sl->compare);
  else
    ret = noit_skiplist_find_compare(sl, data, &aiter, sl->compare);
  return ret;
}  
void *noit_skiplist_find_compare(noit_skiplist *sli,
                      void *data,
                      noit_skiplist_node **iter,
                      noit_skiplist_comparator_t comp) {
  noit_skiplist_node *m = NULL;
  noit_skiplist *sl;
  if(comp==sli->compare || !sli->index) {
    sl = sli;
  } else {
    noit_skiplist_find(sli->index, (void *)comp, &m);
    assert(m);
    sl= (noit_skiplist *) m->data;
  }
  noit_skiplisti_find_compare(sl, data, iter, sl->comparek);
  return (*iter)?((*iter)->data):(*iter);
}
int noit_skiplisti_find_compare(noit_skiplist *sl,
                     void *data,
                     noit_skiplist_node **ret,
                     noit_skiplist_comparator_t comp) {
  noit_skiplist_node *m = NULL;
  int count=0;
  m = sl->top;
  while(m) {
    int compared = -1;
    if(m->next) compared=comp(data, m->next->data);
    if(compared == 0) {
#ifdef SL_DEBUG
      printf("Looking -- found in %d steps\n", count);
#endif
      m=m->next;
      while(m->down) m=m->down;
      *ret = m;
      return count;
    }
    if((m->next == NULL) || (compared<0))
      m = m->down, count++;
    else
      m = m->next, count++;
  }
#ifdef SL_DEBUG
  printf("Looking -- not found in %d steps\n", count);
#endif
  *ret = NULL;
  return count;
}
void *noit_skiplist_next(noit_skiplist *sl, noit_skiplist_node **iter) {
  if(!*iter) return NULL;
  *iter = (*iter)->next;
  return (*iter)?((*iter)->data):NULL;
}
void *noit_skiplist_previous(noit_skiplist *sl, noit_skiplist_node **iter) {
  if(!*iter) return NULL;
  *iter = (*iter)->prev;
  return (*iter)?((*iter)->data):NULL;
}
noit_skiplist_node *noit_skiplist_insert(noit_skiplist *sl,
                               void *data) {
  if(!sl->compare) return 0;
  return noit_skiplist_insert_compare(sl, data, sl->compare);
}

noit_skiplist_node *noit_skiplist_insert_compare(noit_skiplist *sl,
                                       void *data,
                                       noit_skiplist_comparator_t comp) {
  noit_skiplist_node *m, *p, *tmp, *ret = NULL, **stack;
  int nh=1, ch, stacki;
  if(!sl->top) {
    sl->height = 1;
    sl->topend = sl->bottomend = sl->top = sl->bottom = 
      (noit_skiplist_node *)malloc(sizeof(noit_skiplist_node));
    assert(sl->top);
    sl->top->next = (noit_skiplist_node *) NULL;
    sl->top->data = (noit_skiplist_node *) NULL;
    sl->top->prev =(noit_skiplist_node *) NULL;
        sl->top->up = (noit_skiplist_node *) NULL;
    sl->top->down = (noit_skiplist_node *) NULL;
        sl->top->nextindex=  (noit_skiplist_node *) NULL;
    sl->top->previndex = (noit_skiplist_node *) NULL;
    sl->top->sl = sl;
  }
  if(sl->preheight) {
    while(nh < sl->preheight && get_b_rand()) nh++;
  } else {
    while(nh <= sl->height && get_b_rand()) nh++;
  }
  /* Now we have the new height at which we wish to insert our new node */
  /* Let us make sure that our tree is a least that tall (grow if necessary)*/
  for(;sl->height<nh;sl->height++) {
    sl->top->up =
      (noit_skiplist_node *)malloc(sizeof(noit_skiplist_node));
    assert(sl->top->up);
    sl->top->up->down = sl->top;
    sl->top = sl->topend = sl->top->up;
    sl->top->prev = sl->top->next = sl->top->nextindex =
      sl->top->previndex = sl->top->up = NULL;
    sl->top->data = NULL;
    sl->top->sl = sl;
  }
  ch = sl->height;
  /* Find the node (or node after which we would insert) */
  /* Keep a stack to pop back through for insertion */
  m = sl->top;
  stack = (noit_skiplist_node **)malloc(sizeof(noit_skiplist_node *)*(nh));
  stacki=0;
  while(m) {
    int compared=-1;
    if(m->next) compared=comp(data, m->next->data);
    if(compared == 0) {
      free(stack);
      return 0;
    }
    if((m->next == NULL) || (compared<0)) {
      if(ch<=nh) {
        /* push on stack */
        stack[stacki++] = m;
      }
      m = m->down;
      ch--;
    } else {
      m = m->next;
    }
  }
  /* Pop the stack and insert nodes */
  p = NULL;
  for(;stacki>0;stacki--) {
    m = stack[stacki-1];
    tmp = (noit_skiplist_node *)malloc(sizeof(noit_skiplist_node));
    tmp->next = m->next;
    if(m->next) m->next->prev=tmp;
    tmp->prev = m;
    tmp->up = NULL;
    tmp->nextindex = tmp->previndex = NULL;
    tmp->down = p;
    if(p) p->up=tmp;
    tmp->data = data;
    tmp->sl = sl;
    m->next = tmp;
    /* This sets ret to the bottom-most node we are inserting */
    if(!p) ret=tmp;
    p = tmp;
  }
  free(stack);
  if(sl->index != NULL) {
    /* this is a external insertion, we must insert into each index as well */
    noit_skiplist_node *p, *ni, *li;
    li=ret;
    for(p = noit_skiplist_getlist(sl->index); p; noit_skiplist_next(sl->index, &p)) {
      ni = noit_skiplist_insert((noit_skiplist *)p->data, ret->data);
      assert(ni);
      li->nextindex = ni;
      ni->previndex = li;
      li = ni;
    }
  } else {
    sl->size++;
  }
  return ret;
}
int noit_skiplist_remove(noit_skiplist *sl,
              void *data, noit_freefunc_t myfree) {
  if(!sl->compare) return 0;
  return noit_skiplist_remove_compare(sl, data, myfree, sl->comparek);
}
int noit_skiplisti_remove(noit_skiplist *sl, noit_skiplist_node *m, noit_freefunc_t myfree) {
  noit_skiplist_node *p;
  if(!m) return 0;
  if(m->nextindex) noit_skiplisti_remove(m->nextindex->sl, m->nextindex, NULL);
  else sl->size--;
  while(m->up) m=m->up;
  while(m) {
    p=m;
    p->prev->next = p->next; /* take me out of the list */
    if(p->next) p->next->prev = p->prev; /* take me out of the list */
    m=m->down;
    /* This only frees the actual data in the bottom one */
    if(!m && myfree && p->data) myfree(p->data);
    free(p);
  }
  while(sl->top && sl->top->next == NULL) {
    /* While the row is empty and we are not on the bottom row */
    p = sl->top;
    sl->top = sl->top->down; /* Move top down one */
    if(sl->top) sl->top->up = NULL;      /* Make it think its the top */
    free(p);
    sl->height--;
  }
  if(!sl->top) sl->bottom = NULL;
  assert(sl->height>=0);
  return sl->height;
}
int noit_skiplist_remove_compare(noit_skiplist *sli,
                      void *data,
                      noit_freefunc_t myfree, noit_skiplist_comparator_t comp) {
  noit_skiplist_node *m;
  noit_skiplist *sl;
  if(comp==sli->comparek || !sli->index) {
    sl = sli;
  } else {
    noit_skiplist_find(sli->index, (void *)comp, &m);
    assert(m);
    sl= (noit_skiplist *) m->data;
  }
  noit_skiplisti_find_compare(sl, data, &m, comp);
  if(!m) return 0;
  while(m->previndex) m=m->previndex;
  return noit_skiplisti_remove(sl, m, myfree);
}
void noit_skiplist_remove_all(noit_skiplist *sl, noit_freefunc_t myfree) {
  /* This must remove even the place holder nodes (bottom though top)
     because we specify in the API that one can free the noit_skiplist after
     making this call without memory leaks */
  noit_skiplist_node *m, *p, *u;
  m=sl->bottom;
  while(m) {
    p = m->next;
    if(myfree && p->data) myfree(p->data);
    while(m) {
      u = m->up;
      free(m);
      m=u;
    }
    m = p;
  }
  sl->top = sl->bottom = NULL;
  sl->height = 0;
  sl->size = 0;
}

void *noit_skiplist_pop(noit_skiplist * a, noit_freefunc_t myfree)
{
  noit_skiplist_node *sln;
  void *data = NULL;
  sln = noit_skiplist_getlist(a);
  if (sln) {
    data = sln->data;
    noit_skiplisti_remove(a, sln, myfree);
  }
  return data;
}
void *noit_skiplist_peek(noit_skiplist * a)
{
  noit_skiplist_node *sln;
  sln = noit_skiplist_getlist(a);
  if (sln) {
    return sln->data;
  }
  return NULL;
}