This library provides a simple hashtable written in C. The hashtable is stored as a single heap allocated array. This storage scheme is good for caching, since everything is densely packed and pointer chasing is avoided in contrast to hashtables which use linked lists. The array will grow automatically, when the filling reaches a certain threshold.
By using macros, the library is specialized for each entry type. For example it is possible to generate a hashset without overhead, by using entries consisting only of a key. Arbitrary key types are supported and various hash functions are provided in hashfn.h.
At first we create the hashtable functions and datastructure for the special entry type MyEntry.
For optimal performance all hash functions are specialized for this entry type.
typedef struct {
const char* k;
int v;
} MyEntry;
#define HASH MyHash
#define ENTRY MyEntry
#define PREFIX myhash
#define KEY(e) e->k
#define EXISTS(e) e->k
#define KEYEQ(a, b) !strcmp(a, b)
#define HASHFN hashString
#include "hashtable.h"int main(void) {
MyHash h = HASH_INIT;
MyEntry* e;
if (myhashCreate(&h, "a", &e)) {
printf("ENTRY CREATED\n");
e->k = "a";
e->v = 1;
}
myhashCreate(&h, "b", &e);
e->k = "b";
e->v = 2;
myhashCreate(&h, "c", &e);
e->k = "c";
e->v = 3;
myhashCreate(&h, "c", &e);
e->k = "c";
e->v = 4;
e = myhashFind(&h, "a");
if (e)
printf("FOUND a %d\n", e->v);
else
printf("NOT FOUND a\n");
e = myhashFind(&h, "d");
if (e)
printf("FOUND d %d\n", e->v);
else
printf("NOT FOUND d\n");
HASH_FOREACH(myhash, f, &h)
printf("%s %d\n", f->k, f->v);
}