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