4 * Hewlett-Packard Company
6 * Copyright (c) 1996,1997
7 * Silicon Graphics Computer Systems, Inc.
10 * Moscow Center for SPARC Technology
15 * This material is provided "as is", with absolutely no warranty expressed
16 * or implied. Any use is at your own risk.
18 * Permission to use or copy this software for any purpose is hereby granted
19 * without fee, provided the above notices are retained on all copies.
20 * Permission to modify the code and to distribute modified code is granted,
21 * provided the above notices are retained, and a notice that the code was
22 * modified is included with the above copyright notice.
26 /* NOTE: This is an internal header file, included by other STL headers.
27 * You should not attempt to use it directly.
30 #ifndef _STLP_INTERNAL_DBG_LIST_H
31 #define _STLP_INTERNAL_DBG_LIST_H
33 #ifndef _STLP_INTERNAL_ALGO_H
34 # include <stl/_algo.h>
37 #ifndef _STLP_DBG_ITERATOR_H
38 # include <stl/debug/_iterator.h>
41 #define _STLP_NON_DBG_LIST _STLP_PRIV _STLP_NON_DBG_NAME(list) <_Tp, _Alloc>
45 #if defined (_STLP_DEBUG_USE_DISTINCT_VALUE_TYPE_HELPERS)
46 template <class _Tp
, class _Alloc
>
48 value_type(const _STLP_PRIV _DBG_iter_base
< _STLP_NON_DBG_LIST
>&)
50 template <class _Tp
, class _Alloc
>
51 inline bidirectional_iterator_tag
52 iterator_category(const _STLP_PRIV _DBG_iter_base
< _STLP_NON_DBG_LIST
>&)
53 { return bidirectional_iterator_tag(); }
56 template <class _Tp
, _STLP_DFL_TMPL_PARAM(_Alloc
, allocator
<_Tp
>) >
58 #if !defined (__DMC__)
61 _STLP_PRIV __construct_checker
<_STLP_NON_DBG_LIST
>
62 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
63 , public __stlport_class
<list
<_Tp
, _Alloc
> >
66 typedef _STLP_NON_DBG_LIST _Base
;
67 typedef list
<_Tp
, _Alloc
> _Self
;
68 typedef _STLP_PRIV __construct_checker
<_STLP_NON_DBG_LIST
> _ConstructCheck
;
71 __IMPORT_CONTAINER_TYPEDEFS(_Base
)
74 typedef _STLP_PRIV _DBG_iter
<_Base
, _STLP_PRIV _DbgTraits
<_Nonconst_traits
<value_type
> > > iterator
;
75 typedef _STLP_PRIV _DBG_iter
<_Base
, _STLP_PRIV _DbgTraits
<_Const_traits
<value_type
> > > const_iterator
;
77 _STLP_DECLARE_BIDIRECTIONAL_REVERSE_ITERATORS
;
80 _Base _M_non_dbg_impl
;
81 _STLP_PRIV __owned_list _M_iter_list
;
83 void _Invalidate_iterator(const iterator
& __it
)
84 { _STLP_PRIV
__invalidate_iterator(&_M_iter_list
, __it
); }
85 void _Invalidate_iterators(const iterator
& __first
, const iterator
& __last
)
86 { _STLP_PRIV
__invalidate_range(&_M_iter_list
, __first
, __last
); }
88 typedef typename
_Base::iterator _Base_iterator
;
91 explicit list(const allocator_type
& __a
= allocator_type()) :
92 _M_non_dbg_impl(__a
), _M_iter_list(&_M_non_dbg_impl
) {}
94 #if !defined(_STLP_DONT_SUP_DFLT_PARAM)
95 explicit list(size_type __n
, const _Tp
& __x
= _Tp(),
97 list(size_type __n
, const _Tp
& __x
,
98 #endif /*!_STLP_DONT_SUP_DFLT_PARAM*/
99 const allocator_type
& __a
= allocator_type())
100 : _M_non_dbg_impl(__n
, __x
, __a
), _M_iter_list(&_M_non_dbg_impl
) {}
102 #if defined(_STLP_DONT_SUP_DFLT_PARAM)
103 explicit list(size_type __n
)
104 : _M_non_dbg_impl(__n
), _M_iter_list(&_M_non_dbg_impl
) {}
105 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
107 #if !defined (_STLP_NO_MOVE_SEMANTIC)
108 list(__move_source
<_Self
> src
)
109 : _M_non_dbg_impl(__move_source
<_Base
>(src
.get()._M_non_dbg_impl
)),
110 _M_iter_list(&_M_non_dbg_impl
) {
111 # if defined (_STLP_NO_EXTENSIONS) || (_STLP_DEBUG_LEVEL == _STLP_STANDARD_DBG_LEVEL)
112 src
.get()._M_iter_list
._Invalidate_all();
114 src
.get()._M_iter_list
._Set_owner(_M_iter_list
);
119 #if defined (_STLP_MEMBER_TEMPLATES)
120 template <class _InputIterator
>
121 list(_InputIterator __first
, _InputIterator __last
,
122 const allocator_type
& __a _STLP_ALLOCATOR_TYPE_DFL
)
123 : _ConstructCheck(__first
, __last
),
124 _M_non_dbg_impl(_STLP_PRIV
_Non_Dbg_iter(__first
), _STLP_PRIV
_Non_Dbg_iter(__last
), __a
),
125 _M_iter_list(&_M_non_dbg_impl
) {}
126 # if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
127 template <class _InputIterator
>
128 list(_InputIterator __first
, _InputIterator __last
)
129 : _ConstructCheck(__first
, __last
),
130 _M_non_dbg_impl(_STLP_PRIV
_Non_Dbg_iter(__first
), _STLP_PRIV
_Non_Dbg_iter(__last
)),
131 _M_iter_list(&_M_non_dbg_impl
) {}
135 list(const value_type
* __first
, const value_type
* __last
,
136 const allocator_type
& __a
= allocator_type())
137 : _ConstructCheck(__first
, __last
),
138 _M_non_dbg_impl(__first
, __last
, __a
),
139 _M_iter_list(&_M_non_dbg_impl
) {}
140 list(const_iterator __first
, const_iterator __last
,
141 const allocator_type
& __a
= allocator_type())
142 : _ConstructCheck(__first
, __last
),
143 _M_non_dbg_impl(__first
._M_iterator
, __last
._M_iterator
, __a
),
144 _M_iter_list(&_M_non_dbg_impl
) {}
148 list(const _Self
& __x
) :
149 _ConstructCheck(__x
),
150 _M_non_dbg_impl(__x
._M_non_dbg_impl
) , _M_iter_list(&_M_non_dbg_impl
) {}
152 _Self
& operator=(const _Self
& __x
) {
154 //Should not invalidate end iterator
155 _Invalidate_iterators(begin(), end());
156 _M_non_dbg_impl
= __x
._M_non_dbg_impl
;
161 allocator_type
get_allocator() const { return _M_non_dbg_impl
.get_allocator(); }
163 iterator
begin() { return iterator(&_M_iter_list
, _M_non_dbg_impl
.begin()); }
164 const_iterator
begin() const { return const_iterator(&_M_iter_list
, _M_non_dbg_impl
.begin()); }
166 iterator
end() { return iterator(&_M_iter_list
, _M_non_dbg_impl
.end()); }
167 const_iterator
end() const { return const_iterator(&_M_iter_list
, _M_non_dbg_impl
.end()); }
169 reverse_iterator
rbegin() { return reverse_iterator(end()); }
170 reverse_iterator
rend() { return reverse_iterator(begin()); }
172 const_reverse_iterator
rbegin() const { return const_reverse_iterator(end()); }
173 const_reverse_iterator
rend() const { return const_reverse_iterator(begin()); }
175 size_type
size() const { return _M_non_dbg_impl
.size(); }
176 size_type
max_size() const { return _M_non_dbg_impl
.max_size(); }
177 bool empty() const { return _M_non_dbg_impl
.empty(); }
179 // those are here to enforce checking
181 _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER
)
184 const_reference
front() const {
185 _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER
)
189 _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER
)
192 const_reference
back() const {
193 _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER
)
197 void swap(_Self
& __x
) {
198 _M_iter_list
._Swap_owners(__x
._M_iter_list
);
199 _M_non_dbg_impl
.swap(__x
._M_non_dbg_impl
);
201 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
202 void _M_swap_workaround(_Self
& __x
) { swap(__x
); }
205 #if !defined(_STLP_DONT_SUP_DFLT_PARAM) && !defined(_STLP_NO_ANACHRONISMS)
206 iterator
insert(iterator __pos
, const _Tp
& __x
= _Tp()) {
208 iterator
insert(iterator __pos
, const _Tp
& __x
) {
209 #endif /*!_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
210 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_if_owner(&_M_iter_list
,__pos
))
211 return iterator(&_M_iter_list
,_M_non_dbg_impl
.insert(__pos
._M_iterator
, __x
) );
214 #if defined(_STLP_DONT_SUP_DFLT_PARAM) && !defined(_STLP_NO_ANACHRONISMS)
215 iterator
insert(iterator __pos
) { return insert(__pos
, _STLP_DEFAULT_CONSTRUCTED(_Tp
)); }
216 #endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
218 #if defined (_STLP_MEMBER_TEMPLATES)
219 template <class _InputIterator
>
220 void insert(iterator __pos
, _InputIterator __first
, _InputIterator __last
) {
221 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_if_owner(&_M_iter_list
, __pos
))
222 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
223 _M_non_dbg_impl
.insert(__pos
._M_iterator
,
224 _STLP_PRIV
_Non_Dbg_iter(__first
), _STLP_PRIV
_Non_Dbg_iter(__last
));
228 #if !defined (_STLP_MEMBER_TEMPLATES)
229 void insert(iterator __pos
, const _Tp
* __first
, const _Tp
* __last
) {
230 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_if_owner(&_M_iter_list
,__pos
))
231 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_ptr_range(__first
, __last
))
232 _M_non_dbg_impl
.insert(__pos
._M_iterator
, __first
, __last
);
236 #if !defined (_STLP_MEMBER_TEMPLATES) || !defined (_STLP_NO_METHOD_SPECIALIZATION)
237 void insert(iterator __pos
,
238 const_iterator __first
, const_iterator __last
) {
239 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_if_owner(&_M_iter_list
, __pos
))
240 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
241 # if (_STLP_DEBUG_LEVEL == _STLP_STANDARD_DBG_LEVEL)
242 _STLP_STD_DEBUG_CHECK(__check_if_not_owner(&_M_iter_list
, __first
))
244 _M_non_dbg_impl
.insert(__pos
._M_iterator
, __first
._M_iterator
, __last
._M_iterator
);
246 void insert(iterator __pos
,
247 iterator __first
, iterator __last
) {
248 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_if_owner(&_M_iter_list
, __pos
))
249 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
250 # if (_STLP_DEBUG_LEVEL == _STLP_STANDARD_DBG_LEVEL)
251 _STLP_STD_DEBUG_CHECK(__check_if_not_owner(&_M_iter_list
, __first
))
253 _M_non_dbg_impl
.insert(__pos
._M_iterator
, __first
._M_iterator
, __last
._M_iterator
);
257 void insert(iterator __pos
, size_type __n
, const _Tp
& __x
) {
258 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_if_owner(&_M_iter_list
,__pos
))
259 _M_non_dbg_impl
.insert(__pos
._M_iterator
, __n
, __x
);
262 void push_back(const_reference __x
) { _M_non_dbg_impl
.push_back(__x
); }
264 _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER
)
265 _Invalidate_iterator(end());
266 _M_non_dbg_impl
.pop_back();
269 void push_front(const_reference __x
) { _M_non_dbg_impl
.push_front(__x
); }
271 _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER
)
272 _Invalidate_iterator(begin());
273 _M_non_dbg_impl
.pop_front();
276 iterator
erase(iterator __pos
) {
277 _STLP_DEBUG_CHECK(_STLP_PRIV
_Dereferenceable(__pos
))
278 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_if_owner(&_M_iter_list
,__pos
))
279 _Invalidate_iterator(__pos
);
280 return iterator(&_M_iter_list
,_M_non_dbg_impl
.erase(__pos
._M_iterator
));
282 iterator
erase(iterator __first
, iterator __last
) {
283 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
, begin(), end()))
284 _Invalidate_iterators(__first
, __last
);
285 return iterator (&_M_iter_list
, _M_non_dbg_impl
.erase(__first
._M_iterator
, __last
._M_iterator
));
288 #if !defined(_STLP_DONT_SUP_DFLT_PARAM)
289 void resize(size_type __new_size
, const _Tp
& __x
= _Tp()) {
291 void resize(size_type __new_size
, const _Tp
& __x
) {
292 #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
293 _Base_iterator __i
= _M_non_dbg_impl
.begin();
295 for ( ; __i
!= _M_non_dbg_impl
.end() && __len
< __new_size
; ++__i
, ++__len
);
297 if (__len
== __new_size
)
298 erase(iterator(&_M_iter_list
, __i
), end());
300 _M_non_dbg_impl
.insert(_M_non_dbg_impl
.end(), __new_size
- __len
, __x
);
303 #if defined(_STLP_DONT_SUP_DFLT_PARAM)
304 void resize(size_type __new_size
) { resize(__new_size
, _STLP_DEFAULT_CONSTRUCTED(_Tp
)); }
307 #if defined (_STLP_MEMBER_TEMPLATES)
308 template <class _InputIterator
>
309 void assign(_InputIterator __first
, _InputIterator __last
) {
310 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
311 _M_non_dbg_impl
.assign(_STLP_PRIV
_Non_Dbg_iter(__first
), _STLP_PRIV
_Non_Dbg_iter(__last
));
312 _Invalidate_iterators(begin(), end());
315 void assign(const _Tp
* __first
, const _Tp
* __last
) {
316 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_ptr_range(__first
, __last
))
317 _M_non_dbg_impl
.assign(__first
, __last
);
318 _Invalidate_iterators(begin(), end());
321 void assign(iterator __first
, iterator __last
) {
322 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
323 _M_non_dbg_impl
.assign(__first
._M_iterator
, __last
._M_iterator
);
324 _Invalidate_iterators(begin(), end());
327 void assign(const_iterator __first
, const_iterator __last
) {
328 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
))
329 _M_non_dbg_impl
.assign(__first
._M_iterator
, __last
._M_iterator
);
330 _Invalidate_iterators(begin(), end());
334 void assign(size_type __n
, const _Tp
& __val
) {
335 _Invalidate_iterators(begin(), end());
336 _M_non_dbg_impl
.assign(__n
, __val
);
339 void remove(const _Tp
& __x
) {
340 _Base_iterator __first
= _M_non_dbg_impl
.begin(), __last
= _M_non_dbg_impl
.end();
341 while (__first
!= __last
) {
342 _Base_iterator __next
= __first
;
344 if (__x
== *__first
) {
345 _Invalidate_iterator(iterator(&_M_iter_list
, __first
));
346 _M_non_dbg_impl
.erase(__first
);
353 _Invalidate_iterators(begin(), end());
354 _M_non_dbg_impl
.clear();
358 void splice(iterator __pos
, _Self
& __x
) {
359 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_if_owner(&_M_iter_list
,__pos
))
360 _M_non_dbg_impl
.splice(__pos
._M_iterator
, __x
._M_non_dbg_impl
);
361 #if (_STLP_DEBUG_LEVEL != _STLP_STANDARD_DBG_LEVEL)
362 if (get_allocator() == __x
.get_allocator())
363 __x
._M_iter_list
._Set_owner(_M_iter_list
);
367 // end iterator is not invalidated:
368 __x
._Invalidate_iterators(__x
.begin(), __x
.end());
371 void splice(iterator __pos
, _Self
& __x
, iterator __i
) {
372 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_if_owner(&_M_iter_list
,__pos
))
373 _STLP_DEBUG_CHECK(_STLP_PRIV
_Dereferenceable(__i
))
374 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_if_owner(&(__x
._M_iter_list
),__i
))
375 _M_non_dbg_impl
.splice(__pos
._M_iterator
, __x
._M_non_dbg_impl
, __i
._M_iterator
);
376 #if (_STLP_DEBUG_LEVEL != _STLP_STANDARD_DBG_LEVEL)
377 if (get_allocator() == __x
.get_allocator())
378 _STLP_PRIV
__change_ite_owner(__i
, &_M_iter_list
);
382 __x
._Invalidate_iterator(__i
);
385 void splice(iterator __pos
, _Self
& __x
, iterator __first
, iterator __last
) {
386 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_if_owner(&_M_iter_list
, __pos
))
387 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
, __x
.begin(), __x
.end()))
388 _STLP_DEBUG_CHECK(this == &__x
? !_STLP_PRIV
__check_range(__pos
, __first
, __last
) : true)
389 #if (_STLP_DEBUG_LEVEL != _STLP_STANDARD_DBG_LEVEL)
390 if (this->get_allocator() == __x
.get_allocator())
391 _STLP_PRIV
__change_range_owner(__first
, __last
, &_M_iter_list
);
395 __x
._Invalidate_iterators(__first
, __last
);
396 _M_non_dbg_impl
.splice(__pos
._M_iterator
, __x
._M_non_dbg_impl
, __first
._M_iterator
, __last
._M_iterator
);
399 void merge(_Self
& __x
) {
400 #if !defined (_STLP_NO_EXTENSIONS)
401 _STLP_DEBUG_CHECK(_STLP_STD::is_sorted(begin()._M_iterator
, end()._M_iterator
))
402 _STLP_DEBUG_CHECK(_STLP_STD::is_sorted(__x
.begin()._M_iterator
, __x
.end()._M_iterator
))
404 _M_non_dbg_impl
.merge(__x
._M_non_dbg_impl
);
405 if (this->get_allocator() == __x
.get_allocator()) {
406 __x
._M_iter_list
._Set_owner(_M_iter_list
);
409 __x
._Invalidate_iterators(__x
.begin(), __x
.end());
413 _M_non_dbg_impl
.reverse();
416 _Base_iterator __first
= _M_non_dbg_impl
.begin(), __last
= _M_non_dbg_impl
.end();
417 if (__first
== __last
) return;
418 _Base_iterator __next
= __first
;
419 while (++__next
!= __last
) {
420 if (*__first
== *__next
) {
421 _Invalidate_iterator(iterator(&_M_iter_list
, __next
));
422 _M_non_dbg_impl
.erase(__next
);
430 _M_non_dbg_impl
.sort();
433 #if defined (_STLP_MEMBER_TEMPLATES)
434 template <class _Predicate
>
435 void remove_if(_Predicate __pred
) {
436 _Base_iterator __first
= _M_non_dbg_impl
.begin(), __last
= _M_non_dbg_impl
.end();
437 while (__first
!= __last
) {
438 _Base_iterator __next
= __first
;
440 if (__pred(*__first
)) {
441 _Invalidate_iterator(iterator(&_M_iter_list
, __first
));
442 _M_non_dbg_impl
.erase(__first
);
448 template <class _BinaryPredicate
>
449 void unique(_BinaryPredicate __binary_pred
) {
450 _Base_iterator __first
= _M_non_dbg_impl
.begin(), __last
= _M_non_dbg_impl
.end();
451 if (__first
== __last
) return;
452 _Base_iterator __next
= __first
;
453 while (++__next
!= __last
) {
454 if (__binary_pred(*__first
, *__next
)) {
455 _Invalidate_iterator(iterator(&_M_iter_list
, __next
));
456 _M_non_dbg_impl
.erase(__next
);
464 template <class _StrictWeakOrdering
>
465 void merge(_Self
& __x
, _StrictWeakOrdering __comp
) {
466 #if !defined (_STLP_NO_EXTENSIONS)
467 _STLP_DEBUG_CHECK(_STLP_STD::is_sorted(_M_non_dbg_impl
.begin(), _M_non_dbg_impl
.end(), __comp
))
468 _STLP_DEBUG_CHECK(_STLP_STD::is_sorted(__x
.begin()._M_iterator
, __x
.end()._M_iterator
, __comp
))
470 _M_non_dbg_impl
.merge(__x
._M_non_dbg_impl
, __comp
);
471 if (this->get_allocator() == __x
.get_allocator()) {
472 __x
._M_iter_list
._Set_owner(_M_iter_list
);
475 __x
._Invalidate_iterators(__x
.begin(), __x
.end());
479 template <class _StrictWeakOrdering
>
480 void sort(_StrictWeakOrdering __comp
) {
481 _M_non_dbg_impl
.sort(__comp
);
489 #undef _STLP_NON_DBG_LIST
491 #endif /* _STLP_INTERNAL_LIST_H */