skip.c

   1
   2 /* Skiplists.
   3    Provide three functions to skip_new:
   4      cmp(e1, e2, k)
   5      This should compare e1 with e2 or (if null) k (a key)
   6    free should free an entry
   7    errfn should do something with an error message
   8
   9    skip_new(cmp,free,errfn) -> list
  10    skip_insert(list,entry) -> bool
  11    skip_delete(list,key) -> bool
  12    skip_search(list,key) -> *entry
  13    skip_first(list) -> *entry
  14    skip_next(*entry) -> *entry
  15
  16    */
  17 #include        <unistd.h>
  18 #include        <stdlib.h>
  19 #include        <string.h>
  20
  21 #define false 0
  22 #define true 1
  23 typedef char boolean;
  24 #define BitsInRandom 31
  25
  26 #define MaxNumberOfLevels 16
  27 #define MaxLevel (MaxNumberOfLevels-1)
  28 #define newNodeOfLevel(l) (node)malloc(sizeof(struct node)+(l)*sizeof(node))
  29
  30 typedef void *keyType;
  31 typedef void *valueType;
  32
  33
  34 typedef struct node
  35 {
  36         valueType value;                /* must be first for skip_next to work */
  37         struct node *forward[1];        /* variable sized array of forward pointers */
  38 } *node;
  39
  40 typedef struct list
  41 {
  42         int level;      /* Maximum level of the list
  43                            (1 more than the number of levels in the list) */
  44         node    header; /* pointer to head of list */
  45         int     (*cmpfn)();     /* compares two values or a key an a value */
  46         void (*freefn)();       /* free a value */
  47         void (*errfn)();        /* when malloc error occurs */
  48 } *list;
  49
  50 static void default_errfn(char *msg)
  51 {
  52         write(2, msg, (int)strlen(msg));
  53         write(2, "\n", 2);
  54         abort();
  55 }
  56
  57 static int randomsLeft = 0;
  58 static int randomBits;
  59
  60 list skip_new(
  61         int (*cmpfn)(),
  62         void (*freefn)(),
  63         void (*errfn)())
  64 {
  65         list l;
  66         int i;
  67
  68         if (errfn == NULL)
  69                 errfn = default_errfn;
  70         l = (list)malloc(sizeof(struct list));
  71         if (l == NULL)
  72         {
  73                 (*errfn)("Malloc failed in skip_new");
  74                 return NULL;
  75         }
  76         l->level = 0;
  77         l->header = newNodeOfLevel(MaxNumberOfLevels);
  78         if (l->header == NULL)
  79         {
  80                 (*errfn)("Malloc failed in skip_new");
  81                 return NULL;
  82         }
  83         for (i=0; i<MaxNumberOfLevels; i++)
  84                 l->header->forward[i] = NULL;
  85         l->header->value = NULL;
  86         l->cmpfn = cmpfn;
  87         l->freefn = freefn;
  88         if (errfn)
  89                 l->errfn = errfn;
  90         else
  91                 l->errfn = default_errfn;
  92         return l;
  93 }
  94
  95 void skip_free(list l)
  96 {
  97         register node p;
  98         p = l->header;
  99         while (p != NULL)
 100         {
 101                 register node q;
 102                 q = p->forward[0];
 103                 if (p != l->header) /* header has no meaningful value */
 104                         (*l->freefn)(p->value);
 105                 free(p);
 106                 p = q;
 107         }
 108         free(l);
 109 }
 110
 111 static int randomLevel()
 112 {
 113         register int level = 0;
 114         register int b;
 115         do {
 116                 if (randomsLeft == 0) {
 117 #ifdef POSIX
 118                         randomBits = lrand48();
 119 #else
 120                         randomBits = random();
 121 #endif
 122                         randomsLeft = BitsInRandom/2;
 123                 }
 124                 b = randomBits&3;
 125                 randomBits>>=2;
 126                 randomsLeft--;
 127                 if (!b) level++;
 128         } while (!b);
 129         return(level>MaxLevel ? MaxLevel : level);
 130 }
 131
 132 boolean skip_insert(list l, valueType value)
 133 {
 134         int k;
 135         node update[MaxNumberOfLevels];
 136         node p,q;
 137         int cm=0;
 138
 139         p = l->header;
 140         for (k=l->level ; k>=0 ; k--)
 141         {
 142                 cm = 1;
 143                 while ( p->forward[k] != NULL
 144                         && (cm=(*l->cmpfn)(p->forward[k]->value, value, 0))<0)
 145                         p = p->forward[k];
 146                 update[k] = p;
 147         }
 148
 149         if (cm == 0)
 150                 return false;
 151
 152         k = randomLevel();
 153         if (k> l->level)
 154         {
 155                 k = ++l->level;
 156                 update[k] = l->header;
 157         }
 158         q = newNodeOfLevel(k);
 159         if (q == NULL)
 160         {
 161                 (*l->errfn)("Malloc failed in skip_insert");
 162                 return false;
 163         }
 164         q->value = value;
 165         for ( ; k>=0 ; k--)
 166         {
 167                 p = update[k];
 168                 q->forward[k] = p->forward[k];
 169                 p->forward[k] = q;
 170         }
 171         return true;
 172 }
 173
 174 boolean skip_delete(list l, keyType key)
 175 {
 176         int k, m;
 177         node update[MaxNumberOfLevels];
 178         node p,q;
 179         int cm = 0;
 180
 181         p = l->header;
 182
 183         for (k=l->level ; k>=0 ; k--)
 184         {
 185                 cm = 1;
 186                 while ( p->forward[k] != NULL
 187                         && (cm=(*l->cmpfn)(p->forward[k]->value, NULL, key))<0)
 188                         p = p->forward[k];
 189                 update[k] = p;
 190         }
 191
 192         if (cm == 0)
 193         {
 194                 q = update[0]->forward[0];
 195                 m=l->level;
 196                 for (k=0; k<=m && (p=update[k])->forward[k] == q ; k++)
 197                         p->forward[k] = q->forward[k];
 198                 if (l->freefn)
 199                         (*l->freefn)(q->value);
 200                 free(q);
 201                 while (l->header->forward[m] == NULL && m > 0)
 202                         m--;
 203                 l->level = m;
 204                 return true;
 205         }
 206         else
 207                 return false;
 208 }
 209
 210 valueType *skip_search(list l, keyType key)
 211 {
 212         int k;
 213         node p;
 214         int cm = 0;
 215
 216         p = l->header;
 217         for (k=l->level ; k>=0 ; k--)
 218         {
 219                 cm = 1;
 220                 while ( p->forward[k] != NULL
 221                         && (cm=(*l->cmpfn)(p->forward[k]->value, NULL, key))<0)
 222                         p = p->forward[k];
 223         }
 224         if (cm != 0)
 225                 return NULL;
 226         return &p->forward[0]->value;
 227 }
 228
 229 valueType *skip_first(list l)
 230 {
 231         node p;
 232
 233         p = l->header;
 234         if (p->forward[0] == NULL)
 235                 return NULL;
 236         return & p->forward[0]->value;
 237 }
 238
 239 valueType *skip_next(valueType *c)
 240 {
 241         node p;
 242         p = (node)c;
 243         if (p->forward[0] == NULL)
 244                 return NULL;
 245         return & p->forward[0]->value;
 246 }