4 * Copyright (C) 2004 Giovanni Bajo
5 * Copyright (C) 2004 Develer S.r.l. (http://www.develer.com/)
9 * \brief Portable hash table
11 * This file implements a portable hash table, with the following features:
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.
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.
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().
29 * \author Giovanni Bajo <rasky@develer.com>
34 *#* Revision 1.4 2004/08/25 14:12:09 rasky
35 *#* Aggiornato il comment block dei log RCS
37 *#* Revision 1.3 2004/08/14 19:37:57 rasky
38 *#* Merge da SC: macros.h, pool.h, BIT_CHANGE, nome dei processi, etc.
40 *#* Revision 1.2 2004/08/04 15:52:54 rasky
41 *#* Merge da SC: fixato namespace dell'include guard
43 *#* Revision 1.1 2004/07/14 14:08:16 rasky
44 *#* Implementazione di una tabella hash
46 *#* Revision 1.10 2004/06/14 15:17:15 rasky
47 *#* Qualche fix alla documentazione Doxygen
49 *#* Revision 1.9 2004/06/14 15:15:24 rasky
50 *#* Cambiato key_data in un union invece di castare
51 *#* Aggiunto un ASSERT sull'indice calcolata nella key_internal_get_ptr
53 *#* Revision 1.8 2004/06/14 14:59:40 rasky
54 *#* Rinominanta la macro di configurazione per rispettare il namespace, e aggiunta in un punto in cui mancava
56 *#* Revision 1.7 2004/06/12 15:18:05 rasky
57 *#* Nuova hashtable con chiave esterna o interna a scelta, come discusso
59 *#* Revision 1.6 2004/05/26 16:33:31 rasky
60 *#* Aggiunta interfaccia per visita della hashtable tramite iteratori
62 *#* Revision 1.5 2004/05/24 18:42:23 rasky
63 *#* Fixato un commento doxygen
65 *#* Revision 1.4 2004/05/24 15:28:20 rasky
66 *#* Sistemata la documentazione, rimossa keycmp in favore della memcmp
71 #ifndef MWARE_HASHTABLE_H
72 #define MWARE_HASHTABLE_H
76 #include <drv/kdebug.h>
78 /*! Enable/disable support to declare special hash tables which maintain a copy of
79 * the key internally instead of relying on the hook to extract it from the data.
81 #define CONFIG_HT_OPTIONAL_INTERNAL_KEY 1
83 //! Maximum length of the internal key (use (2^n)-1 for slight speedup)
84 #define INTERNAL_KEY_MAX_LENGTH 15
86 /*! Hook to get the key from \a data, which is an element of the hash table. The
87 * key must be returned together with \a key_length (in words).
89 typedef const void* (*hook_get_key)(const void* data, uint8_t* key_length);
91 /*! Hash table description
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
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.
102 const void** mem; //!< Buckets of data
103 uint16_t max_elts_log2; //!< Log2 of the size of the table
105 bool key_internal : 1; //!< true if the key is copied internally
108 hook_get_key hook; //!< Hook to get the key
109 uint8_t* mem; //!< Pointer to the key memory
113 //! Iterator to walk the hash table
120 /*! Declare a hash table in the current scope
122 * \param name Variable name
123 * \param size Number of elements
124 * \param hook_gk Hook to be used to extract the key from the node
126 * \note The number of elements will be rounded down to the nearest
130 #define DECLARE_HASHTABLE(name, size, hook_gk) \
131 static const void* name##_nodes[1 << UINT32_LOG2(size)]; \
132 struct HashTable name = { name##_nodes, UINT32_LOG2(size), { false }, hook_gk }
134 /*! Exactly like \c DECLARE_HASHTABLE, but the variable will be declared as static. */
135 #define DECLARE_HASHTABLE_STATIC(name, size, hook_gk) \
136 static const void* name##_nodes[1 << UINT32_LOG2(size)]; \
137 static struct HashTable name = { name##_nodes, UINT32_LOG2(size), { false }, hook_gk }
139 #if CONFIG_HT_OPTIONAL_INTERNAL_KEY
140 /*! Declare a hash table with internal copies of the keys. This version does not
141 * require a hook, nor it requires the user to allocate static memory for the keys.
142 * It is mostly suggested for tables whose keys are computed on the fly and need
143 * to be stored somewhere.
145 #define DECLARE_HASHTABLE_INTERNALKEY(name, size) \
146 static uint8_t name##_keys[(1 << UINT32_LOG2(size)) * (INTERNAL_KEY_MAX_LENGTH + 1)]; \
147 static const void* name##_nodes[1 << UINT32_LOG2(size)]; \
148 struct HashTable name = { name##_nodes, UINT32_LOG2(size), { true }, name##_keys }
150 /*! Exactly like \c DECLARE_HASHTABLE_INTERNALKEY, but the variable will be declared as static. */
151 #define DECLARE_HASHTABLE_INTERNALKEY_STATIC(name, size) \
152 static uint8_t name##_keys[(1 << UINT32_LOG2(size)) * (INTERNAL_KEY_MAX_LENGTH + 1)]; \
153 static const void* name##_nodes[1 << UINT32_LOG2(size)]; \
154 static struct HashTable name = { name##_nodes, UINT32_LOG2(size), { true }, name##_keys }
157 /*! Initialize (and clear) a hash table in a memory buffer.
159 * \param ht Hash table declared with \c DECLARE_HASHTABLE
161 * \note This function must be called before using the hash table. Optionally,
162 * it can be called later in the program to clear the hash table,
163 * removing all its elements.
165 void ht_init(struct HashTable* ht);
167 /*! Insert an element into the hash table
169 * \param ht Handle of the hash table
170 * \param data Data to be inserted into the table
171 * \return true if insertion was successful, false otherwise (table is full)
173 * \note The key for the element to insert is extract from the data with
174 * the hook. This means that this function cannot be called for hashtables
175 * with internal keys.
177 * \note If an element with the same key already exists in the table,
178 * it will be overwritten.
180 * \note It is not allowed to store NULL in the table. If you pass NULL as data,
181 * the function call will fail.
183 bool ht_insert(struct HashTable* ht, const void* data);
185 /*! Insert an element into the hash table
187 * \param ht Handle of the hash table
188 * \param key Key of the element
189 * \param key_length Length of the key in characters
190 * \param data Data to be inserted into the table
191 * \return true if insertion was successful, false otherwise (table is full)
193 * \note If this function is called for hash table with external keys,
194 * the key provided must be match the key that would be extracted with the
195 * hook, otherwise the function will fail.
197 * \note If an element with the same key already exists in the table,
198 * it will be overwritten.
200 * \note It is not allowed to store NULL in the table. If you pass NULL as data,
201 * the function call will fail.
203 bool ht_insert_with_key(struct HashTable* ht, const void* key, uint8_t key_length, const void* data);
205 /*! Find an element in the hash table
207 * \param ht Handle of the hash table
208 * \param key Key of the element
209 * \param key_length Length of the key in characters
210 * \return Data of the element, or NULL if no element was found for the given key.
212 const void* ht_find(struct HashTable* ht, const void* key, uint8_t key_length);
214 /*! Similar to \c ht_insert_with_key() but \a key is an ASCIIZ string */
215 #define ht_insert_str(ht, key, data) ht_insert_with_key(ht, key, strlen(key), data)
217 /*! Similar to \c ht_find() but \a key is an ASCIIZ string */
218 #define ht_find_str(ht, key) ht_find(ht, key, strlen(key))
220 //! Get an iterator to the begin of the hash table \a ht
221 INLINE HashIterator ht_iter_begin(struct HashTable* ht)
226 h.end = &ht->mem[1 << ht->max_elts_log2];
228 while (h.pos != h.end && !*h.pos)
234 /*! Get an iterator to the (exclusive) end of the hash table \a ht
236 * \note Like in STL, the end iterator is not a valid iterator (you
237 * cannot call \c ht_iter_get() on it), and it must be used only to
238 * detect if we reached the end of the iteration (through \c ht_iter_cmp()).
240 INLINE HashIterator ht_iter_end(struct HashTable* ht)
244 h.pos = h.end = &ht->mem[1 << ht->max_elts_log2];
249 //! Compare \a it1 and \a it2 for equality
250 INLINE bool ht_iter_cmp(HashIterator it1, HashIterator it2)
252 ASSERT(it1.end == it2.end);
253 return it1.pos == it2.pos;
256 //! Get the element within the hash table \a ht pointed by the iterator \a iter
257 INLINE const void* ht_iter_get(HashIterator iter)
258 { return *iter.pos; }
260 /*! Return an iterator pointing to the element following \a h
262 * \note The order of the elements visited during the iteration is casual,
263 * and depends on the implementation.
266 INLINE HashIterator ht_iter_next(HashIterator h)
269 while (h.pos != h.end && !(*h.pos))
275 #endif /* MWARE_HASHTABLE_H */