"Fossies" - the Fresh Open Source Software Archive

Member "jansson-2.14/src/hashtable.c" (19 Nov 2020, 9028 Bytes) of package /linux/www/jansson-2.14.tar.bz2:

As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "hashtable.c" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 2.13.1_vs_2.14.

    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 "hashtable.h"
   20 #include "jansson_private.h" /* for container_of() */
   21 #include <jansson_config.h>  /* for JSON_INLINE */
   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, len)          ((size_t)hashlittle((key), len, 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, list_t *list) {
   62     if (bucket_is_empty(hashtable, bucket)) {
   63         list_insert(&hashtable->list, list);
   64         bucket->first = bucket->last = list;
   65     } else {
   66         list_insert(bucket->first, list);
   67         bucket->first = list;
   68     }
   69 }
   70 
   71 static pair_t *hashtable_find_pair(hashtable_t *hashtable, bucket_t *bucket,
   72                                    const char *key, size_t key_len, size_t hash) {
   73     list_t *list;
   74     pair_t *pair;
   75 
   76     if (bucket_is_empty(hashtable, bucket))
   77         return NULL;
   78 
   79     list = bucket->first;
   80     while (1) {
   81         pair = list_to_pair(list);
   82         if (pair->hash == hash && pair->key_len == key_len &&
   83             memcmp(pair->key, key, key_len) == 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, const char *key, size_t key_len,
   97                             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, key_len, 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 = &hashtable->list;
  159     }
  160 
  161     list = hashtable->list.next;
  162     list_init(&hashtable->list);
  163 
  164     for (; list != &hashtable->list; list = next) {
  165         next = list->next;
  166         pair = list_to_pair(list);
  167         index = pair->hash % new_size;
  168         insert_to_bucket(hashtable, &hashtable->buckets[index], &pair->list);
  169     }
  170 
  171     return 0;
  172 }
  173 
  174 int hashtable_init(hashtable_t *hashtable) {
  175     size_t i;
  176 
  177     hashtable->size = 0;
  178     hashtable->order = INITIAL_HASHTABLE_ORDER;
  179     hashtable->buckets = jsonp_malloc(hashsize(hashtable->order) * sizeof(bucket_t));
  180     if (!hashtable->buckets)
  181         return -1;
  182 
  183     list_init(&hashtable->list);
  184     list_init(&hashtable->ordered_list);
  185 
  186     for (i = 0; i < hashsize(hashtable->order); i++) {
  187         hashtable->buckets[i].first = hashtable->buckets[i].last = &hashtable->list;
  188     }
  189 
  190     return 0;
  191 }
  192 
  193 void hashtable_close(hashtable_t *hashtable) {
  194     hashtable_do_clear(hashtable);
  195     jsonp_free(hashtable->buckets);
  196 }
  197 
  198 static pair_t *init_pair(json_t *value, const char *key, size_t key_len, size_t hash) {
  199     pair_t *pair;
  200 
  201     /* offsetof(...) returns the size of pair_t without the last,
  202    flexible member. This way, the correct amount is
  203    allocated. */
  204 
  205     if (key_len >= (size_t)-1 - offsetof(pair_t, key)) {
  206         /* Avoid an overflow if the key is very long */
  207         return NULL;
  208     }
  209 
  210     pair = jsonp_malloc(offsetof(pair_t, key) + key_len + 1);
  211 
  212     if (!pair)
  213         return NULL;
  214 
  215     pair->hash = hash;
  216     memcpy(pair->key, key, key_len);
  217     pair->key[key_len] = '\0';
  218     pair->key_len = key_len;
  219     pair->value = value;
  220 
  221     list_init(&pair->list);
  222     list_init(&pair->ordered_list);
  223 
  224     return pair;
  225 }
  226 
  227 int hashtable_set(hashtable_t *hashtable, const char *key, size_t key_len,
  228                   json_t *value) {
  229     pair_t *pair;
  230     bucket_t *bucket;
  231     size_t hash, index;
  232 
  233     /* rehash if the load ratio exceeds 1 */
  234     if (hashtable->size >= hashsize(hashtable->order))
  235         if (hashtable_do_rehash(hashtable))
  236             return -1;
  237 
  238     hash = hash_str(key, key_len);
  239     index = hash & hashmask(hashtable->order);
  240     bucket = &hashtable->buckets[index];
  241     pair = hashtable_find_pair(hashtable, bucket, key, key_len, hash);
  242 
  243     if (pair) {
  244         json_decref(pair->value);
  245         pair->value = value;
  246     } else {
  247         pair = init_pair(value, key, key_len, hash);
  248 
  249         if (!pair)
  250             return -1;
  251 
  252         insert_to_bucket(hashtable, bucket, &pair->list);
  253         list_insert(&hashtable->ordered_list, &pair->ordered_list);
  254 
  255         hashtable->size++;
  256     }
  257     return 0;
  258 }
  259 
  260 void *hashtable_get(hashtable_t *hashtable, const char *key, size_t key_len) {
  261     pair_t *pair;
  262     size_t hash;
  263     bucket_t *bucket;
  264 
  265     hash = hash_str(key, key_len);
  266     bucket = &hashtable->buckets[hash & hashmask(hashtable->order)];
  267 
  268     pair = hashtable_find_pair(hashtable, bucket, key, key_len, hash);
  269     if (!pair)
  270         return NULL;
  271 
  272     return pair->value;
  273 }
  274 
  275 int hashtable_del(hashtable_t *hashtable, const char *key, size_t key_len) {
  276     size_t hash = hash_str(key, key_len);
  277     return hashtable_do_del(hashtable, key, key_len, hash);
  278 }
  279 
  280 void hashtable_clear(hashtable_t *hashtable) {
  281     size_t i;
  282 
  283     hashtable_do_clear(hashtable);
  284 
  285     for (i = 0; i < hashsize(hashtable->order); i++) {
  286         hashtable->buckets[i].first = hashtable->buckets[i].last = &hashtable->list;
  287     }
  288 
  289     list_init(&hashtable->list);
  290     list_init(&hashtable->ordered_list);
  291     hashtable->size = 0;
  292 }
  293 
  294 void *hashtable_iter(hashtable_t *hashtable) {
  295     return hashtable_iter_next(hashtable, &hashtable->ordered_list);
  296 }
  297 
  298 void *hashtable_iter_at(hashtable_t *hashtable, const char *key, size_t key_len) {
  299     pair_t *pair;
  300     size_t hash;
  301     bucket_t *bucket;
  302 
  303     hash = hash_str(key, key_len);
  304     bucket = &hashtable->buckets[hash & hashmask(hashtable->order)];
  305 
  306     pair = hashtable_find_pair(hashtable, bucket, key, key_len, hash);
  307     if (!pair)
  308         return NULL;
  309 
  310     return &pair->ordered_list;
  311 }
  312 
  313 void *hashtable_iter_next(hashtable_t *hashtable, void *iter) {
  314     list_t *list = (list_t *)iter;
  315     if (list->next == &hashtable->ordered_list)
  316         return NULL;
  317     return list->next;
  318 }
  319 
  320 void *hashtable_iter_key(void *iter) {
  321     pair_t *pair = ordered_list_to_pair((list_t *)iter);
  322     return pair->key;
  323 }
  324 
  325 size_t hashtable_iter_key_len(void *iter) {
  326     pair_t *pair = ordered_list_to_pair((list_t *)iter);
  327     return pair->key_len;
  328 }
  329 
  330 void *hashtable_iter_value(void *iter) {
  331     pair_t *pair = ordered_list_to_pair((list_t *)iter);
  332     return pair->value;
  333 }
  334 
  335 void hashtable_iter_set(void *iter, json_t *value) {
  336     pair_t *pair = ordered_list_to_pair((list_t *)iter);
  337 
  338     json_decref(pair->value);
  339     pair->value = value;
  340 }