hash.c

   1
   2 #include <stddef.h>
   3 #include <stdlib.h>
   4 #include <string.h>
   5 #include <math.h>
   6
   7 #include "hash.h"
   8 #include "utils.h"
   9 #include "types.h"
  10
  11 #define DEFAULT_ALLOC_ENTRIES 512
  12 #define INDEX_FOR(hash, size) ((hash) & ((size) - 1))
  13
  14 struct entry {
  15   void *key, *value;
  16   unsigned int hash;
  17   struct entry *next;
  18 };
  19
  20 struct hashtable {
  21   unsigned int tablelength;
  22   unsigned int entrycount;
  23   unsigned int loadlimit;
  24   struct entry **table;
  25   hashfunction hashfn;
  26   equalsfunction eqfn;
  27
  28   struct entry *alloclist;
  29   struct entry *nextavail;
  30 };
  31
  32
  33 static
  34 struct entry *alloc_entry (struct hashtable *ht)
  35 {
  36   struct entry *e;
  37   if (!ht->nextavail) {
  38     int i;
  39     e = (struct entry *) xmalloc (DEFAULT_ALLOC_ENTRIES * sizeof (struct entry));
  40     e->next = ht->alloclist;
  41     ht->alloclist = e;
  42
  43     for (i = 1; i < DEFAULT_ALLOC_ENTRIES - 1; i++)
  44       e[i].next = &e[i + 1];
  45     e[i].next = NULL;
  46
  47     ht->nextavail = &e[1];
  48   }
  49   e = ht->nextavail;
  50   ht->nextavail = e->next;
  51   return e;
  52 }
  53
  54 static
  55 void free_entry (struct hashtable *ht, struct entry *e)
  56 {
  57   e->next = ht->nextavail;
  58   ht->nextavail = e;
  59 }
  60
  61 struct hashtable *hashtable_create (unsigned int size, hashfunction hashfn, equalsfunction eqfn)
  62 {
  63   struct hashtable *ht;
  64
  65   ht = (struct hashtable *) xmalloc (sizeof (struct hashtable));
  66   ht->table = (struct entry **) xmalloc (sizeof (struct entry *) * size);
  67   memset (ht->table, 0, size * sizeof (struct entry *));
  68
  69   ht->tablelength = size;
  70   ht->entrycount = 0;
  71   ht->hashfn = hashfn;
  72   ht->eqfn = eqfn;
  73   ht->loadlimit = size >> 1;
  74   ht->alloclist = NULL;
  75   ht->nextavail = NULL;
  76
  77   return ht;
  78 }
  79
  80 void hashtable_free (struct hashtable *ht, traversefunction destroyfn, void *arg)
  81 {
  82   struct entry *e, *ne;
  83
  84   if (destroyfn)
  85     hashtable_traverse (ht, destroyfn, arg);
  86
  87   for (e = ht->alloclist; e; e = ne) {
  88     ne = e->next;
  89     free (e);
  90   }
  91
  92   free (ht->table);
  93   free (ht);
  94 }
  95
  96 static
  97 void free_all_callback (void *key, void *value, unsigned int hash, void *arg)
  98 {
  99   if (key)   free (key);
 100   if (value) free (value);
 101 }
 102
 103 void hashtable_free_all (struct hashtable *ht)
 104 {
 105   hashtable_free (ht, &free_all_callback, NULL);
 106 }
 107
 108
 109 static
 110 void hashtable_grow (struct hashtable *ht)
 111 {
 112   struct entry **newtable;
 113   struct entry *e, *ne;
 114   unsigned int newsize, i, index;
 115
 116   newsize = ht->tablelength << 1;
 117
 118   newtable = (struct entry **) xmalloc (sizeof (struct entry *) * newsize);
 119   memset (newtable, 0, newsize * sizeof (struct entry *));
 120
 121   for (i = 0; i < ht->tablelength; i++) {
 122     for (e = ht->table[i]; e; e = ne) {
 123       ne = e->next;
 124       index = INDEX_FOR (e->hash, newsize);
 125       e->next = newtable[index];
 126       newtable[index] = e;
 127     }
 128   }
 129
 130   free (ht->table);
 131   ht->table = newtable;
 132   ht->tablelength = newsize;
 133   ht->loadlimit = newsize >> 1;
 134 }
 135
 136 unsigned int hashtable_count (struct hashtable *ht)
 137 {
 138   return ht->entrycount;
 139 }
 140
 141 void hashtable_insert (struct hashtable *ht, void *key, void *value)
 142 {
 143   hashtable_inserth (ht, key, value, ht->hashfn (key));
 144 }
 145
 146 void hashtable_inserth (struct hashtable *ht, void *key, void *value, unsigned int hash)
 147 {
 148   unsigned int index;
 149   struct entry *e;
 150
 151   if (ht->entrycount >= ht->loadlimit) {
 152     hashtable_grow (ht);
 153   }
 154   e = alloc_entry (ht);
 155   e->hash = hash;
 156   index = INDEX_FOR (e->hash, ht->tablelength);
 157   e->key = key;
 158   e->value = value;
 159   e->next = ht->table[index];
 160   ht->entrycount++;
 161   ht->table[index] = e;
 162 }
 163
 164
 165 static
 166 struct entry *find_entry (struct hashtable *ht, void *key, unsigned int hash, int remove)
 167 {
 168   struct entry *e;
 169   struct entry **prev;
 170   unsigned int index;
 171
 172   index = INDEX_FOR (hash, ht->tablelength);
 173   for (prev = &(ht->table[index]); (e = *prev) ; prev = &e->next) {
 174     if (hash != e->hash) continue;
 175     if (key != e->key)
 176       if (!ht->eqfn (key, e->key, hash))
 177         continue;
 178
 179     if (remove) {
 180       *prev = e->next;
 181       ht->entrycount--;
 182       free_entry (ht, e);
 183     }
 184
 185     return e;
 186   }
 187   return NULL;
 188 }
 189
 190 void *hashtable_search (struct hashtable *ht, void *key, void **key_found)
 191 {
 192   return hashtable_searchh (ht, key, key_found, ht->hashfn (key));
 193 }
 194
 195 void *hashtable_searchh (struct hashtable *ht, void *key, void **key_found, unsigned int hash)
 196 {
 197   struct entry *e = find_entry (ht, key, hash, 0);
 198   if (e) {
 199     if (key_found)
 200       *key_found = e->key;
 201     return e->value;
 202   }
 203   return NULL;
 204 }
 205
 206 int hashtable_haskey (struct hashtable *ht, void *key, void **key_found)
 207 {
 208   return hashtable_haskeyh (ht, key, key_found, ht->hashfn (key));
 209 }
 210
 211 int hashtable_haskeyh (struct hashtable *ht, void *key, void **key_found, unsigned int hash)
 212 {
 213   struct entry *e = find_entry (ht, key, hash, 0);
 214   if (e) {
 215     if (key_found)
 216       *key_found = e->key;
 217     return TRUE;
 218   }
 219   return FALSE;
 220 }
 221
 222 void *hashtable_remove (struct hashtable *ht, void *key, void **key_found)
 223 {
 224   return hashtable_removeh (ht, key, key_found, ht->hashfn (key));
 225 }
 226
 227 void *hashtable_removeh (struct hashtable *ht, void *key, void **key_found, unsigned int hash)
 228 {
 229   struct entry *e = find_entry (ht, key, hash, 1);
 230   if (e) {
 231     if (key_found)
 232       *key_found = e->key;
 233     return e->value;
 234   }
 235   return NULL;
 236 }
 237
 238
 239 void hashtable_traverse (struct hashtable *ht, traversefunction traversefn, void *arg)
 240 {
 241   struct entry *e;
 242   unsigned int i;
 243
 244   for (i = 0; i < ht->tablelength; i++) {
 245     for (e = ht->table[i]; e; e = e->next) {
 246       traversefn (e->key, e->value, e->hash, arg);
 247     }
 248   }
 249 }
 250
 251 int hashtable_string_compare (void *key1, void *key2, unsigned int hash)
 252 {
 253   return (strcmp (key1, key2) == 0);
 254 }
 255
 256 int hashtable_pointer_compare (void *key1, void *key2, unsigned int hash)
 257 {
 258   return (key1 == key2);
 259 }
 260
 261
 262 unsigned int hashtable_hash_bytes (unsigned char *key, size_t len)
 263 {
 264   unsigned int hash = 0;
 265   size_t i;
 266
 267   for (i = 0; i < len; i++) {
 268     hash += key[i];
 269     hash += (hash << 10);
 270     hash ^= (hash >> 6);
 271   }
 272
 273   hash += (hash << 3);
 274   hash ^= (hash >> 11);
 275   hash += (hash << 15);
 276
 277   return hash;
 278 }
 279
 280 unsigned int hashtable_hash_string (void *key)
 281 {
 282   unsigned int hash = 0;
 283   unsigned char *bytes = (unsigned char *) key;
 284
 285   while (*bytes) {
 286     hash += *bytes++;
 287     hash += (hash << 10);
 288     hash ^= (hash >> 6);
 289   }
 290
 291   hash += (hash << 3);
 292   hash ^= (hash >> 11);
 293   hash += (hash << 15);
 294
 295   return hash;
 296 }