src/hashtable.c

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