src/hashtable.c

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