BeRTOS
hashtable.h
Go to the documentation of this file.
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 */