hashtable.h File Reference

Portable hash table. More...

#include <cfg/compiler.h>
#include <cfg/macros.h>
#include <cfg/debug.h>


Data Structures
struct	HashTable
	Hash table description. More...
struct	HashIterator
	Iterator to walk the hash table. More...
Defines
#define	CONFIG_HT_OPTIONAL_INTERNAL_KEY 1
	Enable/disable support to declare special hash tables which maintain a copy of the key internally instead of relying on the hook to extract it from the data.
#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	DECLARE_HASHTABLE_INTERNALKEY(name, size)
	Declare a hash table with internal copies of the keys.
#define	DECLARE_HASHTABLE_INTERNALKEY_STATIC(name, size)
	Exactly like `DECLARE_HASHTABLE_INTERNALKEY`, 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.

This file implements a portable hash table, with the following features:

Open double-hashing. The maximum number of elements is fixed. The double hashing function improves recovery in case of collisions.
Configurable size (which is clamped to a power of two)
Visiting interface through iterator (returns the element in random order).
The key is stored within the data and a hook is used to extract it. Optionally, it is possible to store a copy of the key within the hash table.

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().

Version:

Id: hashtable.h 1770 2008-08-31 21:45:01Z bernie

Author:: Giovanni Bajo <rasky@develer.com>

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 = { name##_nodes, UINT32_LOG2(size), { false }, hook_gk }

Declare a hash table in the current scope.

Parameters:

	name	Variable name
	size	Number of elements
	hook_gk	Hook 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 121 of file hashtable.h.

#define DECLARE_HASHTABLE_INTERNALKEY	(	name,
		size		)

Value:

static uint8_t name##_keys[(1 << UINT32_LOG2(size)) * (INTERNAL_KEY_MAX_LENGTH + 1)]; \
        static const void* name##_nodes[1 << UINT32_LOG2(size)]; \
        struct HashTable name = { name##_nodes, UINT32_LOG2(size), { true }, name##_keys }

Declare a hash table with internal copies of the keys.

This version does not require a hook, nor it requires the user to allocate static memory for the keys. It is mostly suggested for tables whose keys are computed on the fly and need to be stored somewhere.

Definition at line 136 of file hashtable.h.

#define DECLARE_HASHTABLE_INTERNALKEY_STATIC	(	name,
		size		)

Value:

static uint8_t name##_keys[(1 << UINT32_LOG2(size)) * (INTERNAL_KEY_MAX_LENGTH + 1)]; \
        static const void* name##_nodes[1 << UINT32_LOG2(size)]; \
        static struct HashTable name = { name##_nodes, UINT32_LOG2(size), { true }, name##_keys }

Exactly like DECLARE_HASHTABLE_INTERNALKEY, but the variable will be declared as static.

Definition at line 142 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 = { name##_nodes, UINT32_LOG2(size), { false }, { hook_gk } }

Exactly like DECLARE_HASHTABLE, but the variable will be declared as static.

Definition at line 126 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 75 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:

	ht	Handle of the hash table
	key	Key of the element
	key_length	Length of the key in characters

Returns:: Data of the element, or NULL if no element was found for the given key.

Definition at line 273 of file hashtable.c.

void ht_init ( struct HashTable * ht )

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

Parameters:

ht Hash 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 202 of file hashtable.c.

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

Insert an element into the hash table.

Parameters:

	ht	Handle of the hash table
	data	Data 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 253 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:

	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

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 234 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 236 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 262 of file hashtable.h.

hashtable.h File Reference

Data Structures

Defines

Typedefs

Functions

Detailed Description

Define Documentation

Typedef Documentation

Function Documentation

Trac Sviluppatori

Abbonati alla Newsletter

Forum di supporto