1// Debugging deque implementation -*- C++ -*- 2 3// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011 4// Free Software Foundation, Inc. 5// 6// This file is part of the GNU ISO C++ Library. This library is free 7// software; you can redistribute it and/or modify it under the 8// terms of the GNU General Public License as published by the 9// Free Software Foundation; either version 3, or (at your option) 10// any later version. 11 12// This library is distributed in the hope that it will be useful, 13// but WITHOUT ANY WARRANTY; without even the implied warranty of 14// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15// GNU General Public License for more details. 16 17// Under Section 7 of GPL version 3, you are granted additional 18// permissions described in the GCC Runtime Library Exception, version 19// 3.1, as published by the Free Software Foundation. 20 21// You should have received a copy of the GNU General Public License and 22// a copy of the GCC Runtime Library Exception along with this program; 23// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24// <http://www.gnu.org/licenses/>. 25 26/** @file debug/deque 27 * This file is a GNU debug extension to the Standard C++ Library. 28 */ 29 30#ifndef _GLIBCXX_DEBUG_DEQUE 31#define _GLIBCXX_DEBUG_DEQUE 1 32 33#include <deque> 34#include <debug/safe_sequence.h> 35#include <debug/safe_iterator.h> 36 37namespace std _GLIBCXX_VISIBILITY(default) 38{ 39namespace __debug 40{ 41 /// Class std::deque with safety/checking/debug instrumentation. 42 template<typename _Tp, typename _Allocator = std::allocator<_Tp> > 43 class deque 44 : public _GLIBCXX_STD_C::deque<_Tp, _Allocator>, 45 public __gnu_debug::_Safe_sequence<deque<_Tp, _Allocator> > 46 { 47 typedef _GLIBCXX_STD_C::deque<_Tp, _Allocator> _Base; 48 49 typedef typename _Base::const_iterator _Base_const_iterator; 50 typedef typename _Base::iterator _Base_iterator; 51 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; 52 public: 53 typedef typename _Base::reference reference; 54 typedef typename _Base::const_reference const_reference; 55 56 typedef __gnu_debug::_Safe_iterator<_Base_iterator,deque> 57 iterator; 58 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,deque> 59 const_iterator; 60 61 typedef typename _Base::size_type size_type; 62 typedef typename _Base::difference_type difference_type; 63 64 typedef _Tp value_type; 65 typedef _Allocator allocator_type; 66 typedef typename _Base::pointer pointer; 67 typedef typename _Base::const_pointer const_pointer; 68 typedef std::reverse_iterator<iterator> reverse_iterator; 69 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 70 71 // 23.2.1.1 construct/copy/destroy: 72 explicit 73 deque(const _Allocator& __a = _Allocator()) 74 : _Base(__a) { } 75 76#ifdef __GXX_EXPERIMENTAL_CXX0X__ 77 explicit 78 deque(size_type __n) 79 : _Base(__n) { } 80 81 deque(size_type __n, const _Tp& __value, 82 const _Allocator& __a = _Allocator()) 83 : _Base(__n, __value, __a) { } 84#else 85 explicit 86 deque(size_type __n, const _Tp& __value = _Tp(), 87 const _Allocator& __a = _Allocator()) 88 : _Base(__n, __value, __a) { } 89#endif 90 91 template<class _InputIterator> 92 deque(_InputIterator __first, _InputIterator __last, 93 const _Allocator& __a = _Allocator()) 94 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 95 __last)), 96 __gnu_debug::__base(__last), __a) 97 { } 98 99 deque(const deque& __x) 100 : _Base(__x) { } 101 102 deque(const _Base& __x) 103 : _Base(__x) { } 104 105#ifdef __GXX_EXPERIMENTAL_CXX0X__ 106 deque(deque&& __x) 107 : _Base(std::move(__x)) 108 { this->_M_swap(__x); } 109 110 deque(initializer_list<value_type> __l, 111 const allocator_type& __a = allocator_type()) 112 : _Base(__l, __a) { } 113#endif 114 115 ~deque() _GLIBCXX_NOEXCEPT { } 116 117 deque& 118 operator=(const deque& __x) 119 { 120 *static_cast<_Base*>(this) = __x; 121 this->_M_invalidate_all(); 122 return *this; 123 } 124 125#ifdef __GXX_EXPERIMENTAL_CXX0X__ 126 deque& 127 operator=(deque&& __x) 128 { 129 // NB: DR 1204. 130 // NB: DR 675. 131 clear(); 132 swap(__x); 133 return *this; 134 } 135 136 deque& 137 operator=(initializer_list<value_type> __l) 138 { 139 *static_cast<_Base*>(this) = __l; 140 this->_M_invalidate_all(); 141 return *this; 142 } 143#endif 144 145 template<class _InputIterator> 146 void 147 assign(_InputIterator __first, _InputIterator __last) 148 { 149 __glibcxx_check_valid_range(__first, __last); 150 _Base::assign(__gnu_debug::__base(__first), 151 __gnu_debug::__base(__last)); 152 this->_M_invalidate_all(); 153 } 154 155 void 156 assign(size_type __n, const _Tp& __t) 157 { 158 _Base::assign(__n, __t); 159 this->_M_invalidate_all(); 160 } 161 162#ifdef __GXX_EXPERIMENTAL_CXX0X__ 163 void 164 assign(initializer_list<value_type> __l) 165 { 166 _Base::assign(__l); 167 this->_M_invalidate_all(); 168 } 169#endif 170 171 using _Base::get_allocator; 172 173 // iterators: 174 iterator 175 begin() _GLIBCXX_NOEXCEPT 176 { return iterator(_Base::begin(), this); } 177 178 const_iterator 179 begin() const _GLIBCXX_NOEXCEPT 180 { return const_iterator(_Base::begin(), this); } 181 182 iterator 183 end() _GLIBCXX_NOEXCEPT 184 { return iterator(_Base::end(), this); } 185 186 const_iterator 187 end() const _GLIBCXX_NOEXCEPT 188 { return const_iterator(_Base::end(), this); } 189 190 reverse_iterator 191 rbegin() _GLIBCXX_NOEXCEPT 192 { return reverse_iterator(end()); } 193 194 const_reverse_iterator 195 rbegin() const _GLIBCXX_NOEXCEPT 196 { return const_reverse_iterator(end()); } 197 198 reverse_iterator 199 rend() _GLIBCXX_NOEXCEPT 200 { return reverse_iterator(begin()); } 201 202 const_reverse_iterator 203 rend() const _GLIBCXX_NOEXCEPT 204 { return const_reverse_iterator(begin()); } 205 206#ifdef __GXX_EXPERIMENTAL_CXX0X__ 207 const_iterator 208 cbegin() const noexcept 209 { return const_iterator(_Base::begin(), this); } 210 211 const_iterator 212 cend() const noexcept 213 { return const_iterator(_Base::end(), this); } 214 215 const_reverse_iterator 216 crbegin() const noexcept 217 { return const_reverse_iterator(end()); } 218 219 const_reverse_iterator 220 crend() const noexcept 221 { return const_reverse_iterator(begin()); } 222#endif 223 224 private: 225 void 226 _M_invalidate_after_nth(difference_type __n) 227 { 228 typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth; 229 this->_M_invalidate_if(_After_nth(__n, _Base::begin())); 230 } 231 232 public: 233 // 23.2.1.2 capacity: 234 using _Base::size; 235 using _Base::max_size; 236 237#ifdef __GXX_EXPERIMENTAL_CXX0X__ 238 void 239 resize(size_type __sz) 240 { 241 bool __invalidate_all = __sz > this->size(); 242 if (__sz < this->size()) 243 this->_M_invalidate_after_nth(__sz); 244 245 _Base::resize(__sz); 246 247 if (__invalidate_all) 248 this->_M_invalidate_all(); 249 } 250 251 void 252 resize(size_type __sz, const _Tp& __c) 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, __c); 259 260 if (__invalidate_all) 261 this->_M_invalidate_all(); 262 } 263#else 264 void 265 resize(size_type __sz, _Tp __c = _Tp()) 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#endif 277 278#ifdef __GXX_EXPERIMENTAL_CXX0X__ 279 void 280 shrink_to_fit() 281 { 282 if (_Base::_M_shrink_to_fit()) 283 this->_M_invalidate_all(); 284 } 285#endif 286 287 using _Base::empty; 288 289 // element access: 290 reference 291 operator[](size_type __n) 292 { 293 __glibcxx_check_subscript(__n); 294 return _M_base()[__n]; 295 } 296 297 const_reference 298 operator[](size_type __n) const 299 { 300 __glibcxx_check_subscript(__n); 301 return _M_base()[__n]; 302 } 303 304 using _Base::at; 305 306 reference 307 front() 308 { 309 __glibcxx_check_nonempty(); 310 return _Base::front(); 311 } 312 313 const_reference 314 front() const 315 { 316 __glibcxx_check_nonempty(); 317 return _Base::front(); 318 } 319 320 reference 321 back() 322 { 323 __glibcxx_check_nonempty(); 324 return _Base::back(); 325 } 326 327 const_reference 328 back() const 329 { 330 __glibcxx_check_nonempty(); 331 return _Base::back(); 332 } 333 334 // 23.2.1.3 modifiers: 335 void 336 push_front(const _Tp& __x) 337 { 338 _Base::push_front(__x); 339 this->_M_invalidate_all(); 340 } 341 342 void 343 push_back(const _Tp& __x) 344 { 345 _Base::push_back(__x); 346 this->_M_invalidate_all(); 347 } 348 349#ifdef __GXX_EXPERIMENTAL_CXX0X__ 350 void 351 push_front(_Tp&& __x) 352 { emplace_front(std::move(__x)); } 353 354 void 355 push_back(_Tp&& __x) 356 { emplace_back(std::move(__x)); } 357 358 template<typename... _Args> 359 void 360 emplace_front(_Args&&... __args) 361 { 362 _Base::emplace_front(std::forward<_Args>(__args)...); 363 this->_M_invalidate_all(); 364 } 365 366 template<typename... _Args> 367 void 368 emplace_back(_Args&&... __args) 369 { 370 _Base::emplace_back(std::forward<_Args>(__args)...); 371 this->_M_invalidate_all(); 372 } 373 374 template<typename... _Args> 375 iterator 376 emplace(iterator __position, _Args&&... __args) 377 { 378 __glibcxx_check_insert(__position); 379 _Base_iterator __res = _Base::emplace(__position.base(), 380 std::forward<_Args>(__args)...); 381 this->_M_invalidate_all(); 382 return iterator(__res, this); 383 } 384#endif 385 386 iterator 387 insert(iterator __position, const _Tp& __x) 388 { 389 __glibcxx_check_insert(__position); 390 _Base_iterator __res = _Base::insert(__position.base(), __x); 391 this->_M_invalidate_all(); 392 return iterator(__res, this); 393 } 394 395#ifdef __GXX_EXPERIMENTAL_CXX0X__ 396 iterator 397 insert(iterator __position, _Tp&& __x) 398 { return emplace(__position, std::move(__x)); } 399 400 void 401 insert(iterator __p, initializer_list<value_type> __l) 402 { 403 _Base::insert(__p, __l); 404 this->_M_invalidate_all(); 405 } 406#endif 407 408 void 409 insert(iterator __position, size_type __n, const _Tp& __x) 410 { 411 __glibcxx_check_insert(__position); 412 _Base::insert(__position.base(), __n, __x); 413 this->_M_invalidate_all(); 414 } 415 416 template<class _InputIterator> 417 void 418 insert(iterator __position, 419 _InputIterator __first, _InputIterator __last) 420 { 421 __glibcxx_check_insert_range(__position, __first, __last); 422 _Base::insert(__position.base(), __gnu_debug::__base(__first), 423 __gnu_debug::__base(__last)); 424 this->_M_invalidate_all(); 425 } 426 427 void 428 pop_front() 429 { 430 __glibcxx_check_nonempty(); 431 this->_M_invalidate_if(_Equal(_Base::begin())); 432 _Base::pop_front(); 433 } 434 435 void 436 pop_back() 437 { 438 __glibcxx_check_nonempty(); 439 this->_M_invalidate_if(_Equal(--_Base::end())); 440 _Base::pop_back(); 441 } 442 443 iterator 444 erase(iterator __position) 445 { 446 __glibcxx_check_erase(__position); 447 _Base_iterator __victim = __position.base(); 448 if (__victim == _Base::begin() || __victim == _Base::end()-1) 449 { 450 this->_M_invalidate_if(_Equal(__victim)); 451 return iterator(_Base::erase(__victim), this); 452 } 453 else 454 { 455 _Base_iterator __res = _Base::erase(__victim); 456 this->_M_invalidate_all(); 457 return iterator(__res, this); 458 } 459 } 460 461 iterator 462 erase(iterator __first, iterator __last) 463 { 464 // _GLIBCXX_RESOLVE_LIB_DEFECTS 465 // 151. can't currently clear() empty container 466 __glibcxx_check_erase_range(__first, __last); 467 468 if (__first.base() == __last.base()) 469 return __first; 470 else if (__first.base() == _Base::begin() 471 || __last.base() == _Base::end()) 472 { 473 this->_M_detach_singular(); 474 for (_Base_iterator __position = __first.base(); 475 __position != __last.base(); ++__position) 476 { 477 this->_M_invalidate_if(_Equal(__position)); 478 } 479 __try 480 { 481 return iterator(_Base::erase(__first.base(), __last.base()), 482 this); 483 } 484 __catch(...) 485 { 486 this->_M_revalidate_singular(); 487 __throw_exception_again; 488 } 489 } 490 else 491 { 492 _Base_iterator __res = _Base::erase(__first.base(), 493 __last.base()); 494 this->_M_invalidate_all(); 495 return iterator(__res, this); 496 } 497 } 498 499 void 500 swap(deque& __x) 501 { 502 _Base::swap(__x); 503 this->_M_swap(__x); 504 } 505 506 void 507 clear() _GLIBCXX_NOEXCEPT 508 { 509 _Base::clear(); 510 this->_M_invalidate_all(); 511 } 512 513 _Base& 514 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 515 516 const _Base& 517 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 518 }; 519 520 template<typename _Tp, typename _Alloc> 521 inline bool 522 operator==(const deque<_Tp, _Alloc>& __lhs, 523 const deque<_Tp, _Alloc>& __rhs) 524 { return __lhs._M_base() == __rhs._M_base(); } 525 526 template<typename _Tp, typename _Alloc> 527 inline bool 528 operator!=(const deque<_Tp, _Alloc>& __lhs, 529 const deque<_Tp, _Alloc>& __rhs) 530 { return __lhs._M_base() != __rhs._M_base(); } 531 532 template<typename _Tp, typename _Alloc> 533 inline bool 534 operator<(const deque<_Tp, _Alloc>& __lhs, 535 const deque<_Tp, _Alloc>& __rhs) 536 { return __lhs._M_base() < __rhs._M_base(); } 537 538 template<typename _Tp, typename _Alloc> 539 inline bool 540 operator<=(const deque<_Tp, _Alloc>& __lhs, 541 const deque<_Tp, _Alloc>& __rhs) 542 { return __lhs._M_base() <= __rhs._M_base(); } 543 544 template<typename _Tp, typename _Alloc> 545 inline bool 546 operator>=(const deque<_Tp, _Alloc>& __lhs, 547 const deque<_Tp, _Alloc>& __rhs) 548 { return __lhs._M_base() >= __rhs._M_base(); } 549 550 template<typename _Tp, typename _Alloc> 551 inline bool 552 operator>(const deque<_Tp, _Alloc>& __lhs, 553 const deque<_Tp, _Alloc>& __rhs) 554 { return __lhs._M_base() > __rhs._M_base(); } 555 556 template<typename _Tp, typename _Alloc> 557 inline void 558 swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs) 559 { __lhs.swap(__rhs); } 560 561} // namespace __debug 562} // namespace std 563 564#endif 565