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