Factor SerialQueue into SerialQueue and SerialMap
This change moves most of SerialQueue into SerialStorage
and factors it to make SerialMap and SerialQueue. SerialMap
does not enforce that items are Enqueue'd in monotonically
increasing order. This is useful for implement timeline fences
because OnCompletion callbacks may be added in an arbitrary order.
Bug: dawn:26
Change-Id: I03376117311112b0b94ed887a31974f36c4a5464
Reviewed-on: https://dawn-review.googlesource.com/c/2720
Reviewed-by: Corentin Wallez <cwallez@chromium.org>
Commit-Queue: Corentin Wallez <cwallez@chromium.org>
diff --git a/BUILD.gn b/BUILD.gn
index 258485f..2408412 100644
--- a/BUILD.gn
+++ b/BUILD.gn
@@ -197,7 +197,9 @@
"src/common/Platform.h",
"src/common/Result.h",
"src/common/Serial.h",
+ "src/common/SerialMap.h",
"src/common/SerialQueue.h",
+ "src/common/SerialStorage.h",
"src/common/SwapChainUtils.h",
"src/common/vulkan_platform.h",
"src/common/windows_with_undefs.h",
@@ -805,6 +807,7 @@
"src/tests/unittests/PerStageTests.cpp",
"src/tests/unittests/RefCountedTests.cpp",
"src/tests/unittests/ResultTests.cpp",
+ "src/tests/unittests/SerialMapTests.cpp",
"src/tests/unittests/SerialQueueTests.cpp",
"src/tests/unittests/ToBackendTests.cpp",
"src/tests/unittests/WireTests.cpp",
diff --git a/src/common/SerialMap.h b/src/common/SerialMap.h
new file mode 100644
index 0000000..93b0019
--- /dev/null
+++ b/src/common/SerialMap.h
@@ -0,0 +1,75 @@
+// Copyright 2018 The Dawn Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef COMMON_SERIALMAP_H_
+#define COMMON_SERIALMAP_H_
+
+#include "common/SerialStorage.h"
+
+#include <map>
+#include <vector>
+
+template <typename T>
+class SerialMap;
+
+template <typename T>
+struct SerialStorageTraits<SerialMap<T>> {
+ using Value = T;
+ using Storage = std::map<Serial, std::vector<T>>;
+ using StorageIterator = typename Storage::iterator;
+ using ConstStorageIterator = typename Storage::const_iterator;
+};
+
+// SerialMap stores a map from Serial to T.
+// Unlike SerialQueue, items may be enqueued with Serials in any
+// arbitrary order. SerialMap provides useful iterators for iterating
+// through T items in order of increasing Serial.
+template <typename T>
+class SerialMap : public SerialStorage<SerialMap<T>> {
+ public:
+ void Enqueue(const T& value, Serial serial);
+ void Enqueue(T&& value, Serial serial);
+ void Enqueue(const std::vector<T>& values, Serial serial);
+ void Enqueue(std::vector<T>&& values, Serial serial);
+};
+
+// SerialMap
+
+template <typename T>
+void SerialMap<T>::Enqueue(const T& value, Serial serial) {
+ this->mStorage[serial].emplace_back(value);
+}
+
+template <typename T>
+void SerialMap<T>::Enqueue(T&& value, Serial serial) {
+ this->mStorage[serial].emplace_back(value);
+}
+
+template <typename T>
+void SerialMap<T>::Enqueue(const std::vector<T>& values, Serial serial) {
+ DAWN_ASSERT(values.size() > 0);
+ for (const T& value : values) {
+ Enqueue(value, serial);
+ }
+}
+
+template <typename T>
+void SerialMap<T>::Enqueue(std::vector<T>&& values, Serial serial) {
+ DAWN_ASSERT(values.size() > 0);
+ for (const T& value : values) {
+ Enqueue(value, serial);
+ }
+}
+
+#endif // COMMON_SERIALMAP_H_
diff --git a/src/common/SerialQueue.h b/src/common/SerialQueue.h
index 3fcead8..f5654a9 100644
--- a/src/common/SerialQueue.h
+++ b/src/common/SerialQueue.h
@@ -15,321 +15,72 @@
#ifndef COMMON_SERIALQUEUE_H_
#define COMMON_SERIALQUEUE_H_
-#include "common/Assert.h"
-#include "common/Serial.h"
+#include "common/SerialStorage.h"
-#include <cstdint>
#include <vector>
template <typename T>
-class SerialQueue {
- private:
+class SerialQueue;
+
+template <typename T>
+struct SerialStorageTraits<SerialQueue<T>> {
+ using Value = T;
using SerialPair = std::pair<Serial, std::vector<T>>;
using Storage = std::vector<SerialPair>;
using StorageIterator = typename Storage::iterator;
using ConstStorageIterator = typename Storage::const_iterator;
+};
+// SerialQueue stores an associative list mapping a Serial to T.
+// It enforces that the Serials enqueued are strictly non-decreasing.
+// This makes it very efficient iterate or clear all items added up
+// to some Serial value because they are stored contiguously in memory.
+template <typename T>
+class SerialQueue : public SerialStorage<SerialQueue<T>> {
public:
- class Iterator {
- public:
- Iterator(StorageIterator start);
- Iterator& operator++();
-
- bool operator==(const Iterator& other) const;
- bool operator!=(const Iterator& other) const;
- T& operator*() const;
-
- private:
- StorageIterator mStorageIterator;
- // Special case the mSerialIterator when it should be equal to mStorageIterator.begin()
- // otherwise we could ask mStorageIterator.begin() when mStorageIterator is mStorage.end()
- // which is invalid. mStorageIterator.begin() is tagged with a nullptr.
- T* mSerialIterator;
- };
-
- class ConstIterator {
- public:
- ConstIterator(ConstStorageIterator start);
- ConstIterator& operator++();
-
- bool operator==(const ConstIterator& other) const;
- bool operator!=(const ConstIterator& other) const;
- const T& operator*() const;
-
- private:
- ConstStorageIterator mStorageIterator;
- const T* mSerialIterator;
- };
-
- class BeginEnd {
- public:
- BeginEnd(StorageIterator start, StorageIterator end);
-
- Iterator begin() const;
- Iterator end() const;
-
- private:
- StorageIterator mStartIt;
- StorageIterator mEndIt;
- };
-
- class ConstBeginEnd {
- public:
- ConstBeginEnd(ConstStorageIterator start, ConstStorageIterator end);
-
- ConstIterator begin() const;
- ConstIterator end() const;
-
- private:
- ConstStorageIterator mStartIt;
- ConstStorageIterator mEndIt;
- };
+ using SerialPair = typename SerialStorageTraits<SerialQueue<T>>::SerialPair;
// The serial must be given in (not strictly) increasing order.
void Enqueue(const T& value, Serial serial);
void Enqueue(T&& value, Serial serial);
void Enqueue(const std::vector<T>& values, Serial serial);
void Enqueue(std::vector<T>&& values, Serial serial);
-
- bool Empty() const;
-
- // The UpTo variants of Iterate and Clear affect all values associated to a serial
- // that is smaller OR EQUAL to the given serial. Iterating is done like so:
- // for (const T& value : queue.IterateAll()) { stuff(T); }
- ConstBeginEnd IterateAll() const;
- ConstBeginEnd IterateUpTo(Serial serial) const;
- BeginEnd IterateAll();
- BeginEnd IterateUpTo(Serial serial);
-
- void Clear();
- void ClearUpTo(Serial serial);
-
- Serial FirstSerial() const;
-
- private:
- // Returns the first StorageIterator that a serial bigger than serial.
- ConstStorageIterator FindUpTo(Serial serial) const;
- StorageIterator FindUpTo(Serial serial);
- Storage mStorage;
};
// SerialQueue
template <typename T>
void SerialQueue<T>::Enqueue(const T& value, Serial serial) {
- DAWN_ASSERT(Empty() || mStorage.back().first <= serial);
+ DAWN_ASSERT(this->Empty() || this->mStorage.back().first <= serial);
- if (Empty() || mStorage.back().first < serial) {
- mStorage.emplace_back(SerialPair(serial, {}));
+ if (this->Empty() || this->mStorage.back().first < serial) {
+ this->mStorage.emplace_back(SerialPair(serial, {}));
}
- mStorage.back().second.emplace_back(value);
+ this->mStorage.back().second.emplace_back(value);
}
template <typename T>
void SerialQueue<T>::Enqueue(T&& value, Serial serial) {
- DAWN_ASSERT(Empty() || mStorage.back().first <= serial);
+ DAWN_ASSERT(this->Empty() || this->mStorage.back().first <= serial);
- if (Empty() || mStorage.back().first < serial) {
- mStorage.emplace_back(SerialPair(serial, {}));
+ if (this->Empty() || this->mStorage.back().first < serial) {
+ this->mStorage.emplace_back(SerialPair(serial, {}));
}
- mStorage.back().second.emplace_back(value);
+ this->mStorage.back().second.emplace_back(value);
}
template <typename T>
void SerialQueue<T>::Enqueue(const std::vector<T>& values, Serial serial) {
DAWN_ASSERT(values.size() > 0);
- DAWN_ASSERT(Empty() || mStorage.back().first <= serial);
- mStorage.emplace_back(SerialPair(serial, {values}));
+ DAWN_ASSERT(this->Empty() || this->mStorage.back().first <= serial);
+ this->mStorage.emplace_back(SerialPair(serial, {values}));
}
template <typename T>
void SerialQueue<T>::Enqueue(std::vector<T>&& values, Serial serial) {
DAWN_ASSERT(values.size() > 0);
- DAWN_ASSERT(Empty() || mStorage.back().first <= serial);
- mStorage.emplace_back(SerialPair(serial, {values}));
-}
-
-template <typename T>
-bool SerialQueue<T>::Empty() const {
- return mStorage.empty();
-}
-
-template <typename T>
-typename SerialQueue<T>::ConstBeginEnd SerialQueue<T>::IterateAll() const {
- return {mStorage.begin(), mStorage.end()};
-}
-
-template <typename T>
-typename SerialQueue<T>::ConstBeginEnd SerialQueue<T>::IterateUpTo(Serial serial) const {
- return {mStorage.begin(), FindUpTo(serial)};
-}
-
-template <typename T>
-typename SerialQueue<T>::BeginEnd SerialQueue<T>::IterateAll() {
- return {mStorage.begin(), mStorage.end()};
-}
-
-template <typename T>
-typename SerialQueue<T>::BeginEnd SerialQueue<T>::IterateUpTo(Serial serial) {
- return {mStorage.begin(), FindUpTo(serial)};
-}
-
-template <typename T>
-void SerialQueue<T>::Clear() {
- mStorage.clear();
-}
-
-template <typename T>
-void SerialQueue<T>::ClearUpTo(Serial serial) {
- mStorage.erase(mStorage.begin(), FindUpTo(serial));
-}
-
-template <typename T>
-Serial SerialQueue<T>::FirstSerial() const {
- DAWN_ASSERT(!Empty());
- return mStorage.front().first;
-}
-
-template <typename T>
-typename SerialQueue<T>::ConstStorageIterator SerialQueue<T>::FindUpTo(Serial serial) const {
- auto it = mStorage.begin();
- while (it != mStorage.end() && it->first <= serial) {
- it++;
- }
- return it;
-}
-
-template <typename T>
-typename SerialQueue<T>::StorageIterator SerialQueue<T>::FindUpTo(Serial serial) {
- auto it = mStorage.begin();
- while (it != mStorage.end() && it->first <= serial) {
- it++;
- }
- return it;
-}
-
-// SerialQueue::BeginEnd
-
-template <typename T>
-SerialQueue<T>::BeginEnd::BeginEnd(typename SerialQueue<T>::StorageIterator start,
- typename SerialQueue<T>::StorageIterator end)
- : mStartIt(start), mEndIt(end) {
-}
-
-template <typename T>
-typename SerialQueue<T>::Iterator SerialQueue<T>::BeginEnd::begin() const {
- return {mStartIt};
-}
-
-template <typename T>
-typename SerialQueue<T>::Iterator SerialQueue<T>::BeginEnd::end() const {
- return {mEndIt};
-}
-
-// SerialQueue::Iterator
-
-template <typename T>
-SerialQueue<T>::Iterator::Iterator(typename SerialQueue<T>::StorageIterator start)
- : mStorageIterator(start), mSerialIterator(nullptr) {
-}
-
-template <typename T>
-typename SerialQueue<T>::Iterator& SerialQueue<T>::Iterator::operator++() {
- T* vectorData = mStorageIterator->second.data();
-
- if (mSerialIterator == nullptr) {
- mSerialIterator = vectorData + 1;
- } else {
- mSerialIterator++;
- }
-
- if (mSerialIterator >= vectorData + mStorageIterator->second.size()) {
- mSerialIterator = nullptr;
- mStorageIterator++;
- }
-
- return *this;
-}
-
-template <typename T>
-bool SerialQueue<T>::Iterator::operator==(const typename SerialQueue<T>::Iterator& other) const {
- return other.mStorageIterator == mStorageIterator && other.mSerialIterator == mSerialIterator;
-}
-
-template <typename T>
-bool SerialQueue<T>::Iterator::operator!=(const typename SerialQueue<T>::Iterator& other) const {
- return !(*this == other);
-}
-
-template <typename T>
-T& SerialQueue<T>::Iterator::operator*() const {
- if (mSerialIterator == nullptr) {
- return *mStorageIterator->second.begin();
- }
- return *mSerialIterator;
-}
-
-// SerialQueue::ConstBeginEnd
-
-template <typename T>
-SerialQueue<T>::ConstBeginEnd::ConstBeginEnd(typename SerialQueue<T>::ConstStorageIterator start,
- typename SerialQueue<T>::ConstStorageIterator end)
- : mStartIt(start), mEndIt(end) {
-}
-
-template <typename T>
-typename SerialQueue<T>::ConstIterator SerialQueue<T>::ConstBeginEnd::begin() const {
- return {mStartIt};
-}
-
-template <typename T>
-typename SerialQueue<T>::ConstIterator SerialQueue<T>::ConstBeginEnd::end() const {
- return {mEndIt};
-}
-
-// SerialQueue::ConstIterator
-
-template <typename T>
-SerialQueue<T>::ConstIterator::ConstIterator(typename SerialQueue<T>::ConstStorageIterator start)
- : mStorageIterator(start), mSerialIterator(nullptr) {
-}
-
-template <typename T>
-typename SerialQueue<T>::ConstIterator& SerialQueue<T>::ConstIterator::operator++() {
- const T* vectorData = mStorageIterator->second.data();
-
- if (mSerialIterator == nullptr) {
- mSerialIterator = vectorData + 1;
- } else {
- mSerialIterator++;
- }
-
- if (mSerialIterator >= vectorData + mStorageIterator->second.size()) {
- mSerialIterator = nullptr;
- mStorageIterator++;
- }
-
- return *this;
-}
-
-template <typename T>
-bool SerialQueue<T>::ConstIterator::operator==(
- const typename SerialQueue<T>::ConstIterator& other) const {
- return other.mStorageIterator == mStorageIterator && other.mSerialIterator == mSerialIterator;
-}
-
-template <typename T>
-bool SerialQueue<T>::ConstIterator::operator!=(
- const typename SerialQueue<T>::ConstIterator& other) const {
- return !(*this == other);
-}
-
-template <typename T>
-const T& SerialQueue<T>::ConstIterator::operator*() const {
- if (mSerialIterator == nullptr) {
- return *mStorageIterator->second.begin();
- }
- return *mSerialIterator;
+ DAWN_ASSERT(this->Empty() || this->mStorage.back().first <= serial);
+ this->mStorage.emplace_back(SerialPair(serial, {values}));
}
#endif // COMMON_SERIALQUEUE_H_
diff --git a/src/common/SerialStorage.h b/src/common/SerialStorage.h
new file mode 100644
index 0000000..60fae47
--- /dev/null
+++ b/src/common/SerialStorage.h
@@ -0,0 +1,315 @@
+// Copyright 2018 The Dawn Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef COMMON_SERIALSTORAGE_H_
+#define COMMON_SERIALSTORAGE_H_
+
+#include "common/Assert.h"
+#include "common/Serial.h"
+
+#include <cstdint>
+#include <utility>
+
+template <typename T>
+struct SerialStorageTraits {};
+
+template <typename Derived>
+class SerialStorage {
+ private:
+ using Value = typename SerialStorageTraits<Derived>::Value;
+ using Storage = typename SerialStorageTraits<Derived>::Storage;
+ using StorageIterator = typename SerialStorageTraits<Derived>::StorageIterator;
+ using ConstStorageIterator = typename SerialStorageTraits<Derived>::ConstStorageIterator;
+
+ public:
+ class Iterator {
+ public:
+ Iterator(StorageIterator start);
+ Iterator& operator++();
+
+ bool operator==(const Iterator& other) const;
+ bool operator!=(const Iterator& other) const;
+ Value& operator*() const;
+
+ private:
+ StorageIterator mStorageIterator;
+ // Special case the mSerialIterator when it should be equal to mStorageIterator.begin()
+ // otherwise we could ask mStorageIterator.begin() when mStorageIterator is mStorage.end()
+ // which is invalid. mStorageIterator.begin() is tagged with a nullptr.
+ Value* mSerialIterator;
+ };
+
+ class ConstIterator {
+ public:
+ ConstIterator(ConstStorageIterator start);
+ ConstIterator& operator++();
+
+ bool operator==(const ConstIterator& other) const;
+ bool operator!=(const ConstIterator& other) const;
+ const Value& operator*() const;
+
+ private:
+ ConstStorageIterator mStorageIterator;
+ const Value* mSerialIterator;
+ };
+
+ class BeginEnd {
+ public:
+ BeginEnd(StorageIterator start, StorageIterator end);
+
+ Iterator begin() const;
+ Iterator end() const;
+
+ private:
+ StorageIterator mStartIt;
+ StorageIterator mEndIt;
+ };
+
+ class ConstBeginEnd {
+ public:
+ ConstBeginEnd(ConstStorageIterator start, ConstStorageIterator end);
+
+ ConstIterator begin() const;
+ ConstIterator end() const;
+
+ private:
+ ConstStorageIterator mStartIt;
+ ConstStorageIterator mEndIt;
+ };
+
+ // Derived classes may specialize constraits for elements stored
+ // Ex.) SerialQueue enforces that the serial must be given in (not strictly)
+ // increasing order
+ template <typename... Params>
+ void Enqueue(Params&&... args, Serial serial) {
+ Derived::Enqueue(std::forward<Params>(args)..., serial);
+ }
+
+ bool Empty() const;
+
+ // The UpTo variants of Iterate and Clear affect all values associated to a serial
+ // that is smaller OR EQUAL to the given serial. Iterating is done like so:
+ // for (const T& value : queue.IterateAll()) { stuff(T); }
+ ConstBeginEnd IterateAll() const;
+ ConstBeginEnd IterateUpTo(Serial serial) const;
+ BeginEnd IterateAll();
+ BeginEnd IterateUpTo(Serial serial);
+
+ void Clear();
+ void ClearUpTo(Serial serial);
+
+ Serial FirstSerial() const;
+
+ protected:
+ // Returns the first StorageIterator that a serial bigger than serial.
+ ConstStorageIterator FindUpTo(Serial serial) const;
+ StorageIterator FindUpTo(Serial serial);
+ Storage mStorage;
+};
+
+// SerialStorage
+
+template <typename Derived>
+bool SerialStorage<Derived>::Empty() const {
+ return mStorage.empty();
+}
+
+template <typename Derived>
+typename SerialStorage<Derived>::ConstBeginEnd SerialStorage<Derived>::IterateAll() const {
+ return {mStorage.begin(), mStorage.end()};
+}
+
+template <typename Derived>
+typename SerialStorage<Derived>::ConstBeginEnd SerialStorage<Derived>::IterateUpTo(
+ Serial serial) const {
+ return {mStorage.begin(), FindUpTo(serial)};
+}
+
+template <typename Derived>
+typename SerialStorage<Derived>::BeginEnd SerialStorage<Derived>::IterateAll() {
+ return {mStorage.begin(), mStorage.end()};
+}
+
+template <typename Derived>
+typename SerialStorage<Derived>::BeginEnd SerialStorage<Derived>::IterateUpTo(Serial serial) {
+ return {mStorage.begin(), FindUpTo(serial)};
+}
+
+template <typename Derived>
+void SerialStorage<Derived>::Clear() {
+ mStorage.clear();
+}
+
+template <typename Derived>
+void SerialStorage<Derived>::ClearUpTo(Serial serial) {
+ mStorage.erase(mStorage.begin(), FindUpTo(serial));
+}
+
+template <typename Derived>
+Serial SerialStorage<Derived>::FirstSerial() const {
+ DAWN_ASSERT(!Empty());
+ return mStorage.begin()->first;
+}
+
+template <typename Derived>
+typename SerialStorage<Derived>::ConstStorageIterator SerialStorage<Derived>::FindUpTo(
+ Serial serial) const {
+ auto it = mStorage.begin();
+ while (it != mStorage.end() && it->first <= serial) {
+ it++;
+ }
+ return it;
+}
+
+template <typename Derived>
+typename SerialStorage<Derived>::StorageIterator SerialStorage<Derived>::FindUpTo(Serial serial) {
+ auto it = mStorage.begin();
+ while (it != mStorage.end() && it->first <= serial) {
+ it++;
+ }
+ return it;
+}
+
+// SerialStorage::BeginEnd
+
+template <typename Derived>
+SerialStorage<Derived>::BeginEnd::BeginEnd(typename SerialStorage<Derived>::StorageIterator start,
+ typename SerialStorage<Derived>::StorageIterator end)
+ : mStartIt(start), mEndIt(end) {
+}
+
+template <typename Derived>
+typename SerialStorage<Derived>::Iterator SerialStorage<Derived>::BeginEnd::begin() const {
+ return {mStartIt};
+}
+
+template <typename Derived>
+typename SerialStorage<Derived>::Iterator SerialStorage<Derived>::BeginEnd::end() const {
+ return {mEndIt};
+}
+
+// SerialStorage::Iterator
+
+template <typename Derived>
+SerialStorage<Derived>::Iterator::Iterator(typename SerialStorage<Derived>::StorageIterator start)
+ : mStorageIterator(start), mSerialIterator(nullptr) {
+}
+
+template <typename Derived>
+typename SerialStorage<Derived>::Iterator& SerialStorage<Derived>::Iterator::operator++() {
+ Value* vectorData = mStorageIterator->second.data();
+
+ if (mSerialIterator == nullptr) {
+ mSerialIterator = vectorData + 1;
+ } else {
+ mSerialIterator++;
+ }
+
+ if (mSerialIterator >= vectorData + mStorageIterator->second.size()) {
+ mSerialIterator = nullptr;
+ mStorageIterator++;
+ }
+
+ return *this;
+}
+
+template <typename Derived>
+bool SerialStorage<Derived>::Iterator::operator==(
+ const typename SerialStorage<Derived>::Iterator& other) const {
+ return other.mStorageIterator == mStorageIterator && other.mSerialIterator == mSerialIterator;
+}
+
+template <typename Derived>
+bool SerialStorage<Derived>::Iterator::operator!=(
+ const typename SerialStorage<Derived>::Iterator& other) const {
+ return !(*this == other);
+}
+
+template <typename Derived>
+typename SerialStorage<Derived>::Value& SerialStorage<Derived>::Iterator::operator*() const {
+ if (mSerialIterator == nullptr) {
+ return *mStorageIterator->second.begin();
+ }
+ return *mSerialIterator;
+}
+
+// SerialStorage::ConstBeginEnd
+
+template <typename Derived>
+SerialStorage<Derived>::ConstBeginEnd::ConstBeginEnd(
+ typename SerialStorage<Derived>::ConstStorageIterator start,
+ typename SerialStorage<Derived>::ConstStorageIterator end)
+ : mStartIt(start), mEndIt(end) {
+}
+
+template <typename Derived>
+typename SerialStorage<Derived>::ConstIterator SerialStorage<Derived>::ConstBeginEnd::begin()
+ const {
+ return {mStartIt};
+}
+
+template <typename Derived>
+typename SerialStorage<Derived>::ConstIterator SerialStorage<Derived>::ConstBeginEnd::end() const {
+ return {mEndIt};
+}
+
+// SerialStorage::ConstIterator
+
+template <typename Derived>
+SerialStorage<Derived>::ConstIterator::ConstIterator(
+ typename SerialStorage<Derived>::ConstStorageIterator start)
+ : mStorageIterator(start), mSerialIterator(nullptr) {
+}
+
+template <typename Derived>
+typename SerialStorage<Derived>::ConstIterator& SerialStorage<Derived>::ConstIterator::
+operator++() {
+ const Value* vectorData = mStorageIterator->second.data();
+
+ if (mSerialIterator == nullptr) {
+ mSerialIterator = vectorData + 1;
+ } else {
+ mSerialIterator++;
+ }
+
+ if (mSerialIterator >= vectorData + mStorageIterator->second.size()) {
+ mSerialIterator = nullptr;
+ mStorageIterator++;
+ }
+
+ return *this;
+}
+
+template <typename Derived>
+bool SerialStorage<Derived>::ConstIterator::operator==(
+ const typename SerialStorage<Derived>::ConstIterator& other) const {
+ return other.mStorageIterator == mStorageIterator && other.mSerialIterator == mSerialIterator;
+}
+
+template <typename Derived>
+bool SerialStorage<Derived>::ConstIterator::operator!=(
+ const typename SerialStorage<Derived>::ConstIterator& other) const {
+ return !(*this == other);
+}
+
+template <typename Derived>
+const typename SerialStorage<Derived>::Value& SerialStorage<Derived>::ConstIterator::operator*()
+ const {
+ if (mSerialIterator == nullptr) {
+ return *mStorageIterator->second.begin();
+ }
+ return *mSerialIterator;
+}
+
+#endif // COMMON_SERIALSTORAGE_H_
diff --git a/src/tests/unittests/SerialMapTests.cpp b/src/tests/unittests/SerialMapTests.cpp
new file mode 100644
index 0000000..e5d23e9
--- /dev/null
+++ b/src/tests/unittests/SerialMapTests.cpp
@@ -0,0 +1,164 @@
+// Copyright 2018 The Dawn Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include <gtest/gtest.h>
+
+#include "common/SerialMap.h"
+
+using TestSerialMap = SerialMap<int>;
+
+// A number of basic tests for SerialMap that are difficult to split from one another
+TEST(SerialMap, BasicTest) {
+ TestSerialMap map;
+
+ // Map starts empty
+ ASSERT_TRUE(map.Empty());
+
+ // Iterating on empty map 1) works 2) doesn't produce any values
+ for (int value : map.IterateAll()) {
+ DAWN_UNUSED(value);
+ ASSERT_TRUE(false);
+ }
+
+ // Enqueuing values as const ref or rvalue ref
+ map.Enqueue(1, 0);
+ map.Enqueue(2, 0);
+ map.Enqueue(std::move(3), 1);
+
+ // Iterating over a non-empty map produces the expected result
+ std::vector<int> expectedValues = {1, 2, 3};
+ for (int value : map.IterateAll()) {
+ EXPECT_EQ(expectedValues.front(), value);
+ ASSERT_FALSE(expectedValues.empty());
+ expectedValues.erase(expectedValues.begin());
+ }
+ ASSERT_TRUE(expectedValues.empty());
+
+ // Clear works and makes the map empty and iteration does nothing.
+ map.Clear();
+ ASSERT_TRUE(map.Empty());
+
+ for (int value : map.IterateAll()) {
+ DAWN_UNUSED(value);
+ ASSERT_TRUE(false);
+ }
+}
+
+// Test that items can be enqueued in an arbitrary order
+TEST(SerialMap, EnqueueOrder) {
+ TestSerialMap map;
+
+ // Enqueue values in an arbitrary order
+ map.Enqueue(3, 1);
+ map.Enqueue(1, 0);
+ map.Enqueue(4, 2);
+ map.Enqueue(5, 2);
+ map.Enqueue(2, 0);
+
+ // Iterating over a non-empty map produces the expected result
+ std::vector<int> expectedValues = {1, 2, 3, 4, 5};
+ for (int value : map.IterateAll()) {
+ EXPECT_EQ(expectedValues.front(), value);
+ ASSERT_FALSE(expectedValues.empty());
+ expectedValues.erase(expectedValues.begin());
+ }
+ ASSERT_TRUE(expectedValues.empty());
+}
+
+// Test enqueuing vectors works
+TEST(SerialMap, EnqueueVectors) {
+ TestSerialMap map;
+
+ std::vector<int> vector1 = {1, 2, 3, 4};
+ std::vector<int> vector2 = {5, 6, 7, 8};
+ std::vector<int> vector3 = {9, 0};
+
+ map.Enqueue(vector1, 0);
+ map.Enqueue(std::move(vector2), 0);
+ map.Enqueue(vector3, 1);
+
+ std::vector<int> expectedValues = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
+ for (int value : map.IterateAll()) {
+ EXPECT_EQ(expectedValues.front(), value);
+ ASSERT_FALSE(expectedValues.empty());
+ expectedValues.erase(expectedValues.begin());
+ }
+ ASSERT_TRUE(expectedValues.empty());
+}
+
+// Test IterateUpTo
+TEST(SerialMap, IterateUpTo) {
+ TestSerialMap map;
+
+ std::vector<int> vector1 = {1, 2, 3, 4};
+ std::vector<int> vector2 = {5, 6, 7, 8};
+ std::vector<int> vector3 = {9, 0};
+
+ map.Enqueue(vector1, 0);
+ map.Enqueue(std::move(vector2), 1);
+ map.Enqueue(vector3, 2);
+
+ std::vector<int> expectedValues = {1, 2, 3, 4, 5, 6, 7, 8};
+ for (int value : map.IterateUpTo(1)) {
+ EXPECT_EQ(expectedValues.front(), value);
+ ASSERT_FALSE(expectedValues.empty());
+ expectedValues.erase(expectedValues.begin());
+ }
+ ASSERT_TRUE(expectedValues.empty());
+}
+
+// Test ClearUpTo
+TEST(SerialMap, ClearUpTo) {
+ TestSerialMap map;
+
+ std::vector<int> vector1 = {1, 2, 3, 4};
+ std::vector<int> vector2 = {5, 6, 7, 8};
+ std::vector<int> vector3 = {9, 0};
+
+ map.Enqueue(vector1, 0);
+ map.Enqueue(std::move(vector2), 0);
+ map.Enqueue(vector3, 1);
+
+ map.ClearUpTo(0);
+
+ std::vector<int> expectedValues = {9, 0};
+ for (int value : map.IterateAll()) {
+ EXPECT_EQ(expectedValues.front(), value);
+ ASSERT_FALSE(expectedValues.empty());
+ expectedValues.erase(expectedValues.begin());
+ }
+ ASSERT_TRUE(expectedValues.empty());
+}
+
+// Test FirstSerial
+TEST(SerialMap, FirstSerial) {
+ TestSerialMap map;
+
+ std::vector<int> vector1 = {1, 2, 3, 4};
+ std::vector<int> vector2 = {5, 6, 7, 8};
+ std::vector<int> vector3 = {9, 0};
+
+ map.Enqueue(vector1, 0);
+ map.Enqueue(std::move(vector2), 1);
+ map.Enqueue(vector3, 2);
+
+ EXPECT_EQ(map.FirstSerial(), 0u);
+
+ map.ClearUpTo(1);
+ EXPECT_EQ(map.FirstSerial(), 2u);
+
+ map.Clear();
+ map.Enqueue(vector1, 6);
+ EXPECT_EQ(map.FirstSerial(), 6u);
+}
