Aggiornato il comment block dei log RCS
[bertos.git] / 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.4  2004/08/25 14:12:09  rasky
35  *#* Aggiornato il comment block dei log RCS
36  *#*
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.
39  *#*
40  *#* Revision 1.2  2004/08/04 15:52:54  rasky
41  *#* Merge da SC: fixato namespace dell'include guard
42  *#*
43  *#* Revision 1.1  2004/07/14 14:08:16  rasky
44  *#* Implementazione di una tabella hash
45  *#*
46  *#* Revision 1.10  2004/06/14 15:17:15  rasky
47  *#* Qualche fix alla documentazione Doxygen
48  *#*
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
52  *#*
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
55  *#*
56  *#* Revision 1.7  2004/06/12 15:18:05  rasky
57  *#* Nuova hashtable con chiave esterna o interna a scelta, come discusso
58  *#*
59  *#* Revision 1.6  2004/05/26 16:33:31  rasky
60  *#* Aggiunta interfaccia per visita della hashtable tramite iteratori
61  *#*
62  *#* Revision 1.5  2004/05/24 18:42:23  rasky
63  *#* Fixato un commento doxygen
64  *#*
65  *#* Revision 1.4  2004/05/24 15:28:20  rasky
66  *#* Sistemata la documentazione, rimossa keycmp in favore della memcmp
67  *#*
68  *#*/
69
70
71 #ifndef MWARE_HASHTABLE_H
72 #define MWARE_HASHTABLE_H
73
74 #include <compiler.h>
75 #include <macros.h>
76 #include <drv/kdebug.h>
77
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.
80  */
81 #define CONFIG_HT_OPTIONAL_INTERNAL_KEY      1
82
83 //! Maximum length of the internal key (use (2^n)-1 for slight speedup)
84 #define INTERNAL_KEY_MAX_LENGTH     15
85
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).
88  */
89 typedef const void* (*hook_get_key)(const void* data, uint8_t* key_length);
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 //! Iterator to walk the hash table
114 typedef struct
115 {
116         const void** pos;
117         const void** end;
118 } HashIterator;
119
120 /*! Declare a hash table in the current scope
121  *
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
125  *
126  * \note The number of elements will be rounded down to the nearest
127  * power of two.
128  *
129  */
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 }
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         static const void* name##_nodes[1 << UINT32_LOG2(size)]; \
137         static struct HashTable name = { name##_nodes, UINT32_LOG2(size), { false }, hook_gk }
138
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.
144          */
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 }
149
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 }
155 #endif
156
157 /*! Initialize (and clear) a hash table in a memory buffer.
158  *
159  * \param ht Hash table declared with \c DECLARE_HASHTABLE
160  *
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.
164  */
165 void ht_init(struct HashTable* ht);
166
167 /*! Insert an element into the hash table
168  *
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)
172  *
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.
176  *
177  * \note If an element with the same key already exists in the table,
178  * it will be overwritten.
179  *
180  * \note It is not allowed to store NULL in the table. If you pass NULL as data,
181  * the function call will fail.
182  */
183 bool ht_insert(struct HashTable* ht, const void* data);
184
185 /*! Insert an element into the hash table
186  *
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)
192  *
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.
196  *
197  * \note If an element with the same key already exists in the table,
198  * it will be overwritten.
199  *
200  * \note It is not allowed to store NULL in the table. If you pass NULL as data,
201  * the function call will fail.
202  */
203 bool ht_insert_with_key(struct HashTable* ht, const void* key, uint8_t key_length, const void* data);
204
205 /*! Find an element in the hash table
206  *
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.
211  */
212 const void* ht_find(struct HashTable* ht, const void* key, uint8_t key_length);
213
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)
216
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))
219
220 //! Get an iterator to the begin of the hash table \a ht
221 INLINE HashIterator ht_iter_begin(struct HashTable* ht)
222 {
223         HashIterator h;
224
225         h.pos = &ht->mem[0];
226         h.end = &ht->mem[1 << ht->max_elts_log2];
227
228         while (h.pos != h.end && !*h.pos)
229                 ++h.pos;
230
231         return h;
232 }
233
234 /*! Get an iterator to the (exclusive) end of the hash table \a ht
235  *
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()).
239  */
240 INLINE HashIterator ht_iter_end(struct HashTable* ht)
241 {
242         HashIterator h;
243
244         h.pos = h.end = &ht->mem[1 << ht->max_elts_log2];
245
246         return h;
247 }
248
249 //! Compare \a it1 and \a it2 for equality
250 INLINE bool ht_iter_cmp(HashIterator it1, HashIterator it2)
251 {
252         ASSERT(it1.end == it2.end);
253         return it1.pos == it2.pos;
254 }
255
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; }
259
260 /*! Return an iterator pointing to the element following \a h
261  *
262  * \note The order of the elements visited during the iteration is casual,
263  * and depends on the implementation.
264  *
265  */
266 INLINE HashIterator ht_iter_next(HashIterator h)
267 {
268         ++h.pos;
269         while (h.pos != h.end && !(*h.pos))
270                 ++h.pos;
271
272         return h;
273 }
274
275 #endif /* MWARE_HASHTABLE_H */