BeRTOS
Data Structures | Defines | Typedefs | Functions
hashtable.h File Reference

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.

Detailed Description

Portable hash table.

Author:
Giovanni Bajo <rasky@develer.com>

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 Documentation

#define DECLARE_HASHTABLE (   name,
  size,
  hook_gk 
)
Value:
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.

Parameters:
nameVariable name
sizeNumber of elements
hook_gkHook to be used to extract the key from the node
Note:
The number of elements will be rounded down to the nearest power of two.

Definition at line 119 of file hashtable.h.

#define DECLARE_HASHTABLE_STATIC (   name,
  size,
  hook_gk 
)
Value:
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 Documentation

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.


Function Documentation

const void* ht_find ( struct HashTable ht,
const void *  key,
uint8_t  key_length 
)

Find an element in the hash table.

Parameters:
htHandle of the hash table
keyKey of the element
key_lengthLength of the key in characters
Returns:
Data of the element, or NULL if no element was found for the given key.

Definition at line 274 of file hashtable.c.

void ht_init ( struct HashTable ht)

Initialize (and clear) a hash table in a memory buffer.

Parameters:
htHash table declared with DECLARE_HASHTABLE
Note:
This function must be called before using the hash table. Optionally, it can be called later in the program to clear the hash table, removing all its elements.

Definition at line 203 of file hashtable.c.

bool ht_insert ( struct HashTable ht,
const void *  data 
)

Insert an element into the hash table.

Parameters:
htHandle of the hash table
dataData to be inserted into the table
Returns:
true if insertion was successful, false otherwise (table is full)
Note:
The key for the element to insert is extract from the data with the hook. This means that this function cannot be called for hashtables with internal keys.
If an element with the same key already exists in the table, it will be overwritten.
It is not allowed to store NULL in the table. If you pass NULL as data, the function call will fail.

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.

Parameters:
htHandle of the hash table
keyKey of the element
key_lengthLength of the key in characters
dataData to be inserted into the table
Returns:
true if insertion was successful, false otherwise (table is full)
Note:
If this function is called for hash table with external keys, the key provided must be match the key that would be extracted with the hook, otherwise the function will fail.
If an element with the same key already exists in the table, it will be overwritten.
It is not allowed to store NULL in the table. If you pass NULL as data, the function call will fail.

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.

Note:
Like in STL, the end iterator is not a valid iterator (you cannot call 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.

Note:
The order of the elements visited during the iteration is casual, and depends on the implementation.

Definition at line 279 of file hashtable.h.