1 // Copyright 2018 The Dawn Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #ifndef COMMON_SERIALSTORAGE_H_
16 #define COMMON_SERIALSTORAGE_H_
17
18 #include "common/Assert.h"
19
20 #include <cstdint>
21 #include <utility>
22
23 template <typename T>
24 struct SerialStorageTraits {};
25
26 template <typename Derived>
27 class SerialStorage {
28 protected:
29 using Serial = typename SerialStorageTraits<Derived>::Serial;
30 using Value = typename SerialStorageTraits<Derived>::Value;
31 using Storage = typename SerialStorageTraits<Derived>::Storage;
32 using StorageIterator = typename SerialStorageTraits<Derived>::StorageIterator;
33 using ConstStorageIterator = typename SerialStorageTraits<Derived>::ConstStorageIterator;
34
35 public:
36 class Iterator {
37 public:
38 Iterator(StorageIterator start);
39 Iterator& operator++();
40
41 bool operator==(const Iterator& other) const;
42 bool operator!=(const Iterator& other) const;
43 Value& operator*() const;
44
45 private:
46 StorageIterator mStorageIterator;
47 // Special case the mSerialIterator when it should be equal to mStorageIterator.begin()
48 // otherwise we could ask mStorageIterator.begin() when mStorageIterator is mStorage.end()
49 // which is invalid. mStorageIterator.begin() is tagged with a nullptr.
50 Value* mSerialIterator;
51 };
52
53 class ConstIterator {
54 public:
55 ConstIterator(ConstStorageIterator start);
56 ConstIterator& operator++();
57
58 bool operator==(const ConstIterator& other) const;
59 bool operator!=(const ConstIterator& other) const;
60 const Value& operator*() const;
61
62 private:
63 ConstStorageIterator mStorageIterator;
64 const Value* mSerialIterator;
65 };
66
67 class BeginEnd {
68 public:
69 BeginEnd(StorageIterator start, StorageIterator end);
70
71 Iterator begin() const;
72 Iterator end() const;
73
74 private:
75 StorageIterator mStartIt;
76 StorageIterator mEndIt;
77 };
78
79 class ConstBeginEnd {
80 public:
81 ConstBeginEnd(ConstStorageIterator start, ConstStorageIterator end);
82
83 ConstIterator begin() const;
84 ConstIterator end() const;
85
86 private:
87 ConstStorageIterator mStartIt;
88 ConstStorageIterator mEndIt;
89 };
90
91 // Derived classes may specialize constraits for elements stored
92 // Ex.) SerialQueue enforces that the serial must be given in (not strictly)
93 // increasing order
94 template <typename... Params>
Enqueue(Params &&...args,Serial serial)95 void Enqueue(Params&&... args, Serial serial) {
96 Derived::Enqueue(std::forward<Params>(args)..., serial);
97 }
98
99 bool Empty() const;
100
101 // The UpTo variants of Iterate and Clear affect all values associated to a serial
102 // that is smaller OR EQUAL to the given serial. Iterating is done like so:
103 // for (const T& value : queue.IterateAll()) { stuff(T); }
104 ConstBeginEnd IterateAll() const;
105 ConstBeginEnd IterateUpTo(Serial serial) const;
106 BeginEnd IterateAll();
107 BeginEnd IterateUpTo(Serial serial);
108
109 void Clear();
110 void ClearUpTo(Serial serial);
111
112 Serial FirstSerial() const;
113 Serial LastSerial() const;
114
115 protected:
116 // Returns the first StorageIterator that a serial bigger than serial.
117 ConstStorageIterator FindUpTo(Serial serial) const;
118 StorageIterator FindUpTo(Serial serial);
119 Storage mStorage;
120 };
121
122 // SerialStorage
123
124 template <typename Derived>
Empty()125 bool SerialStorage<Derived>::Empty() const {
126 return mStorage.empty();
127 }
128
129 template <typename Derived>
IterateAll()130 typename SerialStorage<Derived>::ConstBeginEnd SerialStorage<Derived>::IterateAll() const {
131 return {mStorage.begin(), mStorage.end()};
132 }
133
134 template <typename Derived>
IterateUpTo(Serial serial)135 typename SerialStorage<Derived>::ConstBeginEnd SerialStorage<Derived>::IterateUpTo(
136 Serial serial) const {
137 return {mStorage.begin(), FindUpTo(serial)};
138 }
139
140 template <typename Derived>
IterateAll()141 typename SerialStorage<Derived>::BeginEnd SerialStorage<Derived>::IterateAll() {
142 return {mStorage.begin(), mStorage.end()};
143 }
144
145 template <typename Derived>
IterateUpTo(Serial serial)146 typename SerialStorage<Derived>::BeginEnd SerialStorage<Derived>::IterateUpTo(Serial serial) {
147 return {mStorage.begin(), FindUpTo(serial)};
148 }
149
150 template <typename Derived>
Clear()151 void SerialStorage<Derived>::Clear() {
152 mStorage.clear();
153 }
154
155 template <typename Derived>
ClearUpTo(Serial serial)156 void SerialStorage<Derived>::ClearUpTo(Serial serial) {
157 mStorage.erase(mStorage.begin(), FindUpTo(serial));
158 }
159
160 template <typename Derived>
FirstSerial()161 typename SerialStorage<Derived>::Serial SerialStorage<Derived>::FirstSerial() const {
162 DAWN_ASSERT(!Empty());
163 return mStorage.begin()->first;
164 }
165
166 template <typename Derived>
LastSerial()167 typename SerialStorage<Derived>::Serial SerialStorage<Derived>::LastSerial() const {
168 DAWN_ASSERT(!Empty());
169 return mStorage.back().first;
170 }
171
172 template <typename Derived>
FindUpTo(Serial serial)173 typename SerialStorage<Derived>::ConstStorageIterator SerialStorage<Derived>::FindUpTo(
174 Serial serial) const {
175 auto it = mStorage.begin();
176 while (it != mStorage.end() && it->first <= serial) {
177 it++;
178 }
179 return it;
180 }
181
182 template <typename Derived>
FindUpTo(Serial serial)183 typename SerialStorage<Derived>::StorageIterator SerialStorage<Derived>::FindUpTo(Serial serial) {
184 auto it = mStorage.begin();
185 while (it != mStorage.end() && it->first <= serial) {
186 it++;
187 }
188 return it;
189 }
190
191 // SerialStorage::BeginEnd
192
193 template <typename Derived>
BeginEnd(typename SerialStorage<Derived>::StorageIterator start,typename SerialStorage<Derived>::StorageIterator end)194 SerialStorage<Derived>::BeginEnd::BeginEnd(typename SerialStorage<Derived>::StorageIterator start,
195 typename SerialStorage<Derived>::StorageIterator end)
196 : mStartIt(start), mEndIt(end) {
197 }
198
199 template <typename Derived>
begin()200 typename SerialStorage<Derived>::Iterator SerialStorage<Derived>::BeginEnd::begin() const {
201 return {mStartIt};
202 }
203
204 template <typename Derived>
end()205 typename SerialStorage<Derived>::Iterator SerialStorage<Derived>::BeginEnd::end() const {
206 return {mEndIt};
207 }
208
209 // SerialStorage::Iterator
210
211 template <typename Derived>
Iterator(typename SerialStorage<Derived>::StorageIterator start)212 SerialStorage<Derived>::Iterator::Iterator(typename SerialStorage<Derived>::StorageIterator start)
213 : mStorageIterator(start), mSerialIterator(nullptr) {
214 }
215
216 template <typename Derived>
217 typename SerialStorage<Derived>::Iterator& SerialStorage<Derived>::Iterator::operator++() {
218 Value* vectorData = mStorageIterator->second.data();
219
220 if (mSerialIterator == nullptr) {
221 mSerialIterator = vectorData + 1;
222 } else {
223 mSerialIterator++;
224 }
225
226 if (mSerialIterator >= vectorData + mStorageIterator->second.size()) {
227 mSerialIterator = nullptr;
228 mStorageIterator++;
229 }
230
231 return *this;
232 }
233
234 template <typename Derived>
235 bool SerialStorage<Derived>::Iterator::operator==(
236 const typename SerialStorage<Derived>::Iterator& other) const {
237 return other.mStorageIterator == mStorageIterator && other.mSerialIterator == mSerialIterator;
238 }
239
240 template <typename Derived>
241 bool SerialStorage<Derived>::Iterator::operator!=(
242 const typename SerialStorage<Derived>::Iterator& other) const {
243 return !(*this == other);
244 }
245
246 template <typename Derived>
247 typename SerialStorage<Derived>::Value& SerialStorage<Derived>::Iterator::operator*() const {
248 if (mSerialIterator == nullptr) {
249 return *mStorageIterator->second.begin();
250 }
251 return *mSerialIterator;
252 }
253
254 // SerialStorage::ConstBeginEnd
255
256 template <typename Derived>
ConstBeginEnd(typename SerialStorage<Derived>::ConstStorageIterator start,typename SerialStorage<Derived>::ConstStorageIterator end)257 SerialStorage<Derived>::ConstBeginEnd::ConstBeginEnd(
258 typename SerialStorage<Derived>::ConstStorageIterator start,
259 typename SerialStorage<Derived>::ConstStorageIterator end)
260 : mStartIt(start), mEndIt(end) {
261 }
262
263 template <typename Derived>
begin()264 typename SerialStorage<Derived>::ConstIterator SerialStorage<Derived>::ConstBeginEnd::begin()
265 const {
266 return {mStartIt};
267 }
268
269 template <typename Derived>
end()270 typename SerialStorage<Derived>::ConstIterator SerialStorage<Derived>::ConstBeginEnd::end() const {
271 return {mEndIt};
272 }
273
274 // SerialStorage::ConstIterator
275
276 template <typename Derived>
ConstIterator(typename SerialStorage<Derived>::ConstStorageIterator start)277 SerialStorage<Derived>::ConstIterator::ConstIterator(
278 typename SerialStorage<Derived>::ConstStorageIterator start)
279 : mStorageIterator(start), mSerialIterator(nullptr) {
280 }
281
282 template <typename Derived>
283 typename SerialStorage<Derived>::ConstIterator&
284 SerialStorage<Derived>::ConstIterator::operator++() {
285 const Value* vectorData = mStorageIterator->second.data();
286
287 if (mSerialIterator == nullptr) {
288 mSerialIterator = vectorData + 1;
289 } else {
290 mSerialIterator++;
291 }
292
293 if (mSerialIterator >= vectorData + mStorageIterator->second.size()) {
294 mSerialIterator = nullptr;
295 mStorageIterator++;
296 }
297
298 return *this;
299 }
300
301 template <typename Derived>
302 bool SerialStorage<Derived>::ConstIterator::operator==(
303 const typename SerialStorage<Derived>::ConstIterator& other) const {
304 return other.mStorageIterator == mStorageIterator && other.mSerialIterator == mSerialIterator;
305 }
306
307 template <typename Derived>
308 bool SerialStorage<Derived>::ConstIterator::operator!=(
309 const typename SerialStorage<Derived>::ConstIterator& other) const {
310 return !(*this == other);
311 }
312
313 template <typename Derived>
314 const typename SerialStorage<Derived>::Value& SerialStorage<Derived>::ConstIterator::operator*()
315 const {
316 if (mSerialIterator == nullptr) {
317 return *mStorageIterator->second.begin();
318 }
319 return *mSerialIterator;
320 }
321
322 #endif // COMMON_SERIALSTORAGE_H_
323