BeRTOS
hashtable.c
Go to the documentation of this file.
00001 
00084 #include "hashtable.h"
00085 
00086 #include "cfg/cfg_hashtable.h"
00087 #include <cfg/debug.h>
00088 #include <cfg/compiler.h>
00089 #include <cfg/macros.h> //ROTL(), ROTR();
00090 
00091 #include <string.h>
00092 
00093 
00094 typedef const void** HashNodePtr;
00095 #define NODE_EMPTY(node)               (!*(node))
00096 #define HT_HAS_INTERNAL_KEY(ht)        (CONFIG_HT_OPTIONAL_INTERNAL_KEY && ht->flags.key_internal)
00097 
00099 INLINE uint8_t *key_internal_get_ptr(struct HashTable *ht, HashNodePtr node)
00100 {
00101     uint8_t* key_buf = ht->key_data.mem;
00102     size_t index;
00103 
00104     // Compute the index of the node and use it to move within the whole key buffer
00105     index = node - &ht->mem[0];
00106     ASSERT(index < (size_t)(1 << ht->max_elts_log2));
00107     key_buf += index * (INTERNAL_KEY_MAX_LENGTH + 1);
00108 
00109     return key_buf;
00110 }
00111 
00112 
00113 INLINE void node_get_key(struct HashTable* ht, HashNodePtr node, const void** key, uint8_t* key_length)
00114 {
00115     if (HT_HAS_INTERNAL_KEY(ht))
00116     {
00117         uint8_t* k = key_internal_get_ptr(ht, node);
00118 
00119         // Key has its length stored in the first byte
00120         *key_length = *k++;
00121         *key = k;
00122     }
00123     else
00124         *key = ht->key_data.hook(*node, key_length);
00125 }
00126 
00127 
00128 INLINE bool node_key_match(struct HashTable* ht, HashNodePtr node, const void* key, uint8_t key_length)
00129 {
00130     const void* key2;
00131     uint8_t key2_length;
00132 
00133     node_get_key(ht, node, &key2, &key2_length);
00134 
00135     return (key_length == key2_length && memcmp(key, key2, key_length) == 0);
00136 }
00137 
00138 
00139 static uint16_t calc_hash(const void* _key, uint8_t key_length)
00140 {
00141     const char* key = (const char*)_key;
00142     uint16_t hash = key_length;
00143     int i;
00144     int len = (int)key_length;
00145 
00146     for (i = 0; i < len; ++i)
00147         hash = ROTL(hash, 4) ^ key[i];
00148 
00149     return hash ^ (hash >> 6) ^ (hash >> 13);
00150 }
00151 
00152 
00153 static HashNodePtr perform_lookup(struct HashTable* ht,
00154                                   const void* key, uint8_t key_length)
00155 {
00156     uint16_t hash = calc_hash(key, key_length);
00157     uint16_t mask = ((1 << ht->max_elts_log2) - 1);
00158     uint16_t index = hash & mask;
00159     uint16_t first_index = index;
00160     uint16_t step;
00161     HashNodePtr node;
00162 
00163     // Fast-path optimization: we check immediately if the current node
00164     //  is the one we were looking for, so we save the computation of the
00165     //  increment step in the common case.
00166     node = &ht->mem[index];
00167     if (NODE_EMPTY(node)
00168         || node_key_match(ht, node, key, key_length))
00169         return node;
00170 
00171     // Increment while going through the hash table in case of collision.
00172     //  This implements the double-hash technique: we use the higher part
00173     //  of the hash as a step increment instead of just going to the next
00174     //  element, to minimize the collisions.
00175     // Notice that the number must be odd to be sure that the whole table
00176     //  is traversed. Actually MCD(table_size, step) must be 1, but
00177     //  table_size is always a power of 2, so we just ensure that step is
00178     //  never a multiple of 2.
00179     step = (ROTR(hash, ht->max_elts_log2) & mask) | 1;
00180 
00181     do
00182     {
00183         index += step;
00184         index &= mask;
00185 
00186         node = &ht->mem[index];
00187         if (NODE_EMPTY(node)
00188             || node_key_match(ht, node, key, key_length))
00189             return node;
00190 
00191         // The check is done after the key compare. This actually causes
00192         //  one more compare in the case the table is full (since the first
00193         //  element was compared at the very start, and then at the end),
00194         //  but it makes faster the common path where we enter this loop
00195         //  for the first time, and index will not match first_index for
00196         //  sure.
00197     } while (index != first_index);
00198 
00199     return NULL;
00200 }
00201 
00202 
00203 void ht_init(struct HashTable* ht)
00204 {
00205     memset(ht->mem, 0, sizeof(ht->mem[0]) * (1 << ht->max_elts_log2));
00206 }
00207 
00208 
00209 static bool insert(struct HashTable* ht, const void* key, uint8_t key_length, const void* data)
00210 {
00211     HashNodePtr node;
00212 
00213     if (!data)
00214         return false;
00215 
00216     if (HT_HAS_INTERNAL_KEY(ht))
00217         key_length = MIN(key_length, (uint8_t)INTERNAL_KEY_MAX_LENGTH);
00218 
00219     node = perform_lookup(ht, key, key_length);
00220     if (!node)
00221         return false;
00222 
00223     if (HT_HAS_INTERNAL_KEY(ht))
00224     {
00225         uint8_t* k = key_internal_get_ptr(ht, node);
00226         *k++ = key_length;
00227         memcpy(k, key, key_length);
00228     }
00229 
00230     *node = data;
00231     return true;
00232 }
00233 
00234 
00235 bool ht_insert_with_key(struct HashTable* ht, const void* key, uint8_t key_length, const void* data)
00236 {
00237 #ifdef _DEBUG
00238     if (!HT_HAS_INTERNAL_KEY(ht))
00239     {
00240         // Construct a fake node and use it to match the key
00241         HashNodePtr node = &data;
00242         if (!node_key_match(ht, node, key, key_length))
00243         {
00244             ASSERT2(0, "parameter key is different from the external key");
00245             return false;
00246         }
00247     }
00248 #endif
00249 
00250     return insert(ht, key, key_length, data);
00251 }
00252 
00253 
00254 bool ht_insert(struct HashTable* ht, const void* data)
00255 {
00256     const void* key;
00257     uint8_t key_length;
00258 
00259 #ifdef _DEBUG
00260     if (HT_HAS_INTERNAL_KEY(ht))
00261     {
00262         ASSERT("parameter cannot be a hash table with internal keys - use ht_insert_with_key()"
00263                && 0);
00264         return false;
00265     }
00266 #endif
00267 
00268     key = ht->key_data.hook(data, &key_length);
00269 
00270     return insert(ht, key, key_length, data);
00271 }
00272 
00273 
00274 const void* ht_find(struct HashTable* ht, const void* key, uint8_t key_length)
00275 {
00276     HashNodePtr node;
00277 
00278     if (HT_HAS_INTERNAL_KEY(ht))
00279         key_length = MIN(key_length, (uint8_t)INTERNAL_KEY_MAX_LENGTH);
00280 
00281     node = perform_lookup(ht, key, key_length);
00282 
00283     if (!node || NODE_EMPTY(node))
00284         return NULL;
00285 
00286     return *node;
00287 }