Mercurial
changeset 2:8a43dedbe530
[Dowa] Added HashMap and Updated Arena naming.
| author | June Park <parkjune1995@gmail.com> |
|---|---|
| date | Wed, 24 Sep 2025 13:15:32 -0700 |
| parents | adcfad6e86fb |
| children | 2758f5527d2b |
| files | bazel-bin bazel-testlogs dowa/BUILD dowa/d_memory.c dowa/dowa.h dowa/dowa_test.c |
| diffstat | 6 files changed, 232 insertions(+), 13 deletions(-) [+] |
line wrap: on
line diff
--- a/bazel-bin Wed Sep 24 09:11:20 2025 -0700 +++ b/bazel-bin Wed Sep 24 13:15:32 2025 -0700 @@ -1,1 +1,1 @@ -/private/var/tmp/_bazel_mrjunejune/db79a4b810633db3e4d84b0e91eb071e/execroot/_main/bazel-out/darwin_arm64-fastbuild/bin \ No newline at end of file +/private/var/tmp/_bazel_mrjunejune/db79a4b810633db3e4d84b0e91eb071e/execroot/_main/bazel-out/darwin_arm64-dbg/bin \ No newline at end of file
--- a/bazel-testlogs Wed Sep 24 09:11:20 2025 -0700 +++ b/bazel-testlogs Wed Sep 24 13:15:32 2025 -0700 @@ -1,1 +1,1 @@ -/private/var/tmp/_bazel_mrjunejune/db79a4b810633db3e4d84b0e91eb071e/execroot/_main/bazel-out/darwin_arm64-fastbuild/testlogs \ No newline at end of file +/private/var/tmp/_bazel_mrjunejune/db79a4b810633db3e4d84b0e91eb071e/execroot/_main/bazel-out/darwin_arm64-dbg/testlogs \ No newline at end of file
--- a/dowa/BUILD Wed Sep 24 09:11:20 2025 -0700 +++ b/dowa/BUILD Wed Sep 24 13:15:32 2025 -0700 @@ -1,14 +1,23 @@ load("@rules_cc//cc:cc_library.bzl", "cc_library") +load("@rules_cc//cc:cc_test.bzl", "cc_test") + cc_library( name = "dowa", - srcs = [ - "d_string.c", - "d_memory.c", - ], + srcs = [ + "d_string.c", + "d_memory.c", + ], hdrs = [ "dowa.h", "dowa_internal.h" ], visibility = ["//visibility:public"], ) + +cc_binary( + name = "dowa_test", + srcs = ["dowa_test.c"], + deps = [":dowa"], + args = [], +)
--- a/dowa/d_memory.c Wed Sep 24 09:11:20 2025 -0700 +++ b/dowa/d_memory.c Wed Sep 24 13:15:32 2025 -0700 @@ -1,14 +1,21 @@ #include "dowa.h" // --- Arena --- // -void Dowa_ArenaIntialize(PArena p_arena, size_t capacity) +Dowa_PArena Dowa_Arena_Initialize(size_t capacity) { + Dowa_PArena p_arena; p_arena = malloc(capacity); + if (p_arena == NULL) + { + perror("malloc"); + return NULL; + } p_arena->offset = 0; p_arena->capacity = capacity; + return p_arena; } -void *Dowa_ArenaAllocate(PArena p_arena, size_t size) +void *Dowa_Arena_Allocate(Dowa_PArena p_arena, size_t size) { if (p_arena->offset + size > p_arena->capacity) { @@ -19,10 +26,90 @@ return currnet_ptr; } -void Dowa_ArenaFree(PArena p_arena) +void Dowa_Arena_Free(Dowa_PArena p_arena) { if (p_arena) { free(p_arena->buffer); free(p_arena); } } + +// --- HashMap --- // +Dowa_PHashMap Dowa_HashMap_Create(size_t capacity) +{ + Dowa_PHashMap p_hash_map; + p_hash_map = malloc(sizeof(Dowa_HashMap)); + if (p_hash_map == NULL) + { + return NULL; + } + p_hash_map->entries = calloc(capacity, sizeof *p_hash_map->entries); + if (p_hash_map->entries == NULL) + { + free(p_hash_map); + return NULL; + } + p_hash_map->capacity = capacity; + p_hash_map->current_capacity = 0; + return p_hash_map; +} + +int32 Dowa_HashMap_GetPosition(Dowa_PHashMap p_hash_map, char *key) +{ + int32 hash_val = HASH_KEY_NUMBER; + int32 c; + while ((c = *key++)) + { + hash_val = (hash_val << 5) + hash_val + c; + } + return hash_val % p_hash_map->capacity; +} + +void Dowa_HashMap_PushValue(Dowa_PHashMap p_hash_map, char *key, void *value, size_t value_size) +{ + int idx = Dowa_HashMap_GetPosition(p_hash_map, key); + Dowa_PHashEntry entry = p_hash_map->entries[idx]; + if (entry) + { + free(entry->key); + free(entry->buffer); + } + else + { + entry = malloc(sizeof(Dowa_HashEntry)); + if (entry == NULL) + { + perror("malloc"); + return; + } + p_hash_map->entries[idx] = entry; + } + entry->key = strdup(key); + entry->buffer = malloc(value_size); + if (entry->buffer == NULL) + { + perror("malloc"); + return; + } + entry->capacity = value_size; + memcpy(entry->buffer, value, value_size); + p_hash_map->current_capacity++; +} + +void Dowa_HashMap_PopKey(Dowa_PHashMap p_hash_map, char *key) +{ + int idx = Dowa_HashMap_GetPosition(p_hash_map, key); + Dowa_PHashEntry entry = p_hash_map->entries[idx]; + if (entry) + { + free(entry->key); + free(entry->buffer); + free(entry); + } + p_hash_map->entries[idx] = NULL; + if (p_hash_map->current_capacity > 0) + { + p_hash_map->current_capacity--; + } +} +
--- a/dowa/dowa.h Wed Sep 24 09:11:20 2025 -0700 +++ b/dowa/dowa.h Wed Sep 24 13:15:32 2025 -0700 @@ -2,9 +2,13 @@ #define DOWA #include <stdio.h> +#include <string.h> // stdup #include <stdlib.h> // only for malloc, free, stuff +#include <assert.h> #include "dowa_internal.h" +#define HASH_KEY_NUMBER 5381 // DJD hash number + typedef unsigned int uint32; typedef int int32; typedef unsigned short uint16; @@ -21,10 +25,29 @@ char *buffer; size_t offset; size_t capacity; -} Areana, *PArena; +} Dowa_Areana, *Dowa_PArena; + +extern Dowa_PArena Dowa_Arena_Initialize(size_t capacity); +extern void *Dowa_Arena_Allocate(Dowa_PArena p_arena, size_t size); +extern void Dowa_Arena_Free(Dowa_PArena p_arena); -void Dowa_ArenaIntialize(PArena p_arena, size_t capacity); -void *Dowa_ArenaAllocate(PArena p_arena, size_t size); -void Dowa_ArenaFree(PArena p_arena); +// --- Map --- // +typedef struct { + char *key; + void *buffer; + size_t capacity; +} Dowa_HashEntry, *Dowa_PHashEntry; + +typedef struct { + Dowa_PHashEntry *entries; + size_t capacity; + uint32 current_capacity; +} Dowa_HashMap, *Dowa_PHashMap; + +extern Dowa_PHashMap Dowa_HashMap_Create(size_t capacity); +extern int32 Dowa_HashMap_GetPosition(Dowa_PHashMap p_hash_map, char *key); +extern void Dowa_HashMap_PushValue(Dowa_PHashMap p_hash_map, char *key, void *value, size_t value_size); +extern void Dowa_HashMap_PopKey(Dowa_PHashMap p_hash_map, char *key); + #endif
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/dowa/dowa_test.c Wed Sep 24 13:15:32 2025 -0700 @@ -0,0 +1,100 @@ +#include "dowa.h" + +static void TestArena() { + const size_t capacity = 64; + Dowa_PArena arena = Dowa_Arena_Initialize(capacity); + assert(arena != NULL); + assert(arena->offset == 0); + assert(arena->capacity == capacity); + + // Allocate within capacity + void *p1 = Dowa_Arena_Allocate(arena, 16); + // assert(p1 != NULL); + assert(arena->offset == 16); + + // Allocate more + void *p2 = Dowa_Arena_Allocate(arena, 32); + assert(p2 != NULL); + assert(arena->offset == 48); + + // Overflow allocation should return NULL and not advance offset + void *p3 = Dowa_Arena_Allocate(arena, 20); + assert(p3 == NULL); + assert(arena->offset == 48); + + Dowa_Arena_Free(arena); +} + +static void TestHashMap() { + const size_t capacity = 10; + Dowa_PHashMap map = Dowa_HashMap_Create(capacity); + assert(map != NULL); + assert(map->capacity == capacity); + assert(map->current_capacity == 0); + + // Insert "foo" -> 42 + int val1 = 42; + Dowa_HashMap_PushValue(map, "foo", &val1, sizeof(val1)); + assert(map->current_capacity == 1); + + int idx_foo = Dowa_HashMap_GetPosition(map, "foo"); + Dowa_PHashEntry e_foo = map->entries[idx_foo]; + assert(e_foo != NULL); + assert(strcmp(e_foo->key, "foo") == 0); + assert(*(int*)e_foo->buffer == 42); + + // Overwrite "foo" -> 100 + int val2 = 100; + Dowa_HashMap_PushValue(map, "foo", &val2, sizeof(val2)); + // current_capacity increments again according to your implementation + assert(map->current_capacity == 2); + + Dowa_PHashEntry e_foo2 = map->entries[idx_foo]; + assert(e_foo2 != NULL); + assert(strcmp(e_foo2->key, "foo") == 0); + assert(*(int*)e_foo2->buffer == 100); + + // Insert "bar" -> -7 + int val3 = -7; + Dowa_HashMap_PushValue(map, "bar", &val3, sizeof(val3)); + assert(map->current_capacity == 3); + + int idx_bar = Dowa_HashMap_GetPosition(map, "bar"); + Dowa_PHashEntry e_bar = map->entries[idx_bar]; + assert(e_bar != NULL); + assert(strcmp(e_bar->key, "bar") == 0); + assert(*(int*)e_bar->buffer == -7); + + // Pop "foo" + Dowa_HashMap_PopKey(map, "foo"); + assert(map->entries[idx_foo] == NULL); + assert(map->current_capacity == 2); + + // Pop "bar" + Dowa_HashMap_PopKey(map, "bar"); + assert(map->entries[idx_bar] == NULL); + assert(map->current_capacity == 1); + + // Clean up remaining entries and the map itself + for (size_t i = 0; i < map->capacity; ++i) { + Dowa_PHashEntry ent = map->entries[i]; + if (ent) { + free(ent->key); + free(ent->buffer); + free(ent); + } + } + free(map->entries); + free(map); +} + +int main(void) { + TestArena(); + printf("Arena tests passed.\n"); + + TestHashMap(); + printf("HashMap tests passed.\n"); + + return 0; +} +