From 89fe36162221ab36c5f2dfec1446dc406c68272b Mon Sep 17 00:00:00 2001 From: Johnny Richard Date: Wed, 17 May 2023 18:06:12 +0200 Subject: util: Create hashmap data structure with FNV-1a 32-bit hashing This path implements a hashmap data structure using the FNV-1a hashing function of 32 bits. However, there are a few limitations to consider: a) The table does not automatically expand when it becomes too large. b) The capacity of the hashmap must be a power of 2 to optimize performance, as we utilize bitwise shifting instead of modulus calculations. c) Currently, there are no functions available to destroy hashmap entries. Collisions are handled using a linked list, which is not the most optimal solution in terms of performance. However, it serves our current needs adequately. Signed-off-by: Johnny Richard --- test/hashmap_test.c | 65 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 65 insertions(+) create mode 100644 test/hashmap_test.c (limited to 'test/hashmap_test.c') diff --git a/test/hashmap_test.c b/test/hashmap_test.c new file mode 100644 index 0000000..df0101c --- /dev/null +++ b/test/hashmap_test.c @@ -0,0 +1,65 @@ +/* + * Copyright (C) 2023 Johnny Richard + * + * 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 "hashmap.h" +#include "munit.h" + +static MunitResult +test_create_new(const MunitParameter params[], void *user_data_or_fixture) +{ + hashmap_t *map = hashmap_new(); + + assert_not_null(map); + + hashmap_destroy(map); + + return MUNIT_OK; +} + +static MunitResult +test_hashmap_put_and_get(const MunitParameter params[], void *user_data_or_fixture) +{ + hashmap_t *map = hashmap_new(); + + int n1 = 1; + int n2 = 2; + + hashmap_put(map, "n1", (void *)&n1); + hashmap_put(map, "n2", (void *)&n2); + + assert_int(*((int *)hashmap_get(map, "n1")), ==, n1); + assert_int(*((int *)hashmap_get(map, "n2")), ==, n2); + + hashmap_destroy(map); + + return MUNIT_OK; +} + +static MunitTest tests[] = { + { "/test_create_new", test_create_new, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL }, + { "/test_hashmap_put_and_get", test_hashmap_put_and_get, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL }, + { NULL, NULL, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL } +}; + +static const MunitSuite suite = { "/hashmap", tests, NULL, 1, MUNIT_SUITE_OPTION_NONE }; + +int +main(int argc, char *argv[]) +{ + return munit_suite_main(&suite, NULL, argc, argv); + return EXIT_SUCCESS; +} -- cgit v1.2.3