home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / snip9707.zip / HASH.C < prev    next >
C/C++ Source or Header  |  1997-07-05  |  9KB  |  345 lines
  1. /* +++Date last modified: 05-Jul-1997 */
  2.  
  3. #include <string.h>
  4. #include <stdlib.h>
  5.  
  6. #include "hash.h"
  7.  
  8. /*
  9. ** public domain code by Jerry Coffin, with improvements by HenkJan Wolthuis.
  10. **
  11. ** Tested with Visual C 1.0 and Borland C 3.1.
  12. ** Compiles without warnings, and seems like it should be pretty
  13. ** portable.
  14. */
  15.  
  16. /*
  17. ** These are used in freeing a table.  Perhaps I should code up
  18. ** something a little less grungy, but it works, so what the heck.
  19. */
  20.  
  21. static void (*function)(void *) = (void (*)(void *))NULL;
  22. static hash_table *the_table = NULL;
  23.  
  24.  
  25. /* Initialize the hash_table to the size asked for.  Allocates space
  26. ** for the correct number of pointers and sets them to NULL.  If it
  27. ** can't allocate sufficient memory, signals error by setting the size
  28. ** of the table to 0.
  29. */
  30.  
  31. hash_table *construct_table(hash_table *table, size_t size)
  32. {
  33.       size_t i;
  34.       bucket **temp;
  35.  
  36.       table -> size  = size;
  37.       table -> table = (bucket * *)malloc(sizeof(bucket *) * size);
  38.       temp = table -> table;
  39.  
  40.       if ( temp == NULL )
  41.       {
  42.             table -> size = 0;
  43.             return table;
  44.       }
  45.  
  46.       for (i=0;i<size;i++)
  47.             temp[i] = NULL;
  48.       return table;
  49. }
  50.  
  51.  
  52. /*
  53. ** Hashes a string to produce an unsigned short, which should be
  54. ** sufficient for most purposes.
  55. */
  56.  
  57. static unsigned hash(char *string)
  58. {
  59.       unsigned ret_val = 0;
  60.       int i;
  61.  
  62.       while (*string)
  63.       {
  64.             i = *( int *)string;
  65.             ret_val ^= i;
  66.             ret_val <<= 1;
  67.             string ++;
  68.       }
  69.       return ret_val;
  70. }
  71.  
  72. /*
  73. ** Insert 'key' into hash table.
  74. ** Returns pointer to old data associated with the key, if any, or
  75. ** NULL if the key wasn't in the table previously.
  76. */
  77.  
  78. void *insert(char *key, void *data, hash_table *table)
  79. {
  80.       unsigned val = hash(key) % table->size;
  81.       bucket *ptr;
  82.  
  83.       /*
  84.       ** NULL means this bucket hasn't been used yet.  We'll simply
  85.       ** allocate space for our new bucket and put our data there, with
  86.       ** the table pointing at it.
  87.       */
  88.  
  89.       if (NULL == (table->table)[val])
  90.       {
  91.             (table->table)[val] = (bucket *)malloc(sizeof(bucket));
  92.             if (NULL==(table->table)[val])
  93.                   return NULL;
  94.  
  95.             (table->table)[val] -> key = strdup(key);
  96.             (table->table)[val] -> next = NULL;
  97.             (table->table)[val] -> data = data;
  98.             return (table->table)[val] -> data;
  99.       }
  100.  
  101.       /*
  102.       ** This spot in the table is already in use.  See if the current string
  103.       ** has already been inserted, and if so, increment its count.
  104.       */
  105.  
  106.       for (ptr = (table->table)[val];NULL != ptr; ptr = ptr -> next)
  107.             if (0 == strcmp(key, ptr->key))
  108.             {
  109.                   void *old_data;
  110.  
  111.                   old_data = ptr->data;
  112.                   ptr -> data = data;
  113.                   return old_data;
  114.             }
  115.  
  116.       /*
  117.       ** This key must not be in the table yet.  We'll add it to the head of
  118.       ** the list at this spot in the hash table.  Speed would be
  119.       ** slightly improved if the list was kept sorted instead.  In this case,
  120.       ** this code would be moved into the loop above, and the insertion would
  121.       ** take place as soon as it was determined that the present key in the
  122.       ** list was larger than this one.
  123.       */
  124.  
  125.       ptr = (bucket *)malloc(sizeof(bucket));
  126.       if (NULL==ptr)
  127.             return 0;
  128.       ptr -> key = strdup(key);
  129.       ptr -> data = data;
  130.       ptr -> next = (table->table)[val];
  131.       (table->table)[val] = ptr;
  132.       return data;
  133. }
  134.  
  135.  
  136. /*
  137. ** Look up a key and return the associated data.  Returns NULL if
  138. ** the key is not in the table.
  139. */
  140.  
  141. void *lookup(char *key, hash_table *table)
  142. {
  143.       unsigned val = hash(key) % table->size;
  144.       bucket *ptr;
  145.  
  146.       if (NULL == (table->table)[val])
  147.             return NULL;
  148.  
  149.       for ( ptr = (table->table)[val];NULL != ptr; ptr = ptr->next )
  150.       {
  151.             if (0 == strcmp(key, ptr -> key ) )
  152.                   return ptr->data;
  153.       }
  154.       return NULL;
  155. }
  156.  
  157. /*
  158. ** Delete a key from the hash table and return associated
  159. ** data, or NULL if not present.
  160. */
  161.  
  162. void *del(char *key, hash_table *table)
  163. {
  164.       unsigned val = hash(key) % table->size;
  165.       void *data;
  166.       bucket *ptr, *last = NULL;
  167.  
  168.       if (NULL == (table->table)[val])
  169.             return NULL;
  170.  
  171.       /*
  172.       ** Traverse the list, keeping track of the previous node in the list.
  173.       ** When we find the node to delete, we set the previous node's next
  174.       ** pointer to point to the node after ourself instead.  We then delete
  175.       ** the key from the present node, and return a pointer to the data it
  176.       ** contains.
  177.       */
  178.  
  179.       for (last = NULL, ptr = (table->table)[val];
  180.             NULL != ptr;
  181.             last = ptr, ptr = ptr->next)
  182.       {
  183.             if (0 == strcmp(key, ptr -> key))
  184.             {
  185.                   if (last != NULL )
  186.                   {
  187.                         data = ptr -> data;
  188.                         last -> next = ptr -> next;
  189.                         free(ptr->key);
  190.                         free(ptr);
  191.                         return data;
  192.                   }
  193.  
  194.                   /*
  195.                   ** If 'last' still equals NULL, it means that we need to
  196.                   ** delete the first node in the list. This simply consists
  197.                   ** of putting our own 'next' pointer in the array holding
  198.                   ** the head of the list.  We then dispose of the current
  199.                   ** node as above.
  200.                   */
  201.  
  202.                   else
  203.                   {
  204.                         data = ptr->data;
  205.                         (table->table)[val] = ptr->next;
  206.                         free(ptr->key);
  207.                         free(ptr);
  208.                         return data;
  209.                   }
  210.             }
  211.       }
  212.  
  213.       /*
  214.       ** If we get here, it means we didn't find the item in the table.
  215.       ** Signal this by returning NULL.
  216.       */
  217.  
  218.       return NULL;
  219. }
  220.  
  221. /*
  222. ** free_table iterates the table, calling this repeatedly to free
  223. ** each individual node.  This, in turn, calls one or two other
  224. ** functions - one to free the storage used for the key, the other
  225. ** passes a pointer to the data back to a function defined by the user,
  226. ** process the data as needed.
  227. */
  228.  
  229. static void free_node(char *key, void *data)
  230. {
  231.       (void) data;
  232.  
  233.       if (function)
  234.             function(del(key,the_table));
  235.       else  del(key,the_table);
  236. }
  237.  
  238. /*
  239. ** Frees a complete table by iterating over it and freeing each node.
  240. ** the second parameter is the address of a function it will call with a
  241. ** pointer to the data associated with each node.  This function is
  242. ** responsible for freeing the data, or doing whatever is needed with
  243. ** it.
  244. */
  245.  
  246. void free_table(hash_table *table, void (*func)(void *))
  247. {
  248.       function = func;
  249.       the_table = table;
  250.  
  251.       enumerate( table, free_node);
  252.       free(table->table);
  253.       table->table = NULL;
  254.       table->size = 0;
  255.  
  256.       the_table = NULL;
  257.       function = (void (*)(void *))NULL;
  258. }
  259.  
  260. /*
  261. ** Simply invokes the function given as the second parameter for each
  262. ** node in the table, passing it the key and the associated data.
  263. */
  264.  
  265. void enumerate( hash_table *table, void (*func)(char *, void *))
  266. {
  267.       unsigned i;
  268.       bucket *temp;
  269.  
  270.       for (i=0;i<table->size; i++)
  271.       {
  272.             if ((table->table)[i] != NULL)
  273.             {
  274.                   for (temp = (table->table)[i];
  275.                         NULL != temp;
  276.                         temp = temp -> next)
  277.                   {
  278.                         func(temp -> key, temp->data);
  279.                   }
  280.             }
  281.       }
  282. }
  283.  
  284.  
  285. #ifdef TEST
  286.  
  287. #include <stdio.h>
  288.  
  289. void printer(char *string, void *data)
  290. {
  291.       printf("%s: %s\n", string, (char *)data);
  292. }
  293.  
  294. int main(void)
  295. {
  296.       hash_table table;
  297.  
  298.       char *strings[] = {
  299.             "The first string",
  300.             "The second string",
  301.             "The third string",
  302.             "The fourth string",
  303.             "A much longer string than the rest in this example.",
  304.             "The last string",
  305.             NULL
  306.             };
  307.  
  308.       char *junk[] = {
  309.             "The first data",
  310.             "The second data",
  311.             "The third data",
  312.             "The fourth data",
  313.             "The fifth datum",
  314.             "The sixth piece of data"
  315.             };
  316.  
  317.       int i;
  318.       void *j;
  319.  
  320.       construct_table(&table,200);
  321.  
  322.       for (i = 0; NULL != strings[i]; i++ )
  323.             insert(strings[i], junk[i], &table);
  324.  
  325.       for (i=0;NULL != strings[i];i++)
  326.       {
  327.             printf("\n");
  328.             enumerate(&table, printer);
  329.             del(strings[i],&table);
  330.       }
  331.  
  332.       for (i=0;NULL != strings[i];i++)
  333.       {
  334.             j = lookup(strings[i], &table);
  335.             if (NULL == j)
  336.                   printf("\n'%s' is not in table",strings[i]);
  337.             else  printf("\nERROR: %s was deleted but is still in table.",
  338.                   strings[i]);
  339.       }
  340.       free_table(&table, NULL);
  341.       return 0;
  342. }
  343.  
  344. #endif /* TEST */
  345.