src/hashtable.c

   1 /*
   2  * Copyright (c) 2009, 2010 Petri Lehtinen <petri@digip.org>
   3  *
   4  * This library is free software; you can redistribute it and/or modify
   5  * it under the terms of the MIT license. See LICENSE for details.
   6  */
   7
   8 #include <config.h>
   9
  10 #include <stdlib.h>
  11 #include "hashtable.h"
  12
  13 typedef struct hashtable_list list_t;
  14 typedef struct hashtable_pair pair_t;
  15 typedef struct hashtable_bucket bucket_t;
  16
  17 #define container_of(ptr_, type_, member_)                      \
  18     ((type_ *)((char *)ptr_ - (size_t)&((type_ *)0)->member_))
  19
  20 #define list_to_pair(list_)  container_of(list_, pair_t, list)
  21
  22 static inline void list_init(list_t *list)
  23 {
  24     list->next = list;
  25     list->prev = list;
  26 }
  27
  28 static inline void list_insert(list_t *list, list_t *node)
  29 {
  30     node->next = list;
  31     node->prev = list->prev;
  32     list->prev->next = node;
  33     list->prev = node;
  34 }
  35
  36 static inline void list_remove(list_t *list)
  37 {
  38     list->prev->next = list->next;
  39     list->next->prev = list->prev;
  40 }
  41
  42 static inline int bucket_is_empty(hashtable_t *hashtable, bucket_t *bucket)
  43 {
  44     return bucket->first == &hashtable->list && bucket->first == bucket->last;
  45 }
  46
  47 static void insert_to_bucket(hashtable_t *hashtable, bucket_t *bucket,
  48                              list_t *list)
  49 {
  50     if(bucket_is_empty(hashtable, bucket))
  51     {
  52         list_insert(&hashtable->list, list);
  53         bucket->first = bucket->last = list;
  54     }
  55     else
  56     {
  57         list_insert(bucket->first, list);
  58         bucket->first = list;
  59     }
  60 }
  61
  62 static size_t primes[] = {
  63     5, 13, 23, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
  64     49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
  65     12582917, 25165843, 50331653, 100663319, 201326611, 402653189,
  66     805306457, 1610612741
  67 };
  68 static const size_t num_primes = sizeof(primes) / sizeof(size_t);
  69
  70 static inline size_t num_buckets(hashtable_t *hashtable)
  71 {
  72     return primes[hashtable->num_buckets];
  73 }
  74
  75
  76 static pair_t *hashtable_find_pair(hashtable_t *hashtable, bucket_t *bucket,
  77                                    const void *key, size_t hash)
  78 {
  79     list_t *list;
  80     pair_t *pair;
  81
  82     if(bucket_is_empty(hashtable, bucket))
  83         return NULL;
  84
  85     list = bucket->first;
  86     while(1)
  87     {
  88         pair = list_to_pair(list);
  89         if(pair->hash == hash && hashtable->cmp_keys(pair->key, key))
  90             return pair;
  91
  92         if(list == bucket->last)
  93             break;
  94
  95         list = list->next;
  96     }
  97
  98     return NULL;
  99 }
 100
 101 /* returns 0 on success, -1 if key was not found */
 102 static int hashtable_do_del(hashtable_t *hashtable,
 103                             const void *key, size_t hash)
 104 {
 105     pair_t *pair;
 106     bucket_t *bucket;
 107     size_t index;
 108
 109     index = hash % num_buckets(hashtable);
 110     bucket = &hashtable->buckets[index];
 111
 112     pair = hashtable_find_pair(hashtable, bucket, key, hash);
 113     if(!pair)
 114         return -1;
 115
 116     if(&pair->list == bucket->first && &pair->list == bucket->last)
 117         bucket->first = bucket->last = &hashtable->list;
 118
 119     else if(&pair->list == bucket->first)
 120         bucket->first = pair->list.next;
 121
 122     else if(&pair->list == bucket->last)
 123         bucket->last = pair->list.prev;
 124
 125     list_remove(&pair->list);
 126
 127     if(hashtable->free_key)
 128         hashtable->free_key(pair->key);
 129     if(hashtable->free_value)
 130         hashtable->free_value(pair->value);
 131
 132     free(pair);
 133     hashtable->size--;
 134
 135     return 0;
 136 }
 137
 138 static void hashtable_do_clear(hashtable_t *hashtable)
 139 {
 140     list_t *list, *next;
 141     pair_t *pair;
 142
 143     for(list = hashtable->list.next; list != &hashtable->list; list = next)
 144     {
 145         next = list->next;
 146         pair = list_to_pair(list);
 147         if(hashtable->free_key)
 148             hashtable->free_key(pair->key);
 149         if(hashtable->free_value)
 150             hashtable->free_value(pair->value);
 151         free(pair);
 152     }
 153 }
 154
 155 static int hashtable_do_rehash(hashtable_t *hashtable)
 156 {
 157     list_t *list, *next;
 158     pair_t *pair;
 159     size_t i, index, new_size;
 160
 161     free(hashtable->buckets);
 162
 163     hashtable->num_buckets++;
 164     new_size = num_buckets(hashtable);
 165
 166     hashtable->buckets = malloc(new_size * sizeof(bucket_t));
 167     if(!hashtable->buckets)
 168         return -1;
 169
 170     for(i = 0; i < num_buckets(hashtable); i++)
 171     {
 172         hashtable->buckets[i].first = hashtable->buckets[i].last =
 173             &hashtable->list;
 174     }
 175
 176     list = hashtable->list.next;
 177     list_init(&hashtable->list);
 178
 179     for(; list != &hashtable->list; list = next) {
 180         next = list->next;
 181         pair = list_to_pair(list);
 182         index = pair->hash % new_size;
 183         insert_to_bucket(hashtable, &hashtable->buckets[index], &pair->list);
 184     }
 185
 186     return 0;
 187 }
 188
 189
 190 hashtable_t *hashtable_create(key_hash_fn hash_key, key_cmp_fn cmp_keys,
 191                               free_fn free_key, free_fn free_value)
 192 {
 193     hashtable_t *hashtable = malloc(sizeof(hashtable_t));
 194     if(!hashtable)
 195         return NULL;
 196
 197     if(hashtable_init(hashtable, hash_key, cmp_keys, free_key, free_value))
 198     {
 199         free(hashtable);
 200         return NULL;
 201     }
 202
 203     return hashtable;
 204 }
 205
 206 void hashtable_destroy(hashtable_t *hashtable)
 207 {
 208     hashtable_close(hashtable);
 209     free(hashtable);
 210 }
 211
 212 int hashtable_init(hashtable_t *hashtable,
 213                    key_hash_fn hash_key, key_cmp_fn cmp_keys,
 214                    free_fn free_key, free_fn free_value)
 215 {
 216     size_t i;
 217
 218     hashtable->size = 0;
 219     hashtable->num_buckets = 0;  /* index to primes[] */
 220     hashtable->buckets = malloc(num_buckets(hashtable) * sizeof(bucket_t));
 221     if(!hashtable->buckets)
 222         return -1;
 223
 224     list_init(&hashtable->list);
 225
 226     hashtable->hash_key = hash_key;
 227     hashtable->cmp_keys = cmp_keys;
 228     hashtable->free_key = free_key;
 229     hashtable->free_value = free_value;
 230
 231     for(i = 0; i < num_buckets(hashtable); i++)
 232     {
 233         hashtable->buckets[i].first = hashtable->buckets[i].last =
 234             &hashtable->list;
 235     }
 236
 237     return 0;
 238 }
 239
 240 void hashtable_close(hashtable_t *hashtable)
 241 {
 242     hashtable_do_clear(hashtable);
 243     free(hashtable->buckets);
 244 }
 245
 246 int hashtable_set(hashtable_t *hashtable, void *key, void *value)
 247 {
 248     pair_t *pair;
 249     bucket_t *bucket;
 250     size_t hash, index;
 251
 252     /* rehash if the load ratio exceeds 1 */
 253     if(hashtable->size >= num_buckets(hashtable))
 254         if(hashtable_do_rehash(hashtable))
 255             return -1;
 256
 257     hash = hashtable->hash_key(key);
 258     index = hash % num_buckets(hashtable);
 259     bucket = &hashtable->buckets[index];
 260     pair = hashtable_find_pair(hashtable, bucket, key, hash);
 261
 262     if(pair)
 263     {
 264         if(hashtable->free_key)
 265             hashtable->free_key(key);
 266         if(hashtable->free_value)
 267             hashtable->free_value(pair->value);
 268         pair->value = value;
 269     }
 270     else
 271     {
 272         pair = malloc(sizeof(pair_t));
 273         if(!pair)
 274             return -1;
 275
 276         pair->key = key;
 277         pair->value = value;
 278         pair->hash = hash;
 279         list_init(&pair->list);
 280
 281         insert_to_bucket(hashtable, bucket, &pair->list);
 282
 283         hashtable->size++;
 284     }
 285     return 0;
 286 }
 287
 288 void *hashtable_get(hashtable_t *hashtable, const void *key)
 289 {
 290     pair_t *pair;
 291     size_t hash;
 292     bucket_t *bucket;
 293
 294     hash = hashtable->hash_key(key);
 295     bucket = &hashtable->buckets[hash % num_buckets(hashtable)];
 296
 297     pair = hashtable_find_pair(hashtable, bucket, key, hash);
 298     if(!pair)
 299         return NULL;
 300
 301     return pair->value;
 302 }
 303
 304 int hashtable_del(hashtable_t *hashtable, const void *key)
 305 {
 306     size_t hash = hashtable->hash_key(key);
 307     return hashtable_do_del(hashtable, key, hash);
 308 }
 309
 310 void hashtable_clear(hashtable_t *hashtable)
 311 {
 312     size_t i;
 313
 314     hashtable_do_clear(hashtable);
 315
 316     for(i = 0; i < num_buckets(hashtable); i++)
 317     {
 318         hashtable->buckets[i].first = hashtable->buckets[i].last =
 319             &hashtable->list;
 320     }
 321
 322     list_init(&hashtable->list);
 323     hashtable->size = 0;
 324 }
 325
 326 void *hashtable_iter(hashtable_t *hashtable)
 327 {
 328     return hashtable_iter_next(hashtable, &hashtable->list);
 329 }
 330
 331 void *hashtable_iter_at(hashtable_t *hashtable, const void *key)
 332 {
 333     pair_t *pair;
 334     size_t hash;
 335     bucket_t *bucket;
 336
 337     hash = hashtable->hash_key(key);
 338     bucket = &hashtable->buckets[hash % num_buckets(hashtable)];
 339
 340     pair = hashtable_find_pair(hashtable, bucket, key, hash);
 341     if(!pair)
 342         return NULL;
 343
 344     return &pair->list;
 345 }
 346
 347 void *hashtable_iter_next(hashtable_t *hashtable, void *iter)
 348 {
 349     list_t *list = (list_t *)iter;
 350     if(list->next == &hashtable->list)
 351         return NULL;
 352     return list->next;
 353 }
 354
 355 void *hashtable_iter_key(void *iter)
 356 {
 357     pair_t *pair = list_to_pair((list_t *)iter);
 358     return pair->key;
 359 }
 360
 361 void *hashtable_iter_value(void *iter)
 362 {
 363     pair_t *pair = list_to_pair((list_t *)iter);
 364     return pair->value;
 365 }
 366
 367 void hashtable_iter_set(hashtable_t *hashtable, void *iter, void *value)
 368 {
 369     pair_t *pair = list_to_pair((list_t *)iter);
 370
 371     if(hashtable->free_value)
 372         hashtable->free_value(pair->value);
 373
 374     pair->value = value;
 375 }