Last active
October 27, 2017 04:50
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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