1 /* 2 * 3 * Copyright (c) 1996,1997 4 * Silicon Graphics Computer Systems, Inc. 5 * 6 * Copyright (c) 1997 7 * Moscow Center for SPARC Technology 8 * 9 * Copyright (c) 1999 10 * Boris Fomitchev 11 * 12 * This material is provided "as is", with absolutely no warranty expressed 13 * or implied. Any use is at your own risk. 14 * 15 * Permission to use or copy this software for any purpose is hereby granted 16 * without fee, provided the above notices are retained on all copies. 17 * Permission to modify the code and to distribute modified code is granted, 18 * provided the above notices are retained, and a notice that the code was 19 * modified is included with the above copyright notice. 20 * 21 */ 22 23 /* NOTE: This is an internal header file, included by other STL headers. 24 * You should not attempt to use it directly. 25 */ 26 27 #ifndef _STLP_INTERNAL_SLIST_H 28 #define _STLP_INTERNAL_SLIST_H 29 30 #ifndef _STLP_INTERNAL_ALGOBASE_H 31 # include <stl/_algobase.h> 32 #endif 33 34 #ifndef _STLP_INTERNAL_ALLOC_H 35 # include <stl/_alloc.h> 36 #endif 37 38 #ifndef _STLP_INTERNAL_ITERATOR_H 39 # include <stl/_iterator.h> 40 #endif 41 42 #ifndef _STLP_INTERNAL_CONSTRUCT_H 43 # include <stl/_construct.h> 44 #endif 45 46 #ifndef _STLP_INTERNAL_FUNCTION_BASE_H 47 # include <stl/_function_base.h> 48 #endif 49 50 #ifndef _STLP_INTERNAL_SLIST_BASE_H 51 # include <stl/_slist_base.h> 52 #endif 53 54 _STLP_BEGIN_NAMESPACE 55 56 _STLP_MOVE_TO_PRIV_NAMESPACE 57 58 template <class _Tp> 59 class _Slist_node : public _Slist_node_base { 60 public: 61 _Tp _M_data; 62 __TRIVIAL_STUFF(_Slist_node) 63 }; 64 65 struct _Slist_iterator_base { 66 typedef size_t size_type; 67 typedef ptrdiff_t difference_type; 68 typedef forward_iterator_tag iterator_category; 69 70 _Slist_node_base *_M_node; 71 72 _Slist_iterator_base(_Slist_node_base *__x) : _M_node(__x) {} 73 74 void _M_incr() { 75 _M_node = _M_node->_M_next; 76 } 77 }; 78 79 template <class _Tp, class _Traits> 80 class _Slist_iterator : public _Slist_iterator_base { 81 public: 82 typedef typename _Traits::value_type value_type; 83 typedef typename _Traits::pointer pointer; 84 typedef typename _Traits::reference reference; 85 typedef forward_iterator_tag iterator_category; 86 typedef size_t size_type; 87 typedef ptrdiff_t difference_type; 88 89 typedef _Slist_iterator<_Tp, _Traits> _Self; 90 typedef typename _Traits::_NonConstTraits _NonConstTraits; 91 typedef _Slist_iterator<_Tp, _NonConstTraits> iterator; 92 typedef typename _Traits::_ConstTraits _ConstTraits; 93 typedef _Slist_iterator<_Tp, _ConstTraits> const_iterator; 94 95 typedef _Slist_node<value_type> _Node; 96 97 explicit _Slist_iterator(_Slist_node_base *__x) : _Slist_iterator_base(__x) {} 98 _Slist_iterator() : _Slist_iterator_base(0) {} 99 //copy constructor for iterator and constructor from iterator for const_iterator 100 _Slist_iterator(const iterator& __x) : _Slist_iterator_base(__x._M_node) {} 101 102 reference operator*() const { return __STATIC_CAST(_Node*, this->_M_node)->_M_data; } 103 104 _STLP_DEFINE_ARROW_OPERATOR 105 106 _Self& operator++() { 107 _M_incr(); 108 return *this; 109 } 110 _Self operator++(int) { 111 _Self __tmp = *this; 112 _M_incr(); 113 return __tmp; 114 } 115 116 bool operator==(const_iterator __y ) const { 117 return this->_M_node == __y._M_node; 118 } 119 bool operator!=(const_iterator __y ) const { 120 return this->_M_node != __y._M_node; 121 } 122 }; 123 124 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) 125 _STLP_MOVE_TO_STD_NAMESPACE 126 template <class _Tp, class _Traits> 127 struct __type_traits<_STLP_PRIV _Slist_iterator<_Tp, _Traits> > { 128 typedef __false_type has_trivial_default_constructor; 129 typedef __true_type has_trivial_copy_constructor; 130 typedef __true_type has_trivial_assignment_operator; 131 typedef __true_type has_trivial_destructor; 132 typedef __false_type is_POD_type; 133 }; 134 _STLP_MOVE_TO_PRIV_NAMESPACE 135 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */ 136 137 #if defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES) 138 _STLP_MOVE_TO_STD_NAMESPACE 139 template <class _Tp, class _Traits> 140 inline _Tp* _STLP_CALL value_type(const _STLP_PRIV _Slist_iterator<_Tp, _Traits>&) { return __STATIC_CAST(_Tp*, 0); } 141 inline ptrdiff_t* _STLP_CALL distance_type(const _STLP_PRIV _Slist_iterator_base&) { return 0; } 142 inline forward_iterator_tag _STLP_CALL iterator_category(const _STLP_PRIV _Slist_iterator_base&) { return forward_iterator_tag(); } 143 _STLP_MOVE_TO_PRIV_NAMESPACE 144 #endif /* OLD_QUERIES */ 145 146 // Base class that encapsulates details of allocators and simplifies EH 147 template <class _Tp, class _Alloc> 148 class _Slist_base { 149 protected: 150 typedef _Slist_node<_Tp> _Node; 151 typedef typename _Alloc_traits<_Node,_Alloc>::allocator_type _M_node_allocator_type; 152 typedef _Slist_base<_Tp, _Alloc> _Self; 153 154 public: 155 typedef _STLP_alloc_proxy<_Slist_node_base, _Node, _M_node_allocator_type> _AllocProxy; 156 157 _STLP_FORCE_ALLOCATORS(_Tp, _Alloc) 158 typedef _Alloc allocator_type; 159 160 _Slist_base(const allocator_type& __a) : 161 _M_head(_STLP_CONVERT_ALLOCATOR(__a, _Node), _Slist_node_base() ) 162 { _M_head._M_data._M_next = 0; } 163 164 #if !defined (_STLP_NO_MOVE_SEMANTIC) 165 _Slist_base(__move_source<_Self> src) : 166 _M_head(__move_source<_AllocProxy>(src.get()._M_head)) 167 { src.get()._M_head._M_data._M_next = 0; } 168 #endif 169 170 ~_Slist_base() { _M_erase_after(&_M_head._M_data, 0); } 171 172 protected: 173 _Slist_node_base* _M_erase_after(_Slist_node_base* __pos) { 174 _Node* __next = __STATIC_CAST(_Node*, __pos->_M_next); 175 _Slist_node_base* __next_next = __next->_M_next; 176 __pos->_M_next = __next_next; 177 _STLP_STD::_Destroy(&__next->_M_data); 178 _M_head.deallocate(__next,1); 179 return __next_next; 180 } 181 _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*); 182 183 public: 184 allocator_type get_allocator() const 185 { return _STLP_CONVERT_ALLOCATOR((const _M_node_allocator_type&)_M_head, _Tp); } 186 _AllocProxy _M_head; 187 }; 188 189 #if defined (_STLP_USE_PTR_SPECIALIZATIONS) 190 # define slist _STLP_PTR_IMPL_NAME(slist) 191 #elif defined (_STLP_DEBUG) 192 # define slist _STLP_NON_DBG_NAME(slist) 193 #else 194 _STLP_MOVE_TO_STD_NAMESPACE 195 #endif 196 197 template <class _Tp, _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Tp>) > 198 class slist; 199 200 #if !defined (slist) 201 _STLP_MOVE_TO_PRIV_NAMESPACE 202 #endif 203 204 // helper functions to reduce code duplication 205 template <class _Tp, class _Alloc, class _BinaryPredicate> 206 void _Slist_unique(slist<_Tp, _Alloc>& __that, _BinaryPredicate __binary_pred); 207 208 template <class _Tp, class _Alloc, class _StrictWeakOrdering> 209 void _Slist_merge(slist<_Tp, _Alloc>& __that, slist<_Tp, _Alloc>& __x, 210 _StrictWeakOrdering __comp); 211 212 template <class _Tp, class _Alloc, class _StrictWeakOrdering> 213 void _Slist_sort(slist<_Tp, _Alloc>& __that, _StrictWeakOrdering __comp); 214 215 #if !defined (slist) 216 _STLP_MOVE_TO_STD_NAMESPACE 217 #endif 218 219 template <class _Tp, class _Alloc> 220 class slist : protected _STLP_PRIV _Slist_base<_Tp,_Alloc> 221 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (slist) 222 , public __stlport_class<slist<_Tp, _Alloc> > 223 #endif 224 { 225 private: 226 typedef _STLP_PRIV _Slist_base<_Tp,_Alloc> _Base; 227 typedef slist<_Tp,_Alloc> _Self; 228 public: 229 typedef _Tp value_type; 230 231 typedef value_type* pointer; 232 typedef const value_type* const_pointer; 233 typedef value_type& reference; 234 typedef const value_type& const_reference; 235 typedef size_t size_type; 236 typedef ptrdiff_t difference_type; 237 typedef forward_iterator_tag _Iterator_category; 238 239 typedef _STLP_PRIV _Slist_iterator<_Tp, _Nonconst_traits<_Tp> > iterator; 240 typedef _STLP_PRIV _Slist_iterator<_Tp, _Const_traits<_Tp> > const_iterator; 241 242 _STLP_FORCE_ALLOCATORS(_Tp, _Alloc) 243 typedef typename _Base::allocator_type allocator_type; 244 245 private: 246 typedef _STLP_PRIV _Slist_node<_Tp> _Node; 247 typedef _STLP_PRIV _Slist_node_base _Node_base; 248 249 #if !defined(_STLP_DONT_SUP_DFLT_PARAM) 250 _Node* _M_create_node(const value_type& __x = _Tp()) { 251 #else 252 _Node* _M_create_node(const value_type& __x) { 253 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/ 254 _Node* __node = this->_M_head.allocate(1); 255 _STLP_TRY { 256 _Copy_Construct(&__node->_M_data, __x); 257 __node->_M_next = 0; 258 } 259 _STLP_UNWIND(this->_M_head.deallocate(__node, 1)) 260 return __node; 261 } 262 263 #if defined(_STLP_DONT_SUP_DFLT_PARAM) 264 _Node* _M_create_node() { 265 _Node* __node = this->_M_head.allocate(1); 266 _STLP_TRY { 267 _STLP_STD::_Construct(&__node->_M_data); 268 __node->_M_next = 0; 269 } 270 _STLP_UNWIND(this->_M_head.deallocate(__node, 1)) 271 return __node; 272 } 273 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/ 274 275 public: 276 277 allocator_type get_allocator() const { return _Base::get_allocator(); } 278 279 #if !defined (_STLP_DONT_SUP_DFLT_PARAM) 280 explicit slist(const allocator_type& __a = allocator_type()) 281 #else 282 slist() 283 : _STLP_PRIV _Slist_base<_Tp,_Alloc>(allocator_type()) {} 284 slist(const allocator_type& __a) 285 #endif 286 : _STLP_PRIV _Slist_base<_Tp,_Alloc>(__a) {} 287 288 #if !defined (_STLP_DONT_SUP_DFLT_PARAM) 289 explicit slist(size_type __n, const value_type& __x = _STLP_DEFAULT_CONSTRUCTED(_Tp), 290 const allocator_type& __a = allocator_type()) 291 #else 292 explicit slist(size_type __n) 293 : _STLP_PRIV _Slist_base<_Tp,_Alloc>(allocator_type()) 294 { _M_insert_after_fill(&this->_M_head._M_data, __n, _STLP_DEFAULT_CONSTRUCTED(_Tp)); } 295 slist(size_type __n, const value_type& __x) 296 : _STLP_PRIV _Slist_base<_Tp,_Alloc>(allocator_type()) 297 { _M_insert_after_fill(&this->_M_head._M_data, __n, __x); } 298 slist(size_type __n, const value_type& __x, const allocator_type& __a) 299 #endif 300 : _STLP_PRIV _Slist_base<_Tp,_Alloc>(__a) 301 { _M_insert_after_fill(&this->_M_head._M_data, __n, __x); } 302 303 #if defined (_STLP_MEMBER_TEMPLATES) 304 // We don't need any dispatching tricks here, because _M_insert_after_range 305 // already does them. 306 template <class _InputIterator> 307 slist(_InputIterator __first, _InputIterator __last, 308 const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL) 309 : _STLP_PRIV _Slist_base<_Tp,_Alloc>(__a) 310 { _M_insert_after_range(&this->_M_head._M_data, __first, __last); } 311 # if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS) 312 // VC++ needs this crazyness 313 template <class _InputIterator> 314 slist(_InputIterator __first, _InputIterator __last) 315 : _STLP_PRIV _Slist_base<_Tp,_Alloc>(allocator_type()) 316 { _M_insert_after_range(&this->_M_head._M_data, __first, __last); } 317 # endif 318 #else /* _STLP_MEMBER_TEMPLATES */ 319 slist(const_iterator __first, const_iterator __last, 320 const allocator_type& __a = allocator_type() ) 321 : _STLP_PRIV _Slist_base<_Tp,_Alloc>(__a) 322 { _M_insert_after_range(&this->_M_head._M_data, __first, __last); } 323 slist(const value_type* __first, const value_type* __last, 324 const allocator_type& __a = allocator_type()) 325 : _STLP_PRIV _Slist_base<_Tp,_Alloc>(__a) 326 { _M_insert_after_range(&this->_M_head._M_data, __first, __last); } 327 #endif /* _STLP_MEMBER_TEMPLATES */ 328 329 slist(const _Self& __x) 330 : _STLP_PRIV _Slist_base<_Tp,_Alloc>(__x.get_allocator()) 331 { _M_insert_after_range(&this->_M_head._M_data, __x.begin(), __x.end()); } 332 333 #if !defined (_STLP_NO_MOVE_SEMANTIC) 334 slist(__move_source<_Self> src) 335 : _STLP_PRIV _Slist_base<_Tp, _Alloc>(__move_source<_Base>(src.get())) {} 336 #endif 337 338 _Self& operator= (const _Self& __x); 339 340 ~slist() {} 341 342 public: 343 // assign(), a generalized assignment member function. Two 344 // versions: one that takes a count, and one that takes a range. 345 // The range version is a member template, so we dispatch on whether 346 // or not the type is an integer. 347 348 void assign(size_type __n, const _Tp& __val) { _M_fill_assign(__n, __val); } 349 350 private: 351 void _M_fill_assign(size_type __n, const _Tp& __val); 352 353 #if defined (_STLP_MEMBER_TEMPLATES) 354 public: 355 template <class _InputIterator> 356 void assign(_InputIterator __first, _InputIterator __last) { 357 typedef typename _IsIntegral<_InputIterator>::_Ret _Integral; 358 _M_assign_dispatch(__first, __last, _Integral()); 359 } 360 361 private: 362 template <class _Integer> 363 void _M_assign_dispatch(_Integer __n, _Integer __val, 364 const __true_type& /*_IsIntegral*/) { 365 _M_fill_assign((size_type) __n, (_Tp) __val); 366 } 367 368 template <class _InputIter> 369 void _M_assign_dispatch(_InputIter __first, _InputIter __last, 370 const __false_type& /*_IsIntegral*/) { 371 #else 372 public: 373 void assign(const_pointer __first, const_pointer __last) { 374 _Node_base* __prev = &this->_M_head._M_data; 375 _Node_base* __node = this->_M_head._M_data._M_next; 376 while (__node != 0 && __first != __last) { 377 __STATIC_CAST(_Node*, __node)->_M_data = *__first; 378 __prev = __node; 379 __node = __node->_M_next; 380 ++__first; 381 } 382 if (__first != __last) 383 _M_insert_after_range(__prev, __first, __last); 384 else 385 this->_M_erase_after(__prev, 0); 386 } 387 void assign(const_iterator __first, const_iterator __last) { 388 #endif /* _STLP_MEMBER_TEMPLATES */ 389 _Node_base* __prev = &this->_M_head._M_data; 390 _Node_base* __node = this->_M_head._M_data._M_next; 391 while (__node != 0 && __first != __last) { 392 __STATIC_CAST(_Node*, __node)->_M_data = *__first; 393 __prev = __node; 394 __node = __node->_M_next; 395 ++__first; 396 } 397 if (__first != __last) 398 _M_insert_after_range(__prev, __first, __last); 399 else 400 this->_M_erase_after(__prev, 0); 401 } 402 403 public: 404 405 // Experimental new feature: before_begin() returns a 406 // non-dereferenceable iterator that, when incremented, yields 407 // begin(). This iterator may be used as the argument to 408 // insert_after, erase_after, etc. Note that even for an empty 409 // slist, before_begin() is not the same iterator as end(). It 410 // is always necessary to increment before_begin() at least once to 411 // obtain end(). 412 iterator before_begin() { return iterator(&this->_M_head._M_data); } 413 const_iterator before_begin() const 414 { return const_iterator(__CONST_CAST(_Node_base*, &this->_M_head._M_data)); } 415 416 iterator begin() { return iterator(this->_M_head._M_data._M_next); } 417 const_iterator begin() const 418 { return const_iterator(this->_M_head._M_data._M_next);} 419 420 iterator end() { return iterator(); } 421 const_iterator end() const { return const_iterator(); } 422 423 size_type size() const 424 { return _STLP_PRIV _Sl_global_inst::size(this->_M_head._M_data._M_next); } 425 426 size_type max_size() const { return size_type(-1); } 427 428 bool empty() const { return this->_M_head._M_data._M_next == 0; } 429 430 void swap(_Self& __x) 431 { this->_M_head.swap(__x._M_head); } 432 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER) 433 void _M_swap_workaround(_Self& __x) { swap(__x); } 434 #endif 435 436 public: 437 reference front() { return *begin(); } 438 const_reference front() const { return *begin(); } 439 #if !defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS) 440 void push_front(const value_type& __x = _Tp()) { 441 #else 442 void push_front(const value_type& __x) { 443 #endif /*!_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/ 444 _STLP_PRIV __slist_make_link(&this->_M_head._M_data, _M_create_node(__x)); 445 } 446 447 #if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS) 448 void push_front() { _STLP_PRIV __slist_make_link(&this->_M_head._M_data, _M_create_node());} 449 #endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/ 450 451 void pop_front() { 452 _Node* __node = __STATIC_CAST(_Node*, this->_M_head._M_data._M_next); 453 this->_M_head._M_data._M_next = __node->_M_next; 454 _STLP_STD::_Destroy(&__node->_M_data); 455 this->_M_head.deallocate(__node, 1); 456 } 457 458 iterator previous(const_iterator __pos) { 459 return iterator(_STLP_PRIV _Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node)); 460 } 461 const_iterator previous(const_iterator __pos) const { 462 return const_iterator(__CONST_CAST(_Node_base*, 463 _STLP_PRIV _Sl_global_inst::__previous(&this->_M_head._M_data, 464 __pos._M_node))); 465 } 466 467 private: 468 #if !defined (_STLP_DONT_SUP_DFLT_PARAM) 469 _Node* _M_insert_after(_Node_base* __pos, const value_type& __x = _Tp()) { 470 #else 471 _Node* _M_insert_after(_Node_base* __pos, const value_type& __x) { 472 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/ 473 return __STATIC_CAST(_Node*, _STLP_PRIV __slist_make_link(__pos, _M_create_node(__x))); 474 } 475 476 #if defined (_STLP_DONT_SUP_DFLT_PARAM) 477 _Node* _M_insert_after(_Node_base* __pos) { 478 return __STATIC_CAST(_Node*, _STLP_PRIV __slist_make_link(__pos, _M_create_node())); 479 } 480 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/ 481 482 void _M_insert_after_fill(_Node_base* __pos, 483 size_type __n, const value_type& __x) { 484 for (size_type __i = 0; __i < __n; ++__i) 485 __pos = _STLP_PRIV __slist_make_link(__pos, _M_create_node(__x)); 486 } 487 488 #if defined (_STLP_MEMBER_TEMPLATES) 489 // Check whether it's an integral type. If so, it's not an iterator. 490 template <class _InIter> 491 void _M_insert_after_range(_Node_base* __pos, 492 _InIter __first, _InIter __last) { 493 typedef typename _IsIntegral<_InIter>::_Ret _Integral; 494 _M_insert_after_range(__pos, __first, __last, _Integral()); 495 } 496 497 template <class _Integer> 498 void _M_insert_after_range(_Node_base* __pos, _Integer __n, _Integer __x, 499 const __true_type&) { 500 _M_insert_after_fill(__pos, __n, __x); 501 } 502 503 template <class _InIter> 504 void _M_insert_after_range(_Node_base* __pos, 505 _InIter __first, _InIter __last, 506 const __false_type&) { 507 #else /* _STLP_MEMBER_TEMPLATES */ 508 void _M_insert_after_range(_Node_base* __pos, 509 const value_type* __first, 510 const value_type* __last) { 511 while (__first != __last) { 512 __pos = _STLP_PRIV __slist_make_link(__pos, _M_create_node(*__first)); 513 ++__first; 514 } 515 } 516 void _M_insert_after_range(_Node_base* __pos, 517 const_iterator __first, const_iterator __last) { 518 #endif /* _STLP_MEMBER_TEMPLATES */ 519 while (__first != __last) { 520 __pos = _STLP_PRIV __slist_make_link(__pos, _M_create_node(*__first)); 521 ++__first; 522 } 523 } 524 525 #if defined (_STLP_MEMBER_TEMPLATES) 526 // Check whether it's an integral type. If so, it's not an iterator. 527 template <class _InIter> 528 void _M_splice_after_range(_Node_base* __pos, 529 _InIter __first, _InIter __last) { 530 typedef typename _IsIntegral<_InIter>::_Ret _Integral; 531 _M_splice_after_range(__pos, __first, __last, _Integral()); 532 } 533 534 template <class _Integer> 535 void _M_splice_after_range(_Node_base* __pos, _Integer __n, _Integer __x, 536 const __true_type&) { 537 _M_insert_after_fill(__pos, __n, __x); 538 } 539 540 template <class _InIter> 541 void _M_splice_after_range(_Node_base* __pos, 542 _InIter __first, _InIter __last, 543 const __false_type&) { 544 #else /* _STLP_MEMBER_TEMPLATES */ 545 void _M_splice_after_range(_Node_base* __pos, 546 const value_type* __first, 547 const value_type* __last) { 548 while (__first != __last) { 549 __pos = _STLP_PRIV __slist_make_link(__pos, _M_create_node(*__first)); 550 ++__first; 551 } 552 } 553 void _M_splice_after_range(_Node_base* __pos, 554 const_iterator __first, const_iterator __last) { 555 #endif /* _STLP_MEMBER_TEMPLATES */ 556 //We use a temporary slist to avoid the auto reference troubles (infinite loop) 557 _Self __tmp(__first, __last, this->get_allocator()); 558 splice_after(iterator(__pos), __tmp); 559 } 560 561 #if defined (_STLP_MEMBER_TEMPLATES) 562 // Check whether it's an integral type. If so, it's not an iterator. 563 template <class _InIter> 564 void _M_splice_range(_Node_base* __pos, 565 _InIter __first, _InIter __last) { 566 typedef typename _IsIntegral<_InIter>::_Ret _Integral; 567 _M_splice_range(__pos, __first, __last, _Integral()); 568 } 569 570 template <class _Integer> 571 void _M_splice_range(_Node_base* __pos, _Integer __n, _Integer __x, 572 const __true_type&) { 573 _M_insert_after_fill(_STLP_PRIV _Sl_global_inst::__previous(&this->_M_head._M_data, __pos), 574 __n, __x); 575 } 576 577 template <class _InIter> 578 void _M_splice_range(_Node_base* __pos, 579 _InIter __first, _InIter __last, 580 const __false_type&) { 581 #else /* _STLP_MEMBER_TEMPLATES */ 582 void _M_splice_range(_Node_base* __pos, 583 const value_type* __first, 584 const value_type* __last) { 585 while (__first != __last) { 586 __pos = _STLP_PRIV __slist_make_link(__pos, _M_create_node(*__first)); 587 ++__first; 588 } 589 } 590 void _M_splice_range(_Node_base* __pos, 591 const_iterator __first, const_iterator __last) { 592 #endif /* _STLP_MEMBER_TEMPLATES */ 593 //We use a temporary slist to avoid the auto reference troubles (infinite loop) 594 _Self __tmp(__first, __last, this->get_allocator()); 595 splice(iterator(__pos), __tmp); 596 } 597 598 public: 599 600 #if !defined (_STLP_DONT_SUP_DFLT_PARAM) 601 iterator insert_after(iterator __pos, const value_type& __x = _Tp()) { 602 #else 603 iterator insert_after(iterator __pos, const value_type& __x) { 604 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/ 605 return iterator(_M_insert_after(__pos._M_node, __x)); 606 } 607 608 #if defined (_STLP_DONT_SUP_DFLT_PARAM) 609 iterator insert_after(iterator __pos) { 610 return insert_after(__pos, _STLP_DEFAULT_CONSTRUCTED(_Tp)); 611 } 612 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/ 613 614 void insert_after(iterator __pos, size_type __n, const value_type& __x) { 615 _M_insert_after_fill(__pos._M_node, __n, __x); 616 } 617 618 #if defined (_STLP_MEMBER_TEMPLATES) 619 // We don't need any dispatching tricks here, because _M_insert_after_range 620 // already does them. 621 template <class _InIter> 622 void insert_after(iterator __pos, _InIter __first, _InIter __last) { 623 #else /* _STLP_MEMBER_TEMPLATES */ 624 void insert_after(iterator __pos, 625 const value_type* __first, const value_type* __last) { 626 _M_insert_after_range(__pos._M_node, __first, __last); 627 } 628 void insert_after(iterator __pos, 629 const_iterator __first, const_iterator __last) { 630 #endif /* _STLP_MEMBER_TEMPLATES */ 631 _M_splice_after_range(__pos._M_node, __first, __last); 632 } 633 634 #if !defined (_STLP_DONT_SUP_DFLT_PARAM) 635 iterator insert(iterator __pos, const value_type& __x = _Tp()) { 636 #else 637 iterator insert(iterator __pos, const value_type& __x) { 638 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/ 639 return iterator(_M_insert_after(_STLP_PRIV _Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node), 640 __x)); 641 } 642 643 #if defined (_STLP_DONT_SUP_DFLT_PARAM) 644 iterator insert(iterator __pos) { 645 return iterator(_M_insert_after(_STLP_PRIV _Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node), 646 _STLP_DEFAULT_CONSTRUCTED(_Tp))); 647 } 648 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/ 649 650 void insert(iterator __pos, size_type __n, const value_type& __x) { 651 _M_insert_after_fill(_STLP_PRIV _Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node), __n, __x); 652 } 653 654 #if defined (_STLP_MEMBER_TEMPLATES) 655 // We don't need any dispatching tricks here, because _M_insert_after_range 656 // already does them. 657 template <class _InIter> 658 void insert(iterator __pos, _InIter __first, _InIter __last) { 659 #else /* _STLP_MEMBER_TEMPLATES */ 660 void insert(iterator __pos, const value_type* __first, 661 const value_type* __last) { 662 _M_insert_after_range(_STLP_PRIV _Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node), 663 __first, __last); 664 } 665 void insert(iterator __pos, const_iterator __first, const_iterator __last) { 666 #endif /* _STLP_MEMBER_TEMPLATES */ 667 _M_splice_range(__pos._M_node, __first, __last); 668 } 669 670 public: 671 iterator erase_after(iterator __pos) 672 { return iterator(this->_M_erase_after(__pos._M_node)); } 673 iterator erase_after(iterator __before_first, iterator __last) 674 { return iterator(this->_M_erase_after(__before_first._M_node, __last._M_node)); } 675 676 iterator erase(iterator __pos) 677 { return iterator(this->_M_erase_after(_STLP_PRIV _Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node))); } 678 iterator erase(iterator __first, iterator __last) 679 { return iterator(this->_M_erase_after(_STLP_PRIV _Sl_global_inst::__previous(&this->_M_head._M_data, __first._M_node), __last._M_node)); } 680 681 #if !defined (_STLP_DONT_SUP_DFLT_PARAM) 682 void resize(size_type new_size, const value_type& __x = _Tp()); 683 #else 684 void resize(size_type new_size, const value_type& __x); 685 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/ 686 687 #if defined (_STLP_DONT_SUP_DFLT_PARAM) 688 void resize(size_type new_size) { resize(new_size, _STLP_DEFAULT_CONSTRUCTED(_Tp)); } 689 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/ 690 691 void clear() 692 { this->_M_erase_after(&this->_M_head._M_data, 0); } 693 694 public: 695 // Moves the range [__before_first + 1, __before_last + 1) to *this, 696 // inserting it immediately after __pos. This is constant time. 697 void splice_after(iterator __pos, _Self& __x, 698 iterator __before_first, iterator __before_last) { 699 if (__before_first != __before_last) { 700 if (this->get_allocator() == __x.get_allocator()) { 701 _STLP_PRIV _Sl_global_inst::__splice_after(__pos._M_node, 702 __before_first._M_node, __before_last._M_node); 703 } 704 else { 705 this->insert_after(__pos, iterator(__before_first._M_node->_M_next), iterator(__before_last._M_node->_M_next)); 706 __x.erase_after(__before_first, ++__before_last); 707 } 708 } 709 } 710 711 // Moves the element that follows __prev to *this, inserting it immediately 712 // after __pos. This is constant time. 713 void splice_after(iterator __pos, _Self& __x, iterator __prev) { 714 if (this->get_allocator() == __x.get_allocator()) { 715 _STLP_PRIV _Sl_global_inst::__splice_after(__pos._M_node, 716 __prev._M_node, __prev._M_node->_M_next); 717 } 718 else { 719 this->insert_after(__pos, __STATIC_CAST(_Node*, __prev._M_node->_M_next)->_M_data); 720 __x.erase_after(__prev); 721 } 722 } 723 724 // Removes all of the elements from the list __x to *this, inserting 725 // them immediately after __pos. __x must not be *this. Complexity: 726 // linear in __x.size(). 727 void splice_after(iterator __pos, _Self& __x) { 728 if (this->get_allocator() == __x.get_allocator()) 729 _STLP_PRIV _Sl_global_inst::__splice_after(__pos._M_node, &__x._M_head._M_data); 730 else { 731 this->insert_after(__pos, __x.begin(), __x.end()); 732 __x.clear(); 733 } 734 } 735 736 // Linear in distance(begin(), __pos), and linear in __x.size(). 737 void splice(iterator __pos, _Self& __x) { 738 if (__x._M_head._M_data._M_next) { 739 if (this->get_allocator() == __x.get_allocator()) { 740 _STLP_PRIV _Sl_global_inst::__splice_after(_STLP_PRIV _Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node), 741 &__x._M_head._M_data, 742 _STLP_PRIV _Sl_global_inst::__previous(&__x._M_head._M_data, 0)); 743 } 744 else { 745 insert(__pos, __x.begin(), __x.end()); 746 __x.clear(); 747 } 748 } 749 } 750 751 // Linear in distance(begin(), __pos), and in distance(__x.begin(), __i). 752 void splice(iterator __pos, _Self& __x, iterator __i) { 753 if (this->get_allocator() == __x.get_allocator()) { 754 _STLP_PRIV _Sl_global_inst::__splice_after(_STLP_PRIV _Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node), 755 _STLP_PRIV _Sl_global_inst::__previous(&__x._M_head._M_data, __i._M_node), 756 __i._M_node); 757 } 758 else { 759 insert(__pos, *__i); 760 __x.erase(__i); 761 } 762 } 763 764 // Linear in distance(begin(), __pos), in distance(__x.begin(), __first), 765 // and in distance(__first, __last). 766 void splice(iterator __pos, _Self& __x, iterator __first, iterator __last) { 767 if (__first != __last) { 768 if (this->get_allocator() == __x.get_allocator()) { 769 _STLP_PRIV _Sl_global_inst::__splice_after(_STLP_PRIV _Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node), 770 _STLP_PRIV _Sl_global_inst::__previous(&__x._M_head._M_data, __first._M_node), 771 _STLP_PRIV _Sl_global_inst::__previous(__first._M_node, __last._M_node)); 772 } 773 else { 774 insert(__pos, __first, __last); 775 __x.erase(__first, __last); 776 } 777 } 778 } 779 780 public: 781 void reverse() { 782 if (this->_M_head._M_data._M_next) 783 this->_M_head._M_data._M_next = _STLP_PRIV _Sl_global_inst::__reverse(this->_M_head._M_data._M_next); 784 } 785 786 void remove(const _Tp& __val); 787 788 void unique() { _STLP_PRIV _Slist_unique(*this, equal_to<value_type>()); } 789 void merge(_Self& __x) { _STLP_PRIV _Slist_merge(*this, __x, less<value_type>()); } 790 void sort() { _STLP_PRIV _Slist_sort(*this, less<value_type>()); } 791 792 #if defined (_STLP_MEMBER_TEMPLATES) 793 template <class _Predicate> 794 void remove_if(_Predicate __pred) { 795 _Node_base* __cur = &this->_M_head._M_data; 796 while (__cur->_M_next) { 797 if (__pred(__STATIC_CAST(_Node*, __cur->_M_next)->_M_data)) 798 this->_M_erase_after(__cur); 799 else 800 __cur = __cur->_M_next; 801 } 802 } 803 804 template <class _BinaryPredicate> 805 void unique(_BinaryPredicate __pred) 806 { _STLP_PRIV _Slist_unique(*this, __pred); } 807 808 template <class _StrictWeakOrdering> 809 void merge(_Self& __x, _StrictWeakOrdering __comp) 810 { _STLP_PRIV _Slist_merge(*this, __x, __comp); } 811 812 template <class _StrictWeakOrdering> 813 void sort(_StrictWeakOrdering __comp) 814 { _STLP_PRIV _Slist_sort(*this, __comp); } 815 #endif /* _STLP_MEMBER_TEMPLATES */ 816 }; 817 818 #if defined (slist) 819 # undef slist 820 _STLP_MOVE_TO_STD_NAMESPACE 821 #endif 822 823 _STLP_END_NAMESPACE 824 825 #if !defined (_STLP_LINK_TIME_INSTANTIATION) 826 # include <stl/_slist.c> 827 #endif 828 829 #if defined (_STLP_USE_PTR_SPECIALIZATIONS) 830 # include <stl/pointers/_slist.h> 831 #endif 832 833 #if defined (_STLP_DEBUG) 834 # include <stl/debug/_slist.h> 835 #endif 836 837 _STLP_BEGIN_NAMESPACE 838 839 template <class _Tp, class _Alloc> 840 inline bool _STLP_CALL 841 operator == (const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) { 842 typedef typename slist<_Tp,_Alloc>::const_iterator const_iterator; 843 const_iterator __end1 = _SL1.end(); 844 const_iterator __end2 = _SL2.end(); 845 846 const_iterator __i1 = _SL1.begin(); 847 const_iterator __i2 = _SL2.begin(); 848 while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) { 849 ++__i1; 850 ++__i2; 851 } 852 return __i1 == __end1 && __i2 == __end2; 853 } 854 855 #define _STLP_EQUAL_OPERATOR_SPECIALIZED 856 #define _STLP_TEMPLATE_HEADER template <class _Tp, class _Alloc> 857 #define _STLP_TEMPLATE_CONTAINER slist<_Tp, _Alloc> 858 #include <stl/_relops_cont.h> 859 #undef _STLP_TEMPLATE_CONTAINER 860 #undef _STLP_TEMPLATE_HEADER 861 #undef _STLP_EQUAL_OPERATOR_SPECIALIZED 862 863 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) 864 # if !defined (_STLP_NO_MOVE_SEMANTIC) 865 template <class _Tp, class _Alloc> 866 struct __move_traits<slist<_Tp, _Alloc> > { 867 typedef __true_type implemented; 868 typedef typename __move_traits<_Alloc>::complete complete; 869 }; 870 # endif 871 872 // Specialization of insert_iterator so that insertions will be constant 873 // time rather than linear time. 874 template <class _Tp, class _Alloc> 875 class insert_iterator<slist<_Tp, _Alloc> > { 876 protected: 877 typedef slist<_Tp, _Alloc> _Container; 878 _Container* _M_container; 879 typename _Container::iterator _M_iter; 880 public: 881 typedef _Container container_type; 882 typedef output_iterator_tag iterator_category; 883 typedef void value_type; 884 typedef void difference_type; 885 typedef void pointer; 886 typedef void reference; 887 888 insert_iterator(_Container& __x, typename _Container::iterator __i) 889 : _M_container(&__x) { 890 if (__i == __x.begin()) 891 _M_iter = __x.before_begin(); 892 else 893 _M_iter = __x.previous(__i); 894 } 895 896 insert_iterator<_Container>& 897 operator = (const typename _Container::value_type& __val) { 898 _M_iter = _M_container->insert_after(_M_iter, __val); 899 return *this; 900 } 901 902 insert_iterator<_Container>& operator*() { return *this; } 903 insert_iterator<_Container>& operator++() { return *this; } 904 insert_iterator<_Container>& operator++(int) { return *this; } 905 }; 906 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */ 907 908 _STLP_END_NAMESPACE 909 910 #endif /* _STLP_INTERNAL_SLIST_H */ 911 912 // Local Variables: 913 // mode:C++ 914 // End: 915
