From f65912600fc301cbdbb613f1df0dc29820f1da35 Mon Sep 17 00:00:00 2001 From: David Robillard Date: Thu, 18 Aug 2022 13:18:52 -0400 Subject: Use conventional test executable names --- test/test_hash.c | 421 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 421 insertions(+) create mode 100644 test/test_hash.c (limited to 'test/test_hash.c') diff --git a/test/test_hash.c b/test/test_hash.c new file mode 100644 index 0000000..287dbaa --- /dev/null +++ b/test/test_hash.c @@ -0,0 +1,421 @@ +// Copyright 2011-2021 David Robillard +// SPDX-License-Identifier: ISC + +#undef NDEBUG + +#define ZIX_HASH_KEY_TYPE const char +#define ZIX_HASH_RECORD_TYPE const char + +#include "failing_allocator.h" +#include "test_data.h" + +#include "zix/allocator.h" +#include "zix/attributes.h" +#include "zix/common.h" +#include "zix/digest.h" +#include "zix/hash.h" + +#include +#include +#include +#include +#include +#include +#include +#include + +static bool expect_failure = false; + +ZIX_LOG_FUNC(4, 5) +static int +test_fail(ZixHash* const hash, + char* const buffer, + char** const strings, + const char* fmt, + ...) +{ + if (!expect_failure) { + va_list args; + va_start(args, fmt); + fprintf(stderr, "error: "); + vfprintf(stderr, fmt, args); + va_end(args); + } + + zix_hash_free(hash); + free(buffer); + free(strings); + + return expect_failure ? 0 : 1; +} + +ZIX_PURE_FUNC static const char* +identity(const char* record) +{ + return record; +} + +/// Decent hash function using zix_digest (murmur2) +ZIX_PURE_FUNC static size_t +decent_string_hash(const char* const str) +{ + return zix_digest(0U, str, strlen(str)); +} + +/// Terrible hash function from K&R first edition +ZIX_PURE_FUNC static size_t +terrible_string_hash(const char* str) +{ + size_t hash = 0U; + uint8_t c = 0U; + + while ((c = (uint8_t)*str++)) { + hash += c; + } + + return hash; +} + +ZIX_PURE_FUNC static size_t +string_hash_aligned(const char* const str) +{ + size_t length = strlen(str); + + length = (length + (sizeof(size_t) - 1)) / sizeof(size_t) * sizeof(size_t); + return zix_digest_aligned(0U, str, length); +} + +ZIX_PURE_FUNC static size_t +string_hash32(const char* const str) +{ + return (size_t)zix_digest32(0U, str, strlen(str)); +} + +ZIX_PURE_FUNC static size_t +string_hash64(const char* const str) +{ + return (size_t)zix_digest64(0U, str, strlen(str)); +} + +ZIX_PURE_FUNC static size_t +string_hash32_aligned(const char* const str) +{ + size_t length = strlen(str); + + length = (length + 3U) / 4U * 4U; + return (size_t)zix_digest32_aligned(0U, str, length); +} + +#if UINTPTR_MAX >= UINT64_MAX + +ZIX_PURE_FUNC static size_t +string_hash64_aligned(const char* const str) +{ + size_t length = strlen(str); + + length = (length + 7U) / 8U * 8U; + return (size_t)zix_digest64_aligned(0U, str, length); +} + +#endif + +static bool +string_equal(const char* const a, const char* const b) +{ + return !strcmp(a, b); +} + +static int +stress_with(ZixAllocator* const allocator, + const ZixHashFunc hash_func, + const size_t n_elems) +{ + ZixHash* hash = zix_hash_new(allocator, identity, hash_func, string_equal); + if (!hash) { + return test_fail(hash, NULL, NULL, "Failed to allocate hash\n"); + } + + static const size_t string_length = 15; + + char* const buffer = (char*)calloc(1, n_elems * (string_length + 1)); + char** const strings = (char**)calloc(sizeof(char*), n_elems); + if (!buffer || !strings) { + return test_fail(hash, buffer, strings, "Failed to allocate strings\n"); + } + + uint32_t seed = 1U; + for (size_t i = 0U; i < n_elems; ++i) { + strings[i] = buffer + i * (string_length + 1); + assert((uintptr_t)strings[i] % sizeof(size_t) == 0); + assert((uintptr_t)strings[i] % sizeof(uint32_t) == 0); + + for (size_t j = 0U; j < string_length; ++j) { + seed = lcg32(seed); + strings[i][j] = (char)('!' + (seed % 92)); + } + } + + // Insert each string + for (size_t i = 0; i < n_elems; ++i) { + ZixStatus st = zix_hash_insert(hash, strings[i]); + if (st) { + return test_fail( + hash, buffer, strings, "Failed to insert `%s'\n", strings[i]); + } + } + + // Ensure hash size is correct + if (zix_hash_size(hash) != n_elems) { + return test_fail(hash, + buffer, + strings, + "Hash size %" PRIuPTR " != %" PRIuPTR "\n", + zix_hash_size(hash), + n_elems); + } + + // Attempt to insert each string again + for (size_t i = 0; i < n_elems; ++i) { + ZixStatus st = zix_hash_insert(hash, strings[i]); + if (st != ZIX_STATUS_EXISTS) { + return test_fail(hash, + buffer, + strings, + "Double inserted `%s' (%s)\n", + strings[i], + zix_strerror(st)); + } + } + + // Search for each string + for (size_t i = 0; i < n_elems; ++i) { + const char* match = (const char*)zix_hash_find_record(hash, strings[i]); + if (!match) { + return test_fail( + hash, buffer, strings, "Failed to find `%s'\n", strings[i]); + } + if (match != strings[i]) { + return test_fail( + hash, buffer, strings, "Bad match for `%s': `%s'\n", strings[i], match); + } + } + + static const char* const not_indexed_string = "__not__indexed__"; + + // Do a quick smoke test to ensure that false matches don't succeed + char* const not_indexed = (char*)calloc(1, strlen(not_indexed_string) + 1); + if (not_indexed) { + memcpy(not_indexed, not_indexed_string, strlen(not_indexed_string) + 1); + const char* match = (const char*)zix_hash_find_record(hash, not_indexed); + if (match) { + return test_fail( + hash, buffer, strings, "Unexpectedly found `%s'\n", not_indexed); + } + free(not_indexed); + } + + // Remove strings + for (size_t i = 0; i < n_elems; ++i) { + const size_t initial_size = zix_hash_size(hash); + + // Remove string + const char* removed = NULL; + ZixStatus st = zix_hash_remove(hash, strings[i], &removed); + if (st) { + return test_fail( + hash, buffer, strings, "Failed to remove `%s'\n", strings[i]); + } + + // Ensure the removed value is what we expected + if (removed != strings[i]) { + return test_fail(hash, + buffer, + strings, + "Removed `%s` instead of `%s`\n", + removed, + strings[i]); + } + + // Ensure size is updated + if (zix_hash_size(hash) != initial_size - 1) { + return test_fail( + hash, buffer, strings, "Removing node did not decrease hash size\n"); + } + + // Ensure second removal fails + st = zix_hash_remove(hash, strings[i], &removed); + if (st != ZIX_STATUS_NOT_FOUND) { + return test_fail( + hash, buffer, strings, "Unexpectedly removed `%s' twice\n", strings[i]); + } + + // Ensure value can no longer be found + assert(zix_hash_find(hash, strings[i]) == zix_hash_end(hash)); + + // Check to ensure remaining strings are still present + for (size_t j = i + 1; j < n_elems; ++j) { + const char* match = (const char*)zix_hash_find_record(hash, strings[j]); + if (!match) { + return test_fail(hash, + buffer, + strings, + "Failed to find `%s' after remove\n", + strings[j]); + } + if (match != strings[j]) { + return test_fail(hash, + buffer, + strings, + "Bad match for `%s' after remove\n", + strings[j]); + } + } + } + + // Insert each string again (to check non-empty destruction) + for (size_t i = 0; i < n_elems; ++i) { + ZixHashInsertPlan plan = zix_hash_plan_insert(hash, strings[i]); + + assert(!zix_hash_record_at(hash, plan)); + ZixStatus st = zix_hash_insert_at(hash, plan, strings[i]); + if (st) { + return test_fail( + hash, buffer, strings, "Failed to insert `%s'\n", strings[i]); + } + } + + // Check key == value (and test zix_hash_foreach) + size_t n_checked = 0U; + for (ZixHashIter i = zix_hash_begin(hash); i != zix_hash_end(hash); + i = zix_hash_next(hash, i)) { + const char* const string = (const char*)zix_hash_get(hash, i); + assert(string); + if (strlen(string) < 3) { + return test_fail(hash, buffer, strings, "Corrupt value `%s'\n", string); + } + + ++n_checked; + } + if (n_checked != n_elems) { + return test_fail(hash, buffer, strings, "Check failed\n"); + } + + free(strings); + free(buffer); + zix_hash_free(hash); + + return 0; +} + +static int +stress(ZixAllocator* const allocator, const size_t n_elems) +{ + if (stress_with(allocator, decent_string_hash, n_elems) || + stress_with(allocator, terrible_string_hash, n_elems / 4) || + stress_with(allocator, string_hash_aligned, n_elems / 4) || + stress_with(allocator, string_hash32, n_elems / 4) || + stress_with(allocator, string_hash64, n_elems / 4) || + stress_with(allocator, string_hash32_aligned, n_elems / 4)) { + return 1; + } + +#if UINTPTR_MAX >= UINT64_MAX + if (stress_with(allocator, string_hash64_aligned, n_elems / 4)) { + return 1; + } +#endif + + return 0; +} + +/// Identity hash function for numeric strings for explicitly hitting cases +ZIX_PURE_FUNC static size_t +identity_index_hash(const char* const str) +{ + return strtoul(str, NULL, 10); +} + +static void +test_all_tombstones(void) +{ + /* This tests an edge case where a minimum-sized table can be entirely full + of tombstones. If the search loop is not written carefully, then this can + result in a hang. This has been seen to occur in real code, though it's + very hard to hit with a decent hash function. So, we use the above + degenerate index hashing function to explicitly place elements exactly + where we want to hit this case. */ + +#define N_STRINGS 4 + + static const char* original_strings[N_STRINGS] = { + "0 a", + "1 a", + "2 a", + "3 a", + }; + + static const char* collision_strings[N_STRINGS] = { + "0 b", + "1 b", + "2 b", + "3 b", + }; + + ZixStatus st = ZIX_STATUS_SUCCESS; + ZixHash* hash = + zix_hash_new(NULL, identity, identity_index_hash, string_equal); + + // Insert each element then immediately remove it + for (unsigned i = 0U; i < N_STRINGS; ++i) { + const char* removed = NULL; + + assert(!zix_hash_insert(hash, original_strings[i])); + assert(!zix_hash_remove(hash, original_strings[i], &removed)); + } + + // Now the table should be "empty" but contain tombstones + assert(zix_hash_size(hash) == 0); + + // Insert clashing elements which should hit the "all tombstones" case + for (unsigned i = 0U; i < N_STRINGS; ++i) { + assert(!zix_hash_insert(hash, collision_strings[i])); + assert(!st); + } + + zix_hash_free(hash); + +#undef N_STRINGS +} + +static void +test_failed_alloc(void) +{ + ZixFailingAllocator allocator = zix_failing_allocator(); + + // Successfully stress test the tree to count the number of allocations + assert(!stress(&allocator.base, 16)); + + // Test that each allocation failing is handled gracefully + const size_t n_new_allocs = allocator.n_allocations; + for (size_t i = 0U; i < n_new_allocs; ++i) { + allocator.n_remaining = i; + assert(stress(&allocator.base, 16)); + } +} + +int +main(void) +{ + zix_hash_free(NULL); + + test_all_tombstones(); + test_failed_alloc(); + + static const size_t n_elems = 1024U; + + if (stress(NULL, n_elems)) { + return 1; + } + + return 0; +} -- cgit v1.2.1