1 // Safe iterator implementation -*- C++ -*- 2 3 // Copyright (C) 2011 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::size_type size_type; 56 57 /// The underlying iterator 58 _Iterator _M_current; 59 60 /// The bucket this local iterator belongs to 61 size_type _M_bucket; 62 63 /// Determine if this is a constant iterator. 64 bool 65 _M_constant() const 66 { 67 typedef typename _Sequence::const_local_iterator const_iterator; 68 return std::__are_same<const_iterator, _Safe_local_iterator>::__value; 69 } 70 71 typedef std::iterator_traits<_Iterator> _Traits; 72 73 public: 74 typedef _Iterator iterator_type; 75 typedef typename _Traits::iterator_category iterator_category; 76 typedef typename _Traits::value_type value_type; 77 typedef typename _Traits::difference_type difference_type; 78 typedef typename _Traits::reference reference; 79 typedef typename _Traits::pointer pointer; 80 81 /// @post the iterator is singular and unattached 82 _Safe_local_iterator() : _M_current() { } 83 84 /** 85 * @brief Safe iterator construction from an unsafe iterator and 86 * its sequence. 87 * 88 * @pre @p seq is not NULL 89 * @post this is not singular 90 */ 91 _Safe_local_iterator(const _Iterator& __i, size_type __bucket, 92 const _Sequence* __seq) 93 : _Safe_local_iterator_base(__seq, _M_constant()), _M_current(__i), 94 _M_bucket(__bucket) 95 { 96 _GLIBCXX_DEBUG_VERIFY(!this->_M_singular(), 97 _M_message(__msg_init_singular) 98 ._M_iterator(*this, "this")); 99 } 100 101 /** 102 * @brief Copy construction. 103 */ 104 _Safe_local_iterator(const _Safe_local_iterator& __x) 105 : _Safe_local_iterator_base(__x, _M_constant()), 106 _M_current(__x._M_current), _M_bucket(__x._M_bucket) 107 { 108 // _GLIBCXX_RESOLVE_LIB_DEFECTS 109 // DR 408. Is vector<reverse_iterator<char*> > forbidden? 110 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 111 || __x._M_current == _Iterator(), 112 _M_message(__msg_init_copy_singular) 113 ._M_iterator(*this, "this") 114 ._M_iterator(__x, "other")); 115 } 116 117 /** 118 * @brief Converting constructor from a mutable iterator to a 119 * constant iterator. 120 */ 121 template<typename _MutableIterator> 122 _Safe_local_iterator( 123 const _Safe_local_iterator<_MutableIterator, 124 typename __gnu_cxx::__enable_if<std::__are_same< 125 _MutableIterator, 126 typename _Sequence::local_iterator::iterator_type>::__value, 127 _Sequence>::__type>& __x) 128 : _Safe_local_iterator_base(__x, _M_constant()), 129 _M_current(__x.base()), _M_bucket(__x._M_bucket) 130 { 131 // _GLIBCXX_RESOLVE_LIB_DEFECTS 132 // DR 408. Is vector<reverse_iterator<char*> > forbidden? 133 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 134 || __x.base() == _Iterator(), 135 _M_message(__msg_init_const_singular) 136 ._M_iterator(*this, "this") 137 ._M_iterator(__x, "other")); 138 } 139 140 /** 141 * @brief Copy assignment. 142 */ 143 _Safe_local_iterator& 144 operator=(const _Safe_local_iterator& __x) 145 { 146 // _GLIBCXX_RESOLVE_LIB_DEFECTS 147 // DR 408. Is vector<reverse_iterator<char*> > forbidden? 148 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 149 || __x._M_current == _Iterator(), 150 _M_message(__msg_copy_singular) 151 ._M_iterator(*this, "this") 152 ._M_iterator(__x, "other")); 153 _M_current = __x._M_current; 154 _M_bucket = __x._M_bucket; 155 this->_M_attach(__x._M_sequence); 156 return *this; 157 } 158 159 /** 160 * @brief Iterator dereference. 161 * @pre iterator is dereferenceable 162 */ 163 reference 164 operator*() const 165 { 166 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(), 167 _M_message(__msg_bad_deref) 168 ._M_iterator(*this, "this")); 169 return *_M_current; 170 } 171 172 /** 173 * @brief Iterator dereference. 174 * @pre iterator is dereferenceable 175 * @todo Make this correct w.r.t. iterators that return proxies 176 * @todo Use addressof() instead of & operator 177 */ 178 pointer 179 operator->() const 180 { 181 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(), 182 _M_message(__msg_bad_deref) 183 ._M_iterator(*this, "this")); 184 return &*_M_current; 185 } 186 187 // ------ Input iterator requirements ------ 188 /** 189 * @brief Iterator preincrement 190 * @pre iterator is incrementable 191 */ 192 _Safe_local_iterator& 193 operator++() 194 { 195 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(), 196 _M_message(__msg_bad_inc) 197 ._M_iterator(*this, "this")); 198 ++_M_current; 199 return *this; 200 } 201 202 /** 203 * @brief Iterator postincrement 204 * @pre iterator is incrementable 205 */ 206 _Safe_local_iterator 207 operator++(int) 208 { 209 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(), 210 _M_message(__msg_bad_inc) 211 ._M_iterator(*this, "this")); 212 _Safe_local_iterator __tmp(*this); 213 ++_M_current; 214 return __tmp; 215 } 216 217 // ------ Utilities ------ 218 /** 219 * @brief Return the underlying iterator 220 */ 221 _Iterator 222 base() const { return _M_current; } 223 224 /** 225 * @brief Return the bucket 226 */ 227 size_type 228 bucket() const { return _M_bucket; } 229 230 /** 231 * @brief Conversion to underlying non-debug iterator to allow 232 * better interaction with non-debug containers. 233 */ 234 operator _Iterator() const { return _M_current; } 235 236 /** Attach iterator to the given sequence. */ 237 void 238 _M_attach(_Safe_sequence_base* __seq) 239 { _Safe_iterator_base::_M_attach(__seq, _M_constant()); } 240 241 /** Likewise, but not thread-safe. */ 242 void 243 _M_attach_single(_Safe_sequence_base* __seq) 244 { _Safe_iterator_base::_M_attach_single(__seq, _M_constant()); } 245 246 /// Is the iterator dereferenceable? 247 bool 248 _M_dereferenceable() const 249 { return !this->_M_singular() && !_M_is_end(); } 250 251 /// Is the iterator incrementable? 252 bool 253 _M_incrementable() const 254 { return !this->_M_singular() && !_M_is_end(); } 255 256 // Is the iterator range [*this, __rhs) valid? 257 template<typename _Other> 258 bool 259 _M_valid_range(const _Safe_local_iterator<_Other, 260 _Sequence>& __rhs) const; 261 262 // The sequence this iterator references. 263 const _Sequence* 264 _M_get_sequence() const 265 { return static_cast<const _Sequence*>(_M_sequence); } 266 267 /// Is this iterator equal to the sequence's begin() iterator? 268 bool _M_is_begin() const 269 { return base() == _M_get_sequence()->_M_base().begin(_M_bucket); } 270 271 /// Is this iterator equal to the sequence's end() iterator? 272 bool _M_is_end() const 273 { return base() == _M_get_sequence()->_M_base().end(_M_bucket); } 274 275 /// Is this iterator part of the same bucket as the other one? 276 template <typename _Other> 277 bool _M_in_same_bucket(const _Safe_local_iterator<_Other, 278 _Sequence>& __other) const 279 { return _M_bucket == __other.bucket(); } 280 }; 281 282 template<typename _IteratorL, typename _IteratorR, typename _Sequence> 283 inline bool 284 operator==(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs, 285 const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs) 286 { 287 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 288 _M_message(__msg_iter_compare_bad) 289 ._M_iterator(__lhs, "lhs") 290 ._M_iterator(__rhs, "rhs")); 291 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 292 _M_message(__msg_compare_different) 293 ._M_iterator(__lhs, "lhs") 294 ._M_iterator(__rhs, "rhs")); 295 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 296 _M_message(__msg_compare_different) 297 ._M_iterator(__lhs, "lhs") 298 ._M_iterator(__rhs, "rhs")); 299 _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs), 300 _M_message(__msg_local_iter_compare_bad) 301 ._M_iterator(__lhs, "lhs") 302 ._M_iterator(__rhs, "rhs")); 303 return __lhs.base() == __rhs.base(); 304 } 305 306 template<typename _Iterator, typename _Sequence> 307 inline bool 308 operator==(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs, 309 const _Safe_local_iterator<_Iterator, _Sequence>& __rhs) 310 { 311 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 312 _M_message(__msg_iter_compare_bad) 313 ._M_iterator(__lhs, "lhs") 314 ._M_iterator(__rhs, "rhs")); 315 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 316 _M_message(__msg_compare_different) 317 ._M_iterator(__lhs, "lhs") 318 ._M_iterator(__rhs, "rhs")); 319 _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs), 320 _M_message(__msg_local_iter_compare_bad) 321 ._M_iterator(__lhs, "lhs") 322 ._M_iterator(__rhs, "rhs")); 323 return __lhs.base() == __rhs.base(); 324 } 325 326 template<typename _IteratorL, typename _IteratorR, typename _Sequence> 327 inline bool 328 operator!=(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs, 329 const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs) 330 { 331 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 332 _M_message(__msg_iter_compare_bad) 333 ._M_iterator(__lhs, "lhs") 334 ._M_iterator(__rhs, "rhs")); 335 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 336 _M_message(__msg_compare_different) 337 ._M_iterator(__lhs, "lhs") 338 ._M_iterator(__rhs, "rhs")); 339 _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs), 340 _M_message(__msg_local_iter_compare_bad) 341 ._M_iterator(__lhs, "lhs") 342 ._M_iterator(__rhs, "rhs")); 343 return __lhs.base() != __rhs.base(); 344 } 345 346 template<typename _Iterator, typename _Sequence> 347 inline bool 348 operator!=(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs, 349 const _Safe_local_iterator<_Iterator, _Sequence>& __rhs) 350 { 351 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 352 _M_message(__msg_iter_compare_bad) 353 ._M_iterator(__lhs, "lhs") 354 ._M_iterator(__rhs, "rhs")); 355 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 356 _M_message(__msg_compare_different) 357 ._M_iterator(__lhs, "lhs") 358 ._M_iterator(__rhs, "rhs")); 359 _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs), 360 _M_message(__msg_local_iter_compare_bad) 361 ._M_iterator(__lhs, "lhs") 362 ._M_iterator(__rhs, "rhs")); 363 return __lhs.base() != __rhs.base(); 364 } 365 } // namespace __gnu_debug 366 367 #include <debug/safe_local_iterator.tcc> 368 369 #endif 370