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
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.
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.
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/>.
33 #include "eina_config.h"
34 #include "eina_private.h"
35 #include "eina_rbtree.h"
36 #include "eina_error.h"
38 /* undefs EINA_ARG_NONULL() so NULL checks are not compiled out! */
39 #include "eina_safety_checks.h"
40 #include "eina_hash.h"
42 /*============================================================================*
44 *============================================================================*/
50 #define EINA_MAGIC_CHECK_HASH(d) \
52 if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_HASH)) \
53 EINA_MAGIC_FAIL(d, EINA_MAGIC_HASH); \
56 #define EINA_MAGIC_CHECK_HASH_ITERATOR(d, ...) \
58 if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_HASH_ITERATOR)) \
60 EINA_MAGIC_FAIL(d, EINA_MAGIC_HASH_ITERATOR); \
65 #define EINA_HASH_BUCKET_SIZE 8
66 #define EINA_HASH_SMALL_BUCKET_SIZE 5
68 #define EINA_HASH_RBTREE_MASK 0xFFF
70 typedef struct _Eina_Hash_Head Eina_Hash_Head;
71 typedef struct _Eina_Hash_El Eina_Hash_El;
72 typedef struct _Eina_Hash_Foreach_Data Eina_Hash_Foreach_Data;
73 typedef struct _Eina_Iterator_Hash Eina_Iterator_Hash;
74 typedef struct _Eina_Hash_Each Eina_Hash_Each;
78 Eina_Key_Length key_length_cb;
79 Eina_Key_Cmp key_cmp_cb;
80 Eina_Key_Hash key_hash_cb;
81 Eina_Free_Cb data_free_cb;
83 Eina_Rbtree **buckets;
92 struct _Eina_Hash_Head
103 Eina_Hash_Tuple tuple;
107 struct _Eina_Hash_Foreach_Data
109 Eina_Hash_Foreach cb;
113 typedef void *(*Eina_Iterator_Get_Content_Callback)(Eina_Iterator_Hash *it);
114 #define FUNC_ITERATOR_GET_CONTENT(Function) ((Eina_Iterator_Get_Content_Callback)Function)
116 struct _Eina_Iterator_Hash
118 Eina_Iterator iterator;
120 Eina_Iterator_Get_Content_Callback get_content;
121 const Eina_Hash *hash;
123 Eina_Iterator *current;
134 struct _Eina_Hash_Each
137 const Eina_Hash_El *el;
142 #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
143 || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__)
144 # define get16bits(d) (*((const uint16_t *) (d)))
147 #if !defined (get16bits)
148 # define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
149 +(uint32_t)(((const uint8_t *)(d))[0]) )
153 _eina_hash_hash_rbtree_cmp_hash(const Eina_Hash_Head *eh, const int *hash, __UNUSED__ int key_length, __UNUSED__ void *data)
155 return eh->hash - *hash;
158 static Eina_Rbtree_Direction
159 _eina_hash_hash_rbtree_cmp_node(const Eina_Hash_Head *left, const Eina_Hash_Head *right, __UNUSED__ void *data)
161 if (left->hash - right->hash < 0)
162 return EINA_RBTREE_LEFT;
163 return EINA_RBTREE_RIGHT;
167 _eina_hash_key_rbtree_cmp_key_data(const Eina_Hash_El *el, const Eina_Hash_Tuple *tuple, __UNUSED__ unsigned int key_length, Eina_Key_Cmp cmp)
171 result = cmp(el->tuple.key, el->tuple.key_length, tuple->key, tuple->key_length);
173 if (result == 0 && tuple->data && tuple->data != el->tuple.data)
178 static Eina_Rbtree_Direction
179 _eina_hash_key_rbtree_cmp_node(const Eina_Hash_El *left, const Eina_Hash_El *right, Eina_Key_Cmp cmp)
183 result = cmp(left->tuple.key, left->tuple.key_length,
184 right->tuple.key, right->tuple.key_length);
187 return EINA_RBTREE_LEFT;
188 return EINA_RBTREE_RIGHT;
191 static inline Eina_Bool
192 eina_hash_add_alloc_by_hash(Eina_Hash *hash,
193 const void *key, int key_length, int alloc_length,
197 Eina_Hash_El *el = NULL;
199 Eina_Error error = 0;
202 EINA_MAGIC_CHECK_HASH(hash);
203 EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE);
204 EINA_SAFETY_ON_NULL_RETURN_VAL(key, EINA_FALSE);
205 EINA_SAFETY_ON_NULL_RETURN_VAL(data, EINA_FALSE);
206 error = EINA_ERROR_OUT_OF_MEMORY;
208 /* Apply eina mask to hash. */
209 hash_num = key_hash & hash->mask;
210 key_hash &= EINA_HASH_RBTREE_MASK;
214 hash->buckets = malloc(sizeof (Eina_Rbtree*) * hash->size);
215 memset(hash->buckets, 0, sizeof (Eina_Rbtree*) * hash->size);
221 /* Look up for head node. */
222 eh = (Eina_Hash_Head*) eina_rbtree_inline_lookup(hash->buckets[hash_num],
224 EINA_RBTREE_CMP_KEY_CB(_eina_hash_hash_rbtree_cmp_hash), NULL);
229 /* If not found allocate it and a element. */
230 eh = malloc(sizeof (Eina_Hash_Head) + sizeof (Eina_Hash_El) + alloc_length);
231 if (!eh) goto on_error;
235 hash->buckets[hash_num] = eina_rbtree_inline_insert(hash->buckets[hash_num], EINA_RBTREE_GET(eh),
236 EINA_RBTREE_CMP_NODE_CB(_eina_hash_hash_rbtree_cmp_node), NULL);
238 el = (Eina_Hash_El*) (eh + 1);
239 el->begin = EINA_TRUE;
245 Alloc every needed things
246 (No more lookup as we expect to support more than one item for one key).
248 el = malloc(sizeof (Eina_Hash_El) + alloc_length);
249 if (!el) goto on_error;
250 el->begin = EINA_FALSE;
253 /* Setup the element */
254 el->tuple.key_length = key_length;
255 el->tuple.data = (void *) data;
256 if (alloc_length > 0)
258 el->tuple.key = (char *) (el + 1);
259 memcpy((char *) el->tuple.key, key, alloc_length);
266 /* add the new element to the hash. */
267 eh->head = eina_rbtree_inline_insert(eh->head, EINA_RBTREE_GET(el),
268 EINA_RBTREE_CMP_NODE_CB(_eina_hash_key_rbtree_cmp_node), (const void *)hash->key_cmp_cb);
273 eina_error_set(error);
278 _eina_hash_rbtree_each(__UNUSED__ const Eina_Rbtree *container, const Eina_Hash_Head *eh, Eina_Hash_Each *data)
282 Eina_Bool found = EINA_TRUE;
284 it = eina_rbtree_iterator_prefix(eh->head);
285 EINA_ITERATOR_FOREACH(it, el)
287 if (el->tuple.data == data->data)
290 data->eh = (Eina_Hash_Head*) eh;
296 eina_iterator_free(it);
300 static inline Eina_Hash_El *
301 _eina_hash_find_by_hash(const Eina_Hash *hash, Eina_Hash_Tuple *tuple, int key_hash, Eina_Hash_Head **eh)
304 int rb_hash = key_hash & EINA_HASH_RBTREE_MASK;
306 key_hash &= hash->mask;
308 if (!hash->buckets) return NULL;
310 *eh = (Eina_Hash_Head*) eina_rbtree_inline_lookup(hash->buckets[key_hash],
312 EINA_RBTREE_CMP_KEY_CB(_eina_hash_hash_rbtree_cmp_hash), NULL);
313 if (!*eh) return NULL;
315 el = (Eina_Hash_El*) eina_rbtree_inline_lookup((*eh)->head,
317 EINA_RBTREE_CMP_KEY_CB(_eina_hash_key_rbtree_cmp_key_data), (const void *)hash->key_cmp_cb);
322 static inline Eina_Hash_El *
323 _eina_hash_find_by_data(const Eina_Hash *hash, const void *data, int *key_hash, Eina_Hash_Head **eh)
329 if (!hash->buckets) return NULL;
334 for (hash_num = 0; hash_num < hash->size; hash_num++)
336 if (!hash->buckets[hash_num])
338 it = eina_rbtree_iterator_prefix(hash->buckets[hash_num]);
339 eina_iterator_foreach(it, EINA_EACH(_eina_hash_rbtree_each), &each);
340 eina_iterator_free(it);
344 *key_hash = hash_num;
346 return (Eina_Hash_El*) each.el;
354 _eina_hash_el_free(Eina_Hash_El *el, Eina_Hash *hash)
356 if (hash->data_free_cb)
357 hash->data_free_cb(el->tuple.data);
358 if (el->begin == EINA_FALSE) free(el);
362 _eina_hash_head_free(Eina_Hash_Head *eh, Eina_Hash *hash)
364 eina_rbtree_delete(eh->head, EINA_RBTREE_FREE_CB(_eina_hash_el_free), hash);
369 _eina_hash_del_by_hash_el(Eina_Hash *hash, Eina_Hash_El *el, Eina_Hash_Head *eh, int key_hash)
371 eh->head = eina_rbtree_inline_remove(eh->head, EINA_RBTREE_GET(el), EINA_RBTREE_CMP_NODE_CB(_eina_hash_key_rbtree_cmp_node), (const void *)hash->key_cmp_cb);
372 _eina_hash_el_free(el, hash);
376 key_hash &= hash->mask;
378 hash->buckets[key_hash] = eina_rbtree_inline_remove(hash->buckets[key_hash], EINA_RBTREE_GET(eh), EINA_RBTREE_CMP_NODE_CB(_eina_hash_hash_rbtree_cmp_node), NULL);
383 if (hash->population == 0)
386 hash->buckets = NULL;
393 _eina_hash_del_by_key_hash(Eina_Hash *hash, const void *key, int key_length, int key_hash, const void *data)
397 Eina_Hash_Tuple tuple;
399 EINA_MAGIC_CHECK_HASH(hash);
400 EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE);
401 EINA_SAFETY_ON_NULL_RETURN_VAL(key, EINA_FALSE);
403 if (!hash->buckets) return EINA_FALSE;
405 tuple.key = (void *) key;
406 tuple.key_length = key_length;
407 tuple.data = (void *) data;
409 el = _eina_hash_find_by_hash(hash, &tuple, key_hash, &eh);
410 if (!el) return EINA_FALSE;
411 return _eina_hash_del_by_hash_el(hash, el, eh, key_hash);
415 _eina_hash_del_by_key(Eina_Hash *hash, const void *key, const void *data)
417 int key_length, key_hash;
419 EINA_MAGIC_CHECK_HASH(hash);
420 if (!hash) return EINA_FALSE;
421 if (!key) return EINA_FALSE;
422 if (!hash->buckets) return EINA_FALSE;
424 key_length = hash->key_length_cb ? hash->key_length_cb(key) : 0;
425 key_hash = hash->key_hash_cb(key, key_length);
426 return _eina_hash_del_by_key_hash(hash, key, key_length, key_hash, data);
430 _eina_string_key_length(const char *key)
433 return (int)strlen(key) + 1;
437 _eina_string_key_cmp(const char *key1, __UNUSED__ int key1_length,
438 const char *key2, __UNUSED__ int key2_length)
440 return strcmp(key1, key2);
444 _eina_stringshared_key_cmp(const char *key1, __UNUSED__ int key1_length,
445 const char *key2, __UNUSED__ int key2_length)
451 _eina_int32_key_length(__UNUSED__ const uint32_t *key)
457 _eina_int32_key_cmp(const uint32_t *key1, __UNUSED__ int key1_length,
458 const uint32_t *key2, __UNUSED__ int key2_length)
460 return *key1 - *key2;
464 _eina_int64_key_length(__UNUSED__ const uint32_t *key)
470 _eina_int64_key_cmp(const uint64_t *key1, __UNUSED__ int key1_length,
471 const uint64_t *key2, __UNUSED__ int key2_length)
473 return *key1 - *key2;
477 _eina_foreach_cb(const Eina_Hash *hash, Eina_Hash_Tuple *data, Eina_Hash_Foreach_Data *fdata)
479 return fdata->cb((Eina_Hash *) hash, data->key, data->data, (void*) fdata->fdata);
483 _eina_hash_iterator_data_get_content(Eina_Iterator_Hash *it)
487 EINA_MAGIC_CHECK_HASH_ITERATOR(it, NULL);
491 if (!stuff) return NULL;
492 return stuff->tuple.data;
496 _eina_hash_iterator_key_get_content(Eina_Iterator_Hash *it)
500 EINA_MAGIC_CHECK_HASH_ITERATOR(it, NULL);
504 if (!stuff) return NULL;
505 return (void *) stuff->tuple.key;
508 static Eina_Hash_Tuple *
509 _eina_hash_iterator_tuple_get_content(Eina_Iterator_Hash *it)
513 EINA_MAGIC_CHECK_HASH_ITERATOR(it, NULL);
517 if (!stuff) return NULL;
518 return &stuff->tuple;
522 _eina_hash_iterator_next(Eina_Iterator_Hash *it, void **data)
527 if (!(it->index < it->hash->population)) return EINA_FALSE;
528 if (it->current == NULL)
536 ok = eina_iterator_next(it->list, (void**) &it->el);
539 eina_iterator_free(it->list);
542 ok = eina_iterator_next(it->current, (void**) &it->eh);
545 eina_iterator_free(it->current);
551 it->list = eina_rbtree_iterator_prefix(it->eh->head);
552 ok = eina_iterator_next(it->list, (void**) &it->el);
559 if (ok == EINA_FALSE)
561 while (bucket < it->hash->size)
563 if (it->hash->buckets[bucket] != NULL)
565 it->current = eina_rbtree_iterator_prefix(it->hash->buckets[bucket]);
566 ok = eina_iterator_next(it->current, (void**) &it->eh);
568 eina_iterator_free(it->current);
573 if (it->list) eina_iterator_free(it->list);
574 it->list = eina_rbtree_iterator_prefix(it->eh->head);
575 ok = eina_iterator_next(it->list, (void**) &it->el);
576 if (bucket == it->hash->size) ok = EINA_FALSE;
583 *data = it->get_content(it);
589 _eina_hash_iterator_get_container(Eina_Iterator_Hash *it)
591 EINA_MAGIC_CHECK_HASH_ITERATOR(it, NULL);
592 return (void *) it->hash;
596 _eina_hash_iterator_free(Eina_Iterator_Hash *it)
598 EINA_MAGIC_CHECK_HASH_ITERATOR(it);
599 if (it->current) eina_iterator_free(it->current);
600 if (it->list) eina_iterator_free(it->list);
608 /*============================================================================*
610 *============================================================================*/
612 /*============================================================================*
614 *============================================================================*/
617 * @addtogroup Eina_Hash_Group Hash Table
619 * @brief give a small description here : what it is for, what it does
622 * Hash API. Give some hints about the use (functions that must be
623 * used like init / shutdown), general use, etc... Give also a link to
626 * @section hashtable_algo Algorithm
628 * Give here the algorithm used in the implementation
630 * @section hashtable_perf Performance
632 * Give some hints about performance if it is possible, and an image !
634 * @section hashtable_tutorial Tutorial
636 * Here is a fantastic tutorial about our hash table
642 eina_hash_new(Eina_Key_Length key_length_cb,
643 Eina_Key_Cmp key_cmp_cb,
644 Eina_Key_Hash key_hash_cb,
645 Eina_Free_Cb data_free_cb,
646 int buckets_power_size)
648 /* FIXME: Use mempool. */
652 EINA_SAFETY_ON_NULL_RETURN_VAL(key_cmp_cb, NULL);
653 EINA_SAFETY_ON_NULL_RETURN_VAL(key_hash_cb, NULL);
654 EINA_SAFETY_ON_TRUE_RETURN_VAL(buckets_power_size < 3, NULL);
655 EINA_SAFETY_ON_TRUE_RETURN_VAL(buckets_power_size > 16, NULL);
657 new = malloc(sizeof (Eina_Hash));
658 if (!new) goto on_error;
660 new->key_length_cb = key_length_cb;
661 new->key_cmp_cb = key_cmp_cb;
662 new->key_hash_cb = key_hash_cb;
663 new->data_free_cb = data_free_cb;
667 new->size = 1 << buckets_power_size;
668 new->mask = new->size - 1;
670 EINA_MAGIC_SET(new, EINA_MAGIC_HASH);
675 eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
680 eina_hash_string_djb2_new(Eina_Free_Cb data_free_cb)
682 return eina_hash_new(EINA_KEY_LENGTH(_eina_string_key_length),
683 EINA_KEY_CMP(_eina_string_key_cmp),
684 EINA_KEY_HASH(eina_hash_djb2),
686 EINA_HASH_BUCKET_SIZE);
690 * @brief Create a new hash for use with strings.
691 * @param data_free_cb The function to call on values when the hash table is freed
692 * @return The @ref Eina_Hash object, or @c NULL on error
693 * Use to create a new hash for use with strings.
694 * NOTE: If your hash is created by this, you CAN look up values with pointers other
695 * than the original key pointer that was used to add a value.
698 eina_hash_string_superfast_new(Eina_Free_Cb data_free_cb)
700 return eina_hash_new(EINA_KEY_LENGTH(_eina_string_key_length),
701 EINA_KEY_CMP(_eina_string_key_cmp),
702 EINA_KEY_HASH(eina_hash_superfast),
704 EINA_HASH_BUCKET_SIZE);
708 * @brief Create a new hash for use with strings. If you are unsure of which hash creation
709 * function to use, use this one.
710 * @param data_free_cb The function to call on values when the hash table is freed
711 * @return The @ref Eina_Hash object, or @c NULL on error
712 * Use to create a new hash with small bucket size for use with strings.
713 * If you are unsure of which hash creation function to use, you should probably use this one.
714 * NOTE: If your hash is created by this, you CAN look up values with pointers other
715 * than the original key pointer that was used to add a value.
718 eina_hash_string_small_new(Eina_Free_Cb data_free_cb)
720 return eina_hash_new(EINA_KEY_LENGTH(_eina_string_key_length),
721 EINA_KEY_CMP(_eina_string_key_cmp),
722 EINA_KEY_HASH(eina_hash_superfast),
724 EINA_HASH_SMALL_BUCKET_SIZE);
728 eina_hash_int32_new(Eina_Free_Cb data_free_cb)
730 return eina_hash_new(EINA_KEY_LENGTH(_eina_int32_key_length),
731 EINA_KEY_CMP(_eina_int32_key_cmp),
732 EINA_KEY_HASH(eina_hash_int32),
734 EINA_HASH_BUCKET_SIZE);
738 eina_hash_int64_new(Eina_Free_Cb data_free_cb)
740 return eina_hash_new(EINA_KEY_LENGTH(_eina_int64_key_length),
741 EINA_KEY_CMP(_eina_int64_key_cmp),
742 EINA_KEY_HASH(eina_hash_int64),
744 EINA_HASH_BUCKET_SIZE);
748 eina_hash_pointer_new(Eina_Free_Cb data_free_cb)
751 return eina_hash_new(EINA_KEY_LENGTH(_eina_int64_key_length),
752 EINA_KEY_CMP(_eina_int64_key_cmp),
753 EINA_KEY_HASH(eina_hash_int64),
755 EINA_HASH_BUCKET_SIZE);
757 return eina_hash_new(EINA_KEY_LENGTH(_eina_int32_key_length),
758 EINA_KEY_CMP(_eina_int32_key_cmp),
759 EINA_KEY_HASH(eina_hash_int32),
761 EINA_HASH_BUCKET_SIZE);
765 * @brief Create a new hash optimized for stringshared values.
766 * @param data_free_cb The function to call on values when the hash table is freed
767 * @return The @ref Eina_Hash object, or @c NULL on error
768 * Use to create a new hash optimized for stringshared values.
769 * NOTE: If your hash is created by this, you CANNOT look up values with pointers not
770 * equal to the original key pointer that was used to add a value.
771 * The following code will NOT work with this type of hash:
773 * extern Eina_Hash *hash;
774 * extern const char *value;
775 * const char *a = eina_stringshare_add("key");
777 * eina_hash_add(hash, a, value);
778 * eina_hash_find(hash, "key")
782 eina_hash_stringshared_new(Eina_Free_Cb data_free_cb)
784 return eina_hash_new(NULL,
785 EINA_KEY_CMP(_eina_stringshared_key_cmp),
786 EINA_KEY_HASH(eina_hash_superfast),
788 EINA_HASH_BUCKET_SIZE);
792 * @brief Returns the number of entires in the hash table.
793 * @param hash The given hash table.
794 * @return The number of entries in the hash table, @c 0 on error
795 * Returns the number of entires in the hash table.
798 eina_hash_population(const Eina_Hash *hash)
802 EINA_MAGIC_CHECK_HASH(hash);
803 return hash->population;
807 * Calls @ref Eina_Free_Cb (if one was specified at time of creation) on all hash table
808 * buckets, frees the buckets, then frees the hash table
809 * @param hash The hash table to be freed
811 * This function frees up all the memory allocated to storing the specified
812 * hash table pointed to by @p hash. If no data_free_cb has been passed to the
813 * hash at creation time, any entries in the table that the program
814 * has no more pointers for elsewhere may now be lost, so this should only be
815 * called if the program has already freed any allocated data in the hash table
816 * or has the pointers for data in the table stored elsewhere as well.
820 * extern Eina_Hash *hash;
822 * eina_hash_free(hash);
827 eina_hash_free(Eina_Hash *hash)
831 EINA_MAGIC_CHECK_HASH(hash);
832 EINA_SAFETY_ON_NULL_RETURN(hash);
836 for (i = 0; i < hash->size; i++)
837 eina_rbtree_delete(hash->buckets[i], EINA_RBTREE_FREE_CB(_eina_hash_head_free), hash);
844 * Calls @ref Eina_Free_Cb (if one was specified at time of creation) on all hash table buckets,
845 * then frees the buckets.
846 * @param hash The hash table to free buckets on
848 * Frees all memory allocated for hash table buckets. Note that the bucket value is not freed
849 * unless an @ref Eina_Free_Cb was specified at creation time.
850 * @see Noooo they be stealin' my bucket!
853 eina_hash_free_buckets(Eina_Hash *hash)
857 EINA_MAGIC_CHECK_HASH(hash);
858 EINA_SAFETY_ON_NULL_RETURN(hash);
862 for (i = 0; i < hash->size; i++)
863 eina_rbtree_delete(hash->buckets[i], EINA_RBTREE_FREE_CB(_eina_hash_head_free), hash);
865 hash->buckets = NULL;
866 hash->population = 0;
871 * Adds an entry to the given hash table.
873 * @p key is expected to be a unique string within the hash table.
874 * Otherwise, you cannot be sure which inserted data pointer will be
875 * accessed with @ref eina_hash_find , and removed with
876 * @ref eina_hash_del .
878 * @p key_hash is expected to always match @p key. Otherwise, you
879 * cannot be sure to find it again with @ref eina_hash_find_by_hash.
881 * Key strings are case sensitive.
883 * @ref eina_error_get should be used to determine if an
884 * allocation error occurred during this function.
886 * @param hash The given hash table. Can be @c NULL.
887 * @param key A unique key. Can be @c NULL.
888 * @param key_length Should be the length of @p key (don't forget to count '\\0' for string).
889 * @param key_hash The hash that will always match key.
890 * @param data Data to associate with the string given by @p key.
891 * @return Will return EINA_FALSE if an error occured, and EINA_TRUE if every
895 eina_hash_add_by_hash(Eina_Hash *hash,
896 const void *key, int key_length, int key_hash,
899 return eina_hash_add_alloc_by_hash(hash, key, key_length, key_length, key_hash, data);
903 * Adds an entry to the given hash table and does not duplicate the string key.
905 * @p key is expected to be a unique string within the hash table.
906 * Otherwise, you cannot be sure which inserted data pointer will be
907 * accessed with @ref eina_hash_find , and removed with
908 * @ref eina_hash_del . This call does not make a copy of the key so it must
909 * be a string constant or stored elsewhere (in the object being added) etc.
911 * @p key_hash is expected to always match @p key. Otherwise, you
912 * cannot be sure to find it again with @ref eina_hash_find_by_hash.
914 * Key strings are case sensitive.
916 * @ref eina_error_get should be used to determine if an
917 * allocation error occurred during this function.
919 * @param hash The given hash table. Can be @c NULL.
920 * @param key A unique key. Can be @c NULL.
921 * @param key_length Should be the length of @p key (don't forget to count '\\0' for string).
922 * @param key_hash The hash that will always match key.
923 * @param data Data to associate with the string given by @p key.
924 * @return Will return EINA_FALSE if an error occured, and EINA_TRUE if every
928 eina_hash_direct_add_by_hash(Eina_Hash *hash,
929 const void *key, int key_length, int key_hash,
932 return eina_hash_add_alloc_by_hash(hash, key, key_length, 0, key_hash, data);
936 * Adds an entry to the given hash table.
938 * @p key is expected to be unique within the hash table. Key uniqueness varies depending
939 * on the type of @p hash: a stringshared @ref Eina_Hash need only have unique pointers for
940 * keys, but the strings in the pointers may be identical. All other hash types require
941 * the strings themselves to be unique. Failure to use sufficient uniqueness will result in
942 * unexpected results when inserting data pointers accessed with @ref eina_hash_find ,
943 * and removed with @ref eina_hash_del .
945 * Key strings are case sensitive.
947 * @ref eina_error_get() should be used to determine if an
948 * allocation error occurred during this function.
950 * @param hash The given hash table. Can be @c NULL.
951 * @param key A unique key. Can be @c NULL.
952 * @param data Data to associate with the string given by @p key.
953 * @return Will return EINA_FALSE if an error occured, and EINA_TRUE if every
957 eina_hash_add(Eina_Hash *hash, const void *key, const void *data)
959 unsigned int key_length;
962 EINA_MAGIC_CHECK_HASH(hash);
963 EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE);
964 EINA_SAFETY_ON_NULL_RETURN_VAL(hash->key_hash_cb, EINA_FALSE);
965 EINA_SAFETY_ON_NULL_RETURN_VAL(key, EINA_FALSE);
966 EINA_SAFETY_ON_NULL_RETURN_VAL(data, EINA_FALSE);
968 key_length = hash->key_length_cb ? hash->key_length_cb(key) : 0;
969 key_hash = hash->key_hash_cb(key, key_length);
971 return eina_hash_add_by_hash(hash, key, key_length, key_hash, data);
975 * Adds an entry to the given hash table but does not duplicate the string key.
977 * @p key is expected to be unique within the hash table. Key uniqueness varies depending
978 * on the type of @p hash: a stringshared @ref Eina_Hash need only have unique pointers for
979 * keys, but the strings in the pointers may be identical. All other hash types require
980 * the strings themselves to be unique. Failure to use sufficient uniqueness will result in
981 * unexpected results when inserting data pointers accessed with @ref eina_hash_find ,
982 * and removed with @ref eina_hash_del . This call does not make a copy
983 * of the key so it must be a string constant or stored elsewhere (in the object
986 * Key strings are case sensitive.
988 * @ref eina_error_get() should be used to determine if an
989 * allocation error occurred during this function.
991 * @param hash The given hash table. Can be @c NULL.
992 * @param key A unique key. Can be @c NULL.
993 * @param data Data to associate with the string given by @p key.
994 * @return Will return EINA_FALSE if an error occured, and EINA_TRUE if every
998 eina_hash_direct_add(Eina_Hash *hash, const void *key, const void *data)
1003 EINA_MAGIC_CHECK_HASH(hash);
1004 EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE);
1005 EINA_SAFETY_ON_NULL_RETURN_VAL(hash->key_hash_cb, EINA_FALSE);
1006 EINA_SAFETY_ON_NULL_RETURN_VAL(key, EINA_FALSE);
1007 EINA_SAFETY_ON_NULL_RETURN_VAL(data, EINA_FALSE);
1009 key_length = hash->key_length_cb ? hash->key_length_cb(key) : 0;
1010 key_hash = hash->key_hash_cb(key, key_length);
1012 return eina_hash_direct_add_by_hash(hash, key, key_length, key_hash, data);
1016 * Removes the entry identified by @p key and @p key_hash from the given
1019 * @param hash The given hash table.
1020 * @param key The key. Cannot be @c NULL.
1021 * @param key_length Should be the length of @p key (don't forget to count '\\0' for string).
1022 * @param key_hash The hash that always match the key.
1023 * @return Will return EINA_FALSE if an error occured, and EINA_TRUE if every
1026 * @note if you don't have the key_hash, use eina_hash_del_by_key() instead.
1027 * @note if you don't have the key, use eina_hash_del_by_data() instead.
1030 eina_hash_del_by_key_hash(Eina_Hash *hash, const void *key, int key_length, int key_hash)
1032 EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE);
1033 EINA_SAFETY_ON_NULL_RETURN_VAL(key, EINA_FALSE);
1034 return _eina_hash_del_by_key_hash(hash, key, key_length, key_hash, NULL);
1038 * Removes the entry identified by @p key from the given hash table.
1040 * This version will calculate key length and hash by using functions
1041 * provided to hash creation function.
1043 * @param hash The given hash table.
1044 * @param key The key. Cannot be @c NULL.
1045 * @return Will return EINA_FALSE if an error occured, and EINA_TRUE if every
1048 * @note if you already have the key_hash, use eina_hash_del_by_key_hash() instead.
1049 * @note if you don't have the key, use eina_hash_del_by_data() instead.
1052 eina_hash_del_by_key(Eina_Hash *hash, const void *key)
1054 EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE);
1055 EINA_SAFETY_ON_NULL_RETURN_VAL(key, EINA_FALSE);
1056 return _eina_hash_del_by_key(hash, key, NULL);
1060 * Removes the entry identified by @p data from the given hash table.
1062 * This version is slow since there is no quick access to nodes based on data.
1064 * @param hash The given hash table.
1065 * @param data The data value to search and remove.
1066 * @return Will return EINA_FALSE if an error occured, and EINA_TRUE if every
1069 * @note if you already have the key, use eina_hash_del_by_key() or eina_hash_del_by_key_hash() instead.
1072 eina_hash_del_by_data(Eina_Hash *hash, const void *data)
1078 EINA_MAGIC_CHECK_HASH(hash);
1079 EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE);
1080 EINA_SAFETY_ON_NULL_RETURN_VAL(data, EINA_FALSE);
1082 el = _eina_hash_find_by_data(hash, data, &key_hash, &eh);
1083 if (!el) return EINA_FALSE;
1084 if (el->tuple.data != data) return EINA_FALSE;
1085 return _eina_hash_del_by_hash_el(hash, el, eh, key_hash);
1089 * Removes the entry identified by @p key and @p key_hash or @p data from the given
1092 * If @p key is @c NULL, then @p data is used to find a match to
1095 * @param hash The given hash table.
1096 * @param key The key. Can be @c NULL.
1097 * @param key_length Should be the length of @p key (don't forget to count '\\0' for string).
1098 * @param key_hash The hash that always match the key. Ignored if @p key is @c NULL.
1099 * @param data The data pointer to remove if @p key is @c NULL.
1100 * Otherwise, not required and can be @c NULL.
1101 * @return Will return EINA_FALSE if an error occured, and EINA_TRUE if every
1104 * @note if you know you already have the key, use eina_hash_del_by_key_hash(),
1105 * if you know you don't have the key, use eina_hash_del_by_data()
1109 eina_hash_del_by_hash(Eina_Hash *hash, const void *key, int key_length, int key_hash, const void *data)
1111 EINA_MAGIC_CHECK_HASH(hash);
1112 EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE);
1113 if (key) return _eina_hash_del_by_key_hash(hash, key, key_length, key_hash, data);
1114 else return eina_hash_del_by_data(hash, data);
1118 * Removes the entry identified by @p key or @p data from the given
1121 * If @p key is @c NULL, then @p data is used to find a match to
1124 * @param hash The given hash table.
1125 * @param key The key. Can be @c NULL.
1126 * @param data The data pointer to remove if @p key is @c NULL.
1127 * Otherwise, not required and can be @c NULL.
1128 * @return Will return EINA_FALSE if an error occured, and EINA_TRUE if every
1131 * @note if you know you already have the key, use
1132 * eina_hash_del_by_key() or eina_hash_del_by_key_hash(). If you
1133 * know you don't have the key, use eina_hash_del_by_data()
1137 eina_hash_del(Eina_Hash *hash, const void *key, const void *data)
1139 EINA_MAGIC_CHECK_HASH(hash);
1140 EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE);
1141 if (key) return _eina_hash_del_by_key(hash, key, data);
1142 else return eina_hash_del_by_data(hash, data);
1146 * Retrieves a specific entry in the given hash table.
1147 * @param hash The given hash table.
1148 * @param key The key of the entry to find.
1149 * @param key_length Should be the length of @p key (don't forget to count '\\0' for string).
1150 * @param key_hash The hash that always match the key. Ignored if @p key is @c NULL.
1151 * @return The data pointer for the stored entry, or @c NULL if not
1155 eina_hash_find_by_hash(const Eina_Hash *hash, const void *key, int key_length, int key_hash)
1159 Eina_Hash_Tuple tuple;
1161 if (!hash) return NULL;
1163 EINA_MAGIC_CHECK_HASH(hash);
1164 EINA_SAFETY_ON_NULL_RETURN_VAL(key, NULL);
1167 tuple.key_length = key_length;
1170 el = _eina_hash_find_by_hash(hash, &tuple, key_hash, &eh);
1171 if (el) return el->tuple.data;
1176 * Retrieves a specific entry in the given hash table.
1177 * @param hash The given hash table.
1178 * @param key The key of the entry to find.
1179 * @return The data pointer for the stored entry, or @c NULL if not
1183 eina_hash_find(const Eina_Hash *hash, const void *key)
1188 if (!hash) return NULL;
1190 EINA_MAGIC_CHECK_HASH(hash);
1191 EINA_SAFETY_ON_NULL_RETURN_VAL(hash->key_hash_cb, NULL);
1192 EINA_SAFETY_ON_NULL_RETURN_VAL(key, NULL);
1194 key_length = hash->key_length_cb ? hash->key_length_cb(key) : 0;
1195 hash_num = hash->key_hash_cb(key, key_length);
1197 return eina_hash_find_by_hash(hash, key, key_length, hash_num);
1201 * Modifies the entry pointer at the specified key and returns the old entry
1202 * @param hash The given hash table.
1203 * @param key The key of the entry to modify.
1204 * @param key_length Should be the length of @p key (don't forget to count '\\0' for string).
1205 * @param key_hash The hash that always match the key. Ignored if @p key is @c NULL.
1206 * @param data The data to replace the old entry, if it exists.
1207 * @return The data pointer for the old stored entry, or @c NULL if not
1208 * found. If an existing entry is not found, nothing is added to the
1212 eina_hash_modify_by_hash(Eina_Hash *hash, const void *key, int key_length, int key_hash, const void *data)
1216 void *old_data = NULL;
1217 Eina_Hash_Tuple tuple;
1219 EINA_MAGIC_CHECK_HASH(hash);
1220 EINA_SAFETY_ON_NULL_RETURN_VAL(hash, NULL);
1221 EINA_SAFETY_ON_NULL_RETURN_VAL(key, NULL);
1222 EINA_SAFETY_ON_NULL_RETURN_VAL(data, NULL);
1225 tuple.key_length = key_length;
1228 el = _eina_hash_find_by_hash(hash, &tuple, key_hash, &eh);
1231 old_data = el->tuple.data;
1232 el->tuple.data = (void *) data;
1239 * Modifies the entry pointer at the specified key and returns the old entry
1240 * @param hash The given hash table.
1241 * @param key The key of the entry to modify.
1242 * @param data The data to replace the old entry, if it exists.
1243 * @return The data pointer for the old stored entry, or @c NULL if not
1244 * found. If an existing entry is not found, nothing is added to the
1248 eina_hash_modify(Eina_Hash *hash, const void *key, const void *data)
1253 EINA_MAGIC_CHECK_HASH(hash);
1254 EINA_SAFETY_ON_NULL_RETURN_VAL(hash, NULL);
1255 EINA_SAFETY_ON_NULL_RETURN_VAL(hash->key_hash_cb, NULL);
1256 EINA_SAFETY_ON_NULL_RETURN_VAL(key, NULL);
1257 EINA_SAFETY_ON_NULL_RETURN_VAL(data, NULL);
1259 key_length = hash->key_length_cb ? hash->key_length_cb(key) : 0;
1260 hash_num = hash->key_hash_cb(key, key_length);
1262 return eina_hash_modify_by_hash(hash, key, key_length, hash_num, data);
1265 /*============================================================================*
1267 *============================================================================*/
1270 * Call a function on every member stored in the hash table
1271 * @param hash The hash table whose members will be walked
1272 * @param func The function to call on each parameter
1273 * @param fdata The data pointer to pass to the function being called
1275 * This function goes through every entry in the hash table @p hash and calls
1276 * the function @p func on each member. The function should NOT modify the
1277 * hash table contents if it returns 1. IF the hash table contents are
1278 * modified by this function or the function wishes to stop processing it must
1279 * return 0, otherwise return 1 to keep processing.
1283 * extern Eina_Hash *hash;
1285 * Eina_Bool hash_fn(const Eina_Hash *hash, const void *key, void *data, void *fdata)
1287 * printf("Func data: %s, Hash entry: %s / %p\n", fdata, (const char *)key, data);
1291 * int main(int argc, char **argv)
1293 * char *hash_fn_data;
1295 * hash_fn_data = strdup("Hello World");
1296 * eina_hash_foreach(hash, hash_fn, hash_fn_data);
1297 * free(hash_fn_data);
1302 eina_hash_foreach(const Eina_Hash *hash,
1303 Eina_Hash_Foreach func,
1307 Eina_Hash_Foreach_Data foreach;
1309 EINA_MAGIC_CHECK_HASH(hash);
1310 EINA_SAFETY_ON_NULL_RETURN(hash);
1311 EINA_SAFETY_ON_NULL_RETURN(func);
1314 foreach.fdata = fdata;
1316 it = eina_hash_iterator_tuple_new(hash);
1319 eina_iterator_foreach(it, EINA_EACH(_eina_foreach_cb), &foreach);
1320 eina_iterator_free(it);
1324 * @brief Returned a new iterator asociated to hash data.
1326 * @param hash The hash.
1327 * @return A new iterator.
1329 * This function returns a newly allocated iterator associated to @p
1330 * hash. If @p hash is not populated, this function still returns a
1331 * valid iterator that will always return false on
1332 * eina_iterator_next(), thus keeping API sane.
1334 * If the memory can not be allocated, NULL is returned and
1335 * #EINA_ERROR_OUT_OF_MEMORY is set. Otherwise, a valid iterator is
1338 * @warning if the hash structure changes then the iterator becomes
1339 * invalid! That is, if you add or remove items this iterator
1340 * behavior is undefined and your program may crash!
1342 EAPI Eina_Iterator *
1343 eina_hash_iterator_data_new(const Eina_Hash *hash)
1345 Eina_Iterator_Hash *it;
1347 EINA_MAGIC_CHECK_HASH(hash);
1348 EINA_SAFETY_ON_NULL_RETURN_VAL(hash, NULL);
1351 it = calloc(1, sizeof (Eina_Iterator_Hash));
1353 eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
1358 it->get_content = FUNC_ITERATOR_GET_CONTENT(_eina_hash_iterator_data_get_content);
1360 it->iterator.next = FUNC_ITERATOR_NEXT(_eina_hash_iterator_next);
1361 it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER(_eina_hash_iterator_get_container);
1362 it->iterator.free = FUNC_ITERATOR_FREE(_eina_hash_iterator_free);
1364 EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR);
1365 EINA_MAGIC_SET(it, EINA_MAGIC_HASH_ITERATOR);
1367 return &it->iterator;
1371 * @brief Returned a new iterator asociated to hash keys.
1373 * @param hash The hash.
1374 * @return A new iterator.
1376 * This function returns a newly allocated iterator associated to @p
1377 * hash. If @p hash is not populated, this function still returns a
1378 * valid iterator that will always return false on
1379 * eina_iterator_next(), thus keeping API sane.
1381 * If the memory can not be allocated, NULL is returned and
1382 * #EINA_ERROR_OUT_OF_MEMORY is set. Otherwise, a valid iterator is
1385 * @warning if the hash structure changes then the iterator becomes
1386 * invalid! That is, if you add or remove items this iterator
1387 * behavior is undefined and your program may crash!
1389 EAPI Eina_Iterator *
1390 eina_hash_iterator_key_new(const Eina_Hash *hash)
1392 Eina_Iterator_Hash *it;
1394 EINA_MAGIC_CHECK_HASH(hash);
1395 EINA_SAFETY_ON_NULL_RETURN_VAL(hash, NULL);
1398 it = calloc(1, sizeof (Eina_Iterator_Hash));
1400 eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
1405 it->get_content = FUNC_ITERATOR_GET_CONTENT(_eina_hash_iterator_key_get_content);
1407 it->iterator.next = FUNC_ITERATOR_NEXT(_eina_hash_iterator_next);
1408 it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER(_eina_hash_iterator_get_container);
1409 it->iterator.free = FUNC_ITERATOR_FREE(_eina_hash_iterator_free);
1411 EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR);
1412 EINA_MAGIC_SET(it, EINA_MAGIC_HASH_ITERATOR);
1414 return &it->iterator;
1418 * @brief Returned a new iterator asociated to hash keys and data.
1420 * @param hash The hash.
1421 * @return A new iterator.
1423 * This function returns a newly allocated iterator associated to @p
1424 * hash. If @p hash is not populated, this function still returns a
1425 * valid iterator that will always return false on
1426 * eina_iterator_next(), thus keeping API sane.
1428 * If the memory can not be allocated, NULL is returned and
1429 * #EINA_ERROR_OUT_OF_MEMORY is set. Otherwise, a valid iterator is
1432 * @note iterator data will provide values as Eina_Hash_Tuple that should not
1435 * @warning if the hash structure changes then the iterator becomes
1436 * invalid! That is, if you add or remove items this iterator
1437 * behavior is undefined and your program may crash!
1439 EAPI Eina_Iterator *
1440 eina_hash_iterator_tuple_new(const Eina_Hash *hash)
1442 Eina_Iterator_Hash *it;
1444 EINA_MAGIC_CHECK_HASH(hash);
1445 EINA_SAFETY_ON_NULL_RETURN_VAL(hash, NULL);
1448 it = calloc(1, sizeof (Eina_Iterator_Hash));
1450 eina_error_set(EINA_ERROR_OUT_OF_MEMORY);
1455 it->get_content = FUNC_ITERATOR_GET_CONTENT(_eina_hash_iterator_tuple_get_content);
1457 it->iterator.next = FUNC_ITERATOR_NEXT(_eina_hash_iterator_next);
1458 it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER(_eina_hash_iterator_get_container);
1459 it->iterator.free = FUNC_ITERATOR_FREE(_eina_hash_iterator_free);
1461 EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR);
1462 EINA_MAGIC_SET(it, EINA_MAGIC_HASH_ITERATOR);
1464 return &it->iterator;
1467 /* Common hash functions */
1469 /* Paul Hsieh (http://www.azillionmonkeys.com/qed/hash.html)
1470 used by WebCore (http://webkit.org/blog/8/hashtables-part-2/) */
1472 eina_hash_superfast(const char *key, int len)
1474 int hash = len, tmp;
1481 for ( ;len > 0; len--)
1483 hash += get16bits(key);
1484 tmp = (get16bits(key + 2) << 11) ^ hash;
1485 hash = (hash << 16) ^ tmp;
1486 key += 2 * sizeof (uint16_t);
1490 /* Handle end cases */
1494 hash += get16bits(key);
1496 hash ^= key[sizeof (uint16_t)] << 18;
1500 hash += get16bits(key);
1510 /* Force "avalanching" of final 127 bits */