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