ReactOS  0.4.13-dev-92-gf251225
_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 
49 template <class _Key, class _Compare>
50 class _DbgCompare {
51 public:
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; }
69 private:
70  _Compare _M_non_dbg_cmp;
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)
77 template <class _Key, class _Compare,
78  class _Value, class _KeyOfValue, class _Traits, class _Alloc >
79 inline _Value*
81 { return (_Value*)0; }
82 template <class _Key, class _Compare,
83  class _Value, class _KeyOfValue, class _Traits, class _Alloc >
85 iterator_category(const _STLP_PRIV _DBG_iter_base< _STLP_NON_DBG_TREE >&)
86 { return bidirectional_iterator_tag(); }
88 #endif
89 
90 template <class _Key, class _Compare,
91  class _Value, class _KeyOfValue, class _Traits,
93 class _Rb_tree {
97  _STLP_PRIV __owned_list _M_iter_list;
98 
99 public:
102 
107 
109 
110 private:
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 
120 public:
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  }
275  size_type erase(const key_type& __x) {
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:
_Rb_tree(__move_source< _Self > src)
Definition: _tree.h:131
iterator insert_equal(const value_type &__x)
Definition: _tree.h:227
#define bidirectional_iterator_tag
Definition: _abbrevs.h:27
size_type size() const
Definition: _tree.h:167
const_reverse_iterator rbegin() const
Definition: _tree.h:162
void _Invalidate_iterators(const iterator &__first, const iterator &__last)
Definition: _tree.h:114
_Rb_tree(const _Compare &__comp)
Definition: _tree.h:123
_Rb_tree(const _Compare &__comp, const allocator_type &__a)
Definition: _tree.h:125
return __n
Definition: _algo.h:75
size_type erase(const key_type &__x)
Definition: _tree.h:275
#define _STLP_DFL_TMPL_PARAM(classname, defval)
Definition: features.h:338
char typename[32]
Definition: main.c:84
allocator_type get_allocator() const
Definition: _tree.h:244
#define _Alloc
Definition: _bvector.h:330
_STLP_TEMPLATE_FOR_CONT_EXT iterator upper_bound(const _KT &__x)
Definition: _tree.h:192
#define reverse_iterator
Definition: _abbrevs.h:34
pair< iterator, bool > insert_unique(const value_type &__x)
Definition: _tree.h:223
#define _STLP_TEMPLATE_FOR_CONT_EXT
Definition: features.h:623
bool _Dereferenceable(const _Iterator &__it)
Definition: _iterator.h:93
iterator end()
Definition: _tree.h:158
_Compare _M_non_dbg_cmp
Definition: _tree.h:70
const_reverse_iterator rend() const
Definition: _tree.h:164
GLuint GLuint end
Definition: gl.h:1545
~_Rb_tree()
Definition: _tree.h:142
_STLP_TEMPLATE_FOR_CONT_EXT iterator lower_bound(const _KT &__x)
Definition: _tree.h:185
const_iterator begin() const
Definition: _tree.h:157
_STLP_TEMPLATE_FOR_CONT_EXT pair< const_iterator, const_iterator > equal_range_unique(const _KT &__x) const
Definition: _tree.h:216
GLsizei GLsizei GLfloat distance
Definition: glext.h:11755
#define _STLP_MOVE_TO_PRIV_NAMESPACE
Definition: features.h:524
_Base::iterator _Base_iterator
Definition: _tree.h:117
bool operator()(const _Key &__lhs, const _Key &__rhs) const
Definition: _tree.h:57
_Base::const_iterator _Base_const_iterator
Definition: _tree.h:118
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator upper_bound(const _KT &__x) const
Definition: _tree.h:195
void insert_unique(const_iterator __first, const_iterator __last)
Definition: _tree.h:251
iterator insert_equal(iterator __pos, const value_type &__x)
Definition: _tree.h:234
_STLP_TEMPLATE_FOR_CONT_EXT size_type count(const _KT &__x) const
Definition: _tree.h:170
_STLP_TEMPLATE_FOR_CONT_EXT pair< iterator, iterator > equal_range_unique(const _KT &__x)
Definition: _tree.h:210
iterator begin()
Definition: _tree.h:156
void insert_equal(const_iterator __first, const_iterator __last)
Definition: _tree.h:259
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
static clock_t begin
Definition: xmllint.c:466
#define __IMPORT_CONTAINER_TYPEDEFS(_Super)
Definition: features.h:750
_Base _M_non_dbg_impl
Definition: _tree.h:96
_T1 first
Definition: _pair.h:51
_Iterator _Non_Dbg_iter(_Iterator __it)
Definition: _iterator.h:362
_STLP_PRIV __owned_list _M_iter_list
Definition: _tree.h:97
#define _STLP_MOVE_TO_STD_NAMESPACE
Definition: features.h:525
void get(int argc, const char *argv[])
Definition: cmds.c:480
allocator_type get_allocator() const
Definition: _tree.h:153
iterator insert_unique(iterator __pos, const value_type &__x)
Definition: _tree.h:230
_STLP_TEMPLATE_FOR_CONT_EXT pair< iterator, iterator > equal_range(const _KT &__x)
Definition: _tree.h:199
_DbgCompare(const _Compare &__cmp)
Definition: _tree.h:53
void insert_equal(const value_type *__first, const value_type *__last)
Definition: _tree.h:263
void insert_unique(const value_type *__first, const value_type *__last)
Definition: _tree.h:255
reverse_iterator rend()
Definition: _tree.h:163
_Compare key_comp() const
Definition: _tree.h:154
_Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc > _Self
Definition: _tree.h:95
reverse_iterator rbegin()
Definition: _tree.h:161
_STLP_MOVE_TO_PRIV_NAMESPACE const _InputIterator const input_iterator_tag &_InputIterator __it(__first)
void swap(_Self &__t)
Definition: _tree.h:172
_DbgCompare(const _DbgCompare &__cmp)
Definition: _tree.h:54
_STLP_MOVE_TO_STD_NAMESPACE pair< _ForwardIter, _ForwardIter > equal_range(_ForwardIter __first, _ForwardIter __last, const _Tp &__val)
Definition: _algo.h:535
_Compare non_dbg_key_comp() const
Definition: _tree.h:68
#define _STLP_PRIV
Definition: _dm.h:70
_Rb_tree(const _Self &__x)
Definition: _tree.h:127
#define _STLP_DEBUG_CHECK(expr)
Definition: _debug.h:440
GLenum src
Definition: glext.h:6340
#define _STLP_NON_DBG_TREE
Definition: _tree.h:73
#define _STLP_KEY_TYPE_FOR_CONT_EXT(type)
Definition: features.h:622
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator find(const _KT &__k) const
Definition: _tree.h:181
const_iterator end() const
Definition: _tree.h:159
void erase(iterator __pos)
Definition: _tree.h:269
size_type erase_unique(const key_type &__x)
Definition: _tree.h:282
#define _STLP_END_NAMESPACE
Definition: features.h:503
Definition: _pair.h:47
void erase(iterator __first, iterator __last)
Definition: _tree.h:292
_T2 second
Definition: _pair.h:52
_Self & operator=(const _Self &__x)
Definition: _tree.h:144
_DbgCompare()
Definition: _tree.h:52
_Rb_tree()
Definition: _tree.h:121
size_type max_size() const
Definition: _tree.h:168
#define const
Definition: zconf.h:230
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator lower_bound(const _KT &__x) const
Definition: _tree.h:188
_STLP_NON_DBG_TREE _Base
Definition: _tree.h:94
#define _STLP_BEGIN_NAMESPACE
Definition: features.h:501
int _Value
Definition: setjmp.h:188
_STLP_TEMPLATE_FOR_CONT_EXT pair< const_iterator, const_iterator > equal_range(const _KT &__x) const
Definition: _tree.h:204
_STLP_TEMPLATE_FOR_CONT_EXT iterator find(const _KT &__k)
Definition: _tree.h:178
void clear()
Definition: _tree.h:301
#define _STLP_DECLARE_BIDIRECTIONAL_REVERSE_ITERATORS
Definition: features.h:745
void erase(const key_type *__first, const key_type *__last)
Definition: _tree.h:297
bool empty() const
Definition: _tree.h:166