diff options
Diffstat (limited to '')
-rw-r--r-- | libraries/eina/src/lib/eina_hash.c | 1375 |
1 files changed, 1375 insertions, 0 deletions
diff --git a/libraries/eina/src/lib/eina_hash.c b/libraries/eina/src/lib/eina_hash.c new file mode 100644 index 0000000..5df20aa --- /dev/null +++ b/libraries/eina/src/lib/eina_hash.c | |||
@@ -0,0 +1,1375 @@ | |||
1 | /* EINA - EFL data type library | ||
2 | * Copyright (C) 2002-2008 Carsten Haitzler, Gustavo Sverzut Barbieri, | ||
3 | * Vincent Torri, Jorge Luis Zapata Muga, Cedric Bail | ||
4 | * | ||
5 | * This library is free software; you can redistribute it and/or | ||
6 | * modify it under the terms of the GNU Lesser General Public | ||
7 | * License as published by the Free Software Foundation; either | ||
8 | * version 2.1 of the License, or (at your option) any later version. | ||
9 | * | ||
10 | * This library is distributed in the hope that it will be useful, | ||
11 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
12 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | ||
13 | * Lesser General Public License for more details. | ||
14 | * | ||
15 | * You should have received a copy of the GNU Lesser General Public | ||
16 | * License along with this library; | ||
17 | * if not, see <http://www.gnu.org/licenses/>. | ||
18 | */ | ||
19 | |||
20 | #ifdef HAVE_CONFIG_H | ||
21 | # include "config.h" | ||
22 | #endif | ||
23 | |||
24 | #include <stdio.h> | ||
25 | #include <stdlib.h> | ||
26 | #include <string.h> | ||
27 | |||
28 | #ifdef HAVE_STDINT_H | ||
29 | # include <stdint.h> | ||
30 | #endif | ||
31 | |||
32 | #ifdef _MSC_VER | ||
33 | # include <Evil.h> | ||
34 | #endif | ||
35 | |||
36 | #include "eina_config.h" | ||
37 | #include "eina_private.h" | ||
38 | #include "eina_rbtree.h" | ||
39 | #include "eina_error.h" | ||
40 | |||
41 | /* undefs EINA_ARG_NONULL() so NULL checks are not compiled out! */ | ||
42 | #include "eina_safety_checks.h" | ||
43 | #include "eina_hash.h" | ||
44 | |||
45 | /*============================================================================* | ||
46 | * Local * | ||
47 | *============================================================================*/ | ||
48 | |||
49 | /** | ||
50 | * @cond LOCAL | ||
51 | */ | ||
52 | |||
53 | #define EINA_MAGIC_CHECK_HASH(d) \ | ||
54 | do { \ | ||
55 | if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_HASH)) { \ | ||
56 | EINA_MAGIC_FAIL(d, EINA_MAGIC_HASH); } \ | ||
57 | } while(0) | ||
58 | |||
59 | #define EINA_MAGIC_CHECK_HASH_ITERATOR(d, ...) \ | ||
60 | do { \ | ||
61 | if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_HASH_ITERATOR)) \ | ||
62 | { \ | ||
63 | EINA_MAGIC_FAIL(d, EINA_MAGIC_HASH_ITERATOR); \ | ||
64 | return __VA_ARGS__; \ | ||
65 | } \ | ||
66 | } while(0) | ||
67 | |||
68 | #define EINA_HASH_BUCKET_SIZE 8 | ||
69 | #define EINA_HASH_SMALL_BUCKET_SIZE 5 | ||
70 | |||
71 | #define EINA_HASH_RBTREE_MASK 0xFFF | ||
72 | |||
73 | typedef struct _Eina_Hash_Head Eina_Hash_Head; | ||
74 | typedef struct _Eina_Hash_Element Eina_Hash_Element; | ||
75 | typedef struct _Eina_Hash_Foreach_Data Eina_Hash_Foreach_Data; | ||
76 | typedef struct _Eina_Iterator_Hash Eina_Iterator_Hash; | ||
77 | typedef struct _Eina_Hash_Each Eina_Hash_Each; | ||
78 | |||
79 | struct _Eina_Hash | ||
80 | { | ||
81 | Eina_Key_Length key_length_cb; | ||
82 | Eina_Key_Cmp key_cmp_cb; | ||
83 | Eina_Key_Hash key_hash_cb; | ||
84 | Eina_Free_Cb data_free_cb; | ||
85 | |||
86 | Eina_Rbtree **buckets; | ||
87 | int size; | ||
88 | int mask; | ||
89 | |||
90 | int population; | ||
91 | |||
92 | EINA_MAGIC | ||
93 | }; | ||
94 | |||
95 | struct _Eina_Hash_Head | ||
96 | { | ||
97 | EINA_RBTREE; | ||
98 | int hash; | ||
99 | |||
100 | Eina_Rbtree *head; | ||
101 | }; | ||
102 | |||
103 | struct _Eina_Hash_Element | ||
104 | { | ||
105 | EINA_RBTREE; | ||
106 | Eina_Hash_Tuple tuple; | ||
107 | Eina_Bool begin : 1; | ||
108 | }; | ||
109 | |||
110 | struct _Eina_Hash_Foreach_Data | ||
111 | { | ||
112 | Eina_Hash_Foreach cb; | ||
113 | const void *fdata; | ||
114 | }; | ||
115 | |||
116 | typedef void *(*Eina_Iterator_Get_Content_Callback)(Eina_Iterator_Hash *it); | ||
117 | #define FUNC_ITERATOR_GET_CONTENT(Function) \ | ||
118 | ((Eina_Iterator_Get_Content_Callback)Function) | ||
119 | |||
120 | struct _Eina_Iterator_Hash | ||
121 | { | ||
122 | Eina_Iterator iterator; | ||
123 | |||
124 | Eina_Iterator_Get_Content_Callback get_content; | ||
125 | const Eina_Hash *hash; | ||
126 | |||
127 | Eina_Iterator *current; | ||
128 | Eina_Iterator *list; | ||
129 | Eina_Hash_Head *hash_head; | ||
130 | Eina_Hash_Element *hash_element; | ||
131 | int bucket; | ||
132 | |||
133 | int index; | ||
134 | |||
135 | EINA_MAGIC | ||
136 | }; | ||
137 | |||
138 | struct _Eina_Hash_Each | ||
139 | { | ||
140 | Eina_Hash_Head *hash_head; | ||
141 | const Eina_Hash_Element *hash_element; | ||
142 | const void *data; | ||
143 | }; | ||
144 | |||
145 | #undef get16bits | ||
146 | #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \ | ||
147 | || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__) | ||
148 | # define get16bits(d) (*((const uint16_t *)(d))) | ||
149 | #endif | ||
150 | |||
151 | #if !defined (get16bits) | ||
152 | # define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8) \ | ||
153 | + (uint32_t)(((const uint8_t *)(d))[0])) | ||
154 | #endif | ||
155 | |||
156 | static inline int | ||
157 | _eina_hash_hash_rbtree_cmp_hash(const Eina_Hash_Head *hash_head, | ||
158 | const int *hash, | ||
159 | __UNUSED__ int key_length, | ||
160 | __UNUSED__ void *data) | ||
161 | { | ||
162 | return hash_head->hash - *hash; | ||
163 | } | ||
164 | |||
165 | static Eina_Rbtree_Direction | ||
166 | _eina_hash_hash_rbtree_cmp_node(const Eina_Hash_Head *left, | ||
167 | const Eina_Hash_Head *right, | ||
168 | __UNUSED__ void *data) | ||
169 | { | ||
170 | if (left->hash - right->hash < 0) | ||
171 | return EINA_RBTREE_LEFT; | ||
172 | |||
173 | return EINA_RBTREE_RIGHT; | ||
174 | } | ||
175 | |||
176 | static inline int | ||
177 | _eina_hash_key_rbtree_cmp_key_data(const Eina_Hash_Element *hash_element, | ||
178 | const Eina_Hash_Tuple *tuple, | ||
179 | __UNUSED__ unsigned int key_length, | ||
180 | Eina_Key_Cmp cmp) | ||
181 | { | ||
182 | int result; | ||
183 | |||
184 | result = cmp(hash_element->tuple.key, | ||
185 | hash_element->tuple.key_length, | ||
186 | tuple->key, | ||
187 | tuple->key_length); | ||
188 | |||
189 | if (result == 0 && tuple->data && tuple->data != hash_element->tuple.data) | ||
190 | return 1; | ||
191 | |||
192 | return result; | ||
193 | } | ||
194 | |||
195 | static Eina_Rbtree_Direction | ||
196 | _eina_hash_key_rbtree_cmp_node(const Eina_Hash_Element *left, | ||
197 | const Eina_Hash_Element *right, | ||
198 | Eina_Key_Cmp cmp) | ||
199 | { | ||
200 | int result; | ||
201 | |||
202 | result = cmp(left->tuple.key, left->tuple.key_length, | ||
203 | right->tuple.key, right->tuple.key_length); | ||
204 | |||
205 | if (result < 0) | ||
206 | return EINA_RBTREE_LEFT; | ||
207 | |||
208 | return EINA_RBTREE_RIGHT; | ||
209 | } | ||
210 | |||
211 | static inline Eina_Bool | ||
212 | eina_hash_add_alloc_by_hash(Eina_Hash *hash, | ||
213 | const void *key, int key_length, int alloc_length, | ||
214 | int key_hash, | ||
215 | const void *data) | ||
216 | { | ||
217 | Eina_Hash_Element *new_hash_element = NULL; | ||
218 | Eina_Hash_Head *hash_head; | ||
219 | Eina_Error error = 0; | ||
220 | int hash_num; | ||
221 | |||
222 | EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE); | ||
223 | EINA_SAFETY_ON_NULL_RETURN_VAL(key, EINA_FALSE); | ||
224 | EINA_SAFETY_ON_NULL_RETURN_VAL(data, EINA_FALSE); | ||
225 | EINA_MAGIC_CHECK_HASH(hash); | ||
226 | |||
227 | error = EINA_ERROR_OUT_OF_MEMORY; | ||
228 | |||
229 | /* Apply eina mask to hash. */ | ||
230 | hash_num = key_hash & hash->mask; | ||
231 | key_hash &= EINA_HASH_RBTREE_MASK; | ||
232 | |||
233 | if (!hash->buckets) | ||
234 | { | ||
235 | hash->buckets = calloc(sizeof (Eina_Rbtree *), hash->size); | ||
236 | if (!hash->buckets) goto on_error; | ||
237 | |||
238 | hash_head = NULL; | ||
239 | } | ||
240 | else | ||
241 | /* Look up for head node. */ | ||
242 | hash_head = (Eina_Hash_Head *) | ||
243 | eina_rbtree_inline_lookup(hash->buckets[hash_num], | ||
244 | &key_hash, 0, | ||
245 | EINA_RBTREE_CMP_KEY_CB( | ||
246 | _eina_hash_hash_rbtree_cmp_hash), | ||
247 | NULL); | ||
248 | |||
249 | if (!hash_head) | ||
250 | { | ||
251 | /* If not found allocate it and an element. */ | ||
252 | hash_head = malloc(sizeof(Eina_Hash_Head) + sizeof(Eina_Hash_Element) | ||
253 | + alloc_length); | ||
254 | if (!hash_head) | ||
255 | goto on_error; | ||
256 | |||
257 | hash_head->hash = key_hash; | ||
258 | hash_head->head = NULL; | ||
259 | |||
260 | hash->buckets[hash_num] = | ||
261 | eina_rbtree_inline_insert(hash->buckets[hash_num], | ||
262 | EINA_RBTREE_GET(hash_head), | ||
263 | EINA_RBTREE_CMP_NODE_CB( | ||
264 | _eina_hash_hash_rbtree_cmp_node), | ||
265 | NULL); | ||
266 | |||
267 | new_hash_element = (Eina_Hash_Element *)(hash_head + 1); | ||
268 | new_hash_element->begin = EINA_TRUE; | ||
269 | } | ||
270 | |||
271 | if (!new_hash_element) | ||
272 | { | ||
273 | /* | ||
274 | Alloc a new element | ||
275 | (No more lookup as we expect to support more than one item for one key). | ||
276 | */ | ||
277 | new_hash_element = malloc(sizeof (Eina_Hash_Element) + alloc_length); | ||
278 | if (!new_hash_element) | ||
279 | goto on_error; | ||
280 | |||
281 | new_hash_element->begin = EINA_FALSE; | ||
282 | } | ||
283 | |||
284 | /* Setup the element */ | ||
285 | new_hash_element->tuple.key_length = key_length; | ||
286 | new_hash_element->tuple.data = (void *)data; | ||
287 | if (alloc_length > 0) | ||
288 | { | ||
289 | new_hash_element->tuple.key = (char *)(new_hash_element + 1); | ||
290 | memcpy((char *)new_hash_element->tuple.key, key, alloc_length); | ||
291 | } | ||
292 | else | ||
293 | new_hash_element->tuple.key = key; | ||
294 | |||
295 | /* add the new element to the hash. */ | ||
296 | hash_head->head = eina_rbtree_inline_insert(hash_head->head, | ||
297 | EINA_RBTREE_GET(new_hash_element), | ||
298 | EINA_RBTREE_CMP_NODE_CB( | ||
299 | _eina_hash_key_rbtree_cmp_node), | ||
300 | (const void *)hash->key_cmp_cb); | ||
301 | hash->population++; | ||
302 | return EINA_TRUE; | ||
303 | |||
304 | on_error: | ||
305 | eina_error_set(error); | ||
306 | return EINA_FALSE; | ||
307 | } | ||
308 | |||
309 | static Eina_Bool | ||
310 | _eina_hash_rbtree_each(__UNUSED__ const Eina_Rbtree *container, | ||
311 | const Eina_Hash_Head *hash_head, | ||
312 | Eina_Hash_Each *data) | ||
313 | { | ||
314 | Eina_Iterator *it; | ||
315 | Eina_Hash_Element *hash_element; | ||
316 | Eina_Bool found = EINA_TRUE; | ||
317 | |||
318 | it = eina_rbtree_iterator_prefix(hash_head->head); | ||
319 | EINA_ITERATOR_FOREACH(it, hash_element) | ||
320 | { | ||
321 | if (hash_element->tuple.data == data->data) | ||
322 | { | ||
323 | data->hash_element = hash_element; | ||
324 | data->hash_head = (Eina_Hash_Head *)hash_head; | ||
325 | found = EINA_FALSE; | ||
326 | break; | ||
327 | } | ||
328 | } | ||
329 | |||
330 | eina_iterator_free(it); | ||
331 | return found; | ||
332 | } | ||
333 | |||
334 | static inline Eina_Hash_Element * | ||
335 | _eina_hash_find_by_hash(const Eina_Hash *hash, | ||
336 | Eina_Hash_Tuple *tuple, | ||
337 | int key_hash, | ||
338 | Eina_Hash_Head **hash_head) | ||
339 | { | ||
340 | Eina_Hash_Element *hash_element; | ||
341 | int rb_hash = key_hash & EINA_HASH_RBTREE_MASK; | ||
342 | |||
343 | key_hash &= hash->mask; | ||
344 | |||
345 | if (!hash->buckets) | ||
346 | return NULL; | ||
347 | |||
348 | *hash_head = (Eina_Hash_Head *) | ||
349 | eina_rbtree_inline_lookup(hash->buckets[key_hash], | ||
350 | &rb_hash, 0, | ||
351 | EINA_RBTREE_CMP_KEY_CB( | ||
352 | _eina_hash_hash_rbtree_cmp_hash), | ||
353 | NULL); | ||
354 | if (!*hash_head) | ||
355 | return NULL; | ||
356 | |||
357 | hash_element = (Eina_Hash_Element *) | ||
358 | eina_rbtree_inline_lookup((*hash_head)->head, | ||
359 | tuple, 0, | ||
360 | EINA_RBTREE_CMP_KEY_CB( | ||
361 | _eina_hash_key_rbtree_cmp_key_data), | ||
362 | (const void *)hash->key_cmp_cb); | ||
363 | |||
364 | return hash_element; | ||
365 | } | ||
366 | |||
367 | static inline Eina_Hash_Element * | ||
368 | _eina_hash_find_by_data(const Eina_Hash *hash, | ||
369 | const void *data, | ||
370 | int *key_hash, | ||
371 | Eina_Hash_Head **hash_head) | ||
372 | { | ||
373 | Eina_Hash_Each each; | ||
374 | Eina_Iterator *it; | ||
375 | int hash_num; | ||
376 | |||
377 | if (!hash->buckets) | ||
378 | return NULL; | ||
379 | |||
380 | each.hash_element = NULL; | ||
381 | each.data = data; | ||
382 | |||
383 | for (hash_num = 0; hash_num < hash->size; hash_num++) | ||
384 | { | ||
385 | if (!hash->buckets[hash_num]) | ||
386 | continue; | ||
387 | |||
388 | it = eina_rbtree_iterator_prefix(hash->buckets[hash_num]); | ||
389 | eina_iterator_foreach(it, EINA_EACH_CB(_eina_hash_rbtree_each), &each); | ||
390 | eina_iterator_free(it); | ||
391 | |||
392 | if (each.hash_element) | ||
393 | { | ||
394 | *key_hash = hash_num; | ||
395 | *hash_head = each.hash_head; | ||
396 | return (Eina_Hash_Element *)each.hash_element; | ||
397 | } | ||
398 | } | ||
399 | |||
400 | return NULL; | ||
401 | } | ||
402 | |||
403 | static void | ||
404 | _eina_hash_el_free(Eina_Hash_Element *hash_element, Eina_Hash *hash) | ||
405 | { | ||
406 | if (hash->data_free_cb) | ||
407 | hash->data_free_cb(hash_element->tuple.data); | ||
408 | |||
409 | if (hash_element->begin == EINA_FALSE) | ||
410 | free(hash_element); | ||
411 | } | ||
412 | |||
413 | static void | ||
414 | _eina_hash_head_free(Eina_Hash_Head *hash_head, Eina_Hash *hash) | ||
415 | { | ||
416 | eina_rbtree_delete(hash_head->head, EINA_RBTREE_FREE_CB(_eina_hash_el_free), hash); | ||
417 | free(hash_head); | ||
418 | } | ||
419 | |||
420 | static Eina_Bool | ||
421 | _eina_hash_del_by_hash_el(Eina_Hash *hash, | ||
422 | Eina_Hash_Element *hash_element, | ||
423 | Eina_Hash_Head *hash_head, | ||
424 | int key_hash) | ||
425 | { | ||
426 | hash_head->head = eina_rbtree_inline_remove(hash_head->head, EINA_RBTREE_GET( | ||
427 | hash_element), EINA_RBTREE_CMP_NODE_CB( | ||
428 | _eina_hash_key_rbtree_cmp_node), | ||
429 | (const void *)hash->key_cmp_cb); | ||
430 | _eina_hash_el_free(hash_element, hash); | ||
431 | |||
432 | if (!hash_head->head) | ||
433 | { | ||
434 | key_hash &= hash->mask; | ||
435 | |||
436 | hash->buckets[key_hash] = | ||
437 | eina_rbtree_inline_remove(hash->buckets[key_hash], EINA_RBTREE_GET( | ||
438 | hash_head), | ||
439 | EINA_RBTREE_CMP_NODE_CB( | ||
440 | _eina_hash_hash_rbtree_cmp_node), NULL); | ||
441 | free(hash_head); | ||
442 | } | ||
443 | |||
444 | hash->population--; | ||
445 | if (hash->population == 0) | ||
446 | { | ||
447 | free(hash->buckets); | ||
448 | hash->buckets = NULL; | ||
449 | } | ||
450 | |||
451 | return EINA_TRUE; | ||
452 | } | ||
453 | |||
454 | static Eina_Bool | ||
455 | _eina_hash_del_by_key_hash(Eina_Hash *hash, | ||
456 | const void *key, | ||
457 | int key_length, | ||
458 | int key_hash, | ||
459 | const void *data) | ||
460 | { | ||
461 | Eina_Hash_Element *hash_element; | ||
462 | Eina_Hash_Head *hash_head; | ||
463 | Eina_Hash_Tuple tuple; | ||
464 | |||
465 | EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE); | ||
466 | EINA_SAFETY_ON_NULL_RETURN_VAL(key, EINA_FALSE); | ||
467 | EINA_MAGIC_CHECK_HASH(hash); | ||
468 | |||
469 | if (!hash->buckets) | ||
470 | return EINA_FALSE; | ||
471 | |||
472 | tuple.key = (void *)key; | ||
473 | tuple.key_length = key_length; | ||
474 | tuple.data = (void *)data; | ||
475 | |||
476 | hash_element = _eina_hash_find_by_hash(hash, &tuple, key_hash, &hash_head); | ||
477 | if (!hash_element) | ||
478 | return EINA_FALSE; | ||
479 | |||
480 | return _eina_hash_del_by_hash_el(hash, hash_element, hash_head, key_hash); | ||
481 | } | ||
482 | |||
483 | static Eina_Bool | ||
484 | _eina_hash_del_by_key(Eina_Hash *hash, const void *key, const void *data) | ||
485 | { | ||
486 | int key_length, key_hash; | ||
487 | |||
488 | EINA_MAGIC_CHECK_HASH(hash); | ||
489 | if (!hash) | ||
490 | return EINA_FALSE; | ||
491 | |||
492 | if (!key) | ||
493 | return EINA_FALSE; | ||
494 | |||
495 | if (!hash->buckets) | ||
496 | return EINA_FALSE; | ||
497 | |||
498 | key_length = hash->key_length_cb ? hash->key_length_cb(key) : 0; | ||
499 | key_hash = hash->key_hash_cb(key, key_length); | ||
500 | return _eina_hash_del_by_key_hash(hash, key, key_length, key_hash, data); | ||
501 | } | ||
502 | |||
503 | static unsigned int | ||
504 | _eina_string_key_length(const char *key) | ||
505 | { | ||
506 | if (!key) | ||
507 | return 0; | ||
508 | |||
509 | return (int)strlen(key) + 1; | ||
510 | } | ||
511 | |||
512 | static int | ||
513 | _eina_string_key_cmp(const char *key1, __UNUSED__ int key1_length, | ||
514 | const char *key2, __UNUSED__ int key2_length) | ||
515 | { | ||
516 | return strcmp(key1, key2); | ||
517 | } | ||
518 | |||
519 | static int | ||
520 | _eina_stringshared_key_cmp(const char *key1, __UNUSED__ int key1_length, | ||
521 | const char *key2, __UNUSED__ int key2_length) | ||
522 | { | ||
523 | return key1 - key2; | ||
524 | } | ||
525 | |||
526 | static unsigned int | ||
527 | _eina_int32_key_length(__UNUSED__ const uint32_t *key) | ||
528 | { | ||
529 | return 4; | ||
530 | } | ||
531 | |||
532 | static int | ||
533 | _eina_int32_key_cmp(const uint32_t *key1, __UNUSED__ int key1_length, | ||
534 | const uint32_t *key2, __UNUSED__ int key2_length) | ||
535 | { | ||
536 | return *key1 - *key2; | ||
537 | } | ||
538 | |||
539 | static unsigned int | ||
540 | _eina_int64_key_length(__UNUSED__ const uint32_t *key) | ||
541 | { | ||
542 | return 8; | ||
543 | } | ||
544 | |||
545 | static int | ||
546 | _eina_int64_key_cmp(const uint64_t *key1, __UNUSED__ int key1_length, | ||
547 | const uint64_t *key2, __UNUSED__ int key2_length) | ||
548 | { | ||
549 | return *key1 - *key2; | ||
550 | } | ||
551 | |||
552 | static Eina_Bool | ||
553 | _eina_foreach_cb(const Eina_Hash *hash, | ||
554 | Eina_Hash_Tuple *data, | ||
555 | Eina_Hash_Foreach_Data *fdata) | ||
556 | { | ||
557 | return fdata->cb((Eina_Hash *)hash, | ||
558 | data->key, | ||
559 | data->data, | ||
560 | (void *)fdata->fdata); | ||
561 | } | ||
562 | |||
563 | static void * | ||
564 | _eina_hash_iterator_data_get_content(Eina_Iterator_Hash *it) | ||
565 | { | ||
566 | Eina_Hash_Element *stuff; | ||
567 | |||
568 | EINA_MAGIC_CHECK_HASH_ITERATOR(it, NULL); | ||
569 | |||
570 | stuff = it->hash_element; | ||
571 | |||
572 | if (!stuff) | ||
573 | return NULL; | ||
574 | |||
575 | return stuff->tuple.data; | ||
576 | } | ||
577 | |||
578 | static void * | ||
579 | _eina_hash_iterator_key_get_content(Eina_Iterator_Hash *it) | ||
580 | { | ||
581 | Eina_Hash_Element *stuff; | ||
582 | |||
583 | EINA_MAGIC_CHECK_HASH_ITERATOR(it, NULL); | ||
584 | |||
585 | stuff = it->hash_element; | ||
586 | |||
587 | if (!stuff) | ||
588 | return NULL; | ||
589 | |||
590 | return (void *)stuff->tuple.key; | ||
591 | } | ||
592 | |||
593 | static Eina_Hash_Tuple * | ||
594 | _eina_hash_iterator_tuple_get_content(Eina_Iterator_Hash *it) | ||
595 | { | ||
596 | Eina_Hash_Element *stuff; | ||
597 | |||
598 | EINA_MAGIC_CHECK_HASH_ITERATOR(it, NULL); | ||
599 | |||
600 | stuff = it->hash_element; | ||
601 | |||
602 | if (!stuff) | ||
603 | return NULL; | ||
604 | |||
605 | return &stuff->tuple; | ||
606 | } | ||
607 | |||
608 | static Eina_Bool | ||
609 | _eina_hash_iterator_next(Eina_Iterator_Hash *it, void **data) | ||
610 | { | ||
611 | Eina_Bool ok; | ||
612 | int bucket; | ||
613 | |||
614 | if (!(it->index < it->hash->population)) | ||
615 | return EINA_FALSE; | ||
616 | |||
617 | if (!it->current) | ||
618 | { | ||
619 | ok = EINA_FALSE; | ||
620 | bucket = 0; | ||
621 | it->index = -1; | ||
622 | } | ||
623 | else | ||
624 | { | ||
625 | ok = eina_iterator_next(it->list, (void **)(void*)&it->hash_element); | ||
626 | if (!ok) | ||
627 | { | ||
628 | eina_iterator_free(it->list); | ||
629 | it->list = NULL; | ||
630 | |||
631 | ok = eina_iterator_next(it->current, (void **)(void*)&it->hash_head); | ||
632 | if (!ok) | ||
633 | { | ||
634 | eina_iterator_free(it->current); | ||
635 | it->current = NULL; | ||
636 | it->bucket++; | ||
637 | } | ||
638 | else | ||
639 | { | ||
640 | it->list = eina_rbtree_iterator_prefix(it->hash_head->head); | ||
641 | ok = eina_iterator_next(it->list, (void **)(void*)&it->hash_element); | ||
642 | } | ||
643 | } | ||
644 | |||
645 | bucket = it->bucket; | ||
646 | } | ||
647 | |||
648 | if (ok == EINA_FALSE) | ||
649 | { | ||
650 | while (bucket < it->hash->size) | ||
651 | { | ||
652 | if (it->hash->buckets[bucket]) | ||
653 | { | ||
654 | it->current = | ||
655 | eina_rbtree_iterator_prefix(it->hash->buckets[bucket]); | ||
656 | ok = eina_iterator_next(it->current, (void **)(void*)&it->hash_head); | ||
657 | if (ok) | ||
658 | break; | ||
659 | |||
660 | eina_iterator_free(it->current); | ||
661 | it->current = NULL; | ||
662 | } | ||
663 | |||
664 | ++bucket; | ||
665 | } | ||
666 | if (it->list) | ||
667 | eina_iterator_free(it->list); | ||
668 | |||
669 | it->list = eina_rbtree_iterator_prefix(it->hash_head->head); | ||
670 | ok = eina_iterator_next(it->list, (void **)(void*)&it->hash_element); | ||
671 | if (bucket == it->hash->size) | ||
672 | ok = EINA_FALSE; | ||
673 | } | ||
674 | |||
675 | it->index++; | ||
676 | it->bucket = bucket; | ||
677 | |||
678 | if (ok) | ||
679 | *data = it->get_content(it); | ||
680 | |||
681 | return ok; | ||
682 | } | ||
683 | |||
684 | static void * | ||
685 | _eina_hash_iterator_get_container(Eina_Iterator_Hash *it) | ||
686 | { | ||
687 | EINA_MAGIC_CHECK_HASH_ITERATOR(it, NULL); | ||
688 | return (void *)it->hash; | ||
689 | } | ||
690 | |||
691 | static void | ||
692 | _eina_hash_iterator_free(Eina_Iterator_Hash *it) | ||
693 | { | ||
694 | EINA_MAGIC_CHECK_HASH_ITERATOR(it); | ||
695 | if (it->current) | ||
696 | eina_iterator_free(it->current); | ||
697 | |||
698 | if (it->list) | ||
699 | eina_iterator_free(it->list); | ||
700 | |||
701 | free(it); | ||
702 | } | ||
703 | |||
704 | /** | ||
705 | * @endcond | ||
706 | */ | ||
707 | |||
708 | /*============================================================================* | ||
709 | * Global * | ||
710 | *============================================================================*/ | ||
711 | |||
712 | /*============================================================================* | ||
713 | * API * | ||
714 | *============================================================================*/ | ||
715 | |||
716 | EAPI void | ||
717 | eina_hash_free_cb_set(Eina_Hash *hash, Eina_Free_Cb data_free_cb) | ||
718 | { | ||
719 | EINA_MAGIC_CHECK_HASH(hash); | ||
720 | EINA_SAFETY_ON_NULL_RETURN(hash); | ||
721 | |||
722 | hash->data_free_cb = data_free_cb; | ||
723 | } | ||
724 | |||
725 | EAPI Eina_Hash * | ||
726 | eina_hash_new(Eina_Key_Length key_length_cb, | ||
727 | Eina_Key_Cmp key_cmp_cb, | ||
728 | Eina_Key_Hash key_hash_cb, | ||
729 | Eina_Free_Cb data_free_cb, | ||
730 | int buckets_power_size) | ||
731 | { | ||
732 | /* FIXME: Use mempool. */ | ||
733 | Eina_Hash *new; | ||
734 | |||
735 | eina_error_set(0); | ||
736 | EINA_SAFETY_ON_NULL_RETURN_VAL(key_cmp_cb, NULL); | ||
737 | EINA_SAFETY_ON_NULL_RETURN_VAL(key_hash_cb, NULL); | ||
738 | EINA_SAFETY_ON_TRUE_RETURN_VAL(buckets_power_size <= 2, NULL); | ||
739 | EINA_SAFETY_ON_TRUE_RETURN_VAL(buckets_power_size >= 17, NULL); | ||
740 | |||
741 | new = malloc(sizeof (Eina_Hash)); | ||
742 | if (!new) | ||
743 | goto on_error; | ||
744 | |||
745 | EINA_MAGIC_SET(new, EINA_MAGIC_HASH); | ||
746 | |||
747 | new->key_length_cb = key_length_cb; | ||
748 | new->key_cmp_cb = key_cmp_cb; | ||
749 | new->key_hash_cb = key_hash_cb; | ||
750 | new->data_free_cb = data_free_cb; | ||
751 | new->buckets = NULL; | ||
752 | new->population = 0; | ||
753 | |||
754 | new->size = 1 << buckets_power_size; | ||
755 | new->mask = new->size - 1; | ||
756 | |||
757 | return new; | ||
758 | |||
759 | on_error: | ||
760 | eina_error_set(EINA_ERROR_OUT_OF_MEMORY); | ||
761 | return NULL; | ||
762 | } | ||
763 | |||
764 | EAPI Eina_Hash * | ||
765 | eina_hash_string_djb2_new(Eina_Free_Cb data_free_cb) | ||
766 | { | ||
767 | return eina_hash_new(EINA_KEY_LENGTH(_eina_string_key_length), | ||
768 | EINA_KEY_CMP(_eina_string_key_cmp), | ||
769 | EINA_KEY_HASH(eina_hash_djb2), | ||
770 | data_free_cb, | ||
771 | EINA_HASH_BUCKET_SIZE); | ||
772 | } | ||
773 | |||
774 | EAPI Eina_Hash * | ||
775 | eina_hash_string_superfast_new(Eina_Free_Cb data_free_cb) | ||
776 | { | ||
777 | return eina_hash_new(EINA_KEY_LENGTH(_eina_string_key_length), | ||
778 | EINA_KEY_CMP(_eina_string_key_cmp), | ||
779 | EINA_KEY_HASH(eina_hash_superfast), | ||
780 | data_free_cb, | ||
781 | EINA_HASH_BUCKET_SIZE); | ||
782 | } | ||
783 | |||
784 | EAPI Eina_Hash * | ||
785 | eina_hash_string_small_new(Eina_Free_Cb data_free_cb) | ||
786 | { | ||
787 | return eina_hash_new(EINA_KEY_LENGTH(_eina_string_key_length), | ||
788 | EINA_KEY_CMP(_eina_string_key_cmp), | ||
789 | EINA_KEY_HASH(eina_hash_superfast), | ||
790 | data_free_cb, | ||
791 | EINA_HASH_SMALL_BUCKET_SIZE); | ||
792 | } | ||
793 | |||
794 | EAPI Eina_Hash * | ||
795 | eina_hash_int32_new(Eina_Free_Cb data_free_cb) | ||
796 | { | ||
797 | return eina_hash_new(EINA_KEY_LENGTH(_eina_int32_key_length), | ||
798 | EINA_KEY_CMP(_eina_int32_key_cmp), | ||
799 | EINA_KEY_HASH(eina_hash_int32), | ||
800 | data_free_cb, | ||
801 | EINA_HASH_BUCKET_SIZE); | ||
802 | } | ||
803 | |||
804 | EAPI Eina_Hash * | ||
805 | eina_hash_int64_new(Eina_Free_Cb data_free_cb) | ||
806 | { | ||
807 | return eina_hash_new(EINA_KEY_LENGTH(_eina_int64_key_length), | ||
808 | EINA_KEY_CMP(_eina_int64_key_cmp), | ||
809 | EINA_KEY_HASH(eina_hash_int64), | ||
810 | data_free_cb, | ||
811 | EINA_HASH_BUCKET_SIZE); | ||
812 | } | ||
813 | |||
814 | EAPI Eina_Hash * | ||
815 | eina_hash_pointer_new(Eina_Free_Cb data_free_cb) | ||
816 | { | ||
817 | #ifdef __LP64__ | ||
818 | return eina_hash_new(EINA_KEY_LENGTH(_eina_int64_key_length), | ||
819 | EINA_KEY_CMP(_eina_int64_key_cmp), | ||
820 | EINA_KEY_HASH(eina_hash_int64), | ||
821 | data_free_cb, | ||
822 | EINA_HASH_BUCKET_SIZE); | ||
823 | #else | ||
824 | return eina_hash_new(EINA_KEY_LENGTH(_eina_int32_key_length), | ||
825 | EINA_KEY_CMP(_eina_int32_key_cmp), | ||
826 | EINA_KEY_HASH(eina_hash_int32), | ||
827 | data_free_cb, | ||
828 | EINA_HASH_BUCKET_SIZE); | ||
829 | #endif | ||
830 | } | ||
831 | |||
832 | EAPI Eina_Hash * | ||
833 | eina_hash_stringshared_new(Eina_Free_Cb data_free_cb) | ||
834 | { | ||
835 | return eina_hash_new(NULL, | ||
836 | EINA_KEY_CMP(_eina_stringshared_key_cmp), | ||
837 | EINA_KEY_HASH(eina_hash_superfast), | ||
838 | data_free_cb, | ||
839 | EINA_HASH_BUCKET_SIZE); | ||
840 | } | ||
841 | |||
842 | EAPI int | ||
843 | eina_hash_population(const Eina_Hash *hash) | ||
844 | { | ||
845 | if (!hash) | ||
846 | return 0; | ||
847 | |||
848 | EINA_MAGIC_CHECK_HASH(hash); | ||
849 | return hash->population; | ||
850 | } | ||
851 | |||
852 | EAPI void | ||
853 | eina_hash_free(Eina_Hash *hash) | ||
854 | { | ||
855 | int i; | ||
856 | |||
857 | EINA_MAGIC_CHECK_HASH(hash); | ||
858 | EINA_SAFETY_ON_NULL_RETURN(hash); | ||
859 | |||
860 | if (hash->buckets) | ||
861 | { | ||
862 | for (i = 0; i < hash->size; i++) | ||
863 | eina_rbtree_delete(hash->buckets[i], EINA_RBTREE_FREE_CB(_eina_hash_head_free), hash); | ||
864 | free(hash->buckets); | ||
865 | } | ||
866 | free(hash); | ||
867 | } | ||
868 | |||
869 | EAPI void | ||
870 | eina_hash_free_buckets(Eina_Hash *hash) | ||
871 | { | ||
872 | int i; | ||
873 | |||
874 | EINA_MAGIC_CHECK_HASH(hash); | ||
875 | EINA_SAFETY_ON_NULL_RETURN(hash); | ||
876 | |||
877 | if (hash->buckets) | ||
878 | { | ||
879 | for (i = 0; i < hash->size; i++) | ||
880 | eina_rbtree_delete(hash->buckets[i], | ||
881 | EINA_RBTREE_FREE_CB(_eina_hash_head_free), hash); | ||
882 | free(hash->buckets); | ||
883 | hash->buckets = NULL; | ||
884 | hash->population = 0; | ||
885 | } | ||
886 | } | ||
887 | |||
888 | EAPI Eina_Bool | ||
889 | eina_hash_add_by_hash(Eina_Hash *hash, | ||
890 | const void *key, | ||
891 | int key_length, | ||
892 | int key_hash, | ||
893 | const void *data) | ||
894 | { | ||
895 | return eina_hash_add_alloc_by_hash(hash, | ||
896 | key, | ||
897 | key_length, | ||
898 | key_length, | ||
899 | key_hash, | ||
900 | data); | ||
901 | } | ||
902 | |||
903 | EAPI Eina_Bool | ||
904 | eina_hash_direct_add_by_hash(Eina_Hash *hash, | ||
905 | const void *key, | ||
906 | int key_length, | ||
907 | int key_hash, | ||
908 | const void *data) | ||
909 | { | ||
910 | return eina_hash_add_alloc_by_hash(hash, key, key_length, 0, key_hash, data); | ||
911 | } | ||
912 | |||
913 | EAPI Eina_Bool | ||
914 | eina_hash_add(Eina_Hash *hash, const void *key, const void *data) | ||
915 | { | ||
916 | unsigned int key_length; | ||
917 | int key_hash; | ||
918 | |||
919 | EINA_MAGIC_CHECK_HASH(hash); | ||
920 | EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE); | ||
921 | EINA_SAFETY_ON_NULL_RETURN_VAL(hash->key_hash_cb, EINA_FALSE); | ||
922 | EINA_SAFETY_ON_NULL_RETURN_VAL(key, EINA_FALSE); | ||
923 | EINA_SAFETY_ON_NULL_RETURN_VAL(data, EINA_FALSE); | ||
924 | |||
925 | key_length = hash->key_length_cb ? hash->key_length_cb(key) : 0; | ||
926 | key_hash = hash->key_hash_cb(key, key_length); | ||
927 | |||
928 | return eina_hash_add_alloc_by_hash(hash, key, key_length, key_length, key_hash, data); | ||
929 | } | ||
930 | |||
931 | EAPI Eina_Bool | ||
932 | eina_hash_direct_add(Eina_Hash *hash, const void *key, const void *data) | ||
933 | { | ||
934 | int key_length; | ||
935 | int key_hash; | ||
936 | |||
937 | EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE); | ||
938 | EINA_SAFETY_ON_NULL_RETURN_VAL(hash->key_hash_cb, EINA_FALSE); | ||
939 | EINA_SAFETY_ON_NULL_RETURN_VAL(key, EINA_FALSE); | ||
940 | EINA_SAFETY_ON_NULL_RETURN_VAL(data, EINA_FALSE); | ||
941 | EINA_MAGIC_CHECK_HASH(hash); | ||
942 | |||
943 | key_length = hash->key_length_cb ? hash->key_length_cb(key) : 0; | ||
944 | key_hash = hash->key_hash_cb(key, key_length); | ||
945 | |||
946 | return eina_hash_add_alloc_by_hash(hash, key, key_length, 0, key_hash, data); | ||
947 | } | ||
948 | |||
949 | EAPI Eina_Bool | ||
950 | eina_hash_del_by_key_hash(Eina_Hash *hash, | ||
951 | const void *key, | ||
952 | int key_length, | ||
953 | int key_hash) | ||
954 | { | ||
955 | EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE); | ||
956 | EINA_SAFETY_ON_NULL_RETURN_VAL(key, EINA_FALSE); | ||
957 | |||
958 | return _eina_hash_del_by_key_hash(hash, key, key_length, key_hash, NULL); | ||
959 | } | ||
960 | |||
961 | EAPI Eina_Bool | ||
962 | eina_hash_del_by_key(Eina_Hash *hash, const void *key) | ||
963 | { | ||
964 | EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE); | ||
965 | EINA_SAFETY_ON_NULL_RETURN_VAL(key, EINA_FALSE); | ||
966 | |||
967 | return _eina_hash_del_by_key(hash, key, NULL); | ||
968 | } | ||
969 | |||
970 | EAPI Eina_Bool | ||
971 | eina_hash_del_by_data(Eina_Hash *hash, const void *data) | ||
972 | { | ||
973 | Eina_Hash_Element *hash_element; | ||
974 | Eina_Hash_Head *hash_head; | ||
975 | int key_hash; | ||
976 | |||
977 | EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE); | ||
978 | EINA_SAFETY_ON_NULL_RETURN_VAL(data, EINA_FALSE); | ||
979 | EINA_MAGIC_CHECK_HASH(hash); | ||
980 | |||
981 | hash_element = _eina_hash_find_by_data(hash, data, &key_hash, &hash_head); | ||
982 | if (!hash_element) | ||
983 | goto error; | ||
984 | |||
985 | if (hash_element->tuple.data != data) | ||
986 | goto error; | ||
987 | |||
988 | return _eina_hash_del_by_hash_el(hash, hash_element, hash_head, key_hash); | ||
989 | |||
990 | error: | ||
991 | return EINA_FALSE; | ||
992 | } | ||
993 | |||
994 | EAPI Eina_Bool | ||
995 | eina_hash_del_by_hash(Eina_Hash *hash, | ||
996 | const void *key, | ||
997 | int key_length, | ||
998 | int key_hash, | ||
999 | const void *data) | ||
1000 | { | ||
1001 | Eina_Bool ret; | ||
1002 | |||
1003 | EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE); | ||
1004 | EINA_MAGIC_CHECK_HASH(hash); | ||
1005 | |||
1006 | if (key) | ||
1007 | ret = _eina_hash_del_by_key_hash(hash, key, key_length, key_hash, data); | ||
1008 | else | ||
1009 | ret = eina_hash_del_by_data(hash, data); | ||
1010 | |||
1011 | return ret; | ||
1012 | } | ||
1013 | |||
1014 | EAPI Eina_Bool | ||
1015 | eina_hash_del(Eina_Hash *hash, const void *key, const void *data) | ||
1016 | { | ||
1017 | EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE); | ||
1018 | EINA_MAGIC_CHECK_HASH(hash); | ||
1019 | |||
1020 | if (!key) | ||
1021 | return eina_hash_del_by_data(hash, data); | ||
1022 | |||
1023 | return _eina_hash_del_by_key(hash, key, data); | ||
1024 | } | ||
1025 | |||
1026 | EAPI void * | ||
1027 | eina_hash_find_by_hash(const Eina_Hash *hash, | ||
1028 | const void *key, | ||
1029 | int key_length, | ||
1030 | int key_hash) | ||
1031 | { | ||
1032 | Eina_Hash_Head *hash_head; | ||
1033 | Eina_Hash_Element *hash_element; | ||
1034 | Eina_Hash_Tuple tuple; | ||
1035 | |||
1036 | if (!hash) | ||
1037 | return NULL; | ||
1038 | |||
1039 | EINA_SAFETY_ON_NULL_RETURN_VAL(key, NULL); | ||
1040 | EINA_MAGIC_CHECK_HASH(hash); | ||
1041 | |||
1042 | tuple.key = key; | ||
1043 | tuple.key_length = key_length; | ||
1044 | tuple.data = NULL; | ||
1045 | |||
1046 | hash_element = _eina_hash_find_by_hash(hash, &tuple, key_hash, &hash_head); | ||
1047 | if (hash_element) | ||
1048 | return hash_element->tuple.data; | ||
1049 | |||
1050 | return NULL; | ||
1051 | } | ||
1052 | |||
1053 | EAPI void * | ||
1054 | eina_hash_find(const Eina_Hash *hash, const void *key) | ||
1055 | { | ||
1056 | int key_length; | ||
1057 | int hash_num; | ||
1058 | |||
1059 | if (!hash) | ||
1060 | return NULL; | ||
1061 | |||
1062 | EINA_SAFETY_ON_NULL_RETURN_VAL(hash->key_hash_cb, NULL); | ||
1063 | EINA_SAFETY_ON_NULL_RETURN_VAL(key, NULL); | ||
1064 | EINA_MAGIC_CHECK_HASH(hash); | ||
1065 | |||
1066 | key_length = hash->key_length_cb ? hash->key_length_cb(key) : 0; | ||
1067 | hash_num = hash->key_hash_cb(key, key_length); | ||
1068 | |||
1069 | return eina_hash_find_by_hash(hash, key, key_length, hash_num); | ||
1070 | } | ||
1071 | |||
1072 | EAPI void * | ||
1073 | eina_hash_modify_by_hash(Eina_Hash *hash, | ||
1074 | const void *key, | ||
1075 | int key_length, | ||
1076 | int key_hash, | ||
1077 | const void *data) | ||
1078 | { | ||
1079 | Eina_Hash_Head *hash_head; | ||
1080 | Eina_Hash_Element *hash_element; | ||
1081 | void *old_data = NULL; | ||
1082 | Eina_Hash_Tuple tuple; | ||
1083 | |||
1084 | EINA_SAFETY_ON_NULL_RETURN_VAL(hash, NULL); | ||
1085 | EINA_SAFETY_ON_NULL_RETURN_VAL(key, NULL); | ||
1086 | EINA_SAFETY_ON_NULL_RETURN_VAL(data, NULL); | ||
1087 | EINA_MAGIC_CHECK_HASH(hash); | ||
1088 | |||
1089 | tuple.key = key; | ||
1090 | tuple.key_length = key_length; | ||
1091 | tuple.data = NULL; | ||
1092 | |||
1093 | hash_element = _eina_hash_find_by_hash(hash, &tuple, key_hash, &hash_head); | ||
1094 | if (hash_element) | ||
1095 | { | ||
1096 | old_data = hash_element->tuple.data; | ||
1097 | hash_element->tuple.data = (void *)data; | ||
1098 | } | ||
1099 | |||
1100 | return old_data; | ||
1101 | } | ||
1102 | |||
1103 | EAPI void * | ||
1104 | eina_hash_set(Eina_Hash *hash, const void *key, const void *data) | ||
1105 | { | ||
1106 | Eina_Hash_Tuple tuple; | ||
1107 | Eina_Hash_Head *hash_head; | ||
1108 | Eina_Hash_Element *hash_element; | ||
1109 | int key_length; | ||
1110 | int key_hash; | ||
1111 | |||
1112 | EINA_SAFETY_ON_NULL_RETURN_VAL(hash, NULL); | ||
1113 | EINA_SAFETY_ON_NULL_RETURN_VAL(hash->key_hash_cb, NULL); | ||
1114 | EINA_SAFETY_ON_NULL_RETURN_VAL(key, NULL); | ||
1115 | EINA_MAGIC_CHECK_HASH(hash); | ||
1116 | |||
1117 | key_length = hash->key_length_cb ? hash->key_length_cb(key) : 0; | ||
1118 | key_hash = hash->key_hash_cb(key, key_length); | ||
1119 | |||
1120 | tuple.key = key; | ||
1121 | tuple.key_length = key_length; | ||
1122 | tuple.data = NULL; | ||
1123 | |||
1124 | hash_element = _eina_hash_find_by_hash(hash, &tuple, key_hash, &hash_head); | ||
1125 | if (hash_element) | ||
1126 | { | ||
1127 | void *old_data = NULL; | ||
1128 | |||
1129 | old_data = hash_element->tuple.data; | ||
1130 | |||
1131 | if (data) | ||
1132 | { | ||
1133 | hash_element->tuple.data = (void *)data; | ||
1134 | } | ||
1135 | else | ||
1136 | { | ||
1137 | _eina_hash_del_by_hash_el(hash, hash_element, hash_head, key_hash); | ||
1138 | } | ||
1139 | |||
1140 | return old_data; | ||
1141 | } | ||
1142 | |||
1143 | if (!data) return NULL; | ||
1144 | |||
1145 | eina_hash_add_alloc_by_hash(hash, | ||
1146 | key, | ||
1147 | key_length, | ||
1148 | key_length, | ||
1149 | key_hash, | ||
1150 | data); | ||
1151 | return NULL; | ||
1152 | } | ||
1153 | EAPI void * | ||
1154 | eina_hash_modify(Eina_Hash *hash, const void *key, const void *data) | ||
1155 | { | ||
1156 | int key_length; | ||
1157 | int hash_num; | ||
1158 | |||
1159 | EINA_SAFETY_ON_NULL_RETURN_VAL(hash, NULL); | ||
1160 | EINA_SAFETY_ON_NULL_RETURN_VAL(hash->key_hash_cb, NULL); | ||
1161 | EINA_SAFETY_ON_NULL_RETURN_VAL(key, NULL); | ||
1162 | EINA_SAFETY_ON_NULL_RETURN_VAL(data, NULL); | ||
1163 | EINA_MAGIC_CHECK_HASH(hash); | ||
1164 | |||
1165 | key_length = hash->key_length_cb ? hash->key_length_cb(key) : 0; | ||
1166 | hash_num = hash->key_hash_cb(key, key_length); | ||
1167 | |||
1168 | return eina_hash_modify_by_hash(hash, key, key_length, hash_num, data); | ||
1169 | } | ||
1170 | |||
1171 | EAPI Eina_Bool | ||
1172 | eina_hash_move(Eina_Hash *hash, const void *old_key, const void *new_key) | ||
1173 | { | ||
1174 | Eina_Free_Cb hash_free_cb; | ||
1175 | const void *data; | ||
1176 | Eina_Bool result = EINA_FALSE; | ||
1177 | |||
1178 | EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE); | ||
1179 | EINA_SAFETY_ON_NULL_RETURN_VAL(hash->key_hash_cb, EINA_FALSE); | ||
1180 | EINA_SAFETY_ON_NULL_RETURN_VAL(old_key, EINA_FALSE); | ||
1181 | EINA_SAFETY_ON_NULL_RETURN_VAL(new_key, EINA_FALSE); | ||
1182 | EINA_MAGIC_CHECK_HASH(hash); | ||
1183 | |||
1184 | data = eina_hash_find(hash, old_key); | ||
1185 | if (!data) goto error; | ||
1186 | |||
1187 | hash_free_cb = hash->data_free_cb; | ||
1188 | hash->data_free_cb = NULL; | ||
1189 | |||
1190 | eina_hash_del(hash, old_key, data); | ||
1191 | result = eina_hash_add(hash, new_key, data); | ||
1192 | |||
1193 | hash->data_free_cb = hash_free_cb; | ||
1194 | |||
1195 | error: | ||
1196 | return result; | ||
1197 | } | ||
1198 | |||
1199 | /*============================================================================* | ||
1200 | * Iterator * | ||
1201 | *============================================================================*/ | ||
1202 | |||
1203 | EAPI void | ||
1204 | eina_hash_foreach(const Eina_Hash *hash, | ||
1205 | Eina_Hash_Foreach func, | ||
1206 | const void *fdata) | ||
1207 | { | ||
1208 | Eina_Iterator *it; | ||
1209 | Eina_Hash_Foreach_Data foreach; | ||
1210 | |||
1211 | EINA_MAGIC_CHECK_HASH(hash); | ||
1212 | EINA_SAFETY_ON_NULL_RETURN(hash); | ||
1213 | EINA_SAFETY_ON_NULL_RETURN(func); | ||
1214 | |||
1215 | foreach.cb = func; | ||
1216 | foreach.fdata = fdata; | ||
1217 | |||
1218 | it = eina_hash_iterator_tuple_new(hash); | ||
1219 | if (!it) | ||
1220 | return; | ||
1221 | eina_iterator_foreach(it, EINA_EACH_CB(_eina_foreach_cb), &foreach); | ||
1222 | |||
1223 | eina_iterator_free(it); | ||
1224 | } | ||
1225 | |||
1226 | EAPI Eina_Iterator * | ||
1227 | eina_hash_iterator_data_new(const Eina_Hash *hash) | ||
1228 | { | ||
1229 | Eina_Iterator_Hash *it; | ||
1230 | |||
1231 | EINA_SAFETY_ON_NULL_RETURN_VAL(hash, NULL); | ||
1232 | EINA_MAGIC_CHECK_HASH(hash); | ||
1233 | |||
1234 | eina_error_set(0); | ||
1235 | it = calloc(1, sizeof (Eina_Iterator_Hash)); | ||
1236 | if (!it) | ||
1237 | { | ||
1238 | eina_error_set(EINA_ERROR_OUT_OF_MEMORY); | ||
1239 | return NULL; | ||
1240 | } | ||
1241 | |||
1242 | it->hash = hash; | ||
1243 | it->get_content = FUNC_ITERATOR_GET_CONTENT(_eina_hash_iterator_data_get_content); | ||
1244 | |||
1245 | it->iterator.version = EINA_ITERATOR_VERSION; | ||
1246 | it->iterator.next = FUNC_ITERATOR_NEXT(_eina_hash_iterator_next); | ||
1247 | it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER( | ||
1248 | _eina_hash_iterator_get_container); | ||
1249 | it->iterator.free = FUNC_ITERATOR_FREE(_eina_hash_iterator_free); | ||
1250 | |||
1251 | EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR); | ||
1252 | EINA_MAGIC_SET(it, EINA_MAGIC_HASH_ITERATOR); | ||
1253 | |||
1254 | return &it->iterator; | ||
1255 | } | ||
1256 | |||
1257 | EAPI Eina_Iterator * | ||
1258 | eina_hash_iterator_key_new(const Eina_Hash *hash) | ||
1259 | { | ||
1260 | Eina_Iterator_Hash *it; | ||
1261 | |||
1262 | EINA_SAFETY_ON_NULL_RETURN_VAL(hash, NULL); | ||
1263 | EINA_MAGIC_CHECK_HASH(hash); | ||
1264 | |||
1265 | eina_error_set(0); | ||
1266 | it = calloc(1, sizeof (Eina_Iterator_Hash)); | ||
1267 | if (!it) | ||
1268 | { | ||
1269 | eina_error_set(EINA_ERROR_OUT_OF_MEMORY); | ||
1270 | return NULL; | ||
1271 | } | ||
1272 | |||
1273 | it->hash = hash; | ||
1274 | it->get_content = FUNC_ITERATOR_GET_CONTENT( | ||
1275 | _eina_hash_iterator_key_get_content); | ||
1276 | |||
1277 | it->iterator.version = EINA_ITERATOR_VERSION; | ||
1278 | it->iterator.next = FUNC_ITERATOR_NEXT(_eina_hash_iterator_next); | ||
1279 | it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER( | ||
1280 | _eina_hash_iterator_get_container); | ||
1281 | it->iterator.free = FUNC_ITERATOR_FREE(_eina_hash_iterator_free); | ||
1282 | |||
1283 | EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR); | ||
1284 | EINA_MAGIC_SET(it, EINA_MAGIC_HASH_ITERATOR); | ||
1285 | |||
1286 | return &it->iterator; | ||
1287 | } | ||
1288 | |||
1289 | EAPI Eina_Iterator * | ||
1290 | eina_hash_iterator_tuple_new(const Eina_Hash *hash) | ||
1291 | { | ||
1292 | Eina_Iterator_Hash *it; | ||
1293 | |||
1294 | EINA_SAFETY_ON_NULL_RETURN_VAL(hash, NULL); | ||
1295 | EINA_MAGIC_CHECK_HASH(hash); | ||
1296 | |||
1297 | eina_error_set(0); | ||
1298 | it = calloc(1, sizeof (Eina_Iterator_Hash)); | ||
1299 | if (!it) | ||
1300 | { | ||
1301 | eina_error_set(EINA_ERROR_OUT_OF_MEMORY); | ||
1302 | return NULL; | ||
1303 | } | ||
1304 | |||
1305 | it->hash = hash; | ||
1306 | it->get_content = FUNC_ITERATOR_GET_CONTENT( | ||
1307 | _eina_hash_iterator_tuple_get_content); | ||
1308 | |||
1309 | it->iterator.version = EINA_ITERATOR_VERSION; | ||
1310 | it->iterator.next = FUNC_ITERATOR_NEXT(_eina_hash_iterator_next); | ||
1311 | it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER( | ||
1312 | _eina_hash_iterator_get_container); | ||
1313 | it->iterator.free = FUNC_ITERATOR_FREE(_eina_hash_iterator_free); | ||
1314 | |||
1315 | EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR); | ||
1316 | EINA_MAGIC_SET(it, EINA_MAGIC_HASH_ITERATOR); | ||
1317 | |||
1318 | return &it->iterator; | ||
1319 | } | ||
1320 | |||
1321 | /* Common hash functions */ | ||
1322 | |||
1323 | /* Paul Hsieh (http://www.azillionmonkeys.com/qed/hash.html) | ||
1324 | used by WebCore (http://webkit.org/blog/8/hashtables-part-2/) */ | ||
1325 | EAPI int | ||
1326 | eina_hash_superfast(const char *key, int len) | ||
1327 | { | ||
1328 | int hash = len, tmp; | ||
1329 | int rem; | ||
1330 | |||
1331 | rem = len & 3; | ||
1332 | len >>= 2; | ||
1333 | |||
1334 | /* Main loop */ | ||
1335 | for (; len > 0; len--) | ||
1336 | { | ||
1337 | hash += get16bits(key); | ||
1338 | tmp = (get16bits(key + 2) << 11) ^ hash; | ||
1339 | hash = (hash << 16) ^ tmp; | ||
1340 | key += 2 * sizeof (uint16_t); | ||
1341 | hash += hash >> 11; | ||
1342 | } | ||
1343 | |||
1344 | /* Handle end cases */ | ||
1345 | switch (rem) | ||
1346 | { | ||
1347 | case 3: | ||
1348 | hash += get16bits(key); | ||
1349 | hash ^= hash << 16; | ||
1350 | hash ^= key[sizeof (uint16_t)] << 18; | ||
1351 | hash += hash >> 11; | ||
1352 | break; | ||
1353 | |||
1354 | case 2: | ||
1355 | hash += get16bits(key); | ||
1356 | hash ^= hash << 11; | ||
1357 | hash += hash >> 17; | ||
1358 | break; | ||
1359 | |||
1360 | case 1: | ||
1361 | hash += *key; | ||
1362 | hash ^= hash << 10; | ||
1363 | hash += hash >> 1; | ||
1364 | } | ||
1365 | |||
1366 | /* Force "avalanching" of final 127 bits */ | ||
1367 | hash ^= hash << 3; | ||
1368 | hash += hash >> 5; | ||
1369 | hash ^= hash << 4; | ||
1370 | hash += hash >> 17; | ||
1371 | hash ^= hash << 25; | ||
1372 | hash += hash >> 6; | ||
1373 | |||
1374 | return hash; | ||
1375 | } | ||