A table for hashable objects.
More...
|
size_t | util_hashtable_size (unsigned int num_elements) |
| Computes the size in bytes for num_elements hashtable entries. More...
|
|
struct util_hashtable * | util_hashtable_init (Tget_hashnode get_hashnode, util_hashtable_get_key get_key, util_hashtable_key_compar key_compar, util_hashtable_hash hash, void *data, size_t size, void *userdata) |
| Initializes the given memory data as hash table. More...
|
|
int | util_hashtable_add (struct util_hashtable *ht, const void *key, unsigned int valueindex) |
| Insert a new object into a hashtable. More...
|
|
int | util_hashtable_remove (struct util_hashtable *ht, const void *key) |
| Remove the object key from the hashtable ht . More...
|
|
unsigned int | util_hashtable_lookup (struct util_hashtable *ht, const void *key) |
| Lookup an object in the hashtable. More...
|
|
util_hashtable_iterator | util_hashtable_iterator_first (struct util_hashtable *ht) |
| Get an iterator to the first element of the hashtable ht . More...
|
|
util_hashtable_iterator | util_hashtable_iterator_next (struct util_hashtable *ht, util_hashtable_iterator it) |
| Get an iterator to the next element. More...
|
|
unsigned int | util_hashtable_iterator_value (struct util_hashtable *ht, util_hashtable_iterator it) |
| Get the valueindex for an iterator it .
|
|
unsigned int | util_hashtable_iterator_remove (struct util_hashtable *ht, util_hashtable_iterator it) |
| Remove the element represented by an interator it . More...
|
|
unsigned int | util_hashtable_collisions (const struct util_hashtable *ht) |
| Computes the number of collisions in the hashtable. More...
|
|
void | util_hashtable_trace_collision_stats (const struct util_hashtable *ht, int level, int facility, const char *ht_name) |
| Trace statistics about the number of entries in each bucket of the hashtable. More...
|
|
A table for hashable objects.
The objects must have a fixed index, this can be achieved by storing the objects in an array or objectpool.
The objects can be of arbitrary type, but must contain the util_hashnode as member at any position. Think of <yourtype> is derived from util_hashnode.
struct mystruct {
int foo;
float bar;
}
#define COMPUTE_HASHTABLE_SIZE |
( |
|
num | ) |
(sizeof(struct util_hashtable) + sizeof(unsigned int)*(num)) |
Helper macro to compute the hashtable size.
- Parameters
-
Foreach loop for iterating through a hashtable.
- Parameters
-
#define UTIL_HASHTABLE_ITERATOR_INVALID -1 |
Identifier for invalid util_hashtable_iterator.
typedef struct util_hashnode*(* Tget_hashnode)(unsigned int valueindex, void *userdata) |
Function which returns the hashnode for a given value.
int util_hashtable_add |
( |
struct util_hashtable * |
ht, |
|
|
const void * |
key, |
|
|
unsigned int |
valueindex |
|
) |
| |
Insert a new object into a hashtable.
- Parameters
-
ht | Hashtable to add object to. |
key | Object to add, must be derived from util_hashnode. |
valueindex | Index to identify the object. |
- Returns
- Index of the object in the hashtable.
unsigned int util_hashtable_collisions |
( |
const struct util_hashtable * |
ht | ) |
|
Computes the number of collisions in the hashtable.
This is only diagnostic information.
- Returns
- Number of collisions in hashtable;
struct util_hashtable* util_hashtable_init |
( |
Tget_hashnode |
get_hashnode, |
|
|
util_hashtable_get_key |
get_key, |
|
|
util_hashtable_key_compar |
key_compar, |
|
|
util_hashtable_hash |
hash, |
|
|
void * |
data, |
|
|
size_t |
size, |
|
|
void * |
userdata |
|
) |
| |
Initializes the given memory data
as hash table.
The size of data must be big enough to hold num_objects*object_size+ sizeof(struct objectpool).
Usage:
1 static unsigned char g_hashtabledata[COMPUTE_HASHTABLE_SIZE(100)];
2 static struct hashtable *g_hashtable;
5 struct util_hashnode hashnode;
10 static struct util_hashnode my_get_hashnode(unsigned int valueindex, void *userdata)
12 const my_data *data = objectpool_get(userdata, valueindex);
13 return &data->hashnode;
16 static const void *my_get_key(unsigned int valueindex, void *userdata)
18 const my_data *data = objectpool_get(userdata, valueindex);
22 static int my_key_compar(const void *key1, const void *key2, void *userdata)
24 return strcmp(key1, key2);
27 static unsigned int my_hash(const void *key, void *userdata)
29 size_t len = strlen(key);
30 return util_rotating_hash(key, len);
35 g_hashtable = hashtable_init(my_get_hashnode, my_get_key, my_key_compar, my_hash, g_hashtabledata, sizeof(g_hashtabledata), NULL);
- Parameters
-
git_hashnode | Function which returns util_hashnode element of the indexed data. This is used to resolve hash collissions using a linked list. |
get_key | Function which returns the key for a given node. |
key_compar | Function for comparing two indexed elements. |
hash | Function for computing the elements hash value. |
data | memory area to be used for the hashtable |
size | size of the data in bytes |
userdata | userdata pointer that is returned in all callbacks |
- Returns
- Pointer to initialized hashtable.
Get an iterator to the first element of the hashtable ht
.
- Returns
- Iterator or negative value if hashtable is empty.
Get an iterator to the next element.
- Parameters
-
ht | Hashtable. |
it | Iterator to current element. |
- Returns
- Iterator or negative value if hashtable has no more elements.
Remove the element represented by an interator it
.
unsigned int util_hashtable_lookup |
( |
struct util_hashtable * |
ht, |
|
|
const void * |
key |
|
) |
| |
Lookup an object in the hashtable.
- Parameters
-
ht | Hashtable to lookup object. |
key | Object to lookup. |
- Returns
- Valueindex of the object or UTIL_HT_KEY_NOT_FOUND if not found.
int util_hashtable_remove |
( |
struct util_hashtable * |
ht, |
|
|
const void * |
key |
|
) |
| |
Remove the object key
from the hashtable ht
.
- Returns
- Zero on success or errorcode on failure.
size_t util_hashtable_size |
( |
unsigned int |
num_elements | ) |
|
Computes the size in bytes for num_elements
hashtable entries.
This can be used by the called to allocate the correct amount of memory for util_hashtable_init.
void util_hashtable_trace_collision_stats |
( |
const struct util_hashtable * |
ht, |
|
|
int |
level, |
|
|
int |
facility, |
|
|
const char * |
ht_name |
|
) |
| |
Trace statistics about the number of entries in each bucket of the hashtable.
- Parameters
-
ht | Hashtable to print statistics for. |
level | Trace level to use. |
facility | Trace faility to use. |
ht_name | Name to identify the hashtable. |