mware/hashtable.h

   1 /*!
   2  * \file
   3  * <!--
   4  * Copyright (C) 2004 Giovanni Bajo
   5  * Copyright (C) 2004 Develer S.r.l. (http://www.develer.com/)
   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.3  2004/08/14 19:37:57  rasky
  35  * Merge da SC: macros.h, pool.h, BIT_CHANGE, nome dei processi, etc.
  36  *
  37  * Revision 1.2  2004/08/04 15:52:54  rasky
  38  * Merge da SC: fixato namespace dell'include guard
  39  *
  40  * Revision 1.1  2004/07/14 14:08:16  rasky
  41  * Implementazione di una tabella hash
  42  *
  43  * Revision 1.10  2004/06/14 15:17:15  rasky
  44  * Qualche fix alla documentazione Doxygen
  45  *
  46  * Revision 1.9  2004/06/14 15:15:24  rasky
  47  * Cambiato key_data in un union invece di castare
  48  * Aggiunto un ASSERT sull'indice calcolata nella key_internal_get_ptr
  49  *
  50  * Revision 1.8  2004/06/14 14:59:40  rasky
  51  * Rinominanta la macro di configurazione per rispettare il namespace, e aggiunta in un punto in cui mancava
  52  *
  53  * Revision 1.7  2004/06/12 15:18:05  rasky
  54  * Nuova hashtable con chiave esterna o interna a scelta, come discusso
  55  *
  56  * Revision 1.6  2004/05/26 16:33:31  rasky
  57  * Aggiunta interfaccia per visita della hashtable tramite iteratori
  58  *
  59  * Revision 1.5  2004/05/24 18:42:23  rasky
  60  * Fixato un commento doxygen
  61  *
  62  * Revision 1.4  2004/05/24 15:28:20  rasky
  63  * Sistemata la documentazione, rimossa keycmp in favore della memcmp
  64  *
  65  */
  66
  67
  68 #ifndef MWARE_HASHTABLE_H
  69 #define MWARE_HASHTABLE_H
  70
  71 #include <compiler.h>
  72 #include <macros.h>
  73 #include <drv/kdebug.h>
  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 /*! Hook to get the key from \a data, which is an element of the hash table. The
  84  *  key must be returned together with \a key_length (in words).
  85  */
  86 typedef const void* (*hook_get_key)(const void* data, uint8_t* key_length);
  87
  88 /*! Hash table description
  89  *
  90  * \note This structures MUST NOT be accessed directly. Its definition is
  91  * provided in the header file only for optimization purposes (see the rationale
  92  * in hashtable.c).
  93  *
  94  * \note If new elements must be added to this list, please double check
  95  * \c DECLARE_HASHTABLE, which requires the existing elements to be at the top.
  96  */
  97 struct HashTable
  98 {
  99         const void** mem;            //!< Buckets of data
 100         uint16_t max_elts_log2;      //!< Log2 of the size of the table
 101         struct {
 102                 bool key_internal : 1;   //!< true if the key is copied internally
 103         } flags;
 104         union {
 105                 hook_get_key hook;       //!< Hook to get the key
 106                 uint8_t* mem;            //!< Pointer to the key memory
 107         } key_data;
 108 };
 109
 110 //! Iterator to walk the hash table
 111 typedef struct
 112 {
 113         const void** pos;
 114         const void** end;
 115 } HashIterator;
 116
 117 /*! Declare a hash table in the current scope
 118  *
 119  * \param name Variable name
 120  * \param size Number of elements
 121  * \param hook_gk Hook to be used to extract the key from the node
 122  *
 123  * \note The number of elements will be rounded down to the nearest
 124  * power of two.
 125  *
 126  */
 127 #define DECLARE_HASHTABLE(name, size, hook_gk) \
 128         static const void* name##_nodes[1 << UINT32_LOG2(size)]; \
 129         struct HashTable name = { name##_nodes, UINT32_LOG2(size), { false }, hook_gk }
 130
 131 /*! Exactly like \c DECLARE_HASHTABLE, but the variable will be declared as static. */
 132 #define DECLARE_HASHTABLE_STATIC(name, size, hook_gk) \
 133         static const void* name##_nodes[1 << UINT32_LOG2(size)]; \
 134         static struct HashTable name = { name##_nodes, UINT32_LOG2(size), { false }, hook_gk }
 135
 136 #if CONFIG_HT_OPTIONAL_INTERNAL_KEY
 137         /*! Declare a hash table with internal copies of the keys. This version does not
 138          *  require a hook, nor it requires the user to allocate static memory for the keys.
 139          *  It is mostly suggested for tables whose keys are computed on the fly and need
 140          *  to be stored somewhere.
 141          */
 142         #define DECLARE_HASHTABLE_INTERNALKEY(name, size) \
 143                 static uint8_t name##_keys[(1 << UINT32_LOG2(size)) * (INTERNAL_KEY_MAX_LENGTH + 1)]; \
 144                 static const void* name##_nodes[1 << UINT32_LOG2(size)]; \
 145                 struct HashTable name = { name##_nodes, UINT32_LOG2(size), { true }, name##_keys }
 146
 147         /*! Exactly like \c DECLARE_HASHTABLE_INTERNALKEY, but the variable will be declared as static. */
 148         #define DECLARE_HASHTABLE_INTERNALKEY_STATIC(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                 static struct HashTable name = { name##_nodes, UINT32_LOG2(size), { true }, name##_keys }
 152 #endif
 153
 154 /*! Initialize (and clear) a hash table in a memory buffer.
 155  *
 156  * \param ht Hash table declared with \c DECLARE_HASHTABLE
 157  *
 158  * \note This function must be called before using the hash table. Optionally,
 159  * it can be called later in the program to clear the hash table,
 160  * removing all its elements.
 161  */
 162 void ht_init(struct HashTable* ht);
 163
 164 /*! Insert an element into the hash table
 165  *
 166  * \param ht Handle of the hash table
 167  * \param data Data to be inserted into the table
 168  * \return true if insertion was successful, false otherwise (table is full)
 169  *
 170  * \note The key for the element to insert is extract from the data with
 171  * the hook. This means that this function cannot be called for hashtables
 172  * with internal keys.
 173  *
 174  * \note If an element with the same key already exists in the table,
 175  * it will be overwritten.
 176  *
 177  * \note It is not allowed to store NULL in the table. If you pass NULL as data,
 178  * the function call will fail.
 179  */
 180 bool ht_insert(struct HashTable* ht, const void* data);
 181
 182 /*! Insert an element into the hash table
 183  *
 184  * \param ht Handle of the hash table
 185  * \param key Key of the element
 186  * \param key_length Length of the key in characters
 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 If this function is called for hash table with external keys,
 191  * the key provided must be match the key that would be extracted with the
 192  * hook, otherwise the function will fail.
 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_with_key(struct HashTable* ht, const void* key, uint8_t key_length, const void* data);
 201
 202 /*! Find an element in the hash table
 203  *
 204  * \param ht Handle of the hash table
 205  * \param key Key of the element
 206  * \param key_length Length of the key in characters
 207  * \return Data of the element, or NULL if no element was found for the given key.
 208  */
 209 const void* ht_find(struct HashTable* ht, const void* key, uint8_t key_length);
 210
 211 /*! Similar to \c ht_insert_with_key() but \a key is an ASCIIZ string */
 212 #define ht_insert_str(ht, key, data)         ht_insert_with_key(ht, key, strlen(key), data)
 213
 214 /*! Similar to \c ht_find() but \a key is an ASCIIZ string */
 215 #define ht_find_str(ht, key)                 ht_find(ht, key, strlen(key))
 216
 217 //! Get an iterator to the begin of the hash table \a ht
 218 INLINE HashIterator ht_iter_begin(struct HashTable* ht)
 219 {
 220         HashIterator h;
 221
 222         h.pos = &ht->mem[0];
 223         h.end = &ht->mem[1 << ht->max_elts_log2];
 224
 225         while (h.pos != h.end && !*h.pos)
 226                 ++h.pos;
 227
 228         return h;
 229 }
 230
 231 /*! Get an iterator to the (exclusive) end of the hash table \a ht
 232  *
 233  *  \note Like in STL, the end iterator is not a valid iterator (you
 234  *  cannot call \c ht_iter_get() on it), and it must be used only to
 235  *  detect if we reached the end of the iteration (through \c ht_iter_cmp()).
 236  */
 237 INLINE HashIterator ht_iter_end(struct HashTable* ht)
 238 {
 239         HashIterator h;
 240
 241         h.pos = h.end = &ht->mem[1 << ht->max_elts_log2];
 242
 243         return h;
 244 }
 245
 246 //! Compare \a it1 and \a it2 for equality
 247 INLINE bool ht_iter_cmp(HashIterator it1, HashIterator it2)
 248 {
 249         ASSERT(it1.end == it2.end);
 250         return it1.pos == it2.pos;
 251 }
 252
 253 //! Get the element within the hash table \a ht pointed by the iterator \a iter
 254 INLINE const void* ht_iter_get(HashIterator iter)
 255 { return *iter.pos; }
 256
 257 /*! Return an iterator pointing to the element following \a h
 258  *
 259  * \note The order of the elements visited during the iteration is casual,
 260  * and depends on the implementation.
 261  *
 262  */
 263 INLINE HashIterator ht_iter_next(HashIterator h)
 264 {
 265         ++h.pos;
 266         while (h.pos != h.end && !(*h.pos))
 267                 ++h.pos;
 268
 269         return h;
 270 }
 271
 272 #endif /* MWARE_HASHTABLE_H */