1 // Safe iterator implementation -*- C++ -*- 2 3 // Copyright (C) 2011-2014 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /** @file debug/safe_local_iterator.h 26 * This file is a GNU debug extension to the Standard C++ Library. 27 */ 28 29 #ifndef _GLIBCXX_DEBUG_SAFE_LOCAL_ITERATOR_H 30 #define _GLIBCXX_DEBUG_SAFE_LOCAL_ITERATOR_H 1 31 32 #include <debug/debug.h> 33 #include <debug/macros.h> 34 #include <debug/functions.h> 35 #include <debug/safe_unordered_base.h> 36 #include <ext/type_traits.h> 37 38 namespace __gnu_debug 39 { 40 /** \brief Safe iterator wrapper. 41 * 42 * The class template %_Safe_local_iterator is a wrapper around an 43 * iterator that tracks the iterator's movement among sequences and 44 * checks that operations performed on the "safe" iterator are 45 * legal. In additional to the basic iterator operations (which are 46 * validated, and then passed to the underlying iterator), 47 * %_Safe_local_iterator has member functions for iterator invalidation, 48 * attaching/detaching the iterator from sequences, and querying 49 * the iterator's state. 50 */ 51 template<typename _Iterator, typename _Sequence> 52 class _Safe_local_iterator : public _Safe_local_iterator_base 53 { 54 typedef _Safe_local_iterator _Self; 55 typedef typename _Sequence::const_local_iterator _Const_local_iterator; 56 typedef typename _Sequence::size_type size_type; 57 58 /// The underlying iterator 59 _Iterator _M_current; 60 61 /// Determine if this is a constant iterator. 62 bool 63 _M_constant() const 64 { 65 return std::__are_same<_Const_local_iterator, 66 _Safe_local_iterator>::__value; 67 } 68 69 typedef std::iterator_traits<_Iterator> _Traits; 70 71 public: 72 typedef _Iterator iterator_type; 73 typedef typename _Traits::iterator_category iterator_category; 74 typedef typename _Traits::value_type value_type; 75 typedef typename _Traits::difference_type difference_type; 76 typedef typename _Traits::reference reference; 77 typedef typename _Traits::pointer pointer; 78 79 /// @post the iterator is singular and unattached 80 _Safe_local_iterator() : _M_current() { } 81 82 /** 83 * @brief Safe iterator construction from an unsafe iterator and 84 * its sequence. 85 * 86 * @pre @p seq is not NULL 87 * @post this is not singular 88 */ 89 _Safe_local_iterator(const _Iterator& __i, const _Sequence* __seq) 90 : _Safe_local_iterator_base(__seq, _M_constant()), _M_current(__i) 91 { 92 _GLIBCXX_DEBUG_VERIFY(!this->_M_singular(), 93 _M_message(__msg_init_singular) 94 ._M_iterator(*this, "this")); 95 } 96 97 /** 98 * @brief Copy construction. 99 */ 100 _Safe_local_iterator(const _Safe_local_iterator& __x) 101 : _Safe_local_iterator_base(__x, _M_constant()), 102 _M_current(__x._M_current) 103 { 104 // _GLIBCXX_RESOLVE_LIB_DEFECTS 105 // DR 408. Is vector<reverse_iterator<char*> > forbidden? 106 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 107 || __x.base() == _Iterator(), 108 _M_message(__msg_init_copy_singular) 109 ._M_iterator(*this, "this") 110 ._M_iterator(__x, "other")); 111 } 112 113 /** 114 * @brief Converting constructor from a mutable iterator to a 115 * constant iterator. 116 */ 117 template<typename _MutableIterator> 118 _Safe_local_iterator( 119 const _Safe_local_iterator<_MutableIterator, 120 typename __gnu_cxx::__enable_if<std::__are_same< 121 _MutableIterator, 122 typename _Sequence::local_iterator::iterator_type>::__value, 123 _Sequence>::__type>& __x) 124 : _Safe_local_iterator_base(__x, _M_constant()), 125 _M_current(__x.base()) 126 { 127 // _GLIBCXX_RESOLVE_LIB_DEFECTS 128 // DR 408. Is vector<reverse_iterator<char*> > forbidden? 129 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 130 || __x.base() == _Iterator(), 131 _M_message(__msg_init_const_singular) 132 ._M_iterator(*this, "this") 133 ._M_iterator(__x, "other")); 134 } 135 136 /** 137 * @brief Copy assignment. 138 */ 139 _Safe_local_iterator& 140 operator=(const _Safe_local_iterator& __x) 141 { 142 // _GLIBCXX_RESOLVE_LIB_DEFECTS 143 // DR 408. Is vector<reverse_iterator<char*> > forbidden? 144 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 145 || __x.base() == _Iterator(), 146 _M_message(__msg_copy_singular) 147 ._M_iterator(*this, "this") 148 ._M_iterator(__x, "other")); 149 _M_current = __x._M_current; 150 this->_M_attach(__x._M_sequence); 151 return *this; 152 } 153 154 /** 155 * @brief Iterator dereference. 156 * @pre iterator is dereferenceable 157 */ 158 reference 159 operator*() const 160 { 161 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(), 162 _M_message(__msg_bad_deref) 163 ._M_iterator(*this, "this")); 164 return *_M_current; 165 } 166 167 /** 168 * @brief Iterator dereference. 169 * @pre iterator is dereferenceable 170 * @todo Make this correct w.r.t. iterators that return proxies 171 */ 172 pointer 173 operator->() const 174 { 175 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(), 176 _M_message(__msg_bad_deref) 177 ._M_iterator(*this, "this")); 178 return std::__addressof(*_M_current); 179 } 180 181 // ------ Input iterator requirements ------ 182 /** 183 * @brief Iterator preincrement 184 * @pre iterator is incrementable 185 */ 186 _Safe_local_iterator& 187 operator++() 188 { 189 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(), 190 _M_message(__msg_bad_inc) 191 ._M_iterator(*this, "this")); 192 ++_M_current; 193 return *this; 194 } 195 196 /** 197 * @brief Iterator postincrement 198 * @pre iterator is incrementable 199 */ 200 _Safe_local_iterator 201 operator++(int) 202 { 203 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(), 204 _M_message(__msg_bad_inc) 205 ._M_iterator(*this, "this")); 206 _Safe_local_iterator __tmp(*this); 207 ++_M_current; 208 return __tmp; 209 } 210 211 // ------ Utilities ------ 212 /** 213 * @brief Return the underlying iterator 214 */ 215 _Iterator 216 base() const { return _M_current; } 217 218 /** 219 * @brief Return the bucket 220 */ 221 size_type 222 bucket() const { return _M_current._M_get_bucket(); } 223 224 /** 225 * @brief Conversion to underlying non-debug iterator to allow 226 * better interaction with non-debug containers. 227 */ 228 operator _Iterator() const { return _M_current; } 229 230 /** Attach iterator to the given sequence. */ 231 void 232 _M_attach(_Safe_sequence_base* __seq) 233 { _Safe_iterator_base::_M_attach(__seq, _M_constant()); } 234 235 /** Likewise, but not thread-safe. */ 236 void 237 _M_attach_single(_Safe_sequence_base* __seq) 238 { _Safe_iterator_base::_M_attach_single(__seq, _M_constant()); } 239 240 /// Is the iterator dereferenceable? 241 bool 242 _M_dereferenceable() const 243 { return !this->_M_singular() && !_M_is_end(); } 244 245 /// Is the iterator incrementable? 246 bool 247 _M_incrementable() const 248 { return !this->_M_singular() && !_M_is_end(); } 249 250 // Is the iterator range [*this, __rhs) valid? 251 bool 252 _M_valid_range(const _Safe_local_iterator& __rhs) const; 253 254 // The sequence this iterator references. 255 typename 256 __gnu_cxx::__conditional_type<std::__are_same<_Const_local_iterator, 257 _Safe_local_iterator>::__value, 258 const _Sequence*, 259 _Sequence*>::__type 260 _M_get_sequence() const 261 { return static_cast<_Sequence*>(_M_sequence); } 262 263 /// Is this iterator equal to the sequence's begin(bucket) iterator? 264 bool _M_is_begin() const 265 { return base() == _M_get_sequence()->_M_base().begin(bucket()); } 266 267 /// Is this iterator equal to the sequence's end(bucket) iterator? 268 bool _M_is_end() const 269 { return base() == _M_get_sequence()->_M_base().end(bucket()); } 270 271 /// Is this iterator part of the same bucket as the other one? 272 template<typename _Other> 273 bool 274 _M_in_same_bucket(const _Safe_local_iterator<_Other, 275 _Sequence>& __other) const 276 { return bucket() == __other.bucket(); } 277 }; 278 279 template<typename _IteratorL, typename _IteratorR, typename _Sequence> 280 inline bool 281 operator==(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs, 282 const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs) 283 { 284 _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(), 285 _M_message(__msg_iter_compare_bad) 286 ._M_iterator(__lhs, "lhs") 287 ._M_iterator(__rhs, "rhs")); 288 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 289 _M_message(__msg_compare_different) 290 ._M_iterator(__lhs, "lhs") 291 ._M_iterator(__rhs, "rhs")); 292 _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs), 293 _M_message(__msg_local_iter_compare_bad) 294 ._M_iterator(__lhs, "lhs") 295 ._M_iterator(__rhs, "rhs")); 296 return __lhs.base() == __rhs.base(); 297 } 298 299 template<typename _Iterator, typename _Sequence> 300 inline bool 301 operator==(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs, 302 const _Safe_local_iterator<_Iterator, _Sequence>& __rhs) 303 { 304 _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(), 305 _M_message(__msg_iter_compare_bad) 306 ._M_iterator(__lhs, "lhs") 307 ._M_iterator(__rhs, "rhs")); 308 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 309 _M_message(__msg_compare_different) 310 ._M_iterator(__lhs, "lhs") 311 ._M_iterator(__rhs, "rhs")); 312 _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs), 313 _M_message(__msg_local_iter_compare_bad) 314 ._M_iterator(__lhs, "lhs") 315 ._M_iterator(__rhs, "rhs")); 316 return __lhs.base() == __rhs.base(); 317 } 318 319 template<typename _IteratorL, typename _IteratorR, typename _Sequence> 320 inline bool 321 operator!=(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs, 322 const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs) 323 { 324 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 325 _M_message(__msg_iter_compare_bad) 326 ._M_iterator(__lhs, "lhs") 327 ._M_iterator(__rhs, "rhs")); 328 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 329 _M_message(__msg_compare_different) 330 ._M_iterator(__lhs, "lhs") 331 ._M_iterator(__rhs, "rhs")); 332 _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs), 333 _M_message(__msg_local_iter_compare_bad) 334 ._M_iterator(__lhs, "lhs") 335 ._M_iterator(__rhs, "rhs")); 336 return __lhs.base() != __rhs.base(); 337 } 338 339 template<typename _Iterator, typename _Sequence> 340 inline bool 341 operator!=(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs, 342 const _Safe_local_iterator<_Iterator, _Sequence>& __rhs) 343 { 344 _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(), 345 _M_message(__msg_iter_compare_bad) 346 ._M_iterator(__lhs, "lhs") 347 ._M_iterator(__rhs, "rhs")); 348 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 349 _M_message(__msg_compare_different) 350 ._M_iterator(__lhs, "lhs") 351 ._M_iterator(__rhs, "rhs")); 352 _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs), 353 _M_message(__msg_local_iter_compare_bad) 354 ._M_iterator(__lhs, "lhs") 355 ._M_iterator(__rhs, "rhs")); 356 return __lhs.base() != __rhs.base(); 357 } 358 } // namespace __gnu_debug 359 360 #include <debug/safe_local_iterator.tcc> 361 362 #endif 363