Skip to content

Instantly share code, notes, and snippets.

@vi
Last active October 27, 2017 04:50
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save vi/42c4d7bc854653a17e9085c8831c6dcd to your computer and use it in GitHub Desktop.
Save vi/42c4d7bc854653a17e9085c8831c6dcd to your computer and use it in GitHub Desktop.
Simple Robin Hood hash table implemented using C macros. See also: https://github.com/vi/macro_robinhood_hash
#include <stdio.h>
#include <stddef.h>
#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;
}
#ifndef ROBINHOOD_HASH_H
#define ROBINHOOD_HASH_H
// Flexible C macros implementation of fixed size array-based Robin Hood hash table with backward-shift deletion.
// Implemented by Vitaly "_Vi" Shukela in 2017. License = MIT or Apache 2.0.
// Don't shrink this hash table by sequentially iterating it and inserting elements into a smaller table
// "X macro" pattern is expected to be for this parameters:
// "x" part is variable, substitude it with your identifier and specify it later as "tbl"
// #define x_setvalue(index, key, val) is a macro to set value to the table cell
// #define x_setnil(index) is a macro that marks table entry as empty
// #define x_swap(index1, index2) is a macro that swaps two entries in the table
// #define x_nilvalue is a value siganlizing that key is not found
// #define x_getvalue(index) is a macro to get value of the table cell
// #define x_getkey(index) is a macro for obtaining key for given index of the table.
// #define x_keysequal(key1,key2) is a macro that should return true when keys are equal
// #define x_isnil(index) is a macro that checks if table entry is empty
// #define x_n_elem should point to number of buckets in hash table
// #define x_getbucket(key) is a macro for obtaining adviced
// index of the table of the given key. Should be in range [1, n_elem[.
// #define x_overflow is a macro that is called when table is full
// #define x_removefailed(key) is a macro that called when trying to remove nonexisting element
// hash table entry should consist only of key and value and x_setvalue should completely set an entry
// If you don't need value just use reuse key as value
// API:
#define ROBINHOOD_HASH_SET(tbl, key, value) \
_ROBINHOOD_HASH_SET(tbl, key, value)
#define ROBINHOOD_HASH_GET(tbl, key, assignme) \
_ROBINHOOD_HASH_GET(tbl, key, assignme)
#define ROBINHOOD_HASH_DEL(tbl, key) \
_ROBINHOOD_HASH_DEL(tbl, key)
#define ROBINHOOD_HASH_SIZE(tbl, assignme) \
_ROBINHOOD_HASH_SIZE(tbl, assignme)
#define ROBINHOOD_HASH_CLEAR(tbl) \
_ROBINHOOD_HASH_CLEAR(tbl)
// Impl:
#include <stddef.h> // size_t
#define _ROBINHOOD_HASH_TYPICAL_INIT(key, getbucket) \
size_t _rh_i = getbucket(key); \
size_t _rh_i_orig = _rh_i; \
size_t _rh_temperature = 0;
#define _ROBINHOOD_HASH_TYPICAL_INCREMENT(breakcode, n_elem) \
_rh_temperature += 1; \
_rh_i += 1; \
if (_rh_i>=n_elem) _rh_i=1; \
if (_rh_i == _rh_i_orig) { \
breakcode \
break; \
}
#define _ROBINHOOD_HASH_DEBUGPRINT(tbl) { \
size_t _rh_i; \
printf("RBHDP: "); \
for(_rh_i=1; _rh_i < tbl##_n_elem; ++_rh_i) { \
printf("%02d:",_rh_i); \
if (tbl##_isnil(_rh_i)) { \
printf("___+__ "); \
} else { \
printf("%03u+%02d ", tbl##_getkey(_rh_i), tbl##_getbucket(tbl##_getkey(i))); \
} \
} \
printf("\n"); \
}
#define _ROBINHOOD_HASH_SET(tbl, key, value) { \
_ROBINHOOD_HASH_TYPICAL_INIT(key, tbl##_getbucket) \
tbl##_setvalue(0, key, value); \
int _rh_check_for_match = 1; \
for(;;) { \
if (tbl##_isnil(_rh_i)) { \
tbl##_setvalue(_rh_i, tbl##_getkey(0), tbl##_getvalue(0)); \
break; \
} else { \
if (_rh_check_for_match && (tbl##_keysequal(tbl##_getkey(_rh_i),key))) { \
tbl##_setvalue(_rh_i, key, value); \
break; \
} \
size_t _rh_i_want = tbl##_getbucket(tbl##_getkey(_rh_i)); \
size_t _rh_i_temp; \
if (_rh_i_want <= _rh_i) { \
_rh_i_temp = _rh_i - _rh_i_want; \
} else { \
_rh_i_temp = tbl##_n_elem - _rh_i_want + _rh_i - 1; \
} \
if (_rh_i_temp < _rh_temperature) { \
/* Rob the rich, give the poor */ \
tbl##_swap(0, _rh_i); \
_rh_temperature = _rh_i_temp; \
_rh_check_for_match = 0; \
} \
_ROBINHOOD_HASH_TYPICAL_INCREMENT({tbl##_overflow;}, tbl##_n_elem) \
} \
} \
}
#define _ROBINHOOD_HASH_GET(tbl, key, assignme) { \
_ROBINHOOD_HASH_TYPICAL_INIT(key, tbl##_getbucket) \
for(;;) { \
if (tbl##_isnil(_rh_i)) { \
assignme = tbl##_nilvalue; \
break; \
} else { \
if (tbl##_keysequal(tbl##_getkey(_rh_i),key)) { \
assignme = tbl##_getvalue(_rh_i); \
break; \
} \
_ROBINHOOD_HASH_TYPICAL_INCREMENT({assignme = tbl##_nilvalue;}, tbl##_n_elem) \
} \
} \
}
#define _ROBINHOOD_HASH_DEL(tbl, key) { \
_ROBINHOOD_HASH_TYPICAL_INIT(key, tbl##_getbucket) \
int _ri_needbackshift = 0; \
for(;;) { \
if (tbl##_isnil(_rh_i)) { \
tbl##_removefailed(key); \
break; \
} else { \
if (tbl##_keysequal(tbl##_getkey(_rh_i),key)) { \
tbl##_setnil(_rh_i); \
_ri_needbackshift = 1; \
break; \
} \
_ROBINHOOD_HASH_TYPICAL_INCREMENT({tbl##_removefailed(key);}, tbl##_n_elem) \
} \
} \
/* Backshift */ \
if(_ri_needbackshift)\
for(;;) { \
size_t _rh_nexti = _rh_i + 1; \
if (_rh_nexti >= tbl##_n_elem) _rh_nexti=1; \
if (tbl##_isnil(_rh_nexti)) { \
break; \
} else \
if (tbl##_getbucket(tbl##_getkey(_rh_nexti)) == _rh_nexti) { \
break; \
} else { \
tbl##_swap(_rh_nexti, _rh_i); \
} \
_rh_i = _rh_nexti; \
} \
}
#define _ROBINHOOD_HASH_SIZE(tbl, assignme) { \
size_t _rh_i; \
assignme = 0; \
for(_rh_i=0; _rh_i<tbl##_n_elem; ++_rh_i) { \
if (!(tbl##_isnil(_rh_i))) assignme+=1; \
} \
}
#define _ROBINHOOD_HASH_CLEAR(tbl) { \
size_t _rh_i; \
for(_rh_i=0; _rh_i<tbl##_n_elem; ++_rh_i) { \
tbl##_setnil(_rh_i) \
} \
}
#endif // ROBINHOOD_HASH_H
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment