1 // Debugging iterator implementation (out of line) -*- C++ -*- 2 3 // Copyright (C) 2003-2022 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_iterator.tcc 26 * This file is a GNU debug extension to the Standard C++ Library. 27 */ 28 29 #ifndef _GLIBCXX_DEBUG_SAFE_ITERATOR_TCC 30 #define _GLIBCXX_DEBUG_SAFE_ITERATOR_TCC 1 31 32 #include <bits/stl_algobase.h> 33 34 namespace __gnu_debug 35 { 36 template<typename _Iterator, typename _Sequence, typename _Category> 37 typename _Distance_traits<_Iterator>::__type 38 _Safe_iterator<_Iterator, _Sequence, _Category>:: 39 _M_get_distance_from_begin() const 40 { 41 typedef _Sequence_traits<_Sequence> _SeqTraits; 42 43 // No need to consider before_begin as this function is only used in 44 // _M_can_advance which won't be used for forward_list iterators. 45 if (_M_is_begin()) 46 return std::make_pair(0, __dp_exact); 47 48 if (_M_is_end()) 49 return _SeqTraits::_S_size(*_M_get_sequence()); 50 51 typename _Distance_traits<_Iterator>::__type __res 52 = __get_distance(_M_get_sequence()->_M_base().begin(), base()); 53 54 if (__res.second == __dp_equality) 55 return std::make_pair(1, __dp_sign); 56 57 return __res; 58 } 59 60 template<typename _Iterator, typename _Sequence, typename _Category> 61 typename _Distance_traits<_Iterator>::__type 62 _Safe_iterator<_Iterator, _Sequence, _Category>:: 63 _M_get_distance_to_end() const 64 { 65 typedef _Sequence_traits<_Sequence> _SeqTraits; 66 67 // No need to consider before_begin as this function is only used in 68 // _M_can_advance which won't be used for forward_list iterators. 69 if (_M_is_begin()) 70 return _SeqTraits::_S_size(*_M_get_sequence()); 71 72 if (_M_is_end()) 73 return std::make_pair(0, __dp_exact); 74 75 typename _Distance_traits<_Iterator>::__type __res 76 = __get_distance(base(), _M_get_sequence()->_M_base().end()); 77 78 if (__res.second == __dp_equality) 79 return std::make_pair(1, __dp_sign); 80 81 return __res; 82 } 83 84 template<typename _Iterator, typename _Sequence, typename _Category> 85 bool 86 _Safe_iterator<_Iterator, _Sequence, _Category>:: 87 _M_can_advance(difference_type __n, bool __strict) const 88 { 89 if (this->_M_singular()) 90 return false; 91 92 if (__n == 0) 93 return true; 94 95 std::pair<difference_type, _Distance_precision> __dist = __n < 0 96 ? _M_get_distance_from_begin() 97 : _M_get_distance_to_end(); 98 99 if (__n < 0) 100 __n = -__n; 101 102 return __dist.second > __dp_sign 103 ? __dist.first >= __n 104 : !__strict && __dist.first > 0; 105 } 106 107 template<typename _Iterator, typename _Sequence, typename _Category> 108 template<typename _Diff> 109 bool 110 _Safe_iterator<_Iterator, _Sequence, _Category>:: 111 _M_can_advance(const std::pair<_Diff, _Distance_precision>& __dist, 112 int __way) const 113 { 114 return __dist.second == __dp_exact 115 ? _M_can_advance(__way * __dist.first) 116 : _M_can_advance(__way * (__dist.first == 0 117 ? 0 118 : __dist.first < 0 ? -1 : 1)); 119 } 120 121 template<typename _Iterator, typename _Sequence, typename _Category> 122 typename _Distance_traits<_Iterator>::__type 123 _Safe_iterator<_Iterator, _Sequence, _Category>:: 124 _M_get_distance_to(const _Safe_iterator& __rhs) const 125 { 126 typedef typename _Distance_traits<_Iterator>::__type _Dist; 127 typedef _Sequence_traits<_Sequence> _SeqTraits; 128 129 _Dist __base_dist = __get_distance(this->base(), __rhs.base()); 130 if (__base_dist.second == __dp_exact) 131 return __base_dist; 132 133 _Dist __seq_dist = _SeqTraits::_S_size(*this->_M_get_sequence()); 134 if (this->_M_is_before_begin()) 135 { 136 if (__rhs._M_is_begin()) 137 return std::make_pair(1, __dp_exact); 138 139 return __seq_dist.second == __dp_exact 140 ? std::make_pair(__seq_dist.first + 1, __dp_exact) 141 : __seq_dist; 142 } 143 144 if (this->_M_is_begin()) 145 { 146 if (__rhs._M_is_before_begin()) 147 return std::make_pair(-1, __dp_exact); 148 149 if (__rhs._M_is_end()) 150 return __seq_dist; 151 152 return std::make_pair(__seq_dist.first, 153 __seq_dist.second == __dp_exact 154 ? __dp_sign_max_size : __seq_dist.second); 155 } 156 157 if (this->_M_is_end()) 158 { 159 if (__rhs._M_is_before_begin()) 160 return __seq_dist.second == __dp_exact 161 ? std::make_pair(-__seq_dist.first - 1, __dp_exact) 162 : std::make_pair(-__seq_dist.first, __dp_sign); 163 164 if (__rhs._M_is_begin()) 165 return std::make_pair(-__seq_dist.first, __seq_dist.second); 166 167 return std::make_pair(-__seq_dist.first, 168 __seq_dist.second == __dp_exact 169 ? __dp_sign_max_size : __seq_dist.second); 170 } 171 172 if (__rhs._M_is_before_begin()) 173 return __seq_dist.second == __dp_exact 174 ? std::make_pair(__seq_dist.first - 1, __dp_exact) 175 : std::make_pair(-__seq_dist.first, __dp_sign); 176 177 if (__rhs._M_is_begin()) 178 return std::make_pair(-__seq_dist.first, 179 __seq_dist.second == __dp_exact 180 ? __dp_sign_max_size : __seq_dist.second); 181 182 if (__rhs._M_is_end()) 183 return std::make_pair(__seq_dist.first, 184 __seq_dist.second == __dp_exact 185 ? __dp_sign_max_size : __seq_dist.second); 186 187 return std::make_pair(1, __dp_equality); 188 } 189 190 template<typename _Iterator, typename _Sequence, typename _Category> 191 bool 192 _Safe_iterator<_Iterator, _Sequence, _Category>:: 193 _M_valid_range(const _Safe_iterator& __rhs, 194 std::pair<difference_type, _Distance_precision>& __dist, 195 bool __check_dereferenceable) const 196 { 197 if (_M_singular() || __rhs._M_singular() || !_M_can_compare(__rhs)) 198 return false; 199 200 /* Determine iterators order */ 201 __dist = _M_get_distance_to(__rhs); 202 if (__dist.second != __dp_equality) 203 { 204 // If range is not empty first iterator must be dereferenceable. 205 return __dist.first == 0 206 || (__dist.first > 0 207 && (!__check_dereferenceable || _M_dereferenceable())); 208 } 209 210 // Assume that this is a valid range; we can't check anything else. 211 return true; 212 } 213 214 template<typename _Iterator, typename _Sequence> 215 bool 216 _Safe_iterator<_Iterator, _Sequence, std::random_access_iterator_tag>:: 217 _M_valid_range(const _Safe_iterator& __rhs, 218 std::pair<difference_type, 219 _Distance_precision>& __dist) const 220 { 221 if (this->_M_singular() || __rhs._M_singular() 222 || !this->_M_can_compare(__rhs)) 223 return false; 224 225 /* Determine iterators order */ 226 __dist = std::make_pair(__rhs.base() - this->base(), __dp_exact); 227 228 // If range is not empty first iterator must be dereferenceable. 229 return __dist.first == 0 230 || (__dist.first > 0 && this->_M_dereferenceable()); 231 } 232 } // namespace __gnu_debug 233 234 namespace std _GLIBCXX_VISIBILITY(default) 235 { 236 _GLIBCXX_BEGIN_NAMESPACE_VERSION 237 238 template<typename _Ite, typename _Seq> 239 _Ite 240 __niter_base(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, 241 std::random_access_iterator_tag>& __it) 242 { return __it.base(); } 243 244 template<bool _IsMove, 245 typename _Ite, typename _Seq, typename _Cat, typename _OI> 246 _OI 247 __copy_move_a( 248 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first, 249 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __last, 250 _OI __result) 251 { 252 typename ::__gnu_debug::_Distance_traits<_Ite>::__type __dist; 253 __glibcxx_check_valid_range2(__first, __last, __dist); 254 __glibcxx_check_can_increment_dist(__result, __dist, 1); 255 256 if (__dist.second > ::__gnu_debug::__dp_equality) 257 return std::__copy_move_a<_IsMove>(__first.base(), __last.base(), 258 __result); 259 260 return std::__copy_move_a1<_IsMove>(__first, __last, __result); 261 } 262 263 template<bool _IsMove, 264 typename _II, typename _Ite, typename _Seq, typename _Cat> 265 __gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat> 266 __copy_move_a(_II __first, _II __last, 267 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __result) 268 { 269 typename ::__gnu_debug::_Distance_traits<_II>::__type __dist; 270 __glibcxx_check_valid_range2(__first, __last, __dist); 271 __glibcxx_check_can_increment_dist(__result, __dist, 1); 272 273 if (__dist.second > ::__gnu_debug::__dp_sign 274 && __result._M_can_advance(__dist.first, true)) 275 return ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>( 276 std::__copy_move_a<_IsMove>(__first, __last, __result.base()), 277 __result._M_sequence); 278 279 return std::__copy_move_a1<_IsMove>(__first, __last, __result); 280 } 281 282 template<bool _IsMove, 283 typename _IIte, typename _ISeq, typename _ICat, 284 typename _OIte, typename _OSeq, typename _OCat> 285 ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat> 286 __copy_move_a( 287 const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>& __first, 288 const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>& __last, 289 const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>& __result) 290 { 291 typename ::__gnu_debug::_Distance_traits<_IIte>::__type __dist; 292 __glibcxx_check_valid_range2(__first, __last, __dist); 293 __glibcxx_check_can_increment_dist(__result, __dist, 1); 294 295 if (__dist.second > ::__gnu_debug::__dp_equality) 296 { 297 if (__dist.second > ::__gnu_debug::__dp_sign 298 && __result._M_can_advance(__dist.first, true)) 299 return ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>( 300 std::__copy_move_a<_IsMove>(__first.base(), __last.base(), 301 __result.base()), 302 __result._M_sequence); 303 304 return std::__copy_move_a<_IsMove>(__first.base(), __last.base(), 305 __result); 306 } 307 308 return std::__copy_move_a1<_IsMove>(__first, __last, __result); 309 } 310 311 template<bool _IsMove, 312 typename _Ite, typename _Seq, typename _Cat, typename _OI> 313 _OI 314 __copy_move_backward_a( 315 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first, 316 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __last, 317 _OI __result) 318 { 319 typename ::__gnu_debug::_Distance_traits<_Ite>::__type __dist; 320 __glibcxx_check_valid_range2(__first, __last, __dist); 321 __glibcxx_check_can_increment_dist(__result, __dist, -1); 322 323 if (__dist.second > ::__gnu_debug::__dp_equality) 324 return std::__copy_move_backward_a<_IsMove>( 325 __first.base(), __last.base(), __result); 326 327 return std::__copy_move_backward_a1<_IsMove>(__first, __last, __result); 328 } 329 330 template<bool _IsMove, 331 typename _II, typename _Ite, typename _Seq, typename _Cat> 332 __gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat> 333 __copy_move_backward_a(_II __first, _II __last, 334 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __result) 335 { 336 typename ::__gnu_debug::_Distance_traits<_II>::__type __dist; 337 __glibcxx_check_valid_range2(__first, __last, __dist); 338 __glibcxx_check_can_increment_dist(__result, __dist, -1); 339 340 if (__dist.second > ::__gnu_debug::__dp_sign 341 && __result._M_can_advance(-__dist.first, true)) 342 return ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>( 343 std::__copy_move_backward_a<_IsMove>(__first, __last, 344 __result.base()), 345 __result._M_sequence); 346 347 return std::__copy_move_backward_a1<_IsMove>(__first, __last, __result); 348 } 349 350 template<bool _IsMove, 351 typename _IIte, typename _ISeq, typename _ICat, 352 typename _OIte, typename _OSeq, typename _OCat> 353 ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat> 354 __copy_move_backward_a( 355 const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>& __first, 356 const ::__gnu_debug::_Safe_iterator<_IIte, _ISeq, _ICat>& __last, 357 const ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>& __result) 358 { 359 typename ::__gnu_debug::_Distance_traits<_IIte>::__type __dist; 360 __glibcxx_check_valid_range2(__first, __last, __dist); 361 __glibcxx_check_can_increment_dist(__result, __dist, -1); 362 363 if (__dist.second > ::__gnu_debug::__dp_equality) 364 { 365 if (__dist.second > ::__gnu_debug::__dp_sign 366 && __result._M_can_advance(-__dist.first, true)) 367 return ::__gnu_debug::_Safe_iterator<_OIte, _OSeq, _OCat>( 368 std::__copy_move_backward_a<_IsMove>(__first.base(), __last.base(), 369 __result.base()), 370 __result._M_sequence); 371 372 return std::__copy_move_backward_a<_IsMove>( 373 __first.base(), __last.base(), __result); 374 } 375 376 return std::__copy_move_backward_a1<_IsMove>(__first, __last, __result); 377 } 378 379 template<typename _Ite, typename _Seq, typename _Cat, typename _Tp> 380 void 381 __fill_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first, 382 const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __last, 383 const _Tp& __value) 384 { 385 typename ::__gnu_debug::_Distance_traits<_Ite>::__type __dist; 386 __glibcxx_check_valid_range2(__first, __last, __dist); 387 388 if (__dist.second > ::__gnu_debug::__dp_equality) 389 std::__fill_a(__first.base(), __last.base(), __value); 390 391 std::__fill_a1(__first, __last, __value); 392 } 393 394 template<typename _Ite, typename _Seq, typename _Cat, typename _Size, 395 typename _Tp> 396 ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat> 397 __fill_n_a(const ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>& __first, 398 _Size __n, const _Tp& __value, 399 std::input_iterator_tag) 400 { 401 #if __cplusplus >= 201103L 402 static_assert(is_integral<_Size>{}, "fill_n must pass integral size"); 403 #endif 404 405 if (__n <= 0) 406 return __first; 407 408 __glibcxx_check_can_increment(__first, __n); 409 if (__first._M_can_advance(__n, true)) 410 return ::__gnu_debug::_Safe_iterator<_Ite, _Seq, _Cat>( 411 std::__fill_n_a(__first.base(), __n, __value, _Cat()), 412 __first._M_sequence); 413 414 return std::__fill_n_a1(__first, __n, __value); 415 } 416 417 template<typename _II1, typename _Seq1, typename _Cat1, typename _II2> 418 bool 419 __equal_aux( 420 const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>& __first1, 421 const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>& __last1, 422 _II2 __first2) 423 { 424 typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist; 425 __glibcxx_check_valid_range2(__first1, __last1, __dist); 426 __glibcxx_check_can_increment_dist(__first2, __dist, 1); 427 428 if (__dist.second > ::__gnu_debug::__dp_equality) 429 return std::__equal_aux(__first1.base(), __last1.base(), __first2); 430 431 return std::__equal_aux1(__first1, __last1, __first2); 432 } 433 434 template<typename _II1, typename _II2, typename _Seq2, typename _Cat2> 435 bool 436 __equal_aux(_II1 __first1, _II1 __last1, 437 const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>& __first2) 438 { 439 typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist; 440 __glibcxx_check_valid_range2(__first1, __last1, __dist); 441 __glibcxx_check_can_increment_dist(__first2, __dist, 1); 442 443 if (__dist.second > ::__gnu_debug::__dp_sign 444 && __first2._M_can_advance(__dist.first, true)) 445 return std::__equal_aux(__first1, __last1, __first2.base()); 446 447 return std::__equal_aux1(__first1, __last1, __first2); 448 } 449 450 template<typename _II1, typename _Seq1, typename _Cat1, 451 typename _II2, typename _Seq2, typename _Cat2> 452 bool 453 __equal_aux( 454 const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>& __first1, 455 const ::__gnu_debug::_Safe_iterator<_II1, _Seq1, _Cat1>& __last1, 456 const ::__gnu_debug::_Safe_iterator<_II2, _Seq2, _Cat2>& __first2) 457 { 458 typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist; 459 __glibcxx_check_valid_range2(__first1, __last1, __dist); 460 __glibcxx_check_can_increment_dist(__first2, __dist, 1); 461 462 if (__dist.second > ::__gnu_debug::__dp_equality) 463 { 464 if (__dist.second > ::__gnu_debug::__dp_sign && 465 __first2._M_can_advance(__dist.first, true)) 466 return std::__equal_aux(__first1.base(), __last1.base(), 467 __first2.base()); 468 return std::__equal_aux(__first1.base(), __last1.base(), __first2); 469 } 470 471 return __equal_aux1(__first1, __last1, __first2); 472 } 473 474 template<typename _Ite1, typename _Seq1, typename _Cat1, 475 typename _II2> 476 bool 477 __lexicographical_compare_aux( 478 const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __first1, 479 const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __last1, 480 _II2 __first2, _II2 __last2) 481 { 482 typename ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1; 483 __glibcxx_check_valid_range2(__first1, __last1, __dist1); 484 __glibcxx_check_valid_range(__first2, __last2); 485 486 if (__dist1.second > ::__gnu_debug::__dp_equality) 487 return std::__lexicographical_compare_aux(__first1.base(), 488 __last1.base(), 489 __first2, __last2); 490 return std::__lexicographical_compare_aux1(__first1, __last1, 491 __first2, __last2); 492 } 493 494 template<typename _II1, 495 typename _Ite2, typename _Seq2, typename _Cat2> 496 bool 497 __lexicographical_compare_aux( 498 _II1 __first1, _II1 __last1, 499 const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __first2, 500 const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __last2) 501 { 502 __glibcxx_check_valid_range(__first1, __last1); 503 typename ::__gnu_debug::_Distance_traits<_II1>::__type __dist2; 504 __glibcxx_check_valid_range2(__first2, __last2, __dist2); 505 506 if (__dist2.second > ::__gnu_debug::__dp_equality) 507 return std::__lexicographical_compare_aux(__first1, __last1, 508 __first2.base(), 509 __last2.base()); 510 return std::__lexicographical_compare_aux1(__first1, __last1, 511 __first2, __last2); 512 } 513 514 template<typename _Ite1, typename _Seq1, typename _Cat1, 515 typename _Ite2, typename _Seq2, typename _Cat2> 516 bool 517 __lexicographical_compare_aux( 518 const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __first1, 519 const ::__gnu_debug::_Safe_iterator<_Ite1, _Seq1, _Cat1>& __last1, 520 const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __first2, 521 const ::__gnu_debug::_Safe_iterator<_Ite2, _Seq2, _Cat2>& __last2) 522 { 523 typename ::__gnu_debug::_Distance_traits<_Ite1>::__type __dist1; 524 __glibcxx_check_valid_range2(__first1, __last1, __dist1); 525 typename ::__gnu_debug::_Distance_traits<_Ite2>::__type __dist2; 526 __glibcxx_check_valid_range2(__first2, __last2, __dist2); 527 528 if (__dist1.second > ::__gnu_debug::__dp_equality) 529 { 530 if (__dist2.second > ::__gnu_debug::__dp_equality) 531 return std::__lexicographical_compare_aux(__first1.base(), 532 __last1.base(), 533 __first2.base(), 534 __last2.base()); 535 return std::__lexicographical_compare_aux(__first1.base(), 536 __last1.base(), 537 __first2, __last2); 538 } 539 540 if (__dist2.second > ::__gnu_debug::__dp_equality) 541 return std::__lexicographical_compare_aux(__first1, __last1, 542 __first2.base(), 543 __last2.base()); 544 return std::__lexicographical_compare_aux1(__first1, __last1, 545 __first2, __last2); 546 } 547 548 _GLIBCXX_END_NAMESPACE_VERSION 549 } // namespace std 550 551 #endif 552
Indexes created Mon Mar 02 05:31:46 UTC 2026