Commit | Line | Data |
---|---|---|
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 | ||
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 | } |