Started working on hashmap

5 files changed, 170 insertions, 6 deletions

diff --git a/src/map.c b/src/map.c
new file mode 100644
index 0000000..5e77995
--- /dev/null
+++ b/src/map.c
@@ -0,0 +1,150 @@
+#include "map.h"
+#include "common.h"
+#include "log.h"
+#include "smrt_arena.h"
+
+#include <stdint.h>
+#include <stdio.h>
+#include <string.h>
+
+#define ENTRY_TOMBSTONE 0b0000000000000000000000000000000000000000000000000000000000000001
+#define ENTRY_MASK      0b1111111111111111111111111111111111111111111111111111111111111110
+
+typedef struct {
+    void *key;
+    u64 keylen;
+} map_key_entry_t;
+
+typedef struct _map_t {
+    u64  table_size;
+    u64 *hashes;
+    map_key_entry_t *keys;
+    void **values;
+} _map_t;
+
+u32 hash(u8 *input, u64 inputlen) {
+    // Make this batched + SIMD eventually
+    u32 sum = UINT32_MAX / 2;
+    for (u64 i = 0; i < inputlen; i++) {
+        sum += input[i];
+    }
+    return sum;
+}
+
+map_t map_create(smrt_arena_t *arena, u64 capacity) {
+    map_t map = smrt_arena_push(arena, sizeof(_map_t), true);
+    map->hashes = SMRTA_ALLOC_ARRAY(arena, u64, capacity);
+    map->keys = SMRTA_ALLOC_ARRAY(arena, map_key_entry_t, capacity);
+    map->values = SMRTA_ALLOC_ARRAY(arena, void*, capacity);
+    map->table_size=capacity;
+
+    return map;
+}
+
+i32 map_insert(map_t map, u8 *key, u64 keylen, void *value) {
+    u64 h = hash(key, keylen) & ENTRY_MASK;
+
+    u64 start = h % map->table_size;
+    i64 first_tombstone = -1;
+    for (u64 i = start; i != start - 1; i = (i+1)%map->table_size) {
+        // If didnt find match, insert at first tombstone or current i
+        if (map->keys[i].key == NULL) {
+            if (first_tombstone != -1) i = first_tombstone;
+            map->hashes[i] = h;
+            map->keys[i] = (map_key_entry_t){.key=key, .keylen=keylen, };
+            map->values[i] = value;
+            return 0;
+        }
+
+        u64 h_cmp = map->hashes[i];
+
+        // if tombstone, update first tombstone
+        if (first_tombstone != -1 && (h_cmp & ENTRY_TOMBSTONE) == ENTRY_TOMBSTONE) {
+            first_tombstone = i;
+            continue;
+        }
+
+        h_cmp &= ENTRY_MASK;
+        map_key_entry_t k = map->keys[i];
+        if (k.keylen == keylen &&
+            h == h_cmp         &&
+            memcmp(key, k.key, keylen) != 0)
+        {
+            map->keys[i].key = key;
+            map->values[i] = value;
+        }
+    }
+
+    return -1;
+}
+
+i32 map_delete(map_t map, u8 *key, u64 keylen) {
+    u64 h = hash(key, keylen) & ENTRY_MASK;
+
+    u64 start = h % map->table_size;
+    for (u64 i = start; i != start - 1; i = (i+1)%map->table_size) {
+        if (map->keys[i].key == NULL) {
+            return -1;
+        }
+
+        u64 h_cmp = map->hashes[i];
+
+        // if tombstone, skip
+        if ((h_cmp & ENTRY_TOMBSTONE) == ENTRY_TOMBSTONE) {
+            continue;
+        }
+
+        h_cmp &= ENTRY_MASK;
+        map_key_entry_t k = map->keys[i];
+        if (k.keylen == keylen &&
+            h == h_cmp         &&
+            memcmp(key, k.key, keylen) == 0)
+        {
+             map->keys[i].keylen = 0;
+            *map->hashes &= ENTRY_TOMBSTONE;
+        }
+    }
+
+    return -1;
+}
+
+void *map_lookup(map_t map, u8 *key, u64 keylen) {
+    u64 h = hash(key, keylen) & ENTRY_MASK;
+
+    u64 start = h % map->table_size;
+    for (u64 i = start; i != start - 1; i = (i+1)%map->table_size) {
+        if (map->keys[i].key == NULL) {
+            return NULL;
+        }
+
+        u64 h_cmp = map->hashes[i];
+
+        // if tombstone, skip
+        if ((h_cmp & ENTRY_TOMBSTONE) == ENTRY_TOMBSTONE) {
+            continue;
+        }
+
+        h_cmp &= ENTRY_MASK;
+        map_key_entry_t k = map->keys[i];
+        if (k.keylen == keylen &&
+            h == h_cmp         &&
+            memcmp(key, k.key, keylen) == 0)
+        {
+            return map->values[i];
+        }
+    }
+
+    return NULL;
+}
+
+void map_print(map_t map) {
+    printf("=== MAP ===\n");
+    for (u64 i = 0; i < map->table_size; i++) {
+        if (map->values[i] || (map->hashes[i] & ENTRY_TOMBSTONE) == 1) {
+            printf("%lu %s %lu\n", i, (char*)map->keys[i].key, *(u64*)map->values[i]);
+        } else {
+            printf("%lu\n", i);
+        }
+    }
+    printf("=== END ===\n");
+}
diff --git a/src/map.h b/src/map.h
new file mode 100644
index 0000000..e8183d2
--- /dev/null
+++ b/src/map.h
@@ -0,0 +1,13 @@
+#pragma once
+
+#include "common.h"
+#include "smrt_arena.h"
+
+typedef struct _map_t* map_t;
+
+map_t  map_create(smrt_arena_t *arena, u64 table_size);
+  i32  map_insert(map_t map, u8 *key, u64 keylen, void *value);
+  i32  map_delete(map_t map, u8 *key, u64 keylen);
+ void *map_lookup(map_t map, u8 *key, u64 keylen);
+
+void map_print(map_t map);
diff --git a/src/string.c b/src/string.c
index 413ad5e..795eb95 100644
--- a/src/string.c
+++ b/src/string.c
@@ -106,12 +106,12 @@ i32 strng_app_c(strng_t *dest, char const *source) {
 }
 
 i32 strng_app_v(strng_t *dest, strng_view_t const *source) {
-    u64 slen = source->end - source->start;
+    u64 slen = sv_len(source);
     u64 nlen = dest->len + slen;
     if (nlen > dest->alloc_size) return -1;
 
     char *dst = STRNG_TO(dest)+dest->len;
-    char const *src = source->string+source->start;
+    char const *src = SV_TO(*source);
     memcpy(dst, src, slen);
 
     dest->len = nlen;
diff --git a/src/string.h b/src/string.h
index e3f74cf..9ff4978 100644
--- a/src/string.h
+++ b/src/string.h
@@ -121,10 +121,10 @@ i32   sv_find_char(strng_view_t const *sv, char n);
 
 b32   sv_starts_with(strng_view_t const *sv, char const *prefix);
 b32     sv_ends_with(strng_view_t const *sv, char const *suffix);
-static inline b32 sv_starts_with_c(strng_view_t sv, char c) { return
-                                                            (sv_len(&sv) > 0) && (*SV_TO(sv) == c); }
-static inline b32   sv_ends_with_c(strng_view_t sv, char c) { return
-                                                            (sv_len(&sv) > 0) && (*(sv.string + sv.end) == c); }
+static inline b32 sv_starts_with_c(strng_view_t const *sv, char c) { return
+                                                            (sv_len(sv) > 0) && (*SV_TO(*sv) == c); }
+static inline b32   sv_ends_with_c(strng_view_t const *sv, char c) { return
+                                                            (sv_len(sv) > 0) && (*(sv->string + sv->end) == c); }
 
 b32 sv_eq_case_insensitive(strng_view_t const *sv1, strng_view_t const *sv2);
 
diff --git a/src/unity.c b/src/unity.c
index 6fe4973..a694f13 100644
--- a/src/unity.c
+++ b/src/unity.c
@@ -21,6 +21,7 @@
 #include "slidingwindow.c"
 #include "vec2sw.c"
 #include "deque.c"
+#include "map.c"
 
 // DSP/Audio
 #include "wav.c"