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.4  2004/12/08 09:42:30  bernie
  65  *#* Suppress warning.
  66  *#*
  67  *#* Revision 1.3  2004/10/03 20:43:22  bernie
  68  *#* Import changes from sc/firmware.
  69  *#*
  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
  73  *#*
  74  *#* Revision 1.11  2004/06/14 15:09:04  rasky
  75  *#* Cambiati i messaggi di assert (è inutile citare il nome della funzione)
  76  *#*
  77  *#* Revision 1.10  2004/06/14 15:07:38  rasky
  78  *#* Convertito il loop di calc_hash a interi (per farlo ottimizzare maggiormente)
  79  *#*
  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
  82  *#*
  83  *#* Revision 1.8  2004/06/12 15:18:05  rasky
  84  *#* Nuova hashtable con chiave esterna o interna a scelta, come discusso
  85  *#*
  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
  88  *#*
  89  *#* Revision 1.6  2004/05/26 16:36:50  rasky
  90  *#* Aggiunto il rationale per l'interfaccia degli iteratori
  91  *#*
  92  *#* Revision 1.5  2004/05/24 15:28:20  rasky
  93  *#* Sistemata la documentazione, rimossa keycmp in favore della memcmp
  94  *#*
  95  *#*/
  96
  97 #include "hashtable.h"
  98 #include <debug.h>
  99 #include <compiler.h>
 100
 101 #include <string.h>
 102
 103
 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))
 106
 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)
 110
 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)
 113 {
 114         uint8_t* key_buf = ht->key_data.mem;
 115         size_t index;
 116
 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);
 121
 122         return key_buf;
 123 }
 124
 125
 126 INLINE void node_get_key(struct HashTable* ht, HashNodePtr node, const void** key, uint8_t* key_length)
 127 {
 128         if (HT_HAS_INTERNAL_KEY(ht))
 129         {
 130                 uint8_t* k = key_internal_get_ptr(ht, node);
 131
 132                 // Key has its length stored in the first byte
 133                 *key_length = *k++;
 134                 *key = k;
 135         }
 136         else
 137                 *key = ht->key_data.hook(*node, key_length);
 138 }
 139
 140
 141 INLINE bool node_key_match(struct HashTable* ht, HashNodePtr node, const void* key, uint8_t key_length)
 142 {
 143         const void* key2;
 144         uint8_t key2_length;
 145
 146         node_get_key(ht, node, &key2, &key2_length);
 147
 148         return (key_length == key2_length && memcmp(key, key2, key_length) == 0);
 149 }
 150
 151
 152 static uint16_t calc_hash(const void* _key, uint8_t key_length)
 153 {
 154         const char* key = (const char*)_key;
 155         uint16_t hash = key_length;
 156         int i;
 157         int len = (int)key_length;
 158
 159         for (i = 0; i < len; ++i)
 160                 hash = ROTATE_LEFT_16(hash, 4) ^ key[i];
 161
 162         return hash ^ (hash >> 6) ^ (hash >> 13);
 163 }
 164
 165
 166 static HashNodePtr perform_lookup(struct HashTable* ht,
 167                                   const void* key, uint8_t key_length)
 168 {
 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;
 173         uint16_t step;
 174         HashNodePtr node;
 175
 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];
 180         if (NODE_EMPTY(node)
 181                 || node_key_match(ht, node, key, key_length))
 182                 return node;
 183
 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;
 193
 194         do
 195         {
 196                 index += step;
 197                 index &= mask;
 198
 199                 node = &ht->mem[index];
 200                 if (NODE_EMPTY(node)
 201                         || node_key_match(ht, node, key, key_length))
 202                         return node;
 203
 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
 209                 //  sure.
 210         } while (index != first_index);
 211
 212         return NULL;
 213 }
 214
 215
 216 void ht_init(struct HashTable* ht)
 217 {
 218         memset(ht->mem, 0, sizeof(ht->mem[0]) * (1 << ht->max_elts_log2));
 219 }
 220
 221
 222 static bool insert(struct HashTable* ht, const void* key, uint8_t key_length, const void* data)
 223 {
 224         HashNodePtr node;
 225
 226         if (!data)
 227                 return false;
 228
 229         if (HT_HAS_INTERNAL_KEY(ht))
 230                 key_length = MIN(key_length, (uint8_t)INTERNAL_KEY_MAX_LENGTH);
 231
 232         node = perform_lookup(ht, key, key_length);
 233         if (!node)
 234                 return false;
 235
 236         if (HT_HAS_INTERNAL_KEY(ht))
 237         {
 238                 uint8_t* k = key_internal_get_ptr(ht, node);
 239                 *k++ = key_length;
 240                 memcpy(k, key, key_length);
 241         }
 242
 243         *node = data;
 244         return true;
 245 }
 246
 247
 248 bool ht_insert_with_key(struct HashTable* ht, const void* key, uint8_t key_length, const void* data)
 249 {
 250 #ifdef _DEBUG
 251         if (!HT_HAS_INTERNAL_KEY(ht))
 252         {
 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))
 256                 {
 257                         ASSERT2(0, "parameter key is different from the external key");
 258                         return false;
 259                 }
 260         }
 261 #endif
 262
 263         return insert(ht, key, key_length, data);
 264 }
 265
 266
 267 bool ht_insert(struct HashTable* ht, const void* data)
 268 {
 269         const void* key;
 270         uint8_t key_length;
 271
 272 #ifdef _DEBUG
 273         if (HT_HAS_INTERNAL_KEY(ht))
 274         {
 275                 ASSERT("parameter cannot be a hash table with internal keys - use ht_insert_with_key()"
 276                        && 0);
 277                 return false;
 278         }
 279 #endif
 280
 281         key = ht->key_data.hook(data, &key_length);
 282
 283         return insert(ht, key, key_length, data);
 284 }
 285
 286
 287 const void* ht_find(struct HashTable* ht, const void* key, uint8_t key_length)
 288 {
 289         HashNodePtr node;
 290
 291         if (HT_HAS_INTERNAL_KEY(ht))
 292                 key_length = MIN(key_length, (uint8_t)INTERNAL_KEY_MAX_LENGTH);
 293
 294         node = perform_lookup(ht, key, key_length);
 295
 296         if (!node || NODE_EMPTY(node))
 297                 return NULL;
 298
 299         return *node;
 300 }
 301
 302
 303 #if 0
 304
 305 #include <stdlib.h>
 306
 307 bool ht_test(void);
 308
 309 static const void* test_get_key(const void* ptr, uint8_t* length)
 310 {
 311         const char* s = ptr;
 312         *length = strlen(s);
 313         return s;
 314 }
 315
 316 #define NUM_ELEMENTS   256
 317 DECLARE_HASHTABLE_STATIC(test1, 256, test_get_key);
 318 DECLARE_HASHTABLE_INTERNALKEY_STATIC(test2, 256);
 319
 320 static char data[NUM_ELEMENTS][10];
 321 static char keydomain[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
 322
 323 static bool single_test(void)
 324 {
 325         int i;
 326
 327         ht_init(&test1);
 328         ht_init(&test2);
 329
 330         for (i=0;i<NUM_ELEMENTS;i++)
 331         {
 332                 int k;
 333                 int klen;
 334
 335                 do
 336                 {
 337                         klen = (rand() % 8) + 1;
 338                         for (k=0;k<klen;k++)
 339                                 data[i][k] = keydomain[rand() % (sizeof(keydomain)-1)];
 340                         data[i][k]=0;
 341                 } while (ht_find_str(&test1, data[i]) != NULL);
 342
 343                 ASSERT(ht_insert(&test1, data[i]));
 344                 ASSERT(ht_insert_str(&test2, data[i], data[i]));
 345         }
 346
 347         for (i=0;i<NUM_ELEMENTS;i++)
 348         {
 349                 char *found1, *found2;
 350
 351                 found1 = (char*)ht_find_str(&test1, data[i]);
 352                 if (strcmp(found1, data[i]) != 0)
 353                 {
 354                         ASSERT(strcmp(found1,data[i]) == 0);
 355                         return false;
 356                 }
 357
 358                 found2 = (char*)ht_find_str(&test2, data[i]);
 359                 if (strcmp(found2, data[i]) != 0)
 360                 {
 361                         ASSERT(strcmp(found2,data[i]) == 0);
 362                         return false;
 363                 }
 364         }
 365
 366         return true;
 367 }
 368
 369 static uint16_t rand_seeds[] = { 1, 42, 666, 0xDEAD, 0xBEEF, 0x1337, 0xB00B };
 370
 371 bool ht_test(void)
 372 {
 373         int i;
 374
 375         for (i=0;i<countof(rand_seeds);++i)
 376         {
 377                 srand(rand_seeds[i]);
 378                 if (!single_test())
 379                 {
 380                         kprintf("ht_test failed\n");
 381                         return false;
 382                 }
 383         }
 384
 385         kprintf("ht_test successful\n");
 386         return true;
 387 }
 388
 389 #endif