1 // Copyright 2017 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_SERIALQUEUE_H_ 16 #define COMMON_SERIALQUEUE_H_ 17 18 #include "common/SerialStorage.h" 19 20 #include <vector> 21 22 template <typename Serial, typename Value> 23 class SerialQueue; 24 25 template <typename SerialT, typename ValueT> 26 struct SerialStorageTraits<SerialQueue<SerialT, ValueT>> { 27 using Serial = SerialT; 28 using Value = ValueT; 29 using SerialPair = std::pair<Serial, std::vector<Value>>; 30 using Storage = std::vector<SerialPair>; 31 using StorageIterator = typename Storage::iterator; 32 using ConstStorageIterator = typename Storage::const_iterator; 33 }; 34 35 // SerialQueue stores an associative list mapping a Serial to Value. 36 // It enforces that the Serials enqueued are strictly non-decreasing. 37 // This makes it very efficient iterate or clear all items added up 38 // to some Serial value because they are stored contiguously in memory. 39 template <typename Serial, typename Value> 40 class SerialQueue : public SerialStorage<SerialQueue<Serial, Value>> { 41 public: 42 43 // The serial must be given in (not strictly) increasing order. 44 void Enqueue(const Value& value, Serial serial); 45 void Enqueue(Value&& value, Serial serial); 46 void Enqueue(const std::vector<Value>& values, Serial serial); 47 void Enqueue(std::vector<Value>&& values, Serial serial); 48 }; 49 50 // SerialQueue 51 52 template <typename Serial, typename Value> 53 void SerialQueue<Serial, Value>::Enqueue(const Value& value, Serial serial) { 54 DAWN_ASSERT(this->Empty() || this->mStorage.back().first <= serial); 55 56 if (this->Empty() || this->mStorage.back().first < serial) { 57 this->mStorage.emplace_back(serial, std::vector<Value>{}); 58 } 59 this->mStorage.back().second.push_back(value); 60 } 61 62 template <typename Serial, typename Value> 63 void SerialQueue<Serial, Value>::Enqueue(Value&& value, Serial serial) { 64 DAWN_ASSERT(this->Empty() || this->mStorage.back().first <= serial); 65 66 if (this->Empty() || this->mStorage.back().first < serial) { 67 this->mStorage.emplace_back(serial, std::vector<Value>{}); 68 } 69 this->mStorage.back().second.push_back(std::move(value)); 70 } 71 72 template <typename Serial, typename Value> 73 void SerialQueue<Serial, Value>::Enqueue(const std::vector<Value>& values, Serial serial) { 74 DAWN_ASSERT(values.size() > 0); 75 DAWN_ASSERT(this->Empty() || this->mStorage.back().first <= serial); 76 this->mStorage.emplace_back(serial, values); 77 } 78 79 template <typename Serial, typename Value> 80 void SerialQueue<Serial, Value>::Enqueue(std::vector<Value>&& values, Serial serial) { 81 DAWN_ASSERT(values.size() > 0); 82 DAWN_ASSERT(this->Empty() || this->mStorage.back().first <= serial); 83 this->mStorage.emplace_back(serial, values); 84 } 85 86 #endif // COMMON_SERIALQUEUE_H_ 87