Fix naming conventions.
[bertos.git] / mware / hashtable.h
1 /*!
2  * \file
3  * <!--
4  * Copyright 2004 Develer S.r.l. (http://www.develer.com/)
5  * Copyright 2004 Giovanni Bajo
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.6  2005/04/11 19:10:28  bernie
35  *#* Include top-level headers from cfg/ subdir.
36  *#*
37  *#* Revision 1.5  2004/10/03 20:43:22  bernie
38  *#* Import changes from sc/firmware.
39  *#*
40  *#* Revision 1.9  2004/06/14 15:15:24  rasky
41  *#* Cambiato key_data in un union invece di castare
42  *#* Aggiunto un ASSERT sull'indice calcolata nella key_internal_get_ptr
43  *#*
44  *#* Revision 1.8  2004/06/14 14:59:40  rasky
45  *#* Rinominanta la macro di configurazione per rispettare il namespace, e aggiunta in un punto in cui mancava
46  *#*
47  *#* Revision 1.7  2004/06/12 15:18:05  rasky
48  *#* Nuova hashtable con chiave esterna o interna a scelta, come discusso
49  *#*
50  *#* Revision 1.6  2004/05/26 16:33:31  rasky
51  *#* Aggiunta interfaccia per visita della hashtable tramite iteratori
52  *#*
53  *#* Revision 1.5  2004/05/24 18:42:23  rasky
54  *#* Fixato un commento doxygen
55  *#*
56  *#* Revision 1.4  2004/05/24 15:28:20  rasky
57  *#* Sistemata la documentazione, rimossa keycmp in favore della memcmp
58  *#*/
59
60 #ifndef MWARE_HASHTABLE_H
61 #define MWARE_HASHTABLE_H
62
63 #include <cfg/compiler.h>
64 #include <cfg/macros.h>
65 #include <cfg/debug.h>
66
67 /*!
68  * Enable/disable support to declare special hash tables which maintain a copy of
69  * the key internally instead of relying on the hook to extract it from the data.
70  */
71 #define CONFIG_HT_OPTIONAL_INTERNAL_KEY      1
72
73 //! Maximum length of the internal key (use (2^n)-1 for slight speedup)
74 #define INTERNAL_KEY_MAX_LENGTH     15
75
76 /*!
77  * Hook to get the key from \a data, which is an element of the hash table. The
78  * key must be returned together with \a key_length (in words).
79  */
80 typedef const void* (*hook_get_key)(const void* data, uint8_t* key_length);
81
82
83 /*!
84  * Hash table description
85  *
86  * \note This structures MUST NOT be accessed directly. Its definition is
87  * provided in the header file only for optimization purposes (see the rationale
88  * in hashtable.c).
89  *
90  * \note If new elements must be added to this list, please double check
91  * \c DECLARE_HASHTABLE, which requires the existing elements to be at the top.
92  */
93 struct HashTable
94 {
95         const void** mem;            //!< Buckets of data
96         uint16_t max_elts_log2;      //!< Log2 of the size of the table
97         struct {
98                 bool key_internal : 1;   //!< true if the key is copied internally
99         } flags;
100         union {
101                 hook_get_key hook;       //!< Hook to get the key
102                 uint8_t* mem;            //!< Pointer to the key memory
103         } key_data;
104 };
105
106
107 //! Iterator to walk the hash table
108 typedef struct
109 {
110         const void** pos;
111         const void** end;
112 } HashIterator;
113
114
115 /*!
116  * Declare a hash table in the current scope
117  *
118  * \param name Variable name
119  * \param size Number of elements
120  * \param hook_gk Hook to be used to extract the key from the node
121  *
122  * \note The number of elements will be rounded down to the nearest
123  * power of two.
124  *
125  */
126 #define DECLARE_HASHTABLE(name, size, hook_gk) \
127         static const void* name##_nodes[1 << UINT32_LOG2(size)]; \
128         struct HashTable name = { name##_nodes, UINT32_LOG2(size), { false }, hook_gk }
129
130 /*! Exactly like \c DECLARE_HASHTABLE, but the variable will be declared as static. */
131 #define DECLARE_HASHTABLE_STATIC(name, size, hook_gk) \
132         static const void* name##_nodes[1 << UINT32_LOG2(size)]; \
133         static struct HashTable name = { name##_nodes, UINT32_LOG2(size), { false }, hook_gk }
134
135 #if CONFIG_HT_OPTIONAL_INTERNAL_KEY
136         /*! Declare a hash table with internal copies of the keys. This version does not
137          *  require a hook, nor it requires the user to allocate static memory for the keys.
138          *  It is mostly suggested for tables whose keys are computed on the fly and need
139          *  to be stored somewhere.
140          */
141         #define DECLARE_HASHTABLE_INTERNALKEY(name, size) \
142                 static uint8_t name##_keys[(1 << UINT32_LOG2(size)) * (INTERNAL_KEY_MAX_LENGTH + 1)]; \
143                 static const void* name##_nodes[1 << UINT32_LOG2(size)]; \
144                 struct HashTable name = { name##_nodes, UINT32_LOG2(size), { true }, name##_keys }
145
146         /*! Exactly like \c DECLARE_HASHTABLE_INTERNALKEY, but the variable will be declared as static. */
147         #define DECLARE_HASHTABLE_INTERNALKEY_STATIC(name, size) \
148                 static uint8_t name##_keys[(1 << UINT32_LOG2(size)) * (INTERNAL_KEY_MAX_LENGTH + 1)]; \
149                 static const void* name##_nodes[1 << UINT32_LOG2(size)]; \
150                 static struct HashTable name = { name##_nodes, UINT32_LOG2(size), { true }, name##_keys }
151 #endif
152
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 /*!
165  * Insert an element into the hash table
166  *
167  * \param ht Handle of the hash table
168  * \param data Data to be inserted into the table
169  * \return true if insertion was successful, false otherwise (table is full)
170  *
171  * \note The key for the element to insert is extract from the data with
172  * the hook. This means that this function cannot be called for hashtables
173  * with internal keys.
174  *
175  * \note If an element with the same key already exists in the table,
176  * it will be overwritten.
177  *
178  * \note It is not allowed to store NULL in the table. If you pass NULL as data,
179  * the function call will fail.
180  */
181 bool ht_insert(struct HashTable* ht, const void* data);
182
183 /*!
184  * Insert an element into the hash table
185  *
186  * \param ht Handle of the hash table
187  * \param key Key of the element
188  * \param key_length Length of the key in characters
189  * \param data Data to be inserted into the table
190  * \return true if insertion was successful, false otherwise (table is full)
191  *
192  * \note If this function is called for hash table with external keys,
193  * the key provided must be match the key that would be extracted with the
194  * hook, otherwise the function will fail.
195  *
196  * \note If an element with the same key already exists in the table,
197  * it will be overwritten.
198  *
199  * \note It is not allowed to store NULL in the table. If you pass NULL as data,
200  * the function call will fail.
201  */
202 bool ht_insert_with_key(struct HashTable* ht, const void* key, uint8_t key_length, const void* data);
203
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 /*!
235  * Get an iterator to the (exclusive) end of the hash table \a ht
236  *
237  * \note Like in STL, the end iterator is not a valid iterator (you
238  *       cannot call \c ht_iter_get() on it), and it must be used only to
239  *       detect if we reached the end of the iteration (through \c ht_iter_cmp()).
240  */
241 INLINE HashIterator ht_iter_end(struct HashTable* ht)
242 {
243         HashIterator h;
244
245         h.pos = h.end = &ht->mem[1 << ht->max_elts_log2];
246
247         return h;
248 }
249
250 //! Compare \a it1 and \a it2 for equality
251 INLINE bool ht_iter_cmp(HashIterator it1, HashIterator it2)
252 {
253         ASSERT(it1.end == it2.end);
254         return it1.pos == it2.pos;
255 }
256
257 //! Get the element within the hash table \a ht pointed by the iterator \a iter
258 INLINE const void* ht_iter_get(HashIterator iter)
259 { return *iter.pos; }
260
261 /*! Return an iterator pointing to the element following \a h
262  *
263  * \note The order of the elements visited during the iteration is casual,
264  * and depends on the implementation.
265  *
266  */
267 INLINE HashIterator ht_iter_next(HashIterator h)
268 {
269         ++h.pos;
270         while (h.pos != h.end && !(*h.pos))
271                 ++h.pos;
272
273         return h;
274 }
275
276 #endif /* MWARE_HASHTABLE_H */