4 * Copyright 2004 Develer S.r.l. (http://www.develer.com/)
5 * Copyright 2004 Giovanni Bajo
9 * \brief Portable hash table implementation
11 * Some rationales of our choices in implementation:
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).
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.
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
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.
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).
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:
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>
59 * \author Giovanni Bajo <rasky@develer.com>
64 *#* Revision 1.4 2004/12/08 09:42:30 bernie
67 *#* Revision 1.3 2004/10/03 20:43:22 bernie
68 *#* Import changes from sc/firmware.
70 *#* Revision 1.12 2004/06/14 15:15:24 rasky
71 *#* Cambiato key_data in un union invece di castare
72 *#* Aggiunto un ASSERT sull'indice calcolata nella key_internal_get_ptr
74 *#* Revision 1.11 2004/06/14 15:09:04 rasky
75 *#* Cambiati i messaggi di assert (è inutile citare il nome della funzione)
77 *#* Revision 1.10 2004/06/14 15:07:38 rasky
78 *#* Convertito il loop di calc_hash a interi (per farlo ottimizzare maggiormente)
80 *#* Revision 1.9 2004/06/14 14:59:40 rasky
81 *#* Rinominanta la macro di configurazione per rispettare il namespace, e aggiunta in un punto in cui mancava
83 *#* Revision 1.8 2004/06/12 15:18:05 rasky
84 *#* Nuova hashtable con chiave esterna o interna a scelta, come discusso
86 *#* Revision 1.7 2004/06/04 17:16:31 rasky
87 *#* 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
89 *#* Revision 1.6 2004/05/26 16:36:50 rasky
90 *#* Aggiunto il rationale per l'interfaccia degli iteratori
92 *#* Revision 1.5 2004/05/24 15:28:20 rasky
93 *#* Sistemata la documentazione, rimossa keycmp in favore della memcmp
97 #include "hashtable.h"
104 #define ROTATE_LEFT_16(num, count) (((num) << (count)) | ((num) >> (16-(count))))
105 #define ROTATE_RIGHT_16(num, count) ROTATE_LEFT_16(num, 16-(count))
107 typedef const void** HashNodePtr;
108 #define NODE_EMPTY(node) (!*(node))
109 #define HT_HAS_INTERNAL_KEY(ht) (CONFIG_HT_OPTIONAL_INTERNAL_KEY && ht->flags.key_internal)
111 /*! For hash tables with internal keys, compute the pointer to the internal key for a given \a node. */
112 INLINE uint8_t* key_internal_get_ptr(struct HashTable* ht, HashNodePtr node)
114 uint8_t* key_buf = ht->key_data.mem;
117 // Compute the index of the node and use it to move within the whole key buffer
118 index = node - &ht->mem[0];
119 ASSERT(index < (1 << ht->max_elts_log2));
120 key_buf += index * (INTERNAL_KEY_MAX_LENGTH + 1);
126 INLINE void node_get_key(struct HashTable* ht, HashNodePtr node, const void** key, uint8_t* key_length)
128 if (HT_HAS_INTERNAL_KEY(ht))
130 uint8_t* k = key_internal_get_ptr(ht, node);
132 // Key has its length stored in the first byte
137 *key = ht->key_data.hook(*node, key_length);
141 INLINE bool node_key_match(struct HashTable* ht, HashNodePtr node, const void* key, uint8_t key_length)
146 node_get_key(ht, node, &key2, &key2_length);
148 return (key_length == key2_length && memcmp(key, key2, key_length) == 0);
152 static uint16_t calc_hash(const void* _key, uint8_t key_length)
154 const char* key = (const char*)_key;
155 uint16_t hash = key_length;
157 int len = (int)key_length;
159 for (i = 0; i < len; ++i)
160 hash = ROTATE_LEFT_16(hash, 4) ^ key[i];
162 return hash ^ (hash >> 6) ^ (hash >> 13);
166 static HashNodePtr perform_lookup(struct HashTable* ht,
167 const void* key, uint8_t key_length)
169 uint16_t hash = calc_hash(key, key_length);
170 uint16_t mask = ((1 << ht->max_elts_log2) - 1);
171 uint16_t index = hash & mask;
172 uint16_t first_index = index;
176 // Fast-path optimization: we check immediately if the current node
177 // is the one we were looking for, so we save the computation of the
178 // increment step in the common case.
179 node = &ht->mem[index];
181 || node_key_match(ht, node, key, key_length))
184 // Increment while going through the hash table in case of collision.
185 // This implements the double-hash technique: we use the higher part
186 // of the hash as a step increment instead of just going to the next
187 // element, to minimize the collisions.
188 // Notice that the number must be odd to be sure that the whole table
189 // is traversed. Actually MCD(table_size, step) must be 1, but
190 // table_size is always a power of 2, so we just ensure that step is
191 // never a multiple of 2.
192 step = (ROTATE_RIGHT_16(hash, ht->max_elts_log2) & mask) | 1;
199 node = &ht->mem[index];
201 || node_key_match(ht, node, key, key_length))
204 // The check is done after the key compare. This actually causes
205 // one more compare in the case the table is full (since the first
206 // element was compared at the very start, and then at the end),
207 // but it makes faster the common path where we enter this loop
208 // for the first time, and index will not match first_index for
210 } while (index != first_index);
216 void ht_init(struct HashTable* ht)
218 memset(ht->mem, 0, sizeof(ht->mem[0]) * (1 << ht->max_elts_log2));
222 static bool insert(struct HashTable* ht, const void* key, uint8_t key_length, const void* data)
229 if (HT_HAS_INTERNAL_KEY(ht))
230 key_length = MIN(key_length, (uint8_t)INTERNAL_KEY_MAX_LENGTH);
232 node = perform_lookup(ht, key, key_length);
236 if (HT_HAS_INTERNAL_KEY(ht))
238 uint8_t* k = key_internal_get_ptr(ht, node);
240 memcpy(k, key, key_length);
248 bool ht_insert_with_key(struct HashTable* ht, const void* key, uint8_t key_length, const void* data)
251 if (!HT_HAS_INTERNAL_KEY(ht))
253 // Construct a fake node and use it to match the key
254 HashNodePtr node = &data;
255 if (!node_key_match(ht, node, key, key_length))
257 ASSERT2(0, "parameter key is different from the external key");
263 return insert(ht, key, key_length, data);
267 bool ht_insert(struct HashTable* ht, const void* data)
273 if (HT_HAS_INTERNAL_KEY(ht))
275 ASSERT("parameter cannot be a hash table with internal keys - use ht_insert_with_key()"
281 key = ht->key_data.hook(data, &key_length);
283 return insert(ht, key, key_length, data);
287 const void* ht_find(struct HashTable* ht, const void* key, uint8_t key_length)
291 if (HT_HAS_INTERNAL_KEY(ht))
292 key_length = MIN(key_length, (uint8_t)INTERNAL_KEY_MAX_LENGTH);
294 node = perform_lookup(ht, key, key_length);
296 if (!node || NODE_EMPTY(node))
309 static const void* test_get_key(const void* ptr, uint8_t* length)
316 #define NUM_ELEMENTS 256
317 DECLARE_HASHTABLE_STATIC(test1, 256, test_get_key);
318 DECLARE_HASHTABLE_INTERNALKEY_STATIC(test2, 256);
320 static char data[NUM_ELEMENTS][10];
321 static char keydomain[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
323 static bool single_test(void)
330 for (i=0;i<NUM_ELEMENTS;i++)
337 klen = (rand() % 8) + 1;
339 data[i][k] = keydomain[rand() % (sizeof(keydomain)-1)];
341 } while (ht_find_str(&test1, data[i]) != NULL);
343 ASSERT(ht_insert(&test1, data[i]));
344 ASSERT(ht_insert_str(&test2, data[i], data[i]));
347 for (i=0;i<NUM_ELEMENTS;i++)
349 char *found1, *found2;
351 found1 = (char*)ht_find_str(&test1, data[i]);
352 if (strcmp(found1, data[i]) != 0)
354 ASSERT(strcmp(found1,data[i]) == 0);
358 found2 = (char*)ht_find_str(&test2, data[i]);
359 if (strcmp(found2, data[i]) != 0)
361 ASSERT(strcmp(found2,data[i]) == 0);
369 static uint16_t rand_seeds[] = { 1, 42, 666, 0xDEAD, 0xBEEF, 0x1337, 0xB00B };
375 for (i=0;i<countof(rand_seeds);++i)
377 srand(rand_seeds[i]);
380 kprintf("ht_test failed\n");
385 kprintf("ht_test successful\n");