mware/hashtable.h

   1 /**
   2  * \file
   3  * <!--
   4  * Copyright 2004, 2006 Develer S.r.l. (http://www.develer.com/)
   5  * Copyright 2004 Giovanni Bajo
   6  * All Rights Reserved.
   7  * -->
   8  *
   9  * \brief Portable hash table
  10  *
  11  * This file implements a portable hash table, with the following features:
  12  *
  13  * \li Open double-hashing. The maximum number of elements is fixed. The double hashing
  14  * function improves recovery in case of collisions.
  15  * \li Configurable size (which is clamped to a power of two)
  16  * \li Visiting interface through iterator (returns the element in random order).
  17  * \li The key is stored within the data and a hook is used to extract it. Optionally, it
  18  * is possible to store a copy of the key within the hash table.
  19  *
  20  * Since the hashing is open, there is no way to remove elements from the table. Instead, a
  21  * function is provided to clear the table completely.
  22  *
  23  * The data stored within the table must be a pointer. The NULL pointer is used as
  24  * a marker for a free node, so it is invalid to store a NULL pointer in the table
  25  * with \c ht_insert().
  26  *
  27  * \version $Id$
  28  *
  29  * \author Giovanni Bajo <rasky@develer.com>
  30  */
  31
  32 /*#*
  33  *#* $Log$
  34  *#* Revision 1.8  2006/07/19 12:56:27  bernie
  35  *#* Convert to new Doxygen style.
  36  *#*
  37  *#* Revision 1.7  2006/06/01 12:27:39  marco
  38  *#* Added utilities for protocols
  39  *#*
  40  *#*/
  41
  42 #ifndef MWARE_HASHTABLE_H
  43 #define MWARE_HASHTABLE_H
  44
  45 #include <cfg/compiler.h>
  46 #include <cfg/macros.h>
  47 #include <cfg/debug.h>
  48
  49 /**
  50  * Enable/disable support to declare special hash tables which maintain a copy of
  51  * the key internally instead of relying on the hook to extract it from the data.
  52  */
  53 #define CONFIG_HT_OPTIONAL_INTERNAL_KEY      1
  54
  55 /// Maximum length of the internal key (use (2^n)-1 for slight speedup)
  56 #define INTERNAL_KEY_MAX_LENGTH     15
  57
  58 /**
  59  * Hook to get the key from \a data, which is an element of the hash table. The
  60  * key must be returned together with \a key_length (in words).
  61  */
  62 typedef const void *(*hook_get_key)(const void *data, uint8_t *key_length);
  63
  64
  65 /**
  66  * Hash table description
  67  *
  68  * \note This structures MUST NOT be accessed directly. Its definition is
  69  * provided in the header file only for optimization purposes (see the rationale
  70  * in hashtable.c).
  71  *
  72  * \note If new elements must be added to this list, please double check
  73  * \c DECLARE_HASHTABLE, which requires the existing elements to be at the top.
  74  */
  75 struct HashTable
  76 {
  77         const void **mem;            ///< Buckets of data
  78         uint16_t max_elts_log2;      ///< Log2 of the size of the table
  79         struct {
  80                 bool key_internal : 1;   ///< true if the key is copied internally
  81         } flags;
  82         union {
  83                 hook_get_key hook;       ///< Hook to get the key
  84                 uint8_t *mem;            ///< Pointer to the key memory
  85         } key_data;
  86 };
  87
  88
  89 /// Iterator to walk the hash table
  90 typedef struct
  91 {
  92         const void** pos;
  93         const void** end;
  94 } HashIterator;
  95
  96
  97 /**
  98  * Declare a hash table in the current scope
  99  *
 100  * \param name Variable name
 101  * \param size Number of elements
 102  * \param hook_gk Hook to be used to extract the key from the node
 103  *
 104  * \note The number of elements will be rounded down to the nearest
 105  * power of two.
 106  *
 107  */
 108 #define DECLARE_HASHTABLE(name, size, hook_gk) \
 109         static const void* name##_nodes[1 << UINT32_LOG2(size)]; \
 110         struct HashTable name = { name##_nodes, UINT32_LOG2(size), { false }, hook_gk }
 111
 112 /** Exactly like \c DECLARE_HASHTABLE, but the variable will be declared as static. */
 113 #define DECLARE_HASHTABLE_STATIC(name, size, hook_gk) \
 114         static const void* name##_nodes[1 << UINT32_LOG2(size)]; \
 115         static struct HashTable name = { name##_nodes, UINT32_LOG2(size), { false }, { hook_gk } }
 116
 117 #if CONFIG_HT_OPTIONAL_INTERNAL_KEY
 118         /** Declare a hash table with internal copies of the keys. This version does not
 119          *  require a hook, nor it requires the user to allocate static memory for the keys.
 120          *  It is mostly suggested for tables whose keys are computed on the fly and need
 121          *  to be stored somewhere.
 122          */
 123         #define DECLARE_HASHTABLE_INTERNALKEY(name, size) \
 124                 static uint8_t name##_keys[(1 << UINT32_LOG2(size)) * (INTERNAL_KEY_MAX_LENGTH + 1)]; \
 125                 static const void* name##_nodes[1 << UINT32_LOG2(size)]; \
 126                 struct HashTable name = { name##_nodes, UINT32_LOG2(size), { true }, name##_keys }
 127
 128         /** Exactly like \c DECLARE_HASHTABLE_INTERNALKEY, but the variable will be declared as static. */
 129         #define DECLARE_HASHTABLE_INTERNALKEY_STATIC(name, size) \
 130                 static uint8_t name##_keys[(1 << UINT32_LOG2(size)) * (INTERNAL_KEY_MAX_LENGTH + 1)]; \
 131                 static const void* name##_nodes[1 << UINT32_LOG2(size)]; \
 132                 static struct HashTable name = { name##_nodes, UINT32_LOG2(size), { true }, name##_keys }
 133 #endif
 134
 135 /**
 136  * Initialize (and clear) a hash table in a memory buffer.
 137  *
 138  * \param ht Hash table declared with \c DECLARE_HASHTABLE
 139  *
 140  * \note This function must be called before using the hash table. Optionally,
 141  * it can be called later in the program to clear the hash table,
 142  * removing all its elements.
 143  */
 144 void ht_init(struct HashTable* ht);
 145
 146 /**
 147  * Insert an element into the hash table
 148  *
 149  * \param ht Handle of the hash table
 150  * \param data Data to be inserted into the table
 151  * \return true if insertion was successful, false otherwise (table is full)
 152  *
 153  * \note The key for the element to insert is extract from the data with
 154  * the hook. This means that this function cannot be called for hashtables
 155  * with internal keys.
 156  *
 157  * \note If an element with the same key already exists in the table,
 158  * it will be overwritten.
 159  *
 160  * \note It is not allowed to store NULL in the table. If you pass NULL as data,
 161  * the function call will fail.
 162  */
 163 bool ht_insert(struct HashTable* ht, const void* data);
 164
 165 /**
 166  * Insert an element into the hash table
 167  *
 168  * \param ht Handle of the hash table
 169  * \param key Key of the element
 170  * \param key_length Length of the key in characters
 171  * \param data Data to be inserted into the table
 172  * \return true if insertion was successful, false otherwise (table is full)
 173  *
 174  * \note If this function is called for hash table with external keys,
 175  * the key provided must be match the key that would be extracted with the
 176  * hook, otherwise the function will fail.
 177  *
 178  * \note If an element with the same key already exists in the table,
 179  * it will be overwritten.
 180  *
 181  * \note It is not allowed to store NULL in the table. If you pass NULL as data,
 182  * the function call will fail.
 183  */
 184 bool ht_insert_with_key(struct HashTable* ht, const void* key, uint8_t key_length, const void* data);
 185
 186 /**
 187  * Find an element in the hash table
 188  *
 189  * \param ht Handle of the hash table
 190  * \param key Key of the element
 191  * \param key_length Length of the key in characters
 192  * \return Data of the element, or NULL if no element was found for the given key.
 193  */
 194 const void* ht_find(struct HashTable* ht, const void* key, uint8_t key_length);
 195
 196 /** Similar to \c ht_insert_with_key() but \a key is an ASCIIZ string */
 197 #define ht_insert_str(ht, key, data)         ht_insert_with_key(ht, key, strlen(key), data)
 198
 199 /** Similar to \c ht_find() but \a key is an ASCIIZ string */
 200 #define ht_find_str(ht, key)                 ht_find(ht, key, strlen(key))
 201
 202 /// Get an iterator to the begin of the hash table \a ht
 203 INLINE HashIterator ht_iter_begin(struct HashTable* ht)
 204 {
 205         HashIterator h;
 206
 207         h.pos = &ht->mem[0];
 208         h.end = &ht->mem[1 << ht->max_elts_log2];
 209
 210         while (h.pos != h.end && !*h.pos)
 211                 ++h.pos;
 212
 213         return h;
 214 }
 215
 216 /**
 217  * Get an iterator to the (exclusive) end of the hash table \a ht
 218  *
 219  * \note Like in STL, the end iterator is not a valid iterator (you
 220  *       cannot call \c ht_iter_get() on it), and it must be used only to
 221  *       detect if we reached the end of the iteration (through \c ht_iter_cmp()).
 222  */
 223 INLINE HashIterator ht_iter_end(struct HashTable* ht)
 224 {
 225         HashIterator h;
 226
 227         h.pos = h.end = &ht->mem[1 << ht->max_elts_log2];
 228
 229         return h;
 230 }
 231
 232 /// Compare \a it1 and \a it2 for equality
 233 INLINE bool ht_iter_cmp(HashIterator it1, HashIterator it2)
 234 {
 235         ASSERT(it1.end == it2.end);
 236         return it1.pos == it2.pos;
 237 }
 238
 239 /// Get the element within the hash table \a ht pointed by the iterator \a iter
 240 INLINE const void* ht_iter_get(HashIterator iter)
 241 { return *iter.pos; }
 242
 243 /** Return an iterator pointing to the element following \a h
 244  *
 245  * \note The order of the elements visited during the iteration is casual,
 246  * and depends on the implementation.
 247  *
 248  */
 249 INLINE HashIterator ht_iter_next(HashIterator h)
 250 {
 251         ++h.pos;
 252         while (h.pos != h.end && !(*h.pos))
 253                 ++h.pos;
 254
 255         return h;
 256 }
 257
 258 #endif /* MWARE_HASHTABLE_H */