Hash Table
[Containers]
give a small description here : what it is for, what it does , etc. More...
Data Structures | |
struct | _Eina_Hash_Tuple |
Defines | |
#define | EINA_KEY_LENGTH(Function) ((Eina_Key_Length)Function) |
#define | EINA_KEY_CMP(Function) ((Eina_Key_Cmp)Function) |
#define | EINA_KEY_HASH(Function) ((Eina_Key_Hash)Function) |
Typedefs | |
typedef struct _Eina_Hash | Eina_Hash |
typedef struct _Eina_Hash_Tuple | Eina_Hash_Tuple |
typedef unsigned int(* | Eina_Key_Length )(const void *key) |
typedef int(* | Eina_Key_Cmp )(const void *key1, int key1_length, const void *key2, int key2_length) |
typedef int(* | Eina_Key_Hash )(const void *key, int key_length) |
typedef Eina_Bool(* | Eina_Hash_Foreach )(const Eina_Hash *hash, const void *key, void *data, void *fdata) |
Functions | |
EAPI int | eina_hash_init (void) |
Initialize the hash table module. | |
EAPI int | eina_hash_shutdown (void) |
Shut down the hash table module. | |
EAPI Eina_Hash * | eina_hash_new (Eina_Key_Length key_length_cb, Eina_Key_Cmp key_cmp_cb, Eina_Key_Hash key_hash_cb, Eina_Free_Cb data_free_cb, int buckets_power_size) EINA_MALLOC EINA_WARN_UNUSED_RESULT EINA_ARG_NONNULL(1 |
EAPI Eina_Hash EAPI Eina_Hash * | eina_hash_string_djb2_new (Eina_Free_Cb data_free_cb) |
EAPI Eina_Hash * | eina_hash_string_superfast_new (Eina_Free_Cb data_free_cb) |
EAPI Eina_Hash * | eina_hash_string_small_new (Eina_Free_Cb data_free_cb) |
EAPI Eina_Hash * | eina_hash_int32_new (Eina_Free_Cb data_free_cb) |
EAPI Eina_Hash * | eina_hash_int64_new (Eina_Free_Cb data_free_cb) |
EAPI Eina_Hash * | eina_hash_pointer_new (Eina_Free_Cb data_free_cb) |
EAPI Eina_Hash * | eina_hash_stringshared_new (Eina_Free_Cb data_free_cb) |
EAPI Eina_Bool | eina_hash_add (Eina_Hash *hash, const void *key, const void *data) |
Adds an entry to the given hash table. | |
EAPI Eina_Bool EAPI Eina_Bool | eina_hash_direct_add (Eina_Hash *hash, const void *key, const void *data) |
Adds an entry to the given hash table and does not duplicate the string key. | |
EAPI Eina_Bool EAPI Eina_Bool EAPI Eina_Bool | eina_hash_del (Eina_Hash *hash, const void *key, const void *data) |
Removes the entry identified by key or data from the given hash table. | |
EAPI void * | eina_hash_find (const Eina_Hash *hash, const void *key) |
Retrieves a specific entry in the given hash table. | |
EAPI void *EAPI void * | eina_hash_modify (Eina_Hash *hash, const void *key, const void *data) |
Modifies the entry pointer at the specified key and returns the old entry. | |
EAPI void *EAPI void EAPI void | eina_hash_free (Eina_Hash *hash) |
Free an entire hash table. | |
EAPI int | eina_hash_population (const Eina_Hash *hash) |
Retrieves the number of buckets available in the given hash table. | |
EAPI Eina_Bool | eina_hash_add_by_hash (Eina_Hash *hash, const void *key, int key_length, int key_hash, const void *data) |
Adds an entry to the given hash table. | |
EAPI Eina_Bool EAPI Eina_Bool | eina_hash_direct_add_by_hash (Eina_Hash *hash, const void *key, int key_length, int key_hash, const void *data) |
Adds an entry to the given hash table and does not duplicate the string key. | |
EAPI Eina_Bool EAPI Eina_Bool EAPI Eina_Bool | eina_hash_del_by_key_hash (Eina_Hash *hash, const void *key, int key_length, int key_hash) |
Removes the entry identified by key and key_hash from the given hash table. | |
EAPI Eina_Bool EAPI Eina_Bool EAPI Eina_Bool EAPI Eina_Bool | eina_hash_del_by_key (Eina_Hash *hash, const void *key) |
Removes the entry identified by key from the given hash table. | |
EAPI Eina_Bool EAPI Eina_Bool EAPI Eina_Bool EAPI Eina_Bool EAPI Eina_Bool | eina_hash_del_by_data (Eina_Hash *hash, const void *data) |
Removes the entry identified by data from the given hash table. | |
EAPI Eina_Bool EAPI Eina_Bool EAPI Eina_Bool EAPI Eina_Bool EAPI Eina_Bool EAPI Eina_Bool | eina_hash_del_by_hash (Eina_Hash *hash, const void *key, int key_length, int key_hash, const void *data) |
Removes the entry identified by key and key_hash or data from the given hash table. | |
EAPI void * | eina_hash_find_by_hash (const Eina_Hash *hash, const void *key, int key_length, int key_hash) |
Retrieves a specific entry in the given hash table. | |
EAPI void *EAPI void * | eina_hash_modify_by_hash (Eina_Hash *hash, const void *key, int key_length, int key_hash, const void *data) |
Modifies the entry pointer at the specified key and returns the old entry. | |
EAPI void *EAPI void EAPI Eina_Iterator * | eina_hash_iterator_key_new (const Eina_Hash *hash) |
Returned a new iterator asociated to hash keys. | |
EAPI Eina_Iterator * | eina_hash_iterator_data_new (const Eina_Hash *hash) |
Returned a new iterator asociated to hash data. | |
EAPI Eina_Iterator * | eina_hash_iterator_tuple_new (const Eina_Hash *hash) |
Returned a new iterator asociated to hash keys and data. | |
EAPI void | eina_hash_foreach (const Eina_Hash *hash, Eina_Hash_Foreach func, const void *fdata) |
Call a function on every member stored in the hash table. | |
EAPI void EAPI int | eina_hash_superfast (const char *key, int len) EINA_ARG_NONNULL(1) |
static int | eina_hash_djb2 (const char *key, int len) EINA_ARG_NONNULL(1) |
static int | eina_hash_djb2_len (const char *key, int *plen) EINA_ARG_NONNULL(1 |
static int static int | eina_hash_int32 (const unsigned int *pkey, int len) EINA_ARG_NONNULL(1) |
static int | eina_hash_int64 (const unsigned long int *pkey, int len) EINA_ARG_NONNULL(1) |
Detailed Description
give a small description here : what it is for, what it does , etc.
..
Hash API. Give some hints about the use (functions that must be used like init / shutdown), general use, etc... Give also a link to tutorial below.
Algorithm
Give here the algorithm used in the implementation
Performance
Give some hints about performance if it is possible, and an image !
Tutorial
Here is a fantastic tutorial about our hash table
Function Documentation
EAPI int eina_hash_init | ( | void | ) |
Initialize the hash table module.
- Returns:
- 1 or greater on success, 0 on error.
This function sets up the error module of Eina. It is also called by eina_init(). It returns 0 on failure, otherwise it returns the number of times it has already been called. See eina_error_init() for the documentation of the initialisation of the dependency module.
When no more Eina hash tables are used, call eina_hash_shutdown() to shut down the array module.
- See also:
- eina_error_init()
References eina_error_init().
Referenced by eina_init().
EAPI int eina_hash_shutdown | ( | void | ) |
Shut down the hash table module.
- Returns:
- 0 when the error module is completely shut down, 1 or greater otherwise.
This function just shut down the error module set up by eina_hash_init(). It is also called by eina_shutdown(). It returns 0 when it is called the same number of times than eina_error_init().
References eina_error_shutdown().
Referenced by eina_init(), and eina_shutdown().
EAPI Eina_Bool eina_hash_add | ( | Eina_Hash * | hash, | |
const void * | key, | |||
const void * | data | |||
) |
Adds an entry to the given hash table.
key
is expected to be a unique string within the hash table. Otherwise, you cannot be sure which inserted data pointer will be accessed with eina_hash_find , and removed with eina_hash_del .
Key strings are case sensitive.
eina_error_get() should be used to determine if an allocation error occurred during this function.
- Parameters:
-
hash The given hash table. Can be NULL
.key A unique key. Can be NULL
.data Data to associate with the string given by key
.
- Returns:
- Will return EINA_FALSE if an error occured, and EINA_TRUE if every thing goes fine.
References EINA_FALSE, and eina_hash_add_by_hash().
EAPI Eina_Bool eina_hash_direct_add | ( | Eina_Hash * | hash, | |
const void * | key, | |||
const void * | data | |||
) |
Adds an entry to the given hash table and does not duplicate the string key.
key
is expected to be a unique string within the hash table. Otherwise, you cannot be sure which inserted data pointer will be accessed with eina_hash_find , and removed with eina_hash_del . This call does not make a copy of the key so it must be a string constant or stored elsewhere (in the object being added) etc.
Key strings are case sensitive.
eina_error_get() should be used to determine if an allocation error occurred during this function.
- Parameters:
-
hash The given hash table. Can be NULL
.key A unique key. Can be NULL
.data Data to associate with the string given by key
.
- Returns:
- Will return EINA_FALSE if an error occured, and EINA_TRUE if every thing goes fine.
References EINA_FALSE, and eina_hash_direct_add_by_hash().
EAPI Eina_Bool eina_hash_del | ( | Eina_Hash * | hash, | |
const void * | key, | |||
const void * | data | |||
) |
Removes the entry identified by key
or data
from the given hash table.
If key
is NULL
, then data
is used to find a match to remove.
- Parameters:
-
hash The given hash table. key The key. Can be NULL
.data The data pointer to remove if key
isNULL
. Otherwise, not required and can beNULL
.
- Returns:
- Will return EINA_FALSE if an error occured, and EINA_TRUE if every thing goes fine.
- Note:
- if you know you already have the key, use eina_hash_del_by_key() or eina_hash_del_by_key_hash(). If you know you don't have the key, use eina_hash_del_by_data() directly.
References EINA_FALSE, and eina_hash_del_by_data().
EAPI void * eina_hash_find | ( | const Eina_Hash * | hash, | |
const void * | key | |||
) |
Retrieves a specific entry in the given hash table.
- Parameters:
-
hash The given hash table. key The key of the entry to find.
- Returns:
- The data pointer for the stored entry, or
NULL
if not found.
References eina_hash_find_by_hash().
EAPI void * eina_hash_modify | ( | Eina_Hash * | hash, | |
const void * | key, | |||
const void * | data | |||
) |
Modifies the entry pointer at the specified key and returns the old entry.
- Parameters:
-
hash The given hash table. key The key of the entry to modify. data The data to replace the old entry, if it exists.
- Returns:
- The data pointer for the old stored entry, or
NULL
if not found. If an existing entry is not found, nothing is added to the hash.
References eina_hash_modify_by_hash().
EAPI void eina_hash_free | ( | Eina_Hash * | hash | ) |
Free an entire hash table.
- Parameters:
-
hash The hash table to be freed
This function frees up all the memory allocated to storing the specified hash tale pointed to by hash
. Any entries in the table that the program has no more pointers for elsewhere may now be lost, so this should only be called if the program has lready freed any allocated data in the hash table or has the pointers for data in teh table stored elswehere as well.
Example:
extern Eina_Hash *hash; eina_hash_free(hash); hash = NULL;
EAPI int eina_hash_population | ( | const Eina_Hash * | hash | ) |
Retrieves the number of buckets available in the given hash table.
- Parameters:
-
hash The given hash table.
- Returns:
256
ifhash
is notNULL
.0
otherwise.
EAPI Eina_Bool eina_hash_add_by_hash | ( | Eina_Hash * | hash, | |
const void * | key, | |||
int | key_length, | |||
int | key_hash, | |||
const void * | data | |||
) |
Adds an entry to the given hash table.
key
is expected to be a unique string within the hash table. Otherwise, you cannot be sure which inserted data pointer will be accessed with eina_hash_find , and removed with eina_hash_del .
key_hash
is expected to always match key
. Otherwise, you cannot be sure to find it again with eina_hash_find_by_hash.
Key strings are case sensitive.
eina_error_get should be used to determine if an allocation error occurred during this function.
- Parameters:
-
hash The given hash table. Can be NULL
.key A unique key. Can be NULL
.key_length Should be the length of key
(don't forget to count '\0' for string).key_hash The hash that will always match key. data Data to associate with the string given by key
.
- Returns:
- Will return EINA_FALSE if an error occured, and EINA_TRUE if every thing goes fine.
Referenced by eina_hash_add().
EAPI Eina_Bool eina_hash_direct_add_by_hash | ( | Eina_Hash * | hash, | |
const void * | key, | |||
int | key_length, | |||
int | key_hash, | |||
const void * | data | |||
) |
Adds an entry to the given hash table and does not duplicate the string key.
key
is expected to be a unique string within the hash table. Otherwise, you cannot be sure which inserted data pointer will be accessed with eina_hash_find , and removed with eina_hash_del . This call does not make a copy of the key so it must be a string constant or stored elsewhere (in the object being added) etc.
key_hash
is expected to always match key
. Otherwise, you cannot be sure to find it again with eina_hash_find_by_hash.
Key strings are case sensitive.
eina_error_get should be used to determine if an allocation error occurred during this function.
- Parameters:
-
hash The given hash table. Can be NULL
.key A unique key. Can be NULL
.key_length Should be the length of key
(don't forget to count '\0' for string).key_hash The hash that will always match key. data Data to associate with the string given by key
.
- Returns:
- Will return EINA_FALSE if an error occured, and EINA_TRUE if every thing goes fine.
Referenced by eina_hash_direct_add().
EAPI Eina_Bool eina_hash_del_by_key_hash | ( | Eina_Hash * | hash, | |
const void * | key, | |||
int | key_length, | |||
int | key_hash | |||
) |
Removes the entry identified by key
and key_hash
from the given hash table.
- Parameters:
-
hash The given hash table. key The key. Cannot be NULL
.key_length Should be the length of key
(don't forget to count '\0' for string).key_hash The hash that always match the key.
- Returns:
- Will return EINA_FALSE if an error occured, and EINA_TRUE if every thing goes fine.
- Note:
- if you don't have the key_hash, use eina_hash_del_by_key() instead.
- if you don't have the key, use eina_hash_del_by_data() instead.
References EINA_FALSE.
EAPI Eina_Bool eina_hash_del_by_key | ( | Eina_Hash * | hash, | |
const void * | key | |||
) |
Removes the entry identified by key
from the given hash table.
This version will calculate key length and hash by using functions provided to hash creation function.
- Parameters:
-
hash The given hash table. key The key. Cannot be NULL
.
- Returns:
- Will return EINA_FALSE if an error occured, and EINA_TRUE if every thing goes fine.
- Note:
- if you already have the key_hash, use eina_hash_del_by_key_hash() instead.
- if you don't have the key, use eina_hash_del_by_data() instead.
References EINA_FALSE.
EAPI Eina_Bool eina_hash_del_by_data | ( | Eina_Hash * | hash, | |
const void * | data | |||
) |
Removes the entry identified by data
from the given hash table.
This version is slow since there is no quick access to nodes based on data.
- Parameters:
-
hash The given hash table. data The data value to search and remove.
- Returns:
- Will return EINA_FALSE if an error occured, and EINA_TRUE if every thing goes fine.
- Note:
- if you already have the key, use eina_hash_del_by_key() or eina_hash_del_by_key_hash() instead.
References EINA_FALSE.
Referenced by eina_hash_del(), and eina_hash_del_by_hash().
EAPI Eina_Bool eina_hash_del_by_hash | ( | Eina_Hash * | hash, | |
const void * | key, | |||
int | key_length, | |||
int | key_hash, | |||
const void * | data | |||
) |
Removes the entry identified by key
and key_hash
or data
from the given hash table.
If key
is NULL
, then data
is used to find a match to remove.
- Parameters:
-
hash The given hash table. key The key. Can be NULL
.key_length Should be the length of key
(don't forget to count '\0' for string).key_hash The hash that always match the key. Ignored if key
isNULL
.data The data pointer to remove if key
isNULL
. Otherwise, not required and can beNULL
.
- Returns:
- Will return EINA_FALSE if an error occured, and EINA_TRUE if every thing goes fine.
- Note:
- if you know you already have the key, use eina_hash_del_by_key_hash(), if you know you don't have the key, use eina_hash_del_by_data() directly.
References EINA_FALSE, and eina_hash_del_by_data().
EAPI void * eina_hash_find_by_hash | ( | const Eina_Hash * | hash, | |
const void * | key, | |||
int | key_length, | |||
int | key_hash | |||
) |
Retrieves a specific entry in the given hash table.
- Parameters:
-
hash The given hash table. key The key of the entry to find. key_length Should be the length of key
(don't forget to count '\0' for string).key_hash The hash that always match the key. Ignored if key
isNULL
.
- Returns:
- The data pointer for the stored entry, or
NULL
if not found.
Referenced by eina_hash_find().
EAPI void * eina_hash_modify_by_hash | ( | Eina_Hash * | hash, | |
const void * | key, | |||
int | key_length, | |||
int | key_hash, | |||
const void * | data | |||
) |
Modifies the entry pointer at the specified key and returns the old entry.
- Parameters:
-
hash The given hash table. key The key of the entry to modify. key_length Should be the length of key
(don't forget to count '\0' for string).key_hash The hash that always match the key. Ignored if key
isNULL
.data The data to replace the old entry, if it exists.
- Returns:
- The data pointer for the old stored entry, or
NULL
if not found. If an existing entry is not found, nothing is added to the hash.
Referenced by eina_hash_modify().
EAPI Eina_Iterator * eina_hash_iterator_key_new | ( | const Eina_Hash * | hash | ) |
Returned a new iterator asociated to hash keys.
- Parameters:
-
hash The hash.
- Returns:
- A new iterator.
This function returns a newly allocated iterator associated to hash
. If hash
is not populated, this function still returns a valid iterator that will always return false on eina_iterator_next(), thus keeping API sane.
If the memory can not be allocated, NULL is returned and EINA_ERROR_OUT_OF_MEMORY is set. Otherwise, a valid iterator is returned.
- Warning:
- if the hash structure changes then the iterator becomes invalid! That is, if you add or remove items this iterator behavior is undefined and your program may crash!
References EINA_ERROR_OUT_OF_MEMORY, and eina_error_set().
EAPI Eina_Iterator * eina_hash_iterator_data_new | ( | const Eina_Hash * | hash | ) |
Returned a new iterator asociated to hash data.
- Parameters:
-
hash The hash.
- Returns:
- A new iterator.
This function returns a newly allocated iterator associated to hash
. If hash
is not populated, this function still returns a valid iterator that will always return false on eina_iterator_next(), thus keeping API sane.
If the memory can not be allocated, NULL is returned and EINA_ERROR_OUT_OF_MEMORY is set. Otherwise, a valid iterator is returned.
- Warning:
- if the hash structure changes then the iterator becomes invalid! That is, if you add or remove items this iterator behavior is undefined and your program may crash!
References EINA_ERROR_OUT_OF_MEMORY, and eina_error_set().
EAPI Eina_Iterator * eina_hash_iterator_tuple_new | ( | const Eina_Hash * | hash | ) |
Returned a new iterator asociated to hash keys and data.
- Parameters:
-
hash The hash.
- Returns:
- A new iterator.
This function returns a newly allocated iterator associated to hash
. If hash
is not populated, this function still returns a valid iterator that will always return false on eina_iterator_next(), thus keeping API sane.
If the memory can not be allocated, NULL is returned and EINA_ERROR_OUT_OF_MEMORY is set. Otherwise, a valid iterator is returned.
- Note:
- iterator data will provide values as Eina_Hash_Tuple that should not be modified!
- Warning:
- if the hash structure changes then the iterator becomes invalid! That is, if you add or remove items this iterator behavior is undefined and your program may crash!
References EINA_ERROR_OUT_OF_MEMORY, and eina_error_set().
Referenced by eina_hash_foreach().
EAPI void eina_hash_foreach | ( | const Eina_Hash * | hash, | |
Eina_Hash_Foreach | func, | |||
const void * | fdata | |||
) |
Call a function on every member stored in the hash table.
- Parameters:
-
hash The hash table whose members will be walked func The function to call on each parameter fdata The data pointer to pass to the function being called
This function goes through every entry in the hash table hash
and calls the function func
on each member. The function should NOT modify the hash table contents if it returns 1. IF the hash table contents are modified by this function or the function wishes to stop processing it must return 0, otherwise return 1 to keep processing.
Example:
extern Eina_Hash *hash; Eina_Bool hash_fn(Eina_Hash *hash, const char *key, void *data, void *fdata) { printf("Func data: %s, Hash entry: %s / %p\n", fdata, key, data); return 1; } int main(int argc, char **argv) { char *hash_fn_data; hash_fn_data = strdup("Hello World"); eina_hash_foreach(hash, hash_fn, hash_fn_data); free(hash_fn_data); }
References eina_hash_iterator_tuple_new(), eina_iterator_foreach(), and eina_iterator_free().