hashtable.h

Go to the documentation of this file.

#ifndef STRUCT_HASHTABLE_H
#define STRUCT_HASHTABLE_H

#include "cfg/cfg_hashtable.h"

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

#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 = \
        { \
            .mem = name##_nodes, \
            .max_elts_log2 = UINT32_LOG2(size), \
            .flags = { .key_internal = false }, \
            .key_data.hook = hook_gk \
        }


#define DECLARE_HASHTABLE_STATIC(name, size, hook_gk) \
    static const void* name##_nodes[1 << UINT32_LOG2(size)]; \
    static struct HashTable name = \
        { \
            .mem = name##_nodes, \
            .max_elts_log2 = UINT32_LOG2(size), \
            .flags = { .key_internal = false }, \
            .key_data.hook = 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 = \
            { \
                .mem = name##_nodes, \
                .max_elts_log2 = UINT32_LOG2(size), \
                .flags = { .key_internal = true }, \
                .key_data.mem = 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;
}

int hashtable_testSetup(void);
int hashtable_testRun(void);
int hashtable_testTearDown(void);

#endif /* STRUCT_HASHTABLE_H */