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 added, removed;
  19         unsigned int entries;
  20         unsigned int max_entries;
  21 };
  22
  23 /* struct data access functions */
  24 unsigned int hash_entries(hash_table *table)
  25 {
  26         return table ? table->entries : 0;
  27 }
  28
  29 unsigned int hash_entries_max(hash_table *table)
  30 {
  31         return table ? table->max_entries : 0;
  32 }
  33
  34 unsigned int hash_entries_added(hash_table *table)
  35 {
  36         return table ? table->added : 0;
  37 }
  38
  39 unsigned int hash_entries_removed(hash_table *table)
  40 {
  41         return table ? table->removed : 0;
  42 }
  43
  44 unsigned int hash_table_size(hash_table *table)
  45 {
  46         return table ? table->num_buckets : 0;
  47 }
  48
  49 void hash_debug_print_table_data(hash_table *table, const char *name, int force)
  50 {
  51         int delta = hash_check_table(table);
  52         unsigned int count;
  53         if (!delta && !force)
  54                 return;
  55
  56         count = hash_count_entries(table);
  57         printf("debug data for hash table '%s'\n", name);
  58         printf("  entries: %u; counted: %u; delta: %d\n",
  59                    table->entries, count, delta);
  60         printf("  added: %u; removed: %u; delta: %d\n",
  61                    table->added, table->removed, table->added - table->removed);
  62 }
  63
  64 /*
  65  * polynomial conversion ignoring overflows
  66  *
  67  * Ozan Yigit's original sdbm algorithm, but without Duff's device
  68  * so we can use it without knowing the length of the string
  69  */
  70 static inline unsigned int sdbm(const unsigned register char *k)
  71 {
  72         register unsigned int h = 0;
  73
  74         while (*k)
  75                 h = *k++ + 65599 * h;
  76
  77         return h;
  78 }
  79
  80 static inline int hash_add_bucket(hash_table *table, const char *k1, const char *k2, void *data, unsigned int h)
  81 {
  82         hash_bucket *bkt;
  83
  84         if (!(bkt = malloc(sizeof(*bkt))))
  85                 return -1;
  86
  87         h = h % table->num_buckets;
  88
  89         table->added++;
  90         bkt->data = data;
  91         bkt->key = k1;
  92         bkt->key2 = k2;
  93         bkt->next = table->buckets[h];
  94         table->buckets[h] = bkt;
  95
  96         if (++table->entries > table->max_entries)
  97                 table->max_entries = table->entries;
  98
  99         return 0;
 100 }
 101
 102 int hash_add2(hash_table *table, const char *k1, const char *k2, void *data)
 103 {
 104         return hash_add_bucket(table, k1, k2, data, hash_func2(k1, k2));
 105 }
 106
 107 int hash_add(hash_table *table, const char *key, void *data)
 108 {
 109         return hash_add_bucket(table, key, NULL, data, hash_func(key));
 110 }
 111
 112 static hash_bucket *hash_get_bucket(hash_table *table, const char *key)
 113 {
 114         hash_bucket *bkt;
 115
 116         if (!table)
 117                 return NULL;
 118
 119         bkt = table->buckets[hash_func(key) % table->num_buckets];
 120         for (; bkt; bkt = bkt->next) {
 121                 if (!strcmp(key, bkt->key))
 122                         return bkt;
 123         }
 124
 125         return NULL;
 126 }
 127
 128 static hash_bucket *hash_get_bucket2(hash_table *table, const char *k1, const char *k2)
 129 {
 130         hash_bucket *bkt;
 131
 132         if (!table)
 133                 return NULL;
 134
 135         bkt = table->buckets[hash_func2(k1, k2) % table->num_buckets];
 136         for (; bkt; bkt = bkt->next) {
 137                 if (!strcmp(k1, bkt->key) && !strcmp(k2, bkt->key2))
 138                         return bkt;
 139         }
 140
 141         return NULL;
 142 }
 143
 144 void *hash_find(hash_table *table, const char *key)
 145 {
 146         hash_bucket *bkt;
 147
 148         bkt = hash_get_bucket(table, key);
 149
 150         return bkt ? bkt->data : NULL;
 151 }
 152
 153 void *hash_find2(hash_table *table, const char *k1, const char *k2)
 154 {
 155         hash_bucket *bkt;
 156
 157         bkt = hash_get_bucket2(table, k1, k2);
 158
 159         return bkt ? bkt->data : NULL;
 160 }
 161
 162 hash_table *hash_init(unsigned int buckets)
 163 {
 164         hash_table *table = calloc(sizeof(hash_table), 1);
 165
 166         if (table) {
 167                 table->buckets = calloc(buckets, sizeof(hash_bucket *));
 168                 if (table->buckets) {
 169                         table->num_buckets = buckets;
 170                         return table;
 171                 }
 172
 173                 free(table);
 174         }
 175
 176         return NULL;
 177 }
 178
 179 void *hash_update(hash_table *table, const char *key, void *data)
 180 {
 181         hash_bucket *bkt;
 182         void *current_data;
 183
 184         bkt = hash_get_bucket(table, key);
 185         if (!bkt) {
 186                 hash_add(table, key, data);
 187                 return NULL;
 188         }
 189
 190         current_data = bkt->data;
 191         bkt->data = data;
 192         return current_data;
 193 }
 194
 195 void *hash_update2(hash_table *table, const char *key, const char *key2, void *data)
 196 {
 197         hash_bucket *bkt;
 198
 199         bkt = hash_get_bucket2(table, key, key2);
 200         if (!bkt) {
 201                 hash_add2(table, key, key2, data);
 202                 return NULL;
 203         }
 204
 205         bkt->data = data;
 206         return NULL;
 207 }
 208
 209 static inline void *hash_destroy_bucket(hash_bucket *bkt)
 210 {
 211         void *data;
 212
 213         data = bkt->data;
 214         free(bkt);
 215         return data;
 216 }
 217
 218 void *hash_remove(hash_table *table, const char *key)
 219 {
 220         unsigned int h;
 221         hash_bucket *bkt, *prev;
 222
 223         h = hash_func(key) % table->num_buckets;
 224
 225         if (!(bkt = table->buckets[h]))
 226                 return NULL;
 227
 228         if (!strcmp(key, bkt->key)) {
 229                 table->buckets[h] = bkt->next;
 230                 table->entries--;
 231                 table->removed++;
 232                 return hash_destroy_bucket(bkt);
 233         }
 234
 235         prev = bkt;
 236         for (bkt = bkt->next; bkt; bkt = bkt->next) {
 237                 if (!strcmp(key, bkt->key)) {
 238                         prev->next = bkt->next;
 239                         table->entries--;
 240                         table->removed++;
 241                         return hash_destroy_bucket(bkt);
 242                 }
 243         }
 244
 245         return NULL;
 246 }
 247
 248 void *hash_remove2(hash_table *table, const char *k1, const char *k2)
 249 {
 250         unsigned int h;
 251         hash_bucket *bkt, *prev;
 252
 253         h = hash_func2(k1, k2) % table->num_buckets;
 254
 255         if (!(bkt = table->buckets[h]))
 256                 return NULL;
 257
 258         if (!strcmp(k1, bkt->key) && !strcmp(k2, bkt->key2)) {
 259                 table->buckets[h] = bkt->next;
 260                 table->entries--;
 261                 table->removed++;
 262                 return hash_destroy_bucket(bkt);
 263         }
 264
 265         prev = bkt;
 266         for (bkt = bkt->next; bkt; bkt = bkt->next) {
 267                 if (!strcmp(k1, bkt->key) && !strcmp(k2, bkt->key2)) {
 268                         prev->next = bkt->next;
 269                         table->entries--;
 270                         table->removed++;
 271                         return hash_destroy_bucket(bkt);
 272                 }
 273         }
 274
 275         return NULL;
 276 }
 277
 278 unsigned int hash_count_entries(hash_table *table)
 279 {
 280         int i;
 281         unsigned int count = 0;
 282
 283         for (i = 0; i < table->num_buckets; i++) {
 284                 hash_bucket *bkt;
 285                 for (bkt = table->buckets[i]; bkt; bkt = bkt->next)
 286                         count++;
 287         }
 288
 289         return count;
 290 }
 291
 292 int hash_check_table(hash_table *table)
 293 {
 294         return table ? table->entries - hash_count_entries(table) : 0;
 295 }
 296
 297 void hash_walk_data(hash_table *table, int (*walker)(void *))
 298 {
 299         hash_bucket *bkt, *prev;
 300         int i;
 301
 302         if (!table->entries)
 303                 return;
 304
 305         for (i = 0; i < table->num_buckets; i++) {
 306                 int depth = 0;
 307
 308                 prev = table->buckets[i];
 309                 hash_bucket *next;
 310                 for (bkt = table->buckets[i]; bkt; bkt = next) {
 311                         next = bkt->next;
 312
 313                         if (walker(bkt->data) != HASH_WALK_REMOVE) {
 314                                 /* only update prev if we don't remove current */
 315                                 prev = bkt;
 316                                 depth++;
 317                                 continue;
 318                         }
 319                         table->removed++;
 320                         table->entries--;
 321                         hash_destroy_bucket(bkt);
 322                         prev->next = next;
 323                         if (!depth) {
 324                                 table->buckets[i] = next;
 325                         }
 326                 }
 327         }
 328 }
 329
 330 /* inserts a guaranteed unique entry to the hash-table */
 331 int hash_add_unique(hash_table *table, const char *key, void *data)
 332 {
 333         unsigned int h;
 334         hash_bucket *bkt;
 335
 336         h = hash_func(key) % table->num_buckets;
 337         for (bkt = table->buckets[h]; bkt; bkt = bkt->next)
 338                 if (!strcmp(bkt->key, key))
 339                         return -1;
 340
 341         /* it's a unique key */
 342         return hash_add_bucket(table, key, NULL, data, h);
 343 }
 344
 345 int hash_add_unique2(hash_table *table, const char *k1, const char *k2, void *data)
 346 {
 347         unsigned int h;
 348         hash_bucket *bkt;
 349
 350         h = hash_func2(k1, k2) % table->num_buckets;
 351         for (bkt = table->buckets[h]; bkt; bkt = bkt->next)
 352                 if (!strcmp(bkt->key, k1) && !strcmp(bkt->key2, k2))
 353                         return -1;
 354
 355         return hash_add_bucket(table, k1, k2, data, h);
 356 }