1 // Safe iterator implementation -*- C++ -*- 2 3 // Copyright (C) 2011-2018 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 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 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 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 */ 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 */ 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 */ 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> 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 */ 240 pointer 241 operator->() const 242 { 243 _GLIBCXX_DEBUG_VERIFY(this->_M_dereferenceable(), 244 _M_message(__msg_bad_deref) 245 ._M_iterator(*this, "this")); 246 return base().operator->(); 247 } 248 249 // ------ Input iterator requirements ------ 250 /** 251 * @brief Iterator preincrement 252 * @pre iterator is incrementable 253 */ 254 _Safe_local_iterator& 255 operator++() 256 { 257 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(), 258 _M_message(__msg_bad_inc) 259 ._M_iterator(*this, "this")); 260 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 261 ++base(); 262 return *this; 263 } 264 265 /** 266 * @brief Iterator postincrement 267 * @pre iterator is incrementable 268 */ 269 _Safe_local_iterator 270 operator++(int) 271 { 272 _GLIBCXX_DEBUG_VERIFY(this->_M_incrementable(), 273 _M_message(__msg_bad_inc) 274 ._M_iterator(*this, "this")); 275 __gnu_cxx::__scoped_lock __l(this->_M_get_mutex()); 276 return _Safe_local_iterator(base()++, this->_M_sequence, 277 _Attach_single()); 278 } 279 280 // ------ Utilities ------ 281 /** 282 * @brief Return the underlying iterator 283 */ 284 _Iterator& 285 base() noexcept { return *this; } 286 287 const _Iterator& 288 base() const noexcept { return *this; } 289 290 /** 291 * @brief Return the bucket 292 */ 293 size_type 294 bucket() const { return base()._M_get_bucket(); } 295 296 /** 297 * @brief Conversion to underlying non-debug iterator to allow 298 * better interaction with non-debug containers. 299 */ 300 operator _Iterator() const { return *this; } 301 302 /** Attach iterator to the given sequence. */ 303 void 304 _M_attach(_Safe_sequence_base* __seq) 305 { _Safe_base::_M_attach(__seq, _M_constant()); } 306 307 /** Likewise, but not thread-safe. */ 308 void 309 _M_attach_single(_Safe_sequence_base* __seq) 310 { _Safe_base::_M_attach_single(__seq, _M_constant()); } 311 312 /// Is the iterator dereferenceable? 313 bool 314 _M_dereferenceable() const 315 { return !this->_M_singular() && !_M_is_end(); } 316 317 /// Is the iterator incrementable? 318 bool 319 _M_incrementable() const 320 { return !this->_M_singular() && !_M_is_end(); } 321 322 // Is the iterator range [*this, __rhs) valid? 323 bool 324 _M_valid_range(const _Safe_local_iterator& __rhs, 325 std::pair<difference_type, 326 _Distance_precision>& __dist_info) const; 327 328 // The sequence this iterator references. 329 typename 330 __gnu_cxx::__conditional_type<std::__are_same<_Const_local_iterator, 331 _Safe_local_iterator>::__value, 332 const _Sequence*, 333 _Sequence*>::__type 334 _M_get_sequence() const 335 { return static_cast<_Sequence*>(_M_sequence); } 336 337 /// Is this iterator equal to the sequence's begin(bucket) iterator? 338 bool _M_is_begin() const 339 { return base() == _M_get_sequence()->_M_base().begin(bucket()); } 340 341 /// Is this iterator equal to the sequence's end(bucket) iterator? 342 bool _M_is_end() const 343 { return base() == _M_get_sequence()->_M_base().end(bucket()); } 344 345 /// Is this iterator part of the same bucket as the other one? 346 template<typename _Other> 347 bool 348 _M_in_same_bucket(const _Safe_local_iterator<_Other, 349 _Sequence>& __other) const 350 { return bucket() == __other.bucket(); } 351 }; 352 353 template<typename _IteratorL, typename _IteratorR, typename _Sequence> 354 inline bool 355 operator==(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs, 356 const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs) 357 { 358 _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(), 359 _M_message(__msg_iter_compare_bad) 360 ._M_iterator(__lhs, "lhs") 361 ._M_iterator(__rhs, "rhs")); 362 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 363 _M_message(__msg_compare_different) 364 ._M_iterator(__lhs, "lhs") 365 ._M_iterator(__rhs, "rhs")); 366 _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs), 367 _M_message(__msg_local_iter_compare_bad) 368 ._M_iterator(__lhs, "lhs") 369 ._M_iterator(__rhs, "rhs")); 370 return __lhs.base() == __rhs.base(); 371 } 372 373 template<typename _Iterator, typename _Sequence> 374 inline bool 375 operator==(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs, 376 const _Safe_local_iterator<_Iterator, _Sequence>& __rhs) 377 { 378 _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(), 379 _M_message(__msg_iter_compare_bad) 380 ._M_iterator(__lhs, "lhs") 381 ._M_iterator(__rhs, "rhs")); 382 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 383 _M_message(__msg_compare_different) 384 ._M_iterator(__lhs, "lhs") 385 ._M_iterator(__rhs, "rhs")); 386 _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs), 387 _M_message(__msg_local_iter_compare_bad) 388 ._M_iterator(__lhs, "lhs") 389 ._M_iterator(__rhs, "rhs")); 390 return __lhs.base() == __rhs.base(); 391 } 392 393 template<typename _IteratorL, typename _IteratorR, typename _Sequence> 394 inline bool 395 operator!=(const _Safe_local_iterator<_IteratorL, _Sequence>& __lhs, 396 const _Safe_local_iterator<_IteratorR, _Sequence>& __rhs) 397 { 398 _GLIBCXX_DEBUG_VERIFY(! __lhs._M_singular() && ! __rhs._M_singular(), 399 _M_message(__msg_iter_compare_bad) 400 ._M_iterator(__lhs, "lhs") 401 ._M_iterator(__rhs, "rhs")); 402 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 403 _M_message(__msg_compare_different) 404 ._M_iterator(__lhs, "lhs") 405 ._M_iterator(__rhs, "rhs")); 406 _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs), 407 _M_message(__msg_local_iter_compare_bad) 408 ._M_iterator(__lhs, "lhs") 409 ._M_iterator(__rhs, "rhs")); 410 return __lhs.base() != __rhs.base(); 411 } 412 413 template<typename _Iterator, typename _Sequence> 414 inline bool 415 operator!=(const _Safe_local_iterator<_Iterator, _Sequence>& __lhs, 416 const _Safe_local_iterator<_Iterator, _Sequence>& __rhs) 417 { 418 _GLIBCXX_DEBUG_VERIFY(!__lhs._M_singular() && !__rhs._M_singular(), 419 _M_message(__msg_iter_compare_bad) 420 ._M_iterator(__lhs, "lhs") 421 ._M_iterator(__rhs, "rhs")); 422 _GLIBCXX_DEBUG_VERIFY(__lhs._M_can_compare(__rhs), 423 _M_message(__msg_compare_different) 424 ._M_iterator(__lhs, "lhs") 425 ._M_iterator(__rhs, "rhs")); 426 _GLIBCXX_DEBUG_VERIFY(__lhs._M_in_same_bucket(__rhs), 427 _M_message(__msg_local_iter_compare_bad) 428 ._M_iterator(__lhs, "lhs") 429 ._M_iterator(__rhs, "rhs")); 430 return __lhs.base() != __rhs.base(); 431 } 432 433 /** Safe local iterators know if they are dereferenceable. */ 434 template<typename _Iterator, typename _Sequence> 435 inline bool 436 __check_dereferenceable(const _Safe_local_iterator<_Iterator, 437 _Sequence>& __x) 438 { return __x._M_dereferenceable(); } 439 440 /** Safe local iterators know how to check if they form a valid range. */ 441 template<typename _Iterator, typename _Sequence> 442 inline bool 443 __valid_range(const _Safe_local_iterator<_Iterator, _Sequence>& __first, 444 const _Safe_local_iterator<_Iterator, _Sequence>& __last, 445 typename _Distance_traits<_Iterator>::__type& __dist_info) 446 { return __first._M_valid_range(__last, __dist_info); } 447 448 /** Safe local iterators need a special method to get distance between each 449 other. */ 450 template<typename _Iterator, typename _Sequence> 451 inline std::pair<typename std::iterator_traits<_Iterator>::difference_type, 452 _Distance_precision> 453 __get_distance(const _Safe_local_iterator<_Iterator, _Sequence>& __first, 454 const _Safe_local_iterator<_Iterator, _Sequence>& __last, 455 std::input_iterator_tag) 456 { 457 if (__first.base() == __last.base()) 458 return { 0, __dp_exact }; 459 460 if (__first._M_is_begin()) 461 { 462 if (__last._M_is_end()) 463 return 464 { 465 __first._M_get_sequence()->bucket_size(__first.bucket()), 466 __dp_exact 467 }; 468 469 return { 1, __dp_sign }; 470 } 471 472 if (__first._M_is_end()) 473 { 474 if (__last._M_is_begin()) 475 return 476 { 477 -__first._M_get_sequence()->bucket_size(__first.bucket()), 478 __dp_exact 479 }; 480 481 return { -1, __dp_sign }; 482 } 483 484 if (__last._M_is_begin()) 485 return { -1, __dp_sign }; 486 487 if (__last._M_is_end()) 488 return { 1, __dp_sign }; 489 490 return { 1, __dp_equality }; 491 } 492 493 #if __cplusplus < 201103L 494 template<typename _Iterator, typename _Sequence> 495 struct _Unsafe_type<_Safe_local_iterator<_Iterator, _Sequence> > 496 { typedef _Iterator _Type; }; 497 #endif 498 499 template<typename _Iterator, typename _Sequence> 500 inline _Iterator 501 __unsafe(const _Safe_local_iterator<_Iterator, _Sequence>& __it) 502 { return __it.base(); } 503 504 } // namespace __gnu_debug 505 506 #include <debug/safe_local_iterator.tcc> 507 508 #endif 509