]> git.zerfleddert.de Git - proxmark3-svn/blob - client/jansson/hashtable.c
c819319a76d5707ddbc5329082b9ee9bfdb1d829
[proxmark3-svn] / client / 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 #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
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 {
42 list->next = list;
43 list->prev = list;
44 }
45
46 static 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
54 static JSON_INLINE void list_remove(list_t *list)
55 {
56 list->prev->next = list->next;
57 list->next->prev = list->prev;
58 }
59
60 static 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
65 static 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
80 static 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 */
106 static 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
139 static 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
153 static 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
191 int 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
213 void hashtable_close(hashtable_t *hashtable)
214 {
215 hashtable_do_clear(hashtable);
216 jsonp_free(hashtable->buckets);
217 }
218
219 int 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
270 void *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
286 int 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
292 void 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
309 void *hashtable_iter(hashtable_t *hashtable)
310 {
311 return hashtable_iter_next(hashtable, &hashtable->ordered_list);
312 }
313
314 void *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
330 void *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
338 void *hashtable_iter_key(void *iter)
339 {
340 pair_t *pair = ordered_list_to_pair((list_t *)iter);
341 return pair->key;
342 }
343
344 void *hashtable_iter_value(void *iter)
345 {
346 pair_t *pair = ordered_list_to_pair((list_t *)iter);
347 return pair->value;
348 }
349
350 void 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