diff options
33 files changed, 77 insertions, 686 deletions
diff --git a/benchmarks/insert_query_tput.cpp b/benchmarks/insert_query_tput.cpp index 40a5f8d..ce05264 100644 --- a/benchmarks/insert_query_tput.cpp +++ b/benchmarks/insert_query_tput.cpp @@ -19,7 +19,7 @@ typedef de::Record<int64_t, int64_t> Rec; typedef de::ISAMTree<Rec> ISAM; -typedef de::irs::Query<ISAM, Rec> Q; +typedef de::irs::Query<Rec, ISAM> Q; typedef de::DynamicExtension<Rec, ISAM, Q> Ext; typedef de::irs::Parms<Rec> QP; diff --git a/benchmarks/insert_tail_latency.cpp b/benchmarks/insert_tail_latency.cpp index 1640ce5..bdc4536 100644 --- a/benchmarks/insert_tail_latency.cpp +++ b/benchmarks/insert_tail_latency.cpp @@ -18,7 +18,7 @@ typedef de::Record<int64_t, int64_t> Rec; typedef de::ISAMTree<Rec> ISAM; -typedef de::rc::Query<ISAM, Rec> Q; +typedef de::rc::Query<Rec, ISAM> Q; typedef de::DynamicExtension<Rec, ISAM, Q, de::LayoutPolicy::TEIRING, de::DeletePolicy::TAGGING, de::SerialScheduler> Ext; std::atomic<size_t> total_latency = 0; diff --git a/benchmarks/insertion_tput.cpp b/benchmarks/insertion_tput.cpp index 785b933..b4428f6 100644 --- a/benchmarks/insertion_tput.cpp +++ b/benchmarks/insertion_tput.cpp @@ -14,7 +14,7 @@ typedef de::Record<int64_t, int64_t> Rec; typedef de::ISAMTree<Rec> ISAM; -typedef de::rq::Query<ISAM, Rec> Q; +typedef de::rq::Query<Rec, ISAM> Q; typedef de::DynamicExtension<Rec, ISAM, Q> Ext; diff --git a/benchmarks/irs_bench.cpp b/benchmarks/irs_bench.cpp index 6de8681..ddb4220 100644 --- a/benchmarks/irs_bench.cpp +++ b/benchmarks/irs_bench.cpp @@ -19,7 +19,7 @@ typedef de::Record<int64_t, int64_t> Rec; typedef de::ISAMTree<Rec> ISAM; -typedef de::irs::Query<ISAM, Rec> Q; +typedef de::irs::Query<Rec, ISAM> Q; typedef de::DynamicExtension<Rec, ISAM, Q, de::LayoutPolicy::TEIRING, de::DeletePolicy::TOMBSTONE, de::SerialScheduler> Ext; typedef de::irs::Parms<Rec> QP; diff --git a/benchmarks/query_workload_bench.cpp b/benchmarks/query_workload_bench.cpp index 114f780..db8f61a 100644 --- a/benchmarks/query_workload_bench.cpp +++ b/benchmarks/query_workload_bench.cpp @@ -18,7 +18,7 @@ typedef de::Record<int64_t, int64_t> Rec; typedef de::ISAMTree<Rec> ISAM; -typedef de::rc::Query<ISAM, Rec> Q; +typedef de::rc::Query<Rec, ISAM> Q; typedef de::DynamicExtension<Rec, ISAM, Q> Ext; size_t g_insert_size = 50000; diff --git a/benchmarks/reconstruction_interference.cpp b/benchmarks/reconstruction_interference.cpp index c4c8c1b..57eb923 100644 --- a/benchmarks/reconstruction_interference.cpp +++ b/benchmarks/reconstruction_interference.cpp @@ -16,7 +16,7 @@ typedef de::Record<int64_t, int64_t> Rec; typedef de::ISAMTree<Rec> ISAM; -typedef de::rc::Query<ISAM, Rec> Q; +typedef de::rc::Query<Rec, ISAM> Q; typedef de::DynamicExtension<Rec, ISAM, Q> Ext; volatile std::atomic<bool> queries_done; diff --git a/benchmarks/static_dynamic_comp.cpp b/benchmarks/static_dynamic_comp.cpp index 2d8f041..5a89d88 100644 --- a/benchmarks/static_dynamic_comp.cpp +++ b/benchmarks/static_dynamic_comp.cpp @@ -21,7 +21,7 @@ typedef de::Record<key_type, value_type> Rec; typedef de::ISAMTree<Rec> ISAM; typedef de::TrieSpline<Rec> TS; -typedef de::rc::Query<ISAM, Rec> Q; +typedef de::rc::Query<Rec, ISAM> Q; typedef de::DynamicExtension<Rec, ISAM, Q> Ext; typedef de::MutableBuffer<Rec> Buffer; diff --git a/benchmarks/watermark_testing.cpp b/benchmarks/watermark_testing.cpp index e016aa4..caba8ff 100644 --- a/benchmarks/watermark_testing.cpp +++ b/benchmarks/watermark_testing.cpp @@ -14,7 +14,7 @@ typedef de::Record<int64_t, int64_t> Rec; typedef de::ISAMTree<Rec> ISAM; -typedef de::rq::Query<ISAM, Rec> Q; +typedef de::rq::Query<Rec, ISAM> Q; typedef de::DynamicExtension<Rec, ISAM, Q> Ext; diff --git a/include/framework/DynamicExtension.h b/include/framework/DynamicExtension.h index 5c021f2..d88a945 100644 --- a/include/framework/DynamicExtension.h +++ b/include/framework/DynamicExtension.h @@ -31,7 +31,7 @@ namespace de { -template <RecordInterface R, ShardInterface S, QueryInterface<R, S> Q, LayoutPolicy L=LayoutPolicy::TEIRING, +template <RecordInterface R, ShardInterface<R> S, QueryInterface<R, S> Q, LayoutPolicy L=LayoutPolicy::TEIRING, DeletePolicy D=DeletePolicy::TAGGING, SchedulerInterface SCHED=SerialScheduler> class DynamicExtension { typedef S Shard; diff --git a/include/framework/interface/Shard.h b/include/framework/interface/Shard.h index 8c4db34..c4a9180 100644 --- a/include/framework/interface/Shard.h +++ b/include/framework/interface/Shard.h @@ -8,25 +8,17 @@ */ #pragma once -#include <concepts> - -#include "util/types.h" -#include "framework/interface/Record.h" -#include <vector> +#include "framework/ShardRequirements.h" namespace de { -// FIXME: The interface is not completely specified yet, as it is pending -// determining a good way to handle additional template arguments -// to get the Record type into play -template <typename S> -concept ShardInterface = requires(S s, std::vector<S*> spp, void *p, bool b, size_t i) { +template <typename S, typename R> +concept ShardInterface = RecordInterface<R> && requires(S s, std::vector<S*> spp, void *p, bool b, size_t i, BufferView<R> bv, R r) { {S(spp)}; - /* - {S(mutable buffer)} - {s.point_lookup(r, b) } -> std::convertible_to<void*> - */ - {s.get_data()} -> std::convertible_to<void*>; + {S(std::move(bv))}; + + {s.point_lookup(r, b) } -> std::same_as<Wrapped<R>*>; + {s.get_data()} -> std::same_as<Wrapped<R>*>; {s.get_record_count()} -> std::convertible_to<size_t>; {s.get_tombstone_count()} -> std::convertible_to<size_t>; @@ -35,9 +27,10 @@ concept ShardInterface = requires(S s, std::vector<S*> spp, void *p, bool b, siz }; template <typename S, typename R> -concept SortedShardInterface = ShardInterface<S> && requires(S s, R r, R *rp) { +concept SortedShardInterface = ShardInterface<S, R> && requires(S s, R r, R *rp, size_t i) { {s.lower_bound(r)} -> std::convertible_to<size_t>; {s.upper_bound(r)} -> std::convertible_to<size_t>; + {s.get_record_at(i)} -> std::same_as<Wrapped<R>*>; }; } diff --git a/include/framework/scheduling/Epoch.h b/include/framework/scheduling/Epoch.h index 48b7742..e58bd11 100644 --- a/include/framework/scheduling/Epoch.h +++ b/include/framework/scheduling/Epoch.h @@ -18,7 +18,7 @@ namespace de { -template <RecordInterface R, ShardInterface S, QueryInterface<R, S> Q, LayoutPolicy L> +template <RecordInterface R, ShardInterface<R> S, QueryInterface<R, S> Q, LayoutPolicy L> class Epoch { private: typedef MutableBuffer<R> Buffer; diff --git a/include/framework/scheduling/Task.h b/include/framework/scheduling/Task.h index ba0001d..008f232 100644 --- a/include/framework/scheduling/Task.h +++ b/include/framework/scheduling/Task.h @@ -18,7 +18,7 @@ namespace de { -template <RecordInterface R, ShardInterface S, QueryInterface<R, S> Q, LayoutPolicy L> +template <RecordInterface R, ShardInterface<R> S, QueryInterface<R, S> Q, LayoutPolicy L> struct ReconstructionArgs { Epoch<R, S, Q, L> *epoch; std::vector<ReconstructionTask> merges; @@ -27,7 +27,7 @@ struct ReconstructionArgs { void *extension; }; -template <RecordInterface R, ShardInterface S, QueryInterface<R, S> Q, LayoutPolicy L> +template <RecordInterface R, ShardInterface<R> S, QueryInterface<R, S> Q, LayoutPolicy L> struct QueryArgs { std::promise<std::vector<R>> result_set; void *query_parms; diff --git a/include/framework/structure/ExtensionStructure.h b/include/framework/structure/ExtensionStructure.h index 0b8263e..373a1e2 100644 --- a/include/framework/structure/ExtensionStructure.h +++ b/include/framework/structure/ExtensionStructure.h @@ -22,7 +22,7 @@ namespace de { -template <RecordInterface R, ShardInterface S, QueryInterface<R, S> Q, LayoutPolicy L=LayoutPolicy::TEIRING> +template <RecordInterface R, ShardInterface<R> S, QueryInterface<R, S> Q, LayoutPolicy L=LayoutPolicy::TEIRING> class ExtensionStructure { typedef S Shard; typedef BufferView<R> BuffView; diff --git a/include/framework/structure/InternalLevel.h b/include/framework/structure/InternalLevel.h index 0fd5275..d586869 100644 --- a/include/framework/structure/InternalLevel.h +++ b/include/framework/structure/InternalLevel.h @@ -19,12 +19,12 @@ #include "framework/structure/BufferView.h" namespace de { -template <RecordInterface R, ShardInterface S, QueryInterface<R, S> Q> +template <RecordInterface R, ShardInterface<R> S, QueryInterface<R, S> Q> class InternalLevel; -template <RecordInterface R, ShardInterface S, QueryInterface<R, S> Q> +template <RecordInterface R, ShardInterface<R> S, QueryInterface<R, S> Q> class InternalLevel { typedef S Shard; typedef BufferView<R> BuffView; diff --git a/include/query/irs.h b/include/query/irs.h index bef75bf..c14d0cf 100644 --- a/include/query/irs.h +++ b/include/query/irs.h @@ -44,7 +44,7 @@ struct BufferState { BufferState(BufferView<R> *buffer) : buffer(buffer) {} }; -template <ShardInterface S, RecordInterface R, bool Rejection=true> +template <RecordInterface R, ShardInterface<R> S, bool Rejection=true> class Query { public: constexpr static bool EARLY_ABORT=false; diff --git a/include/query/rangecount.h b/include/query/rangecount.h index a09ad64..6c57809 100644 --- a/include/query/rangecount.h +++ b/include/query/rangecount.h @@ -35,7 +35,7 @@ struct BufferState { : buffer(buffer) {} }; -template <ShardInterface S, KVPInterface R> +template <KVPInterface R, ShardInterface<R> S> class Query { public: constexpr static bool EARLY_ABORT=false; diff --git a/include/query/rangequery.h b/include/query/rangequery.h index c3985fa..24b38ec 100644 --- a/include/query/rangequery.h +++ b/include/query/rangequery.h @@ -36,7 +36,7 @@ struct BufferState { : buffer(buffer) {} }; -template <ShardInterface S, RecordInterface R> +template <RecordInterface R, ShardInterface<R> S> class Query { public: constexpr static bool EARLY_ABORT=false; diff --git a/include/query/wirs.h b/include/query/wirs.h index 07c5292..4fac7e7 100644 --- a/include/query/wirs.h +++ b/include/query/wirs.h @@ -57,7 +57,7 @@ struct BufferState { } }; -template <ShardInterface S, RecordInterface R, bool Rejection=true> +template <RecordInterface R, ShardInterface<R> S, bool Rejection=true> class Query { public: constexpr static bool EARLY_ABORT=false; diff --git a/include/query/wss.h b/include/query/wss.h index 9f192ee..ea36cb2 100644 --- a/include/query/wss.h +++ b/include/query/wss.h @@ -46,7 +46,7 @@ struct BufferState { } }; -template <ShardInterface S, RecordInterface R, bool Rejection=true> +template <RecordInterface R, ShardInterface<R> S, bool Rejection=true> class Query { public: constexpr static bool EARLY_ABORT=false; diff --git a/include/shard/Alias.h b/include/shard/Alias.h index a3e8ad8..a234575 100644 --- a/include/shard/Alias.h +++ b/include/shard/Alias.h @@ -15,9 +15,6 @@ #include <vector> #include <cassert> -#include <queue> -#include <memory> -#include <concepts> #include "framework/ShardRequirements.h" @@ -34,7 +31,7 @@ using psudb::queue_record; namespace de { -thread_local size_t wss_cancelations = 0; +static thread_local size_t wss_cancelations = 0; template <WeightedRecordInterface R> class Alias { @@ -44,7 +41,7 @@ private: typedef decltype(R::weight) W; public: - Alias(MutableBuffer<R>* buffer) + Alias(BufferView<R>* buffer) : m_reccnt(0), m_tombstone_cnt(0), m_total_weight(0), m_alias(nullptr), m_bf(nullptr) { m_alloc_size = (buffer->get_record_count() * sizeof(Wrapped<R>)) + (CACHELINE_SIZE - (buffer->get_record_count() * sizeof(Wrapped<R>)) % CACHELINE_SIZE); @@ -96,17 +93,17 @@ public: } } - Alias(Alias** shards, size_t len) + Alias(std::vector<Alias*> &shards) : m_reccnt(0), m_tombstone_cnt(0), m_total_weight(0), m_alias(nullptr), m_bf(nullptr) { std::vector<Cursor<Wrapped<R>>> cursors; - cursors.reserve(len); + cursors.reserve(shards.size()); - PriorityQueue<Wrapped<R>> pq(len); + PriorityQueue<Wrapped<R>> pq(shards.size()); size_t attemp_reccnt = 0; size_t tombstone_count = 0; - for (size_t i = 0; i < len; ++i) { + for (size_t i = 0; i < shards.size(); ++i) { if (shards[i]) { auto base = shards[i]->get_data(); cursors.emplace_back(Cursor{base, base + shards[i]->get_record_count(), 0, shards[i]->get_record_count()}); diff --git a/include/shard/ISAMTree.h b/include/shard/ISAMTree.h index 932e767..7de9cb1 100644 --- a/include/shard/ISAMTree.h +++ b/include/shard/ISAMTree.h @@ -25,6 +25,7 @@ using psudb::CACHELINE_SIZE; using psudb::BloomFilter; using psudb::PriorityQueue; using psudb::queue_record; +using psudb::byte; namespace de { @@ -222,9 +223,6 @@ public: return m_tombstone_cnt; } - const Wrapped<R>* get_record_at(size_t idx) const { - return (idx < m_reccnt) ? m_data + idx : nullptr; - } size_t get_memory_usage() { return m_alloc_size; @@ -234,6 +232,7 @@ public: return m_bf->memory_usage(); } + /* SortedShardInterface methods */ size_t get_lower_bound(const K& key) const { const InternalNode* now = m_root; while (!is_leaf(reinterpret_cast<const byte*>(now))) { @@ -274,6 +273,9 @@ public: return pos - m_data; } + const Wrapped<R>* get_record_at(size_t idx) const { + return (idx < m_reccnt) ? m_data + idx : nullptr; + } private: void build_internal_levels() { diff --git a/include/shard/TrieSpline.h b/include/shard/TrieSpline.h index 8142a67..9473177 100644 --- a/include/shard/TrieSpline.h +++ b/include/shard/TrieSpline.h @@ -25,6 +25,7 @@ using psudb::CACHELINE_SIZE; using psudb::BloomFilter; using psudb::PriorityQueue; using psudb::queue_record; +using psudb::byte; namespace de { diff --git a/tests/de_cc_isam_level.cpp b/tests/de_cc_isam_level.cpp deleted file mode 100644 index 4972fb5..0000000 --- a/tests/de_cc_isam_level.cpp +++ /dev/null @@ -1,461 +0,0 @@ -/* - * tests/de_cc_isam_level.cpp - * - * Unit tests for Dynamic Extension Framework - * - * Copyright (C) 2023 Douglas B. Rumbaugh <drumbaugh@psu.edu> - * - * Distributed under the Modified BSD License. - * - */ - -#include <random> - -#include "framework/DynamicExtension.h" -#include "shard/MemISAM.h" - -#include <check.h> - -using namespace de; - -typedef Record<int32_t, int32_t> Rec; -typedef DynamicExtension<Rec, MemISAM<Rec>, ISAMRangeQuery<Rec>, LayoutPolicy::LEVELING, DeletePolicy::TOMBSTONE> DE; - -START_TEST(t_create) -{ - auto de_isam = new DE(100, 2, 1); - - ck_assert_ptr_nonnull(de_isam); - ck_assert_int_eq(de_isam->get_record_count(), 0); - ck_assert_int_eq(de_isam->get_height(), 0); - - delete de_isam; -} -END_TEST - - -START_TEST(t_insert) -{ - auto ext_wirs = new DE(100, 2, 1); - - int32_t key = 0; - int32_t val = 0; - for (size_t i=0; i<100; i++) { - Rec r = {key, val}; - 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_debug_insert) -{ - auto ext_wirs = new DE(100, 2, 1); - - int32_t key = 0; - int32_t val = 0; - for (size_t i=0; i<1000; i++) { - Rec r = {key, val}; - ck_assert_int_eq(ext_wirs->insert(r), 1); - ck_assert_int_eq(ext_wirs->get_record_count(), i+1); - key++; - val++; - } - - delete ext_wirs; -} -END_TEST - - -START_TEST(t_insert_with_mem_merges) -{ - auto ext_wirs = new DE(100, 2, 1); - - int32_t key = 0; - int32_t val = 0; - for (size_t i=0; i<300; i++) { - Rec r = {key, val}; - 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); - - int32_t key = 0; - int32_t val = 0; - for (size_t i=0; i<100; i++) { - Rec r = {key, val}; - ck_assert_int_eq(ext_wirs->insert(r), 1); - key++; - val++; - } - - int32_t lower_bound = 20; - int32_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); - Rec 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); - - int32_t key = 0; - int32_t val = 0; - for (size_t i=0; i<300; i++) { - Rec r = {key, val}; - ck_assert_int_eq(ext_wirs->insert(r), 1); - key++; - val++; - } - - int32_t lower_bound = 100; - int32_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); - - Rec 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<int32_t> keys; - - int32_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++) { - int32_t weight; - if (keys[i] == 1) { - weight = 2; - } else if (keys[i] == 2) { - weight = 4; - } else { - weight = 8; - } - - Rec r = {keys[i], (int32_t) i, weight}; - ext_wirs->insert(r); - } - size_t k = 1000; - int32_t lower_key = 0; - int32_t upper_key = 5; - - size_t cnt[3] = {0}; - size_t total_samples = 0; - - wirs_query_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(); - - for (size_t j=0; j<r.size(); j++) { - cnt[r[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<int32_t, int32_t>> records; - std::set<std::pair<int32_t, int32_t>> to_delete; - std::set<std::pair<int32_t, int32_t>> deleted; - - while (records.size() < reccnt) { - int32_t key = rand(); - int32_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) { - Rec 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<int32_t, int32_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++) { - Rec 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<Rec> records; - std::set<Rec> to_delete; - std::set<Rec> deleted; - - while (records.size() < reccnt) { - int32_t key = rand(); - int32_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<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]); - 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<Rec> records; - std::set<Rec> to_delete; - std::set<Rec> deleted; - - while (records.size() < reccnt) { - int32_t key = rand(); - int32_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(ext_wirs->insert(rec), 1); - t_reccnt++; - - if (gsl_rng_uniform(rng) < 0.05 && !to_delete.empty()) { - 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); - - 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); - - int32_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); - 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 *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/de_level_concurrent.cpp b/tests/de_level_concurrent.cpp index b52fdd9..40605c4 100644 --- a/tests/de_level_concurrent.cpp +++ b/tests/de_level_concurrent.cpp @@ -22,7 +22,7 @@ #include <check.h> using namespace de; -typedef DynamicExtension<Rec, ISAMTree<Rec>, rq::Query<ISAMTree<Rec>, Rec>, LayoutPolicy::LEVELING, DeletePolicy::TOMBSTONE, FIFOScheduler> DE; +typedef DynamicExtension<Rec, ISAMTree<Rec>, rq::Query<Rec, ISAMTree<Rec>>, LayoutPolicy::LEVELING, DeletePolicy::TOMBSTONE, FIFOScheduler> DE; #include "include/concurrent_extension.h" diff --git a/tests/de_level_tag.cpp b/tests/de_level_tag.cpp index 5c95aa2..2ff2d26 100644 --- a/tests/de_level_tag.cpp +++ b/tests/de_level_tag.cpp @@ -21,7 +21,7 @@ #include <check.h> using namespace de; -typedef DynamicExtension<Rec, ISAMTree<Rec>, rq::Query<ISAMTree<Rec>, Rec>, LayoutPolicy::LEVELING, DeletePolicy::TAGGING, SerialScheduler> DE; +typedef DynamicExtension<Rec, ISAMTree<Rec>, rq::Query<Rec, ISAMTree<Rec>>, LayoutPolicy::LEVELING, DeletePolicy::TAGGING, SerialScheduler> DE; #include "include/dynamic_extension.h" diff --git a/tests/de_level_tomb.cpp b/tests/de_level_tomb.cpp index 44a0759..9b30ac0 100644 --- a/tests/de_level_tomb.cpp +++ b/tests/de_level_tomb.cpp @@ -22,7 +22,7 @@ #include <check.h> using namespace de; -typedef DynamicExtension<Rec, ISAMTree<Rec>, rq::Query<ISAMTree<Rec>, Rec>, LayoutPolicy::LEVELING, DeletePolicy::TOMBSTONE, SerialScheduler> DE; +typedef DynamicExtension<Rec, ISAMTree<Rec>, rq::Query<Rec, ISAMTree<Rec>>, LayoutPolicy::LEVELING, DeletePolicy::TOMBSTONE, SerialScheduler> DE; #include "include/dynamic_extension.h" diff --git a/tests/de_tier_concurrent.cpp b/tests/de_tier_concurrent.cpp index 9387b21..418332b 100644 --- a/tests/de_tier_concurrent.cpp +++ b/tests/de_tier_concurrent.cpp @@ -21,7 +21,7 @@ #include <check.h> using namespace de; -typedef DynamicExtension<Rec, ISAMTree<Rec>, rq::Query<ISAMTree<Rec>, Rec>, LayoutPolicy::TEIRING, DeletePolicy::TOMBSTONE, FIFOScheduler> DE; +typedef DynamicExtension<Rec, ISAMTree<Rec>, rq::Query<Rec, ISAMTree<Rec>>, LayoutPolicy::TEIRING, DeletePolicy::TOMBSTONE, FIFOScheduler> DE; #include "include/concurrent_extension.h" diff --git a/tests/de_tier_tag.cpp b/tests/de_tier_tag.cpp index 9d4fe7d..83c37af 100644 --- a/tests/de_tier_tag.cpp +++ b/tests/de_tier_tag.cpp @@ -22,7 +22,7 @@ #include <check.h> using namespace de; -typedef DynamicExtension<Rec, ISAMTree<Rec>, rq::Query<ISAMTree<Rec>, Rec>, LayoutPolicy::TEIRING, DeletePolicy::TAGGING, SerialScheduler> DE; +typedef DynamicExtension<Rec, ISAMTree<Rec>, rq::Query<Rec, ISAMTree<Rec>>, LayoutPolicy::TEIRING, DeletePolicy::TAGGING, SerialScheduler> DE; #include "include/dynamic_extension.h" diff --git a/tests/de_tier_tomb.cpp b/tests/de_tier_tomb.cpp index 7d8f144..58a7a0f 100644 --- a/tests/de_tier_tomb.cpp +++ b/tests/de_tier_tomb.cpp @@ -22,7 +22,7 @@ #include <check.h> using namespace de; -typedef DynamicExtension<Rec, ISAMTree<Rec>, rq::Query<ISAMTree<Rec>, Rec>, LayoutPolicy::TEIRING, DeletePolicy::TOMBSTONE, SerialScheduler> DE; +typedef DynamicExtension<Rec, ISAMTree<Rec>, rq::Query<Rec, ISAMTree<Rec>>, LayoutPolicy::TEIRING, DeletePolicy::TOMBSTONE, SerialScheduler> DE; #include "include/dynamic_extension.h" diff --git a/tests/include/rangecount.h b/tests/include/rangecount.h index e09ab12..471af27 100644 --- a/tests/include/rangecount.h +++ b/tests/include/rangecount.h @@ -41,9 +41,9 @@ START_TEST(t_range_count) parms.lower_bound = 300; parms.upper_bound = 500; - auto state = rc::Query<Shard, Rec>::get_query_state(&shard, &parms); - auto result = rc::Query<Shard, Rec>::query(&shard, state, &parms); - rc::Query<Shard, Rec>::delete_query_state(state); + auto state = rc::Query<Rec, Shard>::get_query_state(&shard, &parms); + auto result = rc::Query<Rec, Shard>::query(&shard, state, &parms); + rc::Query<Rec, 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); @@ -63,9 +63,9 @@ START_TEST(t_buffer_range_count) { auto view = buffer->get_buffer_view(); - auto state = rc::Query<Shard, Rec>::get_buffer_query_state(&view, &parms); - auto result = rc::Query<Shard, Rec>::buffer_query(state, &parms); - rc::Query<Shard, Rec>::delete_buffer_query_state(state); + auto state = rc::Query<Rec, Shard>::get_buffer_query_state(&view, &parms); + auto result = rc::Query<Rec, Shard>::buffer_query(state, &parms); + rc::Query<Rec, 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); @@ -90,20 +90,20 @@ START_TEST(t_range_count_merge) size_t result_size = parms.upper_bound - parms.lower_bound + 1 - 200; - auto state1 = rc::Query<Shard, Rec>::get_query_state(&shard1, &parms); - auto state2 = rc::Query<Shard, Rec>::get_query_state(&shard2, &parms); + auto state1 = rc::Query<Rec, Shard>::get_query_state(&shard1, &parms); + auto state2 = rc::Query<Rec, Shard>::get_query_state(&shard2, &parms); std::vector<std::vector<de::Wrapped<Rec>>> results(2); - results[0] = rc::Query<Shard, Rec>::query(&shard1, state1, &parms); - results[1] = rc::Query<Shard, Rec>::query(&shard2, state2, &parms); + results[0] = rc::Query<Rec, Shard>::query(&shard1, state1, &parms); + results[1] = rc::Query<Rec, Shard>::query(&shard2, state2, &parms); - rc::Query<Shard, Rec>::delete_query_state(state1); - rc::Query<Shard, Rec>::delete_query_state(state2); + rc::Query<Rec, Shard>::delete_query_state(state1); + rc::Query<Rec, 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<Shard, Rec>::merge(results, nullptr); + auto result = rc::Query<Rec, Shard>::merge(results, nullptr); ck_assert_int_eq(result[0].key, result_size); diff --git a/tests/include/rangequery.h b/tests/include/rangequery.h index b9694a4..dbb71db 100644 --- a/tests/include/rangequery.h +++ b/tests/include/rangequery.h @@ -41,9 +41,9 @@ START_TEST(t_range_query) parms.lower_bound = 300; parms.upper_bound = 500; - auto state = rq::Query<Shard, Rec>::get_query_state(&shard, &parms); - auto result = rq::Query<Shard, Rec>::query(&shard, state, &parms); - rq::Query<Shard, Rec>::delete_query_state(state); + auto state = rq::Query<Rec, Shard>::get_query_state(&shard, &parms); + auto result = rq::Query<Rec, Shard>::query(&shard, state, &parms); + rq::Query<Rec, 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++) { @@ -66,9 +66,9 @@ START_TEST(t_buffer_range_query) { auto view = buffer->get_buffer_view(); - auto state = rq::Query<Shard, Rec>::get_buffer_query_state(&view, &parms); - auto result = rq::Query<Shard, Rec>::buffer_query(state, &parms); - rq::Query<Shard, Rec>::delete_buffer_query_state(state); + auto state = rq::Query<Rec, Shard>::get_buffer_query_state(&view, &parms); + auto result = rq::Query<Rec, Shard>::buffer_query(state, &parms); + rq::Query<Rec, 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++) { @@ -96,15 +96,15 @@ START_TEST(t_range_query_merge) size_t result_size = parms.upper_bound - parms.lower_bound + 1 - 200; - auto state1 = rq::Query<Shard, Rec>::get_query_state(&shard1, &parms); - auto state2 = rq::Query<Shard, Rec>::get_query_state(&shard2, &parms); + auto state1 = rq::Query<Rec, Shard>::get_query_state(&shard1, &parms); + auto state2 = rq::Query<Rec, Shard>::get_query_state(&shard2, &parms); std::vector<std::vector<de::Wrapped<Rec>>> results(2); - results[0] = rq::Query<Shard, Rec>::query(&shard1, state1, &parms); - results[1] = rq::Query<Shard, Rec>::query(&shard2, state2, &parms); + results[0] = rq::Query<Rec, Shard>::query(&shard1, state1, &parms); + results[1] = rq::Query<Rec, Shard>::query(&shard2, state2, &parms); - rq::Query<Shard, Rec>::delete_query_state(state1); - rq::Query<Shard, Rec>::delete_query_state(state2); + rq::Query<Rec, Shard>::delete_query_state(state1); + rq::Query<Rec, Shard>::delete_query_state(state2); ck_assert_int_eq(results[0].size() + results[1].size(), result_size); @@ -117,7 +117,7 @@ START_TEST(t_range_query_merge) } } - auto result = rq::Query<Shard, Rec>::merge(proc_results, nullptr); + auto result = rq::Query<Rec, Shard>::merge(proc_results, nullptr); std::sort(result.begin(), result.end()); ck_assert_int_eq(result.size(), result_size); diff --git a/tests/internal_level_tests.cpp b/tests/internal_level_tests.cpp index 79b9c21..06b0bab 100644 --- a/tests/internal_level_tests.cpp +++ b/tests/internal_level_tests.cpp @@ -22,7 +22,7 @@ using namespace de; -typedef InternalLevel<Rec, ISAMTree<Rec>, rq::Query<ISAMTree<Rec>, Rec>> ILevel; +typedef InternalLevel<Rec, ISAMTree<Rec>, rq::Query<Rec, ISAMTree<Rec>>> ILevel; START_TEST(t_memlevel_merge) { diff --git a/tests/rangequery_tests.cpp b/tests/rangequery_tests.cpp index c78571c..49c73d3 100644 --- a/tests/rangequery_tests.cpp +++ b/tests/rangequery_tests.cpp @@ -21,153 +21,12 @@ using namespace de; typedef ISAMTree<Rec> Shard; -START_TEST(t_range_query) -{ - auto buffer = create_sequential_mbuffer<Rec>(100, 1000); - auto shard = Shard(buffer->get_buffer_view()); - - rq::Parms<Rec> parms; - parms.lower_bound = 300; - parms.upper_bound = 500; - - auto state = rq::Query<Shard, Rec>::get_query_state(&shard, &parms); - auto result = rq::Query<Shard, Rec>::query(&shard, state, &parms); - rq::Query<Shard, 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); - - rq::Parms<Rec> parms; - parms.lower_bound = 300; - parms.upper_bound = 500; - - { - auto view = buffer->get_buffer_view(); - auto state = rq::Query<Shard, Rec>::get_buffer_query_state(&view, &parms); - auto result = rq::Query<Shard, Rec>::buffer_query(state, &parms); - rq::Query<Shard, 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->get_buffer_view()); - auto shard2 = Shard(buffer2->get_buffer_view()); - - rq::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 = rq::Query<Shard, Rec>::get_query_state(&shard1, &parms); - auto state2 = rq::Query<Shard, Rec>::get_query_state(&shard2, &parms); - - std::vector<std::vector<de::Wrapped<Rec>>> results(2); - results[0] = rq::Query<Shard, Rec>::query(&shard1, state1, &parms); - results[1] = rq::Query<Shard, Rec>::query(&shard2, state2, &parms); - - rq::Query<Shard, Rec>::delete_query_state(state1); - rq::Query<Shard, 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 = rq::Query<Shard, 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); - - auto shard1 = Shard(buffer1->get_buffer_view()); - auto shard2 = Shard(buffer2->get_buffer_view()); - - std::vector<Shard *> shards = {&shard1, &shard2}; - - auto merged = Shard(shards); - - 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 - +#include "include/rangequery.h" Suite *unit_testing() { - Suite *unit = suite_create("Range Query Unit Testing"); - - 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); + Suite *unit = suite_create("Range Count Query Testing"); + inject_rangequery_tests(unit); return unit; } |