client/jansson/hashtable.c

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