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 unsigned int 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 unsigned int num_primes = sizeof(primes) / sizeof(unsigned int);
  69
  70 static inline unsigned int 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, unsigned int 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, unsigned int hash)
 104 {
 105     pair_t *pair;
 106     bucket_t *bucket;
 107     unsigned int 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     unsigned int 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     unsigned int 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     unsigned int hash, index;
 251
 252     hash = hashtable->hash_key(key);
 253
 254     /* if the key already exists, delete it */
 255     hashtable_do_del(hashtable, key, hash);
 256
 257     /* rehash if the load ratio exceeds 1 */
 258     if(hashtable->size >= num_buckets(hashtable))
 259         if(hashtable_do_rehash(hashtable))
 260             return -1;
 261
 262     pair = malloc(sizeof(pair_t));
 263     if(!pair)
 264         return -1;
 265
 266     pair->key = key;
 267     pair->value = value;
 268     pair->hash = hash;
 269     list_init(&pair->list);
 270
 271     index = hash % num_buckets(hashtable);
 272     bucket = &hashtable->buckets[index];
 273
 274     insert_to_bucket(hashtable, bucket, &pair->list);
 275
 276     hashtable->size++;
 277     return 0;
 278 }
 279
 280 void *hashtable_get(hashtable_t *hashtable, const void *key)
 281 {
 282     pair_t *pair;
 283     unsigned int hash;
 284     bucket_t *bucket;
 285
 286     hash = hashtable->hash_key(key);
 287     bucket = &hashtable->buckets[hash % num_buckets(hashtable)];
 288
 289     pair = hashtable_find_pair(hashtable, bucket, key, hash);
 290     if(!pair)
 291         return NULL;
 292
 293     return pair->value;
 294 }
 295
 296 int hashtable_del(hashtable_t *hashtable, const void *key)
 297 {
 298     unsigned int hash = hashtable->hash_key(key);
 299     return hashtable_do_del(hashtable, key, hash);
 300 }
 301
 302 void hashtable_clear(hashtable_t *hashtable)
 303 {
 304     unsigned int i;
 305
 306     hashtable_do_clear(hashtable);
 307
 308     for(i = 0; i < num_buckets(hashtable); i++)
 309     {
 310         hashtable->buckets[i].first = hashtable->buckets[i].last =
 311             &hashtable->list;
 312     }
 313
 314     list_init(&hashtable->list);
 315     hashtable->size = 0;
 316 }
 317
 318 void *hashtable_iter(hashtable_t *hashtable)
 319 {
 320     return hashtable_iter_next(hashtable, &hashtable->list);
 321 }
 322
 323 void *hashtable_iter_next(hashtable_t *hashtable, void *iter)
 324 {
 325     list_t *list = (list_t *)iter;
 326     if(list->next == &hashtable->list)
 327         return NULL;
 328     return list->next;
 329 }
 330
 331 void *hashtable_iter_key(void *iter)
 332 {
 333     pair_t *pair = list_to_pair((list_t *)iter);
 334     return pair->key;
 335 }
 336
 337 void *hashtable_iter_value(void *iter)
 338 {
 339     pair_t *pair = list_to_pair((list_t *)iter);
 340     return pair->value;
 341 }