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