diff options
| -rw-r--r-- | CMakeLists.txt | 10 | ||||
| -rw-r--r-- | tests/de_level_tag.cpp | 5 | ||||
| -rw-r--r-- | tests/de_level_tomb.cpp | 5 | ||||
| -rw-r--r-- | tests/de_tier_tag.cpp | 5 | ||||
| -rw-r--r-- | tests/de_tier_tomb.cpp | 5 | ||||
| -rw-r--r-- | tests/dynamic_extension_tests.inc | 206 | ||||
| -rw-r--r-- | tests/internal_level_tests.cpp | 13 |
7 files changed, 106 insertions, 143 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt index 13f24d9..c4f28e0 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -29,9 +29,9 @@ if (tests) set(CMAKE_RUNTIME_OUTPUT_DIRECTORY "${CMAKE_CURRENT_SOURCE_DIR}/bin/tests") file(MAKE_DIRECTORY "${CMAKE_CURRENT_SOURCE_DIR}/tests/data") - add_executable(wirs_tests ${CMAKE_CURRENT_SOURCE_DIR}/tests/wirs_tests.cpp) - target_link_libraries(wirs_tests PUBLIC gsl check subunit pthread) - target_include_directories(wirs_tests PRIVATE include external/psudb-common/cpp/include) + add_executable(augbtree_tests ${CMAKE_CURRENT_SOURCE_DIR}/tests/augbtree_tests.cpp) + target_link_libraries(augbtree_tests PUBLIC gsl check subunit pthread) + target_include_directories(augbtree_tests PRIVATE include external/psudb-common/cpp/include) add_executable(internal_level_tests ${CMAKE_CURRENT_SOURCE_DIR}/tests/internal_level_tests.cpp) target_link_libraries(internal_level_tests PUBLIC gsl check subunit pthread) @@ -45,10 +45,6 @@ if (tests) target_link_libraries(vptree_tests PUBLIC gsl check subunit pthread) target_include_directories(vptree_tests PRIVATE include external/vptree external/psudb-common/cpp/include) - #add_executable(dynamic_extension_tests ${CMAKE_CURRENT_SOURCE_DIR}/tests/dynamic_extension_tests.cpp) - #target_link_libraries(dynamic_extension_tests PUBLIC gsl check subunit pthread) - #target_include_directories(dynamic_extension_tests PRIVATE include) - add_executable(de_tier_tag ${CMAKE_CURRENT_SOURCE_DIR}/tests/de_tier_tag.cpp) target_link_libraries(de_tier_tag PUBLIC gsl check subunit pthread) target_include_directories(de_tier_tag PRIVATE include external/psudb-common/cpp/include) diff --git a/tests/de_level_tag.cpp b/tests/de_level_tag.cpp index 822ccc2..f3f099d 100644 --- a/tests/de_level_tag.cpp +++ b/tests/de_level_tag.cpp @@ -15,11 +15,12 @@ #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, SerialScheduler> DE; +typedef DynamicExtension<Rec, ISAMTree<Rec>, rq::Query<ISAMTree<Rec>, Rec>, LayoutPolicy::LEVELING, DeletePolicy::TAGGING, SerialScheduler> DE; #include "dynamic_extension_tests.inc" diff --git a/tests/de_level_tomb.cpp b/tests/de_level_tomb.cpp index 264b5b0..912743c 100644 --- a/tests/de_level_tomb.cpp +++ b/tests/de_level_tomb.cpp @@ -15,11 +15,12 @@ #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::TOMBSTONE, SerialScheduler> DE; +typedef DynamicExtension<Rec, ISAMTree<Rec>, rq::Query<ISAMTree<Rec>, Rec>, LayoutPolicy::LEVELING, DeletePolicy::TOMBSTONE, SerialScheduler> DE; #include "dynamic_extension_tests.inc" diff --git a/tests/de_tier_tag.cpp b/tests/de_tier_tag.cpp index 2c263eb..712c203 100644 --- a/tests/de_tier_tag.cpp +++ b/tests/de_tier_tag.cpp @@ -16,11 +16,12 @@ #include "testing.h" #include "framework/DynamicExtension.h" #include "framework/scheduling/SerialScheduler.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::TEIRING, DeletePolicy::TAGGING, SerialScheduler> DE; +typedef DynamicExtension<Rec, ISAMTree<Rec>, rq::Query<ISAMTree<Rec>, Rec>, LayoutPolicy::TEIRING, DeletePolicy::TAGGING, SerialScheduler> DE; #include "dynamic_extension_tests.inc" diff --git a/tests/de_tier_tomb.cpp b/tests/de_tier_tomb.cpp index 509494a..f25ec34 100644 --- a/tests/de_tier_tomb.cpp +++ b/tests/de_tier_tomb.cpp @@ -15,11 +15,12 @@ #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::TEIRING, DeletePolicy::TOMBSTONE, SerialScheduler> DE; +typedef DynamicExtension<Rec, ISAMTree<Rec>, rq::Query<ISAMTree<Rec>, Rec>, LayoutPolicy::TEIRING, DeletePolicy::TOMBSTONE, SerialScheduler> DE; #include "dynamic_extension_tests.inc" diff --git a/tests/dynamic_extension_tests.inc b/tests/dynamic_extension_tests.inc index 2f82e92..aa12e31 100644 --- a/tests/dynamic_extension_tests.inc +++ b/tests/dynamic_extension_tests.inc @@ -12,75 +12,74 @@ START_TEST(t_create) { - auto ext_wirs = new DE(100, 2, 1); + auto test_de = new DE(100, 2, 1); + 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); - 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; + delete test_de; } END_TEST START_TEST(t_insert) { - auto ext_wirs = new DE(100, 2, 1); + auto test_de = 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); + Rec r = {key, val}; + ck_assert_int_eq(test_de->insert(r), 1); key++; val++; } - ck_assert_int_eq(ext_wirs->get_height(), 0); - ck_assert_int_eq(ext_wirs->get_record_count(), 100); + ck_assert_int_eq(test_de->get_height(), 0); + ck_assert_int_eq(test_de->get_record_count(), 100); - delete ext_wirs; + delete test_de; } END_TEST START_TEST(t_debug_insert) { - auto ext_wirs = new DE(100, 2, 1); + auto test_de = new DE(100, 2, 1); uint64_t key = 0; uint32_t val = 0; for (size_t i=0; i<1000; i++) { - WRec r = {key, val, 1}; - ck_assert_int_eq(ext_wirs->insert(r), 1); - ck_assert_int_eq(ext_wirs->get_record_count(), i+1); + Rec 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 ext_wirs; + delete test_de; } END_TEST START_TEST(t_insert_with_mem_merges) { - auto ext_wirs = new DE(100, 2, 1); + auto test_de = 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); + Rec r = {key, val}; + ck_assert_int_eq(test_de->insert(r), 1); key++; val++; } - ck_assert_int_eq(ext_wirs->get_record_count(), 300); - ck_assert_int_eq(ext_wirs->get_height(), 1); + ck_assert_int_eq(test_de->get_record_count(), 300); + ck_assert_int_eq(test_de->get_height(), 1); - delete ext_wirs; + delete test_de; } END_TEST @@ -88,13 +87,13 @@ END_TEST /* START_TEST(t_range_sample_memtable) { - auto ext_wirs = new DE(100, 2, 1); + auto test_de = 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); + Rec r = {key, val}; + ck_assert_int_eq(test_de->insert(r), 1); key++; val++; } @@ -104,9 +103,9 @@ START_TEST(t_range_sample_memtable) 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]; + Rec sample_set[100]; - ext_wirs->range_sample(sample_set, lower_bound, upper_bound, 100); + test_de->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); @@ -116,20 +115,20 @@ START_TEST(t_range_sample_memtable) free(buf); free(util_buf); - delete ext_wirs; + delete test_de; } END_TEST START_TEST(t_range_sample_memlevels) { - auto ext_wirs = new DE(100, 2, 1); + auto test_de = 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); + Rec r = {key, val}; + ck_assert_int_eq(test_de->insert(r), 1); key++; val++; } @@ -140,8 +139,8 @@ START_TEST(t_range_sample_memlevels) 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); + Rec sample_set[100]; + test_de->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); @@ -151,33 +150,19 @@ START_TEST(t_range_sample_memlevels) free(buf); free(util_buf); - delete ext_wirs; + delete test_de; } END_TEST */ -START_TEST(t_range_sample_weighted) +START_TEST(t_range_query) { - auto ext_wirs = new DE(100, 2, 1); + auto test_de = 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); + for (size_t i=0; i<n; i++) { + keys.push_back(rand() % 25000); } std::random_device rd; @@ -185,48 +170,31 @@ START_TEST(t_range_sample_weighted) 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); + Rec r = {keys[i], (uint32_t) i}; + ck_assert_int_eq(test_de->insert(r), 1); } - size_t k = 1000; - uint64_t lower_key = 0; - uint64_t upper_key = 5; - size_t cnt[3] = {0}; - size_t total_samples = 0; + std::sort(keys.begin(), keys.end()); + + auto idx = rand() % (keys.size() - 250); - wirs_query_parms<WRec> p; + uint64_t lower_key = keys[idx]; + uint64_t upper_key = keys[idx + 250]; + + rq::Parms<Rec> 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); - auto r = result.get(); - total_samples += r.size(); + 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 j=0; j<r.size(); j++) { - cnt[r[j].key - 1]++; - } + for (size_t i=0; i<r.size(); i++) { + ck_assert_int_eq(r[i].key, keys[idx + i]); } - 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; + delete test_de; } END_TEST @@ -234,7 +202,7 @@ END_TEST START_TEST(t_tombstone_merging_01) { size_t reccnt = 100000; - auto ext_wirs = new DE(100, 2, .01); + auto test_de = new DE(100, 2, .01); auto rng = gsl_rng_alloc(gsl_rng_mt19937); @@ -254,16 +222,16 @@ START_TEST(t_tombstone_merging_01) 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); + Rec 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++) { - WRec dr = {del_vec[i].first, del_vec[i].second, 1}; - ext_wirs->erase(dr); + Rec 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]); @@ -274,24 +242,24 @@ START_TEST(t_tombstone_merging_01) to_delete.insert(rec); } - ck_assert(ext_wirs->validate_tombstone_proportion()); + ck_assert(test_de->validate_tombstone_proportion()); } - ck_assert(ext_wirs->validate_tombstone_proportion()); + ck_assert(test_de->validate_tombstone_proportion()); gsl_rng_free(rng); - delete ext_wirs; + 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 ext_wirs = new DE(1000, 2, 1); + auto test_de = new DE(1000, 2, 1); - std::set<WRec> records; - std::set<WRec> to_delete; - std::set<WRec> deleted; + std::set<Rec> records; + std::set<Rec> to_delete; + std::set<Rec> deleted; while (records.size() < reccnt) { uint64_t key = rand(); @@ -304,14 +272,14 @@ DE *create_test_tree(size_t reccnt, size_t memlevel_cnt) { size_t deletes = 0; for (auto rec : records) { - ck_assert_int_eq(ext_wirs->insert(rec), 1); + ck_assert_int_eq(test_de->insert(rec), 1); if (gsl_rng_uniform(rng) < 0.05 && !to_delete.empty()) { - std::vector<WRec> del_vec; + std::vector<Rec> 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]); + test_de->erase(del_vec[i]); deletes++; to_delete.erase(del_vec[i]); deleted.insert(del_vec[i]); @@ -325,7 +293,7 @@ DE *create_test_tree(size_t reccnt, size_t memlevel_cnt) { gsl_rng_free(rng); - return ext_wirs; + return test_de; } START_TEST(t_static_structure) @@ -333,11 +301,11 @@ 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); + auto test_de = new DE(100, 2, 1); - std::set<WRec> records; - std::set<WRec> to_delete; - std::set<WRec> deleted; + std::set<Rec> records; + std::set<Rec> to_delete; + std::set<Rec> deleted; while (records.size() < reccnt) { uint64_t key = rand(); @@ -345,7 +313,7 @@ START_TEST(t_static_structure) if (records.find({key, val}) != records.end()) continue; - records.insert({key, val, 1}); + records.insert({key, val}); } size_t deletes = 0; @@ -353,15 +321,15 @@ START_TEST(t_static_structure) size_t k=0; for (auto rec : records) { k++; - ck_assert_int_eq(ext_wirs->insert(rec), 1); + ck_assert_int_eq(test_de->insert(rec), 1); t_reccnt++; if (gsl_rng_uniform(rng) < 0.05 && !to_delete.empty()) { - std::vector<WRec> del_vec; + std::vector<Rec> 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); + ck_assert_int_eq(test_de->erase(del_vec[i]), 1); deletes++; to_delete.erase(del_vec[i]); @@ -374,7 +342,7 @@ START_TEST(t_static_structure) } } - auto flat = ext_wirs->create_static_structure(); + auto flat = test_de->create_static_structure(); ck_assert_int_eq(flat->get_record_count(), reccnt - deletes); uint64_t prev_key = 0; @@ -386,7 +354,7 @@ START_TEST(t_static_structure) gsl_rng_free(rng); delete flat; - delete ext_wirs; + delete test_de; } END_TEST @@ -399,21 +367,15 @@ Suite *unit_testing() tcase_add_test(create, t_create); suite_add_tcase(unit, create); - TCase *insert = tcase_create("de::DynamicExtension<WIRS>::insert Testing"); + TCase *insert = tcase_create("de::DynamicExtension<ISAMTree>::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(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 *query = tcase_create("de::DynamicExtension<ISAMTree>::range_query Testing"); + tcase_add_test(query, t_range_query); + suite_add_tcase(unit, query); TCase *ts = tcase_create("de::DynamicExtension::tombstone_compaction Testing"); tcase_add_test(ts, t_tombstone_merging_01); diff --git a/tests/internal_level_tests.cpp b/tests/internal_level_tests.cpp index 056e458..1009ea8 100644 --- a/tests/internal_level_tests.cpp +++ b/tests/internal_level_tests.cpp @@ -9,7 +9,8 @@ * All rights reserved. Published under the Modified BSD License. * */ -#include "shard/WIRS.h" +#include "shard/ISAMTree.h" +#include "query/rangequery.h" #include "framework/structure/InternalLevel.h" #include "framework/interface/Record.h" #include "framework/interface/Query.h" @@ -21,12 +22,12 @@ using namespace de; -typedef InternalLevel<WRec, WIRS<WRec>, WIRSQuery<WRec>> ILevel; +typedef InternalLevel<Rec, ISAMTree<Rec>, rq::Query<ISAMTree<Rec>, 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); @@ -48,8 +49,8 @@ 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); |