diff options
| -rw-r--r-- | .gitignore | 3 | ||||
| -rwxr-xr-x | Makefile | 23 | ||||
| -rwxr-xr-x | include/hashfuncs.h | 33 | ||||
| -rwxr-xr-x | include/strmap.h | 38 | ||||
| -rwxr-xr-x | src/strmap.c | 157 | ||||
| -rwxr-xr-x | tests/strmap_tests.c | 228 |
6 files changed, 482 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..f9ed49a --- /dev/null +++ b/.gitignore @@ -0,0 +1,3 @@ +bin/* +build/* +lib/* diff --git a/Makefile b/Makefile new file mode 100755 index 0000000..97269af --- /dev/null +++ b/Makefile @@ -0,0 +1,23 @@ +CFLAGS = -Wall -Wextra -Werror -std=c11 -Iinclude -Wno-unused-function -I/usr/local/include -ggdb -O0 + +.PHONY build: +build: + mkdir -p build + mkdir -p bin + mkdir -p lib + +build/strmap.o: src/strmap.c build + clang $(CFLAGS) -c src/strmap.c -o build/strmap.o + +lib/strmap.a: build/strmap.o + ar rcs lib/strmap.a build/strmap.o + ranlib lib/strmap.a + +.PHONY tests: +tests: lib/strmap.a + clang $(CFLAGS) -L/usr/local/lib -lcheck -pthread lib/strmap.a tests/strmap_tests.c -o bin/strmap_tests + + +.PHONY clean: +clean: + rm -r build bin lib diff --git a/include/hashfuncs.h b/include/hashfuncs.h new file mode 100755 index 0000000..da5d788 --- /dev/null +++ b/include/hashfuncs.h @@ -0,0 +1,33 @@ +#include <stdlib.h> + +/* + * + * 32 bit FNV-1a algorithm + * https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function + * + */ +static size_t hash_key(const char *key, const size_t max_hash_value) { + uint32_t hash = 2166136261U; /* FNV-1a 32-bit offset basis */ + /* + * We'll explicitly use unsigned chars here, since we're doing arithmetic. The + * C standard doesn't state whether an implementation must use signed or + * unsigned values for characters, so this conversion ensures we get + * correct behavior. If signed characters are used, we'll get overflows + * and other odd issues in the hash calculation. + */ + const unsigned char *p = (unsigned char *) key; + + while (*p) { + hash ^= *p++; + hash *= 16777619U; /* FNV-1a prime */ + } + + return hash % max_hash_value; +} + +static size_t test_hash(const char *key, const size_t max_hash_value) { + (void) max_hash_value; + + return key[0] % 3; +} + diff --git a/include/strmap.h b/include/strmap.h new file mode 100755 index 0000000..634da60 --- /dev/null +++ b/include/strmap.h @@ -0,0 +1,38 @@ +/* + * strmap.h + * + * A close-addressing based string -> string hash map + * for CISC 301: Operating Systems + */ + +#ifndef H_STRMAP +#define H_STRMAP + +#include <stdlib.h> +#include <string.h> + +typedef struct strmap strmap; +typedef size_t (*hash_func) (const char *, size_t); + +typedef enum { + STRMAP_OK, + STRMAP_ERR, + STRMAP_NOTFOUND +} strmap_status; + +/* + * Inserts a new string into a strmap, returning + */ +strmap_status strmap_put(strmap*, const char*, const char*); + +strmap_status strmap_get(const strmap*, const char*, const char**); + +strmap_status strmap_delete(strmap*, const char*); + +size_t strmap_size(const strmap*); + +strmap *strmap_create(hash_func); +void strmap_destroy(strmap *); + + +#endif diff --git a/src/strmap.c b/src/strmap.c new file mode 100755 index 0000000..c3d0261 --- /dev/null +++ b/src/strmap.c @@ -0,0 +1,157 @@ +/* + * strmap.c + * + * A closed-addressing based string -> string hash map + * for CISC 301: Operating Systems + */ + +#include "strmap.h" + +struct node { + char *key; + char *value; + struct node *next; +}; + +struct bucket { + struct node *node; +}; + +struct strmap { + struct bucket *buckets; + size_t bucket_cnt; + size_t node_cnt; + hash_func hash; +}; + +static const size_t BCKT_CNT = 101; + +static void _destroy_node(struct node *nd) { + free(nd->key); + free(nd->value); + free(nd); +} + +strmap *strmap_create(hash_func hash) { + strmap *map = calloc(1, sizeof(*map)); + if (!map) + return NULL; + + map->buckets = calloc(BCKT_CNT, sizeof(struct bucket)); + + if (!map->buckets) { + free(map); + return NULL; + } + + map->bucket_cnt = BCKT_CNT; + map->node_cnt = 0; + map->hash = hash; + + return map; +} + +void strmap_destroy(strmap *map) { + for (size_t i = 0; i < map->bucket_cnt; i++) { + struct node *nd = map->buckets[i].node; + while (nd) { + struct node *nd2 = nd->next; + _destroy_node(nd); + nd = nd2; + } + } + + free(map->buckets); + free(map); +} + +strmap_status strmap_put(strmap *map, const char *key, const char *value) { + if (!key || !value) + return STRMAP_ERR; + struct bucket *bckt = map->buckets + map->hash(key, map->bucket_cnt); + + /* + * check if the key already exists in the bucket, in which case we + * do an update, rather than allocating a new node + */ + for (struct node *nd = bckt->node; nd; nd = nd->next) { + if (!strcmp(nd->key, key)) { + char *old_value = nd->value; + nd->value = strdup(value); + /* if the allocation fails, put the old value back */ + if (!nd->value) { + nd->value = old_value; + return STRMAP_ERR; + } + + free(old_value); + return STRMAP_OK; + } + } + + struct node *nd = malloc(sizeof(struct node)); + if (!nd) { + /* node allocation failed */ + goto error_nodealloc; + } + + nd->key = strdup(key); + nd->value = strdup(value); + + if (nd->key == NULL || nd->value == NULL) { + /* string allocation failed */ + goto error_stringalloc; + } + + nd->next = bckt->node; + bckt->node = nd; + map->node_cnt++; + return STRMAP_OK; + +error_stringalloc: + free(nd->key); + free(nd->value); +error_nodealloc: + free(nd); + return STRMAP_ERR; +} + +strmap_status strmap_get(const strmap *map, const char *key, + const char **value) { + if (!key) + return STRMAP_NOTFOUND; + + size_t idx = map->hash(key, map->bucket_cnt); + + struct node *nd; + for (nd = map->buckets[idx].node; nd; nd = nd->next) { + if (!strcmp(nd->key, key)) { + *value = nd->value; + return STRMAP_OK; + } + } + + return STRMAP_NOTFOUND; +} + +strmap_status strmap_delete(strmap *map, const char *key) { + if (!key) + return STRMAP_NOTFOUND; + struct node **nd_ptr = &(map->buckets[map->hash(key, map->bucket_cnt)].node); + + while (*nd_ptr) { + struct node *nd = *nd_ptr; + if (!strcmp(nd->key, key)) { + *nd_ptr = nd->next; + _destroy_node(nd); + map->node_cnt--; + return STRMAP_OK; + } + + nd_ptr = &nd->next; + } + + return STRMAP_NOTFOUND; +} + +size_t strmap_size(const strmap *map) { return map->node_cnt; } diff --git a/tests/strmap_tests.c b/tests/strmap_tests.c new file mode 100755 index 0000000..7f3c34f --- /dev/null +++ b/tests/strmap_tests.c @@ -0,0 +1,228 @@ +/* + * strmap_test.c + * + * Unit tests for strmap implementation + */ + +#include "hashfuncs.h" +#include "strmap.h" + +#include <check.h> +#include <stdlib.h> +#include <string.h> + +START_TEST(test_create_destroy) { + strmap *map = strmap_create(hash_key); + ck_assert_ptr_nonnull(map); + ck_assert_uint_eq(strmap_size(map), 0); + strmap_destroy(map); +} +END_TEST + +START_TEST(test_put_get_basic) { + strmap *map = strmap_create(hash_key); + const char *value; + + ck_assert_int_eq(strmap_put(map, "key1", "value1"), STRMAP_OK); + ck_assert_uint_eq(strmap_size(map), 1); + + ck_assert_int_eq(strmap_get(map, "key1", &value), STRMAP_OK); + ck_assert_str_eq(value, "value1"); + + strmap_destroy(map); +} +END_TEST + +START_TEST(test_put_update) { + strmap *map = strmap_create(hash_key); + const char *value; + + ck_assert_int_eq(strmap_put(map, "key1", "value1"), STRMAP_OK); + ck_assert_int_eq(strmap_put(map, "key1", "value2"), STRMAP_OK); + ck_assert_uint_eq(strmap_size(map), 1); + + ck_assert_int_eq(strmap_get(map, "key1", &value), STRMAP_OK); + ck_assert_str_eq(value, "value2"); + + strmap_destroy(map); +} +END_TEST + +START_TEST(test_get_nonexistent) { + strmap *map = strmap_create(hash_key); + const char *value; + + ck_assert_int_eq(strmap_get(map, "nonexistent", &value), STRMAP_NOTFOUND); + + strmap_destroy(map); +} +END_TEST + +START_TEST(test_delete_basic) { + strmap *map = strmap_create(hash_key); + const char *value; + + ck_assert_int_eq(strmap_put(map, "key1", "value1"), STRMAP_OK); + ck_assert_int_eq(strmap_delete(map, "key1"), STRMAP_OK); + ck_assert_uint_eq(strmap_size(map), 0); + + ck_assert_int_eq(strmap_get(map, "key1", &value), STRMAP_NOTFOUND); + + strmap_destroy(map); +} +END_TEST + +START_TEST(test_delete_nonexistent) { + strmap *map = strmap_create(hash_key); + + ck_assert_int_eq(strmap_delete(map, "nonexistent"), STRMAP_NOTFOUND); + + strmap_destroy(map); +} +END_TEST + +START_TEST(test_delete_multiple) { + strmap *map = strmap_create(hash_key); + const char *value; + + // Add multiple items + ck_assert_int_eq(strmap_put(map, "key1", "value1"), STRMAP_OK); + ck_assert_int_eq(strmap_put(map, "key2", "value2"), STRMAP_OK); + ck_assert_int_eq(strmap_put(map, "key3", "value3"), STRMAP_OK); + ck_assert_uint_eq(strmap_size(map), 3); + + // Delete middle item + ck_assert_int_eq(strmap_delete(map, "key2"), STRMAP_OK); + ck_assert_uint_eq(strmap_size(map), 2); + ck_assert_int_eq(strmap_get(map, "key2", &value), STRMAP_NOTFOUND); + + // Verify remaining items + ck_assert_int_eq(strmap_get(map, "key1", &value), STRMAP_OK); + ck_assert_str_eq(value, "value1"); + ck_assert_int_eq(strmap_get(map, "key3", &value), STRMAP_OK); + ck_assert_str_eq(value, "value3"); + + strmap_destroy(map); +} +END_TEST + +START_TEST(test_delete_head) { + strmap *map = strmap_create(hash_key); + const char *value; + + // Add items that will likely hash to same bucket + ck_assert_int_eq(strmap_put(map, "a", "first"), STRMAP_OK); + ck_assert_int_eq(strmap_put(map, "b", "second"), STRMAP_OK); + ck_assert_int_eq(strmap_put(map, "c", "third"), STRMAP_OK); + + // Delete head item + ck_assert_int_eq(strmap_delete(map, "c"), STRMAP_OK); + ck_assert_uint_eq(strmap_size(map), 2); + ck_assert_int_eq(strmap_get(map, "c", &value), STRMAP_NOTFOUND); + + // Verify remaining items + ck_assert_int_eq(strmap_get(map, "a", &value), STRMAP_OK); + ck_assert_str_eq(value, "first"); + ck_assert_int_eq(strmap_get(map, "b", &value), STRMAP_OK); + ck_assert_str_eq(value, "second"); + + strmap_destroy(map); +} +END_TEST + +START_TEST(test_collision_handling) { + strmap *map = strmap_create(test_hash); + const char *value; + + /* all keys with the same initial letter should map to the same bucket */ + ck_assert_int_eq(strmap_put(map, "key1", "value1"), STRMAP_OK); + ck_assert_int_eq(strmap_put(map, "key2", "value2"), STRMAP_OK); + ck_assert_int_eq(strmap_put(map, "key3", "value3"), STRMAP_OK); + ck_assert_uint_eq(strmap_size(map), 3); + + // Retrieve all values + ck_assert_int_eq(strmap_get(map, "key1", &value), STRMAP_OK); + ck_assert_str_eq(value, "value1"); + ck_assert_int_eq(strmap_get(map, "key2", &value), STRMAP_OK); + ck_assert_str_eq(value, "value2"); + ck_assert_int_eq(strmap_get(map, "key3", &value), STRMAP_OK); + ck_assert_str_eq(value, "value3"); + + strmap_destroy(map); +} +END_TEST + +START_TEST(test_empty_key_value) { + strmap *map = strmap_create(hash_key); + const char *value; + + // Test empty string key + ck_assert_int_eq(strmap_put(map, "", "empty_key_value"), STRMAP_OK); + ck_assert_int_eq(strmap_get(map, "", &value), STRMAP_OK); + ck_assert_str_eq(value, "empty_key_value"); + + // Test empty string value + ck_assert_int_eq(strmap_put(map, "empty_value_key", ""), STRMAP_OK); + ck_assert_int_eq(strmap_get(map, "empty_value_key", &value), STRMAP_OK); + ck_assert_str_eq(value, ""); + + strmap_destroy(map); +} +END_TEST + +START_TEST(test_put_null_key) { + strmap *map = strmap_create(hash_key); + + // This should ideally be handled gracefully + // Behavior depends on your strdup implementation with NULL + // For now, we'll assume it fails gracefully + ck_assert_int_eq(strmap_put(map, NULL, "value"), STRMAP_ERR); + + strmap_destroy(map); +} +END_TEST + +Suite *strmap_suite(void) { + Suite *s; + TCase *tc_core; + TCase *tc_edge; + + s = suite_create("Strmap"); + + /* Core test case */ + tc_core = tcase_create("Core"); + tcase_add_test(tc_core, test_create_destroy); + tcase_add_test(tc_core, test_put_get_basic); + tcase_add_test(tc_core, test_put_update); + tcase_add_test(tc_core, test_get_nonexistent); + tcase_add_test(tc_core, test_delete_basic); + tcase_add_test(tc_core, test_delete_nonexistent); + tcase_add_test(tc_core, test_delete_multiple); + tcase_add_test(tc_core, test_delete_head); + tcase_add_test(tc_core, test_collision_handling); + + /* Edge cases */ + tc_edge = tcase_create("Edge"); + tcase_add_test(tc_edge, test_empty_key_value); + tcase_add_test(tc_edge, test_put_null_key); + + suite_add_tcase(s, tc_core); + suite_add_tcase(s, tc_edge); + + return s; +} + +int main(void) { + int number_failed; + Suite *s; + SRunner *sr; + + s = strmap_suite(); + sr = srunner_create(s); + + srunner_run_all(sr, CK_NORMAL); + number_failed = srunner_ntests_failed(sr); + srunner_free(sr); + + return (number_failed == 0) ? EXIT_SUCCESS : EXIT_FAILURE; +} |