ReactOS 0.4.15-dev-8127-g6338913
_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)
46template <class _Dummy>
47void _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
65template <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);
75 _STLP_STD::_Destroy(&__tmp->_M_data);
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
94template <class _Tp, class _Alloc>
95void 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
106template <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
123template <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
138template <class _Tp, class _Alloc, class _Predicate>
139void _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
151template <class _Tp, class _Alloc, class _BinaryPredicate>
152void _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
167template <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
205template <class _Tp, class _Alloc, class _StrictWeakOrdering>
206void _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:
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
_STLP_INLINE_LOOP _InputIter _Predicate __pred
Definition: _algo.h:68
return __n
Definition: _algo.h:75
void __fill(_ForwardIter __first, _ForwardIter __last, const _Tp &__val, const input_iterator_tag &, _Distance *)
Definition: _algobase.h:417
_STLP_INLINE_LOOP _InputIter const _Tp & __val
Definition: _algobase.h:656
#define _STLP_CALL
Definition: _bc.h:131
#define _STLP_VERBOSE_ASSERT(expr, diagnostic)
Definition: _debug.h:439
#define _STLP_PRIV
Definition: _dm.h:70
void _S_sort(list< _Tp, _Alloc > &__that, _StrictWeakOrdering __comp)
Definition: _list.c:206
_STLP_MOVE_TO_PRIV_NAMESPACE void _S_remove_if(list< _Tp, _Alloc > &__that, _Predicate __pred)
Definition: _list.c:139
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
_STLP_THROW_FUNCT_SPEC _STLP_CALL __stl_throw_overflow_error(const char *__msg)
Definition: _range_errors.c:78
void clear()
Definition: _list.c:66
static void _STLP_CALL _Transfer(_Node_base *__pos, _Node_base *__first, _Node_base *__last)
_Tp _M_data
Definition: _list.h:78
Definition: list.h:37
iterator erase(iterator __pos)
Definition: _list.h:518
allocator_type get_allocator() const
Definition: _list.h:161
void swap(_Self &__x)
Definition: _list.h:401
size_t size_type
Definition: _list.h:268
_STLP_PRIV _List_iterator< _Tp, _Const_traits< _Tp > > const_iterator
Definition: _list.h:276
iterator begin()
Definition: _list.h:367
_STLP_PRIV _List_iterator< _Tp, _Nonconst_traits< _Tp > > iterator
Definition: _list.h:275
iterator end()
Definition: _list.h:370
_Self & operator=(const _Self &__x)
Definition: _list.c:107
void clear()
Definition: _list.h:352
bool empty() const
Definition: _list.h:177
void resize(size_type __new_size, const_reference __x=value_type())
iterator insert(iterator __pos, const_reference __x=value_type())
Definition: _list.h:420
void _M_fill_assign(size_type __n, const_reference __val)
Definition: _list.c:124
static const WCHAR empty[]
Definition: main.c:47
#define _STLP_MOVE_TO_STD_NAMESPACE
Definition: features.h:525
#define __STATIC_CAST(__x, __y)
Definition: features.h:585
#define _STLP_BEGIN_NAMESPACE
Definition: features.h:501
#define _STLP_END_NAMESPACE
Definition: features.h:503
#define _STLP_MOVE_TO_PRIV_NAMESPACE
Definition: features.h:524
GLuint GLuint end
Definition: gl.h:1545
_List_node_base * _M_prev
Definition: _list.h:59
_List_node_base * _M_next
Definition: _list.h:58
static clock_t begin
Definition: xmllint.c:458
static int insert
Definition: xmllint.c:138