hash.c

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