1 /* 2 Copyright (c) 2005-2021 Intel Corporation 3 4 Licensed under the Apache License, Version 2.0 (the "License"); 5 you may not use this file except in compliance with the License. 6 You may obtain a copy of the License at 7 8 http://www.apache.org/licenses/LICENSE-2.0 9 10 Unless required by applicable law or agreed to in writing, software 11 distributed under the License is distributed on an "AS IS" BASIS, 12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 See the License for the specific language governing permissions and 14 limitations under the License. 15 */ 16 17 #ifndef __TBB_test_common_iterator_H 18 #define __TBB_test_common_iterator_H 19 20 #include "config.h" 21 22 #include <iterator> 23 #include <memory> 24 #include <atomic> 25 #include "utils_assert.h" 26 27 namespace utils { 28 29 template <typename T> 30 class InputIterator { 31 typedef std::allocator<T> allocator_type; 32 typedef std::allocator_traits<allocator_type> allocator_traits_type; 33 public: 34 typedef std::input_iterator_tag iterator_category; 35 typedef T value_type; 36 typedef typename allocator_traits_type::difference_type difference_type; 37 typedef typename allocator_traits_type::pointer pointer; 38 typedef typename allocator_traits_type::value_type& reference; 39 InputIterator()40 InputIterator() : my_ptr(nullptr) {} InputIterator(T * ptr)41 explicit InputIterator ( T * ptr ) : my_ptr(ptr), my_shared_epoch(new Epoch), my_current_epoch(0) {} 42 InputIterator(const InputIterator & it)43 InputIterator( const InputIterator& it ) { 44 REQUIRE_MESSAGE(it.my_current_epoch == it.my_shared_epoch->epoch, "Copying an invalidated iterator"); 45 my_ptr = it.my_ptr; 46 my_shared_epoch = it.my_shared_epoch; 47 my_current_epoch = it.my_current_epoch; 48 ++my_shared_epoch->refcounter; 49 } 50 51 InputIterator& operator= ( const InputIterator& it ) { 52 REQUIRE_MESSAGE(it.my_current_epoch == it.my_shared_epoch->epoch, "Assigning an invalidated iterator"); 53 my_ptr = it.my_ptr; 54 my_current_epoch = it.my_current_epoch; 55 if(my_shared_epoch == it.my_shared_epoch) 56 return *this; 57 destroy(); 58 my_shared_epoch = it.my_shared_epoch; 59 ++my_shared_epoch->refcounter; 60 return *this; 61 } 62 63 T& operator* () const { 64 REQUIRE_MESSAGE(my_shared_epoch->epoch == my_current_epoch, "Dereferencing an invalidated input iterator"); 65 return *my_ptr; 66 } 67 68 InputIterator& operator++ () { 69 REQUIRE_MESSAGE(my_shared_epoch->epoch == my_current_epoch, "Incrementing an invalidated input iterator"); 70 ++my_ptr; 71 ++my_current_epoch; 72 ++my_shared_epoch->epoch; 73 return *this; 74 } 75 76 InputIterator operator++( int ) { 77 InputIterator it = *this; 78 ++*this; 79 return it; 80 } 81 82 bool operator== ( const InputIterator& it ) const { 83 REQUIRE_MESSAGE(my_shared_epoch->epoch == my_current_epoch, "Comparing an invalidated input iterator"); 84 REQUIRE_MESSAGE(it.my_shared_epoch->epoch == it.my_current_epoch, "Comparing with an invalidated input iterator"); 85 return my_ptr == it.my_ptr; 86 } 87 ~InputIterator()88 ~InputIterator() { 89 destroy(); 90 } 91 private: destroy()92 void destroy() { 93 if(0 == --my_shared_epoch->refcounter) { 94 delete my_shared_epoch; 95 } 96 } 97 struct Epoch { 98 typedef std::atomic<size_t> Counter; EpochEpoch99 Epoch() { epoch = 0; refcounter = 1; } 100 Counter epoch; 101 Counter refcounter; 102 }; 103 104 T * my_ptr; 105 Epoch *my_shared_epoch; 106 size_t my_current_epoch; 107 }; 108 109 template <typename T> 110 class ForwardIterator { 111 T * my_ptr; 112 typedef std::allocator<T> allocator_type; 113 typedef std::allocator_traits<allocator_type> allocator_traits_type; 114 public: 115 typedef std::forward_iterator_tag iterator_category; 116 typedef T value_type; 117 typedef typename allocator_traits_type::difference_type difference_type; 118 typedef typename allocator_traits_type::pointer pointer; 119 typedef typename allocator_traits_type::value_type& reference; 120 ForwardIterator()121 ForwardIterator() : my_ptr(nullptr) {} ForwardIterator(T * ptr)122 explicit ForwardIterator ( T * ptr ) : my_ptr(ptr){} 123 ForwardIterator(const ForwardIterator & r)124 ForwardIterator ( const ForwardIterator& r ) : my_ptr(r.my_ptr){} 125 T& operator* () const { return *my_ptr; } 126 ForwardIterator& operator++ () { ++my_ptr; return *this; } 127 ForwardIterator operator++(int) { 128 ForwardIterator result = *this; 129 ++*this; 130 return result; 131 } 132 133 bool operator== ( const ForwardIterator& r ) const { return my_ptr == r.my_ptr; } 134 }; 135 136 template <typename T> 137 class RandomIterator { 138 T * my_ptr; 139 typedef std::allocator<T> allocator_type; 140 typedef std::allocator_traits<allocator_type> allocator_traits_type; 141 public: 142 typedef std::random_access_iterator_tag iterator_category; 143 typedef T value_type; 144 typedef typename allocator_traits_type::pointer pointer; 145 typedef typename allocator_traits_type::value_type& reference; 146 typedef typename allocator_traits_type::difference_type difference_type; 147 RandomIterator()148 RandomIterator() : my_ptr(nullptr) {} RandomIterator(T * ptr)149 explicit RandomIterator ( T * ptr ) : my_ptr(ptr){} RandomIterator(const RandomIterator & r)150 RandomIterator ( const RandomIterator& r ) : my_ptr(r.my_ptr){} 151 T& operator* () const { return *my_ptr; } 152 RandomIterator& operator++ () { ++my_ptr; return *this; } 153 RandomIterator operator++(int) { 154 RandomIterator result = *this; 155 ++*this; 156 return result; 157 } 158 RandomIterator& operator--() { --my_ptr; return *this; } 159 RandomIterator operator--(int) { 160 RandomIterator result = *this; 161 --*this; 162 return result; 163 } 164 165 bool operator== ( const RandomIterator& r ) const { return my_ptr == r.my_ptr; } 166 bool operator!= ( const RandomIterator& r ) const { return my_ptr != r.my_ptr; } 167 difference_type operator- (const RandomIterator &r) const {return my_ptr - r.my_ptr;} 168 RandomIterator operator+ (difference_type n) const {return RandomIterator(my_ptr + n);} 169 bool operator< (const RandomIterator &r) const {return my_ptr < r.my_ptr;} 170 bool operator> (const RandomIterator &r) const {return my_ptr > r.my_ptr;} 171 bool operator<=(const RandomIterator &r) const {return my_ptr <= r.my_ptr;} 172 bool operator>=(const RandomIterator &r) const {return my_ptr >= r.my_ptr;} 173 174 RandomIterator& operator+=( difference_type n ) { 175 my_ptr += n; 176 return *this; 177 } 178 RandomIterator& operator-=( difference_type n ) { 179 my_ptr -= n; 180 return *this; 181 } 182 183 friend RandomIterator operator+( difference_type n, RandomIterator it ) { 184 return RandomIterator(it.my_ptr + n); 185 } 186 RandomIterator operator-( difference_type n ) const { 187 return RandomIterator(my_ptr - n); 188 } 189 reference operator[]( difference_type n ) const { 190 return my_ptr[n]; 191 } 192 }; 193 194 template <typename T> 195 class ConstRandomIterator { 196 const T * my_ptr; 197 typedef std::allocator<T> allocator_type; 198 typedef std::allocator_traits<allocator_type> allocator_traits_type; 199 public: 200 typedef std::random_access_iterator_tag iterator_category; 201 typedef const T value_type; 202 typedef typename allocator_traits_type::const_pointer pointer; 203 typedef const typename allocator_traits_type::value_type& reference; 204 typedef typename allocator_traits_type::difference_type difference_type; 205 ConstRandomIterator()206 ConstRandomIterator() : my_ptr(nullptr) {} ConstRandomIterator(const T * ptr)207 explicit ConstRandomIterator ( const T * ptr ) : my_ptr(ptr){} ConstRandomIterator(const ConstRandomIterator & r)208 ConstRandomIterator ( const ConstRandomIterator& r ) : my_ptr(r.my_ptr){} 209 const T& operator* () const { return *my_ptr; } 210 ConstRandomIterator& operator++ () { ++my_ptr; return *this; } 211 ConstRandomIterator operator++(int) { 212 ConstRandomIterator result = *this; 213 ++*this; 214 return result; 215 } 216 ConstRandomIterator& operator--() { --my_ptr; return *this; } 217 ConstRandomIterator operator--(int) { 218 ConstRandomIterator result = *this; 219 --*this; 220 return result; 221 } 222 223 bool operator== ( const ConstRandomIterator& r ) const { return my_ptr == r.my_ptr; } 224 bool operator!= ( const ConstRandomIterator& r ) const { return my_ptr != r.my_ptr; } 225 difference_type operator- (const ConstRandomIterator &r) const {return my_ptr - r.my_ptr;} 226 ConstRandomIterator operator+ (difference_type n) const {return ConstRandomIterator(my_ptr + n);} 227 bool operator< (const ConstRandomIterator &r) const {return my_ptr < r.my_ptr;} 228 bool operator> (const ConstRandomIterator &r) const {return my_ptr > r.my_ptr;} 229 bool operator<=(const ConstRandomIterator &r) const {return my_ptr <= r.my_ptr;} 230 bool operator>=(const ConstRandomIterator &r) const {return my_ptr >= r.my_ptr;} 231 232 233 ConstRandomIterator& operator+=( difference_type n ) { 234 my_ptr += n; 235 return *this; 236 } 237 ConstRandomIterator& operator-=( difference_type n ) { 238 my_ptr -= n; 239 return *this; 240 } 241 242 friend ConstRandomIterator operator+( difference_type n, ConstRandomIterator it ) { 243 return ConstRandomIterator(it.my_ptr + n); 244 } 245 ConstRandomIterator operator-( difference_type n ) const { 246 return ConstRandomIterator(my_ptr - n); 247 } 248 reference operator[]( difference_type n ) const { 249 return my_ptr[n]; 250 } 251 }; 252 253 } // namespace utils 254 255 #endif // __TBB_test_common_iterator_H 256