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
|
use hash::fnv;
use strings;
def BUCKETSZ: size = 32z;
export type map = struct {
buckets: [BUCKETSZ][]entry,
};
export type entry = struct {
hash: size,
key: str,
val: str,
};
export type iterator = struct {
i: size,
j: size,
m: map,
};
export fn newmap() map = {
return map {
...
};
};
export fn newiterator(m: map) iterator = {
return iterator {
i = 0z,
j = 0z,
m = m,
};
};
export fn put(m: *map, k: str, v: str) void = {
const s = fnv::string(k);
const bucket = &m.buckets[s%len(m.buckets)];
for (let e &.. bucket) {
if (e.hash == s) {
e.val = v;
return;
};
};
append(bucket, entry {
hash = s,
key = strings::dup(k),
val = strings::dup(v),
})!;
};
export fn get(m: map, k: str) (str | void) = {
const s = fnv::string(k);
const bucket = m.buckets[s%len(m.buckets)];
for (let e .. bucket) {
if (e.hash == s) {
return e.val;
};
};
return;
};
export fn next(it: *iterator) (entry | done) = {
if (len(it.m.buckets) == 0 || len(it.m.buckets) <= it.i) {
return done;
};
for (true) {
if (len(it.m.buckets) <= it.i) {
return done;
};
const b = it.m.buckets[it.i];
if (len(b) == 0 || len(b) <= it.j) {
it.i += 1;
it.j = 0;
} else {
const e = b[it.j];
it.j += 1;
return e;
};
};
};
export fn finishmap(m: *map) void = {
for (let e &.. m.buckets) {
finishentries(e);
};
};
fn finishentries(e: *[]entry) void = {
for (let i = 0z; i < len(e); i += 1) {
free(e[i].key);
free(e[i].val);
};
};
@test fn testmap() void = {
const m = newmap();
defer finishmap(&m);
put(&m, "test", "value");
const v = get(m, "test");
assert(v is str);
assert(v as str == "value");
};
@test fn testit() void = {
const m = newmap();
defer finishmap(&m);
put(&m, "test", "value");
let it = newiterator(m);
let count = 0;
for (let e => next(&it)) {
count += 1;
assert(e.key == "test");
assert(e.val == "value");
};
assert(count == 1);
};
|
