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