summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDaniel Silverstone <dsilvers@digital-scurf.org>2020-02-23 16:46:22 +0000
committerDaniel Silverstone <dsilvers@digital-scurf.org>2020-02-23 20:59:39 +0000
commit54b1960d18042cf6dfd86cfe01d58455357586d2 (patch)
tree42286b7f107b465780cdaaa0532d2f2b8b8e5072
parentfd80341513813684ba3155b87e4e6cc8c87631f1 (diff)
downloadnetsurf-54b1960d18042cf6dfd86cfe01d58455357586d2.tar.gz
netsurf-54b1960d18042cf6dfd86cfe01d58455357586d2.tar.bz2
utils: Add iteration API to hashmap
Signed-off-by: Daniel Silverstone <dsilvers@digital-scurf.org>
-rw-r--r--test/hashmap.c101
-rw-r--r--utils/hashmap.c19
-rw-r--r--utils/hashmap.h22
3 files changed, 141 insertions, 1 deletions
diff --git a/test/hashmap.c b/test/hashmap.c
index 87db6c174..4bda493ae 100644
--- a/test/hashmap.c
+++ b/test/hashmap.c
@@ -151,6 +151,20 @@ static hashmap_parameters_t test_params = {
.value_destroy = value_destroy,
};
+/* Iteration helpers */
+
+static size_t iteration_counter = 0;
+static size_t iteration_stop = 0;
+static char iteration_ctx = 0;
+
+static bool
+hashmap_test_iterator_cb(void *key, void *value, void *ctx)
+{
+ ck_assert(ctx == &iteration_ctx);
+ iteration_counter++;
+ return iteration_counter == iteration_stop;
+}
+
/* Fixtures for basic tests */
static hashmap_t *test_hashmap = NULL;
@@ -230,6 +244,35 @@ START_TEST(insert_then_lookup)
}
END_TEST
+START_TEST(iterate_empty)
+{
+ iteration_stop = iteration_counter = 0;
+ ck_assert(hashmap_iterate(test_hashmap, hashmap_test_iterator_cb, &iteration_ctx) == false);
+ ck_assert_int_eq(iteration_counter, 0);
+}
+END_TEST
+
+START_TEST(iterate_one)
+{
+ iteration_stop = iteration_counter = 0;
+ hashmap_test_value_t *value = hashmap_insert(test_hashmap, corestring_nsurl_about_blank);
+ ck_assert(value != NULL);
+ ck_assert(hashmap_iterate(test_hashmap, hashmap_test_iterator_cb, &iteration_ctx) == false);
+ ck_assert_int_eq(iteration_counter, 1);
+}
+END_TEST
+
+START_TEST(iterate_one_and_stop)
+{
+ iteration_stop = 1;
+ iteration_counter = 0;
+ hashmap_test_value_t *value = hashmap_insert(test_hashmap, corestring_nsurl_about_blank);
+ ck_assert(value != NULL);
+ ck_assert(hashmap_iterate(test_hashmap, hashmap_test_iterator_cb, &iteration_ctx) == true);
+ ck_assert_int_eq(iteration_counter, 1);
+}
+END_TEST
+
static TCase *basic_api_case_create(void)
{
TCase *tc;
@@ -245,7 +288,11 @@ static TCase *basic_api_case_create(void)
tcase_add_test(tc, remove_not_present);
tcase_add_test(tc, insert_then_remove);
tcase_add_test(tc, insert_then_lookup);
-
+
+ tcase_add_test(tc, iterate_empty);
+ tcase_add_test(tc, iterate_one);
+ tcase_add_test(tc, iterate_one_and_stop);
+
return tc;
}
@@ -374,6 +421,57 @@ START_TEST(chain_add_all_twice_remove_all)
}
END_TEST
+START_TEST(chain_add_all_twice_remove_all_iterate)
+{
+ case_pair *chain_case;
+ size_t chain_count = 0;
+
+ 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);
+ chain_count++;
+ }
+
+ iteration_counter = 0;
+ iteration_stop = 0;
+ ck_assert(hashmap_iterate(test_hashmap, hashmap_test_iterator_cb, &iteration_ctx) == false);
+ ck_assert_int_eq(iteration_counter, chain_count);
+
+ 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);
+ }
+
+ iteration_counter = 0;
+ iteration_stop = 0;
+ ck_assert(hashmap_iterate(test_hashmap, hashmap_test_iterator_cb, &iteration_ctx) == false);
+ ck_assert_int_eq(iteration_counter, chain_count);
+
+ iteration_counter = 0;
+ iteration_stop = chain_count;
+ ck_assert(hashmap_iterate(test_hashmap, hashmap_test_iterator_cb, &iteration_ctx) == true);
+ ck_assert_int_eq(iteration_counter, chain_count);
+
+ for (chain_case = chain_pairs;
+ chain_case->url != NULL;
+ chain_case++) {
+ ck_assert(hashmap_remove(test_hashmap, chain_case->nsurl) == true);
+ }
+
+ iteration_counter = 0;
+ iteration_stop = chain_count;
+ ck_assert(hashmap_iterate(test_hashmap, hashmap_test_iterator_cb, &iteration_ctx) == false);
+ ck_assert_int_eq(iteration_counter, 0);
+
+ 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)
@@ -431,6 +529,7 @@ static TCase *chain_case_create(void)
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_test(tc, chain_add_all_twice_remove_all_iterate);
tcase_add_loop_test(tc, chain_add_all_remove_all_alloc, 0, CHAIN_TEST_MALLOC_COUNT_MAX + 1);
diff --git a/utils/hashmap.c b/utils/hashmap.c
index 7ed19946b..bfbf6ceb8 100644
--- a/utils/hashmap.c
+++ b/utils/hashmap.c
@@ -213,3 +213,22 @@ hashmap_remove(hashmap_t *hashmap, void *key)
return false;
}
+
+/* Exported function, documented in hashmap.h */
+bool
+hashmap_iterate(hashmap_t *hashmap, hashmap_iteration_cb_t cb, void *ctx)
+{
+ for (uint32_t bucket = 0;
+ bucket < hashmap->bucket_count;
+ bucket++) {
+ for (hashmap_entry_t *entry = hashmap->buckets[bucket];
+ entry != NULL;
+ entry = entry->next) {
+ /* If the callback returns true, we early-exit */
+ if (cb(entry->key, entry->value, ctx))
+ return true;
+ }
+ }
+
+ return false;
+}
diff --git a/utils/hashmap.h b/utils/hashmap.h
index 462b51ed2..cb8fd5074 100644
--- a/utils/hashmap.h
+++ b/utils/hashmap.h
@@ -62,6 +62,16 @@ typedef void* (*hashmap_value_alloc_t)(void *);
typedef void (*hashmap_value_destroy_t)(void *);
/**
+ * Hashmap iteration callback function type.
+ *
+ * First parameter is the key, second is the value.
+ * The final parameter is the context pointer for the iteration.
+ *
+ * Return true to stop iterating early
+ */
+typedef bool (*hashmap_iteration_cb_t)(void *, void *, void *);
+
+/**
* Parameters for hashmaps
*/
typedef struct {
@@ -163,5 +173,17 @@ void *hashmap_insert(hashmap_t *hashmap, void *key);
*/
bool hashmap_remove(hashmap_t *hashmap, void *key);
+/**
+ * Iterate the hashmap
+ *
+ * For each key/value pair in the hashmap, call the callback passing in
+ * the key and value. During iteration you MUST NOT mutate the hashmap.
+ *
+ * \param hashmap The hashmap to iterate
+ * \param cb The callback for each key,value pair
+ * \param ctx The callback context
+ * \return Whether or not we stopped iteration early
+ */
+bool hashmap_iterate(hashmap_t *hashmap, hashmap_iteration_cb_t cb, void *ctx);
#endif