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) 46 template <class _Tp, class _Alloc> 47 inline _Tp* 48 value_type(const _STLP_PRIV _DBG_iter_base< _STLP_NON_DBG_LIST >&) 49 { return (_Tp*)0; } 50 template <class _Tp, class _Alloc> 51 inline bidirectional_iterator_tag 52 iterator_category(const _STLP_PRIV _DBG_iter_base< _STLP_NON_DBG_LIST >&) 53 { return bidirectional_iterator_tag(); } 54 #endif 55 56 template <class _Tp, _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Tp>) > 57 class 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 70 public: 71 __IMPORT_CONTAINER_TYPEDEFS(_Base) 72 73 public: 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 79 private: 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 90 public: 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 #if !defined (_STLP_NO_MOVE_SEMANTIC) 108 list(__move_source<_Self> src) 109 : _M_non_dbg_impl(__move_source<_Base>(src.get()._M_non_dbg_impl)), 110 _M_iter_list(&_M_non_dbg_impl) { 111 # if defined (_STLP_NO_EXTENSIONS) || (_STLP_DEBUG_LEVEL == _STLP_STANDARD_DBG_LEVEL) 112 src.get()._M_iter_list._Invalidate_all(); 113 # else 114 src.get()._M_iter_list._Set_owner(_M_iter_list); 115 # endif 116 } 117 #endif 118 119 #if defined (_STLP_MEMBER_TEMPLATES) 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 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER) 202 void _M_swap_workaround(_Self& __x) { swap(__x); } 203 #endif 204 205 #if !defined(_STLP_DONT_SUP_DFLT_PARAM) && !defined(_STLP_NO_ANACHRONISMS) 206 iterator insert(iterator __pos, const _Tp& __x = _Tp()) { 207 #else 208 iterator insert(iterator __pos, const _Tp& __x) { 209 #endif /*!_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/ 210 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list,__pos)) 211 return iterator(&_M_iter_list,_M_non_dbg_impl.insert(__pos._M_iterator, __x) ); 212 } 213 214 #if defined(_STLP_DONT_SUP_DFLT_PARAM) && !defined(_STLP_NO_ANACHRONISMS) 215 iterator insert(iterator __pos) { return insert(__pos, _STLP_DEFAULT_CONSTRUCTED(_Tp)); } 216 #endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/ 217 218 #if defined (_STLP_MEMBER_TEMPLATES) 219 template <class _InputIterator> 220 void insert(iterator __pos, _InputIterator __first, _InputIterator __last) { 221 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos)) 222 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 223 _M_non_dbg_impl.insert(__pos._M_iterator, 224 _STLP_PRIV _Non_Dbg_iter(__first), _STLP_PRIV _Non_Dbg_iter(__last)); 225 } 226 #endif 227 228 #if !defined (_STLP_MEMBER_TEMPLATES) 229 void insert(iterator __pos, const _Tp* __first, const _Tp* __last) { 230 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list,__pos)) 231 _STLP_DEBUG_CHECK(_STLP_PRIV __check_ptr_range(__first, __last)) 232 _M_non_dbg_impl.insert(__pos._M_iterator, __first, __last); 233 } 234 #endif 235 236 #if !defined (_STLP_MEMBER_TEMPLATES) || !defined (_STLP_NO_METHOD_SPECIALIZATION) 237 void insert(iterator __pos, 238 const_iterator __first, const_iterator __last) { 239 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos)) 240 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 241 # if (_STLP_DEBUG_LEVEL == _STLP_STANDARD_DBG_LEVEL) 242 _STLP_STD_DEBUG_CHECK(__check_if_not_owner(&_M_iter_list, __first)) 243 # endif 244 _M_non_dbg_impl.insert(__pos._M_iterator, __first._M_iterator, __last._M_iterator); 245 } 246 void insert(iterator __pos, 247 iterator __first, iterator __last) { 248 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos)) 249 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 250 # if (_STLP_DEBUG_LEVEL == _STLP_STANDARD_DBG_LEVEL) 251 _STLP_STD_DEBUG_CHECK(__check_if_not_owner(&_M_iter_list, __first)) 252 # endif 253 _M_non_dbg_impl.insert(__pos._M_iterator, __first._M_iterator, __last._M_iterator); 254 } 255 #endif 256 257 void insert(iterator __pos, size_type __n, const _Tp& __x) { 258 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list,__pos)) 259 _M_non_dbg_impl.insert(__pos._M_iterator, __n, __x); 260 } 261 262 void push_back(const_reference __x) { _M_non_dbg_impl.push_back(__x); } 263 void pop_back() { 264 _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER) 265 _Invalidate_iterator(end()); 266 _M_non_dbg_impl.pop_back(); 267 } 268 269 void push_front(const_reference __x) { _M_non_dbg_impl.push_front(__x); } 270 void pop_front() { 271 _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER) 272 _Invalidate_iterator(begin()); 273 _M_non_dbg_impl.pop_front(); 274 } 275 276 iterator erase(iterator __pos) { 277 _STLP_DEBUG_CHECK(_STLP_PRIV _Dereferenceable(__pos)) 278 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list,__pos)) 279 _Invalidate_iterator(__pos); 280 return iterator(&_M_iter_list,_M_non_dbg_impl.erase(__pos._M_iterator)); 281 } 282 iterator erase(iterator __first, iterator __last) { 283 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last, begin(), end())) 284 _Invalidate_iterators(__first, __last); 285 return iterator (&_M_iter_list, _M_non_dbg_impl.erase(__first._M_iterator, __last._M_iterator)); 286 } 287 288 #if !defined(_STLP_DONT_SUP_DFLT_PARAM) 289 void resize(size_type __new_size, const _Tp& __x = _Tp()) { 290 #else 291 void resize(size_type __new_size, const _Tp& __x) { 292 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/ 293 _Base_iterator __i = _M_non_dbg_impl.begin(); 294 size_type __len = 0; 295 for ( ; __i != _M_non_dbg_impl.end() && __len < __new_size; ++__i, ++__len); 296 297 if (__len == __new_size) 298 erase(iterator(&_M_iter_list, __i), end()); 299 else // __i == end() 300 _M_non_dbg_impl.insert(_M_non_dbg_impl.end(), __new_size - __len, __x); 301 } 302 303 #if defined(_STLP_DONT_SUP_DFLT_PARAM) 304 void resize(size_type __new_size) { resize(__new_size, _STLP_DEFAULT_CONSTRUCTED(_Tp)); } 305 #endif 306 307 #if defined (_STLP_MEMBER_TEMPLATES) 308 template <class _InputIterator> 309 void assign(_InputIterator __first, _InputIterator __last) { 310 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 311 _M_non_dbg_impl.assign(_STLP_PRIV _Non_Dbg_iter(__first), _STLP_PRIV _Non_Dbg_iter(__last)); 312 _Invalidate_iterators(begin(), end()); 313 } 314 #else 315 void assign(const _Tp* __first, const _Tp* __last) { 316 _STLP_DEBUG_CHECK(_STLP_PRIV __check_ptr_range(__first, __last)) 317 _M_non_dbg_impl.assign(__first, __last); 318 _Invalidate_iterators(begin(), end()); 319 } 320 321 void assign(iterator __first, iterator __last) { 322 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 323 _M_non_dbg_impl.assign(__first._M_iterator, __last._M_iterator); 324 _Invalidate_iterators(begin(), end()); 325 } 326 327 void assign(const_iterator __first, const_iterator __last) { 328 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last)) 329 _M_non_dbg_impl.assign(__first._M_iterator, __last._M_iterator); 330 _Invalidate_iterators(begin(), end()); 331 } 332 #endif 333 334 void assign(size_type __n, const _Tp& __val) { 335 _Invalidate_iterators(begin(), end()); 336 _M_non_dbg_impl.assign(__n, __val); 337 } 338 339 void remove(const _Tp& __x) { 340 _Base_iterator __first = _M_non_dbg_impl.begin(), __last = _M_non_dbg_impl.end(); 341 while (__first != __last) { 342 _Base_iterator __next = __first; 343 ++__next; 344 if (__x == *__first) { 345 _Invalidate_iterator(iterator(&_M_iter_list, __first)); 346 _M_non_dbg_impl.erase(__first); 347 } 348 __first = __next; 349 } 350 } 351 352 void clear() { 353 _Invalidate_iterators(begin(), end()); 354 _M_non_dbg_impl.clear(); 355 } 356 357 public: 358 void splice(iterator __pos, _Self& __x) { 359 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list,__pos)) 360 _M_non_dbg_impl.splice(__pos._M_iterator, __x._M_non_dbg_impl); 361 #if (_STLP_DEBUG_LEVEL != _STLP_STANDARD_DBG_LEVEL) 362 if (get_allocator() == __x.get_allocator()) 363 __x._M_iter_list._Set_owner(_M_iter_list); 364 else 365 #endif 366 // Std: 23.2.2.4:4 367 // end iterator is not invalidated: 368 __x._Invalidate_iterators(__x.begin(), __x.end()); 369 } 370 371 void splice(iterator __pos, _Self& __x, iterator __i) { 372 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list,__pos)) 373 _STLP_DEBUG_CHECK(_STLP_PRIV _Dereferenceable(__i)) 374 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&(__x._M_iter_list),__i)) 375 _M_non_dbg_impl.splice(__pos._M_iterator, __x._M_non_dbg_impl, __i._M_iterator); 376 #if (_STLP_DEBUG_LEVEL != _STLP_STANDARD_DBG_LEVEL) 377 if (get_allocator() == __x.get_allocator()) 378 _STLP_PRIV __change_ite_owner(__i, &_M_iter_list); 379 else 380 #endif 381 // Std: 23.2.2.4:7 382 __x._Invalidate_iterator(__i); 383 } 384 385 void splice(iterator __pos, _Self& __x, iterator __first, iterator __last) { 386 _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos)) 387 _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last, __x.begin(), __x.end())) 388 _STLP_DEBUG_CHECK(this == &__x ? !_STLP_PRIV __check_range(__pos, __first, __last) : true) 389 #if (_STLP_DEBUG_LEVEL != _STLP_STANDARD_DBG_LEVEL) 390 if (this->get_allocator() == __x.get_allocator()) 391 _STLP_PRIV __change_range_owner(__first, __last, &_M_iter_list); 392 else 393 #endif 394 // Std: 23.2.2.4:12 395 __x._Invalidate_iterators(__first, __last); 396 _M_non_dbg_impl.splice(__pos._M_iterator, __x._M_non_dbg_impl, __first._M_iterator, __last._M_iterator); 397 } 398 399 void merge(_Self& __x) { 400 #if !defined (_STLP_NO_EXTENSIONS) 401 _STLP_DEBUG_CHECK(_STLP_STD::is_sorted(begin()._M_iterator, end()._M_iterator)) 402 _STLP_DEBUG_CHECK(_STLP_STD::is_sorted(__x.begin()._M_iterator, __x.end()._M_iterator)) 403 #endif 404 _M_non_dbg_impl.merge(__x._M_non_dbg_impl); 405 if (this->get_allocator() == __x.get_allocator()) { 406 __x._M_iter_list._Set_owner(_M_iter_list); 407 } 408 else { 409 __x._Invalidate_iterators(__x.begin(), __x.end()); 410 } 411 } 412 void reverse() { 413 _M_non_dbg_impl.reverse(); 414 } 415 void unique() { 416 _Base_iterator __first = _M_non_dbg_impl.begin(), __last = _M_non_dbg_impl.end(); 417 if (__first == __last) return; 418 _Base_iterator __next = __first; 419 while (++__next != __last) { 420 if (*__first == *__next) { 421 _Invalidate_iterator(iterator(&_M_iter_list, __next)); 422 _M_non_dbg_impl.erase(__next); 423 } 424 else 425 __first = __next; 426 __next = __first; 427 } 428 } 429 void sort() { 430 _M_non_dbg_impl.sort(); 431 } 432 433 #if defined (_STLP_MEMBER_TEMPLATES) 434 template <class _Predicate> 435 void remove_if(_Predicate __pred) { 436 _Base_iterator __first = _M_non_dbg_impl.begin(), __last = _M_non_dbg_impl.end(); 437 while (__first != __last) { 438 _Base_iterator __next = __first; 439 ++__next; 440 if (__pred(*__first)) { 441 _Invalidate_iterator(iterator(&_M_iter_list, __first)); 442 _M_non_dbg_impl.erase(__first); 443 } 444 __first = __next; 445 } 446 } 447 448 template <class _BinaryPredicate> 449 void unique(_BinaryPredicate __binary_pred) { 450 _Base_iterator __first = _M_non_dbg_impl.begin(), __last = _M_non_dbg_impl.end(); 451 if (__first == __last) return; 452 _Base_iterator __next = __first; 453 while (++__next != __last) { 454 if (__binary_pred(*__first, *__next)) { 455 _Invalidate_iterator(iterator(&_M_iter_list, __next)); 456 _M_non_dbg_impl.erase(__next); 457 } 458 else 459 __first = __next; 460 __next = __first; 461 } 462 } 463 464 template <class _StrictWeakOrdering> 465 void merge(_Self& __x, _StrictWeakOrdering __comp) { 466 #if !defined (_STLP_NO_EXTENSIONS) 467 _STLP_DEBUG_CHECK(_STLP_STD::is_sorted(_M_non_dbg_impl.begin(), _M_non_dbg_impl.end(), __comp)) 468 _STLP_DEBUG_CHECK(_STLP_STD::is_sorted(__x.begin()._M_iterator, __x.end()._M_iterator, __comp)) 469 #endif 470 _M_non_dbg_impl.merge(__x._M_non_dbg_impl, __comp); 471 if (this->get_allocator() == __x.get_allocator()) { 472 __x._M_iter_list._Set_owner(_M_iter_list); 473 } 474 else { 475 __x._Invalidate_iterators(__x.begin(), __x.end()); 476 } 477 } 478 479 template <class _StrictWeakOrdering> 480 void sort(_StrictWeakOrdering __comp) { 481 _M_non_dbg_impl.sort(__comp); 482 } 483 #endif 484 }; 485 486 487 _STLP_END_NAMESPACE 488 489 #undef _STLP_NON_DBG_LIST 490 491 #endif /* _STLP_INTERNAL_LIST_H */ 492 493 // Local Variables: 494 // mode:C++ 495 // End: 496
