jansson-2.14.tar.bz2: jansson-2.14/src/hashtable.c

"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.

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 }