Advertisement
ananas

Simple hash

Dec 11th, 2015
138
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.95 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <limits.h>
  4. #include <string.h>
  5.  
  6. struct entry_s {
  7.   char *key;
  8.   float value;
  9.   struct entry_s *next;
  10. };
  11. typedef struct entry_s entry_t;
  12.  
  13. typedef struct {
  14.   int size;
  15.   entry_t **tbl;
  16. } hashtable_t;
  17.  
  18. /* Hash a string for a particular hash table. */
  19. static int
  20. ht_hash (hashtable_t * ht, const char *key)
  21. {
  22.   unsigned long int hashval = 0;
  23.   int len, i = 0;
  24.  
  25.   /* Convert our string to an integer */
  26.   len = strlen (key);
  27.   while (hashval < ULONG_MAX && i < len)
  28.     {
  29.       hashval = hashval << 8;
  30.       hashval += key[i];
  31.       i++;
  32.     }
  33.  
  34.   return hashval % ht->size;
  35. }
  36.  
  37. /* Create a key-value pair. */
  38. static entry_t *
  39. ht_newpair (const char *key, float value)
  40. {
  41.   entry_t *pair = NULL;
  42.  
  43.   if ((pair = (entry_t *) malloc (sizeof (entry_t))) != NULL)
  44.     {
  45.       pair->key = strdup (key);
  46.       pair->value = value;
  47.       pair->next = NULL;
  48.     }
  49.  
  50.   return pair;
  51. }
  52.  
  53. /* Create a new hashtable. */
  54. hashtable_t *
  55. ht_create (int size)
  56. {
  57.   hashtable_t *ht = NULL;
  58.   int i;
  59.  
  60.   if (size < 1)
  61.     return NULL;
  62.  
  63.   /* Allocate the table itself. */
  64.   if ((ht = (hashtable_t *) malloc (sizeof (hashtable_t))) != NULL)
  65.     {
  66.       /* Allocate pointers to the head nodes. */
  67.       if ((ht->tbl = (entry_t **) malloc (sizeof (entry_t *) * size)) == NULL)
  68.         {
  69.           free (ht);
  70.           return NULL;
  71.         }
  72.  
  73.       for (i = 0; i < size; i++)
  74.         ht->tbl[i] = NULL;
  75.  
  76.       ht->size = size;
  77.     }
  78.  
  79.   return ht;
  80. }
  81.  
  82. /* Insert a key-value pair into a hash table. */
  83. void
  84. ht_set (hashtable_t *ht, const char *key, float value)
  85. {
  86.   int bin = 0;
  87.   entry_t *next = NULL;
  88.   entry_t *last = NULL;
  89.  
  90.   if (ht == NULL)
  91.     return;
  92.  
  93.   bin = ht_hash (ht, key);
  94.  
  95.   next = ht->tbl[bin];
  96.  
  97.   /* Looking for existing key */
  98.   while (next)
  99.     {
  100.       if (next->key && strcmp (key, next->key) == 0)
  101.         {
  102.           next->value = value;
  103.           return;
  104.         }
  105.       last = next;
  106.       next = last->next;
  107.     }
  108.  
  109.   /* Not found, appending */
  110.   next = ht_newpair (key, value);
  111.   if (last)
  112.     last->next = next;
  113.   else
  114.     ht->tbl[bin] = next;
  115. }
  116.  
  117. /* Retrieve a value from a hash table. */
  118. float
  119. ht_get (hashtable_t *ht, const char *key)
  120. {
  121.   int bin = 0;
  122.   entry_t *pair;
  123.  
  124.   if (ht == NULL)
  125.     return 0.0;
  126.  
  127.   bin = ht_hash (ht, key);
  128.  
  129.   /* Step through the bin, looking for our value. */
  130.   pair = ht->tbl[bin];
  131.   while (pair)
  132.     {
  133.       if (pair->key && strcmp (key, pair->key) == 0)
  134.         return pair->value;
  135.       pair = pair->next;
  136.     }
  137.  
  138.   return 0.0;
  139. }
  140.  
  141. /* Release memory */
  142. void
  143. ht_delete (hashtable_t *ht)
  144. {
  145.   int i;
  146.  
  147.   if (ht == NULL)
  148.     return;
  149.  
  150.   for (i = 0; i > ht->size; i++)
  151.     {
  152.       entry_t *pair = ht->tbl[i];
  153.  
  154.       while (pair)
  155.         {
  156.           entry_t *next = pair->next;
  157.           free (pair->key);
  158.           free (pair);
  159.           pair = next;
  160.         }
  161.     }
  162.  
  163.   free (ht->tbl);
  164.   free (ht);
  165. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement