_list.h revision 9720d5f59b9c1f5d1b9ecbc9173dbcb71bd557be
1/* 2 * 3 * Copyright (c) 1994 4 * Hewlett-Packard Company 5 * 6 * Copyright (c) 1996,1997 7 * Silicon Graphics Computer Systems, Inc. 8 * 9 * Copyright (c) 1997 10 * Moscow Center for SPARC Technology 11 * 12 * Copyright (c) 1999 13 * Boris Fomitchev 14 * 15 * This material is provided "as is", with absolutely no warranty expressed 16 * or implied. Any use is at your own risk. 17 * 18 * Permission to use or copy this software for any purpose is hereby granted 19 * without fee, provided the above notices are retained on all copies. 20 * Permission to modify the code and to distribute modified code is granted, 21 * provided the above notices are retained, and a notice that the code was 22 * modified is included with the above copyright notice. 23 * 24 */ 25 26/* NOTE: This is an internal header file, included by other STL headers. 27 * You should not attempt to use it directly. 28 */ 29 30#ifndef _STLP_INTERNAL_DBG_LIST_H 31#define _STLP_INTERNAL_DBG_LIST_H 32 33#ifndef _STLP_INTERNAL_ALGO_H 34# include <stl/_algo.h> 35#endif 36 37#ifndef _STLP_DBG_ITERATOR_H 38# include <stl/debug/_iterator.h> 39#endif 40 41#define _STLP_NON_DBG_LIST _STLP_PRIV _STLP_NON_DBG_NAME(list) <_Tp, _Alloc> 42 43_STLP_BEGIN_NAMESPACE 44 45#if defined (_STLP_DEBUG_USE_DISTINCT_VALUE_TYPE_HELPERS) 46template <class _Tp, class _Alloc> 47inline _Tp* 48value_type(const _STLP_PRIV _DBG_iter_base< _STLP_NON_DBG_LIST >&) 49{ return (_Tp*)0; } 50template <class _Tp, class _Alloc> 51inline bidirectional_iterator_tag 52iterator_category(const _STLP_PRIV _DBG_iter_base< _STLP_NON_DBG_LIST >&) 53{ return bidirectional_iterator_tag(); } 54#endif 55 56template <class _Tp, _STLP_DEFAULT_ALLOCATOR_SELECT(_Tp) > 57class list : 58#if !defined (__DMC__) 59 private 60#endif 61 _STLP_PRIV __construct_checker<_STLP_NON_DBG_LIST > 62#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) 63 , public __stlport_class<list<_Tp, _Alloc> > 64#endif 65{ 66 typedef _STLP_NON_DBG_LIST _Base; 67 typedef list<_Tp, _Alloc> _Self; 68 typedef _STLP_PRIV __construct_checker<_STLP_NON_DBG_LIST > _ConstructCheck; 69 70public: 71 __IMPORT_CONTAINER_TYPEDEFS(_Base) 72 73public: 74 typedef _STLP_PRIV _DBG_iter<_Base, _STLP_PRIV _DbgTraits<_Nonconst_traits<value_type> > > iterator; 75 typedef _STLP_PRIV _DBG_iter<_Base, _STLP_PRIV _DbgTraits<_Const_traits<value_type> > > const_iterator; 76 77 _STLP_DECLARE_BIDIRECTIONAL_REVERSE_ITERATORS; 78 79private: 80 _Base _M_non_dbg_impl; 81 _STLP_PRIV __owned_list _M_iter_list; 82 83 void _Invalidate_iterator(const iterator& __it) 84 { _STLP_PRIV __invalidate_iterator(&_M_iter_list, __it); } 85 void _Invalidate_iterators(const iterator& __first, const iterator& __last) 86 { _STLP_PRIV __invalidate_range(&_M_iter_list, __first, __last); } 87 88 typedef typename _Base::iterator _Base_iterator; 89 90public: 91 explicit list(const allocator_type& __a = allocator_type()) : 92 _M_non_dbg_impl(__a), _M_iter_list(&_M_non_dbg_impl) {} 93 94#if !defined(_STLP_DONT_SUP_DFLT_PARAM) 95 explicit list(size_type __n, const _Tp& __x = _Tp(), 96#else 97 list(size_type __n, const _Tp& __x, 98#endif /*!_STLP_DONT_SUP_DFLT_PARAM*/ 99 const allocator_type& __a = allocator_type()) 100 : _M_non_dbg_impl(__n, __x, __a), _M_iter_list(&_M_non_dbg_impl) {} 101 102#if defined(_STLP_DONT_SUP_DFLT_PARAM) 103 explicit list(size_type __n) 104 : _M_non_dbg_impl(__n), _M_iter_list(&_M_non_dbg_impl) {} 105#endif /*_STLP_DONT_SUP_DFLT_PARAM*/ 106 107 list(__move_source<_Self> src) 108 : _M_non_dbg_impl(__move_source<_Base>(src.get()._M_non_dbg_impl)), 109 _M_iter_list(&_M_non_dbg_impl) { 110#if defined (_STLP_NO_EXTENSIONS) || (_STLP_DEBUG_LEVEL == _STLP_STANDARD_DBG_LEVEL) 111 src.get()._M_iter_list._Invalidate_all(); 112#else 113 src.get()._M_iter_list._Set_owner(_M_iter_list); 114#endif 115 } 116 117#if defined (_STLP_MEMBER_TEMPLATES) 118 // We don't need any dispatching tricks here, because insert does all of 119 // that anyway. 120 template <class _InputIterator> 121 list(_InputIterator __first, _InputIterator __last, 122 const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL) 123 : _ConstructCheck(__first, __last), 124 _M_non_dbg_impl(_STLP_PRIV _Non_Dbg_iter(__first), _STLP_PRIV _Non_Dbg_iter(__last), __a), 125 _M_iter_list(&_M_non_dbg_impl) {} 126# if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS) 127 template <class _InputIterator> 128 list(_InputIterator __first, _InputIterator __last) 129 : _ConstructCheck(__first, __last), 130 _M_non_dbg_impl(_STLP_PRIV _Non_Dbg_iter(__first), _STLP_PRIV _Non_Dbg_iter(__last)), 131 _M_iter_list(&_M_non_dbg_impl) {} 132# endif 133#else 134 135 list(const value_type* __first, const value_type* __last, 136 const allocator_type& __a = allocator_type()) 137 : _ConstructCheck(__first, __last), 138 _M_non_dbg_impl(__first, __last, __a), 139 _M_iter_list(&_M_non_dbg_impl) {} 140 list(const_iterator __first, const_iterator __last, 141 const allocator_type& __a = allocator_type()) 142 : _ConstructCheck(__first, __last), 143 _M_non_dbg_impl(__first._M_iterator, __last._M_iterator, __a), 144 _M_iter_list(&_M_non_dbg_impl) {} 145 146#endif 147 148 list(const _Self& __x) : 149 _ConstructCheck(__x), 150 _M_non_dbg_impl(__x._M_non_dbg_impl) , _M_iter_list(&_M_non_dbg_impl) {} 151 152 _Self& operator=(const _Self& __x) { 153 if (this != &__x) { 154 //Should not invalidate end iterator 155 _Invalidate_iterators(begin(), end()); 156 _M_non_dbg_impl = __x._M_non_dbg_impl; 157 } 158 return *this; 159 } 160 161 allocator_type get_allocator() const { return _M_non_dbg_impl.get_allocator(); } 162 163 iterator begin() { return iterator(&_M_iter_list, _M_non_dbg_impl.begin()); } 164 const_iterator begin() const { return const_iterator(&_M_iter_list, _M_non_dbg_impl.begin()); } 165 166 iterator end() { return iterator(&_M_iter_list, _M_non_dbg_impl.end()); } 167 const_iterator end() const { return const_iterator(&_M_iter_list, _M_non_dbg_impl.end()); } 168 169 reverse_iterator rbegin() { return reverse_iterator(end()); } 170 reverse_iterator rend() { return reverse_iterator(begin()); } 171 172 const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } 173 const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } 174 175 size_type size() const { return _M_non_dbg_impl.size(); } 176 size_type max_size() const { return _M_non_dbg_impl.max_size(); } 177 bool empty() const { return _M_non_dbg_impl.empty(); } 178 179 // those are here to enforce checking 180 reference front() { 181 _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER) 182 return *begin(); 183 } 184 const_reference front() const { 185 _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER) 186 return *begin(); 187 } 188 reference back() { 189 _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER) 190 return *(--end()); 191 } 192 const_reference back() const { 193 _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER) 194 return *(--end()); 195 } 196 197 void swap(_Self& __x) { 198 _M_iter_list._Swap_owners(__x._M_iter_list); 199 _M_non_dbg_impl.swap(__x._M_non_dbg_impl); 200 } 201 202#if !defined(_STLP_DONT_SUP_DFLT_PARAM) && !defined(_STLP_NO_ANACHRONISMS) 203 iterator insert(iterator __pos, const _Tp& __x = _Tp()) { 204#else 205 iterator insert(iterator __pos, const _Tp& __x) { 206#endif /*!_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/ 207 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list,__pos)) 208 return iterator(&_M_iter_list,_M_non_dbg_impl.insert(__pos._M_iterator, __x) ); 209 } 210 211#if defined(_STLP_DONT_SUP_DFLT_PARAM) && !defined(_STLP_NO_ANACHRONISMS) 212 iterator insert(iterator __pos) { return insert(__pos, _STLP_DEFAULT_CONSTRUCTED(_Tp)); } 213#endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/ 214 215#if defined (_STLP_MEMBER_TEMPLATES) 216 template <class _InputIterator> 217 void insert(iterator __pos, _InputIterator __first, _InputIterator __last) { 218# if (_STLP_DEBUG_LEVEL == _STLP_STANDARD_DBG_LEVEL) 219 typedef typename _AreSameUnCVTypes<_InputIterator, iterator>::_Ret _IsListIterator; 220 typedef typename _AreSameUnCVTypes<_InputIterator, const_iterator>::_Ret _IsListConstIterator; 221 typedef typename _Lor2<_IsListIterator, _IsListConstIterator>::_Ret _DoCheck; 222# endif 223 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos)) 224 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 225 _STLP_STD_DEBUG_CHECK(__check_if_not_owner(&_M_iter_list, __first, _DoCheck())) 226 _M_non_dbg_impl.insert(__pos._M_iterator, 227 _STLP_PRIV _Non_Dbg_iter(__first), _STLP_PRIV _Non_Dbg_iter(__last)); 228 } 229#else 230 void insert(iterator __pos, const _Tp* __first, const _Tp* __last) { 231 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list,__pos)) 232 _STLP_DEBUG_CHECK(_STLP_PRIV __check_ptr_range(__first, __last)) 233 _M_non_dbg_impl.insert(__pos._M_iterator, __first, __last); 234 } 235 236 void insert(iterator __pos, 237 const_iterator __first, const_iterator __last) { 238 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos)) 239 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 240 _STLP_STD_DEBUG_CHECK(__check_if_not_owner(&_M_iter_list, __first, _DoCheck())) 241 _M_non_dbg_impl.insert(__pos._M_iterator, __first._M_iterator, __last._M_iterator); 242 } 243#endif 244 245 void insert(iterator __pos, size_type __n, const _Tp& __x) { 246 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list,__pos)) 247 _M_non_dbg_impl.insert(__pos._M_iterator, __n, __x); 248 } 249 250 void push_back(const_reference __x) { _M_non_dbg_impl.push_back(__x); } 251 void pop_back() { 252 _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER) 253 _Invalidate_iterator(end()); 254 _M_non_dbg_impl.pop_back(); 255 } 256 257 void push_front(const_reference __x) { _M_non_dbg_impl.push_front(__x); } 258 void pop_front() { 259 _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER) 260 _Invalidate_iterator(begin()); 261 _M_non_dbg_impl.pop_front(); 262 } 263 264 iterator erase(iterator __pos) { 265 _STLP_DEBUG_CHECK(_STLP_PRIV _Dereferenceable(__pos)) 266 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list,__pos)) 267 _Invalidate_iterator(__pos); 268 return iterator(&_M_iter_list,_M_non_dbg_impl.erase(__pos._M_iterator)); 269 } 270 iterator erase(iterator __first, iterator __last) { 271 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last, begin(), end())) 272 _Invalidate_iterators(__first, __last); 273 return iterator (&_M_iter_list, _M_non_dbg_impl.erase(__first._M_iterator, __last._M_iterator)); 274 } 275 276#if !defined(_STLP_DONT_SUP_DFLT_PARAM) 277 void resize(size_type __new_size, const _Tp& __x = _Tp()) { 278#else 279 void resize(size_type __new_size, const _Tp& __x) { 280#endif /*_STLP_DONT_SUP_DFLT_PARAM*/ 281 _Base_iterator __i = _M_non_dbg_impl.begin(); 282 size_type __len = 0; 283 for ( ; __i != _M_non_dbg_impl.end() && __len < __new_size; ++__i, ++__len); 284 285 if (__len == __new_size) 286 erase(iterator(&_M_iter_list, __i), end()); 287 else // __i == end() 288 _M_non_dbg_impl.insert(_M_non_dbg_impl.end(), __new_size - __len, __x); 289 } 290 291#if defined(_STLP_DONT_SUP_DFLT_PARAM) 292 void resize(size_type __new_size) { resize(__new_size, _STLP_DEFAULT_CONSTRUCTED(_Tp)); } 293#endif /*_STLP_DONT_SUP_DFLT_PARAM*/ 294 295#if defined (_STLP_MEMBER_TEMPLATES) 296private: 297 template <class _Integer> 298 void _M_assign_dispatch(_Integer __n, _Integer __val, 299 const __true_type& /*_IsIntegral*/) { 300 _M_check_assign(__n); 301 _M_non_dbg_impl.assign(__n, __val); 302 } 303 304 template <class _InputIter> 305 void _M_assign_dispatch(_InputIter __first, _InputIter __last, 306 const __false_type& /*_IsIntegral*/) { 307 size_type __len = distance(__first, __last); 308 _M_check_assign(__len); 309 _M_non_dbg_impl.assign(_STLP_PRIV _Non_Dbg_iter(__first), _STLP_PRIV _Non_Dbg_iter(__last)); 310 } 311 312public: 313 template <class _InputIterator> 314 void assign(_InputIterator __first, _InputIterator __last) { 315 typedef typename _IsIntegral<_InputIterator>::_Ret _Integral; 316 _M_assign_dispatch(__first, __last, _Integral()); 317 } 318#else 319 void assign(const _Tp* __first, const _Tp* __last) { 320 _STLP_DEBUG_CHECK(_STLP_PRIV __check_ptr_range(__first, __last)) 321 _M_non_dbg_impl.assign(__first, __last); 322 } 323 324 void assign(const_iterator __first, const_iterator __last) { 325 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 326 _M_non_dbg_impl.assign(__first._M_iterator, __last._M_iterator); 327 } 328#endif 329 330private: 331 void _M_check_assign(size_type __n) { 332 size_type __size = size(); 333 if (__n < __size) { 334 iterator __it = begin(); 335 advance(__it, __n + 1); 336 _Invalidate_iterators(__it, end()); 337 } 338 } 339 340public: 341 void assign(size_type __n, const _Tp& __val) { 342 _M_check_assign(__n); 343 _M_non_dbg_impl.assign(__n, __val); 344 } 345 346 void remove(const _Tp& __x) { 347 _Base_iterator __first = _M_non_dbg_impl.begin(), __last = _M_non_dbg_impl.end(); 348 while (__first != __last) { 349 _Base_iterator __next = __first; 350 ++__next; 351 if (__x == *__first) { 352 _Invalidate_iterator(iterator(&_M_iter_list, __first)); 353 _M_non_dbg_impl.erase(__first); 354 } 355 __first = __next; 356 } 357 } 358 359 void clear() { 360 _Invalidate_iterators(begin(), end()); 361 _M_non_dbg_impl.clear(); 362 } 363 364public: 365 void splice(iterator __pos, _Self& __x) { 366 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list,__pos)) 367 _M_non_dbg_impl.splice(__pos._M_iterator, __x._M_non_dbg_impl); 368#if (_STLP_DEBUG_LEVEL != _STLP_STANDARD_DBG_LEVEL) 369 if (get_allocator() == __x.get_allocator()) 370 __x._M_iter_list._Set_owner(_M_iter_list); 371 else 372#endif 373 // Std: 23.2.2.4:4 374 // end iterator is not invalidated: 375 __x._Invalidate_iterators(__x.begin(), __x.end()); 376 } 377 378 void splice(iterator __pos, _Self& __x, iterator __i) { 379 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list,__pos)) 380 _STLP_DEBUG_CHECK(_STLP_PRIV _Dereferenceable(__i)) 381 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&(__x._M_iter_list),__i)) 382 _M_non_dbg_impl.splice(__pos._M_iterator, __x._M_non_dbg_impl, __i._M_iterator); 383#if (_STLP_DEBUG_LEVEL != _STLP_STANDARD_DBG_LEVEL) 384 if (get_allocator() == __x.get_allocator()) 385 _STLP_PRIV __change_ite_owner(__i, &_M_iter_list); 386 else 387#endif 388 // Std: 23.2.2.4:7 389 __x._Invalidate_iterator(__i); 390 } 391 392 void splice(iterator __pos, _Self& __x, iterator __first, iterator __last) { 393 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos)) 394 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last, __x.begin(), __x.end())) 395 _STLP_DEBUG_CHECK(this == &__x ? !_STLP_PRIV __check_range(__pos, __first, __last) : true) 396#if (_STLP_DEBUG_LEVEL != _STLP_STANDARD_DBG_LEVEL) 397 if (this->get_allocator() == __x.get_allocator()) 398 _STLP_PRIV __change_range_owner(__first, __last, &_M_iter_list); 399 else 400#endif 401 // Std: 23.2.2.4:12 402 __x._Invalidate_iterators(__first, __last); 403 _M_non_dbg_impl.splice(__pos._M_iterator, __x._M_non_dbg_impl, __first._M_iterator, __last._M_iterator); 404 } 405 406 void merge(_Self& __x) { 407#if !defined (_STLP_NO_EXTENSIONS) 408 _STLP_DEBUG_CHECK(_STLP_STD::is_sorted(begin()._M_iterator, end()._M_iterator)) 409 _STLP_DEBUG_CHECK(_STLP_STD::is_sorted(__x.begin()._M_iterator, __x.end()._M_iterator)) 410#endif 411 _M_non_dbg_impl.merge(__x._M_non_dbg_impl); 412 if (this->get_allocator() == __x.get_allocator()) { 413 __x._M_iter_list._Set_owner(_M_iter_list); 414 } 415 else { 416 __x._Invalidate_iterators(__x.begin(), __x.end()); 417 } 418 } 419 void reverse() { 420 _M_non_dbg_impl.reverse(); 421 } 422 void unique() { 423 _Base_iterator __first = _M_non_dbg_impl.begin(), __last = _M_non_dbg_impl.end(); 424 if (__first == __last) return; 425 _Base_iterator __next = __first; 426 while (++__next != __last) { 427 if (*__first == *__next) { 428 _Invalidate_iterator(iterator(&_M_iter_list, __next)); 429 _M_non_dbg_impl.erase(__next); 430 } 431 else 432 __first = __next; 433 __next = __first; 434 } 435 } 436 void sort() { 437 _M_non_dbg_impl.sort(); 438 } 439 440#if defined (_STLP_MEMBER_TEMPLATES) 441 template <class _Predicate> 442 void remove_if(_Predicate __pred) { 443 _Base_iterator __first = _M_non_dbg_impl.begin(), __last = _M_non_dbg_impl.end(); 444 while (__first != __last) { 445 _Base_iterator __next = __first; 446 ++__next; 447 if (__pred(*__first)) { 448 _Invalidate_iterator(iterator(&_M_iter_list, __first)); 449 _M_non_dbg_impl.erase(__first); 450 } 451 __first = __next; 452 } 453 } 454 455 template <class _BinaryPredicate> 456 void unique(_BinaryPredicate __binary_pred) { 457 _Base_iterator __first = _M_non_dbg_impl.begin(), __last = _M_non_dbg_impl.end(); 458 if (__first == __last) return; 459 _Base_iterator __next = __first; 460 while (++__next != __last) { 461 if (__binary_pred(*__first, *__next)) { 462 _Invalidate_iterator(iterator(&_M_iter_list, __next)); 463 _M_non_dbg_impl.erase(__next); 464 } 465 else 466 __first = __next; 467 __next = __first; 468 } 469 } 470 471 template <class _StrictWeakOrdering> 472 void merge(_Self& __x, _StrictWeakOrdering __comp) { 473#if !defined (_STLP_NO_EXTENSIONS) 474 _STLP_DEBUG_CHECK(_STLP_STD::is_sorted(_M_non_dbg_impl.begin(), _M_non_dbg_impl.end(), __comp)) 475 _STLP_DEBUG_CHECK(_STLP_STD::is_sorted(__x.begin()._M_iterator, __x.end()._M_iterator, __comp)) 476#endif 477 _M_non_dbg_impl.merge(__x._M_non_dbg_impl, __comp); 478 if (this->get_allocator() == __x.get_allocator()) { 479 __x._M_iter_list._Set_owner(_M_iter_list); 480 } 481 else { 482 __x._Invalidate_iterators(__x.begin(), __x.end()); 483 } 484 } 485 486 template <class _StrictWeakOrdering> 487 void sort(_StrictWeakOrdering __comp) { 488 _M_non_dbg_impl.sort(__comp); 489 } 490#endif 491}; 492 493 494_STLP_END_NAMESPACE 495 496#undef _STLP_NON_DBG_LIST 497 498#endif /* _STLP_INTERNAL_LIST_H */ 499 500// Local Variables: 501// mode:C++ 502// End: 503