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
|
#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_string(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){ 0 };
}
static HtEntry *find(HtEntry *b, size_t cap, ObjString *k) {
// cap is guaranteed to be power of 2
size_t mask = cap - 1;
size_t ix = k->hash & mask;
if (cap == 0) return NULL;
for (;;) {
HtEntry *ent = &b[ix];
// XXX tombstones
if (ent->k == NULL || ent->k == k) {
return ent;
}
ix = (ix+1) & mask;
}
}
ObjString *ht_findstring(State *S, Ht *h, char *s, size_t len, uint32_t hash) {
const size_t cap = h->cap;
if (cap == 0) return NULL;
size_t ix = hash % cap;
for (;;) {
HtEntry *ent = &h->d[ix];
// XXX tombstones
if (ent->k == NULL)
return NULL;
else if (ent->k->hash == hash
&& ent->k->len == len
&& memcmp(ent->k->d, s, len) == 0)
return ent->k;
ix = (ix+1)%cap;
}
}
static void grow(State *S, Ht *h) {
HtEntry *old = h->d;
size_t newsz = h->cap == 0 ? 8 : h->cap * 2;
HtEntry *new = NEW_ARR(S, 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->d = new;
FREE_ARR(S, old, HtEntry, h->cap);
h->cap = newsz;
}
void ht_put(State *S, Ht *h, ObjString *k, Val v) {
if (h->cap == 0 || h->len >= (h->cap/2)) {
grow(S, h);
}
HtEntry *ent = find(h->d, h->cap, k);
if (ent->k == NULL) {
ent->k = k;
h->len++;
}
ent->v = v;
}
Val ht_get(State *S, Ht *h, ObjString *k) {
HtEntry *ent = find(h->d, h->cap, k);
if (ent == NULL)
return VAL_NIL;
else if (ent->k == NULL)
return VAL_NIL;
else
return ent->v;
}
|
