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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
#include "map.h"
#include <assert.h>
#include <string.h>
#define MAP_MAX (0.75)
static
uint32_t hash_val(struct us_val v)
{
switch (v.type) {
case VAL_NUM: {
double n = get_num(v);
return *(uint32_t*)&n;
}
case VAL_BOOL: return get_bool(v) ? 1 : 0;
case VAL_NADA: return 2;
case VAL_STR: // TODO: string should use a different hash function
case VAL_ARR:
case VAL_MAP:
case VAL_PROTO:
case VAL_FUNC:
case VAL_CFUNC:
case VAL_UPVAL:
return (uint32_t)(uint64_t)get_obj(v);
}
return 0;
}
static
struct us_map_kv *find_entry(struct us_map_kv *map, int cap, struct us_val k)
{
if (k.type == VAL_NADA) {
us_err("use of nada as a map key");
}
uint32_t hash = hash_val(k);
uint32_t i = hash % cap;
struct us_map_kv *ts = NULL;
while (true) {
struct us_map_kv *item = &map[i];
if (item->key.type == VAL_NADA) {
if (item->val.type == VAL_NADA) {
return ts ? ts : item;
} else if (ts == NULL) {
ts = item;
}
} else if (vals_eql(item->key, k)) {
return item;
}
i = (i + 1) % cap;
}
}
static
void grow_map(struct us_map *map, int new_cap)
{
struct us_map_kv *new = mem_alloc(sizeof(struct us_map_kv) * new_cap);
for (int i = 0; i < new_cap; i++) {
new[i].key = create_nada();
new[i].val = create_nada();
}
map->len = 0;
for (int i = 0; i < map->cap; i++) {
struct us_map_kv *item = &map->e[i];
if (item->key.type == VAL_NADA)
continue;
struct us_map_kv *dst = find_entry(new, new_cap, item->key);
dst->key = item->key;
dst->val = item->val;
map->len++;
}
mem_free(map->e);
map->e = new;
map->cap = new_cap;
}
void map_set_value(struct us_map *map, struct us_val k, struct us_val v)
{
// hijack the __locked key for faster lookup
if (k.type == VAL_STR) {
struct us_str *sk = get_str(k);
if (
sk->len == 11 &&
memcmp(sk->chars, "__keylocked", sk->len) == 0
) {
map->locked = v;
return;
}
}
if (map->len + 1 > map->cap * MAP_MAX) {
int cap = map->cap < 8 ? 8 : map->cap * 2;
grow_map(map, cap);
}
struct us_map_kv *kv = find_entry(map->e, map->cap, k);
if (kv->key.type == VAL_NADA) {
if (val_as_bool(map->locked))
us_err("attempt to modify keylocked map");
map->len++;
}
kv->key = k;
kv->val = v;
}
bool map_get_value(struct us_map *map, struct us_val k, struct us_val *v)
{
if (map->len == 0)
goto fail;
if (k.type == VAL_STR) {
struct us_str *sk = get_str(k);
if (
sk->len == 8 &&
memcmp(sk->chars, "__keylocked", sk->len) == 0
) {
if (v)
*v = map->locked;
return true;
}
}
struct us_map_kv *kv = find_entry(map->e, map->cap, k);
if (kv->key.type == VAL_NADA)
goto fail;
if (v)
*v = kv->val;
return true;
fail:
if (v)
*v = create_nada();
return false;
}
|
