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