Switched default DE test case over to ISAMTree

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);