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
|
#include "ht.h"
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include "mem.h"
#define FNV_BASIS 0x811c9dc5
#define FNV_PRIME 0x01000193
// fnv-1a
uint32_t hash(char *s, size_t len) {
uint32_t h = FNV_BASIS;
for(int i = 0; i < len; i++) {
h ^= s[i];
h *= FNV_PRIME;
}
return h;
}
Ht ht_new() {
return (Ht){
.len = 0,
.cap = 0,
.b = NULL
};
}
static HtEntry *find(HtEntry *b, size_t cap, ObjString *k) {
size_t ix = k->hash % cap;
for (;;) {
HtEntry *ent = &b[ix];
if (ent->k == k || ent->k == NULL) {
return ent;
}
ix = (ix+1)%cap;
}
}
static void grow(Ht *h) {
HtEntry *old = h->b;
size_t newsz = h->cap == 0 ? 8 : h->cap * 2;
HtEntry *new = NEW_ARR(HtEntry, newsz);
for (int i = 0; i<newsz; i++) {
new[i].k = NULL;
new[i].v = VAL_NIL;
}
if (old != NULL) {
for (int i = 0; i < h->cap; i++) {
HtEntry *oldent = &old[i];
if (oldent->k == NULL) continue;
HtEntry *newent = find(new, newsz, oldent->k);
newent->k = oldent->k;
newent->v = oldent->v;
}
}
h->b = new;
FREE_ARR(old, HtEntry, h->cap);
h->cap = newsz;
}
void ht_put(Ht *h, ObjString *k, Val v) {
if (h->cap == 0 || h->len >= (h->cap/2)) {
grow(h);
}
HtEntry *ent = find(h->b, h->cap, k);
if (ent->k == NULL) {
ent->k = k;
h->len++;
}
ent->v = v;
}
Val ht_get(Ht *h, ObjString *k) {
HtEntry *ent = find(h->b, h->cap, k);
if (ent->k == NULL) {
return VAL_NIL;
} else {
return ent->v;
}
}
|
