ReactOS 0.4.15-dev-7842-g558ab78
_tree.h
Go to the documentation of this file.
1/*
2 *
3 * Copyright (c) 1994
4 * Hewlett-Packard Company
5 *
6 * Copyright (c) 1996,1997
7 * Silicon Graphics Computer Systems, Inc.
8 *
9 * Copyright (c) 1997
10 * Moscow Center for SPARC Technology
11 *
12 * Copyright (c) 1999
13 * Boris Fomitchev
14 *
15 * This material is provided "as is", with absolutely no warranty expressed
16 * or implied. Any use is at your own risk.
17 *
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.
23 *
24 */
25
26/* NOTE: This is an internal header file, included by other STL headers.
27 * You should not attempt to use it directly.
28 */
29
30#ifndef _STLP_INTERNAL_DBG_TREE_H
31#define _STLP_INTERNAL_DBG_TREE_H
32
33#ifndef _STLP_DBG_ITERATOR_H
34# include <stl/debug/_iterator.h>
35#endif
36
37#ifndef _STLP_INTERNAL_FUNCTION_BASE_H
38# include <stl/_function_base.h>
39#endif
40
41#ifndef _STLP_INTERNAL_ALLOC_H
42# include <stl/_alloc.h>
43#endif
44
46
48
49template <class _Key, class _Compare>
51public:
53 _DbgCompare(const _Compare& __cmp) : _M_non_dbg_cmp(__cmp) {}
55
56#if !defined (_STLP_USE_CONTAINERS_EXTENSION)
57 bool operator () (const _Key& __lhs, const _Key& __rhs) const {
58#else
59 template <class _Kp1, class _Kp2>
60 bool operator () (const _Kp1& __lhs, const _Kp2& __rhs) const {
61#endif
62 if (_M_non_dbg_cmp(__lhs, __rhs)) {
63 return true;
64 }
65 return false;
66 }
67
68 _Compare non_dbg_key_comp() const { return _M_non_dbg_cmp; }
69private:
71};
72
73#define _STLP_NON_DBG_TREE _STLP_PRIV _STLP_NON_DBG_NAME(Rb_tree) <_Key, _STLP_PRIV _DbgCompare<_Key, _Compare>, _Value, _KeyOfValue, _Traits, _Alloc>
74
75#if defined (_STLP_DEBUG_USE_DISTINCT_VALUE_TYPE_HELPERS)
77template <class _Key, class _Compare,
78 class _Value, class _KeyOfValue, class _Traits, class _Alloc >
79inline _Value*
81{ return (_Value*)0; }
82template <class _Key, class _Compare,
83 class _Value, class _KeyOfValue, class _Traits, class _Alloc >
88#endif
89
90template <class _Key, class _Compare,
91 class _Value, class _KeyOfValue, class _Traits,
93class _Rb_tree {
98
99public:
102
107
109
110private:
112 void _Invalidate_iterator(const iterator& __it)
113 { _STLP_PRIV __invalidate_iterator(&_M_iter_list,__it); }
114 void _Invalidate_iterators(const iterator& __first, const iterator& __last)
115 { _STLP_PRIV __invalidate_range(&_M_iter_list, __first, __last); }
116
117 typedef typename _Base::iterator _Base_iterator;
118 typedef typename _Base::const_iterator _Base_const_iterator;
119
120public:
122 : _M_non_dbg_impl(), _M_iter_list(&_M_non_dbg_impl) {}
123 _Rb_tree(const _Compare& __comp)
124 : _M_non_dbg_impl(__comp), _M_iter_list(&_M_non_dbg_impl) {}
125 _Rb_tree(const _Compare& __comp, const allocator_type& __a)
126 : _M_non_dbg_impl(__comp, __a), _M_iter_list(&_M_non_dbg_impl) {}
127 _Rb_tree(const _Self& __x)
128 : _M_non_dbg_impl(__x._M_non_dbg_impl), _M_iter_list(&_M_non_dbg_impl) {}
129
130#if !defined (_STLP_NO_MOVE_SEMANTIC)
132 _M_non_dbg_impl(__move_source<_Base>(src.get()._M_non_dbg_impl)),
133 _M_iter_list(&_M_non_dbg_impl) {
134# if defined (_STLP_NO_EXTENSIONS) || (_STLP_DEBUG_LEVEL == _STLP_STANDARD_DBG_LEVEL)
135 src.get()._M_iter_list._Invalidate_all();
136# else
137 src.get()._M_iter_list._Set_owner(_M_iter_list);
138# endif
139 }
140#endif
141
143
144 _Self& operator=(const _Self& __x) {
145 if (this != &__x) {
146 //Should not invalidate end iterator:
147 _Invalidate_iterators(begin(), end());
148 _M_non_dbg_impl = __x._M_non_dbg_impl;
149 }
150 return *this;
151 }
152
153 allocator_type get_allocator() const { return _M_non_dbg_impl.get_allocator(); }
154 _Compare key_comp() const { return _M_non_dbg_impl.key_comp().non_dbg_key_comp(); }
155
156 iterator begin() { return iterator(&_M_iter_list, _M_non_dbg_impl.begin()); }
157 const_iterator begin() const { return const_iterator(&_M_iter_list, _M_non_dbg_impl.begin()); }
158 iterator end() { return iterator(&_M_iter_list, _M_non_dbg_impl.end()); }
159 const_iterator end() const { return const_iterator(&_M_iter_list, _M_non_dbg_impl.end()); }
160
162 const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
164 const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
165
166 bool empty() const { return _M_non_dbg_impl.empty(); }
167 size_type size() const { return _M_non_dbg_impl.size(); }
168 size_type max_size() const { return _M_non_dbg_impl.max_size(); }
170 size_type count(const _KT& __x) const { return _M_non_dbg_impl.count(__x); }
171
172 void swap(_Self& __t) {
173 _M_non_dbg_impl.swap(__t._M_non_dbg_impl);
174 _M_iter_list._Swap_owners(__t._M_iter_list);
175 }
176
178 iterator find(const _KT& __k)
179 { return iterator(&_M_iter_list, _M_non_dbg_impl.find(__k)); }
181 const_iterator find(const _KT& __k) const
182 { return const_iterator(&_M_iter_list, _M_non_dbg_impl.find(__k)); }
183
185 iterator lower_bound(const _KT& __x)
186 { return iterator(&_M_iter_list, _M_non_dbg_impl.lower_bound(__x)); }
188 const_iterator lower_bound(const _KT& __x) const
189 { return const_iterator(&_M_iter_list, _M_non_dbg_impl.lower_bound(__x)); }
190
192 iterator upper_bound(const _KT& __x)
193 { return iterator(&_M_iter_list, _M_non_dbg_impl.upper_bound(__x)); }
195 const_iterator upper_bound(const _KT& __x) const
196 { return const_iterator(&_M_iter_list, _M_non_dbg_impl.upper_bound(__x)); }
197
200 return pair<iterator, iterator>(iterator(&_M_iter_list, _M_non_dbg_impl.lower_bound(__x)),
201 iterator(&_M_iter_list, _M_non_dbg_impl.upper_bound(__x)));
202 }
205 return pair<const_iterator,const_iterator>(const_iterator(&_M_iter_list, _M_non_dbg_impl.lower_bound(__x)),
206 const_iterator(&_M_iter_list, _M_non_dbg_impl.upper_bound(__x)));
207 }
208
211 _STLP_STD::pair<_Base_iterator, _Base_iterator> __p;
212 __p = _M_non_dbg_impl.equal_range_unique(__x);
213 return pair<iterator, iterator>(iterator(&_M_iter_list, __p.first), iterator(&_M_iter_list, __p.second));
214 }
217 _STLP_STD::pair<_Base_const_iterator, _Base_const_iterator> __p;
218 __p = _M_non_dbg_impl.equal_range_unique(__x);
219 return pair<const_iterator, const_iterator>(const_iterator(&_M_iter_list, __p.first),
220 const_iterator(&_M_iter_list, __p.second));
221 }
222
224 _STLP_STD::pair<_Base_iterator, bool> __res = _M_non_dbg_impl.insert_unique(__x);
225 return pair<iterator, bool>(iterator(&_M_iter_list, __res.first), __res.second);
226 }
228 { return iterator(&_M_iter_list, _M_non_dbg_impl.insert_equal(__x)); }
229
231 _STLP_DEBUG_CHECK(__check_if_owner(&_M_iter_list,__pos))
232 return iterator(&_M_iter_list, _M_non_dbg_impl.insert_unique(__pos._M_iterator, __x));
233 }
235 _STLP_DEBUG_CHECK(__check_if_owner(&_M_iter_list, __pos))
236 return iterator(&_M_iter_list, _M_non_dbg_impl.insert_equal(__pos._M_iterator, __x));
237 }
238
239#if defined (_STLP_MEMBER_TEMPLATES)
240 template<class _InputIterator>
241 void insert_equal(_InputIterator __first, _InputIterator __last) {
242 _STLP_DEBUG_CHECK(__check_range(__first,__last))
243 _M_non_dbg_impl.insert_equal(_STLP_PRIV _Non_Dbg_iter(__first), _STLP_PRIV _Non_Dbg_iter(__last));
244 }
245 template<class _InputIterator>
246 void insert_unique(_InputIterator __first, _InputIterator __last) {
247 _STLP_DEBUG_CHECK(__check_range(__first,__last))
248 _M_non_dbg_impl.insert_unique(_STLP_PRIV _Non_Dbg_iter(__first), _STLP_PRIV _Non_Dbg_iter(__last));
249 }
250#else
252 _STLP_DEBUG_CHECK(__check_range(__first,__last))
253 _M_non_dbg_impl.insert_unique(__first._M_iterator, __last._M_iterator);
254 }
255 void insert_unique(const value_type* __first, const value_type* __last) {
256 _STLP_DEBUG_CHECK(__check_ptr_range(__first,__last))
257 _M_non_dbg_impl.insert_unique(__first, __last);
258 }
260 _STLP_DEBUG_CHECK(__check_range(__first,__last))
261 _M_non_dbg_impl.insert_equal(__first._M_iterator, __last._M_iterator);
262 }
263 void insert_equal(const value_type* __first, const value_type* __last) {
264 _STLP_DEBUG_CHECK(__check_ptr_range(__first,__last))
265 _M_non_dbg_impl.insert_equal(__first, __last);
266 }
267#endif
268
269 void erase(iterator __pos) {
270 _STLP_DEBUG_CHECK(__check_if_owner(&_M_iter_list,__pos))
272 _Invalidate_iterator(__pos);
273 _M_non_dbg_impl.erase(__pos._M_iterator);
274 }
277 size_type __n = _STLP_STD::distance(__p.first._M_iterator, __p.second._M_iterator);
278 _Invalidate_iterators(__p.first, __p.second);
279 _M_non_dbg_impl.erase(__p.first._M_iterator, __p.second._M_iterator);
280 return __n;
281 }
283 _Base_iterator __i = _M_non_dbg_impl.find(__x);
284 if (__i != _M_non_dbg_impl.end()) {
285 _Invalidate_iterator(iterator(&_M_iter_list, __i));
286 _M_non_dbg_impl.erase(__i);
287 return 1;
288 }
289 return 0;
290 }
291
292 void erase(iterator __first, iterator __last) {
293 _STLP_DEBUG_CHECK(__check_range(__first, __last, begin(), end()))
294 _Invalidate_iterators(__first, __last);
295 _M_non_dbg_impl.erase(__first._M_iterator, __last._M_iterator);
296 }
297 void erase(const key_type* __first, const key_type* __last) {
298 while (__first != __last) erase(*__first++);
299 }
300
301 void clear() {
302 //should not invalidate end:
303 _Invalidate_iterators(begin(), end());
304 _M_non_dbg_impl.clear();
305 }
306};
307
310
311#undef _STLP_NON_DBG_TREE
312
313#endif /* _STLP_INTERNAL_DBG_TREE_H */
314
315// Local Variables:
316// mode:C++
317// End:
#define reverse_iterator
Definition: _abbrevs.h:34
#define bidirectional_iterator_tag
Definition: _abbrevs.h:27
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
_STLP_MOVE_TO_STD_NAMESPACE pair< _ForwardIter, _ForwardIter > equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp &__val)
Definition: _algo.h:535
return __n
Definition: _algo.h:75
#define _Alloc
Definition: _bvector.h:330
#define _STLP_DEBUG_CHECK(expr)
Definition: _debug.h:440
#define _STLP_PRIV
Definition: _dm.h:70
_STLP_MOVE_TO_PRIV_NAMESPACE const _InputIterator const input_iterator_tag &_InputIterator __it(__first)
void get(int argc, const char *argv[])
Definition: cmds.c:480
bool operator()(const _Key &__lhs, const _Key &__rhs) const
Definition: _tree.h:57
_DbgCompare(const _Compare &__cmp)
Definition: _tree.h:53
_Compare _M_non_dbg_cmp
Definition: _tree.h:70
_Compare non_dbg_key_comp() const
Definition: _tree.h:68
_DbgCompare(const _DbgCompare &__cmp)
Definition: _tree.h:54
_DbgCompare()
Definition: _tree.h:52
allocator_type get_allocator() const
Definition: _tree.h:244
_Key key_type
Definition: _tree.h:301
_Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc > _Self
Definition: _tree.h:95
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator lower_bound(const _KT &__x) const
Definition: _tree.h:188
_STLP_TEMPLATE_FOR_CONT_EXT iterator lower_bound(const _KT &__x)
Definition: _tree.h:185
_Rb_tree(const _Compare &__comp)
Definition: _tree.h:123
_Rb_tree(__move_source< _Self > src)
Definition: _tree.h:131
_Traits::_ConstTraits _ConstIteTraits
Definition: _tree.h:104
_Traits::_NonConstTraits _NonConstTraits
Definition: _tree.h:369
reverse_iterator rend()
Definition: _tree.h:163
_STLP_TEMPLATE_FOR_CONT_EXT pair< const_iterator, const_iterator > equal_range(const _KT &__x) const
Definition: _tree.h:204
const_reverse_iterator rbegin() const
Definition: _tree.h:162
_Compare key_comp() const
Definition: _tree.h:154
allocator_type get_allocator() const
Definition: _tree.h:153
_Rb_tree()
Definition: _tree.h:121
void clear()
Definition: _tree.h:301
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator upper_bound(const _KT &__x) const
Definition: _tree.h:195
_STLP_TEMPLATE_FOR_CONT_EXT pair< iterator, iterator > equal_range(const _KT &__x)
Definition: _tree.h:199
const_iterator begin() const
Definition: _tree.h:157
size_t size_type
Definition: _tree.h:307
_Value value_type
Definition: _tree.h:302
_STLP_TEMPLATE_FOR_CONT_EXT iterator find(const _KT &__k)
Definition: _tree.h:178
_Traits::_NonConstTraits _NonConstIteTraits
Definition: _tree.h:103
pair< iterator, bool > insert_unique(const value_type &__x)
Definition: _tree.h:223
size_type size() const
Definition: _tree.h:167
const_reverse_iterator rend() const
Definition: _tree.h:164
void erase(const key_type *__first, const key_type *__last)
Definition: _tree.h:297
~_Rb_tree()
Definition: _tree.h:142
iterator begin()
Definition: _tree.h:156
void erase(iterator __first, iterator __last)
Definition: _tree.h:292
void insert_equal(const_iterator __first, const_iterator __last)
Definition: _tree.h:259
_STLP_TEMPLATE_FOR_CONT_EXT size_type count(const _KT &__x) const
Definition: _tree.h:170
void swap(_Self &__t)
Definition: _tree.h:172
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator find(const _KT &__k) const
Definition: _tree.h:181
_STLP_TEMPLATE_FOR_CONT_EXT pair< iterator, iterator > equal_range_unique(const _KT &__x)
Definition: _tree.h:210
reverse_iterator rbegin()
Definition: _tree.h:161
void _Invalidate_iterators(const iterator &__first, const iterator &__last)
Definition: _tree.h:114
_STLP_TEMPLATE_FOR_CONT_EXT iterator upper_bound(const _KT &__x)
Definition: _tree.h:192
_Traits::_ConstTraits _ConstTraits
Definition: _tree.h:370
iterator insert_equal(iterator __pos, const value_type &__x)
Definition: _tree.h:234
_STLP_TEMPLATE_FOR_CONT_EXT pair< const_iterator, const_iterator > equal_range_unique(const _KT &__x) const
Definition: _tree.h:216
_Base::allocator_type allocator_type
Definition: _tree.h:310
iterator insert_unique(iterator __pos, const value_type &__x)
Definition: _tree.h:230
iterator end()
Definition: _tree.h:158
_STLP_PRIV __owned_list _M_iter_list
Definition: _tree.h:97
_Base _M_non_dbg_impl
Definition: _tree.h:96
void insert_unique(const_iterator __first, const_iterator __last)
Definition: _tree.h:251
iterator insert_equal(const value_type &__x)
Definition: _tree.h:227
size_type erase_unique(const key_type &__x)
Definition: _tree.h:282
size_type erase(const key_type &__x)
Definition: _tree.h:275
_Rb_tree(const _Self &__x)
Definition: _tree.h:127
void insert_equal(const value_type *__first, const value_type *__last)
Definition: _tree.h:263
_STLP_NON_DBG_TREE _Base
Definition: _tree.h:94
_Self & operator=(const _Self &__x)
Definition: _tree.h:144
_Rb_tree(const _Compare &__comp, const allocator_type &__a)
Definition: _tree.h:125
_Base::iterator _Base_iterator
Definition: _tree.h:117
void insert_unique(const value_type *__first, const value_type *__last)
Definition: _tree.h:255
_Base::const_iterator _Base_const_iterator
Definition: _tree.h:118
size_type max_size() const
Definition: _tree.h:168
const_iterator end() const
Definition: _tree.h:159
bool empty() const
Definition: _tree.h:166
void erase(iterator __pos)
Definition: _tree.h:269
int _Value
Definition: setjmp.h:214
_Iterator _Non_Dbg_iter(_Iterator __it)
Definition: _iterator.h:362
bool _Dereferenceable(const _Iterator &__it)
Definition: _iterator.h:93
#define _STLP_NON_DBG_TREE
Definition: _tree.h:73
#define _STLP_TEMPLATE_FOR_CONT_EXT
Definition: features.h:623
#define _STLP_MOVE_TO_STD_NAMESPACE
Definition: features.h:525
#define _STLP_DECLARE_BIDIRECTIONAL_REVERSE_ITERATORS
Definition: features.h:745
#define __IMPORT_CONTAINER_TYPEDEFS(_Super)
Definition: features.h:750
#define _STLP_DFL_TMPL_PARAM(classname, defval)
Definition: features.h:338
#define _STLP_KEY_TYPE_FOR_CONT_EXT(type)
Definition: features.h:622
#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
char typename[32]
Definition: main.c:84
GLuint GLuint end
Definition: gl.h:1545
GLenum src
Definition: glext.h:6340
Definition: _pair.h:47
_T2 second
Definition: _pair.h:52
_T1 first
Definition: _pair.h:51
static clock_t begin
Definition: xmllint.c:458
#define const
Definition: zconf.h:233