home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / unix / volume26 / philspell-1.0 / part01 / skiplist.c < prev    next >
C/C++ Source or Header  |  1993-05-01  |  4KB  |  139 lines
  1. /*
  2.  * Skiplist library COPYRIGHT (c) 1992, 1991, 1990, 1989, 1988, 1987 by
  3.  * Phillip "Edward" Nunez.  I wrote all this stuff and had it copyrighted
  4.  * and don't let anyone ever tell you any different!
  5.  *
  6.  */
  7.  
  8. #include <stdio.h>
  9. #include <assert.h>
  10.  
  11. #include "skiplist.h"
  12.  
  13. #define PROBABILITY 4
  14.  
  15. /*
  16.  * The definition of PROBABILITY determines how many pointers per node an
  17.  * element of a skiplist has.  A PROBABILITY of 4 means each node will have
  18.  * (3/4)1 + (1/4)(3/4)2 + (1/4)(1/4)(3/4)3... ~~ 1.31 pointers per node.
  19.  * A PROBABILITY of 5 yields (4/5)1 + (1/5)(4/5)2... ~~ 1.24 p/node.
  20.  */
  21.  
  22. #define RANDOM rand
  23.  
  24. /*
  25.  * The RANDOM function you define here should be seeded in your main program.
  26.  */
  27.  
  28. /*
  29.  * skip_create creates the header node for a skiplist.  The pointer to this
  30.  * node is what you should use to refer to the skiplist.  The argument 'max'
  31.  * determines the maximum height of any node in the skiplist; the head is
  32.  * always this high.  Skiplists can store on the order of 2^n elements
  33.  * efficiently where n is that maximum height.
  34.  */
  35.  
  36. skipnode skip_create(int max) {
  37.  
  38.     skipnode newnode;
  39.     int i;
  40.  
  41.     newnode = (skipnode)malloc(sizeof(struct skipnode) + sizeof(skipnode) * max);
  42.     assert(newnode != NULL);
  43.  
  44.     newnode->name = "";
  45.     newnode->ptr = NULL;
  46.  
  47.     for (i = 0; i <= max; i++) newnode->next[i] = newnode;
  48.     return newnode;
  49. }
  50.  
  51. /*
  52.  * skip_add adds an item to the skiplist.  'name' is the name (key)
  53.  * to the data; 'ptr' is the data; level is the maximum level (the same
  54.  * as used in the call to skip_create) and 'node' is the skiplist you're
  55.  * looking things up in.
  56.  *
  57.  * The 'name' parameter must have been allocated with 'malloc' or somesimilar.
  58.  * It will be freed when the node disappears.
  59.  */
  60.  
  61. void skip_add(char *name, void *ptr, skipnode node, int level) {
  62.  
  63.     skipnode newnode;
  64.     int size, newlevel;
  65.  
  66.     newlevel = 0;
  67.     while (RANDOM() % PROBABILITY) newlevel++;
  68.     if (newlevel > level) newlevel = level;
  69.  
  70.         size = sizeof(struct skipnode) + sizeof(skipnode) * newlevel;
  71.         newnode = (skipnode)malloc(size);
  72.     newnode->name = name;
  73.     newnode->ptr = ptr;
  74.  
  75.     while (level >= 0) {
  76.         while (strcasecmp(name, node->next[level]->name) < 0)
  77.             node = node->next[level];
  78.         if (level <= newlevel) {
  79.             newnode->next[level] = node->next[level];
  80.             node->next[level] = newnode;
  81.         }
  82.         level--;
  83.     }
  84. }
  85.  
  86. /*
  87.  * skip_lookup: Given the name of the data, the skiplist, the
  88.  * max level, and the default to return if the data cannot be found,
  89.  * look up the data in the list.
  90.  */
  91.  
  92. void *skip_lookup(char *name, skipnode node, int level, void *def) {
  93.         int d;
  94.  
  95.         while (level >= 0) {
  96.                 while ((d = strcasecmp(name, node->next[level]->name)) < 0)
  97.                         node = node->next[level];
  98.                 if (!d) return node->next[level]->ptr;
  99.                 level--;
  100.         }
  101.         return def;
  102. }
  103.  
  104. /*
  105.  * skip_remove: remove a skipnode from a the skiplist given.  'name'
  106.  * is the key, 'level' is the max level.
  107.  */
  108.  
  109. void skip_remove(char *name, skipnode node, int level) {
  110.     int cmpsav;
  111.     skipnode n;
  112.  
  113.     while (level >= 0) {
  114.         while ((cmpsav = strcasecmp(name, node->next[level]->name)) < 0)
  115.             node = node->next[level];
  116.         if (cmpsav == 0)
  117.             n = node->next[level];
  118.             node->next[level] = node->next[level]->next[level];
  119.         level--;
  120.     }
  121.     free(n->name);
  122.     free(n);
  123. }
  124.  
  125. /*
  126.  * skip_free: free an entire skiplist.
  127.  */
  128.  
  129. void skip_free(skipnode node) {
  130.     skipnode m, n = node->next[0];
  131.     while (n != node) {
  132.         free(n->name);
  133.         m = n->next[0];
  134.         free(n);
  135.         n = m;
  136.     }
  137.     free(node);
  138. }
  139.