microscript: add maps

1 files changed, 143 insertions, 0 deletions

diff --git a/uscript/map.c b/uscript/map.c
new file mode 100644
index 0000000..01f2462
--- /dev/null
+++ b/uscript/map.c
@@ -0,0 +1,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_ZILCH: 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_ZILCH) {
+                us_err("use of zilch 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_ZILCH) {
+                        if (item->val.type == VAL_ZILCH) {
+                                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_zilch();
+                new[i].val = create_zilch();
+        }
+
+        map->len = 0;
+        for (int i = 0; i < map->cap; i++) {
+                struct us_map_kv *item = &map->e[i];
+                if (item->key.type == VAL_ZILCH)
+                        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_ZILCH) {
+                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_ZILCH)
+                goto fail;
+
+        if (v)
+                *v = kv->val;
+        return true;
+fail:
+        if (v)
+                *v = create_zilch();
+        return false;
+}