diff options
Diffstat (limited to 'tests')
27 files changed, 2489 insertions, 2346 deletions
diff --git a/tests/alias_tests.cpp b/tests/alias_tests.cpp new file mode 100644 index 0000000..98d0c63 --- /dev/null +++ b/tests/alias_tests.cpp @@ -0,0 +1,61 @@ +/* + * tests/alias_tests.cpp + * + * Unit tests for Alias shard + * + * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> + * Dong Xie <dongx@psu.edu> + * + * Distributed under the Modified BSD License. + * + */ + +#include "shard/Alias.h" +#include "query/wss.h" +#include "framework/structure/MutableBuffer.h" +#include "include/testing.h" + + +#include <check.h> + +using namespace de; + +typedef WRec R; +typedef Alias<R> Shard; + + +#include "include/shard_standard.h" +#include "include/rangequery.h" + +Suite *unit_testing() +{ + Suite *unit = suite_create("ISAMTree Shard Unit Testing"); + + inject_rangequery_tests(unit); + inject_shard_tests(unit); + + return unit; +} + + +int shard_unit_tests() +{ + int failed = 0; + Suite *unit = unit_testing(); + SRunner *unit_shardner = srunner_create(unit); + + srunner_run_all(unit_shardner, CK_NORMAL); + failed = srunner_ntests_failed(unit_shardner); + srunner_free(unit_shardner); + + return failed; +} + + +int main() +{ + int unit_failed = shard_unit_tests(); + + return (unit_failed == 0) ? EXIT_SUCCESS : EXIT_FAILURE; +} + diff --git a/tests/augbtree_tests.cpp b/tests/augbtree_tests.cpp new file mode 100644 index 0000000..c7a0885 --- /dev/null +++ b/tests/augbtree_tests.cpp @@ -0,0 +1,55 @@ +/* + * tests/isam_tests.cpp + * + * Unit tests for ISAM Tree shard + * + * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> + * Dong Xie <dongx@psu.edu> + * + * Distributed under the Modified BSD License. + * + */ + +#include "shard/AugBTree.h" +#include "include/testing.h" +#include <check.h> + +using namespace de; + +typedef WRec R; +typedef AugBTree<R> Shard; + +#include "include/shard_standard.h" +#include "include/rangequery.h" + +Suite *unit_testing() +{ + Suite *unit = suite_create("Alias-augmented B+Tree Shard Unit Testing"); + + inject_rangequery_tests(unit); + inject_shard_tests(unit); + + return unit; +} + + +int shard_unit_tests() +{ + int failed = 0; + Suite *unit = unit_testing(); + SRunner *unit_shardner = srunner_create(unit); + + srunner_run_all(unit_shardner, CK_NORMAL); + failed = srunner_ntests_failed(unit_shardner); + srunner_free(unit_shardner); + + return failed; +} + + +int main() +{ + int unit_failed = shard_unit_tests(); + + return (unit_failed == 0) ? EXIT_SUCCESS : EXIT_FAILURE; +} diff --git a/tests/de_level_concurrent.cpp b/tests/de_level_concurrent.cpp new file mode 100644 index 0000000..2039efb --- /dev/null +++ b/tests/de_level_concurrent.cpp @@ -0,0 +1,58 @@ +/* + * tests/de_level_tomb.cpp + * + * Unit tests for Dynamic Extension Framework + * + * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> + * Dong Xie <dongx@psu.edu> + * + * Distributed under the Modified BSD License. + * + */ +#include <set> +#include <random> +#include <algorithm> + +#include "include/testing.h" +#include "framework/DynamicExtension.h" +#include "shard/ISAMTree.h" +#include "query/rangequery.h" + +#include <check.h> +using namespace de; + +typedef Rec R; +typedef DynamicExtension<R, ISAMTree<R>, rq::Query<R, ISAMTree<R>>, LayoutPolicy::LEVELING, DeletePolicy::TOMBSTONE, FIFOScheduler> DE; + +#include "include/concurrent_extension.h" + + +Suite *unit_testing() +{ + Suite *unit = suite_create("DynamicExtension: Tombstone Leveling Testing"); + inject_dynamic_extension_tests(unit); + + return unit; +} + + +int shard_unit_tests() +{ + int failed = 0; + Suite *unit = unit_testing(); + SRunner *unit_shardner = srunner_create(unit); + + srunner_run_all(unit_shardner, CK_NORMAL); + failed = srunner_ntests_failed(unit_shardner); + srunner_free(unit_shardner); + + return failed; +} + + +int main() +{ + int unit_failed = shard_unit_tests(); + + return (unit_failed == 0) ? EXIT_SUCCESS : EXIT_FAILURE; +} diff --git a/tests/de_level_tag.cpp b/tests/de_level_tag.cpp index 91f158c..75131c4 100644 --- a/tests/de_level_tag.cpp +++ b/tests/de_level_tag.cpp @@ -1,25 +1,58 @@ /* - * tests/dynamic_extension_tests.cpp + * tests/de_level_tag.cpp * * Unit tests for Dynamic Extension Framework * * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> * Dong Xie <dongx@psu.edu> * - * All rights reserved. Published under the Modified BSD License. + * Distributed under the Modified BSD License. * */ #include <set> #include <random> #include <algorithm> -#include "testing.h" +#include "include/testing.h" #include "framework/DynamicExtension.h" -#include "shard/WIRS.h" +#include "shard/ISAMTree.h" +#include "query/rangequery.h" #include <check.h> using namespace de; -typedef DynamicExtension<WRec, WIRS<WRec>, WIRSQuery<WRec>, LayoutPolicy::LEVELING, DeletePolicy::TAGGING> DE; +typedef Rec R; +typedef DynamicExtension<R, ISAMTree<R>, rq::Query<R, ISAMTree<R>>, LayoutPolicy::LEVELING, DeletePolicy::TAGGING, SerialScheduler> DE; -#include "dynamic_extension_tests.inc" +#include "include/dynamic_extension.h" + + +Suite *unit_testing() +{ + Suite *unit = suite_create("DynamicExtension: Tagged Leveling Testing"); + inject_dynamic_extension_tests(unit); + + return unit; +} + + +int shard_unit_tests() +{ + int failed = 0; + Suite *unit = unit_testing(); + SRunner *unit_shardner = srunner_create(unit); + + srunner_run_all(unit_shardner, CK_NORMAL); + failed = srunner_ntests_failed(unit_shardner); + srunner_free(unit_shardner); + + return failed; +} + + +int main() +{ + int unit_failed = shard_unit_tests(); + + return (unit_failed == 0) ? EXIT_SUCCESS : EXIT_FAILURE; +} diff --git a/tests/de_level_tomb.cpp b/tests/de_level_tomb.cpp index c3dc5df..6da211d 100644 --- a/tests/de_level_tomb.cpp +++ b/tests/de_level_tomb.cpp @@ -1,25 +1,59 @@ /* - * tests/dynamic_extension_tests.cpp + * tests/de_level_tomb.cpp * * Unit tests for Dynamic Extension Framework * * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> * Dong Xie <dongx@psu.edu> * - * All rights reserved. Published under the Modified BSD License. + * Distributed under the Modified BSD License. * */ #include <set> #include <random> #include <algorithm> -#include "testing.h" +#include "include/testing.h" #include "framework/DynamicExtension.h" -#include "shard/WIRS.h" +#include "shard/ISAMTree.h" +#include "query/rangequery.h" +#include "shard/TrieSpline.h" #include <check.h> using namespace de; -typedef DynamicExtension<WRec, WIRS<WRec>, WIRSQuery<WRec>, LayoutPolicy::LEVELING, DeletePolicy::TOMBSTONE> DE; +typedef Rec R; +typedef DynamicExtension<R, ISAMTree<R>, rq::Query<R, ISAMTree<R>>, LayoutPolicy::LEVELING, DeletePolicy::TOMBSTONE, SerialScheduler> DE; -#include "dynamic_extension_tests.inc" +#include "include/dynamic_extension.h" + + +Suite *unit_testing() +{ + Suite *unit = suite_create("DynamicExtension: Tombstone Leveling Testing"); + inject_dynamic_extension_tests(unit); + + return unit; +} + + +int shard_unit_tests() +{ + int failed = 0; + Suite *unit = unit_testing(); + SRunner *unit_shardner = srunner_create(unit); + + srunner_run_all(unit_shardner, CK_NORMAL); + failed = srunner_ntests_failed(unit_shardner); + srunner_free(unit_shardner); + + return failed; +} + + +int main() +{ + int unit_failed = shard_unit_tests(); + + return (unit_failed == 0) ? EXIT_SUCCESS : EXIT_FAILURE; +} diff --git a/tests/de_tier_concurrent.cpp b/tests/de_tier_concurrent.cpp new file mode 100644 index 0000000..722b9bd --- /dev/null +++ b/tests/de_tier_concurrent.cpp @@ -0,0 +1,58 @@ +/* + * tests/de_level_tomb.cpp + * + * Unit tests for Dynamic Extension Framework + * + * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> + * Dong Xie <dongx@psu.edu> + * + * Distributed under the Modified BSD License. + * + */ +#include <set> +#include <random> +#include <algorithm> + +#include "include/testing.h" +#include "framework/DynamicExtension.h" +#include "shard/ISAMTree.h" +#include "query/rangequery.h" + +#include <check.h> +using namespace de; + +typedef Rec R; +typedef DynamicExtension<R, ISAMTree<R>, rq::Query<R, ISAMTree<R>>, LayoutPolicy::TEIRING, DeletePolicy::TOMBSTONE, FIFOScheduler> DE; + +#include "include/concurrent_extension.h" + + +Suite *unit_testing() +{ + Suite *unit = suite_create("DynamicExtension: Tombstone Leveling Testing"); + inject_dynamic_extension_tests(unit); + + return unit; +} + + +int shard_unit_tests() +{ + int failed = 0; + Suite *unit = unit_testing(); + SRunner *unit_shardner = srunner_create(unit); + + srunner_run_all(unit_shardner, CK_NORMAL); + failed = srunner_ntests_failed(unit_shardner); + srunner_free(unit_shardner); + + return failed; +} + + +int main() +{ + int unit_failed = shard_unit_tests(); + + return (unit_failed == 0) ? EXIT_SUCCESS : EXIT_FAILURE; +} diff --git a/tests/de_tier_tag.cpp b/tests/de_tier_tag.cpp index 9b6b5a4..79bb7bf 100644 --- a/tests/de_tier_tag.cpp +++ b/tests/de_tier_tag.cpp @@ -1,25 +1,59 @@ /* - * tests/dynamic_extension_tests.cpp + * tests/de_tier_tag.cpp * * Unit tests for Dynamic Extension Framework * * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> * Dong Xie <dongx@psu.edu> * - * All rights reserved. Published under the Modified BSD License. + * Distributed under the Modified BSD License. * */ #include <set> #include <random> #include <algorithm> -#include "testing.h" +#include "include/testing.h" #include "framework/DynamicExtension.h" -#include "shard/WIRS.h" +#include "framework/scheduling/SerialScheduler.h" +#include "shard/ISAMTree.h" +#include "query/rangequery.h" #include <check.h> using namespace de; -typedef DynamicExtension<WRec, WIRS<WRec>, WIRSQuery<WRec>, LayoutPolicy::TEIRING, DeletePolicy::TAGGING> DE; +typedef Rec R; +typedef DynamicExtension<R, ISAMTree<R>, rq::Query<R, ISAMTree<R>>, LayoutPolicy::TEIRING, DeletePolicy::TAGGING, SerialScheduler> DE; -#include "dynamic_extension_tests.inc" +#include "include/dynamic_extension.h" + + +Suite *unit_testing() +{ + Suite *unit = suite_create("DynamicExtension: Tagged Tiering Testing"); + inject_dynamic_extension_tests(unit); + + return unit; +} + + +int shard_unit_tests() +{ + int failed = 0; + Suite *unit = unit_testing(); + SRunner *unit_shardner = srunner_create(unit); + + srunner_run_all(unit_shardner, CK_NORMAL); + failed = srunner_ntests_failed(unit_shardner); + srunner_free(unit_shardner); + + return failed; +} + + +int main() +{ + int unit_failed = shard_unit_tests(); + + return (unit_failed == 0) ? EXIT_SUCCESS : EXIT_FAILURE; +} diff --git a/tests/de_tier_tomb.cpp b/tests/de_tier_tomb.cpp index 82942fd..b1387bb 100644 --- a/tests/de_tier_tomb.cpp +++ b/tests/de_tier_tomb.cpp @@ -1,25 +1,59 @@ /* - * tests/dynamic_extension_tests.cpp + * tests/de_tier_tomb.cpp * * Unit tests for Dynamic Extension Framework * * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> * Dong Xie <dongx@psu.edu> * - * All rights reserved. Published under the Modified BSD License. + * Distributed under the Modified BSD License. * */ #include <set> #include <random> #include <algorithm> -#include "testing.h" +#include "include/testing.h" #include "framework/DynamicExtension.h" -#include "shard/WIRS.h" +#include "shard/ISAMTree.h" +#include "shard/TrieSpline.h" +#include "query/rangequery.h" #include <check.h> using namespace de; -typedef DynamicExtension<WRec, WIRS<WRec>, WIRSQuery<WRec>, LayoutPolicy::TEIRING, DeletePolicy::TOMBSTONE> DE; +typedef Rec R; +typedef DynamicExtension<Rec, ISAMTree<R>, rq::Query<R, ISAMTree<R>>, LayoutPolicy::TEIRING, DeletePolicy::TOMBSTONE, SerialScheduler> DE; -#include "dynamic_extension_tests.inc" +#include "include/dynamic_extension.h" + + +Suite *unit_testing() +{ + Suite *unit = suite_create("DynamicExtension: Tombstone Tiering Testing"); + inject_dynamic_extension_tests(unit); + + return unit; +} + + +int shard_unit_tests() +{ + int failed = 0; + Suite *unit = unit_testing(); + SRunner *unit_shardner = srunner_create(unit); + + srunner_run_all(unit_shardner, CK_NORMAL); + failed = srunner_ntests_failed(unit_shardner); + srunner_free(unit_shardner); + + return failed; +} + + +int main() +{ + int unit_failed = shard_unit_tests(); + + return (unit_failed == 0) ? EXIT_SUCCESS : EXIT_FAILURE; +} diff --git a/tests/dynamic_extension_tests.inc b/tests/dynamic_extension_tests.inc deleted file mode 100644 index b9866c3..0000000 --- a/tests/dynamic_extension_tests.inc +++ /dev/null @@ -1,425 +0,0 @@ -/* - * tests/dynamic_extension_tests.cpp - * - * Unit tests for Dynamic Extension Framework - * - * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> - * Dong Xie <dongx@psu.edu> - * - * All rights reserved. Published under the Modified BSD License. - * - */ - -START_TEST(t_create) -{ - auto ext_wirs = new DE(100, 2, 1); - - - ck_assert_ptr_nonnull(ext_wirs); - ck_assert_int_eq(ext_wirs->get_record_count(), 0); - ck_assert_int_eq(ext_wirs->get_height(), 0); - - delete ext_wirs; -} -END_TEST - - -START_TEST(t_insert) -{ - auto ext_wirs = new DE(100, 2, 1); - - uint64_t key = 0; - uint32_t val = 0; - for (size_t i=0; i<100; i++) { - WRec r = {key, val, 1}; - ck_assert_int_eq(ext_wirs->insert(r), 1); - key++; - val++; - } - - ck_assert_int_eq(ext_wirs->get_height(), 0); - ck_assert_int_eq(ext_wirs->get_record_count(), 100); - - delete ext_wirs; -} -END_TEST - - -START_TEST(t_insert_with_mem_merges) -{ - auto ext_wirs = new DE(100, 2, 1); - - uint64_t key = 0; - uint32_t val = 0; - for (size_t i=0; i<300; i++) { - WRec r = {key, val, 1}; - ck_assert_int_eq(ext_wirs->insert(r), 1); - key++; - val++; - } - - ck_assert_int_eq(ext_wirs->get_record_count(), 300); - ck_assert_int_eq(ext_wirs->get_height(), 1); - - delete ext_wirs; -} -END_TEST - - -/* -START_TEST(t_range_sample_memtable) -{ - auto ext_wirs = new DE(100, 2, 1); - - uint64_t key = 0; - uint32_t val = 0; - for (size_t i=0; i<100; i++) { - WRec r = {key, val, 1}; - ck_assert_int_eq(ext_wirs->insert(r), 1); - key++; - val++; - } - - uint64_t lower_bound = 20; - uint64_t upper_bound = 50; - - char *buf = (char *) std::aligned_alloc(SECTOR_SIZE, PAGE_SIZE); - char *util_buf = (char *) std::aligned_alloc(SECTOR_SIZE, PAGE_SIZE); - WRec sample_set[100]; - - ext_wirs->range_sample(sample_set, lower_bound, upper_bound, 100); - - for(size_t i=0; i<100; i++) { - ck_assert_int_le(sample_set[i].key, upper_bound); - ck_assert_int_ge(sample_set[i].key, lower_bound); - } - - free(buf); - free(util_buf); - - delete ext_wirs; -} -END_TEST - - -START_TEST(t_range_sample_memlevels) -{ - auto ext_wirs = new DE(100, 2, 1); - - uint64_t key = 0; - uint32_t val = 0; - for (size_t i=0; i<300; i++) { - WRec r = {key, val, 1}; - ck_assert_int_eq(ext_wirs->insert(r), 1); - key++; - val++; - } - - uint64_t lower_bound = 100; - uint64_t upper_bound = 250; - - char *buf = (char *) std::aligned_alloc(SECTOR_SIZE, PAGE_SIZE); - char *util_buf = (char *) std::aligned_alloc(SECTOR_SIZE, PAGE_SIZE); - - WRec sample_set[100]; - ext_wirs->range_sample(sample_set, lower_bound, upper_bound, 100); - - for(size_t i=0; i<100; i++) { - ck_assert_int_le(sample_set[i].key, upper_bound); - ck_assert_int_ge(sample_set[i].key, lower_bound); - } - - free(buf); - free(util_buf); - - delete ext_wirs; -} -END_TEST -*/ - -START_TEST(t_range_sample_weighted) -{ - auto ext_wirs = new DE(100, 2, 1); - size_t n = 10000; - - std::vector<uint64_t> keys; - - uint64_t key = 1; - for (size_t i=0; i< n / 2; i++) { - keys.push_back(key); - } - - // put in a quarter of the count with weight two. - key = 2; - for (size_t i=0; i< n / 4; i++) { - keys.push_back(key); - } - - // the remaining quarter with weight four. - key = 3; - for (size_t i=0; i< n / 4; i++) { - keys.push_back(key); - } - - std::random_device rd; - std::mt19937 gen{rd()}; - std::shuffle(keys.begin(), keys.end(), gen); - - for (size_t i=0; i<keys.size(); i++) { - uint64_t weight; - if (keys[i] == 1) { - weight = 2; - } else if (keys[i] == 2) { - weight = 4; - } else { - weight = 8; - } - - WRec r = {keys[i], (uint32_t) i, weight}; - ext_wirs->insert(r); - } - size_t k = 1000; - uint64_t lower_key = 0; - uint64_t upper_key = 5; - - size_t cnt[3] = {0}; - size_t total_samples = 0; - - wirs_query_parms<WRec> p; - p.lower_bound = lower_key; - p.upper_bound = upper_key; - p.sample_size = k; - p.rng = gsl_rng_alloc(gsl_rng_mt19937); - - for (size_t i=0; i<1000; i++) { - - auto result = ext_wirs->query(&p); - total_samples += result.size(); - - for (size_t j=0; j<result.size(); j++) { - cnt[result[j].key - 1]++; - } - } - - ck_assert(roughly_equal(cnt[0], (double) total_samples/4.0, total_samples, .03)); - ck_assert(roughly_equal(cnt[1], (double) total_samples/4.0, total_samples, .03)); - ck_assert(roughly_equal(cnt[2], (double) total_samples/2.0, total_samples, .03)); - - gsl_rng_free(p.rng); - delete ext_wirs; -} -END_TEST - - -START_TEST(t_tombstone_merging_01) -{ - size_t reccnt = 100000; - auto ext_wirs = new DE(100, 2, .01); - - auto rng = gsl_rng_alloc(gsl_rng_mt19937); - - std::set<std::pair<uint64_t, uint32_t>> records; - std::set<std::pair<uint64_t, uint32_t>> to_delete; - std::set<std::pair<uint64_t, uint32_t>> deleted; - - while (records.size() < reccnt) { - uint64_t key = rand(); - uint32_t val = rand(); - - if (records.find({key, val}) != records.end()) continue; - - records.insert({key, val}); - } - - size_t deletes = 0; - size_t cnt=0; - for (auto rec : records) { - WRec r = {rec.first, rec.second, 1}; - ck_assert_int_eq(ext_wirs->insert(r), 1); - - if (gsl_rng_uniform(rng) < 0.05 && !to_delete.empty()) { - std::vector<std::pair<uint64_t, uint32_t>> del_vec; - std::sample(to_delete.begin(), to_delete.end(), std::back_inserter(del_vec), 3, std::mt19937{std::random_device{}()}); - - for (size_t i=0; i<del_vec.size(); i++) { - WRec dr = {del_vec[i].first, del_vec[i].second, 1}; - ext_wirs->erase(dr); - deletes++; - to_delete.erase(del_vec[i]); - deleted.insert(del_vec[i]); - } - } - - if (gsl_rng_uniform(rng) < 0.25 && deleted.find(rec) == deleted.end()) { - to_delete.insert(rec); - } - - ck_assert(ext_wirs->validate_tombstone_proportion()); - } - - ck_assert(ext_wirs->validate_tombstone_proportion()); - - gsl_rng_free(rng); - delete ext_wirs; -} -END_TEST - -DE *create_test_tree(size_t reccnt, size_t memlevel_cnt) { - auto rng = gsl_rng_alloc(gsl_rng_mt19937); - - auto ext_wirs = new DE(1000, 2, 1); - - std::set<WRec> records; - std::set<WRec> to_delete; - std::set<WRec> deleted; - - while (records.size() < reccnt) { - uint64_t key = rand(); - uint32_t val = rand(); - - if (records.find({key, val}) != records.end()) continue; - - records.insert({key, val}); - } - - size_t deletes = 0; - for (auto rec : records) { - ck_assert_int_eq(ext_wirs->insert(rec), 1); - - if (gsl_rng_uniform(rng) < 0.05 && !to_delete.empty()) { - std::vector<WRec> del_vec; - std::sample(to_delete.begin(), to_delete.end(), std::back_inserter(del_vec), 3, std::mt19937{std::random_device{}()}); - - for (size_t i=0; i<del_vec.size(); i++) { - ext_wirs->erase(del_vec[i]); - deletes++; - to_delete.erase(del_vec[i]); - deleted.insert(del_vec[i]); - } - } - - if (gsl_rng_uniform(rng) < 0.25 && deleted.find(rec) == deleted.end()) { - to_delete.insert(rec); - } - } - - gsl_rng_free(rng); - - return ext_wirs; -} - -START_TEST(t_static_structure) -{ - auto rng = gsl_rng_alloc(gsl_rng_mt19937); - - size_t reccnt = 100000; - auto ext_wirs = new DE(100, 2, 1); - - std::set<WRec> records; - std::set<WRec> to_delete; - std::set<WRec> deleted; - - while (records.size() < reccnt) { - uint64_t key = rand(); - uint32_t val = rand(); - - if (records.find({key, val}) != records.end()) continue; - - records.insert({key, val, 1}); - } - - size_t deletes = 0; - for (auto rec : records) { - ck_assert_int_eq(ext_wirs->insert(rec), 1); - - if (gsl_rng_uniform(rng) < 0.05 && !to_delete.empty()) { - std::vector<WRec> del_vec; - std::sample(to_delete.begin(), to_delete.end(), std::back_inserter(del_vec), 3, std::mt19937{std::random_device{}()}); - - for (size_t i=0; i<del_vec.size(); i++) { - ck_assert_int_eq(ext_wirs->erase(del_vec[i]), 1); - - deletes++; - to_delete.erase(del_vec[i]); - deleted.insert(del_vec[i]); - } - } - - if (gsl_rng_uniform(rng) < 0.25 && deleted.find(rec) == deleted.end()) { - to_delete.insert(rec); - } - } - - auto flat = ext_wirs->create_static_structure(); - ck_assert_int_eq(flat->get_record_count(), reccnt - deletes); - - uint64_t prev_key = 0; - for (size_t i=0; i<flat->get_record_count(); i++) { - auto k = flat->get_record_at(i)->rec.key; - ck_assert_int_ge(k, prev_key); - prev_key = k; - } - - gsl_rng_free(rng); - delete flat; - delete ext_wirs; -} -END_TEST - - -Suite *unit_testing() -{ - Suite *unit = suite_create("de::DynamicExtension Unit Testing"); - - TCase *create = tcase_create("de::DynamicExtension::constructor Testing"); - tcase_add_test(create, t_create); - suite_add_tcase(unit, create); - - TCase *insert = tcase_create("de::DynamicExtension<WIRS>::insert Testing"); - tcase_add_test(insert, t_insert); - tcase_add_test(insert, t_insert_with_mem_merges); - suite_add_tcase(unit, insert); - - TCase *sampling = tcase_create("de::DynamicExtension<WIRS>::range_sample Testing"); - - tcase_add_test(sampling, t_range_sample_weighted); - suite_add_tcase(unit, sampling); - - /* - tcase_add_test(sampling, t_range_sample_memtable); - tcase_add_test(sampling, t_range_sample_memlevels); - */ - - TCase *ts = tcase_create("de::DynamicExtension::tombstone_compaction Testing"); - tcase_add_test(ts, t_tombstone_merging_01); - tcase_set_timeout(ts, 500); - suite_add_tcase(unit, ts); - - TCase *flat = tcase_create("de::DynamicExtension::create_static_structure Testing"); - tcase_add_test(flat, t_static_structure); - tcase_set_timeout(flat, 500); - suite_add_tcase(unit, flat); - - return unit; -} - -int run_unit_tests() -{ - int failed = 0; - Suite *unit = unit_testing(); - SRunner *unit_runner = srunner_create(unit); - - srunner_run_all(unit_runner, CK_NORMAL); - failed = srunner_ntests_failed(unit_runner); - srunner_free(unit_runner); - - return failed; -} - - -int main() -{ - int unit_failed = run_unit_tests(); - - return (unit_failed == 0) ? EXIT_SUCCESS : EXIT_FAILURE; -} diff --git a/tests/include/concurrent_extension.h b/tests/include/concurrent_extension.h new file mode 100644 index 0000000..0993fac --- /dev/null +++ b/tests/include/concurrent_extension.h @@ -0,0 +1,396 @@ +/* + * tests/include/dynamic_extension.h + * + * Standardized unit tests for DynamicExtension objects + * + * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> + * + * 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, Query, 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 "testing.h" +#include "framework/DynamicExtension.h" +#include "framework/scheduling/FIFOScheduler.h" +#include "shard/ISAMTree.h" +#include "query/rangequery.h" +#include <check.h> + +//using namespace de; +//typedef DynamicExtension<R, ISAMTree<R>, rq::Query<ISAMTree<R>, R>, LayoutPolicy::LEVELING, DeletePolicy::TOMBSTONE, FIFOScheduler> DE; +*/ + + +START_TEST(t_create) +{ + auto test_de = new DE(100, 1000, 2); + + ck_assert_ptr_nonnull(test_de); + ck_assert_int_eq(test_de->get_record_count(), 0); + ck_assert_int_eq(test_de->get_height(), 0); + + delete test_de; +} +END_TEST + + +START_TEST(t_insert) +{ + auto test_de = new DE(100, 1000, 2); + + uint64_t key = 0; + uint32_t val = 0; + for (size_t i=0; i<100; i++) { + R r = {key, val}; + ck_assert_int_eq(test_de->insert(r), 1); + key++; + val++; + } + + ck_assert_int_eq(test_de->get_height(), 0); + ck_assert_int_eq(test_de->get_record_count(), 100); + + delete test_de; +} +END_TEST + + +START_TEST(t_debug_insert) +{ + auto test_de = new DE(100, 1000, 2); + + uint64_t key = 0; + uint32_t val = 0; + for (size_t i=0; i<1000; i++) { + R r = {key, val}; + ck_assert_int_eq(test_de->insert(r), 1); + ck_assert_int_eq(test_de->get_record_count(), i+1); + key++; + val++; + } + + delete test_de; +} +END_TEST + + +START_TEST(t_insert_with_mem_merges) +{ + auto test_de = new DE(100, 1000, 2); + + uint64_t key = 0; + uint32_t val = 0; + + R r = {key, val}; + for (size_t i=0; i<1000; i++) { + ck_assert_int_eq(test_de->insert(r), 1); + r.key++; + r.value++; + } + + ck_assert_int_eq(test_de->get_record_count(), 1000); + + test_de->await_next_epoch(); + + ck_assert_int_eq(test_de->get_record_count(), 1000); + + /* + * verify that we can fill past the high water mark, potentially + * stalling to allow merges to finish as needed. + */ + size_t cnt = 0; + do { + if (test_de->insert(r)) { + r.key++; + r.value++; + cnt++; + ck_assert_int_eq(test_de->get_record_count(), cnt + 1000); + } else { + _mm_pause(); + } + } while (cnt < 100000); + + test_de->await_next_epoch(); + + ck_assert_int_eq(test_de->get_record_count(), 101000); + + delete test_de; +} +END_TEST + + +START_TEST(t_range_query) +{ + auto test_de = new DE(1000, 10000, 4); + size_t n = 10000000; + + std::vector<uint64_t> keys; + for (size_t i=0; i<n; i++) { + keys.push_back(i); + } + + std::random_device rd; + std::mt19937 gen{rd()}; + std::shuffle(keys.begin(), keys.end(), gen); + + size_t i=0; + while ( i < keys.size()) { + R r = {keys[i], (uint32_t) i}; + if (test_de->insert(r)) { + i++; + } else { + _mm_pause(); + } + } + + + test_de->await_next_epoch(); + + std::sort(keys.begin(), keys.end()); + + auto idx = rand() % (keys.size() - 250); + + uint64_t lower_key = keys[idx]; + uint64_t upper_key = keys[idx + 250]; + + rq::Parms<R> p; + p.lower_bound = lower_key; + p.upper_bound = upper_key; + + //fprintf(stderr, "query start\n"); + auto result = test_de->query(&p); + auto r = result.get(); + //fprintf(stderr, "query stop\n"); + std::sort(r.begin(), r.end()); + + ck_assert_int_eq(r.size(), 251); + + for (size_t i=0; i<r.size(); i++) { + ck_assert_int_eq(r[i].key, keys[idx + i]); + } + + delete test_de; +} +END_TEST + + +START_TEST(t_tombstone_merging_01) +{ + size_t reccnt = 100000; + auto test_de = new DE(100, 1000, 2); + + auto rng = gsl_rng_alloc(gsl_rng_mt19937); + + std::set<std::pair<uint64_t, uint32_t>> records; + std::set<std::pair<uint64_t, uint32_t>> to_delete; + std::set<std::pair<uint64_t, uint32_t>> deleted; + + while (records.size() < reccnt) { + uint64_t key = rand(); + uint32_t val = rand(); + + if (records.find({key, val}) != records.end()) continue; + + records.insert({key, val}); + } + + size_t deletes = 0; + size_t cnt=0; + for (auto rec : records) { + R r = {rec.first, rec.second}; + while (!test_de->insert(r)) { + _mm_pause(); + } + + if (gsl_rng_uniform(rng) < 0.05 && !to_delete.empty()) { + std::vector<std::pair<uint64_t, uint32_t>> del_vec; + std::sample(to_delete.begin(), to_delete.end(), std::back_inserter(del_vec), 3, std::mt19937{std::random_device{}()}); + + for (size_t i=0; i<del_vec.size(); i++) { + R dr = {del_vec[i].first, del_vec[i].second}; + while (!test_de->erase(dr)) { + _mm_pause(); + } + deletes++; + to_delete.erase(del_vec[i]); + deleted.insert(del_vec[i]); + } + } + + if (gsl_rng_uniform(rng) < 0.25 && deleted.find(rec) == deleted.end()) { + to_delete.insert(rec); + } + } + + test_de->await_next_epoch(); + + ck_assert(test_de->validate_tombstone_proportion()); + + gsl_rng_free(rng); + delete test_de; +} +END_TEST + +DE *create_test_tree(size_t reccnt, size_t memlevel_cnt) { + auto rng = gsl_rng_alloc(gsl_rng_mt19937); + + auto test_de = new DE(1000, 10000, 2); + + std::set<R> records; + std::set<R> to_delete; + std::set<R> deleted; + + while (records.size() < reccnt) { + uint64_t key = rand(); + uint32_t val = rand(); + + if (records.find({key, val}) != records.end()) continue; + + records.insert({key, val}); + } + + size_t deletes = 0; + for (auto rec : records) { + ck_assert_int_eq(test_de->insert(rec), 1); + + if (gsl_rng_uniform(rng) < 0.05 && !to_delete.empty()) { + std::vector<R> del_vec; + std::sample(to_delete.begin(), to_delete.end(), std::back_inserter(del_vec), 3, std::mt19937{std::random_device{}()}); + + for (size_t i=0; i<del_vec.size(); i++) { + test_de->erase(del_vec[i]); + deletes++; + to_delete.erase(del_vec[i]); + deleted.insert(del_vec[i]); + } + } + + if (gsl_rng_uniform(rng) < 0.25 && deleted.find(rec) == deleted.end()) { + to_delete.insert(rec); + } + } + + gsl_rng_free(rng); + + return test_de; +} + +START_TEST(t_static_structure) +{ + auto rng = gsl_rng_alloc(gsl_rng_mt19937); + + size_t reccnt = 100000; + auto test_de = new DE(100, 1000, 2); + + std::set<R> records; + std::set<R> to_delete; + std::set<R> deleted; + + while (records.size() < reccnt) { + uint64_t key = rand(); + uint32_t val = rand(); + + if (records.find({key, val}) != records.end()) continue; + + records.insert({key, val}); + } + + size_t deletes = 0; + size_t t_reccnt = 0; + size_t k=0; + for (auto rec : records) { + k++; + while (!test_de->insert(rec)) { + _mm_pause(); + } + t_reccnt++; + + if (gsl_rng_uniform(rng) < 0.05 && !to_delete.empty()) { + std::vector<R> del_vec; + std::sample(to_delete.begin(), to_delete.end(), std::back_inserter(del_vec), 3, std::mt19937{std::random_device{}()}); + + for (size_t i=0; i<del_vec.size(); i++) { + while (!test_de->erase(del_vec[i])) { + _mm_pause(); + } + + deletes++; + to_delete.erase(del_vec[i]); + deleted.insert(del_vec[i]); + } + } + + if (gsl_rng_uniform(rng) < 0.25 && deleted.find(rec) == deleted.end()) { + to_delete.insert(rec); + } + } + + + //fprintf(stderr, "Tombstones: %ld\tRords: %ld\n", test_de->get_tombstone_count(), test_de->get_record_count()); + //fprintf(stderr, "Inserts: %ld\tDeletes:%ld\tNet:%ld\n", reccnt, deletes, reccnt - deletes); + + auto flat = test_de->create_static_structure(true); + //fprintf(stderr, "Flat: Tombstones: %ld\tRords %ld\n", flat->get_tombstone_count(), flat->get_record_count()); + //ck_assert_int_eq(flat->get_record_count(), reccnt - deletes); + + uint64_t prev_key = 0; + for (size_t i=0; i<flat->get_record_count(); i++) { + auto k = flat->get_record_at(i)->rec.key; + if (flat->get_record_at(i)->is_tombstone()) { + fprintf(stderr, "%ld %ld %ld\n", flat->get_record_at(i-1)->rec.key, + flat->get_record_at(i)->rec.key, + flat->get_record_at(i+1)->rec.key); + } + // ck_assert(!flat->get_record_at(i)->is_tombstone()); + ck_assert_int_ge(k, prev_key); + prev_key = k; + } + + gsl_rng_free(rng); + delete flat; + delete test_de; +} +END_TEST + + +static void inject_dynamic_extension_tests(Suite *suite) { + TCase *create = tcase_create("de::DynamicExtension::constructor Testing"); + tcase_add_test(create, t_create); + suite_add_tcase(suite, create); + + TCase *insert = tcase_create("de::DynamicExtension::insert Testing"); + tcase_add_test(insert, t_insert); + tcase_add_test(insert, t_insert_with_mem_merges); + tcase_add_test(insert, t_debug_insert); + tcase_set_timeout(insert, 500); + suite_add_tcase(suite, insert); + + TCase *query = tcase_create("de::DynamicExtension::range_query Testing"); + tcase_add_test(query, t_range_query); + tcase_set_timeout(query, 500); + suite_add_tcase(suite, query); + + + TCase *ts = tcase_create("de::DynamicExtension::tombstone_compaction Testing"); + tcase_add_test(ts, t_tombstone_merging_01); + tcase_set_timeout(ts, 500); + suite_add_tcase(suite, ts); + + TCase *flat = tcase_create("de::DynamicExtension::create_static_structure Testing"); + tcase_add_test(flat, t_static_structure); + tcase_set_timeout(flat, 500); + suite_add_tcase(suite, flat); +} diff --git a/tests/include/dynamic_extension.h b/tests/include/dynamic_extension.h new file mode 100644 index 0000000..6e9b16c --- /dev/null +++ b/tests/include/dynamic_extension.h @@ -0,0 +1,343 @@ +/* + * tests/include/dynamic_extension.h + * + * Standardized unit tests for DynamicExtension objects + * + * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> + * + * 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, Query, 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 "testing.h" +#include "framework/DynamicExtension.h" +#include "framework/scheduling/SerialScheduler.h" +#include "shard/ISAMTree.h" +#include "query/rangequery.h" +#include <check.h> +using namespace de; +typedef DynamicExtension<R, ISAMTree<R>, rq::Query<ISAMTree<R>, R>, LayoutPolicy::TEIRING, DeletePolicy::TAGGING, SerialScheduler> DE; +*/ + + +START_TEST(t_create) +{ + auto test_de = new DE(100, 1000, 2); + + ck_assert_ptr_nonnull(test_de); + ck_assert_int_eq(test_de->get_record_count(), 0); + ck_assert_int_eq(test_de->get_height(), 0); + + delete test_de; +} +END_TEST + + +START_TEST(t_insert) +{ + auto test_de = new DE(100, 1000, 2); + + uint64_t key = 0; + uint32_t val = 0; + for (size_t i=0; i<100; i++) { + R r = {key, val}; + ck_assert_int_eq(test_de->insert(r), 1); + key++; + val++; + } + + ck_assert_int_eq(test_de->get_height(), 0); + ck_assert_int_eq(test_de->get_record_count(), 100); + + delete test_de; +} +END_TEST + + +START_TEST(t_debug_insert) +{ + auto test_de = new DE(100, 1000, 2); + + uint64_t key = 0; + uint32_t val = 0; + for (size_t i=0; i<1000; i++) { + R r = {key, val}; + ck_assert_int_eq(test_de->insert(r), 1); + ck_assert_int_eq(test_de->get_record_count(), i+1); + key++; + val++; + } + + delete test_de; +} +END_TEST + + +START_TEST(t_insert_with_mem_merges) +{ + auto test_de = new DE(100, 1000, 2); + + uint64_t key = 0; + uint32_t val = 0; + for (size_t i=0; i<300; i++) { + R r = {key, val}; + ck_assert_int_eq(test_de->insert(r), 1); + key++; + val++; + } + + test_de->await_next_epoch(); + + ck_assert_int_eq(test_de->get_record_count(), 300); + ck_assert_int_eq(test_de->get_height(), 1); + + delete test_de; +} +END_TEST + + +START_TEST(t_range_query) +{ + auto test_de = new DE(100, 1000, 2); + size_t n = 10000; + + std::vector<uint64_t> keys; + for (size_t i=0; i<n; i++) { + keys.push_back(rand() % 25000); + } + + std::random_device rd; + std::mt19937 gen{rd()}; + std::shuffle(keys.begin(), keys.end(), gen); + + for (size_t i=0; i<keys.size(); i++) { + R r = {keys[i], (uint32_t) i}; + ck_assert_int_eq(test_de->insert(r), 1); + } + + test_de->await_next_epoch(); + + std::sort(keys.begin(), keys.end()); + + auto idx = rand() % (keys.size() - 250); + + uint64_t lower_key = keys[idx]; + uint64_t upper_key = keys[idx + 250]; + + rq::Parms<R> p; + p.lower_bound = lower_key; + p.upper_bound = upper_key; + + auto result = test_de->query(&p); + auto r = result.get(); + std::sort(r.begin(), r.end()); + ck_assert_int_eq(r.size(), 251); + + for (size_t i=0; i<r.size(); i++) { + ck_assert_int_eq(r[i].key, keys[idx + i]); + } + + delete test_de; +} +END_TEST + + +START_TEST(t_tombstone_merging_01) +{ + size_t reccnt = 100000; + auto test_de = new DE(100, 1000, 2); + + auto rng = gsl_rng_alloc(gsl_rng_mt19937); + + std::set<std::pair<uint64_t, uint32_t>> records; + std::set<std::pair<uint64_t, uint32_t>> to_delete; + std::set<std::pair<uint64_t, uint32_t>> deleted; + + while (records.size() < reccnt) { + uint64_t key = rand(); + uint32_t val = rand(); + + if (records.find({key, val}) != records.end()) continue; + + records.insert({key, val}); + } + + size_t deletes = 0; + size_t cnt=0; + for (auto rec : records) { + R r = {rec.first, rec.second}; + ck_assert_int_eq(test_de->insert(r), 1); + + if (gsl_rng_uniform(rng) < 0.05 && !to_delete.empty()) { + std::vector<std::pair<uint64_t, uint32_t>> del_vec; + std::sample(to_delete.begin(), to_delete.end(), std::back_inserter(del_vec), 3, std::mt19937{std::random_device{}()}); + + for (size_t i=0; i<del_vec.size(); i++) { + R dr = {del_vec[i].first, del_vec[i].second}; + test_de->erase(dr); + deletes++; + to_delete.erase(del_vec[i]); + deleted.insert(del_vec[i]); + } + } + + if (gsl_rng_uniform(rng) < 0.25 && deleted.find(rec) == deleted.end()) { + to_delete.insert(rec); + } + } + + test_de->await_next_epoch(); + + ck_assert(test_de->validate_tombstone_proportion()); + + gsl_rng_free(rng); + delete test_de; +} +END_TEST + +DE *create_test_tree(size_t reccnt, size_t memlevel_cnt) { + auto rng = gsl_rng_alloc(gsl_rng_mt19937); + + auto test_de = new DE(1000, 10000, 2); + + std::set<R> records; + std::set<R> to_delete; + std::set<R> deleted; + + while (records.size() < reccnt) { + uint64_t key = rand(); + uint32_t val = rand(); + + if (records.find({key, val}) != records.end()) continue; + + records.insert({key, val}); + } + + size_t deletes = 0; + for (auto rec : records) { + ck_assert_int_eq(test_de->insert(rec), 1); + + if (gsl_rng_uniform(rng) < 0.05 && !to_delete.empty()) { + std::vector<R> del_vec; + std::sample(to_delete.begin(), to_delete.end(), std::back_inserter(del_vec), 3, std::mt19937{std::random_device{}()}); + + for (size_t i=0; i<del_vec.size(); i++) { + test_de->erase(del_vec[i]); + deletes++; + to_delete.erase(del_vec[i]); + deleted.insert(del_vec[i]); + } + } + + if (gsl_rng_uniform(rng) < 0.25 && deleted.find(rec) == deleted.end()) { + to_delete.insert(rec); + } + } + + gsl_rng_free(rng); + + return test_de; +} + +START_TEST(t_static_structure) +{ + auto rng = gsl_rng_alloc(gsl_rng_mt19937); + + size_t reccnt = 100000; + auto test_de = new DE(100, 1000, 2); + + std::set<R> records; + std::set<R> to_delete; + std::set<R> deleted; + + while (records.size() < reccnt) { + uint64_t key = rand(); + uint32_t val = rand(); + + if (records.find({key, val}) != records.end()) continue; + + records.insert({key, val}); + } + + size_t deletes = 0; + size_t t_reccnt = 0; + size_t k=0; + for (auto rec : records) { + k++; + ck_assert_int_eq(test_de->insert(rec), 1); + t_reccnt++; + + if (gsl_rng_uniform(rng) < 0.05 && !to_delete.empty()) { + std::vector<R> del_vec; + std::sample(to_delete.begin(), to_delete.end(), std::back_inserter(del_vec), 3, std::mt19937{std::random_device{}()}); + + for (size_t i=0; i<del_vec.size(); i++) { + ck_assert_int_eq(test_de->erase(del_vec[i]), 1); + + deletes++; + to_delete.erase(del_vec[i]); + deleted.insert(del_vec[i]); + } + } + + if (gsl_rng_uniform(rng) < 0.25 && deleted.find(rec) == deleted.end()) { + to_delete.insert(rec); + } + } + + auto flat = test_de->create_static_structure(); + ck_assert_int_eq(flat->get_record_count(), reccnt - deletes); + + uint64_t prev_key = 0; + for (size_t i=0; i<flat->get_record_count(); i++) { + auto k = flat->get_record_at(i)->rec.key; + ck_assert_int_ge(k, prev_key); + prev_key = k; + } + + gsl_rng_free(rng); + delete flat; + delete test_de; +} +END_TEST + + +static void inject_dynamic_extension_tests(Suite *suite) { + TCase *create = tcase_create("de::DynamicExtension::constructor Testing"); + tcase_add_test(create, t_create); + suite_add_tcase(suite, create); + + TCase *insert = tcase_create("de::DynamicExtension::insert Testing"); + tcase_add_test(insert, t_insert); + tcase_add_test(insert, t_insert_with_mem_merges); + tcase_add_test(insert, t_debug_insert); + suite_add_tcase(suite, insert); + + TCase *query = tcase_create("de::DynamicExtension::range_query Testing"); + tcase_add_test(query, t_range_query); + suite_add_tcase(suite, query); + + TCase *ts = tcase_create("de::DynamicExtension::tombstone_compaction Testing"); + tcase_add_test(ts, t_tombstone_merging_01); + tcase_set_timeout(ts, 500); + suite_add_tcase(suite, ts); + + TCase *flat = tcase_create("de::DynamicExtension::create_static_structure Testing"); + tcase_add_test(flat, t_static_structure); + tcase_set_timeout(flat, 500); + suite_add_tcase(suite, flat); +} diff --git a/tests/include/rangecount.h b/tests/include/rangecount.h new file mode 100644 index 0000000..fdd66d9 --- /dev/null +++ b/tests/include/rangecount.h @@ -0,0 +1,162 @@ +/* + * tests/include/rangecount.h + * + * Standardized unit tests for range queries against supporting + * shard types + * + * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> + * + * 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 and Shard needs to support lower_bound. + * For other types of record and shard, 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/ISAMTree.h" +//#include "query/rangecount.h" +//#include "testing.h" +//#include <check.h> +//using namespace de; +//typedef ISAMTree<R> Shard; + + +#include "query/rangecount.h" + +START_TEST(t_range_count) +{ + + auto buffer = create_sequential_mbuffer<R>(100, 1000); + auto shard = Shard(buffer->get_buffer_view()); + + rc::Parms<R> parms; + parms.lower_bound = 300; + parms.upper_bound = 500; + + auto state = rc::Query<R, Shard>::get_query_state(&shard, &parms); + auto result = rc::Query<R, Shard>::query(&shard, state, &parms); + rc::Query<R, Shard>::delete_query_state(state); + + ck_assert_int_eq(result.size(), 1); + ck_assert_int_eq(result[0].rec.key, parms.upper_bound - parms.lower_bound + 1); + + delete buffer; +} +END_TEST + + +START_TEST(t_buffer_range_count) +{ + auto buffer = create_sequential_mbuffer<R>(100, 1000); + + rc::Parms<R> parms; + parms.lower_bound = 300; + parms.upper_bound = 500; + + { + auto view = buffer->get_buffer_view(); + auto state = rc::Query<R, Shard>::get_buffer_query_state(&view, &parms); + auto result = rc::Query<R, Shard>::buffer_query(state, &parms); + rc::Query<R, Shard>::delete_buffer_query_state(state); + + ck_assert_int_eq(result.size(), 1); + ck_assert_int_eq(result[0].rec.key, parms.upper_bound - parms.lower_bound + 1); + } + + delete buffer; +} +END_TEST + + +START_TEST(t_range_count_merge) +{ + auto buffer1 = create_sequential_mbuffer<R>(100, 200); + auto buffer2 = create_sequential_mbuffer<R>(400, 1000); + + auto shard1 = Shard(buffer1->get_buffer_view()); + auto shard2 = Shard(buffer2->get_buffer_view()); + + rc::Parms<R> parms; + parms.lower_bound = 150; + parms.upper_bound = 500; + + size_t result_size = parms.upper_bound - parms.lower_bound + 1 - 200; + + auto state1 = rc::Query<R, Shard>::get_query_state(&shard1, &parms); + auto state2 = rc::Query<R, Shard>::get_query_state(&shard2, &parms); + + std::vector<std::vector<de::Wrapped<R>>> results(2); + results[0] = rc::Query<R, Shard>::query(&shard1, state1, &parms); + results[1] = rc::Query<R, Shard>::query(&shard2, state2, &parms); + + rc::Query<R, Shard>::delete_query_state(state1); + rc::Query<R, Shard>::delete_query_state(state2); + + ck_assert_int_eq(results[0].size(), 1); + ck_assert_int_eq(results[1].size(), 1); + + auto result = rc::Query<R, Shard>::merge(results, nullptr); + + ck_assert_int_eq(result[0].key, result_size); + + delete buffer1; + delete buffer2; +} +END_TEST + + +START_TEST(t_lower_bound) +{ + auto buffer1 = create_sequential_mbuffer<R>(100, 200); + auto buffer2 = create_sequential_mbuffer<R>(400, 1000); + + auto shard1 = new Shard(buffer1->get_buffer_view()); + auto shard2 = new Shard(buffer2->get_buffer_view()); + + std::vector<Shard*> shards = {shard1, shard2}; + + auto merged = Shard(shards); + + for (size_t i=100; i<1000; i++) { + R r; + r.key = i; + r.value = i; + + auto idx = merged.get_lower_bound(i); + + assert(idx < merged.get_record_count()); + + auto res = merged.get_record_at(idx); + + if (i >=200 && i <400) { + ck_assert_int_lt(res->rec.key, i); + } else { + ck_assert_int_eq(res->rec.key, i); + } + } + + delete buffer1; + delete buffer2; + delete shard1; + delete shard2; +} +END_TEST + +static void inject_rangecount_tests(Suite *suite) { + TCase *range_count = tcase_create("Range Query Testing"); + tcase_add_test(range_count, t_range_count); + tcase_add_test(range_count, t_buffer_range_count); + tcase_add_test(range_count, t_range_count_merge); + suite_add_tcase(suite, range_count); +} diff --git a/tests/include/rangequery.h b/tests/include/rangequery.h new file mode 100644 index 0000000..a8a73f7 --- /dev/null +++ b/tests/include/rangequery.h @@ -0,0 +1,183 @@ +/* + * tests/include/rangequery.h + * + * Standardized unit tests for range queries against supporting + * shard types + * + * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> + * + * 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 and Shard needs to support lower_bound. + * For other types of record and shard, 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/ISAMTree.h" +//#include "query/rangequery.h" +//#include "testing.h" +//#include <check.h> +//using namespace de; +//typedef ISAMTree<R> Shard; + +#include "query/rangequery.h" + + +START_TEST(t_range_query) +{ + auto buffer = create_sequential_mbuffer<R>(100, 1000); + auto shard = Shard(buffer->get_buffer_view()); + + rq::Parms<R> parms; + parms.lower_bound = 300; + parms.upper_bound = 500; + + auto state = rq::Query<R, Shard>::get_query_state(&shard, &parms); + auto result = rq::Query<R, Shard>::query(&shard, state, &parms); + rq::Query<R, Shard>::delete_query_state(state); + + ck_assert_int_eq(result.size(), parms.upper_bound - parms.lower_bound + 1); + for (size_t i=0; i<result.size(); i++) { + ck_assert_int_le(result[i].rec.key, parms.upper_bound); + ck_assert_int_ge(result[i].rec.key, parms.lower_bound); + } + + delete buffer; +} +END_TEST + + +START_TEST(t_buffer_range_query) +{ + auto buffer = create_sequential_mbuffer<R>(100, 1000); + + rq::Parms<R> parms; + parms.lower_bound = 300; + parms.upper_bound = 500; + + { + auto view = buffer->get_buffer_view(); + auto state = rq::Query<R, Shard>::get_buffer_query_state(&view, &parms); + auto result = rq::Query<R, Shard>::buffer_query(state, &parms); + rq::Query<R, Shard>::delete_buffer_query_state(state); + + ck_assert_int_eq(result.size(), parms.upper_bound - parms.lower_bound + 1); + for (size_t i=0; i<result.size(); i++) { + ck_assert_int_le(result[i].rec.key, parms.upper_bound); + ck_assert_int_ge(result[i].rec.key, parms.lower_bound); + } + } + + delete buffer; +} +END_TEST + + +START_TEST(t_range_query_merge) +{ + auto buffer1 = create_sequential_mbuffer<R>(100, 200); + auto buffer2 = create_sequential_mbuffer<R>(400, 1000); + + auto shard1 = Shard(buffer1->get_buffer_view()); + auto shard2 = Shard(buffer2->get_buffer_view()); + + rq::Parms<R> parms; + parms.lower_bound = 150; + parms.upper_bound = 500; + + size_t result_size = parms.upper_bound - parms.lower_bound + 1 - 200; + + auto state1 = rq::Query<R, Shard>::get_query_state(&shard1, &parms); + auto state2 = rq::Query<R, Shard>::get_query_state(&shard2, &parms); + + std::vector<std::vector<de::Wrapped<R>>> results(2); + results[0] = rq::Query<R, Shard>::query(&shard1, state1, &parms); + results[1] = rq::Query<R, Shard>::query(&shard2, state2, &parms); + + rq::Query<R, Shard>::delete_query_state(state1); + rq::Query<R, Shard>::delete_query_state(state2); + + ck_assert_int_eq(results[0].size() + results[1].size(), result_size); + + std::vector<std::vector<Wrapped<R>>> proc_results; + + for (size_t j=0; j<results.size(); j++) { + proc_results.emplace_back(std::vector<Wrapped<R>>()); + for (size_t i=0; i<results[j].size(); i++) { + proc_results[j].emplace_back(results[j][i]); + } + } + + auto result = rq::Query<R, Shard>::merge(proc_results, nullptr); + std::sort(result.begin(), result.end()); + + ck_assert_int_eq(result.size(), result_size); + auto key = parms.lower_bound; + for (size_t i=0; i<result.size(); i++) { + ck_assert_int_eq(key++, result[i].key); + if (key == 200) { + key = 400; + } + } + + delete buffer1; + delete buffer2; +} +END_TEST + + +START_TEST(t_lower_bound) +{ + auto buffer1 = create_sequential_mbuffer<R>(100, 200); + auto buffer2 = create_sequential_mbuffer<R>(400, 1000); + + auto shard1 = new Shard(buffer1->get_buffer_view()); + auto shard2 = new Shard(buffer2->get_buffer_view()); + + std::vector<Shard*> shards = {shard1, shard2}; + + auto merged = Shard(shards); + + for (size_t i=100; i<1000; i++) { + R r; + r.key = i; + r.value = i; + + auto idx = merged.get_lower_bound(i); + + assert(idx < merged.get_record_count()); + + auto res = merged.get_record_at(idx); + + if (i >=200 && i <400) { + ck_assert_int_lt(res->rec.key, i); + } else { + ck_assert_int_eq(res->rec.key, i); + } + } + + delete buffer1; + delete buffer2; + delete shard1; + delete shard2; +} +END_TEST + +static void inject_rangequery_tests(Suite *suite) { + TCase *range_query = tcase_create("Range Query Testing"); + tcase_add_test(range_query, t_range_query); + tcase_add_test(range_query, t_buffer_range_query); + tcase_add_test(range_query, t_range_query_merge); + suite_add_tcase(suite, range_query); +} diff --git a/tests/include/shard_standard.h b/tests/include/shard_standard.h new file mode 100644 index 0000000..7d17dcb --- /dev/null +++ b/tests/include/shard_standard.h @@ -0,0 +1,202 @@ +/* + * tests/include/shard_standard.h + * + * Standardized unit tests for Shard objects + * + * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> + * + * 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/ISAMTree.h" +#include "shard/ISAMTree.h" +#include "testing.h" +#include <check.h> +using namespace de; +typedef Rec R; +typedef ISAMTree<R> Shard; +*/ + +START_TEST(t_mbuffer_init) +{ + auto buffer = new MutableBuffer<R>(512, 1024); + for (uint64_t i = 512; i > 0; i--) { + uint32_t v = i; + buffer->append({i, v, 1}); + } + + for (uint64_t i = 1; i <= 256; ++i) { + uint32_t v = i; + buffer->append({i, v, 1}, true); + } + + for (uint64_t i = 257; i <= 512; ++i) { + uint32_t v = i + 1; + buffer->append({i, v, 1}); + } + + 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<R>(n); + auto mbuffer2 = create_test_mbuffer<R>(n); + auto mbuffer3 = create_test_mbuffer<R>(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<Shard*> 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_full_cancelation) +{ + size_t n = 100; + auto buffer = create_double_seq_mbuffer<R>(n, false); + auto buffer_ts = create_double_seq_mbuffer<R>(n, true); + + Shard* shard = new Shard(buffer->get_buffer_view()); + Shard* shard_ts = new Shard(buffer_ts->get_buffer_view()); + + ck_assert_int_eq(shard->get_record_count(), n); + ck_assert_int_eq(shard->get_tombstone_count(), 0); + ck_assert_int_eq(shard_ts->get_record_count(), n); + ck_assert_int_eq(shard_ts->get_tombstone_count(), n); + + std::vector<Shard *> shards = {shard, shard_ts}; + + Shard* merged = new Shard(shards); + + ck_assert_int_eq(merged->get_tombstone_count(), 0); + ck_assert_int_eq(merged->get_record_count(), 0); + + delete buffer; + delete buffer_ts; + delete shard; + delete shard_ts; + delete merged; +} +END_TEST + + +START_TEST(t_point_lookup) +{ + size_t n = 10000; + + auto buffer = create_double_seq_mbuffer<R>(n, false); + auto isam = Shard(buffer->get_buffer_view()); + + { + auto view = buffer->get_buffer_view(); + + for (size_t i=0; i<n; i++) { + R r; + auto rec = view.get(i); + r.key = rec->rec.key; + r.value = rec->rec.value; + + auto result = isam.point_lookup(r); + ck_assert_ptr_nonnull(result); + ck_assert_int_eq(result->rec.key, r.key); + ck_assert_int_eq(result->rec.value, r.value); + } + } + + delete buffer; +} +END_TEST + + +START_TEST(t_point_lookup_miss) +{ + size_t n = 10000; + + auto buffer = create_double_seq_mbuffer<R>(n, false); + auto isam = Shard(buffer->get_buffer_view()); + + for (size_t i=n + 100; i<2*n; i++) { + R r; + r.key = i; + r.value = i; + + auto result = isam.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 *tombstone = tcase_create("Shard tombstone cancellation Testing"); + tcase_add_test(tombstone, t_full_cancelation); + suite_add_tcase(suite, tombstone); + 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); +} diff --git a/tests/testing.h b/tests/include/testing.h index bdf4869..f935b53 100644 --- a/tests/testing.h +++ b/tests/include/testing.h @@ -6,7 +6,7 @@ * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> * Dong Xie <dongx@psu.edu> * - * All rights reserved. Published under the Modified BSD License. + * Distributed under the Modified BSD License. * */ #pragma once @@ -18,12 +18,12 @@ #include "util/types.h" #include "psu-util/alignment.h" -#include "framework/MutableBuffer.h" -#include "framework/RecordInterface.h" +#include "framework/structure/MutableBuffer.h" +#include "framework/interface/Record.h" typedef de::WeightedRecord<uint64_t, uint32_t, uint64_t> WRec; typedef de::Record<uint64_t, uint32_t> Rec; -typedef de::EuclidPoint<int64_t> PRec; +typedef de::EuclidPoint<uint64_t> PRec; template <de::RecordInterface R> std::vector<R> strip_wrapping(std::vector<de::Wrapped<R>> vec) { @@ -76,55 +76,48 @@ static bool roughly_equal(int n1, int n2, size_t mag, double epsilon) { return ((double) std::abs(n1 - n2) / (double) mag) < epsilon; } -static de::MutableBuffer<PRec> *create_2d_mbuffer(size_t cnt) { - auto buffer = new de::MutableBuffer<PRec>(cnt, cnt); - - for (int64_t i=0; i<cnt; i++) { - buffer->append({rand(), rand()}); - } - - return buffer; -} - -static de::MutableBuffer<PRec> *create_2d_sequential_mbuffer(size_t cnt) { - auto buffer = new de::MutableBuffer<PRec>(cnt, cnt); - for (int64_t i=0; i<cnt; i++) { - buffer->append({i, i}); - } - - return buffer; -} - -template <de::KVPInterface R> +template <de::RecordInterface R> static de::MutableBuffer<R> *create_test_mbuffer(size_t cnt) { - auto buffer = new de::MutableBuffer<R>(cnt, cnt); + auto buffer = new de::MutableBuffer<R>(cnt/2, cnt); R rec; - for (size_t i = 0; i < cnt; i++) { - rec.key = rand(); - rec.value = rand(); + if constexpr (de::KVPInterface<R>) { + for (size_t i = 0; i < cnt; i++) { + rec.key = rand(); + rec.value = rand(); - if constexpr (de::WeightedRecordInterface<R>) { - rec.weight = 1; - } + if constexpr (de::WeightedRecordInterface<R>) { + rec.weight = 1; + } - buffer->append(rec); - } + buffer->append(rec); + } + } else if constexpr (de::NDRecordInterface<R>) { + for (size_t i=0; i<cnt; i++) { + uint64_t a = rand(); + uint64_t b = rand(); + buffer->append({a, b}); + } + } return buffer; } -template <de::KVPInterface R> -static de::MutableBuffer<R> *create_sequential_mbuffer(decltype(R::key) start, decltype(R::key) stop) +template <de::RecordInterface R> +static de::MutableBuffer<R> *create_sequential_mbuffer(size_t start, size_t stop) { size_t cnt = stop - start; - auto buffer = new de::MutableBuffer<R>(cnt, cnt); + auto buffer = new de::MutableBuffer<R>(cnt/2, cnt); for (size_t i=start; i<stop; i++) { R rec; - rec.key = i; - rec.value = i; + if constexpr (de::KVPInterface<R>) { + rec.key = i; + rec.value = i; + } else if constexpr (de::NDRecordInterface<R>) { + rec = {i, i}; + } if constexpr (de::WeightedRecordInterface<R>) { rec.weight = 1; @@ -139,7 +132,7 @@ static de::MutableBuffer<R> *create_sequential_mbuffer(decltype(R::key) start, d template <de::KVPInterface R> static de::MutableBuffer<R> *create_test_mbuffer_tombstones(size_t cnt, size_t ts_cnt) { - auto buffer = new de::MutableBuffer<R>(cnt, ts_cnt); + auto buffer = new de::MutableBuffer<R>(cnt/2, cnt); std::vector<std::pair<uint64_t, uint32_t>> tombstones; @@ -171,7 +164,7 @@ template <typename R> requires de::WeightedRecordInterface<R> && de::KVPInterface<R> static de::MutableBuffer<R> *create_weighted_mbuffer(size_t cnt) { - auto buffer = new de::MutableBuffer<R>(cnt, cnt); + auto buffer = new de::MutableBuffer<R>(cnt/2, cnt); // Put in half of the count with weight one. for (uint32_t i=0; i< cnt / 2; i++) { @@ -194,7 +187,7 @@ static de::MutableBuffer<R> *create_weighted_mbuffer(size_t cnt) template <de::KVPInterface R> static de::MutableBuffer<R> *create_double_seq_mbuffer(size_t cnt, bool ts=false) { - auto buffer = new de::MutableBuffer<R>(cnt, cnt); + auto buffer = new de::MutableBuffer<R>(cnt/2, cnt); for (size_t i = 0; i < cnt / 2; i++) { R rec; diff --git a/tests/include/wirs.h b/tests/include/wirs.h new file mode 100644 index 0000000..90cd22d --- /dev/null +++ b/tests/include/wirs.h @@ -0,0 +1,181 @@ +/* + * tests/include/rangequery.h + * + * Standardized unit tests for range queries against supporting + * shard types + * + * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> + * + * 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 and Shard needs to support lower_bound. + * For other types of record and shard, 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/ISAMTree.h" +//#include "query/rangequery.h" +//#include "testing.h" +//#include <check.h> +//using namespace de; +//typedef ISAMTree<R> Shard; + + +START_TEST(t_range_query) +{ + auto buffer = create_sequential_mbuffer<R>(100, 1000); + auto shard = Shard(buffer->get_buffer_view()); + + rq::Parms<R> parms; + parms.lower_bound = 300; + parms.upper_bound = 500; + + auto state = rq::Query<R, Shard>::get_query_state(&shard, &parms); + auto result = rq::Query<R, Shard>::query(&shard, state, &parms); + rq::Query<R, Shard>::delete_query_state(state); + + ck_assert_int_eq(result.size(), parms.upper_bound - parms.lower_bound + 1); + for (size_t i=0; i<result.size(); i++) { + ck_assert_int_le(result[i].rec.key, parms.upper_bound); + ck_assert_int_ge(result[i].rec.key, parms.lower_bound); + } + + delete buffer; +} +END_TEST + + +START_TEST(t_buffer_range_query) +{ + auto buffer = create_sequential_mbuffer<R>(100, 1000); + + rq::Parms<R> parms; + parms.lower_bound = 300; + parms.upper_bound = 500; + + { + auto view = buffer->get_buffer_view(); + auto state = rq::Query<R, Shard>::get_buffer_query_state(&view, &parms); + auto result = rq::Query<R, Shard>::buffer_query(state, &parms); + rq::Query<R, Shard>::delete_buffer_query_state(state); + + ck_assert_int_eq(result.size(), parms.upper_bound - parms.lower_bound + 1); + for (size_t i=0; i<result.size(); i++) { + ck_assert_int_le(result[i].rec.key, parms.upper_bound); + ck_assert_int_ge(result[i].rec.key, parms.lower_bound); + } + } + + delete buffer; +} +END_TEST + + +START_TEST(t_range_query_merge) +{ + auto buffer1 = create_sequential_mbuffer<R>(100, 200); + auto buffer2 = create_sequential_mbuffer<R>(400, 1000); + + auto shard1 = Shard(buffer1->get_buffer_view()); + auto shard2 = Shard(buffer2->get_buffer_view()); + + rq::Parms<R> parms; + parms.lower_bound = 150; + parms.upper_bound = 500; + + size_t result_size = parms.upper_bound - parms.lower_bound + 1 - 200; + + auto state1 = rq::Query<R, Shard>::get_query_state(&shard1, &parms); + auto state2 = rq::Query<R, Shard>::get_query_state(&shard2, &parms); + + std::vector<std::vector<de::Wrapped<R>>> results(2); + results[0] = rq::Query<R, Shard>::query(&shard1, state1, &parms); + results[1] = rq::Query<R, Shard>::query(&shard2, state2, &parms); + + rq::Query<R, Shard>::delete_query_state(state1); + rq::Query<R, Shard>::delete_query_state(state2); + + ck_assert_int_eq(results[0].size() + results[1].size(), result_size); + + std::vector<std::vector<Wrapped<R>>> proc_results; + + for (size_t j=0; j<results.size(); j++) { + proc_results.emplace_back(std::vector<Wrapped<R>>()); + for (size_t i=0; i<results[j].size(); i++) { + proc_results[j].emplace_back(results[j][i]); + } + } + + auto result = rq::Query<R, Shard>::merge(proc_results, nullptr); + std::sort(result.begin(), result.end()); + + ck_assert_int_eq(result.size(), result_size); + auto key = parms.lower_bound; + for (size_t i=0; i<result.size(); i++) { + ck_assert_int_eq(key++, result[i].key); + if (key == 200) { + key = 400; + } + } + + delete buffer1; + delete buffer2; +} +END_TEST + + +START_TEST(t_lower_bound) +{ + auto buffer1 = create_sequential_mbuffer<R>(100, 200); + auto buffer2 = create_sequential_mbuffer<R>(400, 1000); + + auto shard1 = new Shard(buffer1->get_buffer_view()); + auto shard2 = new Shard(buffer2->get_buffer_view()); + + std::vector<Shard*> shards = {shard1, shard2}; + + auto merged = Shard(shards); + + for (size_t i=100; i<1000; i++) { + R r; + r.key = i; + r.value = i; + + auto idx = merged.get_lower_bound(i); + + assert(idx < merged.get_record_count()); + + auto res = merged.get_record_at(idx); + + if (i >=200 && i <400) { + ck_assert_int_lt(res->rec.key, i); + } else { + ck_assert_int_eq(res->rec.key, i); + } + } + + delete buffer1; + delete buffer2; + delete shard1; + delete shard2; +} +END_TEST + +static void inject_rangequery_tests(Suite *suite) { + TCase *range_query = tcase_create("Range Query Testing"); + tcase_add_test(range_query, t_range_query); + tcase_add_test(range_query, t_buffer_range_query); + tcase_add_test(range_query, t_range_query_merge); + suite_add_tcase(suite, range_query); +} diff --git a/tests/include/wss.h b/tests/include/wss.h new file mode 100644 index 0000000..f0ac74c --- /dev/null +++ b/tests/include/wss.h @@ -0,0 +1,144 @@ +/* + * tests/include/rangequery.h + * + * Standardized unit tests for range queries against supporting + * shard types + * + * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> + * + * 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 and Shard needs to support lower_bound. + * For other types of record and shard, 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/Alias.h" +#include "testing.h" +#include <check.h> +using namespace de; +typedef Alias<R> Shard; + +#include "query/wss.h" + +START_TEST(t_wss_query) +{ + auto buffer = create_weighted_mbuffer<R>(1000); + auto shard = Shard(buffer->get_buffer_view()); + + auto rng = gsl_rng_alloc(gsl_rng_mt19937); + + wss::Parms<R> parms; + parms.rng = rng; + parms.sample_size = 20; + + auto state = wss::Query<R, Shard>::get_query_state(&shard, &parms); + auto result = wss::Query<R, Shard>::query(&shard, state, &parms); + wss::Query<R, Shard>::delete_query_state(state); + + delete buffer; + gsl_rng_free(rng); +} +END_TEST + + +START_TEST(t_buffer_wss_query) +{ + auto buffer = create_weighted_mbuffer<R>(1000); + + + auto rng = gsl_rng_alloc(gsl_rng_mt19937); + + wss::Parms<R> parms; + parms.rng = rng; + + { + auto view = buffer->get_buffer_view(); + auto state = wss::Query<R, Shard>::get_buffer_query_state(&view, &parms); + auto result = wss::Query<R, Shard>::buffer_query(state, &parms); + wss::Query<R, Shard>::delete_buffer_query_state(state); + + ck_assert_int_eq(result.size(), parms.sample_size); + for (size_t i=0; i<result.size(); i++) { + + } + } + + delete buffer; +} +END_TEST + + +/* +START_TEST(t_range_query_merge) +{ + auto buffer1 = create_sequential_mbuffer<R>(100, 200); + auto buffer2 = create_sequential_mbuffer<R>(400, 1000); + + auto shard1 = Shard(buffer1->get_buffer_view()); + auto shard2 = Shard(buffer2->get_buffer_view()); + + wss::Parms<R> parms; + parms.lower_bound = 150; + parms.upper_bound = 500; + + size_t result_size = parms.upper_bound - parms.lower_bound + 1 - 200; + + auto state1 = wss::Query<R, Shard>::get_query_state(&shard1, &parms); + auto state2 = wss::Query<R, Shard>::get_query_state(&shard2, &parms); + + std::vector<std::vector<de::Wrapped<R>>> results(2); + results[0] = wss::Query<R, Shard>::query(&shard1, state1, &parms); + results[1] = wss::Query<R, Shard>::query(&shard2, state2, &parms); + + wss::Query<R, Shard>::delete_query_state(state1); + wss::Query<R, Shard>::delete_query_state(state2); + + ck_assert_int_eq(results[0].size() + results[1].size(), result_size); + + std::vector<std::vector<Wrapped<R>>> proc_results; + + for (size_t j=0; j<results.size(); j++) { + proc_results.emplace_back(std::vector<Wrapped<R>>()); + for (size_t i=0; i<results[j].size(); i++) { + proc_results[j].emplace_back(results[j][i]); + } + } + + auto result = wss::Query<R, Shard>::merge(proc_results, nullptr); + std::sort(result.begin(), result.end()); + + ck_assert_int_eq(result.size(), result_size); + auto key = parms.lower_bound; + for (size_t i=0; i<result.size(); i++) { + ck_assert_int_eq(key++, result[i].key); + if (key == 200) { + key = 400; + } + } + + delete buffer1; + delete buffer2; +} +END_TEST +*/ + + +static void inject_wss_tests(Suite *suite) { + TCase *wss_query = tcase_create("WSS Query Testing"); + tcase_add_test(wss_query, t_wss_query); + tcase_add_test(wss_query, t_buffer_wss_query); + //tcase_add_test(wss_query, t_wss_query_merge); + suite_add_tcase(suite, wss_query); +} diff --git a/tests/internal_level_tests.cpp b/tests/internal_level_tests.cpp index 9deb485..06b0bab 100644 --- a/tests/internal_level_tests.cpp +++ b/tests/internal_level_tests.cpp @@ -6,42 +6,41 @@ * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> * Dong Xie <dongx@psu.edu> * - * All rights reserved. Published under the Modified BSD License. + * Distributed under the Modified BSD License. * */ -#include "shard/WIRS.h" -#include "framework/InternalLevel.h" -#include "framework/RecordInterface.h" -#include "framework/QueryInterface.h" -#include "framework/ShardInterface.h" +#include "shard/ISAMTree.h" +#include "query/rangequery.h" +#include "framework/structure/InternalLevel.h" +#include "framework/interface/Record.h" +#include "framework/interface/Query.h" +#include "framework/interface/Shard.h" -#include "testing.h" +#include "include/testing.h" #include <check.h> using namespace de; -typedef InternalLevel<WRec, WIRS<WRec>, WIRSQuery<WRec>> ILevel; +typedef InternalLevel<Rec, ISAMTree<Rec>, rq::Query<Rec, ISAMTree<Rec>>> ILevel; START_TEST(t_memlevel_merge) { - auto tbl1 = create_test_mbuffer<WRec>(100); - auto tbl2 = create_test_mbuffer<WRec>(100); + auto tbl1 = create_test_mbuffer<Rec>(100); + auto tbl2 = create_test_mbuffer<Rec>(100); auto base_level = new ILevel(1, 1); - base_level->append_buffer(tbl1); + base_level->append_buffer(tbl1->get_buffer_view()); ck_assert_int_eq(base_level->get_record_count(), 100); auto merging_level = new ILevel(0, 1); - merging_level->append_buffer(tbl2); + merging_level->append_buffer(tbl2->get_buffer_view()); ck_assert_int_eq(merging_level->get_record_count(), 100); - auto old_level = base_level; - base_level = ILevel::merge_levels(old_level, merging_level); + auto new_level = ILevel::reconstruction(base_level, merging_level); - delete old_level; delete merging_level; - ck_assert_int_eq(base_level->get_record_count(), 200); + ck_assert_int_eq(new_level->get_record_count(), 200); delete base_level; delete tbl1; @@ -50,12 +49,12 @@ START_TEST(t_memlevel_merge) ILevel *create_test_memlevel(size_t reccnt) { - auto tbl1 = create_test_mbuffer<WRec>(reccnt/2); - auto tbl2 = create_test_mbuffer<WRec>(reccnt/2); + auto tbl1 = create_test_mbuffer<Rec>(reccnt/2); + auto tbl2 = create_test_mbuffer<Rec>(reccnt/2); auto base_level = new ILevel(1, 2); - base_level->append_buffer(tbl1); - base_level->append_buffer(tbl2); + base_level->append_buffer(tbl1->get_buffer_view()); + base_level->append_buffer(tbl2->get_buffer_view()); delete tbl1; delete tbl2; @@ -67,7 +66,7 @@ Suite *unit_testing() { Suite *unit = suite_create("InternalLevel Unit Testing"); - TCase *merge = tcase_create("de::InternalLevel::merge_level Testing"); + TCase *merge = tcase_create("de::InternalLevel::reconstruction Testing"); tcase_add_test(merge, t_memlevel_merge); suite_add_tcase(unit, merge); diff --git a/tests/memisam_tests.cpp b/tests/memisam_tests.cpp index 0ae97dc..9117ce3 100644 --- a/tests/memisam_tests.cpp +++ b/tests/memisam_tests.cpp @@ -1,361 +1,33 @@ /* - * tests/irs_tests.cpp + * tests/isam_tests.cpp * - * Unit tests for MemISAM (Augmented B+Tree) shard + * Unit tests for ISAM Tree shard * * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> * Dong Xie <dongx@psu.edu> * - * All rights reserved. Published under the Modified BSD License. + * Distributed under the Modified BSD License. * */ -#include "shard/MemISAM.h" -#include "testing.h" - +#include "shard/ISAMTree.h" +#include "include/testing.h" #include <check.h> using namespace de; -typedef MemISAM<Rec> Shard; - -START_TEST(t_mbuffer_init) -{ - auto buffer = new MutableBuffer<Rec>(1024, 1024); - for (uint64_t i = 512; i > 0; i--) { - uint32_t v = i; - buffer->append({i,v, 1}); - } - - for (uint64_t i = 1; i <= 256; ++i) { - uint32_t v = i; - buffer->append({i, v, 1}, true); - } - - for (uint64_t i = 257; i <= 512; ++i) { - uint32_t v = i + 1; - buffer->append({i, v, 1}); - } - - Shard* shard = new Shard(buffer); - ck_assert_uint_eq(shard->get_record_count(), 512); - - delete buffer; - delete shard; -} - - -START_TEST(t_irs_init) -{ - size_t n = 512; - auto mbuffer1 = create_test_mbuffer<Rec>(n); - auto mbuffer2 = create_test_mbuffer<Rec>(n); - auto mbuffer3 = create_test_mbuffer<Rec>(n); - - auto shard1 = new Shard(mbuffer1); - auto shard2 = new Shard(mbuffer2); - auto shard3 = new Shard(mbuffer3); - - Shard* shards[3] = {shard1, shard2, shard3}; - auto shard4 = new Shard(shards, 3); - - 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_double_seq_mbuffer<Rec>(n, false); - auto isam = Shard(buffer); - - for (size_t i=0; i<n; i++) { - Rec r; - auto rec = (buffer->get_data() + i); - r.key = rec->rec.key; - r.value = rec->rec.value; - - auto result = isam.point_lookup(r); - ck_assert_ptr_nonnull(result); - ck_assert_int_eq(result->rec.key, r.key); - ck_assert_int_eq(result->rec.value, r.value); - } - - delete buffer; -} -END_TEST - - -START_TEST(t_point_lookup_miss) -{ - size_t n = 10000; - - auto buffer = create_double_seq_mbuffer<Rec>(n, false); - auto isam = Shard(buffer); - - for (size_t i=n + 100; i<2*n; i++) { - Rec r; - r.key = i; - r.value = i; - - auto result = isam.point_lookup(r); - ck_assert_ptr_null(result); - } - - delete buffer; -} - - -START_TEST(t_full_cancelation) -{ - size_t n = 100; - auto buffer = create_double_seq_mbuffer<Rec>(n, false); - auto buffer_ts = create_double_seq_mbuffer<Rec>(n, true); - - Shard* shard = new Shard(buffer); - Shard* shard_ts = new Shard(buffer_ts); - - ck_assert_int_eq(shard->get_record_count(), n); - ck_assert_int_eq(shard->get_tombstone_count(), 0); - ck_assert_int_eq(shard_ts->get_record_count(), n); - ck_assert_int_eq(shard_ts->get_tombstone_count(), n); - - Shard* shards[] = {shard, shard_ts}; - - Shard* merged = new Shard(shards, 2); - - ck_assert_int_eq(merged->get_tombstone_count(), 0); - ck_assert_int_eq(merged->get_record_count(), 0); - - delete buffer; - delete buffer_ts; - delete shard; - delete shard_ts; - delete merged; -} -END_TEST - - -START_TEST(t_irs_query) -{ - size_t n=1000; - auto buffer = create_double_seq_mbuffer<Rec>(n); - auto isam = Shard(buffer); - - uint64_t lower_key = 100; - uint64_t upper_key = 250; - - size_t k = 100; - - size_t cnt[3] = {0}; - irs_query_parms<Rec> parms = {lower_key, upper_key, k}; - parms.rng = gsl_rng_alloc(gsl_rng_mt19937); - - size_t total_samples = 0; - - for (size_t i=0; i<1000; i++) { - auto state = IRSQuery<Rec, false>::get_query_state(&isam, &parms); - ((IRSState<WRec> *) state)->sample_size = k; - auto result = IRSQuery<Rec, false>::query(&isam, state, &parms); - - ck_assert_int_eq(result.size(), k); - - for (auto &rec : result) { - ck_assert_int_le(rec.rec.key, upper_key); - ck_assert_int_ge(rec.rec.key, lower_key); - } - - IRSQuery<Rec, false>::delete_query_state(state); - } - - gsl_rng_free(parms.rng); - delete buffer; -} -END_TEST - - -START_TEST(t_irs_query_merge) -{ - size_t n=1000; - auto buffer = create_double_seq_mbuffer<Rec>(n); - - Shard shard = Shard(buffer); - - uint64_t lower_key = 100; - uint64_t upper_key = 250; - - size_t k = 1000; - - size_t cnt[3] = {0}; - irs_query_parms<Rec> parms = {lower_key, upper_key, k}; - parms.rng = gsl_rng_alloc(gsl_rng_mt19937); - - std::vector<std::vector<de::Wrapped<Rec>>> results(2); - - for (size_t i=0; i<1000; i++) { - auto state1 = IRSQuery<Rec>::get_query_state(&shard, &parms); - ((IRSState<WRec> *) state1)->sample_size = k; - results[0] = IRSQuery<Rec>::query(&shard, state1, &parms); - - auto state2 = IRSQuery<Rec>::get_query_state(&shard, &parms); - ((IRSState<WRec> *) state2)->sample_size = k; - results[1] = IRSQuery<Rec>::query(&shard, state2, &parms); - - IRSQuery<Rec>::delete_query_state(state1); - IRSQuery<Rec>::delete_query_state(state2); - } - - auto merged = IRSQuery<Rec>::merge(results, nullptr); - - ck_assert_int_eq(merged.size(), 2*k); - for (size_t i=0; i<merged.size(); i++) { - ck_assert_int_ge(merged[i].key, lower_key); - ck_assert_int_le(merged[i].key, upper_key); - } - - gsl_rng_free(parms.rng); - delete buffer; -} -END_TEST - - -START_TEST(t_irs_buffer_query_scan) -{ - size_t n=1000; - auto buffer = create_double_seq_mbuffer<Rec>(n); - - uint64_t lower_key = 100; - uint64_t upper_key = 250; - - size_t k = 100; - - size_t cnt[3] = {0}; - irs_query_parms<Rec> parms = {lower_key, upper_key, k}; - parms.rng = gsl_rng_alloc(gsl_rng_mt19937); - - size_t total_samples = 0; - - for (size_t i=0; i<1000; i++) { - auto state = IRSQuery<Rec, false>::get_buffer_query_state(buffer, &parms); - ((IRSBufferState<WRec> *) state)->sample_size = k; - auto result = IRSQuery<Rec, false>::buffer_query(buffer, state, &parms); - - ck_assert_int_eq(result.size(), k); - - for (auto &rec : result) { - ck_assert_int_le(rec.rec.key, upper_key); - ck_assert_int_ge(rec.rec.key, lower_key); - } - - IRSQuery<Rec, false>::delete_buffer_query_state(state); - } - - gsl_rng_free(parms.rng); - delete buffer; -} -END_TEST - - -START_TEST(t_irs_buffer_query_rejection) -{ - size_t n=1000; - auto buffer = create_double_seq_mbuffer<Rec>(n); - - uint64_t lower_key = 100; - uint64_t upper_key = 250; - - size_t k = 10000; - - size_t cnt[3] = {0}; - irs_query_parms<Rec> parms = {lower_key, upper_key, k}; - parms.rng = gsl_rng_alloc(gsl_rng_mt19937); - - size_t total_samples = 0; - - for (size_t i=0; i<1000; i++) { - auto state = IRSQuery<Rec>::get_buffer_query_state(buffer, &parms); - ((IRSBufferState<WRec> *) state)->sample_size = k; - auto result = IRSQuery<Rec>::buffer_query(buffer, state, &parms); - - ck_assert_int_gt(result.size(), 0); - ck_assert_int_le(result.size(), k); - - for (auto &rec : result) { - ck_assert_int_le(rec.rec.key, upper_key); - ck_assert_int_ge(rec.rec.key, lower_key); - } - - IRSQuery<Rec>::delete_buffer_query_state(state); - } - - gsl_rng_free(parms.rng); - delete buffer; -} -END_TEST +typedef Rec R; +typedef ISAMTree<R> Shard; +#include "include/shard_standard.h" +#include "include/rangequery.h" Suite *unit_testing() { - Suite *unit = suite_create("MemISAM Shard Unit Testing"); - - TCase *create = tcase_create("de::MemISAM constructor Testing"); - tcase_add_test(create, t_mbuffer_init); - tcase_add_test(create, t_irs_init); - tcase_set_timeout(create, 100); - suite_add_tcase(unit, create); - - - TCase *tombstone = tcase_create("de:MemISAM::tombstone cancellation Testing"); - tcase_add_test(tombstone, t_full_cancelation); - suite_add_tcase(unit, tombstone); - - - TCase *lookup = tcase_create("de:MemISAM:point_lookup Testing"); - tcase_add_test(lookup, t_point_lookup); - tcase_add_test(lookup, t_point_lookup_miss); - suite_add_tcase(unit, lookup); - + Suite *unit = suite_create("Alias-augmented B+Tree Shard Unit Testing"); - TCase *sampling = tcase_create("de:MemISAM::MemISAMQuery Testing"); - tcase_add_test(sampling, t_irs_query); - tcase_add_test(sampling, t_irs_query_merge); - tcase_add_test(sampling, t_irs_buffer_query_rejection); - tcase_add_test(sampling, t_irs_buffer_query_scan); - tcase_set_timeout(sampling, 100); - suite_add_tcase(unit, sampling); + inject_rangequery_tests(unit); + inject_shard_tests(unit); return unit; } diff --git a/tests/mutable_buffer_tests.cpp b/tests/mutable_buffer_tests.cpp index 201fddb..31c16dc 100644 --- a/tests/mutable_buffer_tests.cpp +++ b/tests/mutable_buffer_tests.cpp @@ -1,39 +1,47 @@ /* * tests/mutable_buffer_tests.cpp * - * Unit tests for MutableBuffer + * Unit tests for MutableBuffer and BufferView * * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> * Dong Xie <dongx@psu.edu> * - * All rights reserved. Published under the Modified BSD License. + * Distributed under the Modified BSD License. * */ -#include <string> + #include <thread> #include <vector> -#include <algorithm> -#include "testing.h" -#include "framework/MutableBuffer.h" +#include "include/testing.h" +#include "framework/structure/MutableBuffer.h" #include <check.h> -#define DE_MT_TEST 0 - using namespace de; START_TEST(t_create) { - auto buffer = new MutableBuffer<Rec>(100, 50); + size_t lwm = 50, hwm = 100; + size_t cap = 2 * hwm; + + auto buffer = new MutableBuffer<Rec>(lwm, hwm); ck_assert_ptr_nonnull(buffer); - ck_assert_int_eq(buffer->get_capacity(), 100); - ck_assert_int_eq(buffer->get_record_count(), 0); + ck_assert_int_eq(buffer->get_capacity(), cap); + ck_assert_int_eq(buffer->get_low_watermark(), lwm); + ck_assert_int_eq(buffer->get_high_watermark(), hwm); + ck_assert_int_eq(buffer->is_full(), false); - ck_assert_ptr_nonnull(buffer->get_data()); + ck_assert_int_eq(buffer->is_at_low_watermark(), false); + ck_assert_int_eq(buffer->get_record_count(), 0); ck_assert_int_eq(buffer->get_tombstone_count(), 0); - ck_assert_int_eq(buffer->get_tombstone_capacity(), 50); + + { + auto view = buffer->get_buffer_view(); + ck_assert_int_eq(view.get_tombstone_count(), 0); + ck_assert_int_eq(view.get_record_count(), 0); + } delete buffer; } @@ -42,76 +50,149 @@ END_TEST START_TEST(t_insert) { - auto buffer = new MutableBuffer<WRec>(100, 50); + auto buffer = new MutableBuffer<Rec>(50, 100); + + Rec rec = {0, 5, 1}; - uint64_t key = 0; - uint32_t val = 5; + /* insert records up to the low watermark */ + size_t cnt = 0; + for (size_t i=0; i<50; i++) { + ck_assert_int_eq(buffer->is_at_low_watermark(), false); + ck_assert_int_eq(buffer->append(rec), 1); + ck_assert_int_eq(buffer->check_tombstone(rec), 0); - WRec rec = {0, 5, 1}; + rec.key++; + rec.value++; + cnt++; - for (size_t i=0; i<99; i++) { + ck_assert_int_eq(buffer->get_record_count(), cnt); + ck_assert_int_eq(buffer->get_buffer_view().get_record_count(), cnt); + ck_assert_int_eq(buffer->get_tail(), cnt); + } + + ck_assert_int_eq(buffer->is_at_low_watermark(), true); + + /* insert records up to the high watermark */ + for (size_t i=0; i<50; i++) { + ck_assert_int_eq(buffer->is_full(), 0); ck_assert_int_eq(buffer->append(rec), 1); ck_assert_int_eq(buffer->check_tombstone(rec), 0); rec.key++; rec.value++; + cnt++; + + ck_assert_int_eq(buffer->get_record_count(), cnt); + ck_assert_int_eq(buffer->get_buffer_view().get_record_count(), cnt); - ck_assert_int_eq(buffer->get_record_count(), i+1); ck_assert_int_eq(buffer->get_tombstone_count(), 0); - ck_assert_int_eq(buffer->is_full(), 0); + ck_assert_int_eq(buffer->is_at_low_watermark(), true); + ck_assert_int_eq(buffer->get_tail(), cnt); } - ck_assert_int_eq(buffer->append(rec), 1); - + /* further inserts should fail */ rec.key++; rec.value++; - ck_assert_int_eq(buffer->is_full(), 1); ck_assert_int_eq(buffer->append(rec), 0); delete buffer; - } END_TEST -START_TEST(t_insert_tombstones) +START_TEST(t_advance_head) { - auto buffer = new MutableBuffer<Rec>(100, 50); + auto buffer = new MutableBuffer<Rec>(50, 100); - size_t ts_cnt = 0; + /* insert 75 records and get tail when LWM is exceeded */ + size_t new_head = 0; + Rec rec = {1, 1}; + size_t cnt = 0; + for (size_t i=0; i<75; i++) { + ck_assert_int_eq(buffer->append(rec), 1); - Rec rec = {0, 5}; + rec.key++; + rec.value++; + cnt++; - for (size_t i=0; i<99; i++) { - bool ts = false; - if (i % 2 == 0) { - ts_cnt++; - ts=true; + if (buffer->is_at_low_watermark() && new_head == 0) { + new_head = buffer->get_tail(); } + } - ck_assert_int_eq(buffer->append(rec, ts), 1); - ck_assert_int_eq(buffer->check_tombstone(rec), ts); + ck_assert_int_eq(buffer->get_available_capacity(), 200 - cnt); - rec.key++; - rec.value++; + Wrapped<Rec> *view_records = new Wrapped<Rec>[buffer->get_record_count()]; + { + /* get a view of the pre-advanced state */ + auto view = buffer->get_buffer_view(); + ck_assert_int_eq(view.get_record_count(), cnt); + view.copy_to_buffer((psudb::byte *) view_records); - ck_assert_int_eq(buffer->get_record_count(), i+1); - ck_assert_int_eq(buffer->get_tombstone_count(), ts_cnt); - ck_assert_int_eq(buffer->is_full(), 0); + /* advance the head */ + ck_assert_int_eq(buffer->advance_head(new_head), 1); + ck_assert_int_eq(buffer->get_record_count(), 25); + ck_assert_int_eq(buffer->get_buffer_view().get_record_count(), 25); + ck_assert_int_eq(view.get_record_count(), cnt); + ck_assert_int_eq(buffer->get_available_capacity(), 200 - cnt); + + /* refuse to advance head again while there remain references to the old one */ + ck_assert_int_eq(buffer->advance_head(buffer->get_tail() -1), 0); } - // inserting one more tombstone should not be possible - ck_assert_int_eq(buffer->append(rec, true), 0); + /* once the buffer view falls out of scope, the capacity of the buffer should increase */ + ck_assert_int_eq(buffer->get_available_capacity(), 175); + /* now the head should be able to be advanced */ + ck_assert_int_eq(buffer->advance_head(buffer->get_tail()), 1); - ck_assert_int_eq(buffer->append(rec), 1); + /* and the buffer should be empty */ + ck_assert_int_eq(buffer->get_record_count(), 0); - rec.key++; - rec.value++; + delete buffer; + delete[] view_records; +} +END_TEST + +void insert_records(std::vector<Rec> *values, size_t start, size_t stop, MutableBuffer<Rec> *buffer) +{ + for (size_t i=start; i<stop; i++) { + buffer->append((*values)[i]); + } + +} + +START_TEST(t_multithreaded_insert) +{ + size_t cnt = 10000; + auto buffer = new MutableBuffer<Rec>(cnt/2, cnt); + + std::vector<Rec> records(cnt); + for (size_t i=0; i<cnt; i++) { + records[i] = Rec {(uint64_t) rand(), (uint32_t) rand()}; + } + + /* perform a multithreaded insertion */ + size_t thread_cnt = 8; + size_t per_thread = cnt / thread_cnt; + std::vector<std::thread> workers(thread_cnt); + size_t start = 0; + size_t stop = start + per_thread; + for (size_t i=0; i<thread_cnt; i++) { + workers[i] = std::thread(insert_records, &records, start, stop, buffer); + start = stop; + stop = std::min(start + per_thread, cnt); + } + + for (size_t i=0; i<thread_cnt; i++) { + if (workers[i].joinable()) { + workers[i].join(); + } + } ck_assert_int_eq(buffer->is_full(), 1); - ck_assert_int_eq(buffer->append(rec), 0); + ck_assert_int_eq(buffer->get_record_count(), cnt); delete buffer; } @@ -120,7 +201,7 @@ END_TEST START_TEST(t_truncate) { - auto buffer = new MutableBuffer<Rec>(100, 100); + auto buffer = new MutableBuffer<Rec>(50, 100); size_t ts_cnt = 0; Rec rec = {0, 5}; @@ -157,42 +238,76 @@ START_TEST(t_truncate) } END_TEST - -START_TEST(t_get_data) +START_TEST(t_bview_get) { - size_t cnt = 100; + auto buffer = new MutableBuffer<Rec>(50, 100); - auto buffer = new MutableBuffer<Rec>(cnt, cnt/2); + /* insert 75 records and get tail when LWM is exceeded */ + size_t new_head = 0; + Rec rec = {1, 1}; + size_t cnt = 0; + for (size_t i=0; i<75; i++) { + ck_assert_int_eq(buffer->append(rec), 1); + rec.key++; + rec.value++; + cnt++; - std::vector<uint64_t> keys(cnt); - for (size_t i=0; i<cnt-2; i++) { - keys[i] = rand(); + if (buffer->is_at_low_watermark() && new_head == 0) { + new_head = buffer->get_tail(); + } } - // duplicate final two records for tombstone testing - // purposes - keys[cnt-2] = keys[cnt-3]; - keys[cnt-1] = keys[cnt-2]; + ck_assert_int_eq(buffer->get_available_capacity(), 200 - cnt); + + { + /* get a view of the pre-advanced state */ + auto view = buffer->get_buffer_view(); + auto reccnt = view.get_record_count(); - uint32_t val = 12345; - for (size_t i=0; i<cnt-2; i++) { - buffer->append(Rec {keys[i], val}); + /* scan the records in the view */ + for (size_t i=0; i<reccnt; i++) { + ck_assert_int_eq(view.get(i)->rec.key, i+1); + } + + /* advance the head */ + buffer->advance_head(new_head); + + /* scan the records in the view again -- should be unchanged */ + for (size_t i=0; i<reccnt; i++) { + ck_assert_int_eq(view.get(i)->rec.key, i+1); + } } - Rec r1 = {keys[cnt-2], val}; - buffer->append(r1, true); + { + /* get a new view (should have fewer records) */ + auto view = buffer->get_buffer_view(); + auto reccnt = view.get_record_count(); - Rec r2 = {keys[cnt-1], val}; - buffer->append(r2, true); + /* verify the scan again */ + for (size_t i=0; i<reccnt; i++) { + ck_assert_int_eq(view.get(i)->rec.key, i + 51); + } + } + + /* insert more records (to trigger a wrap-around) */ + for (size_t i=0; i<75; i++) { + ck_assert_int_eq(buffer->append(rec), 1); + rec.key++; + rec.value++; + cnt++; + } - auto *sorted_records = buffer->get_data(); - std::sort(keys.begin(), keys.end()); - std::sort(sorted_records, sorted_records + buffer->get_record_count(), std::less<Wrapped<Rec>>()); + { + /* get a new view (should have fewer records) */ + auto view = buffer->get_buffer_view(); + auto reccnt = view.get_record_count(); - for (size_t i=0; i<cnt; i++) { - ck_assert_int_eq(sorted_records[i].rec.key, keys[i]); + /* verify the scan again */ + for (size_t i=0; i<reccnt; i++) { + ck_assert_int_eq(view.get(i)->rec.key, i + 51); + } } delete buffer; @@ -200,56 +315,65 @@ START_TEST(t_get_data) END_TEST -void insert_records(std::vector<std::pair<uint64_t, uint32_t>> *values, size_t start, size_t stop, MutableBuffer<Rec> *buffer) +START_TEST(t_bview_delete) { - for (size_t i=start; i<stop; i++) { - buffer->append({(*values)[i].first, (*values)[i].second}); - } -} + auto buffer = new MutableBuffer<Rec>(50, 100); -#if DE_MT_TEST -START_TEST(t_multithreaded_insert) -{ - size_t cnt = 10000; - auto buffer = new MutableBuffer<Rec>(cnt, true, cnt/2); - - std::vector<Rec> records(cnt); - for (size_t i=0; i<cnt; i++) { - records[i] = Rec {(uint64_t) rand(), (uint32_t) rand()}; - } + /* insert 75 records and get tail when LWM is exceeded */ + size_t new_head = 0; + Rec rec = {1, 1}; + size_t cnt = 0; + for (size_t i=0; i<75; i++) { + ck_assert_int_eq(buffer->append(rec), 1); - // perform a t_multithreaded insertion - size_t thread_cnt = 8; - size_t per_thread = cnt / thread_cnt; - std::vector<std::thread> workers(thread_cnt); - size_t start = 0; - size_t stop = start + per_thread; - for (size_t i=0; i<thread_cnt; i++) { - workers[i] = std::thread(insert_records, &records, start, stop, buffer); - start = stop; - stop = std::min(start + per_thread, cnt); - } + rec.key++; + rec.value++; + cnt++; - for (size_t i=0; i<thread_cnt; i++) { - if (workers[i].joinable()) { - workers[i].join(); + if (buffer->is_at_low_watermark() && new_head == 0) { + new_head = buffer->get_tail(); } } - ck_assert_int_eq(buffer->is_full(), 1); - ck_assert_int_eq(buffer->get_record_count(), cnt); + buffer->advance_head(new_head); - std::sort(records.begin(), records.end()); - auto *sorted_records = buffer->sorted_output(); - for (size_t i=0; i<cnt; i++) { - ck_assert_int_eq(sorted_records[i].key, records[i].key); + for (size_t i=0; i<75; i++) { + ck_assert_int_eq(buffer->append(rec), 1); + + rec.key++; + rec.value++; + cnt++; + } + + Rec dr1 = {67, 67}; + Rec dr2 = {89, 89}; + Rec dr3 = {103, 103}; + + Rec fdr1 = {5, 5}; + Rec fdr2 = {300, 300}; + { + /* get a new view (should have fewer records) */ + auto view = buffer->get_buffer_view(); + ck_assert_int_eq(view.delete_record(dr1), 1); + ck_assert_int_eq(view.delete_record(dr2), 1); + ck_assert_int_eq(view.delete_record(dr3), 1); + ck_assert_int_eq(view.delete_record(fdr1), 0); + ck_assert_int_eq(view.delete_record(fdr2), 0); + + for (size_t i=0; i<view.get_record_count(); i++) { + if (view.get(i)->rec == dr1 || view.get(i)->rec == dr2 + || view.get(i)->rec == dr3) { + ck_assert_int_eq(view.get(i)->is_deleted(), 1); + } else { + ck_assert_int_eq(view.get(i)->is_deleted(), 0); + } + } } delete buffer; } END_TEST -#endif Suite *unit_testing() @@ -263,13 +387,16 @@ Suite *unit_testing() TCase *append = tcase_create("de::MutableBuffer::append Testing"); tcase_add_test(append, t_insert); - tcase_add_test(append, t_insert_tombstones); - #if DE_MT_TEST - tcase_add_test(append, t_multithreaded_insert); - #endif + tcase_add_test(append, t_advance_head); + tcase_add_test(append, t_multithreaded_insert); suite_add_tcase(unit, append); + TCase *view = tcase_create("de::BufferView Testing"); + tcase_add_test(view, t_bview_get); + tcase_add_test(view, t_bview_delete); + + suite_add_tcase(unit, view); TCase *truncate = tcase_create("de::MutableBuffer::truncate Testing"); tcase_add_test(truncate, t_truncate); @@ -277,11 +404,6 @@ Suite *unit_testing() suite_add_tcase(unit, truncate); - TCase *sorted_out = tcase_create("de::MutableBuffer::get_data"); - tcase_add_test(sorted_out, t_get_data); - - suite_add_tcase(unit, sorted_out); - return unit; } diff --git a/tests/pgm_tests.cpp b/tests/pgm_tests.cpp index 0552417..ee350de 100644 --- a/tests/pgm_tests.cpp +++ b/tests/pgm_tests.cpp @@ -1,339 +1,33 @@ /* - * tests/irs_tests.cpp + * tests/isam_tests.cpp * - * Unit tests for PGM (Augmented B+Tree) shard + * Unit tests for ISAM Tree shard * * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> * Dong Xie <dongx@psu.edu> * - * All rights reserved. Published under the Modified BSD License. + * Distributed under the Modified BSD License. * */ #include "shard/PGM.h" -#include "testing.h" - +#include "include/testing.h" #include <check.h> using namespace de; -typedef PGM<Rec> Shard; - -START_TEST(t_mbuffer_init) -{ - auto buffer = new MutableBuffer<Rec>(1024, 1024); - for (uint64_t i = 512; i > 0; i--) { - uint32_t v = i; - buffer->append({i,v, 1}); - } - - for (uint64_t i = 1; i <= 256; ++i) { - uint32_t v = i; - buffer->append({i, v, 1}, true); - } - - for (uint64_t i = 257; i <= 512; ++i) { - uint32_t v = i + 1; - buffer->append({i, v, 1}); - } - - Shard* shard = new Shard(buffer); - ck_assert_uint_eq(shard->get_record_count(), 512); - - delete buffer; - delete shard; -} - - -START_TEST(t_irs_init) -{ - size_t n = 512; - auto mbuffer1 = create_test_mbuffer<Rec>(n); - auto mbuffer2 = create_test_mbuffer<Rec>(n); - auto mbuffer3 = create_test_mbuffer<Rec>(n); - - auto shard1 = new Shard(mbuffer1); - auto shard2 = new Shard(mbuffer2); - auto shard3 = new Shard(mbuffer3); - - Shard* shards[3] = {shard1, shard2, shard3}; - auto shard4 = new Shard(shards, 3); - - 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_double_seq_mbuffer<Rec>(n, false); - auto shard = Shard(buffer); - - for (size_t i=0; i<n; i++) { - Rec r; - auto rec = (buffer->get_data() + i); - r.key = rec->rec.key; - r.value = rec->rec.value; - - auto result = shard.point_lookup(r); - ck_assert_ptr_nonnull(result); - ck_assert_int_eq(result->rec.key, r.key); - ck_assert_int_eq(result->rec.value, r.value); - } - - delete buffer; -} -END_TEST - - -START_TEST(t_point_lookup_miss) -{ - size_t n = 10000; - - auto buffer = create_double_seq_mbuffer<Rec>(n, false); - auto isam = Shard(buffer); - - for (size_t i=n + 100; i<2*n; i++) { - Rec r; - r.key = i; - r.value = i; - - auto result = isam.point_lookup(r); - ck_assert_ptr_null(result); - } - - delete buffer; -} - - -START_TEST(t_range_query) -{ - auto buffer = create_sequential_mbuffer<Rec>(100, 1000); - auto shard = Shard(buffer); - - pgm_range_query_parms<Rec> parms; - parms.lower_bound = 300; - parms.upper_bound = 500; - - auto state = PGMRangeQuery<Rec>::get_query_state(&shard, &parms); - auto result = PGMRangeQuery<Rec>::query(&shard, state, &parms); - PGMRangeQuery<Rec>::delete_query_state(state); - - ck_assert_int_eq(result.size(), parms.upper_bound - parms.lower_bound + 1); - for (size_t i=0; i<result.size(); i++) { - ck_assert_int_le(result[i].rec.key, parms.upper_bound); - ck_assert_int_ge(result[i].rec.key, parms.lower_bound); - } - - delete buffer; -} -END_TEST - - -START_TEST(t_buffer_range_query) -{ - auto buffer = create_sequential_mbuffer<Rec>(100, 1000); - - pgm_range_query_parms<Rec> parms; - parms.lower_bound = 300; - parms.upper_bound = 500; - - auto state = PGMRangeQuery<Rec>::get_buffer_query_state(buffer, &parms); - auto result = PGMRangeQuery<Rec>::buffer_query(buffer, state, &parms); - PGMRangeQuery<Rec>::delete_buffer_query_state(state); - - ck_assert_int_eq(result.size(), parms.upper_bound - parms.lower_bound + 1); - for (size_t i=0; i<result.size(); i++) { - ck_assert_int_le(result[i].rec.key, parms.upper_bound); - ck_assert_int_ge(result[i].rec.key, parms.lower_bound); - } - - delete buffer; -} -END_TEST - - -START_TEST(t_range_query_merge) -{ - auto buffer1 = create_sequential_mbuffer<Rec>(100, 200); - auto buffer2 = create_sequential_mbuffer<Rec>(400, 1000); - - auto shard1 = Shard(buffer1); - auto shard2 = Shard(buffer2); - - pgm_range_query_parms<Rec> parms; - parms.lower_bound = 150; - parms.upper_bound = 500; - - size_t result_size = parms.upper_bound - parms.lower_bound + 1 - 200; - - auto state1 = PGMRangeQuery<Rec>::get_query_state(&shard1, &parms); - auto state2 = PGMRangeQuery<Rec>::get_query_state(&shard2, &parms); - - std::vector<std::vector<de::Wrapped<Rec>>> results(2); - results[0] = PGMRangeQuery<Rec>::query(&shard1, state1, &parms); - results[1] = PGMRangeQuery<Rec>::query(&shard2, state2, &parms); - - PGMRangeQuery<Rec>::delete_query_state(state1); - PGMRangeQuery<Rec>::delete_query_state(state2); - - ck_assert_int_eq(results[0].size() + results[1].size(), result_size); - - std::vector<std::vector<Wrapped<Rec>>> proc_results; - - for (size_t j=0; j<results.size(); j++) { - proc_results.emplace_back(std::vector<Wrapped<Rec>>()); - for (size_t i=0; i<results[j].size(); i++) { - proc_results[j].emplace_back(results[j][i]); - } - } - - auto result = PGMRangeQuery<Rec>::merge(proc_results, nullptr); - std::sort(result.begin(), result.end()); - - ck_assert_int_eq(result.size(), result_size); - auto key = parms.lower_bound; - for (size_t i=0; i<result.size(); i++) { - ck_assert_int_eq(key++, result[i].key); - if (key == 200) { - key = 400; - } - } - - delete buffer1; - delete buffer2; -} -END_TEST - -START_TEST(t_lower_bound) -{ - auto buffer1 = create_sequential_mbuffer<Rec>(100, 200); - auto buffer2 = create_sequential_mbuffer<Rec>(400, 1000); - - de::PGM<Rec> *shards[2]; - - auto shard1 = Shard(buffer1); - auto shard2 = Shard(buffer2); - - shards[0] = &shard1; - shards[1] = &shard2; - - auto merged = Shard(shards, 2); - - for (size_t i=100; i<1000; i++) { - Rec r; - r.key = i; - r.value = i; - - auto idx = merged.get_lower_bound(i); - - assert(idx < merged.get_record_count()); - - auto res = merged.get_record_at(idx); - - if (i >=200 && i <400) { - ck_assert_int_lt(res->rec.key, i); - } else { - ck_assert_int_eq(res->rec.key, i); - } - } - - delete buffer1; - delete buffer2; -} -END_TEST - - -START_TEST(t_full_cancelation) -{ - size_t n = 100; - auto buffer = create_double_seq_mbuffer<Rec>(n, false); - auto buffer_ts = create_double_seq_mbuffer<Rec>(n, true); - - Shard* shard = new Shard(buffer); - Shard* shard_ts = new Shard(buffer_ts); - - ck_assert_int_eq(shard->get_record_count(), n); - ck_assert_int_eq(shard->get_tombstone_count(), 0); - ck_assert_int_eq(shard_ts->get_record_count(), n); - ck_assert_int_eq(shard_ts->get_tombstone_count(), n); - - Shard* shards[] = {shard, shard_ts}; - - Shard* merged = new Shard(shards, 2); - - ck_assert_int_eq(merged->get_tombstone_count(), 0); - ck_assert_int_eq(merged->get_record_count(), 0); - - delete buffer; - delete buffer_ts; - delete shard; - delete shard_ts; - delete merged; -} -END_TEST +typedef Rec R; +typedef PGM<R> Shard; +#include "include/shard_standard.h" +#include "include/rangequery.h" Suite *unit_testing() { Suite *unit = suite_create("PGM Shard Unit Testing"); - TCase *create = tcase_create("de::PGM constructor Testing"); - tcase_add_test(create, t_mbuffer_init); - tcase_add_test(create, t_irs_init); - tcase_set_timeout(create, 100); - suite_add_tcase(unit, create); - - - TCase *tombstone = tcase_create("de:PGM::tombstone cancellation Testing"); - tcase_add_test(tombstone, t_full_cancelation); - suite_add_tcase(unit, tombstone); - - - TCase *lookup = tcase_create("de:PGM:point_lookup Testing"); - tcase_add_test(lookup, t_point_lookup); - tcase_add_test(lookup, t_point_lookup_miss); - tcase_add_test(lookup, t_lower_bound); - suite_add_tcase(unit, lookup); - - TCase *range_query = tcase_create("de:PGM::range_query Testing"); - tcase_add_test(range_query, t_range_query); - tcase_add_test(range_query, t_buffer_range_query); - tcase_add_test(range_query, t_range_query_merge); - suite_add_tcase(unit, range_query); + inject_rangequery_tests(unit); + inject_shard_tests(unit); return unit; } diff --git a/tests/rangecount_tests.cpp b/tests/rangecount_tests.cpp new file mode 100644 index 0000000..3be8234 --- /dev/null +++ b/tests/rangecount_tests.cpp @@ -0,0 +1,56 @@ +/* + * tests/rangequery_tests.cpp + * + * Unit tests for Range Queries across several different + * shards + * + * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> + * Dong Xie <dongx@psu.edu> + * + * Distributed under the Modified BSD License. + * + */ + +#include "shard/ISAMTree.h" +#include "query/rangecount.h" +#include "include/testing.h" + +#include <check.h> + +using namespace de; + +typedef Rec R; +typedef ISAMTree<Rec> Shard; + +#include "include/rangecount.h" + + +Suite *unit_testing() +{ + Suite *unit = suite_create("Range Count Query Testing"); + inject_rangecount_tests(unit); + + return unit; +} + + +int shard_unit_tests() +{ + int failed = 0; + Suite *unit = unit_testing(); + SRunner *unit_shardner = srunner_create(unit); + + srunner_run_all(unit_shardner, CK_NORMAL); + failed = srunner_ntests_failed(unit_shardner); + srunner_free(unit_shardner); + + return failed; +} + + +int main() +{ + int unit_failed = shard_unit_tests(); + + return (unit_failed == 0) ? EXIT_SUCCESS : EXIT_FAILURE; +} diff --git a/tests/rangequery_tests.cpp b/tests/rangequery_tests.cpp new file mode 100644 index 0000000..bf5fb5e --- /dev/null +++ b/tests/rangequery_tests.cpp @@ -0,0 +1,55 @@ +/* + * tests/rangequery_tests.cpp + * + * Unit tests for Range Queries across several different + * shards + * + * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> + * Dong Xie <dongx@psu.edu> + * + * Distributed under the Modified BSD License. + * + */ + +#include "shard/ISAMTree.h" +#include "query/rangequery.h" +#include "include/testing.h" + +#include <check.h> + +using namespace de; + +typedef Rec R; +typedef ISAMTree<R> Shard; + +#include "include/rangequery.h" + +Suite *unit_testing() +{ + Suite *unit = suite_create("Range Count Query Testing"); + inject_rangequery_tests(unit); + + return unit; +} + + +int shard_unit_tests() +{ + int failed = 0; + Suite *unit = unit_testing(); + SRunner *unit_shardner = srunner_create(unit); + + srunner_run_all(unit_shardner, CK_NORMAL); + failed = srunner_ntests_failed(unit_shardner); + srunner_free(unit_shardner); + + return failed; +} + + +int main() +{ + int unit_failed = shard_unit_tests(); + + return (unit_failed == 0) ? EXIT_SUCCESS : EXIT_FAILURE; +} diff --git a/tests/triespline_tests.cpp b/tests/triespline_tests.cpp index 6f63961..e884360 100644 --- a/tests/triespline_tests.cpp +++ b/tests/triespline_tests.cpp @@ -1,258 +1,33 @@ /* - * tests/triespline_tests.cpp + * tests/isam_tests.cpp * - * Unit tests for TrieSpline (Augmented B+Tree) shard + * Unit tests for ISAM Tree shard * * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> * Dong Xie <dongx@psu.edu> * - * All rights reserved. Published under the Modified BSD License. + * Distributed under the Modified BSD License. * */ -#include <functional> - #include "shard/TrieSpline.h" -#include "testing.h" - +#include "include/testing.h" #include <check.h> using namespace de; -typedef TrieSpline<Rec> Shard; - -START_TEST(t_mbuffer_init) -{ - auto buffer = new MutableBuffer<Rec>(1024, 1024); - for (uint64_t i = 512; i > 0; i--) { - uint32_t v = i; - buffer->append({i,v, 1}); - } - - for (uint64_t i = 1; i <= 256; ++i) { - uint32_t v = i; - buffer->append({i, v, 1}, true); - } - - for (uint64_t i = 257; i <= 512; ++i) { - uint32_t v = i + 1; - buffer->append({i, v, 1}); - } - - Shard* shard = new Shard(buffer); - ck_assert_uint_eq(shard->get_record_count(), 512); - - delete buffer; - delete shard; -} - - -START_TEST(t_init) -{ - size_t n = 512; - auto mbuffer1 = create_test_mbuffer<Rec>(n); - auto mbuffer2 = create_test_mbuffer<Rec>(n); - auto mbuffer3 = create_test_mbuffer<Rec>(n); - - auto shard1 = new Shard(mbuffer1); - auto shard2 = new Shard(mbuffer2); - auto shard3 = new Shard(mbuffer3); - - Shard* shards[3] = {shard1, shard2, shard3}; - auto shard4 = new Shard(shards, 3); - - 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_double_seq_mbuffer<Rec>(n, false); - auto shard = Shard(buffer); - - for (size_t i=0; i<n; i++) { - Rec r; - auto rec = (buffer->get_data() + i); - r.key = rec->rec.key; - r.value = rec->rec.value; - - auto result = shard.point_lookup(r); - ck_assert_ptr_nonnull(result); - ck_assert_int_eq(result->rec.key, r.key); - ck_assert_int_eq(result->rec.value, r.value); - } - - delete buffer; -} -END_TEST - - -START_TEST(t_point_lookup_miss) -{ - size_t n = 10000; - - auto buffer = create_double_seq_mbuffer<Rec>(n, false); - auto isam = Shard(buffer); - - for (size_t i=n + 100; i<2*n; i++) { - Rec r; - r.key = i; - r.value = i; - - auto result = isam.point_lookup(r); - ck_assert_ptr_null(result); - } - - delete buffer; -} - - -START_TEST(t_full_cancelation) -{ - size_t n = 100; - auto buffer = create_double_seq_mbuffer<Rec>(n, false); - auto buffer_ts = create_double_seq_mbuffer<Rec>(n, true); - - Shard* shard = new Shard(buffer); - Shard* shard_ts = new Shard(buffer_ts); - - ck_assert_int_eq(shard->get_record_count(), n); - ck_assert_int_eq(shard->get_tombstone_count(), 0); - ck_assert_int_eq(shard_ts->get_record_count(), n); - ck_assert_int_eq(shard_ts->get_tombstone_count(), n); - - Shard* shards[] = {shard, shard_ts}; - - Shard* merged = new Shard(shards, 2); - - ck_assert_int_eq(merged->get_tombstone_count(), 0); - ck_assert_int_eq(merged->get_record_count(), 0); - - delete buffer; - delete buffer_ts; - delete shard; - delete shard_ts; - delete merged; -} -END_TEST - - -START_TEST(t_range_query) -{ - auto buffer = create_sequential_mbuffer<Rec>(100, 1000); - auto shard = Shard(buffer); - - ts_range_query_parms<Rec> parms; - parms.lower_bound = 300; - parms.upper_bound = 500; - - auto state = TrieSplineRangeQuery<Rec>::get_query_state(&shard, &parms); - auto result = TrieSplineRangeQuery<Rec>::query(&shard, state, &parms); - TrieSplineRangeQuery<Rec>::delete_query_state(state); - - ck_assert_int_eq(result.size(), parms.upper_bound - parms.lower_bound + 1); - for (size_t i=0; i<result.size(); i++) { - ck_assert_int_le(result[i].rec.key, parms.upper_bound); - ck_assert_int_ge(result[i].rec.key, parms.lower_bound); - } - - delete buffer; -} -END_TEST - - -START_TEST(t_buffer_range_query) -{ - auto buffer = create_sequential_mbuffer<Rec>(100, 1000); - - ts_range_query_parms<Rec> parms; - parms.lower_bound = 300; - parms.upper_bound = 500; - - auto state = TrieSplineRangeQuery<Rec>::get_buffer_query_state(buffer, &parms); - auto result = TrieSplineRangeQuery<Rec>::buffer_query(buffer, state, &parms); - TrieSplineRangeQuery<Rec>::delete_buffer_query_state(state); - - ck_assert_int_eq(result.size(), parms.upper_bound - parms.lower_bound + 1); - for (size_t i=0; i<result.size(); i++) { - ck_assert_int_le(result[i].rec.key, parms.upper_bound); - ck_assert_int_ge(result[i].rec.key, parms.lower_bound); - } - - delete buffer; -} -END_TEST - - -START_TEST(t_range_query_merge) -{ - -} -END_TEST +typedef Rec R; +typedef TrieSpline<R> Shard; +#include "include/shard_standard.h" +#include "include/rangequery.h" Suite *unit_testing() { - Suite *unit = suite_create("TrieSpline Shard Unit Testing"); - - TCase *create = tcase_create("de::TrieSpline constructor Testing"); - tcase_add_test(create, t_mbuffer_init); - tcase_add_test(create, t_init); - tcase_set_timeout(create, 100); - suite_add_tcase(unit, create); - - - TCase *tombstone = tcase_create("de:TrieSpline::tombstone cancellation Testing"); - tcase_add_test(tombstone, t_full_cancelation); - suite_add_tcase(unit, tombstone); - - - TCase *lookup = tcase_create("de:TrieSpline:point_lookup Testing"); - tcase_add_test(lookup, t_point_lookup); - tcase_add_test(lookup, t_point_lookup_miss); - suite_add_tcase(unit, lookup); - - - TCase *range_query = tcase_create("de:TrieSpline::range_query Testing"); - tcase_add_test(range_query, t_range_query); - tcase_add_test(range_query, t_buffer_range_query); - tcase_add_test(range_query, t_range_query_merge); - suite_add_tcase(unit, range_query); + Suite *unit = suite_create("Triespline Shard Unit Testing"); + inject_rangequery_tests(unit); + inject_shard_tests(unit); return unit; } diff --git a/tests/vptree_tests.cpp b/tests/vptree_tests.cpp index 06f147b..ff99ba6 100644 --- a/tests/vptree_tests.cpp +++ b/tests/vptree_tests.cpp @@ -5,31 +5,32 @@ * * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> * - * All rights reserved. Published under the Modified BSD License. + * Distributed under the Modified BSD License. * */ + +#include "include/testing.h" #include "shard/VPTree.h" -#include "testing.h" -#include "vptree.hpp" +#include "query/knn.h" #include <check.h> using namespace de; - -typedef VPTree<PRec> Shard; +typedef PRec R; +typedef VPTree<R> Shard; START_TEST(t_mbuffer_init) { size_t n= 24; - auto buffer = new MutableBuffer<PRec>(n, n); + auto buffer = new MutableBuffer<PRec>(n/2, n); for (int64_t i=0; i<n; i++) { - buffer->append({i, i}); + buffer->append({(uint64_t) i, (uint64_t) i}); } - Shard* shard = new Shard(buffer); + Shard* shard = new Shard(buffer->get_buffer_view()); ck_assert_uint_eq(shard->get_record_count(), n); delete buffer; @@ -40,16 +41,16 @@ START_TEST(t_mbuffer_init) START_TEST(t_wss_init) { size_t n = 512; - auto mbuffer1 = create_2d_mbuffer(n); - auto mbuffer2 = create_2d_mbuffer(n); - auto mbuffer3 = create_2d_mbuffer(n); + auto mbuffer1 = create_test_mbuffer<R>(n); + auto mbuffer2 = create_test_mbuffer<R>(n); + auto mbuffer3 = create_test_mbuffer<R>(n); - auto shard1 = new Shard(mbuffer1); - auto shard2 = new Shard(mbuffer2); - auto shard3 = new Shard(mbuffer3); + auto shard1 = new Shard(mbuffer1->get_buffer_view()); + auto shard2 = new Shard(mbuffer2->get_buffer_view()); + auto shard3 = new Shard(mbuffer3->get_buffer_view()); - Shard* shards[3] = {shard1, shard2, shard3}; - auto shard4 = new Shard(shards, 3); + std::vector<Shard *> 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); @@ -69,19 +70,23 @@ START_TEST(t_point_lookup) { size_t n = 16; - auto buffer = create_2d_sequential_mbuffer(n); - auto wss = Shard(buffer); + auto buffer = create_sequential_mbuffer<R>(0, n); + auto wss = Shard(buffer->get_buffer_view()); - for (size_t i=0; i<n; i++) { - PRec r; - auto rec = (buffer->get_data() + i); - r.data[0] = rec->rec.data[0]; - r.data[1] = rec->rec.data[1]; + { + auto bv = buffer->get_buffer_view(); - auto result = wss.point_lookup(r); - ck_assert_ptr_nonnull(result); - ck_assert_int_eq(result->rec.data[0], r.data[0]); - ck_assert_int_eq(result->rec.data[1], r.data[1]); + for (size_t i=0; i<n; i++) { + PRec r; + auto rec = (bv.get(i)); + r.data[0] = rec->rec.data[0]; + r.data[1] = rec->rec.data[1]; + + auto result = wss.point_lookup(r); + ck_assert_ptr_nonnull(result); + ck_assert_int_eq(result->rec.data[0], r.data[0]); + ck_assert_int_eq(result->rec.data[1], r.data[1]); + } } delete buffer; @@ -93,8 +98,8 @@ START_TEST(t_point_lookup_miss) { size_t n = 10000; - auto buffer = create_2d_sequential_mbuffer(n); - auto wss = Shard(buffer); + auto buffer = create_sequential_mbuffer<R>(0, n); + auto wss = Shard(buffer->get_buffer_view()); for (size_t i=n + 100; i<2*n; i++) { PRec r; @@ -112,24 +117,27 @@ START_TEST(t_point_lookup_miss) START_TEST(t_buffer_query) { size_t n = 10000; - auto buffer = create_2d_sequential_mbuffer(n); + auto buffer = create_sequential_mbuffer<R>(0, n); PRec target; target.data[0] = 120; target.data[1] = 120; - KNNQueryParms<PRec> p; + knn::Parms<PRec> p; p.k = 10; p.point = target; - auto state = KNNQuery<PRec>::get_buffer_query_state(buffer, &p); - auto result = KNNQuery<PRec>::buffer_query(buffer, state, &p); - KNNQuery<PRec>::delete_buffer_query_state(state); + { + auto bv = buffer->get_buffer_view(); + auto state = knn::Query<PRec, Shard>::get_buffer_query_state(&bv, &p); + auto result = knn::Query<PRec, Shard>::buffer_query(state, &p); + knn::Query<PRec, Shard>::delete_buffer_query_state(state); - std::sort(result.begin(), result.end()); - size_t start = 120 - 5; - for (size_t i=0; i<result.size(); i++) { - ck_assert_int_eq(result[i].rec.data[0], start++); + std::sort(result.begin(), result.end()); + size_t start = 120 - 5; + for (size_t i=0; i<result.size(); i++) { + ck_assert_int_eq(result[i].rec.data[0], start++); + } } delete buffer; @@ -138,19 +146,19 @@ START_TEST(t_buffer_query) START_TEST(t_knn_query) { size_t n = 1000; - auto buffer = create_2d_sequential_mbuffer(n); + auto buffer = create_sequential_mbuffer<R>(0, n); - auto vptree = VPTree<PRec>(buffer); + auto vptree = VPTree<PRec>(buffer->get_buffer_view()); - KNNQueryParms<PRec> p; + knn::Parms<PRec> p; for (size_t i=0; i<100; i++) { p.k = rand() % 150; p.point.data[0] = rand() % (n-p.k); p.point.data[1] = p.point.data[0]; - auto state = KNNQuery<PRec>::get_query_state(&vptree, &p); - auto results = KNNQuery<PRec>::query(&vptree, state, &p); - KNNQuery<PRec>::delete_query_state(state); + auto state = knn::Query<PRec, Shard>::get_query_state(&vptree, &p); + auto results = knn::Query<PRec, Shard>::query(&vptree, state, &p); + knn::Query<PRec, Shard>::delete_query_state(state); ck_assert_int_eq(results.size(), p.k); diff --git a/tests/wirs_tests.cpp b/tests/wirs_tests.cpp deleted file mode 100644 index a72f950..0000000 --- a/tests/wirs_tests.cpp +++ /dev/null @@ -1,394 +0,0 @@ -/* - * tests/wirs_tests.cpp - * - * Unit tests for WIRS (Augmented B+Tree) shard - * - * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> - * Dong Xie <dongx@psu.edu> - * - * All rights reserved. Published under the Modified BSD License. - * - */ - -#include "shard/WIRS.h" -#include "testing.h" - -#include <check.h> - -using namespace de; - -typedef WIRS<WRec> Shard; - -START_TEST(t_mbuffer_init) -{ - auto buffer = new MutableBuffer<WRec>(1024, 1024); - for (uint64_t i = 512; i > 0; i--) { - uint32_t v = i; - buffer->append({i,v, 1}); - } - - for (uint64_t i = 1; i <= 256; ++i) { - uint32_t v = i; - buffer->append({i, v, 1}, true); - } - - for (uint64_t i = 257; i <= 512; ++i) { - uint32_t v = i + 1; - buffer->append({i, v, 1}); - } - - Shard* shard = new Shard(buffer); - ck_assert_uint_eq(shard->get_record_count(), 512); - - delete buffer; - delete shard; -} - - -START_TEST(t_wirs_init) -{ - size_t n = 512; - auto mbuffer1 = create_test_mbuffer<WRec>(n); - auto mbuffer2 = create_test_mbuffer<WRec>(n); - auto mbuffer3 = create_test_mbuffer<WRec>(n); - - auto shard1 = new Shard(mbuffer1); - auto shard2 = new Shard(mbuffer2); - auto shard3 = new Shard(mbuffer3); - - Shard* shards[3] = {shard1, shard2, shard3}; - auto shard4 = new Shard(shards, 3); - - 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_double_seq_mbuffer<WRec>(n, false); - auto wirs = Shard(buffer); - - for (size_t i=0; i<n; i++) { - WRec r; - auto rec = (buffer->get_data() + i); - r.key = rec->rec.key; - r.value = rec->rec.value; - - auto result = wirs.point_lookup(r); - ck_assert_ptr_nonnull(result); - ck_assert_int_eq(result->rec.key, r.key); - ck_assert_int_eq(result->rec.value, r.value); - } - - delete buffer; -} -END_TEST - - -START_TEST(t_point_lookup_miss) -{ - size_t n = 10000; - - auto buffer = create_double_seq_mbuffer<WRec>(n, false); - auto wirs = Shard(buffer); - - for (size_t i=n + 100; i<2*n; i++) { - WRec r; - r.key = i; - r.value = i; - - auto result = wirs.point_lookup(r); - ck_assert_ptr_null(result); - } - - delete buffer; -} - - -START_TEST(t_full_cancelation) -{ - size_t n = 100; - auto buffer = create_double_seq_mbuffer<WRec>(n, false); - auto buffer_ts = create_double_seq_mbuffer<WRec>(n, true); - - Shard* shard = new Shard(buffer); - Shard* shard_ts = new Shard(buffer_ts); - - ck_assert_int_eq(shard->get_record_count(), n); - ck_assert_int_eq(shard->get_tombstone_count(), 0); - ck_assert_int_eq(shard_ts->get_record_count(), n); - ck_assert_int_eq(shard_ts->get_tombstone_count(), n); - - Shard* shards[] = {shard, shard_ts}; - - Shard* merged = new Shard(shards, 2); - - ck_assert_int_eq(merged->get_tombstone_count(), 0); - ck_assert_int_eq(merged->get_record_count(), 0); - - delete buffer; - delete buffer_ts; - delete shard; - delete shard_ts; - delete merged; -} -END_TEST - - -START_TEST(t_wirs_query) -{ - size_t n=1000; - auto buffer = create_weighted_mbuffer<WRec>(n); - - Shard* shard = new Shard(buffer); - - uint64_t lower_key = 0; - uint64_t upper_key = 5; - - size_t k = 1000; - - size_t cnt[3] = {0}; - wirs_query_parms<WRec> parms = {lower_key, upper_key, k}; - parms.rng = gsl_rng_alloc(gsl_rng_mt19937); - - size_t total_samples = 0; - - for (size_t i=0; i<1000; i++) { - auto state = WIRSQuery<WRec>::get_query_state(shard, &parms); - ((WIRSState<WRec> *) state)->sample_size = k; - auto result = WIRSQuery<WRec>::query(shard, state, &parms); - - total_samples += result.size(); - - for (size_t j=0; j<result.size(); j++) { - cnt[result[j].rec.key - 1]++; - } - - WIRSQuery<WRec>::delete_query_state(state); - } - - ck_assert(roughly_equal(cnt[0], (double) total_samples/4.0, total_samples, .05)); - ck_assert(roughly_equal(cnt[1], (double) total_samples/4.0, total_samples, .05)); - ck_assert(roughly_equal(cnt[2], (double) total_samples/2.0, total_samples, .05)); - - gsl_rng_free(parms.rng); - delete shard; - delete buffer; -} -END_TEST - - -START_TEST(t_wirs_query_merge) -{ - size_t n=1000; - auto buffer = create_weighted_mbuffer<WRec>(n); - - Shard* shard = new Shard(buffer); - - uint64_t lower_key = 0; - uint64_t upper_key = 5; - - size_t k = 1000; - - size_t cnt[3] = {0}; - wirs_query_parms<WRec> parms = {lower_key, upper_key, k}; - parms.rng = gsl_rng_alloc(gsl_rng_mt19937); - - std::vector<std::vector<Wrapped<WRec>>> results(2); - - for (size_t i=0; i<1000; i++) { - auto state1 = WIRSQuery<WRec>::get_query_state(shard, &parms); - ((WIRSState<WRec> *) state1)->sample_size = k; - results[0] = WIRSQuery<WRec>::query(shard, state1, &parms); - - auto state2 = WIRSQuery<WRec>::get_query_state(shard, &parms); - ((WIRSState<WRec> *) state2)->sample_size = k; - results[1] = WIRSQuery<WRec>::query(shard, state2, &parms); - - WIRSQuery<WRec>::delete_query_state(state1); - WIRSQuery<WRec>::delete_query_state(state2); - } - - auto merged = WIRSQuery<WRec>::merge(results, nullptr); - - ck_assert_int_eq(merged.size(), 2*k); - for (size_t i=0; i<merged.size(); i++) { - ck_assert_int_ge(merged[i].key, lower_key); - ck_assert_int_le(merged[i].key, upper_key); - } - - gsl_rng_free(parms.rng); - delete shard; - delete buffer; -} -END_TEST - - -START_TEST(t_wirs_buffer_query_scan) -{ - size_t n=1000; - auto buffer = create_weighted_mbuffer<WRec>(n); - - uint64_t lower_key = 0; - uint64_t upper_key = 5; - - size_t k = 1000; - - size_t cnt[3] = {0}; - wirs_query_parms<WRec> parms = {lower_key, upper_key, k}; - parms.rng = gsl_rng_alloc(gsl_rng_mt19937); - - size_t total_samples = 0; - - for (size_t i=0; i<1000; i++) { - auto state = WIRSQuery<WRec, false>::get_buffer_query_state(buffer, &parms); - ((WIRSBufferState<WRec> *) state)->sample_size = k; - auto result = WIRSQuery<WRec, false>::buffer_query(buffer, state, &parms); - - total_samples += result.size(); - - for (size_t j=0; j<result.size(); j++) { - cnt[result[j].rec.key - 1]++; - } - - WIRSQuery<WRec, false>::delete_buffer_query_state(state); - } - - ck_assert(roughly_equal(cnt[0], (double) total_samples/4.0, total_samples, .05)); - ck_assert(roughly_equal(cnt[1], (double) total_samples/4.0, total_samples, .05)); - ck_assert(roughly_equal(cnt[2], (double) total_samples/2.0, total_samples, .05)); - - gsl_rng_free(parms.rng); - delete buffer; -} -END_TEST - - -START_TEST(t_wirs_buffer_query_rejection) -{ - size_t n=1000; - auto buffer = create_weighted_mbuffer<WRec>(n); - - uint64_t lower_key = 0; - uint64_t upper_key = 5; - - size_t k = 1000; - - size_t cnt[3] = {0}; - wirs_query_parms<WRec> parms = {lower_key, upper_key, k}; - parms.rng = gsl_rng_alloc(gsl_rng_mt19937); - - size_t total_samples = 0; - - for (size_t i=0; i<1000; i++) { - auto state = WIRSQuery<WRec>::get_buffer_query_state(buffer, &parms); - ((WIRSBufferState<WRec> *) state)->sample_size = k; - auto result = WIRSQuery<WRec>::buffer_query(buffer, state, &parms); - - total_samples += result.size(); - - for (size_t j=0; j<result.size(); j++) { - cnt[result[j].rec.key - 1]++; - } - - WIRSQuery<WRec>::delete_buffer_query_state(state); - } - - ck_assert(roughly_equal(cnt[0], (double) total_samples/4.0, total_samples, .05)); - ck_assert(roughly_equal(cnt[1], (double) total_samples/4.0, total_samples, .05)); - ck_assert(roughly_equal(cnt[2], (double) total_samples/2.0, total_samples, .05)); - - gsl_rng_free(parms.rng); - delete buffer; -} -END_TEST - - -Suite *unit_testing() -{ - Suite *unit = suite_create("WIRS Shard Unit Testing"); - - TCase *create = tcase_create("de::WIRS constructor Testing"); - tcase_add_test(create, t_mbuffer_init); - tcase_add_test(create, t_wirs_init); - tcase_set_timeout(create, 100); - suite_add_tcase(unit, create); - - - TCase *tombstone = tcase_create("de:WIRS::tombstone cancellation Testing"); - tcase_add_test(tombstone, t_full_cancelation); - suite_add_tcase(unit, tombstone); - - - TCase *lookup = tcase_create("de:WIRS:point_lookup Testing"); - tcase_add_test(lookup, t_point_lookup); - tcase_add_test(lookup, t_point_lookup_miss); - suite_add_tcase(unit, lookup); - - - TCase *sampling = tcase_create("de:WIRS::WIRSQuery Testing"); - tcase_add_test(sampling, t_wirs_query); - tcase_add_test(sampling, t_wirs_query_merge); - tcase_add_test(sampling, t_wirs_buffer_query_rejection); - tcase_add_test(sampling, t_wirs_buffer_query_scan); - suite_add_tcase(unit, sampling); - - return unit; -} - - -int shard_unit_tests() -{ - int failed = 0; - Suite *unit = unit_testing(); - SRunner *unit_shardner = srunner_create(unit); - - srunner_run_all(unit_shardner, CK_NORMAL); - failed = srunner_ntests_failed(unit_shardner); - srunner_free(unit_shardner); - - return failed; -} - - -int main() -{ - int unit_failed = shard_unit_tests(); - - return (unit_failed == 0) ? EXIT_SUCCESS : EXIT_FAILURE; -} diff --git a/tests/wss_tests.cpp b/tests/wss_tests.cpp deleted file mode 100644 index cdc8001..0000000 --- a/tests/wss_tests.cpp +++ /dev/null @@ -1,390 +0,0 @@ -/* - * tests/wss_tests.cpp - * - * Unit tests for WSS (Augmented B+Tree) shard - * - * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> - * Dong Xie <dongx@psu.edu> - * - * All rights reserved. Published under the Modified BSD License. - * - */ - -#include "shard/WSS.h" -#include "testing.h" - -#include <check.h> - -using namespace de; - -typedef WSS<WRec> Shard; - -START_TEST(t_mbuffer_init) -{ - auto buffer = new MutableBuffer<WRec>(1024, 1024); - for (uint64_t i = 512; i > 0; i--) { - uint32_t v = i; - buffer->append({i,v, 1}); - } - - for (uint64_t i = 1; i <= 256; ++i) { - uint32_t v = i; - buffer->append({i, v, 1}, true); - } - - for (uint64_t i = 257; i <= 512; ++i) { - uint32_t v = i + 1; - buffer->append({i, v, 1}); - } - - Shard* shard = new Shard(buffer); - ck_assert_uint_eq(shard->get_record_count(), 512); - - delete buffer; - delete shard; -} - - -START_TEST(t_wss_init) -{ - size_t n = 512; - auto mbuffer1 = create_test_mbuffer<WRec>(n); - auto mbuffer2 = create_test_mbuffer<WRec>(n); - auto mbuffer3 = create_test_mbuffer<WRec>(n); - - auto shard1 = new Shard(mbuffer1); - auto shard2 = new Shard(mbuffer2); - auto shard3 = new Shard(mbuffer3); - - Shard* shards[3] = {shard1, shard2, shard3}; - auto shard4 = new Shard(shards, 3); - - 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_double_seq_mbuffer<WRec>(n, false); - auto wss = Shard(buffer); - - for (size_t i=0; i<n; i++) { - WRec r; - auto rec = (buffer->get_data() + i); - r.key = rec->rec.key; - r.value = rec->rec.value; - - auto result = wss.point_lookup(r); - ck_assert_ptr_nonnull(result); - ck_assert_int_eq(result->rec.key, r.key); - ck_assert_int_eq(result->rec.value, r.value); - } - - delete buffer; -} -END_TEST - - -START_TEST(t_point_lookup_miss) -{ - size_t n = 10000; - - auto buffer = create_double_seq_mbuffer<WRec>(n, false); - auto wss = Shard(buffer); - - for (size_t i=n + 100; i<2*n; i++) { - WRec r; - r.key = i; - r.value = i; - - auto result = wss.point_lookup(r); - ck_assert_ptr_null(result); - } - - delete buffer; -} - -START_TEST(t_full_cancelation) -{ - size_t n = 100; - auto buffer = create_double_seq_mbuffer<WRec>(n, false); - auto buffer_ts = create_double_seq_mbuffer<WRec>(n, true); - - Shard* shard = new Shard(buffer); - Shard* shard_ts = new Shard(buffer_ts); - - ck_assert_int_eq(shard->get_record_count(), n); - ck_assert_int_eq(shard->get_tombstone_count(), 0); - ck_assert_int_eq(shard_ts->get_record_count(), n); - ck_assert_int_eq(shard_ts->get_tombstone_count(), n); - - Shard* shards[] = {shard, shard_ts}; - - Shard* merged = new Shard(shards, 2); - - ck_assert_int_eq(merged->get_tombstone_count(), 0); - ck_assert_int_eq(merged->get_record_count(), 0); - - delete buffer; - delete buffer_ts; - delete shard; - delete shard_ts; - delete merged; -} -END_TEST - - -START_TEST(t_wss_query) -{ - size_t n=1000; - auto buffer = create_weighted_mbuffer<WRec>(n); - - Shard* shard = new Shard(buffer); - - size_t k = 1000; - - size_t cnt[3] = {0}; - wss_query_parms<WRec> parms = {k}; - parms.rng = gsl_rng_alloc(gsl_rng_mt19937); - - size_t total_samples = 0; - - for (size_t i=0; i<1000; i++) { - auto state = WSSQuery<WRec>::get_query_state(shard, &parms); - ((WSSState<WRec> *) state)->sample_size = k; - auto result = WSSQuery<WRec>::query(shard, state, &parms); - - total_samples += result.size(); - - for (size_t j=0; j<result.size(); j++) { - cnt[result[j].rec.key - 1]++; - } - - WSSQuery<WRec>::delete_query_state(state); - } - - ck_assert(roughly_equal(cnt[0], (double) total_samples/4.0, total_samples, .05)); - ck_assert(roughly_equal(cnt[1], (double) total_samples/4.0, total_samples, .05)); - ck_assert(roughly_equal(cnt[2], (double) total_samples/2.0, total_samples, .05)); - - gsl_rng_free(parms.rng); - delete shard; - delete buffer; -} -END_TEST - - -START_TEST(t_wss_query_merge) -{ - size_t n=1000; - auto buffer = create_weighted_mbuffer<WRec>(n); - - Shard* shard = new Shard(buffer); - - uint64_t lower_key = 0; - uint64_t upper_key = 5; - - size_t k = 1000; - - size_t cnt[3] = {0}; - wss_query_parms<WRec> parms = {k}; - parms.rng = gsl_rng_alloc(gsl_rng_mt19937); - - std::vector<std::vector<Wrapped<WRec>>> results(2); - - for (size_t i=0; i<1000; i++) { - auto state1 = WSSQuery<WRec>::get_query_state(shard, &parms); - ((WSSState<WRec> *) state1)->sample_size = k; - results[0] = WSSQuery<WRec>::query(shard, state1, &parms); - - auto state2 = WSSQuery<WRec>::get_query_state(shard, &parms); - ((WSSState<WRec> *) state2)->sample_size = k; - results[1] = WSSQuery<WRec>::query(shard, state2, &parms); - - WSSQuery<WRec>::delete_query_state(state1); - WSSQuery<WRec>::delete_query_state(state2); - } - - auto merged = WSSQuery<WRec>::merge(results, nullptr); - - ck_assert_int_eq(merged.size(), 2*k); - for (size_t i=0; i<merged.size(); i++) { - ck_assert_int_ge(merged[i].key, lower_key); - ck_assert_int_le(merged[i].key, upper_key); - } - - gsl_rng_free(parms.rng); - delete shard; - delete buffer; -} -END_TEST - - -START_TEST(t_wss_buffer_query_scan) -{ - size_t n=1000; - auto buffer = create_weighted_mbuffer<WRec>(n); - - uint64_t lower_key = 0; - uint64_t upper_key = 5; - - size_t k = 1000; - - size_t cnt[3] = {0}; - wss_query_parms<WRec> parms = {k}; - parms.rng = gsl_rng_alloc(gsl_rng_mt19937); - - size_t total_samples = 0; - - for (size_t i=0; i<1000; i++) { - auto state = WSSQuery<WRec, false>::get_buffer_query_state(buffer, &parms); - ((WSSBufferState<WRec> *) state)->sample_size = k; - auto result = WSSQuery<WRec, false>::buffer_query(buffer, state, &parms); - total_samples += result.size(); - - for (size_t j=0; j<result.size(); j++) { - cnt[result[j].rec.key - 1]++; - } - - WSSQuery<WRec, false>::delete_buffer_query_state(state); - } - - ck_assert(roughly_equal(cnt[0], (double) total_samples/4.0, total_samples, .05)); - ck_assert(roughly_equal(cnt[1], (double) total_samples/4.0, total_samples, .05)); - ck_assert(roughly_equal(cnt[2], (double) total_samples/2.0, total_samples, .05)); - - gsl_rng_free(parms.rng); - delete buffer; -} -END_TEST - - -START_TEST(t_wss_buffer_query_rejection) -{ - size_t n=1000; - auto buffer = create_weighted_mbuffer<WRec>(n); - - uint64_t lower_key = 0; - uint64_t upper_key = 5; - - size_t k = 1000; - - size_t cnt[3] = {0}; - wss_query_parms<WRec> parms = {k}; - parms.rng = gsl_rng_alloc(gsl_rng_mt19937); - - size_t total_samples = 0; - - for (size_t i=0; i<1000; i++) { - auto state = WSSQuery<WRec>::get_buffer_query_state(buffer, &parms); - ((WSSBufferState<WRec> *) state)->sample_size = k; - auto result = WSSQuery<WRec>::buffer_query(buffer, state, &parms); - - total_samples += result.size(); - - for (size_t j=0; j<result.size(); j++) { - cnt[result[j].rec.key - 1]++; - } - - WSSQuery<WRec>::delete_buffer_query_state(state); - } - - ck_assert(roughly_equal(cnt[0], (double) total_samples/4.0, total_samples, .1)); - ck_assert(roughly_equal(cnt[1], (double) total_samples/4.0, total_samples, .1)); - ck_assert(roughly_equal(cnt[2], (double) total_samples/2.0, total_samples, .1)); - - gsl_rng_free(parms.rng); - delete buffer; -} -END_TEST - - -Suite *unit_testing() -{ - Suite *unit = suite_create("WSS Shard Unit Testing"); - - TCase *create = tcase_create("de::WSS constructor Testing"); - tcase_add_test(create, t_mbuffer_init); - tcase_add_test(create, t_wss_init); - tcase_set_timeout(create, 100); - suite_add_tcase(unit, create); - - - TCase *tombstone = tcase_create("de:WSS::tombstone cancellation Testing"); - tcase_add_test(tombstone, t_full_cancelation); - suite_add_tcase(unit, tombstone); - - - TCase *lookup = tcase_create("de:WSS:point_lookup Testing"); - tcase_add_test(lookup, t_point_lookup); - tcase_add_test(lookup, t_point_lookup_miss); - suite_add_tcase(unit, lookup); - - - - TCase *sampling = tcase_create("de:WSS::WSSQuery Testing"); - tcase_add_test(sampling, t_wss_query); - tcase_add_test(sampling, t_wss_query_merge); - tcase_add_test(sampling, t_wss_buffer_query_rejection); - tcase_add_test(sampling, t_wss_buffer_query_scan); - suite_add_tcase(unit, sampling); - - return unit; -} - - -int shard_unit_tests() -{ - int failed = 0; - Suite *unit = unit_testing(); - SRunner *unit_shardner = srunner_create(unit); - - srunner_run_all(unit_shardner, CK_NORMAL); - failed = srunner_ntests_failed(unit_shardner); - srunner_free(unit_shardner); - - return failed; -} - - -int main() -{ - int unit_failed = shard_unit_tests(); - - return (unit_failed == 0) ? EXIT_SUCCESS : EXIT_FAILURE; -} |