1 // Copyright (c) 2016 Google Inc. 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 LIBSPIRV_OPT_ITERATOR_H_ 16 #define LIBSPIRV_OPT_ITERATOR_H_ 17 18 #include <cstddef> // for ptrdiff_t 19 #include <iterator> 20 #include <memory> 21 #include <type_traits> 22 #include <vector> 23 24 namespace spvtools { 25 namespace ir { 26 27 // An ad hoc iterator class for std::vector<std::unique_ptr<|ValueType|>>. The 28 // purpose of this iterator class is to provide transparent access to those 29 // std::unique_ptr managed elements in the vector, behaving like we are using 30 // std::vector<|ValueType|>. 31 template <typename ValueType, bool IsConst = false> 32 class UptrVectorIterator 33 : public std::iterator<std::random_access_iterator_tag, 34 typename std::conditional<IsConst, const ValueType, 35 ValueType>::type> { 36 public: 37 using super = std::iterator< 38 std::random_access_iterator_tag, 39 typename std::conditional<IsConst, const ValueType, ValueType>::type>; 40 41 using pointer = typename super::pointer; 42 using reference = typename super::reference; 43 using difference_type = typename super::difference_type; 44 45 // Type aliases. We need to apply constness properly if |IsConst| is true. 46 using Uptr = std::unique_ptr<ValueType>; 47 using UptrVector = typename std::conditional<IsConst, const std::vector<Uptr>, 48 std::vector<Uptr>>::type; 49 using UnderlyingIterator = 50 typename std::conditional<IsConst, typename UptrVector::const_iterator, 51 typename UptrVector::iterator>::type; 52 53 // Creates a new iterator from the given |container| and its raw iterator 54 // |it|. 55 UptrVectorIterator(UptrVector* container, const UnderlyingIterator& it) 56 : container_(container), iterator_(it) {} 57 UptrVectorIterator(const UptrVectorIterator&) = default; 58 UptrVectorIterator& operator=(const UptrVectorIterator&) = default; 59 60 inline UptrVectorIterator& operator++(); 61 inline UptrVectorIterator operator++(int); 62 inline UptrVectorIterator& operator--(); 63 inline UptrVectorIterator operator--(int); 64 65 reference operator*() const { return **iterator_; } 66 pointer operator->() { return (*iterator_).get(); } 67 reference operator[](ptrdiff_t index) { return **(iterator_ + index); } 68 69 inline bool operator==(const UptrVectorIterator& that) const; 70 inline bool operator!=(const UptrVectorIterator& that) const; 71 72 inline ptrdiff_t operator-(const UptrVectorIterator& that) const; 73 inline bool operator<(const UptrVectorIterator& that) const; 74 75 // Inserts the given |value| to the position pointed to by this iterator 76 // and returns an iterator to the newly iserted |value|. 77 // If the underlying vector changes capacity, all previous iterators will be 78 // invalidated. Otherwise, those previous iterators pointing to after the 79 // insertion point will be invalidated. 80 template <bool IsConstForMethod = IsConst> 81 inline typename std::enable_if<!IsConstForMethod, UptrVectorIterator>::type 82 InsertBefore(Uptr value); 83 84 // Inserts the given |valueVector| to the position pointed to by this iterator 85 // and returns an iterator to the first newly inserted value. 86 // If the underlying vector changes capacity, all previous iterators will be 87 // invalidated. Otherwise, those previous iterators pointing to after the 88 // insertion point will be invalidated. 89 template <bool IsConstForMethod = IsConst> 90 inline typename std::enable_if<!IsConstForMethod, UptrVectorIterator>::type 91 InsertBefore(UptrVector* valueVector); 92 93 // Erases the value at the position pointed to by this iterator 94 // and returns an iterator to the following value. 95 // If the underlying vector changes capacity, all previous iterators will be 96 // invalidated. Otherwise, those previous iterators pointing to after the 97 // erasure point will be invalidated. 98 template <bool IsConstForMethod = IsConst> 99 inline typename std::enable_if<!IsConstForMethod, UptrVectorIterator>::type 100 Erase(); 101 102 private: 103 UptrVector* container_; // The container we are manipulating. 104 UnderlyingIterator iterator_; // The raw iterator from the container. 105 }; 106 107 // Handy class for a (begin, end) iterator pair. 108 template <typename IteratorType> 109 class IteratorRange { 110 public: 111 IteratorRange(IteratorType b, IteratorType e) : begin_(b), end_(e) {} 112 113 IteratorType begin() const { return begin_; } 114 IteratorType end() const { return end_; } 115 116 bool empty() const { return begin_ == end_; } 117 size_t size() const { return end_ - begin_; } 118 119 private: 120 IteratorType begin_; 121 IteratorType end_; 122 }; 123 124 // Returns a (begin, end) iterator pair for the given container. 125 template <typename ValueType, 126 class IteratorType = UptrVectorIterator<ValueType>> 127 inline IteratorRange<IteratorType> make_range( 128 std::vector<std::unique_ptr<ValueType>>& container) { 129 return {IteratorType(&container, container.begin()), 130 IteratorType(&container, container.end())}; 131 } 132 133 // Returns a const (begin, end) iterator pair for the given container. 134 template <typename ValueType, 135 class IteratorType = UptrVectorIterator<ValueType, true>> 136 inline IteratorRange<IteratorType> make_const_range( 137 const std::vector<std::unique_ptr<ValueType>>& container) { 138 return {IteratorType(&container, container.cbegin()), 139 IteratorType(&container, container.cend())}; 140 } 141 142 template <typename VT, bool IC> 143 inline UptrVectorIterator<VT, IC>& UptrVectorIterator<VT, IC>::operator++() { 144 ++iterator_; 145 return *this; 146 } 147 148 template <typename VT, bool IC> 149 inline UptrVectorIterator<VT, IC> UptrVectorIterator<VT, IC>::operator++(int) { 150 auto it = *this; 151 ++(*this); 152 return it; 153 } 154 155 template <typename VT, bool IC> 156 inline UptrVectorIterator<VT, IC>& UptrVectorIterator<VT, IC>::operator--() { 157 --iterator_; 158 return *this; 159 } 160 161 template <typename VT, bool IC> 162 inline UptrVectorIterator<VT, IC> UptrVectorIterator<VT, IC>::operator--(int) { 163 auto it = *this; 164 --(*this); 165 return it; 166 } 167 168 template <typename VT, bool IC> 169 inline bool UptrVectorIterator<VT, IC>::operator==( 170 const UptrVectorIterator& that) const { 171 return container_ == that.container_ && iterator_ == that.iterator_; 172 } 173 174 template <typename VT, bool IC> 175 inline bool UptrVectorIterator<VT, IC>::operator!=( 176 const UptrVectorIterator& that) const { 177 return !(*this == that); 178 } 179 180 template <typename VT, bool IC> 181 inline ptrdiff_t UptrVectorIterator<VT, IC>::operator-( 182 const UptrVectorIterator& that) const { 183 assert(container_ == that.container_); 184 return iterator_ - that.iterator_; 185 } 186 187 template <typename VT, bool IC> 188 inline bool UptrVectorIterator<VT, IC>::operator<( 189 const UptrVectorIterator& that) const { 190 assert(container_ == that.container_); 191 return iterator_ < that.iterator_; 192 } 193 194 template <typename VT, bool IC> 195 template <bool IsConstForMethod> 196 inline 197 typename std::enable_if<!IsConstForMethod, UptrVectorIterator<VT, IC>>::type 198 UptrVectorIterator<VT, IC>::InsertBefore(Uptr value) { 199 auto index = iterator_ - container_->begin(); 200 container_->insert(iterator_, std::move(value)); 201 return UptrVectorIterator(container_, container_->begin() + index); 202 } 203 204 template <typename VT, bool IC> 205 template <bool IsConstForMethod> 206 inline 207 typename std::enable_if<!IsConstForMethod, UptrVectorIterator<VT, IC>>::type 208 UptrVectorIterator<VT, IC>::InsertBefore(UptrVector* values) { 209 const auto pos = iterator_ - container_->begin(); 210 const auto origsz = container_->size(); 211 container_->resize(origsz + values->size()); 212 std::move_backward(container_->begin() + pos, container_->begin() + origsz, 213 container_->end()); 214 std::move(values->begin(), values->end(), container_->begin() + pos); 215 return UptrVectorIterator(container_, container_->begin() + pos); 216 } 217 218 template <typename VT, bool IC> 219 template <bool IsConstForMethod> 220 inline 221 typename std::enable_if<!IsConstForMethod, UptrVectorIterator<VT, IC>>::type 222 UptrVectorIterator<VT, IC>::Erase() { 223 auto index = iterator_ - container_->begin(); 224 (void)container_->erase(iterator_); 225 return UptrVectorIterator(container_, container_->begin() + index); 226 } 227 228 } // namespace ir 229 } // namespace spvtools 230 231 #endif // LIBSPIRV_OPT_ITERATOR_H_ 232
