|
0
|
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 #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 typedef struct hashtable_list list_t; |
|
|
24 typedef struct hashtable_pair pair_t; |
|
|
25 typedef struct hashtable_bucket bucket_t; |
|
|
26 |
|
|
27 extern 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 |
|
|
35 static JSON_INLINE void list_init(list_t *list) |
|
|
36 { |
|
|
37 list->next = list; |
|
|
38 list->prev = list; |
|
|
39 } |
|
|
40 |
|
|
41 static 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 |
|
|
49 static JSON_INLINE void list_remove(list_t *list) |
|
|
50 { |
|
|
51 list->prev->next = list->next; |
|
|
52 list->next->prev = list->prev; |
|
|
53 } |
|
|
54 |
|
|
55 static 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 |
|
|
60 static 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 |
|
|
75 static 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 */ |
|
|
101 static 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 |
|
|
133 static 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 |
|
|
147 static 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 |
|
|
182 int 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 |
|
|
203 void hashtable_close(hashtable_t *hashtable) |
|
|
204 { |
|
|
205 hashtable_do_clear(hashtable); |
|
|
206 jsonp_free(hashtable->buckets); |
|
|
207 } |
|
|
208 |
|
|
209 int 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 |
|
|
261 void *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 |
|
|
277 int 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 |
|
|
283 void 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 |
|
|
299 void *hashtable_iter(hashtable_t *hashtable) |
|
|
300 { |
|
|
301 return hashtable_iter_next(hashtable, &hashtable->list); |
|
|
302 } |
|
|
303 |
|
|
304 void *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 |
|
|
320 void *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 |
|
|
328 void *hashtable_iter_key(void *iter) |
|
|
329 { |
|
|
330 pair_t *pair = list_to_pair((list_t *)iter); |
|
|
331 return pair->key; |
|
|
332 } |
|
|
333 |
|
|
334 size_t hashtable_iter_serial(void *iter) |
|
|
335 { |
|
|
336 pair_t *pair = list_to_pair((list_t *)iter); |
|
|
337 return pair->serial; |
|
|
338 } |
|
|
339 |
|
|
340 void *hashtable_iter_value(void *iter) |
|
|
341 { |
|
|
342 pair_t *pair = list_to_pair((list_t *)iter); |
|
|
343 return pair->value; |
|
|
344 } |
|
|
345 |
|
|
346 void 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 } |
