Add demo application.
[bertos.git] / mware / hashtable.c
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 implementation
10  *
11  * Some rationales of our choices in implementation:
12  *
13  * \li For embedded systems, it is vital to allocate the table in static memory. To do
14  * so, it is necessary to expose the \c HashNode and \c HashTable structures in the header file.
15  * Nevertheless, they should be used as opaque types (that is, the users should not
16  * access the structure fields directly).
17  *
18  * \li To statically allocate the structures, a macro is provided. With this macro, we
19  * are hiding completely \c HashNode to the user (who only manipulates \c HashTable). Without
20  * the macro, the user would have had to define both the \c HashNode and the \c HashTable
21  * manually, and pass both of them to \c ht_init() (which would have created the link between
22  * the two). Instead, the link is created with a literal initialization.
23  *
24  * \li The hash table is created as power of two to remove the divisions from the code.
25  * Of course, hash functions work at their best when the table size is a prime number.
26  * When calculating the modulus to convert the hash value to an index, the actual operation
27  * becomes a bitwise AND: this is fast, but truncates the value losing bits. Thus, the higher
28  * bits are first "merged" with the lower bits through some XOR operations (see the last line of
29  * \c calc_hash()).
30  *
31  * \li To minimize the memory occupation, there is no flag to set for the empty node. An
32  * empty node is recognized by its data pointer set to NULL. It is then invalid to store
33  * NULL as data pointer in the table.
34  *
35  * \li The visiting interface through iterators is implemented with pass-by-value semantic.
36  * While this is overkill for medium-to-stupid compilers, it is the best designed from an
37  * user point of view. Moreover, being totally inlined (defined completely in the header),
38  * even a stupid compiler should be able to perform basic optimizations on it.
39  * We thought about using a pass-by-pointer semantic but it was much more awful to use, and
40  * the compiler is then forced to spill everything to the stack (unless it is *very* smart).
41  *
42  * \li The current implementation allows to either store the key internally (that is, copy
43  * the key within the hash table) or keep it external (that is, a hook is used to extract
44  * the key from the data in the node). The former is more memory-hungry of course, as it
45  * allocated static space to store the key copies. The overhead to keep both methods at
46  * the same time is minimal:
47  *    <ul>
48  *    <li>There is a run-time check in node_get_key which is execute per each node visited.</li>
49  *    <li>Theoretically, there is no memory overhead. In practice, there were no
50  *        flags in \c struct HashTable till now, so we had to add a first bit flag, but the
51  *        overhead will disappear if a second flag is added for a different reason later.</li>
52  *    <li>There is a little interface overhead, since we have two different versions of
53  *        \c ht_insert(), one with the key passed as parameter and one without, but in
54  *        the common case (external keys) both can be used.</li>
55  *    </ul>
56  *
57  * \version $Id$
58  *
59  * \author Giovanni Bajo <rasky@develer.com>
60  */
61
62 /*#*
63  *#* $Log$
64  *#* Revision 1.5  2005/04/11 19:10:28  bernie
65  *#* Include top-level headers from cfg/ subdir.
66  *#*
67  *#* Revision 1.4  2004/12/08 09:42:30  bernie
68  *#* Suppress warning.
69  *#*
70  *#* Revision 1.3  2004/10/03 20:43:22  bernie
71  *#* Import changes from sc/firmware.
72  *#*
73  *#* Revision 1.12  2004/06/14 15:15:24  rasky
74  *#* Cambiato key_data in un union invece di castare
75  *#* Aggiunto un ASSERT sull'indice calcolata nella key_internal_get_ptr
76  *#*
77  *#* Revision 1.11  2004/06/14 15:09:04  rasky
78  *#* Cambiati i messaggi di assert (è inutile citare il nome della funzione)
79  *#*
80  *#* Revision 1.10  2004/06/14 15:07:38  rasky
81  *#* Convertito il loop di calc_hash a interi (per farlo ottimizzare maggiormente)
82  *#*
83  *#* Revision 1.9  2004/06/14 14:59:40  rasky
84  *#* Rinominanta la macro di configurazione per rispettare il namespace, e aggiunta in un punto in cui mancava
85  *#*
86  *#* Revision 1.8  2004/06/12 15:18:05  rasky
87  *#* Nuova hashtable con chiave esterna o interna a scelta, come discusso
88  *#*
89  *#* Revision 1.7  2004/06/04 17:16:31  rasky
90  *#* Fixato un bug nel caso in cui la chiave ecceda la dimensione massima: il clamp non può essere fatto dentro la perform_lookup perché anche la ht_insert deve avere il valore clampato a disposizione per fare la memcpy
91  *#*
92  *#* Revision 1.6  2004/05/26 16:36:50  rasky
93  *#* Aggiunto il rationale per l'interfaccia degli iteratori
94  *#*
95  *#* Revision 1.5  2004/05/24 15:28:20  rasky
96  *#* Sistemata la documentazione, rimossa keycmp in favore della memcmp
97  *#*
98  *#*/
99
100 #include "hashtable.h"
101 #include <cfg/debug.h>
102 #include <cfg/compiler.h>
103
104 #include <string.h>
105
106
107 #define ROTATE_LEFT_16(num, count)     (((num) << (count)) | ((num) >> (16-(count))))
108 #define ROTATE_RIGHT_16(num, count)    ROTATE_LEFT_16(num, 16-(count))
109
110 typedef const void** HashNodePtr;
111 #define NODE_EMPTY(node)               (!*(node))
112 #define HT_HAS_INTERNAL_KEY(ht)        (CONFIG_HT_OPTIONAL_INTERNAL_KEY && ht->flags.key_internal)
113
114 /*! For hash tables with internal keys, compute the pointer to the internal key for a given \a node. */
115 INLINE uint8_t* key_internal_get_ptr(struct HashTable* ht, HashNodePtr node)
116 {
117         uint8_t* key_buf = ht->key_data.mem;
118         size_t index;
119
120         // Compute the index of the node and use it to move within the whole key buffer
121         index = node - &ht->mem[0];
122         ASSERT(index < (1 << ht->max_elts_log2));
123         key_buf += index * (INTERNAL_KEY_MAX_LENGTH + 1);
124
125         return key_buf;
126 }
127
128
129 INLINE void node_get_key(struct HashTable* ht, HashNodePtr node, const void** key, uint8_t* key_length)
130 {
131         if (HT_HAS_INTERNAL_KEY(ht))
132         {
133                 uint8_t* k = key_internal_get_ptr(ht, node);
134
135                 // Key has its length stored in the first byte
136                 *key_length = *k++;
137                 *key = k;
138         }
139         else
140                 *key = ht->key_data.hook(*node, key_length);
141 }
142
143
144 INLINE bool node_key_match(struct HashTable* ht, HashNodePtr node, const void* key, uint8_t key_length)
145 {
146         const void* key2;
147         uint8_t key2_length;
148
149         node_get_key(ht, node, &key2, &key2_length);
150
151         return (key_length == key2_length && memcmp(key, key2, key_length) == 0);
152 }
153
154
155 static uint16_t calc_hash(const void* _key, uint8_t key_length)
156 {
157         const char* key = (const char*)_key;
158         uint16_t hash = key_length;
159         int i;
160         int len = (int)key_length;
161
162         for (i = 0; i < len; ++i)
163                 hash = ROTATE_LEFT_16(hash, 4) ^ key[i];
164
165         return hash ^ (hash >> 6) ^ (hash >> 13);
166 }
167
168
169 static HashNodePtr perform_lookup(struct HashTable* ht,
170                                   const void* key, uint8_t key_length)
171 {
172         uint16_t hash = calc_hash(key, key_length);
173         uint16_t mask = ((1 << ht->max_elts_log2) - 1);
174         uint16_t index = hash & mask;
175         uint16_t first_index = index;
176         uint16_t step;
177         HashNodePtr node;
178
179         // Fast-path optimization: we check immediately if the current node
180         //  is the one we were looking for, so we save the computation of the
181         //  increment step in the common case.
182         node = &ht->mem[index];
183         if (NODE_EMPTY(node)
184                 || node_key_match(ht, node, key, key_length))
185                 return node;
186
187         // Increment while going through the hash table in case of collision.
188         //  This implements the double-hash technique: we use the higher part
189         //  of the hash as a step increment instead of just going to the next
190         //  element, to minimize the collisions.
191         // Notice that the number must be odd to be sure that the whole table
192         //  is traversed. Actually MCD(table_size, step) must be 1, but
193         //  table_size is always a power of 2, so we just ensure that step is
194         //  never a multiple of 2.
195         step = (ROTATE_RIGHT_16(hash, ht->max_elts_log2) & mask) | 1;
196
197         do
198         {
199                 index += step;
200                 index &= mask;
201
202                 node = &ht->mem[index];
203                 if (NODE_EMPTY(node)
204                         || node_key_match(ht, node, key, key_length))
205                         return node;
206
207                 // The check is done after the key compare. This actually causes
208                 //  one more compare in the case the table is full (since the first
209                 //  element was compared at the very start, and then at the end),
210                 //  but it makes faster the common path where we enter this loop
211                 //  for the first time, and index will not match first_index for
212                 //  sure.
213         } while (index != first_index);
214
215         return NULL;
216 }
217
218
219 void ht_init(struct HashTable* ht)
220 {
221         memset(ht->mem, 0, sizeof(ht->mem[0]) * (1 << ht->max_elts_log2));
222 }
223
224
225 static bool insert(struct HashTable* ht, const void* key, uint8_t key_length, const void* data)
226 {
227         HashNodePtr node;
228
229         if (!data)
230                 return false;
231
232         if (HT_HAS_INTERNAL_KEY(ht))
233                 key_length = MIN(key_length, (uint8_t)INTERNAL_KEY_MAX_LENGTH);
234
235         node = perform_lookup(ht, key, key_length);
236         if (!node)
237                 return false;
238
239         if (HT_HAS_INTERNAL_KEY(ht))
240         {
241                 uint8_t* k = key_internal_get_ptr(ht, node);
242                 *k++ = key_length;
243                 memcpy(k, key, key_length);
244         }
245
246         *node = data;
247         return true;
248 }
249
250
251 bool ht_insert_with_key(struct HashTable* ht, const void* key, uint8_t key_length, const void* data)
252 {
253 #ifdef _DEBUG
254         if (!HT_HAS_INTERNAL_KEY(ht))
255         {
256                 // Construct a fake node and use it to match the key
257                 HashNodePtr node = &data;
258                 if (!node_key_match(ht, node, key, key_length))
259                 {
260                         ASSERT2(0, "parameter key is different from the external key");
261                         return false;
262                 }
263         }
264 #endif
265
266         return insert(ht, key, key_length, data);
267 }
268
269
270 bool ht_insert(struct HashTable* ht, const void* data)
271 {
272         const void* key;
273         uint8_t key_length;
274
275 #ifdef _DEBUG
276         if (HT_HAS_INTERNAL_KEY(ht))
277         {
278                 ASSERT("parameter cannot be a hash table with internal keys - use ht_insert_with_key()"
279                        && 0);
280                 return false;
281         }
282 #endif
283
284         key = ht->key_data.hook(data, &key_length);
285
286         return insert(ht, key, key_length, data);
287 }
288
289
290 const void* ht_find(struct HashTable* ht, const void* key, uint8_t key_length)
291 {
292         HashNodePtr node;
293
294         if (HT_HAS_INTERNAL_KEY(ht))
295                 key_length = MIN(key_length, (uint8_t)INTERNAL_KEY_MAX_LENGTH);
296
297         node = perform_lookup(ht, key, key_length);
298
299         if (!node || NODE_EMPTY(node))
300                 return NULL;
301
302         return *node;
303 }
304
305
306 #if 0
307
308 #include <stdlib.h>
309
310 bool ht_test(void);
311
312 static const void* test_get_key(const void* ptr, uint8_t* length)
313 {
314         const char* s = ptr;
315         *length = strlen(s);
316         return s;
317 }
318
319 #define NUM_ELEMENTS   256
320 DECLARE_HASHTABLE_STATIC(test1, 256, test_get_key);
321 DECLARE_HASHTABLE_INTERNALKEY_STATIC(test2, 256);
322
323 static char data[NUM_ELEMENTS][10];
324 static char keydomain[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
325
326 static bool single_test(void)
327 {
328         int i;
329
330         ht_init(&test1);
331         ht_init(&test2);
332
333         for (i=0;i<NUM_ELEMENTS;i++)
334         {
335                 int k;
336                 int klen;
337
338                 do
339                 {
340                         klen = (rand() % 8) + 1;
341                         for (k=0;k<klen;k++)
342                                 data[i][k] = keydomain[rand() % (sizeof(keydomain)-1)];
343                         data[i][k]=0;
344                 } while (ht_find_str(&test1, data[i]) != NULL);
345
346                 ASSERT(ht_insert(&test1, data[i]));
347                 ASSERT(ht_insert_str(&test2, data[i], data[i]));
348         }
349
350         for (i=0;i<NUM_ELEMENTS;i++)
351         {
352                 char *found1, *found2;
353
354                 found1 = (char*)ht_find_str(&test1, data[i]);
355                 if (strcmp(found1, data[i]) != 0)
356                 {
357                         ASSERT(strcmp(found1,data[i]) == 0);
358                         return false;
359                 }
360
361                 found2 = (char*)ht_find_str(&test2, data[i]);
362                 if (strcmp(found2, data[i]) != 0)
363                 {
364                         ASSERT(strcmp(found2,data[i]) == 0);
365                         return false;
366                 }
367         }
368
369         return true;
370 }
371
372 static uint16_t rand_seeds[] = { 1, 42, 666, 0xDEAD, 0xBEEF, 0x1337, 0xB00B };
373
374 bool ht_test(void)
375 {
376         int i;
377
378         for (i=0;i<countof(rand_seeds);++i)
379         {
380                 srand(rand_seeds[i]);
381                 if (!single_test())
382                 {
383                         kprintf("ht_test failed\n");
384                         return false;
385                 }
386         }
387
388         kprintf("ht_test successful\n");
389         return true;
390 }
391
392 #endif