[PATCH olang 0/2] introduce hash map data structure

[PATCH olang 0/2] introduce hash map data structure

[Johnny Richard]

This patchset creates a simple hash map implementation. We need this
data structure before start implementing the parser. After this patchset
I believe we should be able to start the parser.

Johnny Richard (2):
  build: add clean target on root Makefile
  utils: create hash map data structure

 Makefile              |   6 ++
 src/map.c             | 128 ++++++++++++++++++++++++++++++++++++++++++
 src/map.h             |  59 +++++++++++++++++++
 tests/unit/map_test.c |  73 ++++++++++++++++++++++++
 4 files changed, 266 insertions(+)
 create mode 100644 src/map.c
 create mode 100644 src/map.h
 create mode 100644 tests/unit/map_test.c

-- 
2.43.2

[PATCH olang 1/2] build: add clean target on root Makefile

[Johnny Richard]

In order to make easier recompile the whole project and start from a
fresh environemnt, this patch introduce a **clean** target on project
root Makefile which uses the tests/unit and tests/integration **clean**.

Signed-off-by: Johnny Richard <johnny@johnnyrichard.com>
---
 Makefile | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/Makefile b/Makefile
index ea6ba53..662d039 100644
--- a/Makefile
+++ b/Makefile
@@ -38,6 +38,12 @@ unit-test:
 	$(MAKE)
 	$(MAKE) -C tests/unit/
 
+.PHONY: clean
+clean:
+	$(MAKE) -C tests/integration/ clean
+	$(MAKE) -C tests/unit/ clean
+	@rm -rf build/ 0c
+
 .PHONY: check
 check:
 	$(MAKE)
-- 
2.43.2

[PATCH olang 2/2] utils: create hash map data structure

[Johnny Richard]

This is a simple hash map implementation using FNV1A 32 bits hash
function.  The map starts with capacity of 32 but is expandable.

Initially there is no function to destroy the map.  Hence, the memory
ownership will be on the callee.

Signed-off-by: Johnny Richard <johnny@johnnyrichard.com>
---
 src/map.c             | 128 ++++++++++++++++++++++++++++++++++++++++++
 src/map.h             |  59 +++++++++++++++++++
 tests/unit/map_test.c |  73 ++++++++++++++++++++++++
 3 files changed, 260 insertions(+)
 create mode 100644 src/map.c
 create mode 100644 src/map.h
 create mode 100644 tests/unit/map_test.c

