From 418e9b079e559c86f3a5b276f712ad2f5d66533c Mon Sep 17 00:00:00 2001 From: Douglas Rumbaugh Date: Tue, 9 May 2023 17:59:37 -0400 Subject: Ported over IRS with unit tests --- tests/internal_level_tests.cpp | 8 +- tests/memisam_tests.cpp | 227 +++++++++++++++++++++++++++++++++++++++++ tests/testing.h | 27 +++-- tests/wirs_tests.cpp | 14 +-- 4 files changed, 254 insertions(+), 22 deletions(-) create mode 100644 tests/memisam_tests.cpp (limited to 'tests') diff --git a/tests/internal_level_tests.cpp b/tests/internal_level_tests.cpp index 051bb7c..7e542e6 100644 --- a/tests/internal_level_tests.cpp +++ b/tests/internal_level_tests.cpp @@ -20,8 +20,8 @@ using namespace de; START_TEST(t_memlevel_merge) { - auto tbl1 = create_test_mbuffer(100); - auto tbl2 = create_test_mbuffer(100); + auto tbl1 = create_test_mbuffer(100); + auto tbl2 = create_test_mbuffer(100); auto base_level = new WeightedLevel(1, 1, false); base_level->append_mem_table(tbl1, g_rng); @@ -45,8 +45,8 @@ START_TEST(t_memlevel_merge) WeightedLevel *create_test_memlevel(size_t reccnt) { - auto tbl1 = create_test_mbuffer(reccnt/2); - auto tbl2 = create_test_mbuffer(reccnt/2); + auto tbl1 = create_test_mbuffer(reccnt/2); + auto tbl2 = create_test_mbuffer(reccnt/2); auto base_level = new WeightedLevel(1, 2, false); base_level->append_mem_table(tbl1, g_rng); diff --git a/tests/memisam_tests.cpp b/tests/memisam_tests.cpp new file mode 100644 index 0000000..f3b80b3 --- /dev/null +++ b/tests/memisam_tests.cpp @@ -0,0 +1,227 @@ + +#include "shard/MemISAM.h" +#include "framework/InternalLevel.h" +#include "util/bf_config.h" +#include "testing.h" + +#include + +using namespace de; + +typedef MemISAM M_ISAM; + +START_TEST(t_memtable_init) +{ + auto buffer = new UnweightedMBuffer(1024, true, 512, g_rng); + for (uint64_t i = 512; i > 0; i--) { + uint32_t v = i; + buffer->append(i, v); + } + + for (uint64_t i = 1; i <= 256; ++i) { + uint32_t v = i; + buffer->append(i, v, true); + } + + for (uint64_t i = 257; i <= 512; ++i) { + uint32_t v = i + 1; + buffer->append(i, v); + } + + BloomFilter* bf = new BloomFilter(BF_FPR, buffer->get_tombstone_count(), BF_HASH_FUNCS, g_rng); + M_ISAM* run = new M_ISAM(buffer, bf, false); + ck_assert_uint_eq(run->get_record_count(), 512); + + delete bf; + delete buffer; + delete run; +} + +START_TEST(t_inmemrun_init) +{ + size_t n = 512; + auto memtable1 = create_test_mbuffer(n); + auto memtable2 = create_test_mbuffer(n); + auto memtable3 = create_test_mbuffer(n); + + BloomFilter* bf1 = new BloomFilter(100, BF_HASH_FUNCS, g_rng); + BloomFilter* bf2 = new BloomFilter(100, BF_HASH_FUNCS, g_rng); + BloomFilter* bf3 = new BloomFilter(100, BF_HASH_FUNCS, g_rng); + auto run1 = new M_ISAM(memtable1, bf1, false); + auto run2 = new M_ISAM(memtable2, bf2, false); + auto run3 = new M_ISAM(memtable3, bf3, false); + + BloomFilter* bf4 = new BloomFilter(100, BF_HASH_FUNCS, g_rng); + M_ISAM* runs[3] = {run1, run2, run3}; + auto run4 = new M_ISAM(runs, 3, bf4, false); + + ck_assert_int_eq(run4->get_record_count(), n * 3); + ck_assert_int_eq(run4->get_tombstone_count(), 0); + + size_t total_cnt = 0; + size_t run1_idx = 0; + size_t run2_idx = 0; + size_t run3_idx = 0; + + for (size_t i = 0; i < run4->get_record_count(); ++i) { + auto rec1 = run1->get_record_at(run1_idx); + auto rec2 = run2->get_record_at(run2_idx); + auto rec3 = run3->get_record_at(run3_idx); + + auto cur_rec = run4->get_record_at(i); + + if (run1_idx < n && cur_rec->match(rec1)) { + ++run1_idx; + } else if (run2_idx < n && cur_rec->match(rec2)) { + ++run2_idx; + } else if (run3_idx < n && cur_rec->match(rec3)) { + ++run3_idx; + } else { + assert(false); + } + } + + delete memtable1; + delete memtable2; + delete memtable3; + + delete bf1; + delete run1; + delete bf2; + delete run2; + delete bf3; + delete run3; + delete bf4; + delete run4; +} + +START_TEST(t_get_lower_bound_index) +{ + size_t n = 10000; + auto memtable = create_double_seq_mbuffer(n); + + ck_assert_ptr_nonnull(memtable); + BloomFilter* bf = new BloomFilter(100, BF_HASH_FUNCS, g_rng); + M_ISAM* run = new M_ISAM(memtable, bf, false); + + ck_assert_int_eq(run->get_record_count(), n); + ck_assert_int_eq(run->get_tombstone_count(), 0); + + auto tbl_records = memtable->sorted_output(); + for (size_t i=0; iget_record_at(i); + auto pos = run->get_lower_bound(tbl_rec->key); + ck_assert_int_eq(run->get_record_at(pos)->key, tbl_rec->key); + ck_assert_int_le(pos, i); + } + + delete memtable; + delete bf; + delete run; +} + +START_TEST(t_get_upper_bound_index) +{ + size_t n = 10000; + auto memtable = create_double_seq_mbuffer(n); + + ck_assert_ptr_nonnull(memtable); + BloomFilter* bf = new BloomFilter(100, BF_HASH_FUNCS, g_rng); + M_ISAM* run = new M_ISAM(memtable, bf, false); + + ck_assert_int_eq(run->get_record_count(), n); + ck_assert_int_eq(run->get_tombstone_count(), 0); + + auto tbl_records = memtable->sorted_output(); + for (size_t i=0; iget_record_at(i); + auto pos = run->get_upper_bound(tbl_rec->key); + ck_assert(pos == run->get_record_count() || + run->get_record_at(pos)->key > tbl_rec->key); + ck_assert_int_ge(pos, i); + } + + delete memtable; + delete bf; + delete run; +} + + +START_TEST(t_full_cancelation) +{ + size_t n = 100; + auto mtable = create_double_seq_mbuffer(n, false); + auto mtable_ts = create_double_seq_mbuffer(n, true); + BloomFilter* bf1 = new BloomFilter(100, BF_HASH_FUNCS, g_rng); + BloomFilter* bf2 = new BloomFilter(100, BF_HASH_FUNCS, g_rng); + BloomFilter* bf3 = new BloomFilter(100, BF_HASH_FUNCS, g_rng); + + M_ISAM* run = new M_ISAM(mtable, bf1, false); + M_ISAM* run_ts = new M_ISAM(mtable_ts, bf2, false); + + ck_assert_int_eq(run->get_record_count(), n); + ck_assert_int_eq(run->get_tombstone_count(), 0); + ck_assert_int_eq(run_ts->get_record_count(), n); + ck_assert_int_eq(run_ts->get_tombstone_count(), n); + + M_ISAM* runs[] = {run, run_ts}; + + M_ISAM* merged = new M_ISAM(runs, 2, bf3, false); + + ck_assert_int_eq(merged->get_tombstone_count(), 0); + ck_assert_int_eq(merged->get_record_count(), 0); + + delete mtable; + delete mtable_ts; + delete bf1; + delete bf2; + delete bf3; + delete run; + delete run_ts; + delete merged; +} +END_TEST + +Suite *unit_testing() +{ + Suite *unit = suite_create("M_ISAM Unit Testing"); + + TCase *create = tcase_create("lsm::M_ISAM constructor Testing"); + tcase_add_test(create, t_memtable_init); + tcase_add_test(create, t_inmemrun_init); + tcase_set_timeout(create, 100); + suite_add_tcase(unit, create); + + TCase *bounds = tcase_create("lsm::M_ISAM::get_{lower,upper}_bound Testing"); + tcase_add_test(bounds, t_get_lower_bound_index); + tcase_add_test(bounds, t_get_upper_bound_index); + tcase_set_timeout(bounds, 100); + suite_add_tcase(unit, bounds); + + TCase *tombstone = tcase_create("lsm::M_ISAM::tombstone cancellation Testing"); + tcase_add_test(tombstone, t_full_cancelation); + suite_add_tcase(unit, tombstone); + + 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/testing.h b/tests/testing.h index d200e8f..062e930 100644 --- a/tests/testing.h +++ b/tests/testing.h @@ -72,9 +72,10 @@ static bool roughly_equal(int n1, int n2, size_t mag, double epsilon) { return ((double) std::abs(n1 - n2) / (double) mag) < epsilon; } -static WeightedMBuffer *create_test_mbuffer(size_t cnt) +template +static de::MutableBuffer *create_test_mbuffer(size_t cnt) { - auto buffer = new WeightedMBuffer(cnt, true, cnt, g_rng); + auto buffer = new de::MutableBuffer(cnt, true, cnt, g_rng); for (size_t i = 0; i < cnt; i++) { uint64_t key = rand(); @@ -86,9 +87,10 @@ static WeightedMBuffer *create_test_mbuffer(size_t cnt) return buffer; } -static WeightedMBuffer *create_test_mbuffer_tombstones(size_t cnt, size_t ts_cnt) +template +static de::MutableBuffer *create_test_mbuffer_tombstones(size_t cnt, size_t ts_cnt) { - auto buffer = new WeightedMBuffer(cnt, true, ts_cnt, g_rng); + auto buffer = new de::MutableBuffer(cnt, true, ts_cnt, g_rng); std::vector> tombstones; @@ -104,15 +106,17 @@ static WeightedMBuffer *create_test_mbuffer_tombstones(size_t cnt, size_t ts_cnt } for (size_t i=0; iappend(tombstones[i].first, tombstones[i].second, 1.0, true); + buffer->append(tombstones[i].first, tombstones[i].second, true); } return buffer; } -static WeightedMBuffer *create_weighted_mbuffer(size_t cnt) +template +static de::MutableBuffer *create_weighted_mbuffer(size_t cnt) { - auto buffer = new WeightedMBuffer(cnt, true, cnt, g_rng); + static_assert(!std::is_same::value); + auto buffer = new de::MutableBuffer(cnt, true, cnt, g_rng); // Put in half of the count with weight one. uint64_t key = 1; @@ -135,22 +139,23 @@ static WeightedMBuffer *create_weighted_mbuffer(size_t cnt) return buffer; } -static WeightedMBuffer *create_double_seq_mbuffer(size_t cnt, bool ts=false) +template +static de::MutableBuffer *create_double_seq_mbuffer(size_t cnt, bool ts=false) { - auto buffer = new WeightedMBuffer(cnt, true, cnt, g_rng); + auto buffer = new de::MutableBuffer(cnt, true, cnt, g_rng); for (size_t i = 0; i < cnt / 2; i++) { uint64_t key = i; uint32_t val = i; - buffer->append(key, val, 1.0, ts); + buffer->append(key, val, ts); } for (size_t i = 0; i < cnt / 2; i++) { uint64_t key = i; uint32_t val = i + 1; - buffer->append(key, val, 1.0, ts); + buffer->append(key, val, ts); } return buffer; diff --git a/tests/wirs_tests.cpp b/tests/wirs_tests.cpp index fe026d1..ed83d40 100644 --- a/tests/wirs_tests.cpp +++ b/tests/wirs_tests.cpp @@ -51,9 +51,9 @@ START_TEST(t_mbuffer_init) START_TEST(t_wirs_init) { size_t n = 512; - auto mbuffer1 = create_test_mbuffer(n); - auto mbuffer2 = create_test_mbuffer(n); - auto mbuffer3 = create_test_mbuffer(n); + auto mbuffer1 = create_test_mbuffer(n); + auto mbuffer2 = create_test_mbuffer(n); + auto mbuffer3 = create_test_mbuffer(n); BloomFilter* bf1 = new BloomFilter(100, BF_HASH_FUNCS, g_rng); BloomFilter* bf2 = new BloomFilter(100, BF_HASH_FUNCS, g_rng); @@ -109,7 +109,7 @@ START_TEST(t_wirs_init) START_TEST(t_get_lower_bound_index) { size_t n = 10000; - auto mbuffer = create_double_seq_mbuffer(n); + auto mbuffer = create_double_seq_mbuffer(n); ck_assert_ptr_nonnull(mbuffer); BloomFilter* bf = new BloomFilter(100, BF_HASH_FUNCS, g_rng); @@ -135,8 +135,8 @@ START_TEST(t_get_lower_bound_index) START_TEST(t_full_cancelation) { size_t n = 100; - auto buffer = create_double_seq_mbuffer(n, false); - auto buffer_ts = create_double_seq_mbuffer(n, true); + auto buffer = create_double_seq_mbuffer(n, false); + auto buffer_ts = create_double_seq_mbuffer(n, true); BloomFilter* bf1 = new BloomFilter(100, BF_HASH_FUNCS, g_rng); BloomFilter* bf2 = new BloomFilter(100, BF_HASH_FUNCS, g_rng); BloomFilter* bf3 = new BloomFilter(100, BF_HASH_FUNCS, g_rng); @@ -171,7 +171,7 @@ END_TEST START_TEST(t_weighted_sampling) { size_t n=1000; - auto buffer = create_weighted_mbuffer(n); + auto buffer = create_weighted_mbuffer(n); BloomFilter* bf = new BloomFilter(100, BF_HASH_FUNCS, g_rng); Shard* shard = new Shard(buffer, bf, false); -- cgit v1.2.3