BeRTOS
|
Portable hash table. More...
#include "cfg/cfg_hashtable.h"
#include <cfg/compiler.h>
#include <cfg/macros.h>
#include <cfg/debug.h>
Go to the source code of this file.
Data Structures | |
struct | HashTable |
Hash table description. More... | |
struct | HashIterator |
Iterator to walk the hash table. More... | |
Defines | |
#define | INTERNAL_KEY_MAX_LENGTH 15 |
Maximum length of the internal key (use (2^n)-1 for slight speedup) | |
#define | DECLARE_HASHTABLE(name, size, hook_gk) |
Declare a hash table in the current scope. | |
#define | DECLARE_HASHTABLE_STATIC(name, size, hook_gk) |
Exactly like DECLARE_HASHTABLE , but the variable will be declared as static. | |
#define | ht_insert_str(ht, key, data) ht_insert_with_key(ht, key, strlen(key), data) |
Similar to ht_insert_with_key() but key is an ASCIIZ string. | |
#define | ht_find_str(ht, key) ht_find(ht, key, strlen(key)) |
Similar to ht_find() but key is an ASCIIZ string. | |
Typedefs | |
typedef const void *(* | hook_get_key )(const void *data, uint8_t *key_length) |
Hook to get the key from data, which is an element of the hash table. | |
Functions | |
void | ht_init (struct HashTable *ht) |
Initialize (and clear) a hash table in a memory buffer. | |
bool | ht_insert (struct HashTable *ht, const void *data) |
Insert an element into the hash table. | |
bool | ht_insert_with_key (struct HashTable *ht, const void *key, uint8_t key_length, const void *data) |
Insert an element into the hash table. | |
const void * | ht_find (struct HashTable *ht, const void *key, uint8_t key_length) |
Find an element in the hash table. | |
HashIterator | ht_iter_begin (struct HashTable *ht) |
Get an iterator to the begin of the hash table ht. | |
HashIterator | ht_iter_end (struct HashTable *ht) |
Get an iterator to the (exclusive) end of the hash table ht. | |
bool | ht_iter_cmp (HashIterator it1, HashIterator it2) |
Compare it1 and it2 for equality. | |
const void * | ht_iter_get (HashIterator iter) |
Get the element within the hash table ht pointed by the iterator iter. | |
HashIterator | ht_iter_next (HashIterator h) |
Return an iterator pointing to the element following h. |
Portable hash table.
This file implements a portable hash table, with the following features:
Since the hashing is open, there is no way to remove elements from the table. Instead, a function is provided to clear the table completely.
The data stored within the table must be a pointer. The NULL pointer is used as a marker for a free node, so it is invalid to store a NULL pointer in the table with ht_insert()
.
Definition in file hashtable.h.
#define DECLARE_HASHTABLE | ( | name, | |
size, | |||
hook_gk | |||
) |
static const void* name##_nodes[1 << UINT32_LOG2(size)]; \ struct HashTable name = \ { \ .mem = name##_nodes, \ .max_elts_log2 = UINT32_LOG2(size), \ .flags = { .key_internal = false }, \ .key_data.hook = hook_gk \ }
Declare a hash table in the current scope.
name | Variable name |
size | Number of elements |
hook_gk | Hook to be used to extract the key from the node |
Definition at line 119 of file hashtable.h.
#define DECLARE_HASHTABLE_STATIC | ( | name, | |
size, | |||
hook_gk | |||
) |
static const void* name##_nodes[1 << UINT32_LOG2(size)]; \ static struct HashTable name = \ { \ .mem = name##_nodes, \ .max_elts_log2 = UINT32_LOG2(size), \ .flags = { .key_internal = false }, \ .key_data.hook = hook_gk \ }
Exactly like DECLARE_HASHTABLE
, but the variable will be declared as static.
Definition at line 131 of file hashtable.h.
typedef const void*(* hook_get_key)(const void *data, uint8_t *key_length) |
Hook to get the key from data, which is an element of the hash table.
The key must be returned together with key_length (in words).
Definition at line 73 of file hashtable.h.
const void* ht_find | ( | struct HashTable * | ht, |
const void * | key, | ||
uint8_t | key_length | ||
) |
Find an element in the hash table.
ht | Handle of the hash table |
key | Key of the element |
key_length | Length of the key in characters |
Definition at line 274 of file hashtable.c.
void ht_init | ( | struct HashTable * | ht | ) |
Initialize (and clear) a hash table in a memory buffer.
ht | Hash table declared with DECLARE_HASHTABLE |
Definition at line 203 of file hashtable.c.
bool ht_insert | ( | struct HashTable * | ht, |
const void * | data | ||
) |
Insert an element into the hash table.
ht | Handle of the hash table |
data | Data to be inserted into the table |
Definition at line 254 of file hashtable.c.
bool ht_insert_with_key | ( | struct HashTable * | ht, |
const void * | key, | ||
uint8_t | key_length, | ||
const void * | data | ||
) |
Insert an element into the hash table.
ht | Handle of the hash table |
key | Key of the element |
key_length | Length of the key in characters |
data | Data to be inserted into the table |
Definition at line 235 of file hashtable.c.
HashIterator ht_iter_end | ( | struct HashTable * | ht | ) | [inline] |
Get an iterator to the (exclusive) end of the hash table ht.
ht_iter_get()
on it), and it must be used only to detect if we reached the end of the iteration (through ht_iter_cmp()
). Definition at line 253 of file hashtable.h.
HashIterator ht_iter_next | ( | HashIterator | h | ) | [inline] |
Return an iterator pointing to the element following h.
Definition at line 279 of file hashtable.h.