hashtable.h

Go to the documentation of this file.

#ifndef STRUCT_HASHTABLE_H
#define STRUCT_HASHTABLE_H

#include <cfg/compiler.h>
#include <cfg/macros.h>
#include <cfg/debug.h>

#define CONFIG_HT_OPTIONAL_INTERNAL_KEY      1

#define INTERNAL_KEY_MAX_LENGTH     15

typedef const void *(*hook_get_key)(const void *data, uint8_t *key_length);


struct HashTable
{
    const void **mem;            
    uint16_t max_elts_log2;      
    struct {
        bool key_internal : 1;   
    } flags;
    union {
        hook_get_key hook;       
        uint8_t *mem;            
    } key_data;
};


typedef struct
{
    const void** pos;
    const void** end;
} HashIterator;


#define DECLARE_HASHTABLE(name, size, hook_gk) \
    static const void* name##_nodes[1 << UINT32_LOG2(size)]; \
    struct HashTable name = { name##_nodes, UINT32_LOG2(size), { false }, hook_gk }

#define DECLARE_HASHTABLE_STATIC(name, size, hook_gk) \
    static const void* name##_nodes[1 << UINT32_LOG2(size)]; \
    static struct HashTable name = { name##_nodes, UINT32_LOG2(size), { false }, { hook_gk } }

#if CONFIG_HT_OPTIONAL_INTERNAL_KEY

    #define DECLARE_HASHTABLE_INTERNALKEY(name, size) \
        static uint8_t name##_keys[(1 << UINT32_LOG2(size)) * (INTERNAL_KEY_MAX_LENGTH + 1)]; \
        static const void* name##_nodes[1 << UINT32_LOG2(size)]; \
        struct HashTable name = { name##_nodes, UINT32_LOG2(size), { true }, name##_keys }

    #define DECLARE_HASHTABLE_INTERNALKEY_STATIC(name, size) \
        static uint8_t name##_keys[(1 << UINT32_LOG2(size)) * (INTERNAL_KEY_MAX_LENGTH + 1)]; \
        static const void* name##_nodes[1 << UINT32_LOG2(size)]; \
        static struct HashTable name = { name##_nodes, UINT32_LOG2(size), { true }, name##_keys }
#endif

void ht_init(struct HashTable* ht);

bool ht_insert(struct HashTable* ht, const void* data);

bool ht_insert_with_key(struct HashTable* ht, const void* key, uint8_t key_length, const void* data);

const void* ht_find(struct HashTable* ht, const void* key, uint8_t key_length);

#define ht_insert_str(ht, key, data)         ht_insert_with_key(ht, key, strlen(key), data)

#define ht_find_str(ht, key)                 ht_find(ht, key, strlen(key))

INLINE HashIterator ht_iter_begin(struct HashTable* ht)
{
    HashIterator h;

    h.pos = &ht->mem[0];
    h.end = &ht->mem[1 << ht->max_elts_log2];

    while (h.pos != h.end && !*h.pos)
        ++h.pos;

    return h;
}

INLINE HashIterator ht_iter_end(struct HashTable* ht)
{
    HashIterator h;

    h.pos = h.end = &ht->mem[1 << ht->max_elts_log2];

    return h;
}

INLINE bool ht_iter_cmp(HashIterator it1, HashIterator it2)
{
    ASSERT(it1.end == it2.end);
    return it1.pos == it2.pos;
}

INLINE const void* ht_iter_get(HashIterator iter)
{ return *iter.pos; }

INLINE HashIterator ht_iter_next(HashIterator h)
{
    ++h.pos;
    while (h.pos != h.end && !(*h.pos))
        ++h.pos;

    return h;
}

#endif /* STRUCT_HASHTABLE_H */