Deleted Added
sdiff udiff text old ( 275223 ) new ( 279549 )
full compact
ucl_hash.c (275223) ucl_hash.c (279549)
1/* Copyright (c) 2013, Vsevolod Stakhov
2 * All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are met:
6 * * Redistributions of source code must retain the above copyright
7 * notice, this list of conditions and the following disclaimer.
8 * * Redistributions in binary form must reproduce the above copyright

--- 9 unchanged lines hidden (view full) ---

18 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
19 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
20 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
21 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
22 */
23
24#include "ucl_internal.h"
25#include "ucl_hash.h"
1/* Copyright (c) 2013, Vsevolod Stakhov
2 * All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are met:
6 * * Redistributions of source code must retain the above copyright
7 * notice, this list of conditions and the following disclaimer.
8 * * Redistributions in binary form must reproduce the above copyright

--- 9 unchanged lines hidden (view full) ---

18 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
19 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
20 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
21 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
22 */
23
24#include "ucl_internal.h"
25#include "ucl_hash.h"
26#include "utlist.h"
26#include "khash.h"
27#include "kvec.h"
27
28
29struct ucl_hash_elt {
30 const ucl_object_t *obj;
31 size_t ar_idx;
32};
33
34struct ucl_hash_struct {
35 void *hash;
36 kvec_t(const ucl_object_t *) ar;
37 bool caseless;
38};
39
40static inline uint32_t
41ucl_hash_func (const ucl_object_t *o)
42{
43 return XXH32 (o->key, o->keylen, 0xdeadbeef);
44}
45
46static inline int
47ucl_hash_equal (const ucl_object_t *k1, const ucl_object_t *k2)
48{
49 if (k1->keylen == k2->keylen) {
50 return strncmp (k1->key, k2->key, k1->keylen) == 0;
51 }
52
53 return 0;
54}
55
56KHASH_INIT (ucl_hash_node, const ucl_object_t *, struct ucl_hash_elt, 1,
57 ucl_hash_func, ucl_hash_equal)
58
59static inline uint32_t
60ucl_hash_caseless_func (const ucl_object_t *o)
61{
62 void *xxh = XXH32_init (0xdeadbeef);
63 char hash_buf[64], *c;
64 const char *p;
65 ssize_t remain = o->keylen;
66
67 p = o->key;
68 c = &hash_buf[0];
69
70 while (remain > 0) {
71 *c++ = tolower (*p++);
72
73 if (c - &hash_buf[0] == sizeof (hash_buf)) {
74 XXH32_update (xxh, hash_buf, sizeof (hash_buf));
75 c = &hash_buf[0];
76 }
77 remain --;
78 }
79
80 if (c - &hash_buf[0] != 0) {
81 XXH32_update (xxh, hash_buf, c - &hash_buf[0]);
82 }
83
84 return XXH32_digest (xxh);
85}
86
87static inline int
88ucl_hash_caseless_equal (const ucl_object_t *k1, const ucl_object_t *k2)
89{
90 if (k1->keylen == k2->keylen) {
91 return strncasecmp (k1->key, k2->key, k1->keylen) == 0;
92 }
93
94 return 0;
95}
96
97KHASH_INIT (ucl_hash_caseless_node, const ucl_object_t *, struct ucl_hash_elt, 1,
98 ucl_hash_caseless_func, ucl_hash_caseless_equal)
99
28ucl_hash_t*
100ucl_hash_t*
29ucl_hash_create (void)
101ucl_hash_create (bool ignore_case)
30{
31 ucl_hash_t *new;
32
33 new = UCL_ALLOC (sizeof (ucl_hash_t));
34 if (new != NULL) {
102{
103 ucl_hash_t *new;
104
105 new = UCL_ALLOC (sizeof (ucl_hash_t));
106 if (new != NULL) {
35 new->buckets = NULL;
107 kv_init (new->ar);
108
109 new->caseless = ignore_case;
110 if (ignore_case) {
111 khash_t(ucl_hash_caseless_node) *h = kh_init (ucl_hash_caseless_node);
112 new->hash = (void *)h;
113 }
114 else {
115 khash_t(ucl_hash_node) *h = kh_init (ucl_hash_node);
116 new->hash = (void *)h;
117 }
36 }
37 return new;
38}
39
40void ucl_hash_destroy (ucl_hash_t* hashlin, ucl_hash_free_func *func)
41{
118 }
119 return new;
120}
121
122void ucl_hash_destroy (ucl_hash_t* hashlin, ucl_hash_free_func *func)
123{
42 ucl_hash_node_t *elt, *tmp;
43 const ucl_object_t *cur, *otmp;
124 const ucl_object_t *cur, *tmp;
44
125
45 HASH_ITER (hh, hashlin->buckets, elt, tmp) {
46 HASH_DELETE (hh, hashlin->buckets, elt);
47 if (func) {
48 DL_FOREACH_SAFE (elt->data, cur, otmp) {
49 /* Need to deconst here */
50 func (__DECONST (ucl_object_t *, cur));
126 if (hashlin == NULL) {
127 return;
128 }
129
130 if (func != NULL) {
131 /* Iterate over the hash first */
132 khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *)
133 hashlin->hash;
134 khiter_t k;
135
136 for (k = kh_begin (h); k != kh_end (h); ++k) {
137 if (kh_exist (h, k)) {
138 cur = (kh_value (h, k)).obj;
139 while (cur != NULL) {
140 tmp = cur->next;
141 func (__DECONST (ucl_object_t *, cur));
142 cur = tmp;
143 }
51 }
52 }
144 }
145 }
53 UCL_FREE (sizeof (ucl_hash_node_t), elt);
54 }
146 }
55 UCL_FREE (sizeof (ucl_hash_t), hashlin);
147
148 if (hashlin->caseless) {
149 khash_t(ucl_hash_caseless_node) *h = (khash_t(ucl_hash_caseless_node) *)
150 hashlin->hash;
151 kh_destroy (ucl_hash_caseless_node, h);
152 }
153 else {
154 khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *)
155 hashlin->hash;
156 kh_destroy (ucl_hash_node, h);
157 }
158
159 kv_destroy (hashlin->ar);
160 UCL_FREE (sizeof (*hashlin), hashlin);
56}
57
58void
59ucl_hash_insert (ucl_hash_t* hashlin, const ucl_object_t *obj,
60 const char *key, unsigned keylen)
61{
161}
162
163void
164ucl_hash_insert (ucl_hash_t* hashlin, const ucl_object_t *obj,
165 const char *key, unsigned keylen)
166{
62 ucl_hash_node_t *node;
167 khiter_t k;
168 int ret;
169 struct ucl_hash_elt *elt;
63
170
64 node = UCL_ALLOC (sizeof (ucl_hash_node_t));
65 node->data = obj;
66 HASH_ADD_KEYPTR (hh, hashlin->buckets, key, keylen, node);
171 if (hashlin == NULL) {
172 return;
173 }
174
175 if (hashlin->caseless) {
176 khash_t(ucl_hash_caseless_node) *h = (khash_t(ucl_hash_caseless_node) *)
177 hashlin->hash;
178 k = kh_put (ucl_hash_caseless_node, h, obj, &ret);
179 if (ret > 0) {
180 elt = &kh_value (h, k);
181 kv_push (const ucl_object_t *, hashlin->ar, obj);
182 elt->obj = obj;
183 elt->ar_idx = kv_size (hashlin->ar) - 1;
184 }
185 }
186 else {
187 khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *)
188 hashlin->hash;
189 k = kh_put (ucl_hash_node, h, obj, &ret);
190 if (ret > 0) {
191 elt = &kh_value (h, k);
192 kv_push (const ucl_object_t *, hashlin->ar, obj);
193 elt->obj = obj;
194 elt->ar_idx = kv_size (hashlin->ar) - 1;
195 }
196 }
67}
68
69void ucl_hash_replace (ucl_hash_t* hashlin, const ucl_object_t *old,
70 const ucl_object_t *new)
71{
197}
198
199void ucl_hash_replace (ucl_hash_t* hashlin, const ucl_object_t *old,
200 const ucl_object_t *new)
201{
72 ucl_hash_node_t *node;
202 khiter_t k;
203 int ret;
204 struct ucl_hash_elt elt, *pelt;
73
205
74 HASH_FIND (hh, hashlin->buckets, old->key, old->keylen, node);
75 if (node != NULL) {
76 /* Direct replacement */
77 node->data = new;
78 node->hh.key = new->key;
79 node->hh.keylen = new->keylen;
206 if (hashlin == NULL) {
207 return;
80 }
208 }
209
210 if (hashlin->caseless) {
211 khash_t(ucl_hash_caseless_node) *h = (khash_t(ucl_hash_caseless_node) *)
212 hashlin->hash;
213 k = kh_put (ucl_hash_caseless_node, h, old, &ret);
214 if (ret == 0) {
215 elt = kh_value (h, k);
216 kh_del (ucl_hash_caseless_node, h, k);
217 k = kh_put (ucl_hash_caseless_node, h, new, &ret);
218 pelt = &kh_value (h, k);
219 pelt->obj = new;
220 pelt->ar_idx = elt.ar_idx;
221 kv_A (hashlin->ar, elt.ar_idx) = new;
222 }
223 }
224 else {
225 khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *)
226 hashlin->hash;
227 k = kh_put (ucl_hash_node, h, old, &ret);
228 if (ret == 0) {
229 elt = kh_value (h, k);
230 kh_del (ucl_hash_node, h, k);
231 k = kh_put (ucl_hash_node, h, new, &ret);
232 pelt = &kh_value (h, k);
233 pelt->obj = new;
234 pelt->ar_idx = elt.ar_idx;
235 kv_A (hashlin->ar, elt.ar_idx) = new;
236 }
237 }
81}
82
238}
239
240struct ucl_hash_real_iter {
241 const ucl_object_t **cur;
242 const ucl_object_t **end;
243};
244
83const void*
84ucl_hash_iterate (ucl_hash_t *hashlin, ucl_hash_iter_t *iter)
85{
245const void*
246ucl_hash_iterate (ucl_hash_t *hashlin, ucl_hash_iter_t *iter)
247{
86 ucl_hash_node_t *elt = *iter;
248 struct ucl_hash_real_iter *it = (struct ucl_hash_real_iter *)(*iter);
249 const ucl_object_t *ret = NULL;
87
250
88 if (elt == NULL) {
89 if (hashlin == NULL || hashlin->buckets == NULL) {
90 return NULL;
91 }
92 elt = hashlin->buckets;
93 if (elt == NULL) {
94 return NULL;
95 }
251 if (hashlin == NULL) {
252 return NULL;
96 }
253 }
97 else if (elt == hashlin->buckets) {
254
255 if (it == NULL) {
256 it = UCL_ALLOC (sizeof (*it));
257 it->cur = &hashlin->ar.a[0];
258 it->end = it->cur + hashlin->ar.n;
259 }
260
261 if (it->cur < it->end) {
262 ret = *it->cur++;
263 }
264 else {
265 UCL_FREE (sizeof (*it), it);
266 *iter = NULL;
98 return NULL;
99 }
100
267 return NULL;
268 }
269
101 *iter = elt->hh.next ? elt->hh.next : hashlin->buckets;
102 return elt->data;
270 *iter = it;
271
272 return ret;
103}
104
105bool
273}
274
275bool
106ucl_hash_iter_has_next (ucl_hash_iter_t iter)
276ucl_hash_iter_has_next (ucl_hash_t *hashlin, ucl_hash_iter_t iter)
107{
277{
108 ucl_hash_node_t *elt = iter;
278 struct ucl_hash_real_iter *it = (struct ucl_hash_real_iter *)(iter);
109
279
110 return (elt == NULL || elt->hh.prev != NULL);
280 return it->cur < it->end - 1;
111}
112
113
114const ucl_object_t*
115ucl_hash_search (ucl_hash_t* hashlin, const char *key, unsigned keylen)
116{
281}
282
283
284const ucl_object_t*
285ucl_hash_search (ucl_hash_t* hashlin, const char *key, unsigned keylen)
286{
117 ucl_hash_node_t *found;
287 khiter_t k;
288 const ucl_object_t *ret = NULL;
289 ucl_object_t search;
290 struct ucl_hash_elt *elt;
118
291
292 search.key = key;
293 search.keylen = keylen;
294
119 if (hashlin == NULL) {
120 return NULL;
121 }
295 if (hashlin == NULL) {
296 return NULL;
297 }
122 HASH_FIND (hh, hashlin->buckets, key, keylen, found);
123
298
124 if (found) {
125 return found->data;
299 if (hashlin->caseless) {
300 khash_t(ucl_hash_caseless_node) *h = (khash_t(ucl_hash_caseless_node) *)
301 hashlin->hash;
302
303 k = kh_get (ucl_hash_caseless_node, h, &search);
304 if (k != kh_end (h)) {
305 elt = &kh_value (h, k);
306 ret = elt->obj;
307 }
126 }
308 }
127 return NULL;
309 else {
310 khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *)
311 hashlin->hash;
312 k = kh_get (ucl_hash_node, h, &search);
313 if (k != kh_end (h)) {
314 elt = &kh_value (h, k);
315 ret = elt->obj;
316 }
317 }
318
319 return ret;
128}
129
130void
131ucl_hash_delete (ucl_hash_t* hashlin, const ucl_object_t *obj)
132{
320}
321
322void
323ucl_hash_delete (ucl_hash_t* hashlin, const ucl_object_t *obj)
324{
133 ucl_hash_node_t *found;
325 khiter_t k;
326 struct ucl_hash_elt *elt;
134
327
135 HASH_FIND (hh, hashlin->buckets, obj->key, obj->keylen, found);
328 if (hashlin == NULL) {
329 return;
330 }
136
331
137 if (found) {
138 HASH_DELETE (hh, hashlin->buckets, found);
139 UCL_FREE (sizeof (ucl_hash_node_t), found);
332 if (hashlin->caseless) {
333 khash_t(ucl_hash_caseless_node) *h = (khash_t(ucl_hash_caseless_node) *)
334 hashlin->hash;
335
336 k = kh_get (ucl_hash_caseless_node, h, obj);
337 if (k != kh_end (h)) {
338 elt = &kh_value (h, k);
339 kv_A (hashlin->ar, elt->ar_idx) = NULL;
340 kh_del (ucl_hash_caseless_node, h, k);
341 }
140 }
342 }
343 else {
344 khash_t(ucl_hash_node) *h = (khash_t(ucl_hash_node) *)
345 hashlin->hash;
346 k = kh_get (ucl_hash_node, h, obj);
347 if (k != kh_end (h)) {
348 elt = &kh_value (h, k);
349 kv_A (hashlin->ar, elt->ar_idx) = NULL;
350 kh_del (ucl_hash_node, h, k);
351 }
352 }
141}
353}