ReactOS  0.4.14-dev-1256-g2125fec
_slist.c File Reference
#include <stl/_slist.h>
#include <stl/_carray.h>
#include <stl/_range_errors.h>
Include dependency graph for _slist.c:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros

#define _STLP_SLIST_C
 

Functions

template<class _Tp , class _Alloc , class _BinaryPredicate >
_STLP_MOVE_TO_PRIV_NAMESPACE void _Slist_unique (slist< _Tp, _Alloc > &__that, _BinaryPredicate __pred)
 
template<class _Tp , class _Alloc , class _StrictWeakOrdering >
void _Slist_merge (slist< _Tp, _Alloc > &__that, slist< _Tp, _Alloc > &__x, _StrictWeakOrdering __comp)
 
template<class _Tp , class _Alloc , class _StrictWeakOrdering >
void _Slist_sort (slist< _Tp, _Alloc > &__that, _StrictWeakOrdering __comp)
 

Macro Definition Documentation

◆ _STLP_SLIST_C

#define _STLP_SLIST_C

Definition at line 20 of file _slist.c.

Function Documentation

◆ _Slist_merge()

template<class _Tp , class _Alloc , class _StrictWeakOrdering >
void _Slist_merge ( slist< _Tp, _Alloc > &  __that,
slist< _Tp, _Alloc > &  __x,
_StrictWeakOrdering  __comp 
)

Definition at line 148 of file _slist.c.

