]> cvs.zerfleddert.de Git - proxmark3-svn/blame - client/jansson/hashtable.c
Update README.md
[proxmark3-svn] / client / jansson / hashtable.c
CommitLineData
556826b5
OM
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
27typedef struct hashtable_list list_t;
28typedef struct hashtable_pair pair_t;
29typedef struct hashtable_bucket bucket_t;
30
31extern 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
40static JSON_INLINE void list_init(list_t *list)
41{
42 list->next = list;
43 list->prev = list;
44}
45
46static 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
54static JSON_INLINE void list_remove(list_t *list)
55{
56 list->prev->next = list->next;
57 list->next->prev = list->prev;
58}
59
60static 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
65static 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
80static 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 */
106static 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
139static 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
153static 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
191int 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
213void hashtable_close(hashtable_t *hashtable)
214{
215 hashtable_do_clear(hashtable);
216 jsonp_free(hashtable->buckets);
217}
218
219int 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
270void *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
286int 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
292void 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
309void *hashtable_iter(hashtable_t *hashtable)
310{
311 return hashtable_iter_next(hashtable, &hashtable->ordered_list);
312}
313
314void *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
330void *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
338void *hashtable_iter_key(void *iter)
339{
340 pair_t *pair = ordered_list_to_pair((list_t *)iter);
341 return pair->key;
342}
343
344void *hashtable_iter_value(void *iter)
345{
346 pair_t *pair = ordered_list_to_pair((list_t *)iter);
347 return pair->value;
348}
349
350void 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}
Impressum, Datenschutz