BeRTOS
|
00001 00057 #ifndef STRUCT_HASHTABLE_H 00058 #define STRUCT_HASHTABLE_H 00059 00060 #include "cfg/cfg_hashtable.h" 00061 00062 #include <cfg/compiler.h> 00063 #include <cfg/macros.h> 00064 #include <cfg/debug.h> 00065 00067 #define INTERNAL_KEY_MAX_LENGTH 15 00068 00073 typedef const void *(*hook_get_key)(const void *data, uint8_t *key_length); 00074 00075 00086 struct HashTable 00087 { 00088 const void **mem; 00089 uint16_t max_elts_log2; 00090 struct { 00091 bool key_internal : 1; 00092 } flags; 00093 union { 00094 hook_get_key hook; 00095 uint8_t *mem; 00096 } key_data; 00097 }; 00098 00099 00101 typedef struct 00102 { 00103 const void** pos; 00104 const void** end; 00105 } HashIterator; 00106 00107 00119 #define DECLARE_HASHTABLE(name, size, hook_gk) \ 00120 static const void* name##_nodes[1 << UINT32_LOG2(size)]; \ 00121 struct HashTable name = \ 00122 { \ 00123 .mem = name##_nodes, \ 00124 .max_elts_log2 = UINT32_LOG2(size), \ 00125 .flags = { .key_internal = false }, \ 00126 .key_data.hook = hook_gk \ 00127 } 00128 00129 00131 #define DECLARE_HASHTABLE_STATIC(name, size, hook_gk) \ 00132 static const void* name##_nodes[1 << UINT32_LOG2(size)]; \ 00133 static struct HashTable name = \ 00134 { \ 00135 .mem = name##_nodes, \ 00136 .max_elts_log2 = UINT32_LOG2(size), \ 00137 .flags = { .key_internal = false }, \ 00138 .key_data.hook = hook_gk \ 00139 } 00140 00141 #if CONFIG_HT_OPTIONAL_INTERNAL_KEY 00142 00147 #define DECLARE_HASHTABLE_INTERNALKEY(name, size) \ 00148 static uint8_t name##_keys[(1 << UINT32_LOG2(size)) * (INTERNAL_KEY_MAX_LENGTH + 1)]; \ 00149 static const void* name##_nodes[1 << UINT32_LOG2(size)]; \ 00150 struct HashTable name = { name##_nodes, UINT32_LOG2(size), { true }, name##_keys } 00151 00153 #define DECLARE_HASHTABLE_INTERNALKEY_STATIC(name, size) \ 00154 static uint8_t name##_keys[(1 << UINT32_LOG2(size)) * (INTERNAL_KEY_MAX_LENGTH + 1)]; \ 00155 static const void* name##_nodes[1 << UINT32_LOG2(size)]; \ 00156 static struct HashTable name = \ 00157 { \ 00158 .mem = name##_nodes, \ 00159 .max_elts_log2 = UINT32_LOG2(size), \ 00160 .flags = { .key_internal = true }, \ 00161 .key_data.mem = name##_keys \ 00162 } 00163 #endif 00164 00174 void ht_init(struct HashTable* ht); 00175 00193 bool ht_insert(struct HashTable* ht, const void* data); 00194 00214 bool ht_insert_with_key(struct HashTable* ht, const void* key, uint8_t key_length, const void* data); 00215 00224 const void* ht_find(struct HashTable* ht, const void* key, uint8_t key_length); 00225 00227 #define ht_insert_str(ht, key, data) ht_insert_with_key(ht, key, strlen(key), data) 00228 00230 #define ht_find_str(ht, key) ht_find(ht, key, strlen(key)) 00231 00233 INLINE HashIterator ht_iter_begin(struct HashTable* ht) 00234 { 00235 HashIterator h; 00236 00237 h.pos = &ht->mem[0]; 00238 h.end = &ht->mem[1 << ht->max_elts_log2]; 00239 00240 while (h.pos != h.end && !*h.pos) 00241 ++h.pos; 00242 00243 return h; 00244 } 00245 00253 INLINE HashIterator ht_iter_end(struct HashTable* ht) 00254 { 00255 HashIterator h; 00256 00257 h.pos = h.end = &ht->mem[1 << ht->max_elts_log2]; 00258 00259 return h; 00260 } 00261 00263 INLINE bool ht_iter_cmp(HashIterator it1, HashIterator it2) 00264 { 00265 ASSERT(it1.end == it2.end); 00266 return it1.pos == it2.pos; 00267 } 00268 00270 INLINE const void* ht_iter_get(HashIterator iter) 00271 { return *iter.pos; } 00272 00279 INLINE HashIterator ht_iter_next(HashIterator h) 00280 { 00281 ++h.pos; 00282 while (h.pos != h.end && !(*h.pos)) 00283 ++h.pos; 00284 00285 return h; 00286 } 00287 00288 int hashtable_testSetup(void); 00289 int hashtable_testRun(void); 00290 int hashtable_testTearDown(void); 00291 00292 #endif /* STRUCT_HASHTABLE_H */