149  {
150  typedef _Slist_node<_Tp> _Node;
151  typedef _STLP_PRIV _Slist_node_base _Node_base;
152  if (__that.get_allocator() == __x.get_allocator()) {
153  typename slist<_Tp, _Alloc>::iterator __ite(__that.before_begin());
154  while (__ite._M_node->_M_next && !__x.empty()) {
155  if (__comp(__x.front(), __STATIC_CAST(_Node*, __ite._M_node->_M_next)->_M_data)) {
156  _STLP_VERBOSE_ASSERT(!__comp(__STATIC_CAST(_Node*, __ite._M_node->_M_next)->_M_data, __x.front()),
157  _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
158  __that.splice_after(__ite, __x, __x.before_begin());
159  }
160  ++__ite;
161  }
162  if (!__x.empty()) {
163  __that.splice_after(__ite, __x);
164  }
165  }
166  else {
167  typename slist<_Tp, _Alloc>::iterator __i1(__that.before_begin()), __i2(__x.begin());
168  while (__i1._M_node->_M_next && __i2._M_node) {
169  if (__comp(__STATIC_CAST(_Node*, __i1._M_node->_M_next)->_M_data, *__i2)) {
170  _STLP_VERBOSE_ASSERT(!__comp(*__i2, __STATIC_CAST(_Node*, __i1._M_node->_M_next)->_M_data),
171  _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
172  ++__i1;
173  }
174  else {
175  __i1 = __that.insert_after(__i1, *(__i2++));
176  }
177  }
178  __that.insert_after(__i1, __i2, __x.end());
179  __x.clear();
180  }
181 }
iterator insert_after(iterator __pos, const value_type &__x=_Tp())
Definition: _slist.h:601
bool empty() const
Definition: _slist.h:428
#define __STATIC_CAST(__x, __y)
Definition: features.h:585
iterator before_begin()
Definition: _slist.h:412
iterator begin()
Definition: _slist.h:416
reference front()
Definition: _slist.h:437
#define _STLP_PRIV
Definition: _dm.h:70
void clear()
Definition: _slist.h:691
_STLP_PRIV _Slist_iterator< _Tp, _Nonconst_traits< _Tp > > iterator
Definition: _slist.h:239
allocator_type get_allocator() const
Definition: _slist.h:277
iterator end()
Definition: _slist.h:420
void splice_after(iterator __pos, _Self &__x, iterator __before_first, iterator __before_last)
Definition: _slist.h:697
#define _STLP_VERBOSE_ASSERT(expr, diagnostic)
Definition: _debug.h:439

Referenced by _Slist_sort(), and slist< value_type, _All >::merge().

◆ _Slist_sort()

template<class _Tp , class _Alloc , class _StrictWeakOrdering >
void _Slist_sort ( slist< _Tp, _Alloc > &  __that,
_StrictWeakOrdering  __comp 
)

Definition at line 184 of file _slist.c.

184  {
185  if (!__that.begin()._M_node || !__that.begin()._M_node->_M_next)
186  return;
187 
188  slist<_Tp, _Alloc> __carry(__that.get_allocator());
189  const int NB = 64;
190  _STLP_PRIV _CArray<slist<_Tp, _Alloc>, NB> __counter(__carry);
191  int __fill = 0;
192  while (!__that.empty()) {
193  __carry.splice_after(__carry.before_begin(), __that, __that.before_begin());
194  int __i = 0;
195  while (__i < __fill && !__counter[__i].empty()) {
196  _STLP_PRIV _Slist_merge(__counter[__i], __carry, __comp);
197  __carry.swap(__counter[__i]);
198  ++__i;
199  }
200  __carry.swap(__counter[__i]);
201  if (__i == __fill) {
202  ++__fill;
203  if (__fill >= NB) {
204  //Looks like the slist has too many elements to be sorted with this algorithm:
205  __stl_throw_overflow_error("slist::sort");
206  }
207  }
208  }
209 
210  for (int __i = 1; __i < __fill; ++__i)
211  _STLP_PRIV _Slist_merge(__counter[__i], __counter[__i - 1], __comp);
212  __that.swap(__counter[__fill-1]);
213 }
bool empty() const
Definition: _slist.h:428
Definition: _slist.h:198
iterator before_begin()
Definition: _slist.h:412
iterator begin()
Definition: _slist.h:416
void _Slist_merge(slist< _Tp, _Alloc > &__that, slist< _Tp, _Alloc > &__x, _StrictWeakOrdering __comp)
Definition: _slist.c:148
#define _STLP_PRIV
Definition: _dm.h:70
_STLP_THROW_FUNCT_SPEC _STLP_CALL __stl_throw_overflow_error(const char *__msg)
Definition: _range_errors.c:78
allocator_type get_allocator() const
Definition: _slist.h:277
void swap(_Self &__x)
Definition: _slist.h:430
BOOL empty
Definition: button.c:170
void __fill(_ForwardIter __first, _ForwardIter __last, const _Tp &__val, const input_iterator_tag &, _Distance *)
Definition: _algobase.h:417

Referenced by slist< value_type, _All >::sort().

◆ _Slist_unique()

template<class _Tp , class _Alloc , class _BinaryPredicate >
_STLP_MOVE_TO_PRIV_NAMESPACE void _Slist_unique ( slist< _Tp, _Alloc > &  __that,
_BinaryPredicate  __pred 
)

Definition at line 134 of file _slist.c.

134  {
135  typedef _Slist_node<_Tp> _Node;
136  typename slist<_Tp, _Alloc>::iterator __ite(__that.begin());
137  if (__ite != __that.end()) {
138  while (__ite._M_node->_M_next) {
139  if (__pred(*__ite, __STATIC_CAST(_Node*, __ite._M_node->_M_next)->_M_data))
140  __that.erase_after(__ite);
141  else
142  ++__ite;
143  }
144  }
145 }
#define __STATIC_CAST(__x, __y)
Definition: features.h:585
_STLP_INLINE_LOOP _InputIter _Predicate __pred
Definition: _algo.h:68
iterator begin()
Definition: _slist.h:416
iterator erase_after(iterator __pos)
Definition: _slist.h:671
_STLP_PRIV _Slist_iterator< _Tp, _Nonconst_traits< _Tp > > iterator
Definition: _slist.h:239
iterator end()
Definition: _slist.h:420

Referenced by slist< value_type, _All >::unique().