1 // Safe iterator implementation -*- C++ -*- 2 3 // Copyright (C) 2011-2016 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/safe_unordered_base.h> 33 34 namespace __gnu_debug 35 { 36 /** \brief Safe iterator wrapper. 37 * 38 * The class template %_Safe_local_iterator is a wrapper around an 39 * iterator that tracks the iterator's movement among sequences and 40 * checks that operations performed on the "safe" iterator are 41 * legal. In additional to the basic iterator operations (which are 42 * validated, and then passed to the underlying iterator), 43 * %_Safe_local_iterator has member functions for iterator invalidation, 44 * attaching/detaching the iterator from sequences, and querying 45 * the iterator's state. 46 */ 47 template<typename _Iterator, typename _Sequence> 48 class _Safe_local_iterator 49 : private _Iterator 50 , public _Safe_local_iterator_base 51 { 52 typedef _Iterator _Iter_base; 53 typedef _Safe_local_iterator_base _Safe_base; 54 typedef typename _Sequence::const_local_iterator _Const_local_iterator; 55 typedef typename _Sequence::size_type size_type; 56 57 /// Determine if this is a constant iterator. 58 bool _M_constant()59 _M_constant() const 60 { 61 return std::__are_same<_Const_local_iterator, 62 _Safe_local_iterator>::__value; 63 } 64 65 typedef std::iterator_traits<_Iterator> _Traits; 66 67 struct _Attach_single 68 { }; 69 _Safe_local_iterator(const _Iterator & __i,_Safe_sequence_base * __cont,_Attach_single)70 _Safe_local_iterator(const _Iterator& __i, _Safe_sequence_base* __cont, 71 _Attach_single) noexcept 72 : _Iter_base(__i) 73 { _M_attach_single(__cont); } 74 75 public: 76 typedef _Iterator iterator_type; 77 typedef typename _Traits::iterator_category iterator_category; 78 typedef typename _Traits::value_type value_type; 79 typedef typename _Traits::difference_type difference_type; 80 typedef typename _Traits::reference reference; 81 typedef typename _Traits::pointer pointer; 82 83 /// @post the iterator is singular and unattached _Safe_local_iterator()84 _Safe_local_iterator() noexcept : _Iter_base() { } 85 86 /** 87 * @brief Safe iterator construction from an unsafe iterator and 88 * its sequence. 89 * 90 * @pre @p seq is not NULL 91 * @post this is not singular 92 */ _Safe_local_iterator(const _Iterator & __i,const _Safe_sequence_base * __cont)93 _Safe_local_iterator(const _Iterator& __i, 94 const _Safe_sequence_base* __cont) 95 : _Iter_base(__i), _Safe_base(__cont, _M_constant()) 96 { 97 _GLIBCXX_DEBUG_VERIFY(!this->_M_singular(), 98 _M_message(__msg_init_singular) 99 ._M_iterator(*this, "this")); 100 } 101 102 /** 103 * @brief Copy construction. 104 */ _Safe_local_iterator(const _Safe_local_iterator & __x)105 _Safe_local_iterator(const _Safe_local_iterator& __x) noexcept 106 : _Iter_base(__x.base()) 107 { 108 // _GLIBCXX_RESOLVE_LIB_DEFECTS 109 // DR 408. Is vector<reverse_iterator<char*> > forbidden? 110 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 111 || __x.base() == _Iterator(), 112 _M_message(__msg_init_copy_singular) 113 ._M_iterator(*this, "this") 114 ._M_iterator(__x, "other")); 115 _M_attach(__x._M_sequence); 116 } 117 118 /** 119 * @brief Move construction. 120 * @post __x is singular and unattached 121 */ _Safe_local_iterator(_Safe_local_iterator && __x)122 _Safe_local_iterator(_Safe_local_iterator&& __x) noexcept 123 : _Iter_base() 124 { 125 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 126 || __x.base() == _Iterator(), 127 _M_message(__msg_init_copy_singular) 128 ._M_iterator(*this, "this") 129 ._M_iterator(__x, "other")); 130 auto __cont = __x._M_sequence; 131 __x._M_detach(); 132 std::swap(base(), __x.base()); 133 _M_attach(__cont); 134 } 135 136 /** 137 * @brief Converting constructor from a mutable iterator to a 138 * constant iterator. 139 */ 140 template<typename _MutableIterator> _Safe_local_iterator(const _Safe_local_iterator<_MutableIterator,typename __gnu_cxx::__enable_if<std::__are_same<_MutableIterator,typename _Sequence::local_iterator::iterator_type>::__value,_Sequence>::__type> & __x)141 _Safe_local_iterator( 142 const _Safe_local_iterator<_MutableIterator, 143 typename __gnu_cxx::__enable_if<std::__are_same< 144 _MutableIterator, 145 typename _Sequence::local_iterator::iterator_type>::__value, 146 _Sequence>::__type>& __x) 147 : _Iter_base(__x.base()) 148 { 149 // _GLIBCXX_RESOLVE_LIB_DEFECTS 150 // DR 408. Is vector<reverse_iterator<char*> > forbidden? 151 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 152 || __x.base() == _Iterator(), 153 _M_message(__msg_init_const_singular) 154 ._M_iterator(*this, "this") 155 ._M_iterator(__x, "other")); 156 _M_attach(__x._M_sequence); 157 } 158 159 /** 160 * @brief Copy assignment. 161 */ 162 _Safe_local_iterator& 163 operator=(const _Safe_local_iterator& __x) 164 { 165 // _GLIBCXX_RESOLVE_LIB_DEFECTS 166 // DR 408. Is vector<reverse_iterator<char*> > forbidden? 167 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 168 || __x.base() == _Iterator(), 169 _M_message(__msg_copy_singular) 170 ._M_iterator(*this, "this") 171 ._M_iterator(__x, "other")); 172 173 if (this->_M_sequence && this->_M_sequence == __x._M_sequence) 174 { 175 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 176 base() = __x.base(); 177 _M_version = __x._M_sequence->_M_version; 178 } 179 else 180 { 181 _M_detach(); 182 base() = __x.base(); 183 _M_attach(__x._M_sequence); 184 } 185 186 return *this; 187 } 188 189 /** 190 * @brief Move assignment. 191 * @post __x is singular and unattached 192 */ 193 _Safe_local_iterator& 194 operator=(_Safe_local_iterator&& __x) noexcept 195 { 196 _GLIBCXX_DEBUG_VERIFY(this != &__x, 197 _M_message(__msg_self_move_assign) 198 ._M_iterator(*this, "this")); 199 _GLIBCXX_DEBUG_VERIFY(!__x._M_singular() 200 || __x.base() == _Iterator(), 201 _M_message(__msg_copy_singular) 202 ._M_iterator(*this, "this") 203 ._M_iterator(__x, "other")); 204 205 if (this->_M_sequence && this->_M_sequence == __x._M_sequence) 206 { 207 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 208 base() = __x.base(); 209 _M_version = __x._M_sequence->_M_version; 210 } 211 else 212 { 213 _M_detach(); 214 base() = __x.base(); 215 _M_attach(__x._M_sequence); 216 } 217 218 __x._M_detach(); 219 __x.base() = _Iterator(); 220 return *this; 221 } 222 223 /** 224 * @brief Iterator dereference. 225 * @pre iterator is dereferenceable 226 */ 227 reference 228 operator*() const 229 { 230 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(), 231 _M_message(__msg_bad_deref) 232 ._M_iterator(*this, "this")); 233 return *base(); 234 } 235 236 /** 237 * @brief Iterator dereference. 238 * @pre iterator is dereferenceable 239 * @todo Make this correct w.r.t. iterators that return proxies 240 */ 241 pointer 242 operator->() const 243 { 244 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(), 245 _M_message(__msg_bad_deref) 246 ._M_iterator(*this, "this")); 247 return std::__addressof(*base()); 248 } 249 250 // ------ Input iterator requirements ------ 251 /** 252 * @brief Iterator preincrement 253 * @pre iterator is incrementable 254 */ 255 _Safe_local_iterator& 256 operator++() 257 { 258 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(), 259 _M_message(__msg_bad_inc) 260 ._M_iterator(*this, "this")); 261 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 262 ++base(); 263 return *this; 264 } 265 266 /** 267 * @brief Iterator postincrement 268 * @pre iterator is incrementable 269 */ 270 _Safe_local_iterator 271 operator++(int) 272 { 273 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(), 274 _M_message(__msg_bad_inc) 275 ._M_iterator(*this, "this")); 276 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 277 return _Safe_local_iterator(base()++, this->_M_sequence, 278 _Attach_single()); 279 } 280 281 // ------ Utilities ------ 282 /** 283 * @brief Return the underlying iterator 284 */ 285 _Iterator& base()286 base() noexcept { return *this; } 287 288 const _Iterator& base()289 base() const noexcept { return *this; } 290 291 /** 292 * @brief Return the bucket 293 */ 294 size_type bucket()295 bucket() const { return base()._M_get_bucket(); } 296 297 /** 298 * @brief Conversion to underlying non-debug iterator to allow 299 * better interaction with non-debug containers. 300 */ _Iterator()301 operator _Iterator() const { return *this; } 302 303 /** Attach iterator to the given sequence. */ 304 void _M_attach(_Safe_sequence_base * __seq)305 _M_attach(_Safe_sequence_base* __seq) 306 { _Safe_base::_M_attach(__seq, _M_constant()); } 307 308 /** Likewise, but not thread-safe. */ 309 void _M_attach_single(_Safe_sequence_base * __seq)310 _M_attach_single(_Safe_sequence_base* __seq) 311 { _Safe_base::_M_attach_single(__seq, _M_constant()); } 312 313 /// Is the iterator dereferenceable? 314 bool _M_dereferenceable()315 _M_dereferenceable() const 316 { return !this->_M_singular() && !_M_is_end(); } 317 318 /// Is the iterator incrementable? 319 bool _M_incrementable()320 _M_incrementable() const 321 { return !this->_M_singular() && !_M_is_end(); } 322 323 // Is the iterator range [*this, __rhs) valid? 324 bool 325 _M_valid_range(const _Safe_local_iterator& __rhs, 326 std::pair<difference_type, 327 _Distance_precision>& __dist_info) const; 328 329 // The sequence this iterator references. 330 typename 331 __gnu_cxx::__conditional_type<std::__are_same<_Const_local_iterator, 332 _Safe_local_iterator>::__value, 333 const _Sequence*, 334 _Sequence*>::__type _M_get_sequence()335 _M_get_sequence() const 336 { return static_cast<_Sequence*>(_M_sequence); } 337 338 /// Is this iterator equal to the sequence's begin(bucket) iterator? _M_is_begin()339 bool _M_is_begin() const 340 { return base() == _M_get_sequence()->_M_base().begin(bucket()); } 341 342 /// Is this iterator equal to the sequence's end(bucket) iterator? _M_is_end()343 bool _M_is_end() const 344 { return base() == _M_get_sequence()->_M_base().end(bucket()); } 345 346 /// Is this iterator part of the same bucket as the other one? 347 template<typename _Other> 348 bool _M_in_same_bucket(const _Safe_local_iterator<_Other,_Sequence> & __other)349 _M_in_same_bucket(const _Safe_local_iterator<_Other, 350 _Sequence>& __other) const 351 { return bucket() == __other.bucket(); } 352 }; 353 354 template<typename _IteratorL, typename _IteratorR, typename _Sequence> 355 inline bool 356 operator==(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs, 357 const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs) 358 { 359 _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(), 360 _M_message(__msg_iter_compare_bad) 361 ._M_iterator(__lhs, "lhs") 362 ._M_iterator(__rhs, "rhs")); 363 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 364 _M_message(__msg_compare_different) 365 ._M_iterator(__lhs, "lhs") 366 ._M_iterator(__rhs, "rhs")); 367 _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs), 368 _M_message(__msg_local_iter_compare_bad) 369 ._M_iterator(__lhs, "lhs") 370 ._M_iterator(__rhs, "rhs")); 371 return __lhs.base() == __rhs.base(); 372 } 373 374 template<typename _Iterator, typename _Sequence> 375 inline bool 376 operator==(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs, 377 const _Safe_local_iterator<_Iterator, _Sequence>& __rhs) 378 { 379 _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(), 380 _M_message(__msg_iter_compare_bad) 381 ._M_iterator(__lhs, "lhs") 382 ._M_iterator(__rhs, "rhs")); 383 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 384 _M_message(__msg_compare_different) 385 ._M_iterator(__lhs, "lhs") 386 ._M_iterator(__rhs, "rhs")); 387 _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs), 388 _M_message(__msg_local_iter_compare_bad) 389 ._M_iterator(__lhs, "lhs") 390 ._M_iterator(__rhs, "rhs")); 391 return __lhs.base() == __rhs.base(); 392 } 393 394 template<typename _IteratorL, typename _IteratorR, typename _Sequence> 395 inline bool 396 operator!=(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs, 397 const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs) 398 { 399 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 400 _M_message(__msg_iter_compare_bad) 401 ._M_iterator(__lhs, "lhs") 402 ._M_iterator(__rhs, "rhs")); 403 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 404 _M_message(__msg_compare_different) 405 ._M_iterator(__lhs, "lhs") 406 ._M_iterator(__rhs, "rhs")); 407 _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs), 408 _M_message(__msg_local_iter_compare_bad) 409 ._M_iterator(__lhs, "lhs") 410 ._M_iterator(__rhs, "rhs")); 411 return __lhs.base() != __rhs.base(); 412 } 413 414 template<typename _Iterator, typename _Sequence> 415 inline bool 416 operator!=(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs, 417 const _Safe_local_iterator<_Iterator, _Sequence>& __rhs) 418 { 419 _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(), 420 _M_message(__msg_iter_compare_bad) 421 ._M_iterator(__lhs, "lhs") 422 ._M_iterator(__rhs, "rhs")); 423 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 424 _M_message(__msg_compare_different) 425 ._M_iterator(__lhs, "lhs") 426 ._M_iterator(__rhs, "rhs")); 427 _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs), 428 _M_message(__msg_local_iter_compare_bad) 429 ._M_iterator(__lhs, "lhs") 430 ._M_iterator(__rhs, "rhs")); 431 return __lhs.base() != __rhs.base(); 432 } 433 434 /** Safe local iterators know if they are dereferenceable. */ 435 template<typename _Iterator, typename _Sequence> 436 inline bool __check_dereferenceable(const _Safe_local_iterator<_Iterator,_Sequence> & __x)437 __check_dereferenceable(const _Safe_local_iterator<_Iterator, 438 _Sequence>& __x) 439 { return __x._M_dereferenceable(); } 440 441 /** Safe local iterators know how to check if they form a valid range. */ 442 template<typename _Iterator, typename _Sequence> 443 inline bool __valid_range(const _Safe_local_iterator<_Iterator,_Sequence> & __first,const _Safe_local_iterator<_Iterator,_Sequence> & __last,typename _Distance_traits<_Iterator>::__type & __dist_info)444 __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first, 445 const _Safe_local_iterator<_Iterator, _Sequence>& __last, 446 typename _Distance_traits<_Iterator>::__type& __dist_info) 447 { return __first._M_valid_range(__last, __dist_info); } 448 449 /** Safe local iterators need a special method to get distance between each 450 other. */ 451 template<typename _Iterator, typename _Sequence> 452 inline std::pair<typename std::iterator_traits<_Iterator>::difference_type, 453 _Distance_precision> __get_distance(const _Safe_local_iterator<_Iterator,_Sequence> & __first,const _Safe_local_iterator<_Iterator,_Sequence> & __last,std::input_iterator_tag)454 __get_distance(const _Safe_local_iterator<_Iterator, _Sequence>& __first, 455 const _Safe_local_iterator<_Iterator, _Sequence>& __last, 456 std::input_iterator_tag) 457 { 458 if (__first.base() == __last.base()) 459 return { 0, __dp_exact }; 460 461 if (__first._M_is_begin()) 462 { 463 if (__last._M_is_end()) 464 return 465 { 466 __first._M_get_sequence()->bucket_size(__first.bucket()), 467 __dp_exact 468 }; 469 470 return { 1, __dp_sign }; 471 } 472 473 if (__first._M_is_end()) 474 { 475 if (__last._M_is_begin()) 476 return 477 { 478 -__first._M_get_sequence()->bucket_size(__first.bucket()), 479 __dp_exact 480 }; 481 482 return { -1, __dp_sign }; 483 } 484 485 if (__last._M_is_begin()) 486 return { -1, __dp_sign }; 487 488 if (__last._M_is_end()) 489 return { 1, __dp_sign }; 490 491 return { 1, __dp_equality }; 492 } 493 494 #if __cplusplus < 201103L 495 template<typename _Iterator, typename _Sequence> 496 struct _Unsafe_type<_Safe_local_iterator<_Iterator, _Sequence> > 497 { typedef _Iterator _Type; }; 498 #endif 499 500 template<typename _Iterator, typename _Sequence> 501 inline _Iterator 502 __unsafe(const _Safe_local_iterator<_Iterator, _Sequence>& __it) 503 { return __it.base(); } 504 505 } // namespace __gnu_debug 506 507 #include <debug/safe_local_iterator.tcc> 508 509 #endif 510