libstdc++
|
00001 // Debugging deque implementation -*- C++ -*- 00002 00003 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 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 00038 { 00039 namespace __debug 00040 { 00041 template<typename _Tp, typename _Allocator = std::allocator<_Tp> > 00042 class deque 00043 : public _GLIBCXX_STD_D::deque<_Tp, _Allocator>, 00044 public __gnu_debug::_Safe_sequence<deque<_Tp, _Allocator> > 00045 { 00046 typedef _GLIBCXX_STD_D::deque<_Tp, _Allocator> _Base; 00047 typedef __gnu_debug::_Safe_sequence<deque> _Safe_base; 00048 00049 public: 00050 typedef typename _Base::reference reference; 00051 typedef typename _Base::const_reference const_reference; 00052 00053 typedef __gnu_debug::_Safe_iterator<typename _Base::iterator,deque> 00054 iterator; 00055 typedef __gnu_debug::_Safe_iterator<typename _Base::const_iterator,deque> 00056 const_iterator; 00057 00058 typedef typename _Base::size_type size_type; 00059 typedef typename _Base::difference_type difference_type; 00060 00061 typedef _Tp value_type; 00062 typedef _Allocator allocator_type; 00063 typedef typename _Base::pointer pointer; 00064 typedef typename _Base::const_pointer const_pointer; 00065 typedef std::reverse_iterator<iterator> reverse_iterator; 00066 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00067 00068 // 23.2.1.1 construct/copy/destroy: 00069 explicit deque(const _Allocator& __a = _Allocator()) 00070 : _Base(__a) { } 00071 00072 explicit deque(size_type __n, const _Tp& __value = _Tp(), 00073 const _Allocator& __a = _Allocator()) 00074 : _Base(__n, __value, __a) { } 00075 00076 template<class _InputIterator> 00077 deque(_InputIterator __first, _InputIterator __last, 00078 const _Allocator& __a = _Allocator()) 00079 : _Base(__gnu_debug::__check_valid_range(__first, __last), __last, __a) 00080 { } 00081 00082 deque(const deque& __x) 00083 : _Base(__x), _Safe_base() { } 00084 00085 deque(const _Base& __x) 00086 : _Base(__x), _Safe_base() { } 00087 00088 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00089 deque(deque&& __x) 00090 : _Base(std::forward<deque>(__x)), _Safe_base() 00091 { this->_M_swap(__x); } 00092 00093 deque(initializer_list<value_type> __l, 00094 const allocator_type& __a = allocator_type()) 00095 : _Base(__l, __a), _Safe_base() { } 00096 #endif 00097 00098 ~deque() { } 00099 00100 deque& 00101 operator=(const deque& __x) 00102 { 00103 *static_cast<_Base*>(this) = __x; 00104 this->_M_invalidate_all(); 00105 return *this; 00106 } 00107 00108 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00109 deque& 00110 operator=(deque&& __x) 00111 { 00112 // NB: DR 675. 00113 clear(); 00114 swap(__x); 00115 return *this; 00116 } 00117 00118 deque& 00119 operator=(initializer_list<value_type> __l) 00120 { 00121 *static_cast<_Base*>(this) = __l; 00122 this->_M_invalidate_all(); 00123 return *this; 00124 } 00125 #endif 00126 00127 template<class _InputIterator> 00128 void 00129 assign(_InputIterator __first, _InputIterator __last) 00130 { 00131 __glibcxx_check_valid_range(__first, __last); 00132 _Base::assign(__first, __last); 00133 this->_M_invalidate_all(); 00134 } 00135 00136 void 00137 assign(size_type __n, const _Tp& __t) 00138 { 00139 _Base::assign(__n, __t); 00140 this->_M_invalidate_all(); 00141 } 00142 00143 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00144 void 00145 assign(initializer_list<value_type> __l) 00146 { 00147 _Base::assign(__l); 00148 this->_M_invalidate_all(); 00149 } 00150 #endif 00151 00152 using _Base::get_allocator; 00153 00154 // iterators: 00155 iterator 00156 begin() 00157 { return iterator(_Base::begin(), this); } 00158 00159 const_iterator 00160 begin() const 00161 { return const_iterator(_Base::begin(), this); } 00162 00163 iterator 00164 end() 00165 { return iterator(_Base::end(), this); } 00166 00167 const_iterator 00168 end() const 00169 { return const_iterator(_Base::end(), this); } 00170 00171 reverse_iterator 00172 rbegin() 00173 { return reverse_iterator(end()); } 00174 00175 const_reverse_iterator 00176 rbegin() const 00177 { return const_reverse_iterator(end()); } 00178 00179 reverse_iterator 00180 rend() 00181 { return reverse_iterator(begin()); } 00182 00183 const_reverse_iterator 00184 rend() const 00185 { return const_reverse_iterator(begin()); } 00186 00187 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00188 const_iterator 00189 cbegin() const 00190 { return const_iterator(_Base::begin(), this); } 00191 00192 const_iterator 00193 cend() const 00194 { return const_iterator(_Base::end(), this); } 00195 00196 const_reverse_iterator 00197 crbegin() const 00198 { return const_reverse_iterator(end()); } 00199 00200 const_reverse_iterator 00201 crend() const 00202 { return const_reverse_iterator(begin()); } 00203 #endif 00204 00205 // 23.2.1.2 capacity: 00206 using _Base::size; 00207 using _Base::max_size; 00208 00209 void 00210 resize(size_type __sz, _Tp __c = _Tp()) 00211 { 00212 typedef typename _Base::const_iterator _Base_const_iterator; 00213 typedef __gnu_debug::_After_nth_from<_Base_const_iterator> _After_nth; 00214 00215 bool __invalidate_all = __sz > this->size(); 00216 if (__sz < this->size()) 00217 this->_M_invalidate_if(_After_nth(__sz, _M_base().begin())); 00218 00219 _Base::resize(__sz, __c); 00220 00221 if (__invalidate_all) 00222 this->_M_invalidate_all(); 00223 } 00224 00225 using _Base::empty; 00226 00227 // element access: 00228 reference 00229 operator[](size_type __n) 00230 { 00231 __glibcxx_check_subscript(__n); 00232 return _M_base()[__n]; 00233 } 00234 00235 const_reference 00236 operator[](size_type __n) const 00237 { 00238 __glibcxx_check_subscript(__n); 00239 return _M_base()[__n]; 00240 } 00241 00242 using _Base::at; 00243 00244 reference 00245 front() 00246 { 00247 __glibcxx_check_nonempty(); 00248 return _Base::front(); 00249 } 00250 00251 const_reference 00252 front() const 00253 { 00254 __glibcxx_check_nonempty(); 00255 return _Base::front(); 00256 } 00257 00258 reference 00259 back() 00260 { 00261 __glibcxx_check_nonempty(); 00262 return _Base::back(); 00263 } 00264 00265 const_reference 00266 back() const 00267 { 00268 __glibcxx_check_nonempty(); 00269 return _Base::back(); 00270 } 00271 00272 // 23.2.1.3 modifiers: 00273 void 00274 push_front(const _Tp& __x) 00275 { 00276 _Base::push_front(__x); 00277 this->_M_invalidate_all(); 00278 } 00279 00280 void 00281 push_back(const _Tp& __x) 00282 { 00283 _Base::push_back(__x); 00284 this->_M_invalidate_all(); 00285 } 00286 00287 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00288 void 00289 push_front(_Tp&& __x) 00290 { emplace_front(std::move(__x)); } 00291 00292 void 00293 push_back(_Tp&& __x) 00294 { emplace_back(std::move(__x)); } 00295 00296 template<typename... _Args> 00297 void 00298 emplace_front(_Args&&... __args) 00299 { 00300 _Base::emplace_front(std::forward<_Args>(__args)...); 00301 this->_M_invalidate_all(); 00302 } 00303 00304 template<typename... _Args> 00305 void 00306 emplace_back(_Args&&... __args) 00307 { 00308 _Base::emplace_back(std::forward<_Args>(__args)...); 00309 this->_M_invalidate_all(); 00310 } 00311 00312 template<typename... _Args> 00313 iterator 00314 emplace(iterator __position, _Args&&... __args) 00315 { 00316 __glibcxx_check_insert(__position); 00317 typename _Base::iterator __res = _Base::emplace(__position.base(), 00318 std::forward<_Args>(__args)...); 00319 this->_M_invalidate_all(); 00320 return iterator(__res, this); 00321 } 00322 #endif 00323 00324 iterator 00325 insert(iterator __position, const _Tp& __x) 00326 { 00327 __glibcxx_check_insert(__position); 00328 typename _Base::iterator __res = _Base::insert(__position.base(), __x); 00329 this->_M_invalidate_all(); 00330 return iterator(__res, this); 00331 } 00332 00333 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00334 iterator 00335 insert(iterator __position, _Tp&& __x) 00336 { return emplace(__position, std::move(__x)); } 00337 00338 void 00339 insert(iterator __p, initializer_list<value_type> __l) 00340 { 00341 _Base::insert(__p, __l); 00342 this->_M_invalidate_all(); 00343 } 00344 #endif 00345 00346 void 00347 insert(iterator __position, size_type __n, const _Tp& __x) 00348 { 00349 __glibcxx_check_insert(__position); 00350 _Base::insert(__position.base(), __n, __x); 00351 this->_M_invalidate_all(); 00352 } 00353 00354 template<class _InputIterator> 00355 void 00356 insert(iterator __position, 00357 _InputIterator __first, _InputIterator __last) 00358 { 00359 __glibcxx_check_insert_range(__position, __first, __last); 00360 _Base::insert(__position.base(), __first, __last); 00361 this->_M_invalidate_all(); 00362 } 00363 00364 void 00365 pop_front() 00366 { 00367 __glibcxx_check_nonempty(); 00368 iterator __victim = begin(); 00369 __victim._M_invalidate(); 00370 _Base::pop_front(); 00371 } 00372 00373 void 00374 pop_back() 00375 { 00376 __glibcxx_check_nonempty(); 00377 iterator __victim = end(); 00378 --__victim; 00379 __victim._M_invalidate(); 00380 _Base::pop_back(); 00381 } 00382 00383 iterator 00384 erase(iterator __position) 00385 { 00386 __glibcxx_check_erase(__position); 00387 if (__position == begin() || __position == end()-1) 00388 { 00389 __position._M_invalidate(); 00390 return iterator(_Base::erase(__position.base()), this); 00391 } 00392 else 00393 { 00394 typename _Base::iterator __res = _Base::erase(__position.base()); 00395 this->_M_invalidate_all(); 00396 return iterator(__res, this); 00397 } 00398 } 00399 00400 iterator 00401 erase(iterator __first, iterator __last) 00402 { 00403 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00404 // 151. can't currently clear() empty container 00405 __glibcxx_check_erase_range(__first, __last); 00406 if (__first == begin() || __last == end()) 00407 { 00408 this->_M_detach_singular(); 00409 for (iterator __position = __first; __position != __last; ) 00410 { 00411 iterator __victim = __position++; 00412 __victim._M_invalidate(); 00413 } 00414 __try 00415 { 00416 return iterator(_Base::erase(__first.base(), __last.base()), 00417 this); 00418 } 00419 __catch(...) 00420 { 00421 this->_M_revalidate_singular(); 00422 __throw_exception_again; 00423 } 00424 } 00425 else 00426 { 00427 typename _Base::iterator __res = _Base::erase(__first.base(), 00428 __last.base()); 00429 this->_M_invalidate_all(); 00430 return iterator(__res, this); 00431 } 00432 } 00433 00434 void 00435 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00436 swap(deque&& __x) 00437 #else 00438 swap(deque& __x) 00439 #endif 00440 { 00441 _Base::swap(__x); 00442 this->_M_swap(__x); 00443 } 00444 00445 void 00446 clear() 00447 { 00448 _Base::clear(); 00449 this->_M_invalidate_all(); 00450 } 00451 00452 _Base& 00453 _M_base() { return *this; } 00454 00455 const _Base& 00456 _M_base() const { return *this; } 00457 }; 00458 00459 template<typename _Tp, typename _Alloc> 00460 inline bool 00461 operator==(const deque<_Tp, _Alloc>& __lhs, 00462 const deque<_Tp, _Alloc>& __rhs) 00463 { return __lhs._M_base() == __rhs._M_base(); } 00464 00465 template<typename _Tp, typename _Alloc> 00466 inline bool 00467 operator!=(const deque<_Tp, _Alloc>& __lhs, 00468 const deque<_Tp, _Alloc>& __rhs) 00469 { return __lhs._M_base() != __rhs._M_base(); } 00470 00471 template<typename _Tp, typename _Alloc> 00472 inline bool 00473 operator<(const deque<_Tp, _Alloc>& __lhs, 00474 const deque<_Tp, _Alloc>& __rhs) 00475 { return __lhs._M_base() < __rhs._M_base(); } 00476 00477 template<typename _Tp, typename _Alloc> 00478 inline bool 00479 operator<=(const deque<_Tp, _Alloc>& __lhs, 00480 const deque<_Tp, _Alloc>& __rhs) 00481 { return __lhs._M_base() <= __rhs._M_base(); } 00482 00483 template<typename _Tp, typename _Alloc> 00484 inline bool 00485 operator>=(const deque<_Tp, _Alloc>& __lhs, 00486 const deque<_Tp, _Alloc>& __rhs) 00487 { return __lhs._M_base() >= __rhs._M_base(); } 00488 00489 template<typename _Tp, typename _Alloc> 00490 inline bool 00491 operator>(const deque<_Tp, _Alloc>& __lhs, 00492 const deque<_Tp, _Alloc>& __rhs) 00493 { return __lhs._M_base() > __rhs._M_base(); } 00494 00495 template<typename _Tp, typename _Alloc> 00496 inline void 00497 swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>& __rhs) 00498 { __lhs.swap(__rhs); } 00499 00500 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00501 template<typename _Tp, typename _Alloc> 00502 inline void 00503 swap(deque<_Tp, _Alloc>&& __lhs, deque<_Tp, _Alloc>& __rhs) 00504 { __lhs.swap(__rhs); } 00505 00506 template<typename _Tp, typename _Alloc> 00507 inline void 00508 swap(deque<_Tp, _Alloc>& __lhs, deque<_Tp, _Alloc>&& __rhs) 00509 { __lhs.swap(__rhs); } 00510 #endif 00511 00512 } // namespace __debug 00513 } // namespace std 00514 00515 #endif