00001
00061 #ifndef STRUCT_HASHTABLE_H
00062 #define STRUCT_HASHTABLE_H
00063 
00064 #include "cfg/cfg_hashtable.h"
00065
00066 #include <cfg/compiler.h>
00067 #include <cfg/macros.h>
00068 #include <cfg/debug.h>
00069
00071 #define INTERNAL_KEY_MAX_LENGTH     15
00072 
00077 typedef const void *(*hook_get_key)(const void *data, uint8_t *key_length);
00078
00079
00090 struct HashTable
00091 {
00092     const void **mem;
00093     uint16_t max_elts_log2;
00094     struct {
00095         bool key_internal : 1;
00096     } flags;
00097     union {
00098         hook_get_key hook;
00099         uint8_t *mem;
00100     } key_data;
00101 };
00102
00103
00105 typedef struct
00106 {
00107     const void** pos;
00108     const void** end;
00109 } HashIterator;
00110
00111
00123 #define DECLARE_HASHTABLE(name, size, hook_gk) \
00124     static const void* name##_nodes[1 << UINT32_LOG2(size)]; \
00125     struct HashTable name = \
00126         { \
00127             .mem = name##_nodes, \
00128             .max_elts_log2 = UINT32_LOG2(size), \
00129             .flags = { .key_internal = false }, \
00130             .key_data.hook = hook_gk \
00131         }
00132 
00133
00135 #define DECLARE_HASHTABLE_STATIC(name, size, hook_gk) \
00136     enum { name##_SIZE = (1 << UINT32_LOG2(size)), }; \
00137     static const void* name##_nodes[name##_SIZE]; \
00138     static struct HashTable name = \
00139         { \
00140             .mem = name##_nodes, \
00141             .max_elts_log2 = UINT32_LOG2(size), \
00142             .flags = { .key_internal = false }, \
00143             .key_data.hook = hook_gk \
00144         }
00145 
00146 #if CONFIG_HT_OPTIONAL_INTERNAL_KEY
00147 
00152     #define DECLARE_HASHTABLE_INTERNALKEY(name, size) \
00153         static uint8_t name##_keys[(1 << UINT32_LOG2(size)) * (INTERNAL_KEY_MAX_LENGTH + 1)]; \
00154         static const void* name##_nodes[1 << UINT32_LOG2(size)]; \
00155         struct HashTable name = { name##_nodes, UINT32_LOG2(size), { true }, name##_keys }
00156 
00158     #define DECLARE_HASHTABLE_INTERNALKEY_STATIC(name, size) \
00159         enum { name##_KEYS = ((1 << UINT32_LOG2(size)) * (INTERNAL_KEY_MAX_LENGTH + 1)), \
00160             name##_SIZE = (1 << UINT32_LOG2(size)), }; \
00161         static uint8_t name##_keys[name##_KEYS]; \
00162         static const void* name##_nodes[name##_SIZE]; \
00163         static struct HashTable name = \
00164             { \
00165                 .mem = name##_nodes, \
00166                 .max_elts_log2 = UINT32_LOG2(size), \
00167                 .flags = { .key_internal = true }, \
00168                 .key_data.mem = name##_keys \
00169             }
00170 #endif
00171 
00181 void ht_init(struct HashTable* ht);
00182
00200 bool ht_insert(struct HashTable* ht, const void* data);
00201
00221 bool ht_insert_with_key(struct HashTable* ht, const void* key, uint8_t key_length, const void* data);
00222
00231 const void* ht_find(struct HashTable* ht, const void* key, uint8_t key_length);
00232
00234 #define ht_insert_str(ht, key, data)         ht_insert_with_key(ht, key, strlen(key), data)
00235 
00237 #define ht_find_str(ht, key)                 ht_find(ht, key, strlen(key))
00238 
00240 INLINE HashIterator ht_iter_begin(struct HashTable* ht)
00241 {
00242     HashIterator h;
00243
00244     h.pos = &ht->mem[0];
00245     h.end = &ht->mem[1 << ht->max_elts_log2];
00246
00247     while (h.pos != h.end && !*h.pos)
00248         ++h.pos;
00249
00250     return h;
00251 }
00252
00260 INLINE HashIterator ht_iter_end(struct HashTable* ht)
00261 {
00262     HashIterator h;
00263
00264     h.pos = h.end = &ht->mem[1 << ht->max_elts_log2];
00265
00266     return h;
00267 }
00268
00270 INLINE bool ht_iter_cmp(HashIterator it1, HashIterator it2)
00271 {
00272     ASSERT(it1.end == it2.end);
00273     return it1.pos == it2.pos;
00274 }
00275
00277 INLINE const void* ht_iter_get(HashIterator iter)
00278 { return *iter.pos; }
00279
00286 INLINE HashIterator ht_iter_next(HashIterator h)
00287 {
00288     ++h.pos;
00289     while (h.pos != h.end && !(*h.pos))
00290         ++h.pos;
00291
00292     return h;
00293 }
00294
00295 int hashtable_testSetup(void);
00296 int hashtable_testRun(void);
00297 int hashtable_testTearDown(void);
00298  // \defgroup hashtable
00300
00301 #endif /* STRUCT_HASHTABLE_H */