BeRTOS
|
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 }