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
107
108
109
110
111
112
113
114
115
116
117
118
|
#include "hash_table.h"
#include <stdlib.h>
#include <string.h>
#include "basic_traits.h"
#define HTFL_NUL 0
#define HTFL_VAL 1
#define HTFL_DEL 2
HASH_TABLE_IMPL(String, Int);
HASH_TABLE_IMPL(String, String);
HASH_TABLE_IMPL(String, Double);
HASH_TABLE_IMPL(String, VoidPtr);
HASH_TABLE_IMPL(Int, Int);
HASH_TABLE_IMPL(Int, Double);
HASH_TABLE_IMPL(VoidPtr, Int);
HASH_TABLE_IMPL(VoidPtr, String);
static void rebuild(HashTable *ht, uint64_t (*hash)(void*), bool (*eq)(void*, void*)) {
HashTable newht;
init_hash_table(&newht, ht->elemsz, ht->size * 6);
void *iter = hash_table_begin(ht);
while (iter != NULL) {
hash_table_insert(&newht, iter, hash, eq);
iter = hash_table_next(ht, iter);
}
free(ht->buf);
free(ht->flagbuf);
*ht = newht;
}
void init_hash_table(HashTable *ht, int64_t elemsz, int64_t cap) {
if (cap < 16) cap = 16;
ht->buf = malloc(cap * elemsz);
ht->flagbuf = malloc(cap);
memset(ht->buf, 0, cap * elemsz);
memset(ht->flagbuf, 0, cap);
ht->size = 0;
ht->cap = cap;
ht->taken = 0;
ht->elemsz = elemsz;
}
bool hash_table_insert(HashTable *ht, void *elem, uint64_t (*hash)(void*), bool (*eq)(void*, void*)) {
if (ht->taken + 1 > ht->cap / 2) {
rebuild(ht, hash, eq);
}
ht->taken++;
ht->size++;
int64_t pos = hash(elem) % ht->cap;
while (ht->flagbuf[pos] != HTFL_NUL) {
if (ht->flagbuf[pos] == HTFL_VAL
&& eq(ht->buf + pos * ht->elemsz, elem)) {
return false;
}
pos++;
if (pos >= ht->cap) { // arrived end, restart from beginning
pos = 0;
}
}
memcpy(ht->buf + pos * ht->elemsz, elem, ht->elemsz);
ht->flagbuf[pos] = HTFL_VAL;
return true;
}
void hash_table_remove(HashTable *ht, void * ptr) {
ht->size--;
int64_t pos = (ptr - ht->buf) / ht->elemsz;
ht->flagbuf[pos] = HTFL_DEL;
}
void *hash_table_ref(HashTable *ht, int64_t pos) {
return ht->buf + pos * ht->elemsz;
}
void *hash_table_find(HashTable *ht, void *elem, uint64_t (*hash)(void*), bool (*eq)(void*, void*)) {
int64_t pos = hash(elem) % ht->cap;
while (ht->flagbuf[pos] != HTFL_NUL) {
if (ht->flagbuf[pos] == HTFL_VAL
&& eq(hash_table_ref(ht, pos), elem)) {
return hash_table_ref(ht, pos);
}
pos++;
if (pos >= ht->cap) { // arrived end, restart from beginning
pos = 0;
}
}
return NULL;
}
void* hash_table_begin(HashTable *ht) {
if (ht->size <= 0) return NULL;
for (int64_t i = 0; i < ht->cap; i++) {
if (ht->flagbuf[i] == HTFL_VAL) {
return hash_table_ref(ht, i);
}
}
return NULL;
}
void *hash_table_next(HashTable *ht, void *iter) {
int64_t pos = (iter - ht->buf) / ht->elemsz;
do {
pos++;
if (pos >= ht->cap) {
return NULL;
}
} while (ht->flagbuf[pos] != HTFL_VAL);
return hash_table_ref(ht, pos);
}
void destroy_hash_table(HashTable *ht) {
free(ht->buf);
free(ht->flagbuf);
}
|
