1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
|
#include "set.h"
#include <unordered_map>
#include <unordered_set>
#include <utility>
namespace erebos {
using std::pair;
using std::unordered_map;
using std::unordered_set;
using std::move;
SetBase::SetBase():
p(make_shared<Priv>())
{
}
SetBase::SetBase(const vector<Ref> & refs)
{
vector<Stored<SetItem>> items;
for (const auto & r : refs)
items.push_back(Stored<SetItem>::load(r));
p = shared_ptr<Priv>(new Priv {
.items = move(items),
});
}
SetBase::SetBase(shared_ptr<const Priv> p_):
p(move(p_))
{
}
shared_ptr<const SetBase::Priv> SetBase::add(const Storage & st, const vector<Ref> & refs) const
{
auto item = st.store(SetItem {
.prev = p->items,
.item = refs,
});
return shared_ptr<const Priv>(new Priv {
.items = { move(item) },
});
}
static void gatherSetItems(unordered_set<Digest> & seenSet, unordered_set<Digest> & seenElem,
vector<Ref> & res, const Stored<SetItem> & 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<vector<Ref>> 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<Ref> items;
{
unordered_set<Digest> seenSet, seenElem;
for (const auto & i : p->items)
gatherSetItems(seenSet, seenElem, items, i);
}
unordered_map<Digest, unsigned> partMap; // maps item ref to partition number
vector<unsigned> 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<vector<Ref>> 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<Ref>()), res.end());
return res;
}
bool SetBase::operator==(const SetBase & other) const
{
return p->items == other.p->items;
}
bool SetBase::operator!=(const SetBase & other) const
{
return !(*this == other);
}
vector<Digest> SetBase::digests() const
{
vector<Digest> res;
res.reserve(p->items.size());
for (const auto & i : p->items)
res.push_back(i.ref().digest());
return res;
}
vector<Ref> SetBase::store() const
{
vector<Ref> res;
res.reserve(p->items.size());
for (const auto & i : p->items)
res.push_back(i.ref());
return res;
}
SetItem SetItem::load(const Ref & ref)
{
if (auto rec = ref->asRecord()) {
return SetItem {
.prev = rec->items("PREV").as<SetItem>(),
.item = rec->items("item").asRef(),
};
}
return SetItem {
.prev = {},
.item = {},
};
}
Ref SetItem::store(const Storage & st) const
{
vector<Record::Item> 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)));
}
}
|