1// Debugging deque implementation -*- 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/deque 26 * This file is a GNU debug extension to the Standard C++ Library. 27 */ 28 29#ifndef _GLIBCXX_DEBUG_DEQUE 30#define _GLIBCXX_DEBUG_DEQUE 1 31 32#pragma GCC system_header 33 34#include <bits/c++config.h> 35namespace std _GLIBCXX_VISIBILITY(default) { namespace __debug { 36 template<typename _Tp, typename _Allocator> class deque; 37} } // namespace std::__debug 38 39#include <deque> 40#include <debug/safe_sequence.h> 41#include <debug/safe_container.h> 42#include <debug/safe_iterator.h> 43 44namespace std _GLIBCXX_VISIBILITY(default) 45{ 46namespace __debug 47{ 48 /// Class std::deque with safety/checking/debug instrumentation. 49 template<typename _Tp, typename _Allocator = std::allocator<_Tp> > 50 class deque 51 : public __gnu_debug::_Safe_container< 52 deque<_Tp, _Allocator>, _Allocator, 53 __gnu_debug::_Safe_sequence>, 54 public _GLIBCXX_STD_C::deque<_Tp, _Allocator> 55 { 56 typedef _GLIBCXX_STD_C::deque<_Tp, _Allocator> _Base; 57 typedef __gnu_debug::_Safe_container< 58 deque, _Allocator, __gnu_debug::_Safe_sequence> _Safe; 59 60 typedef typename _Base::const_iterator _Base_const_iterator; 61 typedef typename _Base::iterator _Base_iterator; 62 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; 63 64 template<typename _ItT, typename _SeqT, typename _CatT> 65 friend class ::__gnu_debug::_Safe_iterator; 66 67 // Reference wrapper for base class. Disambiguates deque(const _Base&) 68 // from copy constructor by requiring a user-defined conversion. 69 // See PR libstdc++/90102. 70 struct _Base_ref 71 { 72 _Base_ref(const _Base& __r) : _M_ref(__r) { } 73 74 const _Base& _M_ref; 75 }; 76 77 public: 78 typedef typename _Base::reference reference; 79 typedef typename _Base::const_reference const_reference; 80 81 typedef __gnu_debug::_Safe_iterator<_Base_iterator, deque> 82 iterator; 83 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, deque> 84 const_iterator; 85 86 typedef typename _Base::size_type size_type; 87 typedef typename _Base::difference_type difference_type; 88 89 typedef _Tp value_type; 90 typedef _Allocator allocator_type; 91 typedef typename _Base::pointer pointer; 92 typedef typename _Base::const_pointer const_pointer; 93 typedef std::reverse_iterator<iterator> reverse_iterator; 94 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 95 96 // 23.2.1.1 construct/copy/destroy: 97 98#if __cplusplus < 201103L 99 deque() 100 : _Base() { } 101 102 deque(const deque& __x) 103 : _Base(__x) { } 104 105 ~deque() { } 106#else 107 deque() = default; 108 deque(const deque&) = default; 109 deque(deque&&) = default; 110 111 deque(const deque& __d, const __type_identity_t<_Allocator>& __a) 112 : _Base(__d, __a) { } 113 114 deque(deque&& __d, const __type_identity_t<_Allocator>& __a) 115 : _Safe(std::move(__d)), _Base(std::move(__d), __a) { } 116 117 deque(initializer_list<value_type> __l, 118 const allocator_type& __a = allocator_type()) 119 : _Base(__l, __a) { } 120 121 ~deque() = default; 122#endif 123 124 explicit 125 deque(const _Allocator& __a) 126 : _Base(__a) { } 127 128#if __cplusplus >= 201103L 129 explicit 130 deque(size_type __n, const _Allocator& __a = _Allocator()) 131 : _Base(__n, __a) { } 132 133 deque(size_type __n, const __type_identity_t<_Tp>& __value, 134 const _Allocator& __a = _Allocator()) 135 : _Base(__n, __value, __a) { } 136#else 137 explicit 138 deque(size_type __n, const _Tp& __value = _Tp(), 139 const _Allocator& __a = _Allocator()) 140 : _Base(__n, __value, __a) { } 141#endif 142 143#if __cplusplus >= 201103L 144 template<class _InputIterator, 145 typename = std::_RequireInputIter<_InputIterator>> 146#else 147 template<class _InputIterator> 148#endif 149 deque(_InputIterator __first, _InputIterator __last, 150 const _Allocator& __a = _Allocator()) 151 : _Base(__gnu_debug::__base( 152 __glibcxx_check_valid_constructor_range(__first, __last)), 153 __gnu_debug::__base(__last), __a) 154 { } 155 156 deque(_Base_ref __x) 157 : _Base(__x._M_ref) { } 158 159#if __cplusplus >= 201103L 160 deque& 161 operator=(const deque&) = default; 162 163 deque& 164 operator=(deque&&) = default; 165 166 deque& 167 operator=(initializer_list<value_type> __l) 168 { 169 _Base::operator=(__l); 170 this->_M_invalidate_all(); 171 return *this; 172 } 173#endif 174 175#if __cplusplus >= 201103L 176 template<class _InputIterator, 177 typename = std::_RequireInputIter<_InputIterator>> 178#else 179 template<class _InputIterator> 180#endif 181 void 182 assign(_InputIterator __first, _InputIterator __last) 183 { 184 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 185 __glibcxx_check_valid_range2(__first, __last, __dist); 186 if (__dist.second >= __gnu_debug::__dp_sign) 187 _Base::assign(__gnu_debug::__unsafe(__first), 188 __gnu_debug::__unsafe(__last)); 189 else 190 _Base::assign(__first, __last); 191 192 this->_M_invalidate_all(); 193 } 194 195 void 196 assign(size_type __n, const _Tp& __t) 197 { 198 _Base::assign(__n, __t); 199 this->_M_invalidate_all(); 200 } 201 202#if __cplusplus >= 201103L 203 void 204 assign(initializer_list<value_type> __l) 205 { 206 _Base::assign(__l); 207 this->_M_invalidate_all(); 208 } 209#endif 210 211 using _Base::get_allocator; 212 213 // iterators: 214 _GLIBCXX_NODISCARD 215 iterator 216 begin() _GLIBCXX_NOEXCEPT 217 { return iterator(_Base::begin(), this); } 218 219 _GLIBCXX_NODISCARD 220 const_iterator 221 begin() const _GLIBCXX_NOEXCEPT 222 { return const_iterator(_Base::begin(), this); } 223 224 _GLIBCXX_NODISCARD 225 iterator 226 end() _GLIBCXX_NOEXCEPT 227 { return iterator(_Base::end(), this); } 228 229 _GLIBCXX_NODISCARD 230 const_iterator 231 end() const _GLIBCXX_NOEXCEPT 232 { return const_iterator(_Base::end(), this); } 233 234 _GLIBCXX_NODISCARD 235 reverse_iterator 236 rbegin() _GLIBCXX_NOEXCEPT 237 { return reverse_iterator(end()); } 238 239 _GLIBCXX_NODISCARD 240 const_reverse_iterator 241 rbegin() const _GLIBCXX_NOEXCEPT 242 { return const_reverse_iterator(end()); } 243 244 _GLIBCXX_NODISCARD 245 reverse_iterator 246 rend() _GLIBCXX_NOEXCEPT 247 { return reverse_iterator(begin()); } 248 249 _GLIBCXX_NODISCARD 250 const_reverse_iterator 251 rend() const _GLIBCXX_NOEXCEPT 252 { return const_reverse_iterator(begin()); } 253 254#if __cplusplus >= 201103L 255 [[__nodiscard__]] 256 const_iterator 257 cbegin() const noexcept 258 { return const_iterator(_Base::begin(), this); } 259 260 [[__nodiscard__]] 261 const_iterator 262 cend() const noexcept 263 { return const_iterator(_Base::end(), this); } 264 265 [[__nodiscard__]] 266 const_reverse_iterator 267 crbegin() const noexcept 268 { return const_reverse_iterator(end()); } 269 270 [[__nodiscard__]] 271 const_reverse_iterator 272 crend() const noexcept 273 { return const_reverse_iterator(begin()); } 274#endif 275 276 private: 277 void 278 _M_invalidate_after_nth(difference_type __n) 279 { 280 typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth; 281 this->_M_invalidate_if(_After_nth(__n, _Base::begin())); 282 } 283 284 public: 285 // 23.2.1.2 capacity: 286 using _Base::size; 287 using _Base::max_size; 288 289#if __cplusplus >= 201103L 290 void 291 resize(size_type __sz) 292 { 293 bool __invalidate_all = __sz > this->size(); 294 if (__sz < this->size()) 295 this->_M_invalidate_after_nth(__sz); 296 297 _Base::resize(__sz); 298 299 if (__invalidate_all) 300 this->_M_invalidate_all(); 301 } 302 303 void 304 resize(size_type __sz, const _Tp& __c) 305 { 306 bool __invalidate_all = __sz > this->size(); 307 if (__sz < this->size()) 308 this->_M_invalidate_after_nth(__sz); 309 310 _Base::resize(__sz, __c); 311 312 if (__invalidate_all) 313 this->_M_invalidate_all(); 314 } 315#else 316 void 317 resize(size_type __sz, _Tp __c = _Tp()) 318 { 319 bool __invalidate_all = __sz > this->size(); 320 if (__sz < this->size()) 321 this->_M_invalidate_after_nth(__sz); 322 323 _Base::resize(__sz, __c); 324 325 if (__invalidate_all) 326 this->_M_invalidate_all(); 327 } 328#endif 329 330#if __cplusplus >= 201103L 331 void 332 shrink_to_fit() noexcept 333 { 334 if (_Base::_M_shrink_to_fit()) 335 this->_M_invalidate_all(); 336 } 337#endif 338 339 using _Base::empty; 340 341 // element access: 342 _GLIBCXX_NODISCARD 343 reference 344 operator[](size_type __n) _GLIBCXX_NOEXCEPT 345 { 346 __glibcxx_check_subscript(__n); 347 return _Base::operator[](__n); 348 } 349 350 _GLIBCXX_NODISCARD 351 const_reference 352 operator[](size_type __n) const _GLIBCXX_NOEXCEPT 353 { 354 __glibcxx_check_subscript(__n); 355 return _Base::operator[](__n); 356 } 357 358 using _Base::at; 359 360 _GLIBCXX_NODISCARD 361 reference 362 front() _GLIBCXX_NOEXCEPT 363 { 364 __glibcxx_check_nonempty(); 365 return _Base::front(); 366 } 367 368 _GLIBCXX_NODISCARD 369 const_reference 370 front() const _GLIBCXX_NOEXCEPT 371 { 372 __glibcxx_check_nonempty(); 373 return _Base::front(); 374 } 375 376 _GLIBCXX_NODISCARD 377 reference 378 back() _GLIBCXX_NOEXCEPT 379 { 380 __glibcxx_check_nonempty(); 381 return _Base::back(); 382 } 383 384 _GLIBCXX_NODISCARD 385 const_reference 386 back() const _GLIBCXX_NOEXCEPT 387 { 388 __glibcxx_check_nonempty(); 389 return _Base::back(); 390 } 391 392 // 23.2.1.3 modifiers: 393 void 394 push_front(const _Tp& __x) 395 { 396 _Base::push_front(__x); 397 this->_M_invalidate_all(); 398 } 399 400 void 401 push_back(const _Tp& __x) 402 { 403 _Base::push_back(__x); 404 this->_M_invalidate_all(); 405 } 406 407#if __cplusplus >= 201103L 408 void 409 push_front(_Tp&& __x) 410 { emplace_front(std::move(__x)); } 411 412 void 413 push_back(_Tp&& __x) 414 { emplace_back(std::move(__x)); } 415 416 template<typename... _Args> 417#if __cplusplus > 201402L 418 reference 419#else 420 void 421#endif 422 emplace_front(_Args&&... __args) 423 { 424 _Base::emplace_front(std::forward<_Args>(__args)...); 425 this->_M_invalidate_all(); 426#if __cplusplus > 201402L 427 return front(); 428#endif 429 } 430 431 template<typename... _Args> 432#if __cplusplus > 201402L 433 reference 434#else 435 void 436#endif 437 emplace_back(_Args&&... __args) 438 { 439 _Base::emplace_back(std::forward<_Args>(__args)...); 440 this->_M_invalidate_all(); 441#if __cplusplus > 201402L 442 return back(); 443#endif 444 } 445 446 template<typename... _Args> 447 iterator 448 emplace(const_iterator __position, _Args&&... __args) 449 { 450 __glibcxx_check_insert(__position); 451 _Base_iterator __res = _Base::emplace(__position.base(), 452 std::forward<_Args>(__args)...); 453 this->_M_invalidate_all(); 454 return iterator(__res, this); 455 } 456#endif 457 458 iterator 459#if __cplusplus >= 201103L 460 insert(const_iterator __position, const _Tp& __x) 461#else 462 insert(iterator __position, const _Tp& __x) 463#endif 464 { 465 __glibcxx_check_insert(__position); 466 _Base_iterator __res = _Base::insert(__position.base(), __x); 467 this->_M_invalidate_all(); 468 return iterator(__res, this); 469 } 470 471#if __cplusplus >= 201103L 472 iterator 473 insert(const_iterator __position, _Tp&& __x) 474 { return emplace(__position, std::move(__x)); } 475 476 iterator 477 insert(const_iterator __position, initializer_list<value_type> __l) 478 { 479 __glibcxx_check_insert(__position); 480 _Base_iterator __res = _Base::insert(__position.base(), __l); 481 this->_M_invalidate_all(); 482 return iterator(__res, this); 483 } 484#endif 485 486#if __cplusplus >= 201103L 487 iterator 488 insert(const_iterator __position, size_type __n, const _Tp& __x) 489 { 490 __glibcxx_check_insert(__position); 491 _Base_iterator __res = _Base::insert(__position.base(), __n, __x); 492 this->_M_invalidate_all(); 493 return iterator(__res, this); 494 } 495#else 496 void 497 insert(iterator __position, size_type __n, const _Tp& __x) 498 { 499 __glibcxx_check_insert(__position); 500 _Base::insert(__position.base(), __n, __x); 501 this->_M_invalidate_all(); 502 } 503#endif 504 505#if __cplusplus >= 201103L 506 template<class _InputIterator, 507 typename = std::_RequireInputIter<_InputIterator>> 508 iterator 509 insert(const_iterator __position, 510 _InputIterator __first, _InputIterator __last) 511 { 512 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 513 __glibcxx_check_insert_range(__position, __first, __last, __dist); 514 _Base_iterator __res; 515 if (__dist.second >= __gnu_debug::__dp_sign) 516 __res = _Base::insert(__position.base(), 517 __gnu_debug::__unsafe(__first), 518 __gnu_debug::__unsafe(__last)); 519 else 520 __res = _Base::insert(__position.base(), __first, __last); 521 522 this->_M_invalidate_all(); 523 return iterator(__res, this); 524 } 525#else 526 template<class _InputIterator> 527 void 528 insert(iterator __position, 529 _InputIterator __first, _InputIterator __last) 530 { 531 typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; 532 __glibcxx_check_insert_range(__position, __first, __last, __dist); 533 534 if (__dist.second >= __gnu_debug::__dp_sign) 535 _Base::insert(__position.base(), 536 __gnu_debug::__unsafe(__first), 537 __gnu_debug::__unsafe(__last)); 538 else 539 _Base::insert(__position.base(), __first, __last); 540 541 this->_M_invalidate_all(); 542 } 543#endif 544 545 void 546 pop_front() _GLIBCXX_NOEXCEPT 547 { 548 __glibcxx_check_nonempty(); 549 this->_M_invalidate_if(_Equal(_Base::begin())); 550 _Base::pop_front(); 551 } 552 553 void 554 pop_back() _GLIBCXX_NOEXCEPT 555 { 556 __glibcxx_check_nonempty(); 557 this->_M_invalidate_if(_Equal(--_Base::end())); 558 _Base::pop_back(); 559 } 560 561 iterator 562#if __cplusplus >= 201103L 563 erase(const_iterator __position) 564#else 565 erase(iterator __position) 566#endif 567 { 568 __glibcxx_check_erase(__position); 569#if __cplusplus >= 201103L 570 _Base_const_iterator __victim = __position.base(); 571#else 572 _Base_iterator __victim = __position.base(); 573#endif 574 if (__victim == _Base::begin() || __victim == _Base::end() - 1) 575 { 576 this->_M_invalidate_if(_Equal(__victim)); 577 return iterator(_Base::erase(__victim), this); 578 } 579 else 580 { 581 _Base_iterator __res = _Base::erase(__victim); 582 this->_M_invalidate_all(); 583 return iterator(__res, this); 584 } 585 } 586 587 iterator 588#if __cplusplus >= 201103L 589 erase(const_iterator __first, const_iterator __last) 590#else 591 erase(iterator __first, iterator __last) 592#endif 593 { 594 // _GLIBCXX_RESOLVE_LIB_DEFECTS 595 // 151. can't currently clear() empty container 596 __glibcxx_check_erase_range(__first, __last); 597 598 if (__first.base() == __last.base()) 599#if __cplusplus >= 201103L 600 return iterator(__first.base()._M_const_cast(), this); 601#else 602 return __first; 603#endif 604 else if (__first.base() == _Base::begin() 605 || __last.base() == _Base::end()) 606 { 607 this->_M_detach_singular(); 608 for (_Base_const_iterator __position = __first.base(); 609 __position != __last.base(); ++__position) 610 { 611 this->_M_invalidate_if(_Equal(__position)); 612 } 613 __try 614 { 615 return iterator(_Base::erase(__first.base(), __last.base()), 616 this); 617 } 618 __catch(...) 619 { 620 this->_M_revalidate_singular(); 621 __throw_exception_again; 622 } 623 } 624 else 625 { 626 _Base_iterator __res = _Base::erase(__first.base(), 627 __last.base()); 628 this->_M_invalidate_all(); 629 return iterator(__res, this); 630 } 631 } 632 633 void 634 swap(deque& __x) 635 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) ) 636 { 637 _Safe::_M_swap(__x); 638 _Base::swap(__x); 639 } 640 641 void 642 clear() _GLIBCXX_NOEXCEPT 643 { 644 _Base::clear(); 645 this->_M_invalidate_all(); 646 } 647 648 _Base& 649 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 650 651 const _Base& 652 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 653 }; 654 655#if __cpp_deduction_guides >= 201606 656 template<typename _InputIterator, typename _ValT 657 = typename iterator_traits<_InputIterator>::value_type, 658 typename _Allocator = allocator<_ValT>, 659 typename = _RequireInputIter<_InputIterator>, 660 typename = _RequireAllocator<_Allocator>> 661 deque(_InputIterator, _InputIterator, _Allocator = _Allocator()) 662 -> deque<_ValT, _Allocator>; 663 664 template<typename _Tp, typename _Allocator = allocator<_Tp>, 665 typename = _RequireAllocator<_Allocator>> 666 deque(size_t, _Tp, _Allocator = _Allocator()) 667 -> deque<_Tp, _Allocator>; 668#endif 669 670 template<typename _Tp, typename _Alloc> 671 inline bool 672 operator==(const deque<_Tp, _Alloc>& __lhs, 673 const deque<_Tp, _Alloc>& __rhs) 674 { return __lhs._M_base() == __rhs._M_base(); } 675 676#if __cpp_lib_three_way_comparison 677 template<typename _Tp, typename _Alloc> 678 constexpr __detail::__synth3way_t<_Tp> 679 operator<=>(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y) 680 { return __x._M_base() <=> __y._M_base(); } 681#else 682 template<typename _Tp, typename _Alloc> 683 inline bool 684 operator!=(const deque<_Tp, _Alloc>& __lhs, 685 const deque<_Tp, _Alloc>& __rhs) 686 { return __lhs._M_base() != __rhs._M_base(); } 687 688 template<typename _Tp, typename _Alloc> 689 inline bool 690 operator<(const deque<_Tp, _Alloc>& __lhs, 691 const deque<_Tp, _Alloc>& __rhs) 692 { return __lhs._M_base() < __rhs._M_base(); } 693 694 template<typename _Tp, typename _Alloc> 695 inline bool 696 operator<=(const deque<_Tp, _Alloc>& __lhs, 697 const deque<_Tp, _Alloc>& __rhs) 698 { return __lhs._M_base() <= __rhs._M_base(); } 699 700 template<typename _Tp, typename _Alloc> 701 inline bool 702 operator>=(const deque<_Tp, _Alloc>& __lhs, 703 const deque<_Tp, _Alloc>& __rhs) 704 { return __lhs._M_base() >= __rhs._M_base(); } 705 706 template<typename _Tp, typename _Alloc> 707 inline bool 708 operator>(const deque<_Tp, _Alloc>& __lhs, 709 const deque<_Tp, _Alloc>& __rhs) 710 { return __lhs._M_base() > __rhs._M_base(); } 711#endif // three-way comparison 712 713 template<typename _Tp, typename _Alloc> 714 inline void 715 swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs) 716 _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs))) 717 { __lhs.swap(__rhs); } 718 719} // namespace __debug 720} // namespace std 721 722#endif 723