5 * Hewlett-Packard Company
7 * Copyright (c) 1996,1997
8 * Silicon Graphics Computer Systems, Inc.
11 * Moscow Center for SPARC Technology
16 * This material is provided "as is", with absolutely no warranty expressed
17 * or implied. Any use is at your own risk.
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.
29 #ifndef _STLP_INTERNAL_LIST_H
30 # include <stl/_list.h>
33 #ifndef _STLP_CARRAY_H
34 # include <stl/_carray.h>
37 #ifndef _STLP_RANGE_ERRORS_H
38 # include <stl/_range_errors.h>
43 _STLP_MOVE_TO_PRIV_NAMESPACE
45 #if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION)
46 template <class _Dummy
>
48 _List_global
<_Dummy
>::_Transfer(_List_node_base
* __position
,
49 _List_node_base
* __first
, _List_node_base
* __last
) {
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
;
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
;
63 #endif /* _STLP_EXPOSE_GLOBALS_IMPLEMENTATION */
65 template <class _Tp
, class _Alloc
>
66 void _List_base
<_Tp
,_Alloc
>::clear() {
67 _Node
* __cur
= __STATIC_CAST(_Node
*, _M_node
._M_data
._M_next
);
69 #if defined (__BORLANDC__) // runtime error
72 __cur
!= &(_M_node
._M_data
)) {
74 __cur
= __STATIC_CAST(_Node
*, __cur
->_M_next
);
75 _STLP_STD::_Destroy(&__tmp
->_M_data
);
76 this->_M_node
.deallocate(__tmp
, 1);
78 _M_node
._M_data
._M_next
= &_M_node
._M_data
;
79 _M_node
._M_data
._M_prev
= &_M_node
._M_data
;
82 #if defined (_STLP_NESTED_TYPE_PARAM_BUG)
83 # define size_type size_t
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)
91 _STLP_MOVE_TO_STD_NAMESPACE
94 template <class _Tp
, class _Alloc
>
95 void list
<_Tp
, _Alloc
>::resize(size_type __new_size
, const _Tp
& __x
) {
96 iterator __i
= begin();
98 for ( ; __i
!= end() && __len
< __new_size
; ++__i
, ++__len
);
100 if (__len
== __new_size
)
103 insert(end(), __new_size
- __len
, __x
);
106 template <class _Tp
, class _Alloc
>
107 list
<_Tp
, _Alloc
>& list
<_Tp
, _Alloc
>::operator=(const list
<_Tp
, _Alloc
>& __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
);
118 insert(__last1
, __first2
, __last2
);
123 template <class _Tp
, class _Alloc
>
124 void list
<_Tp
, _Alloc
>::_M_fill_assign(size_type __n
, const _Tp
& __val
) {
125 iterator __i
= begin();
126 for ( ; __i
!= end() && __n
> 0; ++__i
, --__n
)
129 insert(end(), __n
, __val
);
135 _STLP_MOVE_TO_PRIV_NAMESPACE
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
;
146 if (__pred(*__first
)) __that
.erase(__first
);
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
);
167 template <class _Tp
, class _Alloc
, class _StrictWeakOrdering
>
168 void _S_merge(list
<_Tp
, _Alloc
>& __that
, list
<_Tp
, _Alloc
>& __x
,
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
);
186 if (__first2
!= __last2
)
187 _List_global_inst::_Transfer(__last1
._M_node
, __first2
._M_node
, __last2
._M_node
);
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
);
198 if (__first2
!= __last2
) {
199 __that
.insert(__first1
, __first2
, __last2
);
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
)
212 list
<_Tp
, _Alloc
> __carry(__that
.get_allocator());
214 _STLP_PRIV _CArray
<list
<_Tp
, _Alloc
>, NB
> __counter(__carry
);
216 while (!__that
.empty()) {
217 __carry
.splice(__carry
.begin(), __that
, __that
.begin());
219 while (__i
< __fill
&& !__counter
[__i
].empty()) {
220 _S_merge(__counter
[__i
], __carry
, __comp
);
221 __carry
.swap(__counter
[__i
++]);
223 __carry
.swap(__counter
[__i
]);
227 //Looks like the list has too many elements to be sorted with this algorithm:
228 __stl_throw_overflow_error("list::sort");
233 for (int __i
= 1; __i
< __fill
; ++__i
)
234 _S_merge(__counter
[__i
], __counter
[__i
- 1], __comp
);
235 __that
.swap(__counter
[__fill
- 1]);
242 _STLP_MOVE_TO_STD_NAMESPACE
246 #endif /* _STLP_LIST_C */