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
|
import "!mem.pry";
import "!stdlib.pry";
let HashMapEntry = struct {
key: *i8,
value: *void,
next: *HashMapEntry,
};
let HashMap = struct {
buckets: **HashMapEntry,
bucket_count: i64,
arena: *arena,
};
let simple_hash = (key: *i8, bucket_count: i64) => i64 {
let hash = 0;
let i = 0;
while true {
let c = *(key + cast(*i8, i));
if c == '\0' {
return hash % bucket_count;
};
let x = cast(i64, c);
hash = hash + x;
i = i + 1;
};
return hash % bucket_count;
};
let hashmap_init = (bucket_count: i64, alloc: *arena) => *HashMap {
let map = cast(*HashMap, arena_alloc(alloc, sizeof(HashMap)));
(*map).buckets = cast(**HashMapEntry, arena_alloc(alloc, sizeof(*HashMapEntry) * bucket_count));
(*map).bucket_count = bucket_count;
(*map).arena = alloc;
let i = 0;
while i < bucket_count {
(*((*map).buckets + cast(**HashMapEntry, i))) = cast(*HashMapEntry, null);
i = i + 1;
};
return map;
};
let hashmap_put = (map: *HashMap, key: *i8, value: *void) => void {
let bucket_index = simple_hash(key, (*map).bucket_count);
let bucket = *((*map).buckets + cast(**HashMapEntry, bucket_index));
let current = bucket;
while current != cast(*HashMapEntry, null) {
if strcmp((*current).key, key) {
(*current).value = value;
return;
};
current = (*current).next;
};
let new_entry = cast(*HashMapEntry, arena_alloc((*map).arena, sizeof(HashMapEntry)));
(*new_entry).key = key;
(*new_entry).value = value;
(*new_entry).next = bucket;
(*((*map).buckets + cast(**HashMapEntry, bucket_index))) = new_entry;
return;
};
let hashmap_get = (map: *HashMap, key: *i8) => *void {
let bucket_index = simple_hash(key, (*map).bucket_count);
let current = *((*map).buckets + cast(**HashMapEntry, bucket_index));
while current != cast(*HashMapEntry, null) {
if strcmp((*current).key, key) {
return (*current).value;
};
current = (*current).next;
};
return cast(*void, null);
};
|
