Hash tables

Hash tables — Hash tables

Synopsis




                    KitHash;
uint32_t            (*KitHashFunc)                      (const void *key);
kit_bool_t          (*KitEqualFunc)                     (const void *key1,
                                                         const void *key2);
void                (*KitFreeFunc)                      (void *p);
void*               (*KitCopyFunc)                      (const void *p);
kit_bool_t          (*KitHashForeachFunc)               (KitHash *hash,
                                                         void *key,
                                                         void *value,
                                                         void *user_data);
KitHash*            kit_hash_new                        (KitHashFunc hash_func,
                                                         KitEqualFunc key_equal_func,
                                                         KitCopyFunc key_copy_func,
                                                         KitCopyFunc value_copy_func,
                                                         KitFreeFunc key_destroy_func,
                                                         KitFreeFunc value_destroy_func);
KitHash*            kit_hash_ref                        (KitHash *hash);
void                kit_hash_unref                      (KitHash *hash);
kit_bool_t          kit_hash_insert                     (KitHash *hash,
                                                         void *key,
                                                         void *value);
void*               kit_hash_lookup                     (KitHash *hash,
                                                         void *key,
                                                         kit_bool_t *found);
kit_bool_t          kit_hash_foreach                    (KitHash *hash,
                                                         KitHashForeachFunc cb,
                                                         void *user_data);
size_t              kit_hash_foreach_remove             (KitHash *hash,
                                                         KitHashForeachFunc cb,
                                                         void *user_data);
uint32_t            kit_hash_direct_hash_func           (const void *key);
kit_bool_t          kit_hash_direct_equal_func          (const void *v1,
                                                         const void *v2);
uint32_t            kit_hash_str_hash_func              (const void *key);
kit_bool_t          kit_hash_str_equal_func             (const void *v1,
                                                         const void *v2);
void*               kit_hash_str_copy                   (const void *p);

Description

This class provides support for hash tables.

Details

KitHash

typedef struct _KitHash KitHash;

The KitHash structure not be accessed directly.


KitHashFunc ()

uint32_t            (*KitHashFunc)                      (const void *key);

The function is passed a key and should return a hash value. The functions kit_hash_direct_hash_func() and kit_hash_str_hash_func() provide hash functions which can be used when the key is a pointer and an char* respectively.

key :

a key

Returns :

the hash value corresponding to the key

KitEqualFunc ()

kit_bool_t          (*KitEqualFunc)                     (const void *key1,
                                                         const void *key2);

Determines if two keys are equal. The functions kit_hash_direct_equal_func() and kit_hash_str_equal_func() provide equality functions which can be used when the key is a pointer and an char* respectively.

key1 :

first key

key2 :

second key

Returns :

TRUE iff the keys are equal

KitFreeFunc ()

void                (*KitFreeFunc)                      (void *p);

Specifies the type of function which is called when a data element is destroyed. It is passed the pointer to the data element and should free any memory and resources allocated for it. The function p_free() or any of the object unref functions can be passed here.

p :

pointer

KitCopyFunc ()

void*               (*KitCopyFunc)                      (const void *p);

Specifies the type of function which is called when a data element is to be cloned or reffed. It is passed the pointer to the data element and should return a new pointer to a reffed or cloned object. The function kit_hash_str_copy() or any of the object ref functions can be passed here.

p :

pointer

Returns :

A copy or ref of the object in question

KitHashForeachFunc ()

kit_bool_t          (*KitHashForeachFunc)               (KitHash *hash,
                                                         void *key,
                                                         void *value,
                                                         void *user_data);

Type signature for callback function used in kit_hash_foreach().

hash :

the hash table

key :

key

value :

value

user_data :

user data passed to kit_hash_foreach()

Returns :

Return TRUE to short-circuit, e.g. stop the iteration.

kit_hash_new ()

KitHash*            kit_hash_new                        (KitHashFunc hash_func,
                                                         KitEqualFunc key_equal_func,
                                                         KitCopyFunc key_copy_func,
                                                         KitCopyFunc value_copy_func,
                                                         KitFreeFunc key_destroy_func,
                                                         KitFreeFunc value_destroy_func);

Creates a new Hash Table.

hash_func :

The hash function to use

key_equal_func :

The function used to determine key equality

key_copy_func :

Function for copying keys or NULL

value_copy_func :

Function for copying values or NULL

key_destroy_func :

Function for freeing keys or NULL

value_destroy_func :

Function for freeing values or NULL

Returns :

The new hash table. Returns NULL on OOM.

kit_hash_ref ()

KitHash*            kit_hash_ref                        (KitHash *hash);

Increase reference count.

hash :

the hash table

Returns :

the hash table

kit_hash_unref ()

void                kit_hash_unref                      (KitHash *hash);

Decrease reference count. If reference count drop to zero the hash table is freed.

hash :

the hash table

kit_hash_insert ()

kit_bool_t          kit_hash_insert                     (KitHash *hash,
                                                         void *key,
                                                         void *value);

Inserts a new key and value into a hash table. If the key already exists in the hash table it's current value is replaced with the new value.

hash :

the hash table

key :

key to insert

value :

value to insert

Returns :

TRUE unless OOM

kit_hash_lookup ()

void*               kit_hash_lookup                     (KitHash *hash,
                                                         void *key,
                                                         kit_bool_t *found);

Look up a value in the hash table.

hash :

the hash table

key :

key to look up

found :

if not NULL, will return TRUE only if the key was found in the hash table

Returns :

the value; caller shall not free/unref this value

kit_hash_foreach ()

kit_bool_t          kit_hash_foreach                    (KitHash *hash,
                                                         KitHashForeachFunc cb,
                                                         void *user_data);

Iterate over all elements in a hash table

hash :

the hash table

cb :

callback function

user_data :

user data

Returns :

TRUE only if the callback short-circuited the iteration

kit_hash_foreach_remove ()

size_t              kit_hash_foreach_remove             (KitHash *hash,
                                                         KitHashForeachFunc cb,
                                                         void *user_data);

Iterate over all elements in a hash table. If cb returns TRUE, the element will be removed.

hash :

the hash table

cb :

callback function

user_data :

user data

Returns :

Number of key/value pairs removed

kit_hash_direct_hash_func ()

uint32_t            kit_hash_direct_hash_func           (const void *key);

Converts a pointer to a hash value.

key :

the key

Returns :

a hash value corresponding to the key

kit_hash_direct_equal_func ()

kit_bool_t          kit_hash_direct_equal_func          (const void *v1,
                                                         const void *v2);

Compares two pointers and return TRUE if they are equal (same address).

v1 :

first value

v2 :

second value

Returns :

TRUE only if the values are equal

kit_hash_str_hash_func ()

uint32_t            kit_hash_str_hash_func              (const void *key);

Converts a string to a hash value.

key :

the key

Returns :

a hash value corresponding to the key

kit_hash_str_equal_func ()

kit_bool_t          kit_hash_str_equal_func             (const void *v1,
                                                         const void *v2);

Compares two strings and return TRUE if they are equal.

v1 :

first value

v2 :

second value

Returns :

TRUE only if the values are equal

kit_hash_str_copy ()

void*               kit_hash_str_copy                   (const void *p);

Similar to kit_strdup() except for types.

p :

void pointer to string

Returns :

a void pointer to a copy or NULL on OOM