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