From mboxrd@z Thu Jan 1 00:00:00 1970 Authentication-Results: mail-a.sr.ht; dkim=pass header.d=johnnyrichard.com header.i=@johnnyrichard.com Received: from out-181.mta1.migadu.com (out-181.mta1.migadu.com [IPv6:2001:41d0:203:375::b5]) by mail-a.sr.ht (Postfix) with ESMTPS id 5E62A20203 for <~johnnyrichard/olang-devel@lists.sr.ht>; Tue, 27 Feb 2024 19:00:27 +0000 (UTC) X-Report-Abuse: Please report any abuse attempt to abuse@migadu.com and include these headers. DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=johnnyrichard.com; s=key1; t=1709060427; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=F9JvuL2erzJvTfAIatNR0tlH43sRuEjQ7kdkjBelXY8=; b=cDORHV3E+GVzY5GNtrlAmR5M5UIslbfenucLL0HCHJdhJGtM+9hzzqcYnMJf0Y2gGwwsS1 NSqUZJgMx89lqL3jz+wFab5vHwx9UaR6SkUG/YjOBS22qxv8CyOckplO1wDjsmSnlp1y0i zyr2s+c9H5h4HvYPP6uEKLDM2RTXypzbCqMXe+f4K2pXpm+RLbaDpifIe/13qfYjxZiWN0 Gqqz+GEV/yBRuChSilB03oS/3ANsazgYMnpDiEjZ26TYUaVzTnUO3tza/fdYuSsfh56uIs 3FoCEywkBofpW28Bi4wMgV+v37+RLGO0Y0mYPVDzbmCOWZukV4PDGGUrTdcuVA== From: Johnny Richard To: ~johnnyrichard/olang-devel@lists.sr.ht Cc: Johnny Richard Subject: [PATCH olang v2 2/2] utils: create hash map data structure Date: Tue, 27 Feb 2024 20:59:08 +0100 Message-ID: <20240227195958.12551-3-johnny@johnnyrichard.com> In-Reply-To: <20240227195958.12551-1-johnny@johnnyrichard.com> References: <20240227195958.12551-1-johnny@johnnyrichard.com> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Migadu-Flow: FLOW_OUT X-TUID: szOzdyHpbHG3 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 --- src/map.c | 140 ++++++++++++++++++++++++++++++++++++++++++ src/map.h | 59 ++++++++++++++++++ tests/unit/map_test.c | 77 +++++++++++++++++++++++ 3 files changed, 276 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..6665e18 --- /dev/null +++ b/src/map.c @@ -0,0 +1,140 @@ +/* + * 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 . + */ +#include "map.h" +#include "arena.h" + +#include +#include +#include +#include +#include +#include +#include + +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); + +static uint32_t +map_get_index(map_t *map, uint32_t hash); + +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 + map_get_index(map, hash); + + 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; + break; + } + 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; + } while (entry != NULL); + + return true; +} + +void * +map_get(map_t *map, char *key) +{ + uint32_t hash = u32_fnv1a_hash(key); + 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; + } + entry = entry->next; + } + 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) +{ + 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 . + */ +#ifndef MAP_H +#define MAP_H + +#include "arena.h" + +#include +#include +#include + +#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..449bca6 --- /dev/null +++ b/tests/unit/map_test.c @@ -0,0 +1,77 @@ +/* + * 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 . + */ +#define MUNIT_ENABLE_ASSERT_ALIASES + +#include "arena.h" +#include "map.h" +#include "munit.h" +#include + +#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); + + map_put(map, "n1", (void *)&n2); + + assert_int(*((int *)map_get(map, "n1")), ==, 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