libstdc++
|
00001 // Debugging deque implementation -*- C++ -*- 00002 00003 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 00004 // Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the 00008 // terms of the GNU General Public License as published by the 00009 // Free Software Foundation; either version 3, or (at your option) 00010 // any later version. 00011 00012 // This library is distributed in the hope that it will be useful, 00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 // GNU General Public License for more details. 00016 00017 // Under Section 7 of GPL version 3, you are granted additional 00018 // permissions described in the GCC Runtime Library Exception, version 00019 // 3.1, as published by the Free Software Foundation. 00020 00021 // You should have received a copy of the GNU General Public License and 00022 // a copy of the GCC Runtime Library Exception along with this program; 00023 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00024 // <http://www.gnu.org/licenses/>. 00025 00026 /** @file debug/deque 00027 * This file is a GNU debug extension to the Standard C++ Library. 00028 */ 00029 00030 #ifndef _GLIBCXX_DEBUG_DEQUE 00031 #define _GLIBCXX_DEBUG_DEQUE 1 00032 00033 #include <deque> 00034 #include <debug/safe_sequence.h> 00035 #include <debug/safe_iterator.h> 00036 00037 namespace std _GLIBCXX_VISIBILITY(default) 00038 { 00039 namespace __debug 00040 { 00041 /// Class std::deque with safety/checking/debug instrumentation. 00042 template<typename _Tp, typename _Allocator = std::allocator<_Tp> > 00043 class deque 00044 : public _GLIBCXX_STD_C::deque<_Tp, _Allocator>, 00045 public __gnu_debug::_Safe_sequence<deque<_Tp, _Allocator> > 00046 { 00047 typedef _GLIBCXX_STD_C::deque<_Tp, _Allocator> _Base; 00048 typedef __gnu_debug::_Safe_sequence<deque> _Safe_base; 00049 00050 typedef typename _Base::const_iterator _Base_const_iterator; 00051 typedef typename _Base::iterator _Base_iterator; 00052 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; 00053 public: 00054 typedef typename _Base::reference reference; 00055 typedef typename _Base::const_reference const_reference; 00056 00057 typedef __gnu_debug::_Safe_iterator<_Base_iterator,deque> 00058 iterator; 00059 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,deque> 00060 const_iterator; 00061 00062 typedef typename _Base::size_type size_type; 00063 typedef typename _Base::difference_type difference_type; 00064 00065 typedef _Tp value_type; 00066 typedef _Allocator allocator_type; 00067 typedef typename _Base::pointer pointer; 00068 typedef typename _Base::const_pointer const_pointer; 00069 typedef std::reverse_iterator<iterator> reverse_iterator; 00070 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00071 00072 // 23.2.1.1 construct/copy/destroy: 00073 explicit 00074 deque(const _Allocator& __a = _Allocator()) 00075 : _Base(__a) { } 00076 00077 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00078 explicit 00079 deque(size_type __n) 00080 : _Base(__n) { } 00081 00082 deque(size_type __n, const _Tp& __value, 00083 const _Allocator& __a = _Allocator()) 00084 : _Base(__n, __value, __a) { } 00085 #else 00086 explicit 00087 deque(size_type __n, const _Tp& __value = _Tp(), 00088 const _Allocator& __a = _Allocator()) 00089 : _Base(__n, __value, __a) { } 00090 #endif 00091 00092 template<class _InputIterator> 00093 deque(_InputIterator __first, _InputIterator __last, 00094 const _Allocator& __a = _Allocator()) 00095 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 00096 __last)), 00097 __gnu_debug::__base(__last), __a) 00098 { } 00099 00100 deque(const deque& __x) 00101 : _Base(__x), _Safe_base() { } 00102 00103 deque(const _Base& __x) 00104 : _Base(__x), _Safe_base() { } 00105 00106 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00107 deque(deque&& __x) 00108 : _Base(std::move(__x)), _Safe_base() 00109 { this->_M_swap(__x); } 00110 00111 deque(initializer_list<value_type> __l, 00112 const allocator_type& __a = allocator_type()) 00113 : _Base(__l, __a), _Safe_base() { } 00114 #endif 00115 00116 ~deque() { } 00117 00118 deque& 00119 operator=(const deque& __x) 00120 { 00121 *static_cast<_Base*>(this) = __x; 00122 this->_M_invalidate_all(); 00123 return *this; 00124 } 00125 00126 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00127 deque& 00128 operator=(deque&& __x) 00129 { 00130 // NB: DR 1204. 00131 // NB: DR 675. 00132 clear(); 00133 swap(__x); 00134 return *this; 00135 } 00136 00137 deque& 00138 operator=(initializer_list<value_type> __l) 00139 { 00140 *static_cast<_Base*>(this) = __l; 00141 this->_M_invalidate_all(); 00142 return *this; 00143 } 00144 #endif 00145 00146 template<class _InputIterator> 00147 void 00148 assign(_InputIterator __first, _InputIterator __last) 00149 { 00150 __glibcxx_check_valid_range(__first, __last); 00151 _Base::assign(__gnu_debug::__base(__first), 00152 __gnu_debug::__base(__last)); 00153 this->_M_invalidate_all(); 00154 } 00155 00156 void 00157 assign(size_type __n, const _Tp& __t) 00158 { 00159 _Base::assign(__n, __t); 00160 this->_M_invalidate_all(); 00161 } 00162 00163 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00164 void 00165 assign(initializer_list<value_type> __l) 00166 { 00167 _Base::assign(__l); 00168 this->_M_invalidate_all(); 00169 } 00170 #endif 00171 00172 using _Base::get_allocator; 00173 00174 // iterators: 00175 iterator 00176 begin() 00177 { return iterator(_Base::begin(), this); } 00178 00179 const_iterator 00180 begin() const 00181 { return const_iterator(_Base::begin(), this); } 00182 00183 iterator 00184 end() 00185 { return iterator(_Base::end(), this); } 00186 00187 const_iterator 00188 end() const 00189 { return const_iterator(_Base::end(), this); } 00190 00191 reverse_iterator 00192 rbegin() 00193 { return reverse_iterator(end()); } 00194 00195 const_reverse_iterator 00196 rbegin() const 00197 { return const_reverse_iterator(end()); } 00198 00199 reverse_iterator 00200 rend() 00201 { return reverse_iterator(begin()); } 00202 00203 const_reverse_iterator 00204 rend() const 00205 { return const_reverse_iterator(begin()); } 00206 00207 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00208 const_iterator 00209 cbegin() const 00210 { return const_iterator(_Base::begin(), this); } 00211 00212 const_iterator 00213 cend() const 00214 { return const_iterator(_Base::end(), this); } 00215 00216 const_reverse_iterator 00217 crbegin() const 00218 { return const_reverse_iterator(end()); } 00219 00220 const_reverse_iterator 00221 crend() const 00222 { return const_reverse_iterator(begin()); } 00223 #endif 00224 00225 private: 00226 void 00227 _M_invalidate_after_nth(difference_type __n) 00228 { 00229 typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth; 00230 this->_M_invalidate_if(_After_nth(__n, _Base::begin())); 00231 } 00232 00233 public: 00234 // 23.2.1.2 capacity: 00235 using _Base::size; 00236 using _Base::max_size; 00237 00238 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00239 void 00240 resize(size_type __sz) 00241 { 00242 bool __invalidate_all = __sz > this->size(); 00243 if (__sz < this->size()) 00244 this->_M_invalidate_after_nth(__sz); 00245 00246 _Base::resize(__sz); 00247 00248 if (__invalidate_all) 00249 this->_M_invalidate_all(); 00250 } 00251 00252 void 00253 resize(size_type __sz, const _Tp& __c) 00254 { 00255 bool __invalidate_all = __sz > this->size(); 00256 if (__sz < this->size()) 00257 this->_M_invalidate_after_nth(__sz); 00258 00259 _Base::resize(__sz, __c); 00260 00261 if (__invalidate_all) 00262 this->_M_invalidate_all(); 00263 } 00264 #else 00265 void 00266 resize(size_type __sz, _Tp __c = _Tp()) 00267 { 00268 bool __invalidate_all = __sz > this->size(); 00269 if (__sz < this->size()) 00270 this->_M_invalidate_after_nth(__sz); 00271 00272 _Base::resize(__sz, __c); 00273 00274 if (__invalidate_all) 00275 this->_M_invalidate_all(); 00276 } 00277 #endif 00278 00279 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00280 using _Base::shrink_to_fit; 00281 #endif 00282 00283 using _Base::empty; 00284 00285 // element access: 00286 reference 00287 operator[](size_type __n) 00288 { 00289 __glibcxx_check_subscript(__n); 00290 return _M_base()[__n]; 00291 } 00292 00293 const_reference 00294 operator[](size_type __n) const 00295 { 00296 __glibcxx_check_subscript(__n); 00297 return _M_base()[__n]; 00298 } 00299 00300 using _Base::at; 00301 00302 reference 00303 front() 00304 { 00305 __glibcxx_check_nonempty(); 00306 return _Base::front(); 00307 } 00308 00309 const_reference 00310 front() const 00311 { 00312 __glibcxx_check_nonempty(); 00313 return _Base::front(); 00314 } 00315 00316 reference 00317 back() 00318 { 00319 __glibcxx_check_nonempty(); 00320 return _Base::back(); 00321 } 00322 00323 const_reference 00324 back() const 00325 { 00326 __glibcxx_check_nonempty(); 00327 return _Base::back(); 00328 } 00329 00330 // 23.2.1.3 modifiers: 00331 void 00332 push_front(const _Tp& __x) 00333 { 00334 _Base::push_front(__x); 00335 this->_M_invalidate_all(); 00336 } 00337 00338 void 00339 push_back(const _Tp& __x) 00340 { 00341 _Base::push_back(__x); 00342 this->_M_invalidate_all(); 00343 } 00344 00345 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00346 void 00347 push_front(_Tp&& __x) 00348 { emplace_front(std::move(__x)); } 00349 00350 void 00351 push_back(_Tp&& __x) 00352 { emplace_back(std::move(__x)); } 00353 00354 template<typename... _Args> 00355 void 00356 emplace_front(_Args&&... __args) 00357 { 00358 _Base::emplace_front(std::forward<_Args>(__args)...); 00359 this->_M_invalidate_all(); 00360 } 00361 00362 template<typename... _Args> 00363 void 00364 emplace_back(_Args&&... __args) 00365 { 00366 _Base::emplace_back(std::forward<_Args>(__args)...); 00367 this->_M_invalidate_all(); 00368 } 00369 00370 template<typename... _Args> 00371 iterator 00372 emplace(iterator __position, _Args&&... __args) 00373 { 00374 __glibcxx_check_insert(__position); 00375 _Base_iterator __res = _Base::emplace(__position.base(), 00376 std::forward<_Args>(__args)...); 00377 this->_M_invalidate_all(); 00378 return iterator(__res, this); 00379 } 00380 #endif 00381 00382 iterator 00383 insert(iterator __position, const _Tp& __x) 00384 { 00385 __glibcxx_check_insert(__position); 00386 _Base_iterator __res = _Base::insert(__position.base(), __x); 00387 this->_M_invalidate_all(); 00388 return iterator(__res, this); 00389 } 00390 00391 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00392 iterator 00393 insert(iterator __position, _Tp&& __x) 00394 { return emplace(__position, std::move(__x)); } 00395 00396 void 00397 insert(iterator __p, initializer_list<value_type> __l) 00398 { 00399 _Base::insert(__p, __l); 00400 this->_M_invalidate_all(); 00401 } 00402 #endif 00403 00404 void 00405 insert(iterator __position, size_type __n, const _Tp& __x) 00406 { 00407 __glibcxx_check_insert(__position); 00408 _Base::insert(__position.base(), __n, __x); 00409 this->_M_invalidate_all(); 00410 } 00411 00412 template<class _InputIterator> 00413 void 00414 insert(iterator __position, 00415 _InputIterator __first, _InputIterator __last) 00416 { 00417 __glibcxx_check_insert_range(__position, __first, __last); 00418 _Base::insert(__position.base(), __gnu_debug::__base(__first), 00419 __gnu_debug::__base(__last)); 00420 this->_M_invalidate_all(); 00421 } 00422 00423 void 00424 pop_front() 00425 { 00426 __glibcxx_check_nonempty(); 00427 this->_M_invalidate_if(_Equal(_Base::begin())); 00428 _Base::pop_front(); 00429 } 00430 00431 void 00432 pop_back() 00433 { 00434 __glibcxx_check_nonempty(); 00435 this->_M_invalidate_if(_Equal(--_Base::end())); 00436 _Base::pop_back(); 00437 } 00438 00439 iterator 00440 erase(iterator __position) 00441 { 00442 __glibcxx_check_erase(__position); 00443 _Base_iterator __victim = __position.base(); 00444 if (__victim == _Base::begin() || __victim == _Base::end()-1) 00445 { 00446 this->_M_invalidate_if(_Equal(__victim)); 00447 return iterator(_Base::erase(__victim), this); 00448 } 00449 else 00450 { 00451 _Base_iterator __res = _Base::erase(__victim); 00452 this->_M_invalidate_all(); 00453 return iterator(__res, this); 00454 } 00455 } 00456 00457 iterator 00458 erase(iterator __first, iterator __last) 00459 { 00460 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00461 // 151. can't currently clear() empty container 00462 __glibcxx_check_erase_range(__first, __last); 00463 00464 if (__first.base() == __last.base()) 00465 return __first; 00466 else if (__first.base() == _Base::begin() 00467 || __last.base() == _Base::end()) 00468 { 00469 this->_M_detach_singular(); 00470 for (_Base_iterator __position = __first.base(); 00471 __position != __last.base(); ++__position) 00472 { 00473 this->_M_invalidate_if(_Equal(__position)); 00474 } 00475 __try 00476 { 00477 return iterator(_Base::erase(__first.base(), __last.base()), 00478 this); 00479 } 00480 __catch(...) 00481 { 00482 this->_M_revalidate_singular(); 00483 __throw_exception_again; 00484 } 00485 } 00486 else 00487 { 00488 _Base_iterator __res = _Base::erase(__first.base(), 00489 __last.base()); 00490 this->_M_invalidate_all(); 00491 return iterator(__res, this); 00492 } 00493 } 00494 00495 void 00496 swap(deque& __x) 00497 { 00498 _Base::swap(__x); 00499 this->_M_swap(__x); 00500 } 00501 00502 void 00503 clear() 00504 { 00505 _Base::clear(); 00506 this->_M_invalidate_all(); 00507 } 00508 00509 _Base& 00510 _M_base() { return *this; } 00511 00512 const _Base& 00513 _M_base() const { return *this; } 00514 }; 00515 00516 template<typename _Tp, typename _Alloc> 00517 inline bool 00518 operator==(const deque<_Tp, _Alloc>& __lhs, 00519 const deque<_Tp, _Alloc>& __rhs) 00520 { return __lhs._M_base() == __rhs._M_base(); } 00521 00522 template<typename _Tp, typename _Alloc> 00523 inline bool 00524 operator!=(const deque<_Tp, _Alloc>& __lhs, 00525 const deque<_Tp, _Alloc>& __rhs) 00526 { return __lhs._M_base() != __rhs._M_base(); } 00527 00528 template<typename _Tp, typename _Alloc> 00529 inline bool 00530 operator<(const deque<_Tp, _Alloc>& __lhs, 00531 const deque<_Tp, _Alloc>& __rhs) 00532 { return __lhs._M_base() < __rhs._M_base(); } 00533 00534 template<typename _Tp, typename _Alloc> 00535 inline bool 00536 operator<=(const deque<_Tp, _Alloc>& __lhs, 00537 const deque<_Tp, _Alloc>& __rhs) 00538 { return __lhs._M_base() <= __rhs._M_base(); } 00539 00540 template<typename _Tp, typename _Alloc> 00541 inline bool 00542 operator>=(const deque<_Tp, _Alloc>& __lhs, 00543 const deque<_Tp, _Alloc>& __rhs) 00544 { return __lhs._M_base() >= __rhs._M_base(); } 00545 00546 template<typename _Tp, typename _Alloc> 00547 inline bool 00548 operator>(const deque<_Tp, _Alloc>& __lhs, 00549 const deque<_Tp, _Alloc>& __rhs) 00550 { return __lhs._M_base() > __rhs._M_base(); } 00551 00552 template<typename _Tp, typename _Alloc> 00553 inline void 00554 swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs) 00555 { __lhs.swap(__rhs); } 00556 00557 } // namespace __debug 00558 } // namespace std 00559 00560 #endif