1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
#include "htable.h"
#include <stdlib.h>
#include <string.h>
#define HTFL_NUL 0
#define HTFL_VAL 1
#define HTFL_DEL 2
static void* htable_end(HTable *ht) {
return ht->buf + ht->cap * (ht->elemsz + 1);
}
static void rebuild(HTable *ht) {
HTable newht;
htable_init(&newht, ht->elemsz, ht->size * 6, ht->hash, ht->eq);
void *iter = htable_begin(ht);
while (iter != NULL) {
htable_insert(&newht, iter);
iter = htable_next(ht, iter);
}
free(ht->buf);
*ht = newht;
}
static uint8_t getflag(void *iter) {
return *(uint8_t*)(iter - 1);
}
static void setflag(void *iter, uint8_t flag) {
*(uint8_t *)(iter - 1) = flag;
}
void htable_init(HTable *ht, int elemsz, int cap, uint32_t (*hash)(void*),
bool (*eq)(void*, void*)) {
if (cap < 16) cap = 16;
ht->buf = malloc(cap * (elemsz + 1));
memset(ht->buf, 0, cap * (elemsz + 1));
ht->size = 0;
ht->cap = cap;
ht->taken = 0;
ht->begin = NULL;
ht->elemsz = elemsz;
ht->hash = hash;
ht->eq = eq;
}
bool htable_insert(HTable *ht, void* elem) {
if (ht->taken + 1 > ht->cap / 2) {
rebuild(ht);
}
ht->taken++;
ht->size++;
int hashcode = ht->hash(elem) % ht->cap;
void *pos = ht->buf + hashcode * (ht->elemsz + 1) + 1;
while (getflag(pos) != HTFL_NUL) {
if (getflag(pos) == HTFL_VAL && ht->eq(pos, elem)) return false;
pos += ht->elemsz + 1;
if (pos >= htable_end(ht)) { // arrived end, restart from beginning
pos = ht->buf + 1;
}
}
memcpy(pos, elem, ht->elemsz);
setflag(pos, HTFL_VAL);
if (pos < ht->begin || ht->begin == NULL) {
ht->begin = pos;
}
return true;
}
void htable_del(HTable *ht, void* iter) {
ht->size--;
setflag(iter, HTFL_DEL);
if (iter == ht->begin) {
ht->begin = htable_next(ht, iter);
}
}
void* htable_find(HTable *ht, void* elem) {
int hashcode = ht->hash(elem) % ht->cap;
void *pos = ht->buf + hashcode * (ht->elemsz + 1) + 1;
while (getflag(pos) != HTFL_NUL) {
if (getflag(pos) == HTFL_VAL && ht->eq(pos, elem)) return pos;
pos += ht->elemsz + 1;
if (pos >= htable_end(ht)) { // arrived end, restart from beginning
pos = ht->buf + 1;
}
}
return NULL;
}
void* htable_begin(HTable *ht) {
return ht->begin;
}
void* htable_next(HTable *ht, void *iter) {
void *pos = iter;
do {
pos += ht->elemsz + 1;
if (pos >= htable_end(ht)) {
return NULL;
}
} while (getflag(pos) != HTFL_VAL);
return pos;
}
|
