From 9fe190f5d500e22b0894095e7c917f9c652e0a64 Mon Sep 17 00:00:00 2001 From: Douglas Rumbaugh Date: Wed, 20 Mar 2024 17:30:14 -0400 Subject: Updates/progress towards succinct trie support --- tests/include/shard_string.h | 168 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 168 insertions(+) create mode 100644 tests/include/shard_string.h (limited to 'tests/include/shard_string.h') diff --git a/tests/include/shard_string.h b/tests/include/shard_string.h new file mode 100644 index 0000000..27ee782 --- /dev/null +++ b/tests/include/shard_string.h @@ -0,0 +1,168 @@ +/* + * tests/include/shard_string.h + * + * Standardized unit tests for Shard objects with string keys + * + * Copyright (C) 2023 Douglas Rumbaugh + * + * Distributed under the Modified BSD License. + * + * WARNING: This file must be included in the main unit test set + * after the definition of an appropriate Shard and R + * type. In particular, R needs to implement the key-value + * pair interface. For other types of record, you'll need to + * use a different set of unit tests. + */ +#pragma once + +/* + * Uncomment these lines temporarily to remove errors in this file + * temporarily for development purposes. They should be removed prior + * to building, to ensure no duplicate definitions. These includes/defines + * should be included in the source file that includes this one, above the + * include statement. + */ +#include "shard/FSTrie.h" +#include "testing.h" +#include +using namespace de; +typedef StringRec R; +typedef FSTrie Shard; + +START_TEST(t_mbuffer_init) +{ + + auto recs = read_string_data(kjv_wordlist, 1024); + + auto buffer = new MutableBuffer(512, 1024); + + for (uint64_t i = 0; i < 512; i++) { + buffer->append(recs[i]); + } + + for (uint64_t i = 0; i < 256; ++i) { + buffer->delete_record(recs[i]); + } + + for (uint64_t i = 512; i < 768; ++i) { + buffer->append(recs[i]); + } + + Shard* shard = new Shard(buffer->get_buffer_view()); + ck_assert_uint_eq(shard->get_record_count(), 512); + + delete buffer; + delete shard; +} + + +START_TEST(t_shard_init) +{ + size_t n = 512; + auto mbuffer1 = create_test_mbuffer(n); + auto mbuffer2 = create_test_mbuffer(n); + auto mbuffer3 = create_test_mbuffer(n); + + auto shard1 = new Shard(mbuffer1->get_buffer_view()); + auto shard2 = new Shard(mbuffer2->get_buffer_view()); + auto shard3 = new Shard(mbuffer3->get_buffer_view()); + + std::vector shards = {shard1, shard2, shard3}; + auto shard4 = new Shard(shards); + + ck_assert_int_eq(shard4->get_record_count(), n * 3); + ck_assert_int_eq(shard4->get_tombstone_count(), 0); + + size_t total_cnt = 0; + size_t shard1_idx = 0; + size_t shard2_idx = 0; + size_t shard3_idx = 0; + + for (size_t i = 0; i < shard4->get_record_count(); ++i) { + auto rec1 = shard1->get_record_at(shard1_idx); + auto rec2 = shard2->get_record_at(shard2_idx); + auto rec3 = shard3->get_record_at(shard3_idx); + + auto cur_rec = shard4->get_record_at(i); + + if (shard1_idx < n && cur_rec->rec == rec1->rec) { + ++shard1_idx; + } else if (shard2_idx < n && cur_rec->rec == rec2->rec) { + ++shard2_idx; + } else if (shard3_idx < n && cur_rec->rec == rec3->rec) { + ++shard3_idx; + } else { + assert(false); + } + } + + delete mbuffer1; + delete mbuffer2; + delete mbuffer3; + + delete shard1; + delete shard2; + delete shard3; + delete shard4; +} + +START_TEST(t_point_lookup) +{ + size_t n = 10000; + + auto buffer = create_test_mbuffer(n); + auto shard = Shard(buffer->get_buffer_view()); + + { + auto view = buffer->get_buffer_view(); + + for (size_t i=0; irec.key; + r.value = rec->rec.value; + + auto result = shard.point_lookup(r); + ck_assert_ptr_nonnull(result); + ck_assert_str_eq(result->rec.key.c_str(), r.key.c_str()); + ck_assert_int_eq(result->rec.value, r.value); + fprintf(stderr, "%ld\n", i); + } + } + + delete buffer; +} +END_TEST + + +START_TEST(t_point_lookup_miss) +{ + size_t n = 10000; + + auto buffer = create_test_mbuffer(n); + auto shard = Shard(buffer->get_buffer_view()); + + for (size_t i=n + 100; i<2*n; i++) { + R r; + r.key = std::string("computer"); + r.value = 1234; + + auto result = shard.point_lookup(r); + ck_assert_ptr_null(result); + } + + delete buffer; +} + +static void inject_shard_tests(Suite *suite) { + TCase *create = tcase_create("Shard constructor Testing"); + tcase_add_test(create, t_mbuffer_init); + tcase_add_test(create, t_shard_init); + tcase_set_timeout(create, 100); + suite_add_tcase(suite, create); + + TCase *pointlookup = tcase_create("Shard point lookup Testing"); + tcase_add_test(pointlookup, t_point_lookup); + tcase_add_test(pointlookup, t_point_lookup_miss); + suite_add_tcase(suite, pointlookup); +} -- cgit v1.2.3 From 147f0df58e1ff4973bffb7e4628e6b2fdc20eb57 Mon Sep 17 00:00:00 2001 From: Douglas Rumbaugh Date: Fri, 22 Mar 2024 14:04:40 -0400 Subject: FSTrie testing and debugging --- tests/include/shard_string.h | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-) (limited to 'tests/include/shard_string.h') diff --git a/tests/include/shard_string.h b/tests/include/shard_string.h index 27ee782..fa51630 100644 --- a/tests/include/shard_string.h +++ b/tests/include/shard_string.h @@ -58,7 +58,7 @@ START_TEST(t_mbuffer_init) START_TEST(t_shard_init) { - size_t n = 512; + size_t n = 2048; auto mbuffer1 = create_test_mbuffer(n); auto mbuffer2 = create_test_mbuffer(n); auto mbuffer3 = create_test_mbuffer(n); @@ -117,16 +117,14 @@ START_TEST(t_point_lookup) auto view = buffer->get_buffer_view(); for (size_t i=0; irec.key; - r.value = rec->rec.value; + R r = rec->rec; auto result = shard.point_lookup(r); ck_assert_ptr_nonnull(result); ck_assert_str_eq(result->rec.key.c_str(), r.key.c_str()); ck_assert_int_eq(result->rec.value, r.value); - fprintf(stderr, "%ld\n", i); + //fprintf(stderr, "%ld\n", i); } } -- cgit v1.2.3 From b25beb13773072c3b143842b45a7c32a1108f347 Mon Sep 17 00:00:00 2001 From: Douglas Rumbaugh Date: Mon, 15 Apr 2024 14:00:27 -0400 Subject: Updated FSTrie to use const char * instead of std::string Note: this requires the caller to manage the memory of the strings --- tests/include/shard_string.h | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-) (limited to 'tests/include/shard_string.h') diff --git a/tests/include/shard_string.h b/tests/include/shard_string.h index fa51630..2d7a72a 100644 --- a/tests/include/shard_string.h +++ b/tests/include/shard_string.h @@ -122,7 +122,7 @@ START_TEST(t_point_lookup) auto result = shard.point_lookup(r); ck_assert_ptr_nonnull(result); - ck_assert_str_eq(result->rec.key.c_str(), r.key.c_str()); + ck_assert_str_eq(result->rec.key, r.key); ck_assert_int_eq(result->rec.value, r.value); //fprintf(stderr, "%ld\n", i); } @@ -141,9 +141,8 @@ START_TEST(t_point_lookup_miss) auto shard = Shard(buffer->get_buffer_view()); for (size_t i=n + 100; i<2*n; i++) { - R r; - r.key = std::string("computer"); - r.value = 1234; + const char *c = "computer"; + R r = {c, 1234, 8}; auto result = shard.point_lookup(r); ck_assert_ptr_null(result); -- cgit v1.2.3 From 438feac7e56fee425d9c6f1a43298ff9dc5b71d1 Mon Sep 17 00:00:00 2001 From: Douglas Rumbaugh Date: Fri, 19 Apr 2024 17:38:16 -0400 Subject: Properly implemented support for iteratively decomposable problems --- tests/include/shard_string.h | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) (limited to 'tests/include/shard_string.h') diff --git a/tests/include/shard_string.h b/tests/include/shard_string.h index 2d7a72a..881f41a 100644 --- a/tests/include/shard_string.h +++ b/tests/include/shard_string.h @@ -26,8 +26,8 @@ #include "testing.h" #include using namespace de; -typedef StringRec R; -typedef FSTrie Shard; +//typedef StringRec R; +//typedef FSTrie Shard; START_TEST(t_mbuffer_init) { @@ -122,8 +122,8 @@ START_TEST(t_point_lookup) auto result = shard.point_lookup(r); ck_assert_ptr_nonnull(result); - ck_assert_str_eq(result->rec.key, r.key); - ck_assert_int_eq(result->rec.value, r.value); + //ck_assert_str_eq(result->rec.key, r.key); + //ck_assert_int_eq(result->rec.value, r.value); //fprintf(stderr, "%ld\n", i); } } -- cgit v1.2.3