2

Situation: I have a set of key-value pairs of (uint32_t, uint8_t[12]). My current approach to retrieving the uint8_t[12] values is to parse a CSV file that contains the mappings, and fill a buffer if it's found. Ideally, I'd like to retain the ability to reload the hash table from the CSV, but for now I just need something fast and memory efficient.

Constraints: 64kiB of 16-bitRAM, 10MHz CPU, storage for at least 1600 key-value pairs (about 27kB by my calculations).

Solutions I have considered:

  • GHashTable: Seems like it may have too many features. glib is a large library

  • khash: Unmaintained, macro heavy and so difficult to debug/modify

  • uthash: Seems decent, relatively recent release (July 2016), but also macro heavy. Any thoughts?

1

Update: now as a proper Github repository: https://github.com/vi/macro_robinhood_hash


Here is my Robin Hood open addressing hash table in C implemented entirely in macros: https://gist.github.com/vi/42c4d7bc854653a17e9085c8831c6dcd

It is fixed size and memory-allocation-free and you can choose your own storage scheme. You give it primitives: setting/geting/clearing key/value for a cell, swapping cells and it gives you hash map operations.

Example:

#include <assert.h>
#include "robinhoodhash.h"

struct entry {
    int key;
    char value;
};

struct entry hshtable [100];

#define qqq_setvalue(index, key_, val_) \
        hshtable[index].key=key_; hshtable[index].value=val_;
#define qqq_setnil(index)   \
        hshtable[index].key=-1; hshtable[index].value=0;
#define qqq_swap(index1, index2) \
        struct entry tmp = hshtable[index1]; \
        hshtable[index1] = hshtable[index2]; \
        hshtable[index2] = tmp;

#define qqq_nilvalue        0
#define qqq_getvalue(index) hshtable[index].value
#define qqq_getkey(index)   hshtable[index].key
#define qqq_keysequal(key1,key2) key1 == key2
#define qqq_isnil(index)    hshtable[index].key == -1
#define qqq_n_elem          100
#define qqq_getbucket(key)  key%99 + 1
#define qqq_overflow        {}
#define qqq_removefailed(key)  {}

int main() {
    ROBINHOOD_HASH_CLEAR(qqq);

    char value = '_';

    ROBINHOOD_HASH_GET(qqq, 4433, value);
    assert(value == 0);

    ROBINHOOD_HASH_SET(qqq, 4433, 'A');
    ROBINHOOD_HASH_SET(qqq, 123,  'B');

    ROBINHOOD_HASH_GET(qqq, 4433, value);
    assert(value == 'A');
    ROBINHOOD_HASH_GET(qqq, 123, value);
    assert(value == 'B');

    ROBINHOOD_HASH_DEL(qqq, 4433);

    ROBINHOOD_HASH_GET(qqq, 4433, value);
    assert(value == 0);
    ROBINHOOD_HASH_GET(qqq, 123, value);
    assert(value == 'B');
    return 0;
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.