hash.c

   1 #include <stdlib.h>
   2 #include <string.h>
   3 #include "hash.h"
   4
   5 #define hash_func(k) sdbm((unsigned char *)k)
   6 #define hash_func2(k1, k2) (hash_func(k1) ^ hash_func(k2))
   7
   8 typedef struct hash_bucket {
   9         const char *key;
  10         const char *key2;
  11         void *data;
  12         struct hash_bucket *next;
  13 } hash_bucket;
  14
  15 struct hash_table {
  16         hash_bucket **buckets;
  17         unsigned int num_buckets;
  18         unsigned int entries;
  19         unsigned int max_entries;
  20 };
  21
  22 /* struct data access functions */
  23 unsigned int hash_get_max_entries(hash_table *table)
  24 {
  25         return table ? table->max_entries : 0;
  26 }
  27
  28 unsigned int hash_get_num_entries(hash_table *table)
  29 {
  30         return table ? table->entries : 0;
  31 }
  32
  33 unsigned int hash_table_size(hash_table *table)
  34 {
  35         return table ? table->num_buckets : 0;
  36 }
  37
  38 /*
  39  * polynomial conversion ignoring overflows
  40  *
  41  * Ozan Yigit's original sdbm algorithm, but without Duff's device
  42  * so we can use it without knowing the length of the string
  43  */
  44 static inline unsigned int sdbm(const unsigned register char *k)
  45 {
  46         register unsigned int h = 0;
  47
  48         while (*k)
  49                 h = *k++ + 65599 * h;
  50
  51         return h;
  52 }
  53
  54 static inline int hash_add_bucket(hash_table *table, const char *k1, const char *k2, void *data, unsigned int h)
  55 {
  56         hash_bucket *bkt;
  57
  58         if (!(bkt = malloc(sizeof(*bkt))))
  59                 return -1;
  60
  61         h = h % table->num_buckets;
  62
  63         bkt->data = data;
  64         bkt->key = k1;
  65         bkt->key2 = k2;
  66         bkt->next = table->buckets[h];
  67         table->buckets[h] = bkt;
  68
  69         if (++table->entries > table->max_entries)
  70                 table->max_entries = table->entries;
  71
  72         return 0;
  73 }
  74
  75 int hash_add2(hash_table *table, const char *k1, const char *k2, void *data)
  76 {
  77         return hash_add_bucket(table, k1, k2, data, hash_func2(k1, k2));
  78 }
  79
  80 int hash_add(hash_table *table, const char *key, void *data)
  81 {
  82         return hash_add_bucket(table, key, NULL, data, hash_func(key));
  83 }
  84
  85 static hash_bucket *hash_get_bucket(hash_table *table, const char *key)
  86 {
  87         hash_bucket *bkt;
  88
  89         if (!table)
  90                 return NULL;
  91
  92         bkt = table->buckets[hash_func(key) % table->num_buckets];
  93         for (; bkt; bkt = bkt->next) {
  94                 if (!strcmp(key, bkt->key))
  95                         return bkt;
  96         }
  97
  98         return NULL;
  99 }
 100
 101 static hash_bucket *hash_get_bucket2(hash_table *table, const char *k1, const char *k2)
 102 {
 103         hash_bucket *bkt;
 104
 105         if (!table)
 106                 return NULL;
 107
 108         bkt = table->buckets[hash_func2(k1, k2) % table->num_buckets];
 109         for (; bkt; bkt = bkt->next) {
 110                 if (!strcmp(k1, bkt->key) && !strcmp(k2, bkt->key2))
 111                         return bkt;
 112         }
 113
 114         return NULL;
 115 }
 116
 117 void *hash_find(hash_table *table, const char *key)
 118 {
 119         hash_bucket *bkt;
 120
 121         bkt = hash_get_bucket(table, key);
 122
 123         return bkt ? bkt->data : NULL;
 124 }
 125
 126 void *hash_find2(hash_table *table, const char *k1, const char *k2)
 127 {
 128         hash_bucket *bkt;
 129
 130         bkt = hash_get_bucket2(table, k1, k2);
 131
 132         return bkt ? bkt->data : NULL;
 133 }
 134
 135 hash_table *hash_init(unsigned int buckets)
 136 {
 137         hash_table *table = calloc(sizeof(hash_table), 1);
 138
 139         if (table) {
 140                 table->buckets = calloc(buckets, sizeof(hash_bucket *));
 141                 if (table->buckets) {
 142                         table->num_buckets = buckets;
 143                         return table;
 144                 }
 145
 146                 free(table);
 147         }
 148
 149         return NULL;
 150 }
 151
 152 void *hash_update(hash_table *table, const char *key, void *data)
 153 {
 154         hash_bucket *bkt;
 155         void *current_data;
 156
 157         bkt = hash_get_bucket(table, key);
 158         if (!bkt) {
 159                 hash_add(table, key, data);
 160                 return NULL;
 161         }
 162
 163         current_data = bkt->data;
 164         bkt->data = data;
 165         return current_data;
 166 }
 167
 168 void *hash_update2(hash_table *table, const char *key, const char *key2, void *data)
 169 {
 170         hash_bucket *bkt;
 171
 172         bkt = hash_get_bucket2(table, key, key2);
 173         if (!bkt) {
 174                 hash_add2(table, key, key2, data);
 175                 return NULL;
 176         }
 177
 178         bkt->data = data;
 179         return NULL;
 180 }
 181
 182 static inline void *hash_destroy_bucket(hash_bucket *bkt)
 183 {
 184         void *data;
 185
 186         data = bkt->data;
 187         free(bkt);
 188         return data;
 189 }
 190
 191 void *hash_remove(hash_table *table, const char *key)
 192 {
 193         unsigned int h;
 194         hash_bucket *bkt, *prev;
 195
 196         h = hash_func(key) % table->num_buckets;
 197
 198         if (!(bkt = table->buckets[h]))
 199                 return NULL;
 200
 201         if (!strcmp(key, bkt->key)) {
 202                 table->buckets[h] = bkt->next;
 203                 table->entries--;
 204                 return hash_destroy_bucket(bkt);
 205         }
 206
 207         prev = bkt;
 208         for (bkt = bkt->next; bkt; bkt = bkt->next) {
 209                 if (!strcmp(key, bkt->key)) {
 210                         prev->next = bkt->next;
 211                         table->entries--;
 212                         return hash_destroy_bucket(bkt);
 213                 }
 214         }
 215
 216         return NULL;
 217 }
 218
 219 void *hash_remove2(hash_table *table, const char *k1, const char *k2)
 220 {
 221         unsigned int h;
 222         hash_bucket *bkt, *prev;
 223
 224         h = hash_func2(k1, k2) % table->num_buckets;
 225
 226         if (!(bkt = table->buckets[h]))
 227                 return NULL;
 228
 229         if (!strcmp(k1, bkt->key) && !strcmp(k2, bkt->key2)) {
 230                 table->buckets[h] = bkt->next;
 231                 table->entries--;
 232                 return hash_destroy_bucket(bkt);
 233         }
 234
 235         prev = bkt;
 236         for (bkt = bkt->next; bkt; bkt = bkt->next) {
 237                 if (!strcmp(k1, bkt->key) && !strcmp(k2, bkt->key2)) {
 238                         prev->next = bkt->next;
 239                         table->entries--;
 240                         return hash_destroy_bucket(bkt);
 241                 }
 242         }
 243
 244         return NULL;
 245 }
 246
 247 unsigned int hash_count_entries(hash_table *table)
 248 {
 249         int i;
 250         unsigned int count = 0;
 251
 252         for (i = 0; i < table->num_buckets; i++) {
 253                 hash_bucket *bkt;
 254                 for (bkt = table->buckets[i]; bkt; bkt = bkt->next)
 255                         count++;
 256         }
 257
 258         return count;
 259 }
 260
 261 int hash_check_table(hash_table *table)
 262 {
 263         return hash_count_entries(table) - table->entries;
 264 }
 265
 266 void hash_walk_data(hash_table *table, int (*walker)(void *))
 267 {
 268         hash_bucket *bkt;
 269         int i;
 270
 271         for (i = 0; i < table->num_buckets; i++) {
 272                 hash_bucket *next;
 273                 for (bkt = table->buckets[i]; bkt; bkt = next) {
 274                         next = bkt->next;
 275                         walker(bkt->data);
 276                 }
 277         }
 278 }
 279
 280 /* inserts a guaranteed unique entry to the hash-table */
 281 int hash_add_unique(hash_table *table, const char *key, void *data)
 282 {
 283         unsigned int h;
 284         hash_bucket *bkt;
 285
 286         h = hash_func(key) % table->num_buckets;
 287         for (bkt = table->buckets[h]; bkt; bkt = bkt->next)
 288                 if (!strcmp(bkt->key, key))
 289                         return -1;
 290
 291         /* it's a unique key */
 292         return hash_add_bucket(table, key, NULL, data, h);
 293 }
 294
 295 int hash_add_unique2(hash_table *table, const char *k1, const char *k2, void *data)
 296 {
 297         unsigned int h;
 298         hash_bucket *bkt;
 299
 300         h = hash_func2(k1, k2) % table->num_buckets;
 301         for (bkt = table->buckets[h]; bkt; bkt = bkt->next)
 302                 if (!strcmp(bkt->key, k1) && !strcmp(bkt->key2, k2))
 303                         return -1;
 304
 305         return hash_add_bucket(table, k1, k2, data, h);
 306 }