hashtable.c File Reference

Portable hash table implementation. More...

#include "hashtable.h"
#include <cfg/debug.h>
#include <cfg/compiler.h>
#include <cfg/macros.h>
#include <string.h>

Go to the source code of this file.

Functions
uint8_t *	key_internal_get_ptr (struct HashTable *ht, HashNodePtr node)
	For hash tables with internal keys, compute the pointer to the internal key for a given node.
void	ht_init (struct HashTable *ht)
	Initialize (and clear) a hash table in a memory buffer.
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.
bool	ht_insert (struct HashTable *ht, 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.

---

Detailed Description

Portable hash table implementation.

Some rationales of our choices in implementation:

• For embedded systems, it is vital to allocate the table in static memory. To do so, it is necessary to expose the HashNode and HashTable structures in the header file. Nevertheless, they should be used as opaque types (that is, the users should not access the structure fields directly).

• To statically allocate the structures, a macro is provided. With this macro, we are hiding completely HashNode to the user (who only manipulates HashTable). Without the macro, the user would have had to define both the HashNode and the HashTable manually, and pass both of them to ht_init() (which would have created the link between the two). Instead, the link is created with a literal initialization.

• The hash table is created as power of two to remove the divisions from the code. Of course, hash functions work at their best when the table size is a prime number. When calculating the modulus to convert the hash value to an index, the actual operation becomes a bitwise AND: this is fast, but truncates the value losing bits. Thus, the higher bits are first "merged" with the lower bits through some XOR operations (see the last line of calc_hash()).

• To minimize the memory occupation, there is no flag to set for the empty node. An empty node is recognized by its data pointer set to NULL. It is then invalid to store NULL as data pointer in the table.

• The visiting interface through iterators is implemented with pass-by-value semantic. While this is overkill for medium-to-stupid compilers, it is the best designed from an user point of view. Moreover, being totally inlined (defined completely in the header), even a stupid compiler should be able to perform basic optimizations on it. We thought about using a pass-by-pointer semantic but it was much more awful to use, and the compiler is then forced to spill everything to the stack (unless it is *very* smart).

• The current implementation allows to either store the key internally (that is, copy the key within the hash table) or keep it external (that is, a hook is used to extract the key from the data in the node). The former is more memory-hungry of course, as it allocated static space to store the key copies. The overhead to keep both methods at the same time is minimal:
  • There is a run-time check in node_get_key which is execute per each node visited.
  • Theoretically, there is no memory overhead. In practice, there were no flags in struct HashTable till now, so we had to add a first bit flag, but the overhead will disappear if a second flag is added for a different reason later.
  • There is a little interface overhead, since we have two different versions of ht_insert(), one with the key passed as parameter and one without, but in the common case (external keys) both can be used.

Version:

Id

hashtable.c 840 2007-10-08 17:21:31Z marco

Author:

Giovanni Bajo <rasky@develer.com>

Definition in file hashtable.c.

---

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 289 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 218 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 269 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 250 of file hashtable.c.

uint8_t* key_internal_get_ptr	(	struct HashTable *	ht,
		HashNodePtr	node
	)			[inline]

For hash tables with internal keys, compute the pointer to the internal key for a given node.

Definition at line 114 of file hashtable.c.