From 7c03d771475421c1d5a2bbc135242536af1a371c Mon Sep 17 00:00:00 2001 From: Douglas Rumbaugh Date: Mon, 25 Sep 2023 10:49:36 -0400 Subject: Re-structuring Project + scheduling updates This is a big one--probably should have split it apart, but I'm feeling lazy this morning. * Organized the mess of header files in include/framework by splitting them out into their own subdirectories, and renaming a few files to remove redundancies introduced by the directory structure. * Introduced a new framework/ShardRequirements.h header file for simpler shard development. This header simply contains the necessary includes from framework/* for creating shard files. This should help to remove structural dependencies from the framework file structure and shards, as well as centralizing the necessary framework files to make shard development easier. * Created a (currently dummy) SchedulerInterface, and make the scheduler implementation a template parameter of the dynamic extension for easier testing of various scheduling policies. There's still more work to be done to fully integrate the scheduler (queries, multiple buffers), but some more of the necessary framework code for this has been added as well. * Adjusted the Task interface setup for the scheduler. The task structures have been removed from ExtensionStructure and placed in their own header file. Additionally, I started experimenting with using std::variant, as opposed to inheritence, to implement subtype polymorphism on the Merge and Query tasks. The scheduler now has a general task queue that contains both, and std::variant, std::visit, and std::get are used to manipulate them without virtual functions. * Removed Alex.h, as it can't build anyway. There's a branch out there containing the Alex implementation stripped of the C++20 stuff. So there's no need to keep it here. --- include/framework/interface/Record.h | 214 +++++++++++++++++++++++++++++++++++ 1 file changed, 214 insertions(+) create mode 100644 include/framework/interface/Record.h (limited to 'include/framework/interface/Record.h') diff --git a/include/framework/interface/Record.h b/include/framework/interface/Record.h new file mode 100644 index 0000000..1ef1984 --- /dev/null +++ b/include/framework/interface/Record.h @@ -0,0 +1,214 @@ +/* + * include/framework/RecordInterface.h + * + * Copyright (C) 2023 Douglas Rumbaugh + * Dong Xie + * + * All rights reserved. Published under the Modified BSD License. + * + */ +#pragma once + +#include +#include +#include + +#include "psu-util/hash.h" + +namespace de { + +template +concept RecordInterface = requires(R r, R s) { + { r < s } ->std::convertible_to; + { r == s } ->std::convertible_to; +}; + +template +concept WeightedRecordInterface = requires(R r) { + {r.weight} -> std::convertible_to; +}; + +template +concept NDRecordInterface = RecordInterface && requires(R r, R s) { + {r.calc_distance(s)} -> std::convertible_to; +}; + +template +concept KVPInterface = RecordInterface && requires(R r) { + r.key; + r.value; +}; + +template +concept AlexInterface = KVPInterface && requires(R r) { + {r.key} -> std::convertible_to; + {r.value} -> std::convertible_to; +}; + +template +concept WrappedInterface = RecordInterface && requires(R r, R s, bool b) { + {r.header} -> std::convertible_to; + r.rec; + {r.set_delete()}; + {r.is_deleted()} -> std::convertible_to; + {r.set_tombstone(b)}; + {r.is_tombstone()} -> std::convertible_to; + {r < s} -> std::convertible_to; + {r == s} ->std::convertible_to; +}; + +template +struct Wrapped { + uint32_t header; + R rec; + + inline void set_delete() { + header |= 2; + } + + inline bool is_deleted() const { + return header & 2; + } + + inline void set_tombstone(bool val=true) { + if (val) { + header |= val; + } else { + header &= 0; + } + } + + inline bool is_tombstone() const { + return header & 1; + } + + inline bool operator<(const Wrapped& other) const { + return rec < other.rec || (rec == other.rec && header < other.header); + } + + inline bool operator==(const Wrapped& other) const { + return rec == other.rec; + } + +}; + +template +struct Record { + K key; + V value; + uint32_t header = 0; + + inline bool operator<(const Record& other) const { + return key < other.key || (key == other.key && value < other.value); + } + + inline bool operator==(const Record& other) const { + return key == other.key && value == other.value; + } +}; + +template +struct WeightedRecord { + K key; + V value; + W weight = 1; + + inline bool operator==(const WeightedRecord& other) const { + return key == other.key && value == other.value; + } + + inline bool operator<(const WeightedRecord& other) const { + return key < other.key || (key == other.key && value < other.value); + } +}; + + +template +struct CosinePoint{ + V data[D]; + + inline bool operator==(const CosinePoint& other) const { + for (size_t i=0; i other.data[i]) { + return false; + } + } + + return false; + } + + inline double calc_distance(const CosinePoint& other) const { + + double prod = 0; + double asquared = 0; + double bsquared = 0; + + for (size_t i=0; i +struct EuclidPoint{ + V data[D]; + + inline bool operator==(const EuclidPoint& other) const { + for (size_t i=0; i other.data[i]) { + return false; + } + } + + return false; + } + + inline double calc_distance(const EuclidPoint& other) const { + double dist = 0; + for (size_t i=0; i +struct RecordHash { + size_t operator()(R const &rec) const { + return psudb::hash_bytes((std::byte *) &rec, sizeof(R)); + } +}; + +} -- cgit v1.2.3 From d2279e1b96d352a0af1d425dcaaf93e8a26a8d52 Mon Sep 17 00:00:00 2001 From: Douglas Rumbaugh Date: Mon, 30 Oct 2023 17:15:05 -0400 Subject: General Comment + Consistency updates --- include/framework/interface/Record.h | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) (limited to 'include/framework/interface/Record.h') diff --git a/include/framework/interface/Record.h b/include/framework/interface/Record.h index 1ef1984..bf495df 100644 --- a/include/framework/interface/Record.h +++ b/include/framework/interface/Record.h @@ -1,11 +1,12 @@ /* - * include/framework/RecordInterface.h + * include/framework/interface/Record.h * * Copyright (C) 2023 Douglas Rumbaugh - * Dong Xie * * All rights reserved. Published under the Modified BSD License. * + * FIXME: the record implementations could probably be broken out into + * different files, leaving only the interface here */ #pragma once -- cgit v1.2.3 From 357cab549c2ed33970562b84ff6f83923742343d Mon Sep 17 00:00:00 2001 From: Douglas Rumbaugh Date: Tue, 7 Nov 2023 15:34:24 -0500 Subject: Comment and License updates --- include/framework/interface/Record.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'include/framework/interface/Record.h') diff --git a/include/framework/interface/Record.h b/include/framework/interface/Record.h index bf495df..457078d 100644 --- a/include/framework/interface/Record.h +++ b/include/framework/interface/Record.h @@ -3,7 +3,7 @@ * * Copyright (C) 2023 Douglas Rumbaugh * - * All rights reserved. Published under the Modified BSD License. + * Distributed under the Modified BSD License. * * FIXME: the record implementations could probably be broken out into * different files, leaving only the interface here -- cgit v1.2.3 From 711769574e647839677739192698e400529efe75 Mon Sep 17 00:00:00 2001 From: Douglas Rumbaugh Date: Thu, 8 Feb 2024 16:38:44 -0500 Subject: Updated VPTree to new shard/query interfaces --- include/framework/interface/Record.h | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+) (limited to 'include/framework/interface/Record.h') diff --git a/include/framework/interface/Record.h b/include/framework/interface/Record.h index 457078d..29df4b6 100644 --- a/include/framework/interface/Record.h +++ b/include/framework/interface/Record.h @@ -212,4 +212,23 @@ struct RecordHash { } }; +template +class DistCmpMax { +public: + DistCmpMax(R *baseline) : P(baseline) {} + + inline bool operator()(const R *a, const R *b) requires WrappedInterface { + return a->rec.calc_distance(P->rec) > b->rec.calc_distance(P->rec); + } + + inline bool operator()(const R *a, const R *b) requires (!WrappedInterface){ + return a->calc_distance(*P) > b->calc_distance(*P); + } + +private: + R *P; +}; + + + } -- cgit v1.2.3 From 402fc269c0aaa671d84a6d15918735ad4b90e6b2 Mon Sep 17 00:00:00 2001 From: Douglas Rumbaugh Date: Fri, 9 Feb 2024 12:30:21 -0500 Subject: Comment updates/fixes --- include/framework/interface/Record.h | 7 ++----- 1 file changed, 2 insertions(+), 5 deletions(-) (limited to 'include/framework/interface/Record.h') diff --git a/include/framework/interface/Record.h b/include/framework/interface/Record.h index 29df4b6..5b9f307 100644 --- a/include/framework/interface/Record.h +++ b/include/framework/interface/Record.h @@ -138,7 +138,7 @@ struct CosinePoint{ return true; } - // lexicographic order + /* lexicographic order */ inline bool operator<(const CosinePoint& other) const { for (size_t i=0; i