diff --git a/src/map.c b/src/map.c
new file mode 100644
index 0000000..532ba3b
--- /dev/null
+++ b/src/map.c
@@ -0,0 +1,128 @@
+/*
+ * Copyright (C) 2024 olang maintainers
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <https://www.gnu.org/licenses/>.
+ */
+#include "map.h"
+#include "arena.h"
+
+#include <assert.h>
+#include <errno.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+static uint32_t
+u32_fnv1a_hash(const char *s);
+
+static void
+map_init(map_t *map);
+
+static char *
+__strdup(const char *s, arena_t *arena);
+
+map_t *
+map_new(arena_t *arena)
+{
+    map_t *map = (map_t *)arena_alloc(arena, sizeof(map_t));
+    if (map == NULL) {
+        fprintf(stderr, "[FATAL] Out of memory: map_new: %s\n", strerror(errno));
+        exit(EXIT_FAILURE);
+    }
+    map->arena = arena;
+    map_init(map);
+    return map;
+}
+
+static void
+map_init(map_t *map)
+{
+    assert(map);
+    map->entries = (map_entry_t *)arena_alloc(map->arena, MAP_INITIAL_CAPACITY * sizeof(map_entry_t));
+    assert(map->entries != NULL);
+    memset(map->entries, 0, MAP_INITIAL_CAPACITY * sizeof(map_entry_t));
+    if (map->entries == NULL) {
+        fprintf(stderr, "[FATAL] Out of memory: map_init: %s\n", strerror(errno));
+        exit(EXIT_FAILURE);
+    }
+    map->capacity = MAP_INITIAL_CAPACITY;
+}
+
+static uint32_t
+u32_fnv1a_hash(const char *s)
+{
+    uint32_t hash = U32_FNV1A_OFFSET_BASIS;
+    size_t len = strlen(s);
+    for (size_t i = 0; i < len; ++i) {
+        hash ^= s[i];
+        hash *= U32_FNV1A_PRIME;
+    }
+    return hash;
+}
+
+bool
+map_put(map_t *map, char *key, void *value)
+{
+    assert(map && key);
+    uint32_t hash = u32_fnv1a_hash(key);
+    map_entry_t *entry = &(map->entries[hash & (map->capacity - 1)]);
+
+    while (entry != NULL) {
+        if (entry->hash == hash && strcmp(entry->key, key) == 0) {
+            entry->value = value;
+            return true;
+        }
+        if (entry->next == NULL)
+            break;
+        entry = entry->next;
+    }
+
+    if (entry->key == NULL) {
+        *entry = (map_entry_t){ .key = __strdup(key, map->arena), .hash = hash, .value = value, .next = NULL };
+    } else {
+        entry->next = (map_entry_t *)arena_alloc(map->arena, sizeof(map_entry_t));
+        *entry->next = (map_entry_t){ .key = __strdup(key, map->arena), .hash = hash, .value = value, .next = NULL };
+    }
+
+    return true;
+}
+
+void *
+map_get(map_t *map, char *key)
+{
+    uint32_t hash = u32_fnv1a_hash(key);
+    map_entry_t *entry = &map->entries[hash & (map->capacity - 1)];
+    while (entry != NULL) {
+        if (entry->hash == hash && strcmp(entry->key, key) == 0) {
+            return entry->value;
+        }
+        entry = entry->next;
+    }
+    return NULL;
+}
+
+static char *
+__strdup(const char *s, arena_t *arena)
+{
+    size_t slen = strlen(s);
+    char *result = arena_alloc(arena, slen + 1);
+    if (result == NULL) {
+        return NULL;
+    }
+
+    memcpy(result, s, slen + 1);
+    return result;
+}
diff --git a/src/map.h b/src/map.h
new file mode 100644
index 0000000..123ad4d
--- /dev/null
+++ b/src/map.h
@@ -0,0 +1,59 @@
+/*
+ * Copyright (C) 2024 olang maintainers
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <https://www.gnu.org/licenses/>.
+ */
+#ifndef MAP_H
+#define MAP_H
+
+#include "arena.h"
+
+#include <stdbool.h>
+#include <stdint.h>
+#include <string.h>
+
+#define MAP_INITIAL_CAPACITY 32
+
+#define U32_FNV1A_PRIME 0x01000193
+#define U32_FNV1A_OFFSET_BASIS 0x811c9dc5
+
+typedef struct map map_t;
+typedef struct map_bucket map_bucket_t;
+typedef struct map_entry map_entry_t;
+
+typedef struct map
+{
+    arena_t *arena;
+    map_entry_t *entries;
+    size_t capacity;
+} map_t;
+
+typedef struct map_entry
+{
+    char *key;
+    void *value;
+    uint32_t hash;
+    map_entry_t *next;
+} map_entry_t;
+
+map_t *
+map_new(arena_t *arena);
+
+bool
+map_put(map_t *map, char *key, void *value);
+
+void *
+map_get(map_t *map, char *key);
+
+#endif /* MAP_H */
diff --git a/tests/unit/map_test.c b/tests/unit/map_test.c
new file mode 100644
index 0000000..3eb9acd
--- /dev/null
+++ b/tests/unit/map_test.c
@@ -0,0 +1,73 @@
+/*
+ * Copyright (C) 2024 olang maintainers
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <https://www.gnu.org/licenses/>.
+ */
+#define MUNIT_ENABLE_ASSERT_ALIASES
+
+#include "arena.h"
+#include "map.h"
+#include "munit.h"
+#include <stdio.h>
+
+#define MAP_TEST_ARENA_CAPACITY (1024 * 16)
+
+static MunitResult
+test_create_new(const MunitParameter params[], void *user_data_or_fixture)
+{
+    arena_t arena = arena_new(MAP_TEST_ARENA_CAPACITY);
+
+    map_t *map = map_new(&arena);
+
+    assert_not_null(map);
+
+    arena_free(&arena);
+
+    return MUNIT_OK;
+}
+
+static MunitResult
+test_map_put_and_get(const MunitParameter params[], void *user_data_or_fixture)
+{
+    arena_t arena = arena_new(MAP_TEST_ARENA_CAPACITY);
+    map_t *map = map_new(&arena);
+
+    int n1 = 1;
+    int n2 = 2;
+
+    map_put(map, "n1", (void *)&n1);
+    map_put(map, "n2", (void *)&n2);
+
+    assert_int(*((int *)map_get(map, "n1")), ==, n1);
+    assert_int(*((int *)map_get(map, "n2")), ==, n2);
+
+    arena_free(&arena);
+
+    return MUNIT_OK;
+}
+
+static MunitTest tests[] = {
+    { "/test_create_new", test_create_new, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
+    { "/test_map_put_and_get", test_map_put_and_get, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
+    { NULL, NULL, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL }
+};
+
+static const MunitSuite suite = { "/map", tests, NULL, 1, MUNIT_SUITE_OPTION_NONE };
+
+int
+main(int argc, char *argv[])
+{
+    return munit_suite_main(&suite, NULL, argc, argv);
+    return EXIT_SUCCESS;
+}
-- 
2.43.2

[olang/patches/.build.yml] build success

[builds.sr.ht]

olang/patches/.build.yml: SUCCESS in 44s

[introduce hash map data structure][0] from [Johnny Richard][1]

[0]: https://lists.sr.ht/~johnnyrichard/olang-devel/patches/49732
[1]: mailto:johnny@johnnyrichard.com

✓ #1155192 SUCCESS olang/patches/.build.yml https://builds.sr.ht/~johnnyrichard/job/1155192

Re: [PATCH olang 2/2] utils: create hash map data structure

[Carlos Maniero]

Nice work man! I've just a few suggestions.

Changes I'm proposing:
- replace __strdup with a arena function.
- create a function to calculate the hash index.
- some style changes on map_put

---->8----
diff --git a/src/arena.c b/src/arena.c
index ae33e6a..d420002 100644
--- a/src/arena.c
+++ b/src/arena.c
@@ -17,6 +17,7 @@
 #include "arena.h"
 #include <stdio.h>
 #include <stdlib.h>
+#include <string.h>
 
 arena_t
 arena_new(size_t size)
@@ -51,3 +52,16 @@ arena_free(arena_t *arena)
     arena->size = 0;
     free(arena->region);
 }
+
+char *
+arena_strdup(arena_t *arena, const char *s)
+{
+    size_t slen = strlen(s);
+    char *result = arena_alloc(arena, slen + 1);
+    if (result == NULL) {
+        return NULL;
+    }
+
+    memcpy(result, s, slen + 1);
+    return result;
+}
diff --git a/src/arena.h b/src/arena.h
index 157165c..230eb5b 100644
--- a/src/arena.h
+++ b/src/arena.h
@@ -38,4 +38,7 @@ arena_release(arena_t *arena);
 void
 arena_free(arena_t *arena);
 
+char *
+arena_strdup(arena_t *arena, const char *s);
+
 #endif
diff --git a/src/map.c b/src/map.c
index 532ba3b..849130e 100644
--- a/src/map.c
+++ b/src/map.c
@@ -31,8 +31,8 @@ u32_fnv1a_hash(const char *s);
 static void
 map_init(map_t *map);
 
-static char *
-__strdup(const char *s, arena_t *arena);
+static uint32_t
+map_index(map_t *map, uint32_t hash);
 
 map_t *
 map_new(arena_t *arena)
@@ -78,24 +78,27 @@ map_put(map_t *map, char *key, void *value)
 {
     assert(map && key);
     uint32_t hash = u32_fnv1a_hash(key);
-    map_entry_t *entry = &(map->entries[hash & (map->capacity - 1)]);
+    map_entry_t *entry = map->entries + map_index(map, hash);
 
-    while (entry != NULL) {
+    if (entry == NULL) {
+        *entry = (map_entry_t){ .key = arena_strdup(map->arena, key), .hash = hash, .value = value, .next = NULL };
+        return true;
+    }
+
+    do {
         if (entry->hash == hash && strcmp(entry->key, key) == 0) {
             entry->value = value;
-            return true;
+            break;
         }
-        if (entry->next == NULL)
+        if (entry->next == NULL) {
+            entry->next = (map_entry_t *)arena_alloc(map->arena, sizeof(map_entry_t));
+            *entry->next =
+                (map_entry_t){ .key = arena_strdup(map->arena, key), .hash = hash, .value = value, .next = NULL };
+
             break;
+        }
         entry = entry->next;
-    }
-
-    if (entry->key == NULL) {
-        *entry = (map_entry_t){ .key = __strdup(key, map->arena), .hash = hash, .value = value, .next = NULL };
-    } else {
-        entry->next = (map_entry_t *)arena_alloc(map->arena, sizeof(map_entry_t));
-        *entry->next = (map_entry_t){ .key = __strdup(key, map->arena), .hash = hash, .value = value, .next = NULL };
-    }
+    } while (entry != NULL);
 
     return true;
 }
@@ -104,7 +107,7 @@ void *
 map_get(map_t *map, char *key)
 {
     uint32_t hash = u32_fnv1a_hash(key);
-    map_entry_t *entry = &map->entries[hash & (map->capacity - 1)];
+    map_entry_t *entry = map->entries + map_index(map, hash);
     while (entry != NULL) {
         if (entry->hash == hash && strcmp(entry->key, key) == 0) {
             return entry->value;
@@ -114,15 +117,9 @@ map_get(map_t *map, char *key)
     return NULL;
 }
 
-static char *
-__strdup(const char *s, arena_t *arena)
+static uint32_t
+map_index(map_t *map, uint32_t hash)
 {
-    size_t slen = strlen(s);
-    char *result = arena_alloc(arena, slen + 1);
-    if (result == NULL) {
-        return NULL;
-    }
-
-    memcpy(result, s, slen + 1);
-    return result;
+    uint32_t capacity_mask = map->capacity - 1;
+    return hash & capacity_mask;
 }
diff --git a/tests/unit/map_test.c b/tests/unit/map_test.c
index 3eb9acd..fab4c69 100644
--- a/tests/unit/map_test.c
+++ b/tests/unit/map_test.c
@@ -52,7 +52,10 @@ test_map_put_and_get(const MunitParameter params[], void *user_data_or_fixture)
     assert_int(*((int *)map_get(map, "n1")), ==, n1);
     assert_int(*((int *)map_get(map, "n2")), ==, n2);
 
+    map_put(map, "n1", (void *)&n2);
+
     arena_free(&arena);
+    assert_int(*((int *)map_get(map, "n1")), ==, n2);
 
     return MUNIT_OK;
 }

Re: [PATCH olang 2/2] utils: create hash map data structure

[Johnny Richard]

On Tue, Feb 27, 2024 at 02:26:17PM -0300, Carlos Maniero wrote:
> diff --git a/src/arena.h b/src/arena.h
> index 157165c..230eb5b 100644
> --- a/src/arena.h
> +++ b/src/arena.h
> @@ -38,4 +38,7 @@ arena_release(arena_t *arena);
>  void
>  arena_free(arena_t *arena);
>  
> +char *
> +arena_strdup(arena_t *arena, const char *s);

I would move it to arena if the function wasn't cstr specific. I mean,
a memcpy would be a better fit since it's agnostic / generic.

> +
>  #endif
> diff --git a/src/map.c b/src/map.c
> index 532ba3b..849130e 100644
> --- a/src/map.c
> +++ b/src/map.c
> @@ -31,8 +31,8 @@ u32_fnv1a_hash(const char *s);
>  static void
>  map_init(map_t *map);
>  
> -static char *
> -__strdup(const char *s, arena_t *arena);
> +static uint32_t
> +map_index(map_t *map, uint32_t hash);
>  
>  map_t *
>  map_new(arena_t *arena)
> @@ -78,24 +78,27 @@ map_put(map_t *map, char *key, void *value)
>  {
>      assert(map && key);
>      uint32_t hash = u32_fnv1a_hash(key);
> -    map_entry_t *entry = &(map->entries[hash & (map->capacity - 1)]);
> +    map_entry_t *entry = map->entries + map_index(map, hash);
>  
> -    while (entry != NULL) {
> +    if (entry == NULL) {
> +        *entry = (map_entry_t){ .key = arena_strdup(map->arena, key), .hash = hash, .value = value, .next = NULL };

It can cause a segfault, perhaps we should keep the 'entry->key == NULL'
since the entries are filled up with zeros (0).

> +static uint32_t
> +map_index(map_t *map, uint32_t hash)

Nice change, what do you think about rename it to **map_get_index**?

> diff --git a/tests/unit/map_test.c b/tests/unit/map_test.c
> index 3eb9acd..fab4c69 100644
> --- a/tests/unit/map_test.c
> +++ b/tests/unit/map_test.c
> @@ -52,7 +52,10 @@ test_map_put_and_get(const MunitParameter params[], void *user_data_or_fixture)
>      assert_int(*((int *)map_get(map, "n1")), ==, n1);
>      assert_int(*((int *)map_get(map, "n2")), ==, n2);
>  
> +    map_put(map, "n1", (void *)&n2);
> +
>      arena_free(&arena);
> +    assert_int(*((int *)map_get(map, "n1")), ==, n2);

Wired this work after free arena.

Re: [PATCH olang 2/2] utils: create hash map data structure

[Carlos Maniero]

Fixing the suggestions based on Johnny's comments:

- on map_test I was asserting after freeing the memory
- on map.c there was a bug where I was valdating that the entry was NULL
  not the entry->key which was leading to always having an empty first
  entry (not a SEGFAULT).
- It does not makes sense to have strdup on arena.
  - Instead I just kept the convention to have a single _.

If you think we are good to go, please send a v2. So it will trigger the
pipeline.

--->8---
diff --git a/src/map.c b/src/map.c
index 532ba3b..6665e18 100644
--- a/src/map.c
+++ b/src/map.c
@@ -32,7 +32,10 @@ static void
 map_init(map_t *map);
 
 static char *
-__strdup(const char *s, arena_t *arena);
+_strdup(const char *s, arena_t *arena);
+
+static uint32_t
+map_get_index(map_t *map, uint32_t hash);
 
 map_t *
 map_new(arena_t *arena)
@@ -78,24 +81,26 @@ map_put(map_t *map, char *key, void *value)
 {
     assert(map && key);
     uint32_t hash = u32_fnv1a_hash(key);
-    map_entry_t *entry = &(map->entries[hash & (map->capacity - 1)]);
+    map_entry_t *entry = map->entries + map_get_index(map, hash);
 
-    while (entry != NULL) {
+    if (entry->key == NULL) {
+        *entry = (map_entry_t){ .key = _strdup(key, map->arena), .hash = hash, .value = value, .next = NULL };
+        return true;
+    }
+
+    do {
         if (entry->hash == hash && strcmp(entry->key, key) == 0) {
             entry->value = value;
-            return true;
+            break;
         }
-        if (entry->next == NULL)
+        if (entry->next == NULL) {
+            entry->next = (map_entry_t *)arena_alloc(map->arena, sizeof(map_entry_t));
+            *entry->next = (map_entry_t){ .key = _strdup(key, map->arena), .hash = hash, .value = value, .next = NULL };
+
             break;
+        }
         entry = entry->next;
-    }
-
-    if (entry->key == NULL) {
-        *entry = (map_entry_t){ .key = __strdup(key, map->arena), .hash = hash, .value = value, .next = NULL };
-    } else {
-        entry->next = (map_entry_t *)arena_alloc(map->arena, sizeof(map_entry_t));
-        *entry->next = (map_entry_t){ .key = __strdup(key, map->arena), .hash = hash, .value = value, .next = NULL };
-    }
+    } while (entry != NULL);
 
     return true;
 }
@@ -104,7 +109,7 @@ void *
 map_get(map_t *map, char *key)
 {
     uint32_t hash = u32_fnv1a_hash(key);
-    map_entry_t *entry = &map->entries[hash & (map->capacity - 1)];
+    map_entry_t *entry = map->entries + map_get_index(map, hash);
     while (entry != NULL) {
         if (entry->hash == hash && strcmp(entry->key, key) == 0) {
             return entry->value;
@@ -114,8 +119,15 @@ map_get(map_t *map, char *key)
     return NULL;
 }
 
+static uint32_t
+map_get_index(map_t *map, uint32_t hash)
+{
+    uint32_t capacity_mask = map->capacity - 1;
+    return hash & capacity_mask;
+}
+
 static char *
-__strdup(const char *s, arena_t *arena)
+_strdup(const char *s, arena_t *arena)
 {
     size_t slen = strlen(s);
     char *result = arena_alloc(arena, slen + 1);
diff --git a/tests/unit/map_test.c b/tests/unit/map_test.c
index 3eb9acd..449bca6 100644
--- a/tests/unit/map_test.c
+++ b/tests/unit/map_test.c
@@ -52,6 +52,10 @@ test_map_put_and_get(const MunitParameter params[], void *user_data_or_fixture)
     assert_int(*((int *)map_get(map, "n1")), ==, n1);
     assert_int(*((int *)map_get(map, "n2")), ==, n2);
 
+    map_put(map, "n1", (void *)&n2);
+
+    assert_int(*((int *)map_get(map, "n1")), ==, n2);
+
     arena_free(&arena);
 
     return MUNIT_OK;

Re: [PATCH olang 2/2] utils: create hash map data structure

[Johnny Richard]

On Tue, Feb 27, 2024 at 03:44:56PM -0300, Carlos Maniero wrote:
> Fixing the suggestions based on Johnny's comments:
> 
> - on map_test I was asserting after freeing the memory
> - on map.c there was a bug where I was valdating that the entry was NULL
>   not the entry->key which was leading to always having an empty first
>   entry (not a SEGFAULT).
> - It does not makes sense to have strdup on arena.
>   - Instead I just kept the convention to have a single _.
> 
> If you think we are good to go, please send a v2. So it will trigger the
> pipeline.

I applied you change to a version 2, I have not comments, this fixup
looks good.

Thanks for the scissor patch.

Re: [PATCH olang 2/2] utils: create hash map data structure

[Johnny Richard]

Patcheset SUPERSEDED:

https://lists.sr.ht/~johnnyrichard/olang-devel/%3C20240227195958.12551-1-johnny%40johnnyrichard.com%3E