Fixed size array only hash table
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
// Fixed size array only hash table
// How do I know empty?
void p(int v) {
printf("%i\n", v);
}
void p(char *v) {
printf("%s\n", v);
}
uint32_t f(void *data, size_t size) {
return *(int *)data;
}
struct Rae {
int k;
char *v;
};
Rae *init(size_t count, int empty) {
Rae *t = (Rae *)malloc(32 * sizeof(Rae));
for(uint32_t i = 0; i < count; ++i) {
t[i].k = empty;
}
return t;
}
bool add(Rae *t, uint32_t (*f)(void *, size_t), size_t count, int empty, int k, char *v) {
uint32_t hash = f(&k, sizeof(k));
for(uint32_t i_ = 0; i_ < count; ++i_) {
uint32_t i = (i_ + hash) & (count - 1);
if(t[i].k == empty) {
t[i].k = k;
t[i].v = v;
return false;
} else if(t[i].k == k) {
t[i].k = k;
t[i].v = v;
return true;
}
}
assert(0 && "Out of space");
return false;
}
/*
xor eax, eax
mov mask, count
dec mask
mov i_raw, slot
mov end, slot
add end, count
loop_inc:
inc i_raw
cmp i_raw, end
jae out_of_space
mov i, i_raw
and i, mask
cmp m.k, empty
je loop_inc
cmp m.k, key
jne loop_inc
inc rax
enter:
mov m.k, k
mov m.v, v
ret
out_of_space:
int 3
ret
*/
char *get(Rae *t, uint32_t (*f)(void *, size_t), size_t count, int empty, int k) {
uint32_t hash = f(&k, sizeof(k));
for(uint32_t i_ = 0; i_ < count; ++i_) {
uint32_t i = (i_ + hash) & (count - 1);
if(t[i].k == k) {
return t[i].v;
}
}
return 0;
}
int main() {
size_t count = 32;
Rae *t = init(count, -1);
add(t, f, count, -1, 20, "Tera");
add(t, f, count, -1, 20, "Virk");
add(t, f, count, -1, 52, "Hello");
add(t, f, count, -1, 22, "ets");
char *v = get(t, f, count, -1, 20);
p(v);
free(t);
return 0;
}
Cpp
INFO