summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
m---------external/psudb-common0
-rw-r--r--include/framework/interface/Shard.h2
-rw-r--r--include/query/irs.h6
-rw-r--r--include/query/rangequery.h14
-rw-r--r--include/query/wss.h204
-rw-r--r--include/shard/Alias.h (renamed from include/shard/WSS.h)218
-rw-r--r--include/shard/ISAMTree.h (renamed from include/shard/MemISAM.h)44
-rw-r--r--include/shard/PGM.h267
-rw-r--r--include/shard/TrieSpline.h184
-rw-r--r--tests/alias_tests.cpp (renamed from tests/wss_tests.cpp)97
-rw-r--r--tests/memisam_tests.cpp69
-rw-r--r--tests/pgm_tests.cpp33
-rw-r--r--tests/triespline_tests.cpp17
13 files changed, 359 insertions, 796 deletions
diff --git a/external/psudb-common b/external/psudb-common
-Subproject 7005ad856c941d8485843c53a3b08d53ccc3d98
+Subproject b85686b50ab767e5c06eedb975686923aa79dd3
diff --git a/include/framework/interface/Shard.h b/include/framework/interface/Shard.h
index 40a696b..92cdca0 100644
--- a/include/framework/interface/Shard.h
+++ b/include/framework/interface/Shard.h
@@ -37,6 +37,6 @@ template <typename S, typename R>
concept SortedShardInterface = ShardInterface<S> && requires(S s, R r, R *rp) {
{s.lower_bound(r)} -> std::convertible_to<size_t>;
{s.upper_bound(r)} -> std::convertible_to<size_t>;
-}
+};
}
diff --git a/include/query/irs.h b/include/query/irs.h
index 5b09e73..4cb69b0 100644
--- a/include/query/irs.h
+++ b/include/query/irs.h
@@ -44,8 +44,8 @@ public:
static void *get_query_state(S *shard, void *parms) {
auto res = new State<R>();
- decltype(R::key) lower_key = ((PARMS<R> *) parms)->lower_bound;
- decltype(R::key) upper_key = (PARMS<R> *) parms)->upper_bound;
+ decltype(R::key) lower_key = ((Parms<R> *) parms)->lower_bound;
+ decltype(R::key) upper_key = ((Parms<R> *) parms)->upper_bound;
res->lower_bound = shard->get_lower_bound(lower_key);
res->upper_bound = shard->get_upper_bound(upper_key);
@@ -119,7 +119,7 @@ public:
normalized_weights.push_back((double) w / (double) total_weight);
}
- auto shard_alias = Alias(normalized_weights);
+ auto shard_alias = psudb::Alias(normalized_weights);
for (size_t i=0; i<p->sample_size; i++) {
auto idx = shard_alias.get(p->rng);
if (idx == 0) {
diff --git a/include/query/rangequery.h b/include/query/rangequery.h
index f9a34d9..b9ac9db 100644
--- a/include/query/rangequery.h
+++ b/include/query/rangequery.h
@@ -8,6 +8,12 @@
*/
#pragma once
+#include "framework/interface/Record.h"
+#include "framework/interface/Shard.h"
+#include "framework/structure/MutableBuffer.h"
+#include "psu-ds/PriorityQueue.h"
+#include "util/Cursor.h"
+
namespace de { namespace rq {
template <RecordInterface R>
@@ -27,7 +33,7 @@ struct BufferState {
size_t cutoff;
};
-template <RecordInterface R>
+template <ShardInterface S, RecordInterface R>
class Query {
public:
constexpr static bool EARLY_ABORT=false;
@@ -74,7 +80,7 @@ public:
ptr++;
}
- while (ptr->rec.key <= p->upper_bound && ptr < shard->m_data + s->stop_idx) {
+ while (ptr->rec.key <= p->upper_bound && ptr < shard->get_data() + s->stop_idx) {
records.emplace_back(*ptr);
ptr++;
}
@@ -101,7 +107,7 @@ public:
std::vector<Cursor<Wrapped<R>>> cursors;
cursors.reserve(results.size());
- PriorityQueue<Wrapped<R>> pq(results.size());
+ psudb::PriorityQueue<Wrapped<R>> pq(results.size());
size_t total = 0;
size_t tmp_n = results.size();
@@ -126,7 +132,7 @@ public:
while (pq.size()) {
auto now = pq.peek();
- auto next = pq.size() > 1 ? pq.peek(1) : queue_record<Wrapped<R>>{nullptr, 0};
+ auto next = pq.size() > 1 ? pq.peek(1) : psudb::queue_record<Wrapped<R>>{nullptr, 0};
if (!now.data->is_tombstone() && next.data != nullptr &&
now.data->rec == next.data->rec && next.data->is_tombstone()) {
diff --git a/include/query/wss.h b/include/query/wss.h
new file mode 100644
index 0000000..b8a5d54
--- /dev/null
+++ b/include/query/wss.h
@@ -0,0 +1,204 @@
+/*
+ * include/query/rangequery.h
+ *
+ * Copyright (C) 2023 Douglas B. Rumbaugh <drumbaugh@psu.edu>
+ *
+ * All rights reserved. Published under the Modified BSD License.
+ *
+ */
+#pragma once
+
+#include "framework/interface/Record.h"
+#include "framework/interface/Shard.h"
+#include "framework/structure/MutableBuffer.h"
+
+namespace de { namespace wss {
+
+template <WeightedRecordInterface R>
+struct Parms {
+ size_t sample_size;
+ gsl_rng *rng;
+};
+
+template <WeightedRecordInterface R>
+struct State {
+ decltype(R::weight) total_weight;
+ size_t sample_size;
+
+ State() {
+ total_weight = 0;
+ }
+};
+
+template <RecordInterface R>
+struct BufferState {
+ size_t cutoff;
+ size_t sample_size;
+ psudb::Alias *alias;
+ decltype(R::weight) max_weight;
+ decltype(R::weight) total_weight;
+
+ ~BufferState() {
+ delete alias;
+ }
+};
+
+template <ShardInterface S, RecordInterface R, bool Rejection=true>
+class Query {
+public:
+ constexpr static bool EARLY_ABORT=false;
+ constexpr static bool SKIP_DELETE_FILTER=false;
+
+ static void *get_query_state(S *shard, void *parms) {
+ auto res = new State<R>();
+ res->total_weight = shard->get_total_weight();
+ res->sample_size = 0;
+
+ return res;
+ }
+
+ static void* get_buffer_query_state(MutableBuffer<R> *buffer, void *parms) {
+ BufferState<R> *state = new BufferState<R>();
+ auto parameters = (Parms<R>*) parms;
+ if constexpr (Rejection) {
+ state->cutoff = buffer->get_record_count() - 1;
+ state->max_weight = buffer->get_max_weight();
+ state->total_weight = buffer->get_total_weight();
+ return state;
+ }
+
+ std::vector<double> weights;
+
+ state->cutoff = buffer->get_record_count() - 1;
+ double total_weight = 0.0;
+
+ for (size_t i = 0; i <= state->cutoff; i++) {
+ auto rec = buffer->get_data() + i;
+ weights.push_back(rec->rec.weight);
+ total_weight += rec->rec.weight;
+ }
+
+ for (size_t i = 0; i < weights.size(); i++) {
+ weights[i] = weights[i] / total_weight;
+ }
+
+ state->alias = new psudb::Alias(weights);
+ state->total_weight = total_weight;
+
+ return state;
+ }
+
+ static void process_query_states(void *query_parms, std::vector<void*> &shard_states, std::vector<void*> &buffer_states) {
+ auto p = (Parms<R> *) query_parms;
+ auto bs = (BufferState<R> *) buffer_states[0];
+
+ std::vector<size_t> shard_sample_sizes(shard_states.size()+1, 0);
+ size_t buffer_sz = 0;
+
+ std::vector<decltype(R::weight)> weights;
+ weights.push_back(bs->total_weight);
+
+ decltype(R::weight) total_weight = 0;
+ for (auto &s : shard_states) {
+ auto state = (State<R> *) s;
+ total_weight += state->total_weight;
+ weights.push_back(state->total_weight);
+ }
+
+ std::vector<double> normalized_weights;
+ for (auto w : weights) {
+ normalized_weights.push_back((double) w / (double) total_weight);
+ }
+
+ auto shard_alias = psudb::Alias(normalized_weights);
+ for (size_t i=0; i<p->sample_size; i++) {
+ auto idx = shard_alias.get(p->rng);
+ if (idx == 0) {
+ buffer_sz++;
+ } else {
+ shard_sample_sizes[idx - 1]++;
+ }
+ }
+
+
+ bs->sample_size = buffer_sz;
+ for (size_t i=0; i<shard_states.size(); i++) {
+ auto state = (State<R> *) shard_states[i];
+ state->sample_size = shard_sample_sizes[i+1];
+ }
+ }
+
+ static std::vector<Wrapped<R>> query(S *shard, void *q_state, void *parms) {
+ auto rng = ((Parms<R> *) parms)->rng;
+
+ auto state = (State<R> *) q_state;
+ auto sample_size = state->sample_size;
+
+ std::vector<Wrapped<R>> result_set;
+
+ if (sample_size == 0) {
+ return result_set;
+ }
+ size_t attempts = 0;
+ do {
+ attempts++;
+ size_t idx = shard->m_alias->get(rng);
+ result_set.emplace_back(*shard->get_record_at(idx));
+ } while (attempts < sample_size);
+
+ return result_set;
+ }
+
+ static std::vector<Wrapped<R>> buffer_query(MutableBuffer<R> *buffer, void *state, void *parms) {
+ auto st = (BufferState<R> *) state;
+ auto p = (Parms<R> *) parms;
+
+ std::vector<Wrapped<R>> result;
+ result.reserve(st->sample_size);
+
+ if constexpr (Rejection) {
+ for (size_t i=0; i<st->sample_size; i++) {
+ auto idx = gsl_rng_uniform_int(p->rng, st->cutoff);
+ auto rec = buffer->get_data() + idx;
+
+ auto test = gsl_rng_uniform(p->rng) * st->max_weight;
+
+ if (test <= rec->rec.weight) {
+ result.emplace_back(*rec);
+ }
+ }
+ return result;
+ }
+
+ for (size_t i=0; i<st->sample_size; i++) {
+ auto idx = st->alias->get(p->rng);
+ result.emplace_back(*(buffer->get_data() + idx));
+ }
+
+ return result;
+ }
+
+ static std::vector<R> merge(std::vector<std::vector<Wrapped<R>>> &results, void *parms) {
+ std::vector<R> output;
+
+ for (size_t i=0; i<results.size(); i++) {
+ for (size_t j=0; j<results[i].size(); j++) {
+ output.emplace_back(results[i][j].rec);
+ }
+ }
+
+ return output;
+ }
+
+ static void delete_query_state(void *state) {
+ auto s = (State<R> *) state;
+ delete s;
+ }
+
+ static void delete_buffer_query_state(void *state) {
+ auto s = (BufferState<R> *) state;
+ delete s;
+ }
+};
+
+}}
diff --git a/include/shard/WSS.h b/include/shard/Alias.h
index 4e3a326..b6b16c5 100644
--- a/include/shard/WSS.h
+++ b/include/shard/Alias.h
@@ -1,5 +1,5 @@
/*
- * include/shard/WSS.h
+ * include/shard/Alias.h
*
* Copyright (C) 2023 Douglas B. Rumbaugh <drumbaugh@psu.edu>
* Dong Xie <dongx@psu.edu>
@@ -9,7 +9,6 @@
*/
#pragma once
-
#include <vector>
#include <cassert>
#include <queue>
@@ -20,7 +19,7 @@
#include "psu-ds/PriorityQueue.h"
#include "util/Cursor.h"
-#include "psu-ds/Alias.h"
+#include "psu-ds/psudb::Alias.h"
#include "psu-ds/BloomFilter.h"
#include "util/bf_config.h"
@@ -28,59 +27,20 @@ using psudb::CACHELINE_SIZE;
using psudb::BloomFilter;
using psudb::PriorityQueue;
using psudb::queue_record;
-using psudb::Alias;
namespace de {
thread_local size_t wss_cancelations = 0;
template <WeightedRecordInterface R>
-struct wss_query_parms {
- size_t sample_size;
- gsl_rng *rng;
-};
-
-template <WeightedRecordInterface R, bool Rejection>
-class WSSQuery;
-
-template <WeightedRecordInterface R>
-struct WSSState {
- decltype(R::weight) total_weight;
- size_t sample_size;
-
- WSSState() {
- total_weight = 0;
- }
-};
-
-template <WeightedRecordInterface R>
-struct WSSBufferState {
- size_t cutoff;
- size_t sample_size;
- Alias* alias;
- decltype(R::weight) max_weight;
- decltype(R::weight) total_weight;
-
- ~WSSBufferState() {
- delete alias;
- }
-
-};
-
-template <WeightedRecordInterface R>
-class WSS {
+class Alias {
private:
typedef decltype(R::key) K;
typedef decltype(R::value) V;
typedef decltype(R::weight) W;
public:
-
- // FIXME: there has to be a better way to do this
- friend class WSSQuery<R, true>;
- friend class WSSQuery<R, false>;
-
- WSS(MutableBuffer<R>* buffer)
+ Alias(MutableBuffer<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);
@@ -132,7 +92,7 @@ public:
}
}
- WSS(WSS** shards, size_t len)
+ Alias(Alias** shards, size_t len)
: 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);
@@ -195,7 +155,7 @@ public:
}
}
- ~WSS() {
+ ~Alias() {
if (m_data) free(m_data);
if (m_alias) delete m_alias;
if (m_bf) delete m_bf;
@@ -277,11 +237,11 @@ private:
}
// build the alias structure
- m_alias = new Alias(norm_weights);
+ m_alias = new psudb::Alias(norm_weights);
}
Wrapped<R>* m_data;
- Alias *m_alias;
+ psudb::Alias *m_alias;
W m_total_weight;
size_t m_reccnt;
size_t m_tombstone_cnt;
@@ -289,165 +249,3 @@ private:
size_t m_alloc_size;
BloomFilter<R> *m_bf;
};
-
-
-template <WeightedRecordInterface R, bool Rejection=true>
-class WSSQuery {
-public:
-
- constexpr static bool EARLY_ABORT=false;
- constexpr static bool SKIP_DELETE_FILTER=false;
-
- static void *get_query_state(WSS<R> *wss, void *parms) {
- auto res = new WSSState<R>();
- res->total_weight = wss->m_total_weight;
- res->sample_size = 0;
-
- return res;
- }
-
- static void* get_buffer_query_state(MutableBuffer<R> *buffer, void *parms) {
- WSSBufferState<R> *state = new WSSBufferState<R>();
- auto parameters = (wss_query_parms<R>*) parms;
- if constexpr (Rejection) {
- state->cutoff = buffer->get_record_count() - 1;
- state->max_weight = buffer->get_max_weight();
- state->total_weight = buffer->get_total_weight();
- return state;
- }
-
- std::vector<double> weights;
-
- state->cutoff = buffer->get_record_count() - 1;
- double total_weight = 0.0;
-
- for (size_t i = 0; i <= state->cutoff; i++) {
- auto rec = buffer->get_data() + i;
- weights.push_back(rec->rec.weight);
- total_weight += rec->rec.weight;
- }
-
- for (size_t i = 0; i < weights.size(); i++) {
- weights[i] = weights[i] / total_weight;
- }
-
- state->alias = new Alias(weights);
- state->total_weight = total_weight;
-
- return state;
- }
-
- static void process_query_states(void *query_parms, std::vector<void*> &shard_states, void *buff_state) {
- auto p = (wss_query_parms<R> *) query_parms;
- auto bs = (WSSBufferState<R> *) buff_state;
-
- std::vector<size_t> shard_sample_sizes(shard_states.size()+1, 0);
- size_t buffer_sz = 0;
-
- std::vector<decltype(R::weight)> weights;
- weights.push_back(bs->total_weight);
-
- decltype(R::weight) total_weight = 0;
- for (auto &s : shard_states) {
- auto state = (WSSState<R> *) s;
- total_weight += state->total_weight;
- weights.push_back(state->total_weight);
- }
-
- std::vector<double> normalized_weights;
- for (auto w : weights) {
- normalized_weights.push_back((double) w / (double) total_weight);
- }
-
- auto shard_alias = Alias(normalized_weights);
- for (size_t i=0; i<p->sample_size; i++) {
- auto idx = shard_alias.get(p->rng);
- if (idx == 0) {
- buffer_sz++;
- } else {
- shard_sample_sizes[idx - 1]++;
- }
- }
-
-
- bs->sample_size = buffer_sz;
- for (size_t i=0; i<shard_states.size(); i++) {
- auto state = (WSSState<R> *) shard_states[i];
- state->sample_size = shard_sample_sizes[i+1];
- }
- }
-
- static std::vector<Wrapped<R>> query(WSS<R> *wss, void *q_state, void *parms) {
- auto rng = ((wss_query_parms<R> *) parms)->rng;
-
- auto state = (WSSState<R> *) q_state;
- auto sample_size = state->sample_size;
-
- std::vector<Wrapped<R>> result_set;
-
- if (sample_size == 0) {
- return result_set;
- }
- size_t attempts = 0;
- do {
- attempts++;
- size_t idx = wss->m_alias->get(rng);
- result_set.emplace_back(*wss->get_record_at(idx));
- } while (attempts < sample_size);
-
- return result_set;
- }
-
- static std::vector<Wrapped<R>> buffer_query(MutableBuffer<R> *buffer, void *state, void *parms) {
- auto st = (WSSBufferState<R> *) state;
- auto p = (wss_query_parms<R> *) parms;
-
- std::vector<Wrapped<R>> result;
- result.reserve(st->sample_size);
-
- if constexpr (Rejection) {
- for (size_t i=0; i<st->sample_size; i++) {
- auto idx = gsl_rng_uniform_int(p->rng, st->cutoff);
- auto rec = buffer->get_data() + idx;
-
- auto test = gsl_rng_uniform(p->rng) * st->max_weight;
-
- if (test <= rec->rec.weight) {
- result.emplace_back(*rec);
- }
- }
- return result;
- }
-
- for (size_t i=0; i<st->sample_size; i++) {
- auto idx = st->alias->get(p->rng);
- result.emplace_back(*(buffer->get_data() + idx));
- }
-
- return result;
- }
-
- static std::vector<R> merge(std::vector<std::vector<Wrapped<R>>> &results, void *parms) {
- std::vector<R> output;
-
- for (size_t i=0; i<results.size(); i++) {
- for (size_t j=0; j<results[i].size(); j++) {
- output.emplace_back(results[i][j].rec);
- }
- }
-
- return output;
- }
-
- static void delete_query_state(void *state) {
- auto s = (WSSState<R> *) state;
- delete s;
- }
-
- static void delete_buffer_query_state(void *state) {
- auto s = (WSSBufferState<R> *) state;
- delete s;
- }
-};
-
-}
diff --git a/include/shard/MemISAM.h b/include/shard/ISAMTree.h
index 6962c19..a610c09 100644
--- a/include/shard/MemISAM.h
+++ b/include/shard/ISAMTree.h
@@ -1,5 +1,5 @@
/*
- * include/shard/MemISAM.h
+ * include/shard/ISAMTree.h
*
* Copyright (C) 2023 Douglas B. Rumbaugh <drumbaugh@psu.edu>
* Dong Xie <dongx@psu.edu>
@@ -32,11 +32,8 @@ namespace de {
thread_local size_t mrun_cancelations = 0;
template <RecordInterface R>
-class MemISAM {
+class ISAMTree {
private:
- friend class IRSQuery<R, true>;
- friend class IRSQuery<R, false>;
- friend class ISAMRangeQuery<R>;
typedef decltype(R::key) K;
typedef decltype(R::value) V;
@@ -44,7 +41,7 @@ typedef decltype(R::value) V;
constexpr static size_t inmem_isam_node_size = 256;
constexpr static size_t inmem_isam_fanout = inmem_isam_node_size / (sizeof(K) + sizeof(char*));
-struct InMemISAMNode {
+struct InternalNode {
K keys[inmem_isam_fanout];
char* child[inmem_isam_fanout];
};
@@ -52,10 +49,10 @@ struct InMemISAMNode {
constexpr static size_t inmem_isam_leaf_fanout = inmem_isam_node_size / sizeof(R);
constexpr static size_t inmem_isam_node_keyskip = sizeof(K) * inmem_isam_fanout;
-static_assert(sizeof(InMemISAMNode) == inmem_isam_node_size, "node size does not match");
+static_assert(sizeof(InternalNode) == inmem_isam_node_size, "node size does not match");
public:
- MemISAM(MutableBuffer<R>* buffer)
+ ISAMTree(MutableBuffer<R>* buffer)
:m_reccnt(0), m_tombstone_cnt(0), m_isam_nodes(nullptr), m_deleted_cnt(0) {
m_bf = new BloomFilter<R>(BF_FPR, buffer->get_tombstone_count(), BF_HASH_FUNCS);
@@ -112,7 +109,7 @@ public:
auto level_time = TIMER_RESULT();
}
- MemISAM(MemISAM** runs, size_t len)
+ ISAMTree(ISAMTree** runs, size_t len)
: m_reccnt(0), m_tombstone_cnt(0), m_deleted_cnt(0), m_isam_nodes(nullptr) {
std::vector<Cursor<Wrapped<R>>> cursors;
cursors.reserve(len);
@@ -173,7 +170,7 @@ public:
}
}
- ~MemISAM() {
+ ~ISAMTree() {
if (m_data) free(m_data);
if (m_isam_nodes) free(m_isam_nodes);
if (m_bf) delete m_bf;
@@ -222,19 +219,18 @@ public:
return 0;
}
-private:
size_t get_lower_bound(const K& key) const {
- const InMemISAMNode* now = m_root;
+ const InternalNode* now = m_root;
while (!is_leaf(reinterpret_cast<const char*>(now))) {
- const InMemISAMNode* next = nullptr;
+ const InternalNode* next = nullptr;
for (size_t i = 0; i < inmem_isam_fanout - 1; ++i) {
if (now->child[i + 1] == nullptr || key <= now->keys[i]) {
- next = reinterpret_cast<InMemISAMNode*>(now->child[i]);
+ next = reinterpret_cast<InternalNode*>(now->child[i]);
break;
}
}
- now = next ? next : reinterpret_cast<const InMemISAMNode*>(now->child[inmem_isam_fanout - 1]);
+ now = next ? next : reinterpret_cast<const InternalNode*>(now->child[inmem_isam_fanout - 1]);
}
const Wrapped<R>* pos = reinterpret_cast<const Wrapped<R>*>(now);
@@ -244,17 +240,17 @@ private:
}
size_t get_upper_bound(const K& key) const {
- const InMemISAMNode* now = m_root;
+ const InternalNode* now = m_root;
while (!is_leaf(reinterpret_cast<const char*>(now))) {
- const InMemISAMNode* next = nullptr;
+ const InternalNode* next = nullptr;
for (size_t i = 0; i < inmem_isam_fanout - 1; ++i) {
if (now->child[i + 1] == nullptr || key < now->keys[i]) {
- next = reinterpret_cast<InMemISAMNode*>(now->child[i]);
+ next = reinterpret_cast<InternalNode*>(now->child[i]);
break;
}
}
- now = next ? next : reinterpret_cast<const InMemISAMNode*>(now->child[inmem_isam_fanout - 1]);
+ now = next ? next : reinterpret_cast<const InternalNode*>(now->child[inmem_isam_fanout - 1]);
}
const Wrapped<R>* pos = reinterpret_cast<const Wrapped<R>*>(now);
@@ -263,6 +259,8 @@ private:
return pos - m_data;
}
+
+private:
void build_internal_levels() {
size_t n_leaf_nodes = m_reccnt / inmem_isam_leaf_fanout + (m_reccnt % inmem_isam_leaf_fanout != 0);
size_t level_node_cnt = n_leaf_nodes;
@@ -275,11 +273,11 @@ private:
m_alloc_size = (node_cnt * inmem_isam_node_size) + (CACHELINE_SIZE - (node_cnt * inmem_isam_node_size) % CACHELINE_SIZE);
assert(m_alloc_size % CACHELINE_SIZE == 0);
- m_isam_nodes = (InMemISAMNode*)std::aligned_alloc(CACHELINE_SIZE, m_alloc_size);
+ m_isam_nodes = (InternalNode*)std::aligned_alloc(CACHELINE_SIZE, m_alloc_size);
m_internal_node_cnt = node_cnt;
memset(m_isam_nodes, 0, node_cnt * inmem_isam_node_size);
- InMemISAMNode* current_node = m_isam_nodes;
+ InternalNode* current_node = m_isam_nodes;
const Wrapped<R>* leaf_base = m_data;
const Wrapped<R>* leaf_stop = m_data + m_reccnt;
@@ -330,8 +328,8 @@ private:
// Members: sorted data, internal ISAM levels, reccnt;
Wrapped<R>* m_data;
psudb::BloomFilter<R> *m_bf;
- InMemISAMNode* m_isam_nodes;
- InMemISAMNode* m_root;
+ InternalNode* m_isam_nodes;
+ InternalNode* m_root;
size_t m_reccnt;
size_t m_tombstone_cnt;
size_t m_internal_node_cnt;
diff --git a/include/shard/PGM.h b/include/shard/PGM.h
index 6d76376..6b66b7d 100644
--- a/include/shard/PGM.h
+++ b/include/shard/PGM.h
@@ -31,34 +31,6 @@ using psudb::Alias;
namespace de {
-template <RecordInterface R>
-struct pgm_range_query_parms {
- decltype(R::key) lower_bound;
- decltype(R::key) upper_bound;
-};
-
-template <RecordInterface R>
-struct PGMPointLookupParms {
- decltype(R::key) target_key;
-};
-
-template <RecordInterface R>
-class PGMRangeQuery;
-
-template <RecordInterface R>
-class PGMPointLookup;
-
-template <RecordInterface R>
-struct PGMState {
- size_t start_idx;
- size_t stop_idx;
-};
-
-template <RecordInterface R>
-struct PGMBufferState {
- size_t cutoff;
-};
-
template <RecordInterface R, size_t epsilon=128>
class PGM {
private:
@@ -67,11 +39,6 @@ private:
public:
-
- // FIXME: there has to be a better way to do this
- friend class PGMRangeQuery<R>;
- friend class PGMPointLookup<R>;
-
PGM(MutableBuffer<R>* buffer)
: m_reccnt(0), m_tombstone_cnt(0) {
@@ -80,8 +47,6 @@ public:
m_data = (Wrapped<R>*)std::aligned_alloc(CACHELINE_SIZE, m_alloc_size);
std::vector<K> keys;
- //m_bf = new BloomFilter<R>(BF_FPR, buffer->get_tombstone_count(), BF_HASH_FUNCS);
-
size_t offset = 0;
m_reccnt = 0;
auto base = buffer->get_data();
@@ -110,13 +75,6 @@ public:
base->header &= 3;
m_data[m_reccnt++] = *base;
keys.emplace_back(base->rec.key);
-
- /*
- if (m_bf && base->is_tombstone()) {
- m_tombstone_cnt++;
- m_bf->insert(base->rec);
- }*/
-
base++;
}
@@ -148,8 +106,6 @@ public:
}
}
- //m_bf = new BloomFilter<R>(BF_FPR, tombstone_count, BF_HASH_FUNCS);
-
m_alloc_size = (attemp_reccnt * sizeof(Wrapped<R>)) + (CACHELINE_SIZE - (attemp_reccnt * sizeof(Wrapped<R>)) % CACHELINE_SIZE);
assert(m_alloc_size % CACHELINE_SIZE == 0);
m_data = (Wrapped<R>*)std::aligned_alloc(CACHELINE_SIZE, m_alloc_size);
@@ -172,10 +128,6 @@ public:
if (!cursor.ptr->is_deleted()) {
m_data[m_reccnt++] = *cursor.ptr;
keys.emplace_back(cursor.ptr->rec.key);
- /*if (m_bf && cursor.ptr->is_tombstone()) {
- ++m_tombstone_cnt;
- if (m_bf) m_bf->insert(cursor.ptr->rec);
- }*/
}
pq.pop();
@@ -190,15 +142,9 @@ public:
~PGM() {
if (m_data) free(m_data);
- //if (m_bf) delete m_bf;
-
}
Wrapped<R> *point_lookup(const R &rec, bool filter=false) {
- //if (filter && !m_bf->lookup(rec)) {
- // return nullptr;
- //}
-
size_t idx = get_lower_bound(rec.key);
if (idx >= m_reccnt) {
return nullptr;
@@ -284,219 +230,6 @@ private:
K m_max_key;
K m_min_key;
pgm::PGMIndex<K, epsilon> m_pgm;
- //BloomFilter<R> *m_bf;
-};
-template <RecordInterface R>
-class PGMPointLookup {
-public:
- constexpr static bool EARLY_ABORT=false;
- constexpr static bool SKIP_DELETE_FILTER=false;
-
- static void *get_query_state(PGM<R> *ts, void *parms) {
- return nullptr;
- }
-
- static void* get_buffer_query_state(MutableBuffer<R> *buffer, void *parms) {
- return nullptr;
- }
-
- static void process_query_states(void *query_parms, std::vector<void*> &shard_states, void *buff_state) {
- return;
- }
-
- static std::vector<Wrapped<R>> query(PGM<R> *ts, void *q_state, void *parms) {
- std::vector<Wrapped<R>> records;
- auto p = (PGMPointLookupParms<R> *) parms;
- auto s = (PGMState<R> *) q_state;
-
- size_t idx = ts->get_lower_bound(p->target_key);
- if (ts->get_record_at(idx)->rec.key == p->target_key) {
- records.emplace_back(*ts->get_record_at(idx));
- }
-
- return records;
- }
-
- static std::vector<Wrapped<R>> buffer_query(MutableBuffer<R> *buffer, void *state, void *parms) {
- auto p = (PGMPointLookupParms<R> *) parms;
- auto s = (PGMBufferState<R> *) state;
-
- std::vector<Wrapped<R>> records;
- for (size_t i=0; i<buffer->get_record_count(); i++) {
- auto rec = buffer->get_data() + i;
- if (rec->rec.key == p->target_key) {
- records.emplace_back(*rec);
- return records;
- }
- }
-
- return records;
- }
-
- static std::vector<R> merge(std::vector<std::vector<Wrapped<R>>> &results, void *parms) {
- std::vector<R> output;
- for (size_t i=0 ;i<results.size(); i++) {
- if (results[i].size() > 0) {
- output.emplace_back(results[i][0].rec);
- return output;
- }
- }
-
- return output;
- }
-
- static void delete_query_state(void *state) {
- }
-
- static void delete_buffer_query_state(void *state) {
- }
};
-
-
-template <RecordInterface R>
-class PGMRangeQuery {
-public:
- constexpr static bool EARLY_ABORT=false;
- constexpr static bool SKIP_DELETE_FILTER=false;
-
- static void *get_query_state(PGM<R> *ts, void *parms) {
- auto res = new PGMState<R>();
- auto p = (pgm_range_query_parms<R> *) parms;
-
- res->start_idx = ts->get_lower_bound(p->lower_bound);
- res->stop_idx = ts->get_record_count();
-
- return res;
- }
-
- static void* get_buffer_query_state(MutableBuffer<R> *buffer, void *parms) {
- auto res = new PGMBufferState<R>();
- res->cutoff = buffer->get_record_count();
-
- return res;
- }
-
- static void process_query_states(void *query_parms, std::vector<void*> &shard_states, void *buff_state) {
- return;
- }
-
- static std::vector<Wrapped<R>> query(PGM<R> *ts, void *q_state, void *parms) {
- size_t tot = 0;
- //std::vector<Wrapped<R>> records;
- auto p = (pgm_range_query_parms<R> *) parms;
- auto s = (PGMState<R> *) q_state;
-
- // if the returned index is one past the end of the
- // records for the PGM, then there are not records
- // in the index falling into the specified range.
- if (s->start_idx == ts->get_record_count()) {
- return {};
- }
-
- auto ptr = ts->get_record_at(s->start_idx);
-
- // roll the pointer forward to the first record that is
- // greater than or equal to the lower bound.
- while(ptr->rec.key < p->lower_bound) {
- ptr++;
- }
-
- while (ptr->rec.key <= p->upper_bound && ptr < ts->m_data + s->stop_idx) {
- if (ptr->is_tombstone()) --tot;
- else if (!ptr->is_deleted()) ++tot;
- //records.emplace_back(*ptr);
- ptr++;
- }
-
- return {Wrapped<R>{0, {tot, 0}}};
- //return records;
- }
-
- static std::vector<Wrapped<R>> buffer_query(MutableBuffer<R> *buffer, void *state, void *parms) {
- size_t tot = 0;
- auto p = (pgm_range_query_parms<R> *) parms;
- auto s = (PGMBufferState<R> *) state;
-
- //std::vector<Wrapped<R>> records;
- for (size_t i=0; i<s->cutoff; i++) {
- auto rec = buffer->get_data() + i;
- if (rec->rec.key >= p->lower_bound && rec->rec.key <= p->upper_bound) {
- if (rec->is_tombstone()) --tot;
- else if (!rec->is_deleted()) ++tot;
- //records.emplace_back(*rec);
- }
- }
-
- return {Wrapped<R>{0, {tot, 0}}};
- //return records;
- }
-
- static std::vector<R> merge(std::vector<std::vector<Wrapped<R>>> &results, void *parms) {
- /*std::vector<Cursor<Wrapped<R>>> cursors;
- cursors.reserve(results.size());
-
- PriorityQueue<Wrapped<R>> pq(results.size());
- size_t total = 0;
- size_t tmp_n = results.size();
-
-
- for (size_t i = 0; i < tmp_n; ++i)
- if (results[i].size() > 0){
- auto base = results[i].data();
- cursors.emplace_back(Cursor{base, base + results[i].size(), 0, results[i].size()});
- assert(i == cursors.size() - 1);
- total += results[i].size();
- pq.push(cursors[i].ptr, tmp_n - i - 1);
- } else {
- cursors.emplace_back(Cursor<Wrapped<R>>{nullptr, nullptr, 0, 0});
- }
-
- if (total == 0) {
- return std::vector<R>();
- }
-
- std::vector<R> output;
- output.reserve(total);
-
- while (pq.size()) {
- auto now = pq.peek();
- auto next = pq.size() > 1 ? pq.peek(1) : queue_record<Wrapped<R>>{nullptr, 0};
- if (!now.data->is_tombstone() && next.data != nullptr &&
- now.data->rec == next.data->rec && next.data->is_tombstone()) {
-
- pq.pop(); pq.pop();
- auto& cursor1 = cursors[tmp_n - now.version - 1];
- auto& cursor2 = cursors[tmp_n - next.version - 1];
- if (advance_cursor<Wrapped<R>>(cursor1)) pq.push(cursor1.ptr, now.version);
- if (advance_cursor<Wrapped<R>>(cursor2)) pq.push(cursor2.ptr, next.version);
- } else {
- auto& cursor = cursors[tmp_n - now.version - 1];
- if (!now.data->is_tombstone()) output.push_back(cursor.ptr->rec);
- pq.pop();
-
- if (advance_cursor<Wrapped<R>>(cursor)) pq.push(cursor.ptr, now.version);
- }
- }*/
-
- size_t tot = 0;
- for (auto& result: results)
- if (result.size() > 0) tot += result[0].rec.key;
-
- return {{tot, 0}};
- }
-
- static void delete_query_state(void *state) {
- auto s = (PGMState<R> *) state;
- delete s;
- }
-
- static void delete_buffer_query_state(void *state) {
- auto s = (PGMBufferState<R> *) state;
- delete s;
- }
-};
-
-;
-
}
diff --git a/include/shard/TrieSpline.h b/include/shard/TrieSpline.h
index a784a38..fdf8edb 100644
--- a/include/shard/TrieSpline.h
+++ b/include/shard/TrieSpline.h
@@ -30,32 +30,6 @@ using psudb::Alias;
namespace de {
-template <RecordInterface R>
-struct ts_range_query_parms {
- decltype(R::key) lower_bound;
- decltype(R::key) upper_bound;
-};
-
-template <RecordInterface R>
-class TrieSplineRangeQuery;
-
-template <RecordInterface R>
-struct TrieSplineState {
- size_t start_idx;
- size_t stop_idx;
-};
-
-template <RecordInterface R>
-struct TrieSplineBufferState {
- size_t cutoff;
- Alias* alias;
-
- ~TrieSplineBufferState() {
- delete alias;
- }
-
-};
-
template <RecordInterface R, size_t E=1024>
class TrieSpline {
private:
@@ -63,10 +37,6 @@ private:
typedef decltype(R::value) V;
public:
-
- // FIXME: there has to be a better way to do this
- friend class TrieSplineRangeQuery<R>;
-
TrieSpline(MutableBuffer<R>* buffer)
: m_reccnt(0), m_tombstone_cnt(0) {
@@ -254,8 +224,6 @@ public:
return 0;
}
-private:
-
size_t get_lower_bound(const K& key) const {
auto bound = m_ts.GetSearchBound(key);
size_t idx = bound.begin;
@@ -293,6 +261,8 @@ private:
return (m_data[idx].rec.key <= key) ? idx : m_reccnt;
}
+private:
+
Wrapped<R>* m_data;
size_t m_reccnt;
size_t m_tombstone_cnt;
@@ -302,154 +272,4 @@ private:
ts::TrieSpline<K> m_ts;
BloomFilter<R> *m_bf;
};
-
-
-template <RecordInterface R>
-class TrieSplineRangeQuery {
-public:
- constexpr static bool EARLY_ABORT=false;
- constexpr static bool SKIP_DELETE_FILTER=true;
-
- static void *get_query_state(TrieSpline<R> *ts, void *parms) {
- auto res = new TrieSplineState<R>();
- auto p = (ts_range_query_parms<R> *) parms;
-
- res->start_idx = ts->get_lower_bound(p->lower_bound);
- res->stop_idx = ts->get_record_count();
-
- return res;
- }
-
- static void* get_buffer_query_state(MutableBuffer<R> *buffer, void *parms) {
- auto res = new TrieSplineBufferState<R>();
- res->cutoff = buffer->get_record_count();
-
- return res;
- }
-
- static void process_query_states(void *query_parms, std::vector<void*> &shard_states, void *buff_state) {
- return;
- }
-
- static std::vector<Wrapped<R>> query(TrieSpline<R> *ts, void *q_state, void *parms) {
- //std::vector<Wrapped<R>> records;
- size_t tot = 0;
- auto p = (ts_range_query_parms<R> *) parms;
- auto s = (TrieSplineState<R> *) q_state;
-
- // if the returned index is one past the end of the
- // records for the TrieSpline, then there are not records
- // in the index falling into the specified range.
- if (s->start_idx == ts->get_record_count()) {
- return {};
- }
-
- auto ptr = ts->get_record_at(s->start_idx);
-
- // roll the pointer forward to the first record that is
- // greater than or equal to the lower bound.
- while(ptr->rec.key < p->lower_bound) {
- ptr++;
- }
-
-
- while (ptr->rec.key <= p->upper_bound && ptr < ts->m_data + s->stop_idx) {
- if (ptr->is_tombstone()) --tot;
- else if (!ptr->is_deleted()) ++tot;
- //records.emplace_back(*ptr);
- ptr++;
- }
-
- return {Wrapped<R>{0, {tot, 0}}};
- //return records;
- }
-
- static std::vector<Wrapped<R>> buffer_query(MutableBuffer<R> *buffer, void *state, void *parms) {
- size_t tot = 0;
- auto p = (ts_range_query_parms<R> *) parms;
- auto s = (TrieSplineBufferState<R> *) state;
-
- //std::vector<Wrapped<R>> records;
- for (size_t i=0; i<s->cutoff; i++) {
- auto rec = buffer->get_data() + i;
- if (rec->rec.key >= p->lower_bound && rec->rec.key <= p->upper_bound) {
- if (rec->is_tombstone()) --tot;
- else if (!rec->is_deleted()) ++tot;
- //records.emplace_back(*rec);
- }
-
- }
-
- return {Wrapped<R>{0, {tot, 0}}};
- //return records;
- }
-
- static std::vector<R> merge(std::vector<std::vector<Wrapped<R>>> &results, void *parms) {
-/*
- std::vector<Cursor<Wrapped<R>>> cursors;
- cursors.reserve(results.size());
-
- PriorityQueue<Wrapped<R>> pq(results.size());
- size_t total = 0;
- size_t tmp_n = results.size();
-
-
- for (size_t i = 0; i < tmp_n; ++i)
- if (results[i].size() > 0){
- auto base = results[i].data();
- cursors.emplace_back(Cursor{base, base + results[i].size(), 0, results[i].size()});
- assert(i == cursors.size() - 1);
- total += results[i].size();
- pq.push(cursors[i].ptr, tmp_n - i - 1);
- } else {
- cursors.emplace_back(Cursor<Wrapped<R>>{nullptr, nullptr, 0, 0});
- }
-
- if (total == 0) {
- return std::vector<R>();
- }
-
- std::vector<R> output;
- output.reserve(total);
-
- while (pq.size()) {
- auto now = pq.peek();
- auto next = pq.size() > 1 ? pq.peek(1) : queue_record<Wrapped<R>>{nullptr, 0};
- if (!now.data->is_tombstone() && next.data != nullptr &&
- now.data->rec == next.data->rec && next.data->is_tombstone()) {
-
- pq.pop(); pq.pop();
- auto& cursor1 = cursors[tmp_n - now.version - 1];
- auto& cursor2 = cursors[tmp_n - next.version - 1];
- if (advance_cursor<Wrapped<R>>(cursor1)) pq.push(cursor1.ptr, now.version);
- if (advance_cursor<Wrapped<R>>(cursor2)) pq.push(cursor2.ptr, next.version);
- } else {
- auto& cursor = cursors[tmp_n - now.version - 1];
- if (!now.data->is_tombstone()) output.push_back(cursor.ptr->rec);
- pq.pop();
-
- if (advance_cursor<Wrapped<R>>(cursor)) pq.push(cursor.ptr, now.version);
- }
- }
-
- return output;*/
-
- size_t tot = 0;
- for (auto& result: results)
- if (result.size() > 0) tot += result[0].rec.key;
-
- return {{tot, 0}};
- }
-
- static void delete_query_state(void *state) {
- auto s = (TrieSplineState<R> *) state;
- delete s;
- }
-
- static void delete_buffer_query_state(void *state) {
- auto s = (TrieSplineBufferState<R> *) state;
- delete s;
- }
-};
-
}
diff --git a/tests/wss_tests.cpp b/tests/alias_tests.cpp
index cdc8001..b9e678b 100644
--- a/tests/wss_tests.cpp
+++ b/tests/alias_tests.cpp
@@ -1,7 +1,7 @@
/*
- * tests/wss_tests.cpp
+ * tests/alias_tests.cpp
*
- * Unit tests for WSS (Augmented B+Tree) shard
+ * Unit tests for Alias shard
*
* Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu>
* Dong Xie <dongx@psu.edu>
@@ -10,14 +10,15 @@
*
*/
-#include "shard/WSS.h"
+#include "shard/Alias.h"
+#include "query/wss.h"
#include "testing.h"
#include <check.h>
using namespace de;
-typedef WSS<WRec> Shard;
+typedef Alias<WRec> Shard;
START_TEST(t_mbuffer_init)
{
@@ -45,7 +46,7 @@ START_TEST(t_mbuffer_init)
}
-START_TEST(t_wss_init)
+START_TEST(t_alias_init)
{
size_t n = 512;
auto mbuffer1 = create_test_mbuffer<WRec>(n);
@@ -101,7 +102,7 @@ START_TEST(t_point_lookup)
size_t n = 10000;
auto buffer = create_double_seq_mbuffer<WRec>(n, false);
- auto wss = Shard(buffer);
+ auto alias = Shard(buffer);
for (size_t i=0; i<n; i++) {
WRec r;
@@ -109,7 +110,7 @@ START_TEST(t_point_lookup)
r.key = rec->rec.key;
r.value = rec->rec.value;
- auto result = wss.point_lookup(r);
+ auto result = alias.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);
@@ -125,14 +126,14 @@ START_TEST(t_point_lookup_miss)
size_t n = 10000;
auto buffer = create_double_seq_mbuffer<WRec>(n, false);
- auto wss = Shard(buffer);
+ auto alias = 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);
+ auto result = alias.point_lookup(r);
ck_assert_ptr_null(result);
}
@@ -169,7 +170,7 @@ START_TEST(t_full_cancelation)
END_TEST
-START_TEST(t_wss_query)
+START_TEST(t_alias_query)
{
size_t n=1000;
auto buffer = create_weighted_mbuffer<WRec>(n);
@@ -179,15 +180,15 @@ START_TEST(t_wss_query)
size_t k = 1000;
size_t cnt[3] = {0};
- wss_query_parms<WRec> parms = {k};
+ wss: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);
+ auto state = wss::Query<Shard, WRec>::get_query_state(shard, &parms);
+ ((wss::State<WRec> *) state)->sample_size = k;
+ auto result = wss::Query<Shard, WRec>::query(shard, state, &parms);
total_samples += result.size();
@@ -195,7 +196,7 @@ START_TEST(t_wss_query)
cnt[result[j].rec.key - 1]++;
}
- WSSQuery<WRec>::delete_query_state(state);
+ wss::Query<Shard, WRec>::delete_query_state(state);
}
ck_assert(roughly_equal(cnt[0], (double) total_samples/4.0, total_samples, .05));
@@ -209,7 +210,7 @@ START_TEST(t_wss_query)
END_TEST
-START_TEST(t_wss_query_merge)
+START_TEST(t_alias_query_merge)
{
size_t n=1000;
auto buffer = create_weighted_mbuffer<WRec>(n);
@@ -222,25 +223,25 @@ START_TEST(t_wss_query_merge)
size_t k = 1000;
size_t cnt[3] = {0};
- wss_query_parms<WRec> parms = {k};
+ wss: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 state1 = wss::Query<Shard, WRec>::get_query_state(shard, &parms);
+ ((wss::State<WRec> *) state1)->sample_size = k;
+ results[0] = wss::Query<Shard, 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);
+ auto state2 = wss::Query<Shard, WRec>::get_query_state(shard, &parms);
+ ((wss::State<WRec> *) state2)->sample_size = k;
+ results[1] = wss::Query<Shard, WRec>::query(shard, state2, &parms);
- WSSQuery<WRec>::delete_query_state(state1);
- WSSQuery<WRec>::delete_query_state(state2);
+ wss::Query<Shard, WRec>::delete_query_state(state1);
+ wss::Query<Shard, WRec>::delete_query_state(state2);
}
- auto merged = WSSQuery<WRec>::merge(results, nullptr);
+ auto merged = wss::Query<Shard, WRec>::merge(results, nullptr);
ck_assert_int_eq(merged.size(), 2*k);
for (size_t i=0; i<merged.size(); i++) {
@@ -255,7 +256,7 @@ START_TEST(t_wss_query_merge)
END_TEST
-START_TEST(t_wss_buffer_query_scan)
+START_TEST(t_alias_buffer_query_scan)
{
size_t n=1000;
auto buffer = create_weighted_mbuffer<WRec>(n);
@@ -266,22 +267,22 @@ START_TEST(t_wss_buffer_query_scan)
size_t k = 1000;
size_t cnt[3] = {0};
- wss_query_parms<WRec> parms = {k};
+ wss: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);
+ auto state = wss::Query<Shard, WRec, false>::get_buffer_query_state(buffer, &parms);
+ ((wss::BufferState<WRec> *) state)->sample_size = k;
+ auto result = wss::Query<Shard, 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);
+ wss::Query<Shard, WRec, false>::delete_buffer_query_state(state);
}
ck_assert(roughly_equal(cnt[0], (double) total_samples/4.0, total_samples, .05));
@@ -294,7 +295,7 @@ START_TEST(t_wss_buffer_query_scan)
END_TEST
-START_TEST(t_wss_buffer_query_rejection)
+START_TEST(t_alias_buffer_query_rejection)
{
size_t n=1000;
auto buffer = create_weighted_mbuffer<WRec>(n);
@@ -305,15 +306,15 @@ START_TEST(t_wss_buffer_query_rejection)
size_t k = 1000;
size_t cnt[3] = {0};
- wss_query_parms<WRec> parms = {k};
+ wss: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);
+ auto state = wss::Query<Shard, WRec>::get_buffer_query_state(buffer, &parms);
+ ((wss::BufferState<WRec> *) state)->sample_size = k;
+ auto result = wss::Query<Shard, WRec>::buffer_query(buffer, state, &parms);
total_samples += result.size();
@@ -321,7 +322,7 @@ START_TEST(t_wss_buffer_query_rejection)
cnt[result[j].rec.key - 1]++;
}
- WSSQuery<WRec>::delete_buffer_query_state(state);
+ wss::Query<Shard, WRec>::delete_buffer_query_state(state);
}
ck_assert(roughly_equal(cnt[0], (double) total_samples/4.0, total_samples, .1));
@@ -336,32 +337,32 @@ END_TEST
Suite *unit_testing()
{
- Suite *unit = suite_create("WSS Shard Unit Testing");
+ Suite *unit = suite_create("Alias Shard Unit Testing");
- TCase *create = tcase_create("de::WSS constructor Testing");
+ TCase *create = tcase_create("de::Alias constructor Testing");
tcase_add_test(create, t_mbuffer_init);
- tcase_add_test(create, t_wss_init);
+ tcase_add_test(create, t_alias_init);
tcase_set_timeout(create, 100);
suite_add_tcase(unit, create);
- TCase *tombstone = tcase_create("de:WSS::tombstone cancellation Testing");
+ TCase *tombstone = tcase_create("de:Alias::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 *lookup = tcase_create("de:Alias: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);
+ TCase *sampling = tcase_create("de:Alias::AliasQuery Testing");
+ tcase_add_test(sampling, t_alias_query);
+ tcase_add_test(sampling, t_alias_query_merge);
+ tcase_add_test(sampling, t_alias_buffer_query_rejection);
+ tcase_add_test(sampling, t_alias_buffer_query_scan);
suite_add_tcase(unit, sampling);
return unit;
diff --git a/tests/memisam_tests.cpp b/tests/memisam_tests.cpp
index 0ae97dc..d3b8087 100644
--- a/tests/memisam_tests.cpp
+++ b/tests/memisam_tests.cpp
@@ -1,7 +1,7 @@
/*
- * 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>
@@ -10,14 +10,15 @@
*
*/
-#include "shard/MemISAM.h"
+#include "shard/ISAMTree.h"
+#include "query/irs.h"
#include "testing.h"
#include <check.h>
using namespace de;
-typedef MemISAM<Rec> Shard;
+typedef ISAMTree<Rec> Shard;
START_TEST(t_mbuffer_init)
{
@@ -181,15 +182,15 @@ START_TEST(t_irs_query)
size_t k = 100;
size_t cnt[3] = {0};
- irs_query_parms<Rec> parms = {lower_key, upper_key, k};
+ irs::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);
+ auto state = irs::Query<Shard, Rec, false>::get_query_state(&isam, &parms);
+ ((irs::State<WRec> *) state)->sample_size = k;
+ auto result = irs::Query<Shard, Rec, false>::query(&isam, state, &parms);
ck_assert_int_eq(result.size(), k);
@@ -198,7 +199,7 @@ START_TEST(t_irs_query)
ck_assert_int_ge(rec.rec.key, lower_key);
}
- IRSQuery<Rec, false>::delete_query_state(state);
+ irs::Query<Shard, Rec, false>::delete_query_state(state);
}
gsl_rng_free(parms.rng);
@@ -220,25 +221,25 @@ START_TEST(t_irs_query_merge)
size_t k = 1000;
size_t cnt[3] = {0};
- irs_query_parms<Rec> parms = {lower_key, upper_key, k};
+ irs::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 state1 = irs::Query<Shard, Rec>::get_query_state(&shard, &parms);
+ ((irs::State<WRec> *) state1)->sample_size = k;
+ results[0] = irs::Query<Shard, 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);
+ auto state2 = irs::Query<Shard, Rec>::get_query_state(&shard, &parms);
+ ((irs::State<WRec> *) state2)->sample_size = k;
+ results[1] = irs::Query<Shard, Rec>::query(&shard, state2, &parms);
- IRSQuery<Rec>::delete_query_state(state1);
- IRSQuery<Rec>::delete_query_state(state2);
+ irs::Query<Shard, Rec>::delete_query_state(state1);
+ irs::Query<Shard, Rec>::delete_query_state(state2);
}
- auto merged = IRSQuery<Rec>::merge(results, nullptr);
+ auto merged = irs::Query<Shard, Rec>::merge(results, nullptr);
ck_assert_int_eq(merged.size(), 2*k);
for (size_t i=0; i<merged.size(); i++) {
@@ -263,15 +264,15 @@ START_TEST(t_irs_buffer_query_scan)
size_t k = 100;
size_t cnt[3] = {0};
- irs_query_parms<Rec> parms = {lower_key, upper_key, k};
+ irs::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);
+ auto state = irs::Query<Shard, Rec, false>::get_buffer_query_state(buffer, &parms);
+ ((irs::BufferState<WRec> *) state)->sample_size = k;
+ auto result = irs::Query<Shard, Rec, false>::buffer_query(buffer, state, &parms);
ck_assert_int_eq(result.size(), k);
@@ -280,7 +281,7 @@ START_TEST(t_irs_buffer_query_scan)
ck_assert_int_ge(rec.rec.key, lower_key);
}
- IRSQuery<Rec, false>::delete_buffer_query_state(state);
+ irs::Query<Shard, Rec, false>::delete_buffer_query_state(state);
}
gsl_rng_free(parms.rng);
@@ -300,15 +301,15 @@ START_TEST(t_irs_buffer_query_rejection)
size_t k = 10000;
size_t cnt[3] = {0};
- irs_query_parms<Rec> parms = {lower_key, upper_key, k};
+ irs::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);
+ auto state = irs::Query<Shard, Rec>::get_buffer_query_state(buffer, &parms);
+ ((irs::BufferState<WRec> *) state)->sample_size = k;
+ auto result = irs::Query<Shard, Rec>::buffer_query(buffer, state, &parms);
ck_assert_int_gt(result.size(), 0);
ck_assert_int_le(result.size(), k);
@@ -318,7 +319,7 @@ START_TEST(t_irs_buffer_query_rejection)
ck_assert_int_ge(rec.rec.key, lower_key);
}
- IRSQuery<Rec>::delete_buffer_query_state(state);
+ irs::Query<Shard, Rec>::delete_buffer_query_state(state);
}
gsl_rng_free(parms.rng);
@@ -329,27 +330,27 @@ END_TEST
Suite *unit_testing()
{
- Suite *unit = suite_create("MemISAM Shard Unit Testing");
+ Suite *unit = suite_create("ISAMTree Shard Unit Testing");
- TCase *create = tcase_create("de::MemISAM constructor Testing");
+ TCase *create = tcase_create("de::ISAMTree 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 *tombstone = tcase_create("de:ISAMTree::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 *lookup = tcase_create("de:ISAMTree: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:MemISAM::MemISAMQuery Testing");
+ TCase *sampling = tcase_create("de:ISAMTree::ISAMTreeQuery 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);
diff --git a/tests/pgm_tests.cpp b/tests/pgm_tests.cpp
index 0552417..1565384 100644
--- a/tests/pgm_tests.cpp
+++ b/tests/pgm_tests.cpp
@@ -11,6 +11,7 @@
*/
#include "shard/PGM.h"
+#include "query/rangequery.h"
#include "testing.h"
#include <check.h>
@@ -144,13 +145,13 @@ START_TEST(t_range_query)
auto buffer = create_sequential_mbuffer<Rec>(100, 1000);
auto shard = Shard(buffer);
- pgm_range_query_parms<Rec> parms;
+ rq::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);
+ 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++) {
@@ -167,13 +168,13 @@ START_TEST(t_buffer_range_query)
{
auto buffer = create_sequential_mbuffer<Rec>(100, 1000);
- pgm_range_query_parms<Rec> parms;
+ rq::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);
+ auto state = rq::Query<Shard, Rec>::get_buffer_query_state(buffer, &parms);
+ auto result = rq::Query<Shard, Rec>::buffer_query(buffer, 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++) {
@@ -194,21 +195,21 @@ START_TEST(t_range_query_merge)
auto shard1 = Shard(buffer1);
auto shard2 = Shard(buffer2);
- pgm_range_query_parms<Rec> parms;
+ 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 = PGMRangeQuery<Rec>::get_query_state(&shard1, &parms);
- auto state2 = PGMRangeQuery<Rec>::get_query_state(&shard2, &parms);
+ 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] = PGMRangeQuery<Rec>::query(&shard1, state1, &parms);
- results[1] = PGMRangeQuery<Rec>::query(&shard2, state2, &parms);
+ results[0] = rq::Query<Shard, Rec>::query(&shard1, state1, &parms);
+ results[1] = rq::Query<Shard, Rec>::query(&shard2, state2, &parms);
- PGMRangeQuery<Rec>::delete_query_state(state1);
- PGMRangeQuery<Rec>::delete_query_state(state2);
+ 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);
@@ -221,7 +222,7 @@ START_TEST(t_range_query_merge)
}
}
- auto result = PGMRangeQuery<Rec>::merge(proc_results, nullptr);
+ auto result = rq::Query<Shard, Rec>::merge(proc_results, nullptr);
std::sort(result.begin(), result.end());
ck_assert_int_eq(result.size(), result_size);
diff --git a/tests/triespline_tests.cpp b/tests/triespline_tests.cpp
index 6f63961..101f143 100644
--- a/tests/triespline_tests.cpp
+++ b/tests/triespline_tests.cpp
@@ -13,6 +13,7 @@
#include <functional>
#include "shard/TrieSpline.h"
+#include "query/rangequery.h"
#include "testing.h"
#include <check.h>
@@ -176,13 +177,13 @@ START_TEST(t_range_query)
auto buffer = create_sequential_mbuffer<Rec>(100, 1000);
auto shard = Shard(buffer);
- ts_range_query_parms<Rec> parms;
+ rq::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);
+ 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++) {
@@ -199,13 +200,13 @@ START_TEST(t_buffer_range_query)
{
auto buffer = create_sequential_mbuffer<Rec>(100, 1000);
- ts_range_query_parms<Rec> parms;
+ rq::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);
+ auto state = rq::Query<Shard, Rec>::get_buffer_query_state(buffer, &parms);
+ auto result = rq::Query<Shard, Rec>::buffer_query(buffer, 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++) {