aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/libraries/eina/src/lib/eina_hash.c
diff options
context:
space:
mode:
Diffstat (limited to 'libraries/eina/src/lib/eina_hash.c')
-rw-r--r--libraries/eina/src/lib/eina_hash.c1377
1 files changed, 0 insertions, 1377 deletions
diff --git a/libraries/eina/src/lib/eina_hash.c b/libraries/eina/src/lib/eina_hash.c
deleted file mode 100644
index 5196894..0000000
--- a/libraries/eina/src/lib/eina_hash.c
+++ /dev/null
@@ -1,1377 +0,0 @@
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
73typedef struct _Eina_Hash_Head Eina_Hash_Head;
74typedef struct _Eina_Hash_Element Eina_Hash_Element;
75typedef struct _Eina_Hash_Foreach_Data Eina_Hash_Foreach_Data;
76typedef struct _Eina_Iterator_Hash Eina_Iterator_Hash;
77typedef struct _Eina_Hash_Each Eina_Hash_Each;
78
79struct _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
95struct _Eina_Hash_Head
96{
97 EINA_RBTREE;
98 int hash;
99
100 Eina_Rbtree *head;
101};
102
103struct _Eina_Hash_Element
104{
105 EINA_RBTREE;
106 Eina_Hash_Tuple tuple;
107 Eina_Bool begin : 1;
108};
109
110struct _Eina_Hash_Foreach_Data
111{
112 Eina_Hash_Foreach cb;
113 const void *fdata;
114};
115
116typedef 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
120struct _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
138struct _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
156static 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
165static 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
176static 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
195static 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
211static inline Eina_Bool
212eina_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
304on_error:
305 eina_error_set(error);
306 return EINA_FALSE;
307}
308
309static 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
334static 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
367static 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
403static 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
413static 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
420static 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
454static 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
483static 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
503static 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
512static 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
519static 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
526static unsigned int
527_eina_int32_key_length(__UNUSED__ const uint32_t *key)
528{
529 return 4;
530}
531
532static 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
539static unsigned int
540_eina_int64_key_length(__UNUSED__ const uint32_t *key)
541{
542 return 8;
543}
544
545static 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
552static 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
563static 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
578static 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
593static 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
608static 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
684static 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
691static 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
716EAPI void
717eina_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
725EAPI Eina_Hash *
726eina_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
759on_error:
760 eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
761 return NULL;
762}
763
764EAPI Eina_Hash *
765eina_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
774EAPI Eina_Hash *
775eina_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
784EAPI Eina_Hash *
785eina_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
794EAPI Eina_Hash *
795eina_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
804EAPI Eina_Hash *
805eina_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
814EAPI Eina_Hash *
815eina_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
832EAPI Eina_Hash *
833eina_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
842EAPI int
843eina_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
852EAPI void
853eina_hash_free(Eina_Hash *hash)
854{
855 int i;
856
857 if (!hash) return ;
858
859 EINA_MAGIC_CHECK_HASH(hash);
860
861 if (hash->buckets)
862 {
863 for (i = 0; i < hash->size; i++)
864 eina_rbtree_delete(hash->buckets[i], EINA_RBTREE_FREE_CB(_eina_hash_head_free), hash);
865 free(hash->buckets);
866 }
867 free(hash);
868}
869
870EAPI void
871eina_hash_free_buckets(Eina_Hash *hash)
872{
873 int i;
874
875 if (!hash) return ;
876
877 EINA_MAGIC_CHECK_HASH(hash);
878
879 if (hash->buckets)
880 {
881 for (i = 0; i < hash->size; i++)
882 eina_rbtree_delete(hash->buckets[i],
883 EINA_RBTREE_FREE_CB(_eina_hash_head_free), hash);
884 free(hash->buckets);
885 hash->buckets = NULL;
886 hash->population = 0;
887 }
888}
889
890EAPI Eina_Bool
891eina_hash_add_by_hash(Eina_Hash *hash,
892 const void *key,
893 int key_length,
894 int key_hash,
895 const void *data)
896{
897 return eina_hash_add_alloc_by_hash(hash,
898 key,
899 key_length,
900 key_length,
901 key_hash,
902 data);
903}
904
905EAPI Eina_Bool
906eina_hash_direct_add_by_hash(Eina_Hash *hash,
907 const void *key,
908 int key_length,
909 int key_hash,
910 const void *data)
911{
912 return eina_hash_add_alloc_by_hash(hash, key, key_length, 0, key_hash, data);
913}
914
915EAPI Eina_Bool
916eina_hash_add(Eina_Hash *hash, const void *key, const void *data)
917{
918 unsigned int key_length;
919 int key_hash;
920
921 EINA_MAGIC_CHECK_HASH(hash);
922 EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE);
923 EINA_SAFETY_ON_NULL_RETURN_VAL(hash->key_hash_cb, EINA_FALSE);
924 EINA_SAFETY_ON_NULL_RETURN_VAL(key, EINA_FALSE);
925 EINA_SAFETY_ON_NULL_RETURN_VAL(data, EINA_FALSE);
926
927 key_length = hash->key_length_cb ? hash->key_length_cb(key) : 0;
928 key_hash = hash->key_hash_cb(key, key_length);
929
930 return eina_hash_add_alloc_by_hash(hash, key, key_length, key_length, key_hash, data);
931}
932
933EAPI Eina_Bool
934eina_hash_direct_add(Eina_Hash *hash, const void *key, const void *data)
935{
936 int key_length;
937 int key_hash;
938
939 EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE);
940 EINA_SAFETY_ON_NULL_RETURN_VAL(hash->key_hash_cb, EINA_FALSE);
941 EINA_SAFETY_ON_NULL_RETURN_VAL(key, EINA_FALSE);
942 EINA_SAFETY_ON_NULL_RETURN_VAL(data, EINA_FALSE);
943 EINA_MAGIC_CHECK_HASH(hash);
944
945 key_length = hash->key_length_cb ? hash->key_length_cb(key) : 0;
946 key_hash = hash->key_hash_cb(key, key_length);
947
948 return eina_hash_add_alloc_by_hash(hash, key, key_length, 0, key_hash, data);
949}
950
951EAPI Eina_Bool
952eina_hash_del_by_key_hash(Eina_Hash *hash,
953 const void *key,
954 int key_length,
955 int key_hash)
956{
957 EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE);
958 EINA_SAFETY_ON_NULL_RETURN_VAL(key, EINA_FALSE);
959
960 return _eina_hash_del_by_key_hash(hash, key, key_length, key_hash, NULL);
961}
962
963EAPI Eina_Bool
964eina_hash_del_by_key(Eina_Hash *hash, const void *key)
965{
966 EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE);
967 EINA_SAFETY_ON_NULL_RETURN_VAL(key, EINA_FALSE);
968
969 return _eina_hash_del_by_key(hash, key, NULL);
970}
971
972EAPI Eina_Bool
973eina_hash_del_by_data(Eina_Hash *hash, const void *data)
974{
975 Eina_Hash_Element *hash_element;
976 Eina_Hash_Head *hash_head;
977 int key_hash;
978
979 EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE);
980 EINA_SAFETY_ON_NULL_RETURN_VAL(data, EINA_FALSE);
981 EINA_MAGIC_CHECK_HASH(hash);
982
983 hash_element = _eina_hash_find_by_data(hash, data, &key_hash, &hash_head);
984 if (!hash_element)
985 goto error;
986
987 if (hash_element->tuple.data != data)
988 goto error;
989
990 return _eina_hash_del_by_hash_el(hash, hash_element, hash_head, key_hash);
991
992error:
993 return EINA_FALSE;
994}
995
996EAPI Eina_Bool
997eina_hash_del_by_hash(Eina_Hash *hash,
998 const void *key,
999 int key_length,
1000 int key_hash,
1001 const void *data)
1002{
1003 Eina_Bool ret;
1004
1005 EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE);
1006 EINA_MAGIC_CHECK_HASH(hash);
1007
1008 if (key)
1009 ret = _eina_hash_del_by_key_hash(hash, key, key_length, key_hash, data);
1010 else
1011 ret = eina_hash_del_by_data(hash, data);
1012
1013 return ret;
1014}
1015
1016EAPI Eina_Bool
1017eina_hash_del(Eina_Hash *hash, const void *key, const void *data)
1018{
1019 EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE);
1020 EINA_MAGIC_CHECK_HASH(hash);
1021
1022 if (!key)
1023 return eina_hash_del_by_data(hash, data);
1024
1025 return _eina_hash_del_by_key(hash, key, data);
1026}
1027
1028EAPI void *
1029eina_hash_find_by_hash(const Eina_Hash *hash,
1030 const void *key,
1031 int key_length,
1032 int key_hash)
1033{
1034 Eina_Hash_Head *hash_head;
1035 Eina_Hash_Element *hash_element;
1036 Eina_Hash_Tuple tuple;
1037
1038 if (!hash)
1039 return NULL;
1040
1041 EINA_SAFETY_ON_NULL_RETURN_VAL(key, NULL);
1042 EINA_MAGIC_CHECK_HASH(hash);
1043
1044 tuple.key = key;
1045 tuple.key_length = key_length;
1046 tuple.data = NULL;
1047
1048 hash_element = _eina_hash_find_by_hash(hash, &tuple, key_hash, &hash_head);
1049 if (hash_element)
1050 return hash_element->tuple.data;
1051
1052 return NULL;
1053}
1054
1055EAPI void *
1056eina_hash_find(const Eina_Hash *hash, const void *key)
1057{
1058 int key_length;
1059 int hash_num;
1060
1061 if (!hash)
1062 return NULL;
1063
1064 EINA_SAFETY_ON_NULL_RETURN_VAL(hash->key_hash_cb, NULL);
1065 EINA_SAFETY_ON_NULL_RETURN_VAL(key, NULL);
1066 EINA_MAGIC_CHECK_HASH(hash);
1067
1068 key_length = hash->key_length_cb ? hash->key_length_cb(key) : 0;
1069 hash_num = hash->key_hash_cb(key, key_length);
1070
1071 return eina_hash_find_by_hash(hash, key, key_length, hash_num);
1072}
1073
1074EAPI void *
1075eina_hash_modify_by_hash(Eina_Hash *hash,
1076 const void *key,
1077 int key_length,
1078 int key_hash,
1079 const void *data)
1080{
1081 Eina_Hash_Head *hash_head;
1082 Eina_Hash_Element *hash_element;
1083 void *old_data = NULL;
1084 Eina_Hash_Tuple tuple;
1085
1086 EINA_SAFETY_ON_NULL_RETURN_VAL(hash, NULL);
1087 EINA_SAFETY_ON_NULL_RETURN_VAL(key, NULL);
1088 EINA_SAFETY_ON_NULL_RETURN_VAL(data, NULL);
1089 EINA_MAGIC_CHECK_HASH(hash);
1090
1091 tuple.key = key;
1092 tuple.key_length = key_length;
1093 tuple.data = NULL;
1094
1095 hash_element = _eina_hash_find_by_hash(hash, &tuple, key_hash, &hash_head);
1096 if (hash_element)
1097 {
1098 old_data = hash_element->tuple.data;
1099 hash_element->tuple.data = (void *)data;
1100 }
1101
1102 return old_data;
1103}
1104
1105EAPI void *
1106eina_hash_set(Eina_Hash *hash, const void *key, const void *data)
1107{
1108 Eina_Hash_Tuple tuple;
1109 Eina_Hash_Head *hash_head;
1110 Eina_Hash_Element *hash_element;
1111 int key_length;
1112 int key_hash;
1113
1114 EINA_SAFETY_ON_NULL_RETURN_VAL(hash, NULL);
1115 EINA_SAFETY_ON_NULL_RETURN_VAL(hash->key_hash_cb, NULL);
1116 EINA_SAFETY_ON_NULL_RETURN_VAL(key, NULL);
1117 EINA_MAGIC_CHECK_HASH(hash);
1118
1119 key_length = hash->key_length_cb ? hash->key_length_cb(key) : 0;
1120 key_hash = hash->key_hash_cb(key, key_length);
1121
1122 tuple.key = key;
1123 tuple.key_length = key_length;
1124 tuple.data = NULL;
1125
1126 hash_element = _eina_hash_find_by_hash(hash, &tuple, key_hash, &hash_head);
1127 if (hash_element)
1128 {
1129 void *old_data = NULL;
1130
1131 old_data = hash_element->tuple.data;
1132
1133 if (data)
1134 {
1135 hash_element->tuple.data = (void *)data;
1136 }
1137 else
1138 {
1139 _eina_hash_del_by_hash_el(hash, hash_element, hash_head, key_hash);
1140 }
1141
1142 return old_data;
1143 }
1144
1145 if (!data) return NULL;
1146
1147 eina_hash_add_alloc_by_hash(hash,
1148 key,
1149 key_length,
1150 key_length,
1151 key_hash,
1152 data);
1153 return NULL;
1154}
1155EAPI void *
1156eina_hash_modify(Eina_Hash *hash, const void *key, const void *data)
1157{
1158 int key_length;
1159 int hash_num;
1160
1161 EINA_SAFETY_ON_NULL_RETURN_VAL(hash, NULL);
1162 EINA_SAFETY_ON_NULL_RETURN_VAL(hash->key_hash_cb, NULL);
1163 EINA_SAFETY_ON_NULL_RETURN_VAL(key, NULL);
1164 EINA_SAFETY_ON_NULL_RETURN_VAL(data, NULL);
1165 EINA_MAGIC_CHECK_HASH(hash);
1166
1167 key_length = hash->key_length_cb ? hash->key_length_cb(key) : 0;
1168 hash_num = hash->key_hash_cb(key, key_length);
1169
1170 return eina_hash_modify_by_hash(hash, key, key_length, hash_num, data);
1171}
1172
1173EAPI Eina_Bool
1174eina_hash_move(Eina_Hash *hash, const void *old_key, const void *new_key)
1175{
1176 Eina_Free_Cb hash_free_cb;
1177 const void *data;
1178 Eina_Bool result = EINA_FALSE;
1179
1180 EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE);
1181 EINA_SAFETY_ON_NULL_RETURN_VAL(hash->key_hash_cb, EINA_FALSE);
1182 EINA_SAFETY_ON_NULL_RETURN_VAL(old_key, EINA_FALSE);
1183 EINA_SAFETY_ON_NULL_RETURN_VAL(new_key, EINA_FALSE);
1184 EINA_MAGIC_CHECK_HASH(hash);
1185
1186 data = eina_hash_find(hash, old_key);
1187 if (!data) goto error;
1188
1189 hash_free_cb = hash->data_free_cb;
1190 hash->data_free_cb = NULL;
1191
1192 eina_hash_del(hash, old_key, data);
1193 result = eina_hash_add(hash, new_key, data);
1194
1195 hash->data_free_cb = hash_free_cb;
1196
1197error:
1198 return result;
1199}
1200
1201/*============================================================================*
1202* Iterator *
1203*============================================================================*/
1204
1205EAPI void
1206eina_hash_foreach(const Eina_Hash *hash,
1207 Eina_Hash_Foreach func,
1208 const void *fdata)
1209{
1210 Eina_Iterator *it;
1211 Eina_Hash_Foreach_Data foreach;
1212
1213 EINA_MAGIC_CHECK_HASH(hash);
1214 EINA_SAFETY_ON_NULL_RETURN(hash);
1215 EINA_SAFETY_ON_NULL_RETURN(func);
1216
1217 foreach.cb = func;
1218 foreach.fdata = fdata;
1219
1220 it = eina_hash_iterator_tuple_new(hash);
1221 if (!it)
1222 return;
1223 eina_iterator_foreach(it, EINA_EACH_CB(_eina_foreach_cb), &foreach);
1224
1225 eina_iterator_free(it);
1226}
1227
1228EAPI Eina_Iterator *
1229eina_hash_iterator_data_new(const Eina_Hash *hash)
1230{
1231 Eina_Iterator_Hash *it;
1232
1233 EINA_SAFETY_ON_NULL_RETURN_VAL(hash, NULL);
1234 EINA_MAGIC_CHECK_HASH(hash);
1235
1236 eina_error_set(0);
1237 it = calloc(1, sizeof (Eina_Iterator_Hash));
1238 if (!it)
1239 {
1240 eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
1241 return NULL;
1242 }
1243
1244 it->hash = hash;
1245 it->get_content = FUNC_ITERATOR_GET_CONTENT(_eina_hash_iterator_data_get_content);
1246
1247 it->iterator.version = EINA_ITERATOR_VERSION;
1248 it->iterator.next = FUNC_ITERATOR_NEXT(_eina_hash_iterator_next);
1249 it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER(
1250 _eina_hash_iterator_get_container);
1251 it->iterator.free = FUNC_ITERATOR_FREE(_eina_hash_iterator_free);
1252
1253 EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR);
1254 EINA_MAGIC_SET(it, EINA_MAGIC_HASH_ITERATOR);
1255
1256 return &it->iterator;
1257}
1258
1259EAPI Eina_Iterator *
1260eina_hash_iterator_key_new(const Eina_Hash *hash)
1261{
1262 Eina_Iterator_Hash *it;
1263
1264 EINA_SAFETY_ON_NULL_RETURN_VAL(hash, NULL);
1265 EINA_MAGIC_CHECK_HASH(hash);
1266
1267 eina_error_set(0);
1268 it = calloc(1, sizeof (Eina_Iterator_Hash));
1269 if (!it)
1270 {
1271 eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
1272 return NULL;
1273 }
1274
1275 it->hash = hash;
1276 it->get_content = FUNC_ITERATOR_GET_CONTENT(
1277 _eina_hash_iterator_key_get_content);
1278
1279 it->iterator.version = EINA_ITERATOR_VERSION;
1280 it->iterator.next = FUNC_ITERATOR_NEXT(_eina_hash_iterator_next);
1281 it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER(
1282 _eina_hash_iterator_get_container);
1283 it->iterator.free = FUNC_ITERATOR_FREE(_eina_hash_iterator_free);
1284
1285 EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR);
1286 EINA_MAGIC_SET(it, EINA_MAGIC_HASH_ITERATOR);
1287
1288 return &it->iterator;
1289}
1290
1291EAPI Eina_Iterator *
1292eina_hash_iterator_tuple_new(const Eina_Hash *hash)
1293{
1294 Eina_Iterator_Hash *it;
1295
1296 EINA_SAFETY_ON_NULL_RETURN_VAL(hash, NULL);
1297 EINA_MAGIC_CHECK_HASH(hash);
1298
1299 eina_error_set(0);
1300 it = calloc(1, sizeof (Eina_Iterator_Hash));
1301 if (!it)
1302 {
1303 eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
1304 return NULL;
1305 }
1306
1307 it->hash = hash;
1308 it->get_content = FUNC_ITERATOR_GET_CONTENT(
1309 _eina_hash_iterator_tuple_get_content);
1310
1311 it->iterator.version = EINA_ITERATOR_VERSION;
1312 it->iterator.next = FUNC_ITERATOR_NEXT(_eina_hash_iterator_next);
1313 it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER(
1314 _eina_hash_iterator_get_container);
1315 it->iterator.free = FUNC_ITERATOR_FREE(_eina_hash_iterator_free);
1316
1317 EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR);
1318 EINA_MAGIC_SET(it, EINA_MAGIC_HASH_ITERATOR);
1319
1320 return &it->iterator;
1321}
1322
1323/* Common hash functions */
1324
1325/* Paul Hsieh (http://www.azillionmonkeys.com/qed/hash.html)
1326 used by WebCore (http://webkit.org/blog/8/hashtables-part-2/) */
1327EAPI int
1328eina_hash_superfast(const char *key, int len)
1329{
1330 int hash = len, tmp;
1331 int rem;
1332
1333 rem = len & 3;
1334 len >>= 2;
1335
1336 /* Main loop */
1337 for (; len > 0; len--)
1338 {
1339 hash += get16bits(key);
1340 tmp = (get16bits(key + 2) << 11) ^ hash;
1341 hash = (hash << 16) ^ tmp;
1342 key += 2 * sizeof (uint16_t);
1343 hash += hash >> 11;
1344 }
1345
1346 /* Handle end cases */
1347 switch (rem)
1348 {
1349 case 3:
1350 hash += get16bits(key);
1351 hash ^= hash << 16;
1352 hash ^= key[sizeof (uint16_t)] << 18;
1353 hash += hash >> 11;
1354 break;
1355
1356 case 2:
1357 hash += get16bits(key);
1358 hash ^= hash << 11;
1359 hash += hash >> 17;
1360 break;
1361
1362 case 1:
1363 hash += *key;
1364 hash ^= hash << 10;
1365 hash += hash >> 1;
1366 }
1367
1368 /* Force "avalanching" of final 127 bits */
1369 hash ^= hash << 3;
1370 hash += hash >> 5;
1371 hash ^= hash << 4;
1372 hash += hash >> 17;
1373 hash ^= hash << 25;
1374 hash += hash >> 6;
1375
1376 return hash;
1377}
generated by cgit v1.1 at 2024-08-30 19:12:59 +0000