SHARE
TWEET

Untitled

a guest Feb 23rd, 2019 165 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  
  3. Example of Skip List source code for C:
  4.  
  5. Skip Lists are a probabilistic alternative to balanced trees, as
  6. described in the June 1990 issue of CACM and were invented by
  7. William Pugh in 1987.
  8.  
  9. This file contains source code to implement a dictionary using
  10. skip lists and a test driver to test the routines.
  11.  
  12. A couple of comments about this implementation:
  13.   The routine randomLevel has been hard-coded to generate random
  14.   levels using p=0.25. It can be easily changed.
  15.  
  16.   The insertion routine has been implemented so as to use the
  17.   dirty hack described in the CACM paper: if a random level is
  18.   generated that is more than the current maximum level, the
  19.   current maximum level plus one is used instead.
  20.  
  21.   Levels start at zero and go up to MaxLevel (which is equal to
  22.     (MaxNumberOfLevels-1).
  23.  
  24. The compile flag allowDuplicates determines whether or not duplicates
  25. are allowed. If defined, duplicates are allowed and act in a FIFO manner.
  26. If not defined, an insertion of a value already in the file updates the
  27. previously existing binding.
  28.  
  29. BitsInRandom is defined to be the number of bits returned by a call to
  30. random(). For most all machines with 32-bit integers, this is 31 bits
  31. as currently set.
  32.  
  33. The routines defined in this file are:
  34.  
  35.   init: defines NIL and initializes the random bit source
  36.  
  37.   newList: returns a new, empty list
  38.  
  39.   freeList(l): deallocates the list l (along with any elements in l)
  40.  
  41.   randomLevel: Returns a random level
  42.  
  43.   insert(l,key,value): inserts the binding (key,value) into l. If
  44.     allowDuplicates is undefined, returns true if key was newly
  45.     inserted into the list, false if key already existed
  46.  
  47.   delete(l,key): deletes any binding of key from the l. Returns
  48.     false if key was not defined.
  49.  
  50.   search(l,key,&value): Searches for key in l and returns true if found.
  51.     If found, the value associated with key is stored in the
  52.     location pointed to by &value
  53.  
  54. */
  55.  
  56.  
  57. #define false 0
  58. #define true 1
  59. typedef char boolean;
  60. #define BitsInRandom 31
  61.  
  62. #define allowDuplicates
  63.  
  64. #define MaxNumberOfLevels 16
  65. #define MaxLevel (MaxNumberOfLevels-1)
  66. #define newNodeOfLevel(l) (node)malloc(sizeof(struct nodeStructure)+(l)*sizeof(node *))
  67.  
  68. typedef int keyType;
  69. typedef int valueType;
  70.  
  71. #ifdef allowDuplicates
  72. boolean delete(), search();
  73. void insert();
  74. #else
  75. boolean insert(), delete(), search();
  76. #endif
  77.  
  78. typedef struct nodeStructure *node;
  79.  
  80. typedef struct nodeStructure{
  81.     keyType key;
  82.     valueType value;
  83.     node forward[1]; /* variable sized array of forward pointers */
  84.     };
  85.  
  86. typedef struct listStructure{
  87.    int level;     /* Maximum level of the list
  88.             (1 more than the number of levels in the list) */
  89.    struct nodeStructure * header; /* pointer to header */
  90.    } * list;
  91.  
  92. node NIL;
  93.  
  94. int randomsLeft;
  95. int randomBits;
  96.  
  97. init() {
  98.   NIL = newNodeOfLevel(0);
  99.   NIL->key = 0x7fffffff;
  100.   randomBits = random();
  101.   randomsLeft = BitsInRandom/2;
  102. };
  103.  
  104. list newList() {
  105.   list l;
  106.   int i;
  107.  
  108.   l = (list)malloc(sizeof(struct listStructure));
  109.   l->level = 0;
  110.   l->header = newNodeOfLevel(MaxNumberOfLevels);
  111.   for(i=0;i<MaxNumberOfLevels;i++) l->header->forward[i] = NIL;
  112.   return(l);
  113.   };
  114.  
  115. freeList(l)
  116.   list l;
  117.   {
  118.   register node p,q;
  119.   p = l->header;
  120.   do {
  121.     q = p->forward[0];
  122.     free(p);
  123.     p = q; }
  124.     while (p!=NIL);
  125.   free(l);
  126.   };
  127.  
  128. int randomLevel()
  129.   {register int level = 0;
  130.    register int b;
  131.    do {
  132.     b = randomBits&3;
  133.     if (!b) level++;
  134.     randomBits>>=2;
  135.     if (--randomsLeft == 0) {
  136.         randomBits = random();
  137.         randomsLeft = BitsInRandom/2;
  138.         };
  139.     } while (!b);
  140.     return(level>MaxLevel ? MaxLevel : level);
  141.     };
  142.  
  143. #ifdef allowDuplicates
  144. void insert(l,key,value)
  145. #else
  146. boolean insert(l,key,value)
  147. #endif
  148.  
  149. register list l;
  150. register keyType key;
  151. register valueType value;
  152.   {
  153.   register int k;
  154.   node update[MaxNumberOfLevels];
  155.   register node p,q;
  156.  
  157.   p = l->header;
  158.   k = l->level;
  159.   do {
  160.     while (q = p->forward[k], q->key < key) p = q;
  161.     update[k] = p;
  162.     } while(--k>=0);
  163.  
  164. #ifndef allowDuplicates
  165.   if (q->key == key) {
  166.         q->value = value;
  167.     return(false);
  168.     };
  169. #endif
  170.  
  171.     k = randomLevel();
  172.     if (k>l->level) {
  173.     k = ++l->level;
  174.     update[k] = l->header;
  175.     };
  176.     q = newNodeOfLevel(k);
  177.     q->key = key;
  178.     q->value = value;
  179.     do {
  180.     p = update[k];
  181.     q->forward[k] = p->forward[k];
  182.     p->forward[k] = q;
  183.     } while(--k>=0);
  184. #ifndef allowDuplicates
  185.     return(true);
  186. #endif
  187.     }
  188.  
  189. boolean delete(l,key)
  190. register list l;
  191. register keyType key;
  192.   {
  193.   register int k,m;
  194.   node update[MaxNumberOfLevels];
  195.   register node p,q;
  196.  
  197.   p = l->header;
  198.   k = m = l->level;
  199.   do {
  200.     while (q = p->forward[k], q->key < key) p = q;
  201.     update[k] = p;
  202.     } while(--k>=0);
  203.  
  204.   if (q->key == key) {
  205.     for(k=0; k<=m && (p=update[k])->forward[k] == q; k++)
  206.       p->forward[k] = q->forward[k];
  207.     free(q);
  208.         while( l->header->forward[m] == NIL && m > 0 )
  209.          m--;
  210.     l->level = m;
  211.     return(true);
  212.     }
  213.     else return(false);
  214.     }
  215.  
  216. boolean search(l,key,valuePointer)
  217. register list l;
  218. register keyType key;
  219. valueType * valuePointer;
  220.   {
  221.   register int k;
  222.   register node p,q;
  223.   p = l->header;
  224.   k = l->level;
  225.   do while (q = p->forward[k], q->key < key) p = q;
  226.       while (--k>=0);
  227.   if (q->key != key) return(false);
  228.   *valuePointer = q->value;
  229.   return(true);
  230.   };
  231.  
  232. #define sampleSize 65536
  233. main() {
  234.   list l;
  235.   register int i,k;
  236.   keyType keys[sampleSize];
  237.   valueType v;
  238.  
  239.   init();
  240.  
  241.   l= newList();
  242.  
  243.   for(k=0;k<sampleSize;k++) {
  244.         keys[k]=random();
  245.         insert(l,keys[k],keys[k]);
  246.         };
  247.  
  248.  
  249.   for(i=0;i<4;i++) {
  250.         for(k=0;k<sampleSize;k++) {
  251.         if (!search(l,keys[k],&v)) printf("error in search #%d,#%d\n",i,k);
  252.         if (v != keys[k]) printf("search returned wrong value\n");
  253.             };
  254.         for(k=0;k<sampleSize;k++) {
  255.         if (! delete(l,keys[k])) printf("error in delete\n");
  256.             keys[k] = random();
  257.         insert(l,keys[k],keys[k]);
  258.             };
  259.         };
  260.  
  261.   freeList(l);
  262.  
  263.   };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top