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