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