src/hashtable.c

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