From 4d82c7e2704c035e33b9b606c409e5fac0f4f708 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Roman=20Smr=C5=BE?= Date: Sun, 9 Oct 2022 23:02:54 +0200 Subject: Stored set --- include/erebos/merge.h | 20 ++++++ include/erebos/set.h | 96 ++++++++++++++++++++++++++ include/erebos/storage.h | 10 +++ src/CMakeLists.txt | 1 + src/main.cpp | 36 ++++++++++ src/set.cpp | 171 +++++++++++++++++++++++++++++++++++++++++++++++ src/set.h | 19 ++++++ test/storage.test | 59 ++++++++++++++++ 8 files changed, 412 insertions(+) create mode 100644 include/erebos/merge.h create mode 100644 include/erebos/set.h create mode 100644 src/set.cpp create mode 100644 src/set.h diff --git a/include/erebos/merge.h b/include/erebos/merge.h new file mode 100644 index 0000000..bef8212 --- /dev/null +++ b/include/erebos/merge.h @@ -0,0 +1,20 @@ +#pragma once + +#include + +namespace erebos +{ + +template struct Mergeable +{ +}; + +template<> struct Mergeable>> +{ + using Component = Object; + + static vector> components(const vector> & x) { return x; } + static vector> merge(const vector> & x) { return x; } +}; + +} diff --git a/include/erebos/set.h b/include/erebos/set.h new file mode 100644 index 0000000..f625cb0 --- /dev/null +++ b/include/erebos/set.h @@ -0,0 +1,96 @@ +#pragma once + +#include +#include + +namespace erebos +{ + +class SetViewBase; +template class SetView; + +class SetBase +{ +protected: + struct Priv; + + SetBase(); + SetBase(const vector &); + SetBase(shared_ptr); + + shared_ptr add(Storage &, const vector &) const; + + vector> toList() const; + +public: + vector digests() const; + +protected: + shared_ptr p; +}; + +template +class Set : public SetBase +{ + Set(shared_ptr p): SetBase(p) {}; +public: + Set() = default; + Set(const vector & refs): SetBase(move(refs)) {} + Set(const Set &) = default; + Set(Set &&) = default; + Set & operator=(const Set &) = default; + Set & operator=(Set &&) = default; + + static Set load(const vector & refs) { return Set(move(refs)); } + + Set add(Storage &, const T &) const; + + template + SetView view(F && cmp) const; +}; + +template +class SetView +{ +public: + template + SetView(F && cmp, const vector> & refs); + + typename vector::const_iterator begin() const { return items.begin(); } + typename vector::const_iterator end() const { return items.end(); } + +private: + vector items; +}; + +template +Set Set::add(Storage & st, const T & x) const +{ + return Set(SetBase::add(st, storedRefs(Mergeable::components(x)))); +} + +template +template +SetView Set::view(F && cmp) const +{ + return SetView(std::move(cmp), toList()); +} + +template +template +SetView::SetView(F && cmp, const vector> & refs) +{ + items.reserve(refs.size()); + for (const auto & crefs : refs) { + vector::Component>> comps; + comps.reserve(crefs.size()); + for (const auto & r : crefs) + comps.push_back(Stored::Component>::load(r)); + + filterAncestors(comps); + items.push_back(Mergeable::merge(comps)); + } + std::sort(items.begin(), items.end(), cmp); +} + +} diff --git a/include/erebos/storage.h b/include/erebos/storage.h index 15ee0bb..735b399 100644 --- a/include/erebos/storage.h +++ b/include/erebos/storage.h @@ -668,6 +668,16 @@ WatchedHead::~WatchedHead() T::headTypeId, Head::id(), watcherId); } +template +vector storedRefs(const vector> & v) +{ + vector res; + res.reserve(v.size()); + for (const auto & x : v) + res.push_back(x.ref()); + return res; +} + } namespace std diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt index b68860a..72094b8 100644 --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -13,6 +13,7 @@ add_library(erebos pairing.cpp pubkey.cpp service.cpp + set.cpp state.cpp storage.cpp sync.cpp diff --git a/src/main.cpp b/src/main.cpp index 4dc4582..95d3eeb 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -1,6 +1,7 @@ #include #include #include +#include #include #include @@ -162,6 +163,39 @@ void storedRoots(const vector & args) printLine(ss.str()); } +void storedSetAdd(const vector & args) +{ + auto iref = st.ref(Digest(args.at(0))); + if (!iref) + throw invalid_argument("ref " + args.at(0) + " not found"); + + auto set = args.size() > 1 ? + Set>>::load({ *st.ref(Digest(args.at(1))) }) : + Set>>(); + + ostringstream ss; + ss << "stored-set-add"; + for (const auto & d : set.add(st, { Stored::load(*iref) }).digests()) + ss << " " << string(d); + printLine(ss.str()); +} + +void storedSetList(const vector & args) +{ + auto ref = st.ref(Digest(args.at(0))); + if (!ref) + throw invalid_argument("ref " + args.at(0) + " not found"); + + for (const auto & vec : Set>>::load({ *ref }).view(std::less{})) { + ostringstream ss; + ss << "stored-set-item"; + for (const auto & x : vec) + ss << " " << string(x.ref().digest()); + printLine(ss.str()); + } + printLine("stored-set-done"); +} + void createIdentity(const vector & args) { optional identity; @@ -353,6 +387,8 @@ vector commands = { { "store", store }, { "stored-generation", storedGeneration }, { "stored-roots", storedRoots }, + { "stored-set-add", storedSetAdd }, + { "stored-set-list", storedSetList }, { "create-identity", createIdentity }, { "start-server", startServer }, { "stop-server", stopServer }, diff --git a/src/set.cpp b/src/set.cpp new file mode 100644 index 0000000..001bce3 --- /dev/null +++ b/src/set.cpp @@ -0,0 +1,171 @@ +#include "set.h" + +#include +#include +#include + +namespace erebos { + +using std::pair; +using std::unordered_map; +using std::unordered_set; +using std::move; + +SetBase::SetBase(): + p(make_shared()) +{ +} + +SetBase::SetBase(const vector & refs) +{ + vector> items; + for (const auto & r : refs) + items.push_back(Stored::load(r)); + + p = shared_ptr(new Priv { + .items = move(items), + }); +} + +SetBase::SetBase(shared_ptr p_): + p(move(p_)) +{ +} + +shared_ptr SetBase::add(Storage & st, const vector & refs) const +{ + auto item = st.store(SetItem { + .prev = p->items, + .item = refs, + }); + + return shared_ptr(new Priv { + .items = { move(item) }, + }); +} + +static void gatherSetItems(unordered_set & seenSet, unordered_set & seenElem, + vector & res, const Stored & item) +{ + if (!seenElem.insert(item.ref().digest()).second) + return; + + for (const auto & r : item->item) + if (seenSet.insert(r.digest()).second) + res.push_back(r); + + for (const auto & p : item->prev) + gatherSetItems(seenSet, seenElem, res, p); +} + +vector> SetBase::toList() const +{ + /* Splits the graph starting from all set item refs into connected + * components (partitions), each such partition makes one set item, + * merged together in the templated SetView constructor. */ + + // Gather all item references + vector items; + { + unordered_set seenSet, seenElem; + for (const auto & i : p->items) + gatherSetItems(seenSet, seenElem, items, i); + } + + unordered_map partMap; // maps item ref to partition number + vector partMerge; // maps partitions to resulting one after partition merge + + // Use (cached) root set for assigning partition numbers + for (const auto & item : items) { + const auto roots = item.roots(); + unsigned part = partMerge.size(); + + // If any root has partition number already, pick the smallest one + for (const auto & rdgst : roots) { + auto it = partMap.find(rdgst); + if (it != partMap.end() && it->second < part) + part = it->second; + } + + // Update partition number for the roots and if this item + // merges some partitions, also update the merge info + for (const auto & rdgst : roots) { + auto it = partMap.find(rdgst); + if (it == partMap.end()) { + partMap.emplace(rdgst, part); + } else if (it->second != part) { + partMerge[it->second] = part; + it->second = part; + } + } + + // If no existing partition has been touched, mark a new one + if (part == partMerge.size()) + partMerge.push_back(part); + + // And store resulting partition number + partMap.emplace(item.digest(), part); + } + + // Get all the refs for each partition + vector> res(partMerge.size()); + for (const auto & item : items) { + unsigned part = partMap[item.digest()]; + for (unsigned p = partMerge[part]; p != part; p = partMerge[p]) + part = p; + res[part].push_back(item); + } + + // Remove empty elements (merged partitions) from result list + res.erase(std::remove(res.begin(), res.end(), vector()), res.end()); + + return res; +} + +vector SetBase::digests() const +{ + vector res; + res.reserve(p->items.size()); + for (const auto & i : p->items) + res.push_back(i.ref().digest()); + return res; +} + +SetItem SetItem::load(const Ref & ref) +{ + if (auto rec = ref->asRecord()) { + vector> prev; + for (auto p : rec->items("PREV")) + if (const auto & x = p.as()) + prev.push_back(*x); + + vector item; + for (auto i : rec->items("item")) + if (const auto & x = i.asRef()) + item.push_back(*x); + + return SetItem { + .prev = std::move(prev), + .item = std::move(item), + }; + } + + return SetItem { + .prev = {}, + .item = {}, + }; +} + +Ref SetItem::store(const Storage & st) const +{ + vector items; + + for (const auto & p : prev) + items.emplace_back("PREV", p.ref()); + for (const auto & r : item) + items.emplace_back("item", r); + + return st.storeObject(Record(std::move(items))); +} + +} diff --git a/src/set.h b/src/set.h new file mode 100644 index 0000000..ffbcbd6 --- /dev/null +++ b/src/set.h @@ -0,0 +1,19 @@ +#include + +namespace erebos { + +struct SetItem +{ + static SetItem load(const Ref &); + Ref store(const Storage & st) const; + + const vector> prev; + const vector item; +}; + +struct SetBase::Priv +{ + vector> items; +}; + +} diff --git a/test/storage.test b/test/storage.test index 10f5d2c..12e267d 100644 --- a/test/storage.test +++ b/test/storage.test @@ -1,6 +1,9 @@ test: spawn on node1 as p1 + # Root finding + ############### + # Diamond history send to p1: "store rec" @@ -91,3 +94,59 @@ test: send to p1 "stored-roots $r2_2" expect from p1 /stored-roots $r2_2 $r2_1/ + + + # Set + ##### + + send to p1 "stored-set-add $r1" + expect from p1 /stored-set-add (blake2#[0-9a-f]*)/ capture s1 + send to p1 "stored-set-add $r2 $s1" + expect from p1 /stored-set-add (blake2#[0-9a-f]*)/ capture s2 + send to p1 "stored-set-add $r3 $s2" + expect from p1 /stored-set-add (blake2#[0-9a-f]*)/ capture s3 + send to p1 "stored-set-add $r4 $s3" + expect from p1 /stored-set-add (blake2#[0-9a-f]*)/ capture s4 + + send to p1 "stored-set-list $s1" + expect from p1: + /stored-set-item $r1/ + /stored-set-(.*)/ capture done1 + guard done1 == "done" + + send to p1 "stored-set-list $s2" + expect from p1: + /stored-set-item $r2/ + /stored-set-(.*)/ capture done2 + guard done2 == "done" + + send to p1 "stored-set-list $s3" + expect from p1: + /stored-set-item $r2 $r3/ + /stored-set-(.*)/ capture done3 + guard done3 == "done" + + send to p1 "stored-set-list $s4" + expect from p1: + /stored-set-item $r4/ + /stored-set-(.*)/ capture done4 + guard done4 == "done" + + + send to p1 "stored-set-add $r2_2 $s4" + expect from p1 /stored-set-add (blake2#[0-9a-f]*)/ capture s5 + send to p1 "stored-set-add $r2_3 $s5" + expect from p1 /stored-set-add (blake2#[0-9a-f]*)/ capture s6 + + send to p1 "stored-set-list $s5" + expect from p1: + /stored-set-item $r4/ + /stored-set-item $r2_2/ + /stored-set-(.*)/ capture done5 + guard done5 == "done" + + send to p1 "stored-set-list $s6" + expect from p1: + /stored-set-item $r2_3/ + /stored-set-(.*)/ capture done6 + guard done6 == "done" -- cgit v1.2.3