bertos/struct/hashtable.h

   1 /**
   2  * \file
   3  * <!--
   4  * This file is part of BeRTOS.
   5  *
   6  * Bertos is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation; either version 2 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  19  *
  20  * As a special exception, you may use this file as part of a free software
  21  * library without restriction.  Specifically, if other files instantiate
  22  * templates or use macros or inline functions from this file, or you compile
  23  * this file and link it with other files to produce an executable, this
  24  * file does not by itself cause the resulting executable to be covered by
  25  * the GNU General Public License.  This exception does not however
  26  * invalidate any other reasons why the executable file might be covered by
  27  * the GNU General Public License.
  28  *
  29  * Copyright 2004, 2006, 2008 Develer S.r.l. (http://www.develer.com/)
  30  * Copyright 2004 Giovanni Bajo
  31  * -->
  32  *
  33  * \defgroup hashtable Hash table implementation
  34  * \ingroup struct
  35  * \{
  36  *
  37  * \brief Portable hash table
  38  *
  39  * This file implements a portable hash table, with the following features:
  40  *
  41  * \li Open double-hashing. The maximum number of elements is fixed. The double hashing
  42  * function improves recovery in case of collisions.
  43  * \li Configurable size (which is clamped to a power of two)
  44  * \li Visiting interface through iterator (returns the element in random order).
  45  * \li The key is stored within the data and a hook is used to extract it. Optionally, it
  46  * is possible to store a copy of the key within the hash table.
  47  *
  48  * Since the hashing is open, there is no way to remove elements from the table. Instead, a
  49  * function is provided to clear the table completely.
  50  *
  51  * The data stored within the table must be a pointer. The NULL pointer is used as
  52  * a marker for a free node, so it is invalid to store a NULL pointer in the table
  53  * with \c ht_insert().
  54  *
  55  * \author Giovanni Bajo <rasky@develer.com>
  56  *
  57  * $WIZ$ module_name = "hashtable"
  58  * $WIZ$ module_configuration = "bertos/cfg/cfg_hashtable.h"
  59  */
  60
  61 #ifndef STRUCT_HASHTABLE_H
  62 #define STRUCT_HASHTABLE_H
  63
  64 #include "cfg/cfg_hashtable.h"
  65
  66 #include <cfg/compiler.h>
  67 #include <cfg/macros.h>
  68 #include <cfg/debug.h>
  69
  70 /// Maximum length of the internal key (use (2^n)-1 for slight speedup)
  71 #define INTERNAL_KEY_MAX_LENGTH     15
  72
  73 /**
  74  * Hook to get the key from \a data, which is an element of the hash table. The
  75  * key must be returned together with \a key_length (in words).
  76  */
  77 typedef const void *(*hook_get_key)(const void *data, uint8_t *key_length);
  78
  79
  80 /**
  81  * Hash table description
  82  *
  83  * \note This structures MUST NOT be accessed directly. Its definition is
  84  * provided in the header file only for optimization purposes (see the rationale
  85  * in hashtable.c).
  86  *
  87  * \note If new elements must be added to this list, please double check
  88  * \c DECLARE_HASHTABLE, which requires the existing elements to be at the top.
  89  */
  90 struct HashTable
  91 {
  92         const void **mem;            ///< Buckets of data
  93         uint16_t max_elts_log2;      ///< Log2 of the size of the table
  94         struct {
  95                 bool key_internal : 1;   ///< true if the key is copied internally
  96         } flags;
  97         union {
  98                 hook_get_key hook;       ///< Hook to get the key
  99                 uint8_t *mem;            ///< Pointer to the key memory
 100         } key_data;
 101 };
 102
 103
 104 /// Iterator to walk the hash table
 105 typedef struct
 106 {
 107         const void** pos;
 108         const void** end;
 109 } HashIterator;
 110
 111
 112 /**
 113  * Declare a hash table in the current scope
 114  *
 115  * \param name Variable name
 116  * \param size Number of elements
 117  * \param hook_gk Hook to be used to extract the key from the node
 118  *
 119  * \note The number of elements will be rounded down to the nearest
 120  * power of two.
 121  *
 122  */
 123 #define DECLARE_HASHTABLE(name, size, hook_gk) \
 124         static const void* name##_nodes[1 << UINT32_LOG2(size)]; \
 125         struct HashTable name = \
 126                 { \
 127                         .mem = name##_nodes, \
 128                         .max_elts_log2 = UINT32_LOG2(size), \
 129                         .flags = { .key_internal = false }, \
 130                         .key_data.hook = hook_gk \
 131                 }
 132
 133
 134 /** Exactly like \c DECLARE_HASHTABLE, but the variable will be declared as static. */
 135 #define DECLARE_HASHTABLE_STATIC(name, size, hook_gk) \
 136         enum { name##_SIZE = (1 << UINT32_LOG2(size)), }; \
 137         static const void* name##_nodes[name##_SIZE]; \
 138         static struct HashTable name = \
 139                 { \
 140                         .mem = name##_nodes, \
 141                         .max_elts_log2 = UINT32_LOG2(size), \
 142                         .flags = { .key_internal = false }, \
 143                         .key_data.hook = hook_gk \
 144                 }
 145
 146 #if CONFIG_HT_OPTIONAL_INTERNAL_KEY
 147         /** Declare a hash table with internal copies of the keys. This version does not
 148          *  require a hook, nor it requires the user to allocate static memory for the keys.
 149          *  It is mostly suggested for tables whose keys are computed on the fly and need
 150          *  to be stored somewhere.
 151          */
 152         #define DECLARE_HASHTABLE_INTERNALKEY(name, size) \
 153                 static uint8_t name##_keys[(1 << UINT32_LOG2(size)) * (INTERNAL_KEY_MAX_LENGTH + 1)]; \
 154                 static const void* name##_nodes[1 << UINT32_LOG2(size)]; \
 155                 struct HashTable name = { name##_nodes, UINT32_LOG2(size), { true }, name##_keys }
 156
 157         /** Exactly like \c DECLARE_HASHTABLE_INTERNALKEY, but the variable will be declared as static. */
 158         #define DECLARE_HASHTABLE_INTERNALKEY_STATIC(name, size) \
 159                 enum { name##_KEYS = ((1 << UINT32_LOG2(size)) * (INTERNAL_KEY_MAX_LENGTH + 1)), \
 160                         name##_SIZE = (1 << UINT32_LOG2(size)), }; \
 161                 static uint8_t name##_keys[name##_KEYS]; \
 162                 static const void* name##_nodes[name##_SIZE]; \
 163                 static struct HashTable name = \
 164                         { \
 165                                 .mem = name##_nodes, \
 166                                 .max_elts_log2 = UINT32_LOG2(size), \
 167                                 .flags = { .key_internal = true }, \
 168                                 .key_data.mem = name##_keys \
 169                         }
 170 #endif
 171
 172 /**
 173  * Initialize (and clear) a hash table in a memory buffer.
 174  *
 175  * \param ht Hash table declared with \c DECLARE_HASHTABLE
 176  *
 177  * \note This function must be called before using the hash table. Optionally,
 178  * it can be called later in the program to clear the hash table,
 179  * removing all its elements.
 180  */
 181 void ht_init(struct HashTable* ht);
 182
 183 /**
 184  * Insert an element into the hash table
 185  *
 186  * \param ht Handle of the hash table
 187  * \param data Data to be inserted into the table
 188  * \return true if insertion was successful, false otherwise (table is full)
 189  *
 190  * \note The key for the element to insert is extract from the data with
 191  * the hook. This means that this function cannot be called for hashtables
 192  * with internal keys.
 193  *
 194  * \note If an element with the same key already exists in the table,
 195  * it will be overwritten.
 196  *
 197  * \note It is not allowed to store NULL in the table. If you pass NULL as data,
 198  * the function call will fail.
 199  */
 200 bool ht_insert(struct HashTable* ht, const void* data);
 201
 202 /**
 203  * Insert an element into the hash table
 204  *
 205  * \param ht Handle of the hash table
 206  * \param key Key of the element
 207  * \param key_length Length of the key in characters
 208  * \param data Data to be inserted into the table
 209  * \return true if insertion was successful, false otherwise (table is full)
 210  *
 211  * \note If this function is called for hash table with external keys,
 212  * the key provided must be match the key that would be extracted with the
 213  * hook, otherwise the function will fail.
 214  *
 215  * \note If an element with the same key already exists in the table,
 216  * it will be overwritten.
 217  *
 218  * \note It is not allowed to store NULL in the table. If you pass NULL as data,
 219  * the function call will fail.
 220  */
 221 bool ht_insert_with_key(struct HashTable* ht, const void* key, uint8_t key_length, const void* data);
 222
 223 /**
 224  * Find an element in the hash table
 225  *
 226  * \param ht Handle of the hash table
 227  * \param key Key of the element
 228  * \param key_length Length of the key in characters
 229  * \return Data of the element, or NULL if no element was found for the given key.
 230  */
 231 const void* ht_find(struct HashTable* ht, const void* key, uint8_t key_length);
 232
 233 /** Similar to \c ht_insert_with_key() but \a key is an ASCIIZ string */
 234 #define ht_insert_str(ht, key, data)         ht_insert_with_key(ht, key, strlen(key), data)
 235
 236 /** Similar to \c ht_find() but \a key is an ASCIIZ string */
 237 #define ht_find_str(ht, key)                 ht_find(ht, key, strlen(key))
 238
 239 /// Get an iterator to the begin of the hash table \a ht
 240 INLINE HashIterator ht_iter_begin(struct HashTable* ht)
 241 {
 242         HashIterator h;
 243
 244         h.pos = &ht->mem[0];
 245         h.end = &ht->mem[1 << ht->max_elts_log2];
 246
 247         while (h.pos != h.end && !*h.pos)
 248                 ++h.pos;
 249
 250         return h;
 251 }
 252
 253 /**
 254  * Get an iterator to the (exclusive) end of the hash table \a ht
 255  *
 256  * \note Like in STL, the end iterator is not a valid iterator (you
 257  *       cannot call \c ht_iter_get() on it), and it must be used only to
 258  *       detect if we reached the end of the iteration (through \c ht_iter_cmp()).
 259  */
 260 INLINE HashIterator ht_iter_end(struct HashTable* ht)
 261 {
 262         HashIterator h;
 263
 264         h.pos = h.end = &ht->mem[1 << ht->max_elts_log2];
 265
 266         return h;
 267 }
 268
 269 /// Compare \a it1 and \a it2 for equality
 270 INLINE bool ht_iter_cmp(HashIterator it1, HashIterator it2)
 271 {
 272         ASSERT(it1.end == it2.end);
 273         return it1.pos == it2.pos;
 274 }
 275
 276 /// Get the element within the hash table \a ht pointed by the iterator \a iter
 277 INLINE const void* ht_iter_get(HashIterator iter)
 278 { return *iter.pos; }
 279
 280 /** Return an iterator pointing to the element following \a h
 281  *
 282  * \note The order of the elements visited during the iteration is casual,
 283  * and depends on the implementation.
 284  *
 285  */
 286 INLINE HashIterator ht_iter_next(HashIterator h)
 287 {
 288         ++h.pos;
 289         while (h.pos != h.end && !(*h.pos))
 290                 ++h.pos;
 291
 292         return h;
 293 }
 294
 295 int hashtable_testSetup(void);
 296 int hashtable_testRun(void);
 297 int hashtable_testTearDown(void);
 298
 299 /** \} */ // \defgroup hashtable
 300
 301 #endif /* STRUCT_HASHTABLE_H */