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