ReactOS  0.4.14-dev-77-gd9e7c48
_list.c
Go to the documentation of this file.
1 /*
2  *
3  *
4  * Copyright (c) 1994
5  * Hewlett-Packard Company
6  *
7  * Copyright (c) 1996,1997
8  * Silicon Graphics Computer Systems, Inc.
9  *
10  * Copyright (c) 1997
11  * Moscow Center for SPARC Technology
12  *
13  * Copyright (c) 1999
14  * Boris Fomitchev
15  *
16  * This material is provided "as is", with absolutely no warranty expressed
17  * or implied. Any use is at your own risk.
18  *
19  * Permission to use or copy this software for any purpose is hereby granted
20  * without fee, provided the above notices are retained on all copies.
21  * Permission to modify the code and to distribute modified code is granted,
22  * provided the above notices are retained, and a notice that the code was
23  * modified is included with the above copyright notice.
24  *
25  */
26 #ifndef _STLP_LIST_C
27 #define _STLP_LIST_C
28 
29 #ifndef _STLP_INTERNAL_LIST_H
30 # include <stl/_list.h>
31 #endif
32 
33 #ifndef _STLP_CARRAY_H
34 # include <stl/_carray.h>
35 #endif
36 
37 #ifndef _STLP_RANGE_ERRORS_H
38 # include <stl/_range_errors.h>
39 #endif
40 
42 
44 
45 #if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION)
46 template <class _Dummy>
47 void _STLP_CALL
50  if (__position != __last) {
51  // Remove [first, last) from its old position.
52  __last->_M_prev->_M_next = __position;
53  __first->_M_prev->_M_next = __last;
54  __position->_M_prev->_M_next = __first;
55 
56  // Splice [first, last) into its new position.
57  _Node_base* __tmp = __position->_M_prev;
58  __position->_M_prev = __last->_M_prev;
59  __last->_M_prev = __first->_M_prev;
60  __first->_M_prev = __tmp;
61  }
62 }
63 #endif /* _STLP_EXPOSE_GLOBALS_IMPLEMENTATION */
64 
65 template <class _Tp, class _Alloc>
67  _Node* __cur = __STATIC_CAST(_Node*, _M_node._M_data._M_next);
68  while (
69 #if defined (__BORLANDC__) // runtime error
70  __cur &&
71 #endif
72  __cur != &(_M_node._M_data)) {
73  _Node* __tmp = __cur;
74  __cur = __STATIC_CAST(_Node*, __cur->_M_next);
76  this->_M_node.deallocate(__tmp, 1);
77  }
78  _M_node._M_data._M_next = &_M_node._M_data;
79  _M_node._M_data._M_prev = &_M_node._M_data;
80 }
81 
82 #if defined (_STLP_NESTED_TYPE_PARAM_BUG)
83 # define size_type size_t
84 #endif
85 
86 #if defined (_STLP_USE_PTR_SPECIALIZATIONS)
87 # define list _STLP_PTR_IMPL_NAME(list)
88 #elif defined (_STLP_DEBUG)
89 # define list _STLP_NON_DBG_NAME(list)
90 #else
92 #endif
93 
94 template <class _Tp, class _Alloc>
95 void list<_Tp, _Alloc>::resize(size_type __new_size, const _Tp& __x) {
96  iterator __i = begin();
97  size_type __len = 0;
98  for ( ; __i != end() && __len < __new_size; ++__i, ++__len);
99 
100  if (__len == __new_size)
101  erase(__i, end());
102  else // __i == end()
103  insert(end(), __new_size - __len, __x);
104 }
105 
106 template <class _Tp, class _Alloc>
108  if (this != &__x) {
109  iterator __first1 = begin();
110  iterator __last1 = end();
111  const_iterator __first2 = __x.begin();
112  const_iterator __last2 = __x.end();
113  while (__first1 != __last1 && __first2 != __last2)
114  *__first1++ = *__first2++;
115  if (__first2 == __last2)
116  erase(__first1, __last1);
117  else
118  insert(__last1, __first2, __last2);
119  }
120  return *this;
121 }
122 
123 template <class _Tp, class _Alloc>
125  iterator __i = begin();
126  for ( ; __i != end() && __n > 0; ++__i, --__n)
127  *__i = __val;
128  if (__n > 0)
129  insert(end(), __n, __val);
130  else
131  erase(__i, end());
132 }
133 
134 #if !defined (list)
136 #endif
137 
138 template <class _Tp, class _Alloc, class _Predicate>
139 void _S_remove_if(list<_Tp, _Alloc>& __that, _Predicate __pred) {
140  typedef typename list<_Tp, _Alloc>::iterator _Literator;
141  _Literator __first = __that.begin();
142  _Literator __last = __that.end();
143  while (__first != __last) {
144  _Literator __next = __first;
145  ++__next;
146  if (__pred(*__first)) __that.erase(__first);
147  __first = __next;
148  }
149 }
150 
151 template <class _Tp, class _Alloc, class _BinaryPredicate>
152 void _S_unique(list<_Tp, _Alloc>& __that, _BinaryPredicate __binary_pred) {
153  typedef typename list<_Tp, _Alloc>::iterator _Literator;
154  _Literator __first = __that.begin();
155  _Literator __last = __that.end();
156  if (__first == __last) return;
157  _Literator __next = __first;
158  while (++__next != __last) {
159  if (__binary_pred(*__first, *__next))
160  __that.erase(__next);
161  else
162  __first = __next;
163  __next = __first;
164  }
165 }
166 
167 template <class _Tp, class _Alloc, class _StrictWeakOrdering>
169  _StrictWeakOrdering __comp) {
170  typedef typename list<_Tp, _Alloc>::iterator _Literator;
171  _Literator __first1 = __that.begin();
172  _Literator __last1 = __that.end();
173  _Literator __first2 = __x.begin();
174  _Literator __last2 = __x.end();
175  if (__that.get_allocator() == __x.get_allocator()) {
176  while (__first1 != __last1 && __first2 != __last2) {
177  if (__comp(*__first2, *__first1)) {
178  _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
179  _Literator __next = __first2;
180  _List_global_inst::_Transfer(__first1._M_node, __first2._M_node, (++__next)._M_node);
181  __first2 = __next;
182  }
183  else
184  ++__first1;
185  }
186  if (__first2 != __last2)
187  _List_global_inst::_Transfer(__last1._M_node, __first2._M_node, __last2._M_node);
188  }
189  else {
190  while (__first1 != __last1 && __first2 != __last2) {
191  if (__comp(*__first2, *__first1)) {
192  _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
193  __first1 = __that.insert(__first1, *__first2);
194  }
195  else
196  ++__first1;
197  }
198  if (__first2 != __last2) {
199  __that.insert(__first1, __first2, __last2);
200  }
201  __x.clear();
202  }
203 }
204 
205 template <class _Tp, class _Alloc, class _StrictWeakOrdering>
206 void _S_sort(list<_Tp, _Alloc>& __that, _StrictWeakOrdering __comp) {
207  // Do nothing if the list has length 0 or 1.
208  if (__that._M_node._M_data._M_next == &__that._M_node._M_data ||
209  __that._M_node._M_data._M_next->_M_next == &__that._M_node._M_data)
210  return;
211 
212  list<_Tp, _Alloc> __carry(__that.get_allocator());
213  const int NB = 64;
214  _STLP_PRIV _CArray<list<_Tp, _Alloc>, NB> __counter(__carry);
215  int __fill = 0;
216  while (!__that.empty()) {
217  __carry.splice(__carry.begin(), __that, __that.begin());
218  int __i = 0;
219  while (__i < __fill && !__counter[__i].empty()) {
220  _S_merge(__counter[__i], __carry, __comp);
221  __carry.swap(__counter[__i++]);
222  }
223  __carry.swap(__counter[__i]);
224  if (__i == __fill) {
225  ++__fill;
226  if (__fill >= NB) {
227  //Looks like the list has too many elements to be sorted with this algorithm:
228  __stl_throw_overflow_error("list::sort");
229  }
230  }
231  }
232 
233  for (int __i = 1; __i < __fill; ++__i)
234  _S_merge(__counter[__i], __counter[__i - 1], __comp);
235  __that.swap(__counter[__fill - 1]);
236 }
237 
238 #if defined (list)
239 # undef list
240 #endif
241 
243 
245 
246 #endif /* _STLP_LIST_C */
247 
248 // Local Variables:
249 // mode:C++
250 // End:
void _S_merge(list< _Tp, _Alloc > &__that, list< _Tp, _Alloc > &__x, _StrictWeakOrdering __comp)
Definition: _list.c:168
void _S_unique(list< _Tp, _Alloc > &__that, _BinaryPredicate __binary_pred)
Definition: _list.c:152
iterator begin()
Definition: _list.h:367
iterator erase(iterator __pos)
Definition: _list.h:518
return __n
Definition: _algo.h:75
void _M_fill_assign(size_type __n, const_reference __val)
Definition: _list.c:124
void resize(size_type __new_size, const_reference __x=value_type())
static const WCHAR empty[]
Definition: main.c:49
#define __STATIC_CAST(__x, __y)
Definition: features.h:585
_Tp _M_data
Definition: _list.h:78
void _S_sort(list< _Tp, _Alloc > &__that, _StrictWeakOrdering __comp)
Definition: _list.c:206
_STLP_INLINE_LOOP _InputIter _Predicate __pred
Definition: _algo.h:68
GLuint GLuint end
Definition: gl.h:1545
static int insert
Definition: xmllint.c:144
_STLP_MOVE_TO_PRIV_NAMESPACE void _S_remove_if(list< _Tp, _Alloc > &__that, _Predicate __pred)
Definition: _list.c:139
allocator_type get_allocator() const
Definition: _list.h:161
#define _STLP_MOVE_TO_PRIV_NAMESPACE
Definition: features.h:524
iterator insert(iterator __pos, const_reference __x=value_type())
Definition: _list.h:420
size_t size_type
Definition: _list.h:268
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
static clock_t begin
Definition: xmllint.c:466
void clear()
Definition: _list.h:352
_STLP_PRIV _List_iterator< BookmarkNode, _Const_traits< BookmarkNode > > const_iterator
Definition: _list.h:276
#define _STLP_MOVE_TO_STD_NAMESPACE
Definition: features.h:525
_STLP_INLINE_LOOP _InputIter const _Tp & __val
Definition: _algobase.h:656
void swap(_Self &__x)
Definition: _list.h:401
_STLP_PRIV _List_iterator< _Tp, _Nonconst_traits< _Tp > > iterator
Definition: _list.h:275
#define _STLP_PRIV
Definition: _dm.h:70
void _Destroy(_Tp *__pointer)
Definition: _construct.h:63
static void _STLP_CALL _Transfer(_Node_base *__pos, _Node_base *__first, _Node_base *__last)
Definition: _list.h:228
_STLP_THROW_FUNCT_SPEC _STLP_CALL __stl_throw_overflow_error(const char *__msg)
Definition: _range_errors.c:78
void clear()
Definition: _list.c:66
iterator end()
Definition: _list.h:370
#define _STLP_END_NAMESPACE
Definition: features.h:503
_List_node_base * _M_next
Definition: _list.h:58
void __fill(_ForwardIter __first, _ForwardIter __last, const _Tp &__val, const input_iterator_tag &, _Distance *)
Definition: _algobase.h:417
bool empty() const
Definition: _list.h:177
#define _STLP_BEGIN_NAMESPACE
Definition: features.h:501
_List_node_base * _M_prev
Definition: _list.h:59
#define _STLP_CALL
Definition: _bc.h:131
_Self & operator=(const _Self &__x)
Definition: _list.c:107
#define _STLP_VERBOSE_ASSERT(expr, diagnostic)
Definition: _debug.h:439