From 31e98ced014b9326ddfc990b003864df69cd4dcc Mon Sep 17 00:00:00 2001 From: Danny van Kooten Date: Mon, 16 Mar 2020 14:06:02 +0100 Subject: return old values when inserting or removing from hashmap --- .vscode/settings.json | 13 +++++++++++++ src/hashmap.c | 39 ++++++++++++++++++++++++++++++++------- src/hashmap.h | 10 +++++----- tests/test.h | 2 ++ tests/test_hashmap.c | 38 ++++++++++++++++++++++++++++++++------ 5 files changed, 84 insertions(+), 18 deletions(-) create mode 100644 .vscode/settings.json diff --git a/.vscode/settings.json b/.vscode/settings.json new file mode 100644 index 0000000..420aa6e --- /dev/null +++ b/.vscode/settings.json @@ -0,0 +1,13 @@ +{ + "files.associations": { + "cstdio": "cpp", + "mpc.h": "c", + "stdio.h": "c", + "typeinfo": "c", + "template.h": "c", + "test.h": "c", + "stdlib.h": "c", + "list": "c", + "hashmap.h": "c" + } +} \ No newline at end of file diff --git a/src/hashmap.c b/src/hashmap.c index 6797475..f99ba4c 100644 --- a/src/hashmap.c +++ b/src/hashmap.c @@ -22,16 +22,18 @@ struct hashmap *hashmap_new() { return hm; } -/* insert key-value into hashmap */ -void hashmap_insert(struct hashmap *hm, char *key, void *value) { +/* Inserts a key-value pair into the map. Returns NULL if map did not have key, old value if it did. */ +void *hashmap_insert(struct hashmap *hm, char *key, void *value) { int pos = HASH(key); struct node *head = hm->buckets[pos]; struct node *node = head; + void *old_value; while (node) { if (strcmp(node->key, key) == 0) { + old_value = node->value; node->value = value; - return; + return old_value; } node = node->next; } @@ -41,9 +43,10 @@ void hashmap_insert(struct hashmap *hm, char *key, void *value) { node->value = value; node->next = head; hm->buckets[pos] = node; + return NULL; } -/* retrieve value by key */ +/* Returns a pointer to the value corresponding to the key. */ void *hashmap_get(struct hashmap *hm, char *key) { int pos = HASH(key); struct node *node = hm->buckets[pos]; @@ -58,7 +61,7 @@ void *hashmap_get(struct hashmap *hm, char *key) { return NULL; } -/* retrieve value by key, handles dot notation for nested hashmaps */ +/* Retrieve pointer to value by key, handles dot notation for nested hashmaps */ void *hashmap_resolve(struct hashmap *hm, char *key) { char tmp_key[64]; int i = 0; @@ -83,8 +86,30 @@ void *hashmap_resolve(struct hashmap *hm, char *key) { return hm; } -void hashmap_remove(char *key) { - // TODO: Implement this +/* Removes a key from the map, returning the value at the key if the key was previously in the map. */ +void *hashmap_remove(struct hashmap *hm, char *key) { + int pos = HASH(key); + struct node *node = hm->buckets[pos]; + struct node *prev = NULL; + void *old_value; + + while (node) { + if (strcmp(node->key, key) == 0) { + if (prev) { + prev->next = node->next; + } else { + hm->buckets[pos] = node->next; + } + old_value = node->value; + free(node); + return old_value; + } + + node = node->next; + prev = node; + } + + return NULL; } /* free hashmap related memory */ diff --git a/src/hashmap.h b/src/hashmap.h index 369f594..be2b80e 100644 --- a/src/hashmap.h +++ b/src/hashmap.h @@ -4,9 +4,9 @@ struct hashmap { struct node *buckets[HASHMAP_CAP]; }; -void hashmap_insert(struct hashmap *hm, char *key, void *value); -void *hashmap_get(struct hashmap *hm, char *key); -void hashmap_remove(char *key); struct hashmap *hashmap_new(); -void hashmap_free(struct hashmap *hm); -void *hashmap_resolve(struct hashmap *hm, char *key); \ No newline at end of file +void *hashmap_insert(struct hashmap *hm, char *key, void *value); +void *hashmap_get(struct hashmap *hm, char *key); +void *hashmap_resolve(struct hashmap *hm, char *key); +void *hashmap_remove(struct hashmap *hm, char *key); +void hashmap_free(struct hashmap *hm); \ No newline at end of file diff --git a/tests/test.h b/tests/test.h index f860ee2..7a82d08 100644 --- a/tests/test.h +++ b/tests/test.h @@ -6,6 +6,8 @@ #define START_TESTS int main() { #define END_TESTS } #define TEST(name) strcpy(current_test, #name); +#define assert_null(actual) _assert(actual == NULL, __FILE__, __LINE__, "invalid value: expected NULL, got %s", actual) + #define assert_str(actual, expected) _assert(actual != NULL && strcmp(actual, expected) == 0, __FILE__, __LINE__, "invalid string: expected %s, got %s", expected, actual) #define assert(assertion, format, ...) _assert(assertion, __FILE__, __LINE__, format, ##__VA_ARGS__) #define ARRAY_SIZE(arr) sizeof arr / sizeof arr[0] diff --git a/tests/test_hashmap.c b/tests/test_hashmap.c index 14ec552..82f340c 100644 --- a/tests/test_hashmap.c +++ b/tests/test_hashmap.c @@ -5,23 +5,49 @@ START_TESTS TEST(hashmap) { struct hashmap *hm = hashmap_new(); - assert(hashmap_get(hm, "foo") == NULL, "expected NULL"); - hashmap_insert(hm, "foo", "bar"); char *value = hashmap_get(hm, "foo"); + assert_null(value); + value = hashmap_insert(hm, "foo", "bar"); + assert_null(value); + value = hashmap_get(hm, "foo"); assert_str(value, "bar"); hashmap_free(hm); } TEST(dot_notation) { + void *val; struct hashmap *user = hashmap_new(); - hashmap_insert(user, "name", "Danny"); + val = hashmap_insert(user, "name", "Danny"); + assert_null(val); struct hashmap *hm = hashmap_new(); - hashmap_insert(hm, "user", user); + val = hashmap_insert(hm, "user", user); + assert_null(val); assert(hashmap_resolve(hm, "user") == user, "expected user hashmap, got something else"); - char *value = (char *) hashmap_resolve(hm, "user.name"); - assert_str(value, "Danny"); + val = hashmap_resolve(hm, "user.name"); + assert_str(val, "Danny"); hashmap_free(user); hashmap_free(hm); } +TEST(hashmap_remove) { + struct hashmap *hm = hashmap_new(); + hashmap_insert(hm, "foo", "bar"); + char *value = hashmap_get(hm, "foo"); + assert_str(value, "bar"); + + // remove once + value = hashmap_remove(hm, "foo"); + assert_str(value, "bar"); + value = hashmap_get(hm, "foo"); + assert_null(value); + + // remove again (should no-op) + value = hashmap_remove(hm, "foo"); + assert_null(value); + value = hashmap_get(hm, "foo"); + assert_null(value); + + hashmap_free(hm); +} + END_TESTS \ No newline at end of file -- cgit v1.2.3