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