hashtable.c File Reference

Portable hash table implementation. More...

#include "hashtable.h"
#include "cfg/cfg_hashtable.h"
#include <cfg/compiler.h>
#include <cfg/macros.h>
#include <cfg/debug.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.
Author:
Giovanni Bajo <rasky@develer.com>

Definition in file hashtable.c.

Function Documentation

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 99 of file hashtable.c.