summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--test/Makefile5
-rw-r--r--test/hashmap.c467
-rw-r--r--utils/hashmap.c215
-rw-r--r--utils/hashmap.h137
4 files changed, 824 insertions, 0 deletions
diff --git a/test/Makefile b/test/Makefile
index 963b2e028..34434c30d 100644
--- a/test/Makefile
+++ b/test/Makefile
@@ -7,6 +7,7 @@ TESTS := \
nsoption \
bloom \
hashtable \
+ hashmap \
urlescape \
utils \
messages \
@@ -52,6 +53,10 @@ bloom_SRCS := utils/bloom.c test/bloom.c
# hash table test sources
hashtable_SRCS := utils/hashtable.c test/log.c test/hashtable.c
+# hashmap test sources
+hashmap_SRCS := $(NSURL_SOURCES) utils/hashmap.c utils/corestrings.c test/log.c test/hashmap.c
+hashmap_LD := -lmalloc_fig
+
# url escape test sources
urlescape_SRCS := utils/url.c test/log.c test/urlescape.c
diff --git a/test/hashmap.c b/test/hashmap.c
new file mode 100644
index 000000000..87db6c174
--- /dev/null
+++ b/test/hashmap.c
@@ -0,0 +1,467 @@
+/*
+ * Copyright 2020 Daniel Silverstone <dsilvers@netsurf-browser.org>
+ * Copyright 2016 Vincent Sanders <vince@netsurf-browser.org>
+ *
+ * This file is part of NetSurf, http://www.netsurf-browser.org/
+ *
+ * NetSurf 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; version 2 of the License.
+ *
+ * NetSurf 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 <http://www.gnu.org/licenses/>.
+ */
+
+/**
+ * \file
+ * Tests for hashmap.
+ *
+ * In part, borrows from the corestrings tests
+ */
+
+#include "utils/config.h"
+
+#include <assert.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <check.h>
+#include <limits.h>
+
+#include <libwapcaplet/libwapcaplet.h>
+
+#include "utils/nsurl.h"
+#include "utils/corestrings.h"
+#include "utils/hashmap.h"
+
+#include "test/malloc_fig.h"
+
+/* Low level fixtures */
+
+static void
+corestring_create(void)
+{
+ ck_assert(corestrings_init() == NSERROR_OK);
+}
+
+/**
+ * iterator for any remaining strings in teardown fixture
+ */
+static void
+netsurf_lwc_iterator(lwc_string *str, void *pw)
+{
+ fprintf(stderr,
+ "[%3u] %.*s",
+ str->refcnt,
+ (int)lwc_string_length(str),
+ lwc_string_data(str));
+}
+
+static void
+corestring_teardown(void)
+{
+ corestrings_fini();
+
+ lwc_iterate_strings(netsurf_lwc_iterator, NULL);
+}
+
+/* Infra */
+
+static ssize_t keys;
+static ssize_t values;
+
+typedef struct {
+ nsurl *key;
+} hashmap_test_value_t;
+
+static void *
+key_clone(void *key)
+{
+ /* Pretend cloning costs memory so that it can fail for
+ * testing error return pathways
+ */
+ void *temp = malloc(1);
+ if (temp == NULL) return NULL;
+ free(temp);
+ /* In reality we just ref the nsurl */
+ keys++;
+ return nsurl_ref((nsurl *)key);
+}
+
+static void
+key_destroy(void *key)
+{
+ keys--;
+ nsurl_unref((nsurl *)key);
+}
+
+static uint32_t
+key_hash(void *key)
+{
+ /* Deliberately bad hash.
+ * returns 0, 1, 2, or 3 to force bucket chaining
+ */
+ return nsurl_hash((nsurl *)key) & 3;
+}
+
+static bool
+key_eq(void *key1, void *key2)
+{
+ return nsurl_compare((nsurl *)key1, (nsurl*)key2, NSURL_COMPLETE);
+}
+
+static void *
+value_alloc(void *key)
+{
+ hashmap_test_value_t *ret = malloc(sizeof(hashmap_test_value_t));
+
+ if (ret == NULL)
+ return NULL;
+
+ ret->key = (nsurl *)key;
+
+ values++;
+
+ return ret;
+}
+
+static void
+value_destroy(void *value)
+{
+ hashmap_test_value_t *val = value;
+
+ /* Do nothing for now */
+
+ free(val);
+ values--;
+}
+
+static hashmap_parameters_t test_params = {
+ .key_clone = key_clone,
+ .key_hash = key_hash,
+ .key_eq = key_eq,
+ .key_destroy = key_destroy,
+ .value_alloc = value_alloc,
+ .value_destroy = value_destroy,
+};
+
+/* Fixtures for basic tests */
+
+static hashmap_t *test_hashmap = NULL;
+
+static void
+basic_fixture_create(void)
+{
+ corestring_create();
+
+ test_hashmap = hashmap_create(&test_params);
+
+ ck_assert(test_hashmap != NULL);
+ ck_assert_int_eq(keys, 0);
+ ck_assert_int_eq(values, 0);
+}
+
+static void
+basic_fixture_teardown(void)
+{
+ hashmap_destroy(test_hashmap);
+ test_hashmap = NULL;
+
+ ck_assert_int_eq(keys, 0);
+ ck_assert_int_eq(values, 0);
+
+ corestring_teardown();
+}
+
+/* basic api tests */
+
+START_TEST(empty_hashmap_create_destroy)
+{
+ /* Do nothing in here, all the checks are in the fixture */
+}
+END_TEST
+
+START_TEST(check_not_present)
+{
+ /* We're checking for a key which should not be present */
+ ck_assert(hashmap_lookup(test_hashmap, corestring_nsurl_about_blank) == NULL);
+}
+END_TEST
+
+START_TEST(insert_works)
+{
+ hashmap_test_value_t *value = hashmap_insert(test_hashmap, corestring_nsurl_about_blank);
+ ck_assert(value != NULL);
+ ck_assert(value->key == corestring_nsurl_about_blank);
+}
+END_TEST
+
+START_TEST(remove_not_present)
+{
+ ck_assert(hashmap_remove(test_hashmap, corestring_nsurl_about_blank) == false);
+}
+END_TEST
+
+START_TEST(insert_then_remove)
+{
+ hashmap_test_value_t *value = hashmap_insert(test_hashmap, corestring_nsurl_about_blank);
+ ck_assert(value != NULL);
+ ck_assert(value->key == corestring_nsurl_about_blank);
+ ck_assert_int_eq(keys, 1);
+ ck_assert_int_eq(values, 1);
+ ck_assert(hashmap_remove(test_hashmap, corestring_nsurl_about_blank) == true);
+ ck_assert_int_eq(keys, 0);
+ ck_assert_int_eq(values, 0);
+}
+END_TEST
+
+START_TEST(insert_then_lookup)
+{
+ hashmap_test_value_t *value = hashmap_insert(test_hashmap, corestring_nsurl_about_blank);
+ ck_assert(value != NULL);
+ ck_assert(value->key == corestring_nsurl_about_blank);
+ ck_assert(hashmap_lookup(test_hashmap, corestring_nsurl_about_blank) == value);
+}
+END_TEST
+
+static TCase *basic_api_case_create(void)
+{
+ TCase *tc;
+ tc = tcase_create("Basic API");
+
+ tcase_add_unchecked_fixture(tc,
+ basic_fixture_create,
+ basic_fixture_teardown);
+
+ tcase_add_test(tc, empty_hashmap_create_destroy);
+ tcase_add_test(tc, check_not_present);
+ tcase_add_test(tc, insert_works);
+ tcase_add_test(tc, remove_not_present);
+ tcase_add_test(tc, insert_then_remove);
+ tcase_add_test(tc, insert_then_lookup);
+
+ return tc;
+}
+
+/* Chain verification test suite */
+
+typedef struct {
+ const char *url;
+ nsurl *nsurl;
+} case_pair;
+
+/* The hobbled hash has only 4 values
+ * By having at least 12 test cases, we can be confident that
+ * at worst they'll all be on one chain, but at best there'll
+ * be four chains of 3 entries which means we should be able
+ * to validate prevptr and next in all cases.
+ */
+static case_pair chain_pairs[] = {
+ { "https://www.google.com/", NULL },
+ { "https://www.google.co.uk/", NULL },
+ { "https://www.netsurf-browser.org/", NULL },
+ { "http://www.google.com/", NULL },
+ { "http://www.google.co.uk/", NULL },
+ { "http://www.netsurf-browser.org/", NULL },
+ { "file:///tmp/test.html", NULL },
+ { "file:///tmp/inner.html", NULL },
+ { "about:blank", NULL },
+ { "about:welcome", NULL },
+ { "about:testament", NULL },
+ { "resources:default.css", NULL },
+ { NULL, NULL }
+};
+
+static void
+chain_fixture_create(void)
+{
+ case_pair *chain_case = chain_pairs;
+ basic_fixture_create();
+
+ while (chain_case->url != NULL) {
+ ck_assert(nsurl_create(chain_case->url, &chain_case->nsurl) == NSERROR_OK);
+ chain_case++;
+ }
+
+}
+
+static void
+chain_fixture_teardown(void)
+{
+ case_pair *chain_case = chain_pairs;
+
+ while (chain_case->url != NULL) {
+ nsurl_unref(chain_case->nsurl);
+ chain_case->nsurl = NULL;
+ chain_case++;
+ }
+
+ basic_fixture_teardown();
+}
+
+START_TEST(chain_add_remove_all)
+{
+ case_pair *chain_case;
+
+ for (chain_case = chain_pairs;
+ chain_case->url != NULL;
+ chain_case++) {
+ ck_assert(hashmap_lookup(test_hashmap, chain_case->nsurl) == NULL);
+ ck_assert(hashmap_insert(test_hashmap, chain_case->nsurl) != NULL);
+ ck_assert(hashmap_lookup(test_hashmap, chain_case->nsurl) != NULL);
+ ck_assert(hashmap_remove(test_hashmap, chain_case->nsurl) == true);
+ }
+
+ ck_assert_int_eq(keys, 0);
+ ck_assert_int_eq(values, 0);
+}
+END_TEST
+
+START_TEST(chain_add_all_remove_all)
+{
+ case_pair *chain_case;
+
+ for (chain_case = chain_pairs;
+ chain_case->url != NULL;
+ chain_case++) {
+ ck_assert(hashmap_lookup(test_hashmap, chain_case->nsurl) == NULL);
+ ck_assert(hashmap_insert(test_hashmap, chain_case->nsurl) != NULL);
+ }
+
+ for (chain_case = chain_pairs;
+ chain_case->url != NULL;
+ chain_case++) {
+ ck_assert(hashmap_remove(test_hashmap, chain_case->nsurl) == true);
+ }
+
+ ck_assert_int_eq(keys, 0);
+ ck_assert_int_eq(values, 0);
+}
+END_TEST
+
+START_TEST(chain_add_all_twice_remove_all)
+{
+ case_pair *chain_case;
+
+ for (chain_case = chain_pairs;
+ chain_case->url != NULL;
+ chain_case++) {
+ ck_assert(hashmap_lookup(test_hashmap, chain_case->nsurl) == NULL);
+ ck_assert(hashmap_insert(test_hashmap, chain_case->nsurl) != NULL);
+ }
+
+ for (chain_case = chain_pairs;
+ chain_case->url != NULL;
+ chain_case++) {
+ ck_assert(hashmap_lookup(test_hashmap, chain_case->nsurl) != NULL);
+ ck_assert(hashmap_insert(test_hashmap, chain_case->nsurl) != NULL);
+ }
+
+ for (chain_case = chain_pairs;
+ chain_case->url != NULL;
+ chain_case++) {
+ ck_assert(hashmap_remove(test_hashmap, chain_case->nsurl) == true);
+ }
+
+ ck_assert_int_eq(keys, 0);
+ ck_assert_int_eq(values, 0);
+}
+END_TEST
+
+#define CHAIN_TEST_MALLOC_COUNT_MAX 60
+
+START_TEST(chain_add_all_remove_all_alloc)
+{
+ bool failed = false;
+ case_pair *chain_case;
+
+ malloc_limit(_i);
+
+ for (chain_case = chain_pairs;
+ chain_case->url != NULL;
+ chain_case++) {
+ if (hashmap_insert(test_hashmap, chain_case->nsurl) == NULL) {
+ failed = true;
+ }
+ }
+
+ for (chain_case = chain_pairs;
+ chain_case->url != NULL;
+ chain_case++) {
+ if (hashmap_insert(test_hashmap, chain_case->nsurl) == NULL) {
+ failed = true;
+ }
+ }
+
+ for (chain_case = chain_pairs;
+ chain_case->url != NULL;
+ chain_case++) {
+ hashmap_remove(test_hashmap, chain_case->nsurl);
+ }
+
+ malloc_limit(UINT_MAX);
+
+ ck_assert_int_eq(keys, 0);
+ ck_assert_int_eq(values, 0);
+
+ if (_i < CHAIN_TEST_MALLOC_COUNT_MAX) {
+ ck_assert(failed);
+ } else {
+ ck_assert(!failed);
+ }
+
+}
+END_TEST
+
+static TCase *chain_case_create(void)
+{
+ TCase *tc;
+ tc = tcase_create("Bucket Chain tests");
+
+ tcase_add_unchecked_fixture(tc,
+ chain_fixture_create,
+ chain_fixture_teardown);
+
+ tcase_add_test(tc, chain_add_remove_all);
+ tcase_add_test(tc, chain_add_all_remove_all);
+ tcase_add_test(tc, chain_add_all_twice_remove_all);
+
+ tcase_add_loop_test(tc, chain_add_all_remove_all_alloc, 0, CHAIN_TEST_MALLOC_COUNT_MAX + 1);
+
+ return tc;
+}
+
+/*
+ * hashmap test suite creation
+ */
+static Suite *hashmap_suite_create(void)
+{
+ Suite *s;
+ s = suite_create("Hashmap");
+
+ suite_add_tcase(s, basic_api_case_create());
+ suite_add_tcase(s, chain_case_create());
+
+ return s;
+}
+
+int main(int argc, char **argv)
+{
+ int number_failed;
+ SRunner *sr;
+
+ sr = srunner_create(hashmap_suite_create());
+
+ srunner_run_all(sr, CK_ENV);
+
+ number_failed = srunner_ntests_failed(sr);
+ srunner_free(sr);
+
+ return (number_failed == 0) ? EXIT_SUCCESS : EXIT_FAILURE;
+}
diff --git a/utils/hashmap.c b/utils/hashmap.c
new file mode 100644
index 000000000..7ed19946b
--- /dev/null
+++ b/utils/hashmap.c
@@ -0,0 +1,215 @@
+/*
+ * Copyright 2020 Daniel Silverstone <dsilvers@netsurf-browser.org>
+ *
+ * This file is part of NetSurf, http://www.netsurf-browser.org/
+ *
+ * NetSurf 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; version 2 of the License.
+ *
+ * NetSurf 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 <http://www.gnu.org/licenses/>.
+ */
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "utils/hashmap.h"
+
+/**
+ * The default number of buckets in the hashmaps we create.
+ */
+#define DEFAULT_HASHMAP_BUCKETS (4091)
+
+/**
+ * Hashmaps have chains of entries in buckets.
+ */
+typedef struct hashmap_entry_s {
+ struct hashmap_entry_s **prevptr;
+ struct hashmap_entry_s *next;
+ void *key;
+ void *value;
+ uint32_t key_hash;
+} hashmap_entry_t;
+
+/**
+ * The content of a hashmap
+ */
+struct hashmap_s {
+ /**
+ * The parameters to be used for this hashmap
+ */
+ hashmap_parameters_t *params;
+
+ /**
+ * The buckets for the hash chains
+ */
+ hashmap_entry_t **buckets;
+
+ /**
+ * The number of buckets in this map
+ */
+ uint32_t bucket_count;
+};
+
+/* Exported function, documented in hashmap.h */
+hashmap_t *
+hashmap_create(hashmap_parameters_t *params)
+{
+ hashmap_t *ret = malloc(sizeof(hashmap_t));
+
+ ret->params = params;
+ ret->bucket_count = DEFAULT_HASHMAP_BUCKETS;
+ ret->buckets = malloc(ret->bucket_count * sizeof(hashmap_entry_t *));
+ memset(ret->buckets, 0, ret->bucket_count * sizeof(hashmap_entry_t *));
+
+ if (ret->buckets == NULL) {
+ free(ret);
+ return NULL;
+ }
+
+ return ret;
+}
+
+/* Exported function, documented in hashmap.h */
+void
+hashmap_destroy(hashmap_t *hashmap)
+{
+ uint32_t bucket;
+ hashmap_entry_t *entry;
+
+ for (bucket = 0; bucket < hashmap->bucket_count; bucket++) {
+ for (entry = hashmap->buckets[bucket];
+ entry != NULL;
+ entry = entry->next) {
+ hashmap->params->value_destroy(entry->value);
+ hashmap->params->key_destroy(entry->key);
+ free(entry);
+ }
+ }
+
+ free(hashmap->buckets);
+ free(hashmap);
+}
+
+/* Exported function, documented in hashmap.h */
+void *
+hashmap_lookup(hashmap_t *hashmap, void *key)
+{
+ uint32_t hash = hashmap->params->key_hash(key);
+ hashmap_entry_t *entry = hashmap->buckets[hash % hashmap->bucket_count];
+
+ for(;entry != NULL; entry = entry->next) {
+ if (entry->key_hash == hash) {
+ if (hashmap->params->key_eq(key, entry->key)) {
+ return entry->value;
+ }
+ }
+ }
+
+ return NULL;
+}
+
+/* Exported function, documented in hashmap.h */
+void *
+hashmap_insert(hashmap_t *hashmap, void *key)
+{
+ uint32_t hash = hashmap->params->key_hash(key);
+ uint32_t bucket = hash % hashmap->bucket_count;
+ hashmap_entry_t *entry = hashmap->buckets[bucket];
+ void *new_key, *new_value;
+
+ for(;entry != NULL; entry = entry->next) {
+ if (entry->key_hash == hash) {
+ if (hashmap->params->key_eq(key, entry->key)) {
+ /* This key is already here */
+ new_key = hashmap->params->key_clone(key);
+ if (new_key == NULL) {
+ /* Allocation failed */
+ return NULL;
+ }
+ new_value = hashmap->params->value_alloc(entry->key);
+ if (new_value == NULL) {
+ /* Allocation failed */
+ hashmap->params->key_destroy(new_key);
+ return NULL;
+ }
+ hashmap->params->value_destroy(entry->value);
+ hashmap->params->key_destroy(entry->key);
+ entry->value = new_value;
+ entry->key = new_key;
+ return entry->value;
+ }
+ }
+ }
+
+ /* The key was not found in the map, so allocate a new entry */
+ entry = malloc(sizeof(*entry));
+
+ if (entry == NULL) {
+ return NULL;
+ }
+
+ memset(entry, 0, sizeof(*entry));
+
+ entry->key = hashmap->params->key_clone(key);
+ if (entry->key == NULL) {
+ goto err;
+ }
+ entry->key_hash = hash;
+
+ entry->value = hashmap->params->value_alloc(entry->key);
+ if (entry->value == NULL) {
+ goto err;
+ }
+
+ entry->prevptr = &(hashmap->buckets[bucket]);
+ entry->next = hashmap->buckets[bucket];
+ if (entry->next != NULL) {
+ entry->next->prevptr = &entry->next;
+ }
+
+ hashmap->buckets[bucket] = entry;
+
+ return entry->value;
+
+err:
+ if (entry->value != NULL)
+ hashmap->params->value_destroy(entry->value);
+ if (entry->key != NULL)
+ hashmap->params->key_destroy(entry->key);
+ free(entry);
+
+ return NULL;
+}
+
+/* Exported function, documented in hashmap.h */
+bool
+hashmap_remove(hashmap_t *hashmap, void *key)
+{
+ uint32_t hash = hashmap->params->key_hash(key);
+
+ hashmap_entry_t *entry = hashmap->buckets[hash % hashmap->bucket_count];
+
+ for(;entry != NULL; entry = entry->next) {
+ if (entry->key_hash == hash) {
+ if (hashmap->params->key_eq(key, entry->key)) {
+ hashmap->params->value_destroy(entry->value);
+ hashmap->params->key_destroy(entry->key);
+ if (entry->next != NULL) {
+ entry->next->prevptr = entry->prevptr;
+ }
+ *entry->prevptr = entry->next;
+ free(entry);
+ return true;
+ }
+ }
+ }
+
+ return false;
+}
diff --git a/utils/hashmap.h b/utils/hashmap.h
new file mode 100644
index 000000000..4e1237ae9
--- /dev/null
+++ b/utils/hashmap.h
@@ -0,0 +1,137 @@
+/*
+ * Copyright 2020 Daniel Silverstone <dsilvers@netsurf-browser.org>
+ *
+ * This file is part of NetSurf, http://www.netsurf-browser.org/
+ *
+ * NetSurf 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; version 2 of the License.
+ *
+ * NetSurf 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 <http://www.gnu.org/licenses/>.
+ */
+
+#ifndef NETSURF_HASHMAP_H
+#define NETSURF_HASHMAP_H
+
+#include <stdint.h>
+#include <stdbool.h>
+
+/**
+ * Generic hashmap.
+ *
+ * Hashmaps take ownership of the keys inserted into them by means of a
+ * clone function in their parameters. They also manage the value memory
+ * directly.
+ */
+typedef struct hashmap_s hashmap_t;
+
+/**
+ * Parameters for hashmaps
+ */
+typedef struct {
+ /**
+ * A function which when called will clone a key and give
+ * ownership of the returned object to the hashmap
+ */
+ void * (*key_clone)(void *key);
+
+ /**
+ * A function which when given a key will return its hash.
+ */
+ uint32_t (*key_hash)(void *key);
+
+ /**
+ * A function to compare two keys and return if they are equal.
+ * Note: identity is not necessary, nor strict equality, so long
+ * as the function is a full equality model.
+ * (i.e. key1 == key2 => key2 == key1)
+ */
+ bool (*key_eq)(void *key1, void *key2);
+
+ /**
+ * A function which when called will destroy a key object
+ */
+ void (*key_destroy)(void *key);
+
+ /**
+ * A function which when called will allocate a value object
+ */
+ void * (*value_alloc)(void *key);
+
+ /**
+ * A function which when called will destroy a value object
+ */
+ void (*value_destroy)(void *value);
+} hashmap_parameters_t;
+
+
+/**
+ * Create a hashmap
+ *
+ * The provided hashmap parameter table will be used for map operations
+ * which need to allocate/free etc.
+ *
+ * \param params The hashmap parameters for this map
+ */
+hashmap_t* hashmap_create(hashmap_parameters_t *params);
+
+/**
+ * Destroy a hashmap
+ *
+ * After this, all keys and values will have been destroyed and all memory
+ * associated with this hashmap will be invalidated.
+ *
+ * \param hashmap The hashmap to destroy
+ */
+void hashmap_destroy(hashmap_t *hashmap);
+
+/**
+ * Look up a key in a hashmap
+ *
+ * If the key has an associated value in the hashmap then the pointer to it
+ * is returned, otherwise NULL.
+ *
+ * \param hashmap The hashmap to look up the key inside
+ * \param key The key to look up in the hashmap
+ * \return A pointer to the value if found, NULL otherwise
+ */
+void* hashmap_lookup(hashmap_t *hashmap, void *key);
+
+/**
+ * Create an entry in a hashmap
+ *
+ * This creates a blank value using the parameters and then associates it with
+ * a clone of the given key, inserting it into the hashmap. If a value was
+ * present for the given key already, then it is destroyed first.
+ *
+ * NOTE: If allocation of the new value object fails, then any existing entry
+ * will be left alone, but NULL will be returned.
+ *
+ * \param hashmap The hashmap to insert into
+ * \param key The key to insert an entry for
+ * \return The value pointer for that key, or NULL if allocation failed.
+ */
+void *hashmap_insert(hashmap_t *hashmap, void *key);
+
+/**
+ * Remove an entry from the hashmap
+ *
+ * This will remove the entry for the given key from the hashmap
+ * If there is no such entry, this will safely do nothing.
+ * The value associated with the entry will be destroyed and so should not
+ * be used beyond calling this function.
+ *
+ * \param hashmap The hashmap to remove the entry from
+ * \param key The key to remove the entry for
+ * \return true if an entry was removed, false otherwise
+ */
+bool hashmap_remove(hashmap_t *hashmap, void *key);
+
+
+#endif