From e301a7d3df7718b8f2d0acd46c4ee7ef0d27da7b Mon Sep 17 00:00:00 2001 From: Mike Lowis Date: Wed, 19 Jun 2024 14:57:52 -0400 Subject: [PATCH] implemented basic dictionary --- build.sh | 2 ++ cerise-c.m | 1 + runtime.h | 32 +++++++++++++++++--- runtime/Array.c | 34 ++++++++++++++++----- runtime/Dict.c | 77 ++++++++++++++++++++++++++++++++++++++++++++++++ runtime/Hash.c | 19 ------------ runtime/String.c | 6 ++-- 7 files changed, 138 insertions(+), 33 deletions(-) create mode 100644 runtime/Dict.c delete mode 100644 runtime/Hash.c diff --git a/build.sh b/build.sh index a9d571c..bf84302 100755 --- a/build.sh +++ b/build.sh @@ -1,5 +1,7 @@ #!/bin/sh +rm libruntime.a runtime/*.o + for f in runtime/*.c; do printf "CC %s\n" "$f" gcc -c -I. -O2 -o "${f%.c}.o" "$f" & diff --git a/cerise-c.m b/cerise-c.m index e1b7fa7..f37fc59 100644 --- a/cerise-c.m +++ b/cerise-c.m @@ -102,6 +102,7 @@ TestHashOps() def item = 42 set hash["foo"] = item assert hash["foo"] == 42 + assert hash["foo"] == "bar" assert hash["baz"] == "boo" } diff --git a/runtime.h b/runtime.h index 67e24e1..d6f9fca 100644 --- a/runtime.h +++ b/runtime.h @@ -25,7 +25,7 @@ //#define VALUE_FALSE 0x2llu //#define VALUE_TRUE 0x3llu -//#define NAN_TAG_RECORD 0x0000000000000000llu +#define NAN_TAG_DICT 0x0000000000000000llu #define NAN_TAG_ARRAY 0x0001000000000000llu #define NAN_TAG_STRING 0x0002000000000000llu //#define NAN_TAG_BLOCK 0x0003000000000000llu @@ -57,9 +57,23 @@ typedef struct { typedef struct { uint64_t length; - Value values[]; + uint64_t capacity; + Value* values; } Array; +typedef struct DictNode { + struct DictNode* left; + struct DictNode* right; + Value key; + Value value; + uint32_t hash; +} DictNode; + +typedef struct { + uint64_t length; + DictNode* root; +} Dict; + /* Value Tests *************************************************/ @@ -97,11 +111,11 @@ static inline bool IsString(Value val) { } static inline bool IsArray(Value val) { - return (val.as_uint64 & HIGH16_TAG) == NAN_TAG_STRING; + return (val.as_uint64 & HIGH16_TAG) == NAN_TAG_ARRAY; } static inline bool IsDict(Value val) { - return (val.as_uint64 & HIGH16_TAG) == NAN_TAG_STRING; + return (val.as_uint64 & HIGH16_TAG) == NAN_TAG_DICT; } @@ -129,6 +143,16 @@ static String* ValueAsString(Value val) { return (String*)(val.as_uint64 & MASK_POINTER); } +static Array* ValueAsArray(Value val) { + assert(IsArray(val)); + return (Array*)(val.as_uint64 & MASK_POINTER); +} + +static Dict* ValueAsDict(Value val) { + assert(IsDict(val)); + return (Dict*)(val.as_uint64 & MASK_POINTER); +} + //static Array* to_array(Value val) { // assert(is_array(val)); diff --git a/runtime/Array.c b/runtime/Array.c index b92f5e5..442fb33 100644 --- a/runtime/Array.c +++ b/runtime/Array.c @@ -1,19 +1,39 @@ #include "runtime.h" +static uint64_t NextPow2(uint64_t val) { + val--; + val |= val >> 1; + val |= val >> 2; + val |= val >> 4; + val |= val >> 8; + val |= val >> 16; + val |= val >> 32; + val++; + return val; +} + Value MakeArray(int32_t nslots) { -// Value* record = calloc(2,sizeof(Value)); -// record[0] = MakeInt(1); -// record[1] = MakeInt(nslots); // -// record[2] = MakeInt(nslots); // -// return (Value){ .as_uint64 = (NAN_TAG_ARRAY | (uintptr_t)record) }; - return MakeNil(); + Array* array = calloc(1, sizeof(Array)); + array->length = nslots; + array->capacity = NextPow2(nslots); + array->values = calloc(nslots, sizeof(Value)); + return (Value){ .as_uint64 = (NAN_TAG_ARRAY | (uintptr_t)array) }; } void Array_Set(Value array, int index, Value value) { + Array* ary = ValueAsArray(array); + if (index >= ary->length) { + Error(MakeString("array index out of bounds")); + } + ary->values[index] = value; } Value Array_Get(Value array, int index) { - return MakeNil(); + Array* ary = ValueAsArray(array); + if (index >= ary->length) { + Error(MakeString("array index out of bounds")); + } + return ary->values[index]; } diff --git a/runtime/Dict.c b/runtime/Dict.c new file mode 100644 index 0000000..d413869 --- /dev/null +++ b/runtime/Dict.c @@ -0,0 +1,77 @@ +#include "runtime.h" + +static uint32_t Hash(Value val) { + String* string = ValueAsString(val); + char* key = string->bytes; + uint32_t a=31415u, b=27183u, hash; + for (hash=0; *key; key++, a *= b) { + hash = (a * hash) + *key; + } + hash = (hash + 0x7ed55d16) + (hash << 12); + hash = (hash ^ 0xc761c23c) ^ (hash >> 19); + hash = (hash + 0x165667b1) + (hash << 5); + hash = (hash + 0xd3a2646c) ^ (hash << 9); + hash = (hash + 0xfd7046c5) + (hash << 3); + hash = (hash ^ 0xb55a4f09) ^ (hash >> 16); + return hash; +} + +static int CompareNode(DictNode* left, DictNode* right) { + int cmp = left->hash - right->hash; + if (cmp == 0) { + cmp = ValueAsBool(OpEq(left->key, right->key)) ? 0 : 1; + } + return cmp; +} + +static DictNode** FindNode(DictNode** root, DictNode* node) { + DictNode** curr = root; + while(*curr != NULL) { + int cmp = CompareNode(node, *curr); + if (cmp < 0) + curr = &((*curr)->left); + else if (cmp > 0) + curr = &((*curr)->right); + else + break; + } + return curr; +} + +Value MakeDict(int32_t nslots) { + Dict* dict = calloc(1, sizeof(Dict)); + return (Value){ .as_uint64 = (NAN_TAG_DICT | (uintptr_t)dict) }; +} + +void Dict_Set(Value dictionary, Value key, Value value) +{ + DictNode node = { + .hash = Hash(key), + .key = key, + .value = value + }; + Dict* dict = ValueAsDict(dictionary); + DictNode** curr = FindNode(&(dict->root), &node); + if (!*curr) { + DictNode* new_node = calloc(1, sizeof(DictNode)); + *new_node = node; + *curr = new_node; + } else { + (*curr)->value = value; + } +} + +Value Dict_Get(Value dictionary, Value key) +{ + DictNode node = { + .hash = Hash(key), + .key = key, + }; + Dict* dict = ValueAsDict(dictionary); + DictNode** curr = FindNode(&(dict->root), &node); + Value result = MakeNil(); + if (*curr) { + result = (*curr)->value; + } + return result; +} diff --git a/runtime/Hash.c b/runtime/Hash.c deleted file mode 100644 index 28b031e..0000000 --- a/runtime/Hash.c +++ /dev/null @@ -1,19 +0,0 @@ -#include "runtime.h" - -Value MakeDict(int32_t nslots) { -// Value* record = calloc(2,sizeof(Value)); -// record[0] = MakeInt(1); -// record[1] = MakeInt(nslots); // -// record[2] = MakeInt(nslots); // -// return (Value){ .as_uint64 = (NAN_TAG_ARRAY | (uintptr_t)record) }; - return MakeNil(); -} - -void Dict_Set(Value hash, Value key, Value value) -{ -} - -Value Dict_Get(Value hash, Value key) -{ - return MakeNil(); -} diff --git a/runtime/String.c b/runtime/String.c index 3fea402..d73c1ce 100644 --- a/runtime/String.c +++ b/runtime/String.c @@ -5,9 +5,9 @@ Value MakeString(char* s) { String* str = calloc(sizeof(String) + sz + 1, 1); str->length = sz; strncpy(str->bytes, s, sz+1); - return (Value){ - .as_uint64 = (NAN_TAG_STRING | (uint64_t)str) - }; + Value ret = (Value){ .as_uint64 = (NAN_TAG_STRING | (uint64_t)str) }; + assert(IsString(ret)); + return ret; } Value String_Get(Value hash, int index) -- 2.54.0