GCC Code Coverage Report

ernie/
Coverage:
low: ≥ 0%
medium: ≥ 75.0%
high: ≥ 90.0%
Lines:
193 / 196
98.5%
Branches:
109 / 146
74.7%
Functions:
20 / 20
100.0%
scene/storage.cpp
Line Branch Exec Source
1 // SPDX-License-Identifier: BSD-3-Clause
2 /// @file storage.cpp
3 /// @brief Buckets, rows, versions and change sets of the columnar prim store.
4 #include "ernie/scene/storage.h"
5
6 #include "ernie/util/random.h"
7
8 #include <algorithm>
9
10 namespace ernie {
11
12 namespace {
13
14 constexpr std::uint32_t kNoSlot = std::numeric_limits<std::uint32_t>::max();
15 /// Row changes kept per bucket; a reader further behind resyncs the bucket.
16 constexpr std::size_t kLogLimit = std::size_t{1} << 16;
17
18 } // namespace
19
20 4018 std::size_t PrimStore::KeyHash::operator()(const BucketKey& key) const {
21 4018 std::uint64_t hash = Mix64(key.type);
22
2/2
✓ Branch 0 taken 252 times.
✓ Branch 1 taken 4018 times.
 4270 for (const Token schema : key.apiSchemas) {
23 252 hash = HashCombine(hash, schema);
24 }
25 4018 return static_cast<std::size_t>(hash);
26 }
27
28 3767 BucketKey BucketKey::Normalized() const {
29 3767 BucketKey sorted = *this;
30 3767 std::ranges::sort(sorted.apiSchemas);
31 3767 const auto [last, end] = std::ranges::unique(sorted.apiSchemas);
32 3767 sorted.apiSchemas.erase(last, end);
33 3767 return sorted;
34 }
35
36 3039 std::optional<BucketId> PrimStore::FindBucket(const BucketKey& key) const {
37 6078 const auto found = bucketIndex_.find(key.Normalized());
38
2/2
✓ Branch 0 taken 2324 times.
✓ Branch 1 taken 715 times.
 5363 return found != bucketIndex_.end() ? std::optional(found->second) : std::nullopt;
39 }
40
41 728 BucketId PrimStore::AddBucket(const BucketKey& key, std::span<const ColumnLayout> layout) {
42 728 BucketKey sorted = key.Normalized();
43
2/2
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 726 times.
 728 if (const auto found = bucketIndex_.find(sorted); found != bucketIndex_.end()) {
44 2 return found->second;
45 }
46
1/2
✓ Branch 1 taken 726 times.
✗ Branch 2 not taken.
 726 auto bucket = std::make_unique<Bucket>();
47
1/2
✓ Branch 1 taken 726 times.
✗ Branch 2 not taken.
 726 bucket->key = sorted;
48
2/2
✓ Branch 0 taken 8450 times.
✓ Branch 1 taken 726 times.
 9176 for (const ColumnLayout& column : layout) {
49
2/4
✓ Branch 1 taken 8450 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 8450 times.
✗ Branch 5 not taken.
 8450 AddColumn(*bucket, column.attribute, column.prototype->Clone());
50 }
51
1/2
✓ Branch 1 taken 726 times.
✗ Branch 2 not taken.
 726 const auto id = static_cast<BucketId>(buckets_.size());
52
1/2
✓ Branch 1 taken 726 times.
✗ Branch 2 not taken.
 726 buckets_.push_back(std::move(bucket));
53
1/2
✓ Branch 1 taken 726 times.
✗ Branch 2 not taken.
 726 bucketIndex_.emplace(std::move(sorted), id);
54 726 return id;
55 1454 }
56
57 8642 Column& PrimStore::AddColumn(Bucket& bucket, AttributeId attribute,
58 std::unique_ptr<ColumnValues> values) {
59 8642 values->Grow(bucket.Rows());
60 8642 Column column;
61 8642 column.attribute = attribute;
62 8642 column.values = std::move(values);
63
1/2
✓ Branch 1 taken 8642 times.
✗ Branch 2 not taken.
 8642 column.Resize(bucket.Rows());
64
1/2
✓ Branch 1 taken 8642 times.
✗ Branch 2 not taken.
 8642 bucket.columnIndex.emplace(attribute, static_cast<std::uint32_t>(bucket.columns.size()));
65
1/2
✓ Branch 1 taken 8642 times.
✗ Branch 2 not taken.
 17284 return bucket.columns.emplace_back(std::move(column));
66 8642 }
67
68 352602 const PrimStore::SlotData& PrimStore::Slot(PrimId prim) const {
69
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 352601 times.
 352602 if (!Alive(prim)) {
70
1/2
✓ Branch 2 taken 1 time.
✗ Branch 3 not taken.
 1 throw std::invalid_argument("The prim has been removed");
71 }
72 352601 return slots_[prim.slot];
73 }
74
75 352657 bool PrimStore::Alive(PrimId prim) const {
76
3/4
✓ Branch 0 taken 352657 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 352653 times.
✓ Branch 3 taken 4 times.
 352657 return prim.slot < slots_.size() && slots_[prim.slot].alive &&
77
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 352652 times.
 352653 slots_[prim.slot].generation == prim.generation;
78 }
79
80 186335 std::optional<PrimId> PrimStore::Find(PathId path) const {
81
4/4
✓ Branch 0 taken 177779 times.
✓ Branch 1 taken 8556 times.
✓ Branch 2 taken 142998 times.
✓ Branch 3 taken 34781 times.
 186335 if (path >= pathSlots_.size() || pathSlots_[path] == kNoSlot) {
82 151554 return std::nullopt;
83 }
84 34781 const std::uint32_t slot = pathSlots_[path];
85 34781 return PrimId{slot, slots_[slot].generation};
86 }
87
88 73191 PrimId PrimStore::AddSlot(PathId path, BucketId bucket, std::uint32_t row) {
89 73191 std::uint32_t slot;
90
2/2
✓ Branch 0 taken 2951 times.
✓ Branch 1 taken 70240 times.
 73191 if (free_.empty()) {
91 2951 slot = static_cast<std::uint32_t>(slots_.size());
92 2951 slots_.emplace_back();
93 } else {
94 70240 slot = free_.back();
95 70240 free_.pop_back();
96 }
97
2/2
✓ Branch 0 taken 2823 times.
✓ Branch 1 taken 70368 times.
 73191 SlotData& data = slots_[slot];
98 73191 data.bucket = bucket;
99 73191 data.row = row;
100 73191 data.path = path;
101 73191 data.alive = true;
102
2/2
✓ Branch 0 taken 2823 times.
✓ Branch 1 taken 70368 times.
 73191 if (pathSlots_.size() <= path) {
103
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2823 times.
 2823 pathSlots_.resize(std::max<std::size_t>(paths_.Size(), path + 1), kNoSlot);
104 }
105 73191 pathSlots_[path] = slot;
106 73191 return {slot, data.generation};
107 }
108
109 72993 PrimId PrimStore::Define(PathId path, BucketId bucket) {
110
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 72991 times.
 72993 if (const std::optional<PrimId> existing = Find(path)) {
111
2/2
✓ Branch 1 taken 1 time.
✓ Branch 2 taken 1 time.
 2 if (PrimBucket(*existing) != bucket) {
112
2/4
✓ Branch 1 taken 1 time.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 time.
✗ Branch 5 not taken.
 2 throw std::invalid_argument("Prim " + paths_.ToPath(path).String() +
113
1/2
✓ Branch 2 taken 1 time.
✗ Branch 3 not taken.
 3 " already exists with another type");
114 }
115 1 return *existing;
116 }
117 72991 return DefineMany(std::span(&path, 1), bucket).front();
118 }
119
120 72992 std::vector<PrimId> PrimStore::DefineMany(std::span<const PathId> paths, BucketId bucket) {
121
2/2
✓ Branch 0 taken 73191 times.
✓ Branch 1 taken 72992 times.
 146183 for (const PathId path : paths) {
122
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 73191 times.
 73191 if (Find(path)) {
123
0/6
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
 ✗ throw std::invalid_argument("Prim " + paths_.ToPath(path).String() + " already exists");
124 }
125 }
126 72992 const auto count = static_cast<std::uint32_t>(paths.size());
127 72992 const std::uint32_t first = AddRows(bucket, count);
128
1/2
✓ Branch 1 taken 72992 times.
✗ Branch 2 not taken.
 72992 Bucket& b = *buckets_[bucket];
129 72992 std::vector<PrimId> prims;
130
1/2
✓ Branch 1 taken 72992 times.
✗ Branch 2 not taken.
 72992 prims.reserve(count);
131
2/2
✓ Branch 0 taken 73191 times.
✓ Branch 1 taken 72992 times.
 146183 for (std::uint32_t i = 0; i < count; ++i) {
132
1/2
✓ Branch 1 taken 73191 times.
✗ Branch 2 not taken.
 73191 prims.push_back(AddSlot(paths[i], bucket, first + i));
133 73191 b.prims[first + i] = prims.back();
134 }
135 72992 return prims;
136 ✗ }
137
138 73070 std::uint32_t PrimStore::AddRows(BucketId bucket, std::uint32_t count) {
139 73070 Bucket& b = *buckets_[bucket];
140 73070 const std::uint32_t first = b.Rows();
141
2/2
✓ Branch 0 taken 180411 times.
✓ Branch 1 taken 73070 times.
 253481 for (Column& column : b.columns) {
142 180411 column.values->Grow(count);
143 180411 column.Resize(first + count);
144 }
145 73070 b.prims.resize(first + count);
146 73070 Log(b, {Next(), StructuralChange::Kind::Added, first, count, 0});
147 73070 return first;
148 }
149
150 70265 void PrimStore::Remove(PrimId prim) {
151 70265 SlotData& slot = Slot(prim);
152 70265 DropRow(slot);
153 70265 pathSlots_[slot.path] = kNoSlot;
154 70265 slot.alive = false;
155 70265 ++slot.generation;
156 70265 free_.push_back(prim.slot);
157 70265 }
158
159 78 void PrimStore::Move(PrimId prim, BucketId bucket) {
160 78 SlotData& slot = Slot(prim);
161
1/2
✓ Branch 0 taken 78 times.
✗ Branch 1 not taken.
 78 if (slot.bucket == bucket) {
162 return;
163 }
164 78 const std::uint32_t row = AddRows(bucket, 1);
165 78 Bucket& to = *buckets_[bucket];
166 78 const Bucket& from = *buckets_[slot.bucket];
167 78 to.prims[row] = prim;
168 78 const std::uint64_t version = Next();
169
2/2
✓ Branch 0 taken 1228 times.
✓ Branch 1 taken 78 times.
 1306 for (const Column& source : from.columns) {
170 1228 Column* column = to.Find(source.attribute);
171
5/6
✓ Branch 0 taken 1222 times.
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 11 times.
✓ Branch 3 taken 1211 times.
✓ Branch 4 taken 11 times.
✗ Branch 5 not taken.
 1239 if (column != nullptr && source.authored.Test(slot.row) &&
172 11 column->values->Type() == source.values->Type()) {
173 11 column->values->CopyRow(row, *source.values, slot.row);
174 11 Stamp(bucket, *column, row, row + 1, version);
175 }
176 }
177 78 DropRow(slot);
178 78 slot.bucket = bucket;
179 78 slot.row = row;
180 }
181
182 70343 void PrimStore::DropRow(const SlotData& slot) {
183 70343 Bucket& b = *buckets_[slot.bucket];
184 70343 const std::uint32_t row = slot.row;
185 70343 const std::uint32_t last = b.Rows() - 1;
186 70343 const std::uint64_t version = Next();
187 70343 Log(b, {version, StructuralChange::Kind::Removed, row, 1, 0});
188
2/2
✓ Branch 0 taken 252 times.
✓ Branch 1 taken 70091 times.
 70343 if (row != last) {
189 252 b.prims[row] = b.prims[last];
190 252 slots_[b.prims[row].slot].row = row;
191 252 Log(b, {version, StructuralChange::Kind::Moved, row, 1, last});
192 }
193 70343 b.prims.pop_back();
194
2/2
✓ Branch 0 taken 144854 times.
✓ Branch 1 taken 70343 times.
 215197 for (Column& column : b.columns) {
195 144854 column.values->SwapRemove(row);
196 144854 column.authored.Set(row, column.authored.Test(last));
197 144854 column.Resize(last);
198
2/2
✓ Branch 0 taken 3431 times.
✓ Branch 1 taken 141423 times.
 144854 if (row != last) {
199 // The moved row's values change at its new place, where readers look.
200 3431 Touch(slot.bucket, column, row, row + 1, version);
201 }
202 }
203 70343 }
204
205 10 void PrimStore::Clear(PrimId prim, AttributeId attribute) {
206 10 const SlotData& slot = Slot(prim);
207 10 Column* column = buckets_[slot.bucket]->Find(attribute);
208
2/4
✓ Branch 0 taken 10 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 10 times.
✗ Branch 3 not taken.
 10 if (column == nullptr || !column->authored.Test(slot.row)) {
209 return;
210 }
211 10 column->values->Reset(slot.row);
212 10 column->authored.Set(slot.row, false);
213 10 Touch(slot.bucket, *column, slot.row, slot.row + 1, Next());
214 }
215
216 143665 void PrimStore::Log(Bucket& bucket, StructuralChange change) {
217 143665 bucket.version = change.version;
218 143665 bucket.log.push_back(change);
219
2/2
✓ Branch 0 taken 74465 times.
✓ Branch 1 taken 69200 times.
 143665 if (bucket.log.size() > kLogLimit) {
220 74465 bucket.logStart = bucket.log.front().version;
221 74465 bucket.log.pop_front();
222 }
223 143665 }
224
225 4994 void PrimStore::Stamp(BucketId bucket, Column& column, std::uint32_t begin, std::uint32_t end,
226 std::uint64_t version) {
227 4994 column.authored.SetRange(begin, end);
228 4994 Touch(bucket, column, begin, end, version);
229 4994 }
230
231 8562 void PrimStore::Touch(BucketId bucket, Column& column, std::uint32_t begin, std::uint32_t end,
232 std::uint64_t version) {
233
1/2
✓ Branch 0 taken 8562 times.
✗ Branch 1 not taken.
 8562 if (begin == end) {
234 return;
235 }
236 17124 std::fill(column.chunkVersions.begin() + begin / kChunkRows,
237 8562 column.chunkVersions.begin() + (end - 1) / kChunkRows + 1, version);
238 8562 column.version = version;
239 8562 buckets_[bucket]->version = version;
240 }
241
242 291 ChangeSet PrimStore::ChangesSince(std::uint64_t cursor) const {
243 291 ChangeSet changes;
244 291 changes.version = version_;
245
2/2
✓ Branch 0 taken 748 times.
✓ Branch 1 taken 291 times.
 1039 for (BucketId id = 0; id < buckets_.size(); ++id) {
246
2/2
✓ Branch 0 taken 317 times.
✓ Branch 1 taken 431 times.
 748 const Bucket& bucket = *buckets_[id];
247
2/2
✓ Branch 0 taken 317 times.
✓ Branch 1 taken 431 times.
 748 if (bucket.version <= cursor) {
248 317 continue;
249 }
250 // A reader too far behind to replay the log gets the bucket afresh: every row new and
251 // every value changed.
252 431 const bool reset = cursor < bucket.logStart;
253
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 430 times.
 431 if (reset) {
254
1/2
✓ Branch 1 taken 1 time.
✗ Branch 2 not taken.
 1 changes.rows.push_back(
255
1/2
✓ Branch 1 taken 1 time.
✗ Branch 2 not taken.
 1 {id, {bucket.version, StructuralChange::Kind::Reset, 0, bucket.Rows(), 0}});
256 } else {
257 430 const auto newer =
258 430 std::upper_bound(bucket.log.begin(), bucket.log.end(), cursor,
259 1713 [](std::uint64_t at, const StructuralChange& change) {
260
2/2
✓ Branch 0 taken 909 times.
✓ Branch 1 taken 804 times.
 1713 return at < change.version;
261 430 });
262
2/2
✓ Branch 0 taken 5695 times.
✓ Branch 1 taken 430 times.
 6125 for (auto change = newer; change != bucket.log.end(); ++change) {
263
1/2
✓ Branch 1 taken 5695 times.
✗ Branch 2 not taken.
 5695 changes.rows.push_back({id, *change});
264 }
265 }
266
2/2
✓ Branch 0 taken 5462 times.
✓ Branch 1 taken 431 times.
 5893 for (const Column& column : bucket.columns) {
267
4/4
✓ Branch 0 taken 3263 times.
✓ Branch 1 taken 2199 times.
✓ Branch 2 taken 3261 times.
✓ Branch 3 taken 2 times.
 5462 if (column.version <= cursor && !reset) {
268 3261 continue;
269 }
270 2201 ChangeSet::Values values{id, column.attribute, {}};
271
2/2
✓ Branch 0 taken 10406 times.
✓ Branch 1 taken 2201 times.
 12607 for (std::uint32_t chunk = 0; chunk < column.chunkVersions.size(); ++chunk) {
272
4/4
✓ Branch 0 taken 3740 times.
✓ Branch 1 taken 6666 times.
✓ Branch 2 taken 3738 times.
✓ Branch 3 taken 2 times.
 10406 if (column.chunkVersions[chunk] <= cursor && !reset) {
273 3738 continue;
274 }
275 6668 const std::uint32_t begin = chunk * kChunkRows;
276
2/2
✓ Branch 0 taken 1012 times.
✓ Branch 1 taken 5656 times.
 6668 const std::uint32_t end = std::min(begin + kChunkRows, bucket.Rows());
277
4/4
✓ Branch 0 taken 4467 times.
✓ Branch 1 taken 2201 times.
✓ Branch 2 taken 809 times.
✓ Branch 3 taken 3658 times.
 6668 if (!values.rows.empty() && values.rows.back().end == begin) {
278 3658 values.rows.back().end = end;
279 } else {
280
1/2
✓ Branch 1 taken 3010 times.
✗ Branch 2 not taken.
 3010 values.rows.push_back({begin, end});
281 }
282 }
283
1/2
✓ Branch 0 taken 2201 times.
✗ Branch 1 not taken.
 2201 if (!values.rows.empty()) {
284
1/2
✓ Branch 1 taken 2201 times.
✗ Branch 2 not taken.
 2201 changes.values.push_back(std::move(values));
285 }
286 2201 }
287 }
288 291 return changes;
289 ✗ }
290
291 } // namespace ernie
292