ReactOS  0.4.14-dev-608-gd495a4f
_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_TREE_H
31 #define _STLP_INTERNAL_TREE_H
32 
33 /*
34 
35 Red-black tree class, designed for use in implementing STL
36 associative containers (set, multiset, map, and multimap). The
37 insertion and deletion algorithms are based on those in Cormen,
38 Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),
39 except that
40 
41 (1) the header cell is maintained with links not only to the root
42 but also to the leftmost node of the tree, to enable constant time
43 begin(), and to the rightmost node of the tree, to enable linear time
44 performance when used with the generic set algorithms (set_union,
45 etc.);
46 
47 (2) when a node being deleted has two children its successor node is
48 relinked into its place, rather than copied, so that the only
49 iterators invalidated are those referring to the deleted node.
50 
51 */
52 
53 #ifndef _STLP_INTERNAL_ALGOBASE_H
54 # include <stl/_algobase.h>
55 #endif
56 
57 #ifndef _STLP_INTERNAL_ALLOC_H
58 # include <stl/_alloc.h>
59 #endif
60 
61 #ifndef _STLP_INTERNAL_ITERATOR_H
62 # include <stl/_iterator.h>
63 #endif
64 
65 #ifndef _STLP_INTERNAL_CONSTRUCT_H
66 # include <stl/_construct.h>
67 #endif
68 
69 #ifndef _STLP_INTERNAL_FUNCTION_BASE_H
70 # include <stl/_function_base.h>
71 #endif
72 
74 
76 
77 typedef bool _Rb_tree_Color_type;
78 //const _Rb_tree_Color_type _S_rb_tree_red = false;
79 //const _Rb_tree_Color_type _S_rb_tree_black = true;
80 
81 #define _S_rb_tree_red false
82 #define _S_rb_tree_black true
83 
87 
92 
94  while (__x->_M_left != 0) __x = __x->_M_left;
95  return __x;
96  }
97 
99  while (__x->_M_right != 0) __x = __x->_M_right;
100  return __x;
101  }
102 };
103 
104 template <class _Value>
108 };
109 
111 
112 template <class _Dummy>
113 class _Rb_global {
114 public:
116  // those used to be global functions
117  static void _STLP_CALL _Rebalance(_Base_ptr __x, _Base_ptr& __root);
119  _Base_ptr& __root,
120  _Base_ptr& __leftmost,
121  _Base_ptr& __rightmost);
122  // those are from _Rb_tree_base_iterator - moved here to reduce code bloat
123  // moved here to reduce code bloat without templatizing _Rb_tree_base_iterator
126  static void _STLP_CALL _Rotate_left (_Base_ptr __x, _Base_ptr& __root);
127  static void _STLP_CALL _Rotate_right(_Base_ptr __x, _Base_ptr& __root);
128 };
129 
130 # if defined (_STLP_USE_TEMPLATE_EXPORT)
132 # endif
133 
135 
143 };
144 
145 template <class _Value, class _Traits>
148  typedef typename _Traits::reference reference;
149  typedef typename _Traits::pointer pointer;
153 
154  typedef typename _Traits::_NonConstTraits _NonConstTraits;
156  typedef typename _Traits::_ConstTraits _ConstTraits;
158 
160 #if !defined (_STLP_DEBUG)
161  /* In STL debug mode we need this constructor implicit for the pointer
162  * specialization implementation.
163  */
164  explicit
165 #endif
167  //copy constructor for iterator and constructor from iterator for const_iterator
169 
171  return __STATIC_CAST(_Link_type, _M_node)->_M_value_field;
172  }
173 
175 
178  return *this;
179  }
181  _Self __tmp = *this;
182  ++(*this);
183  return __tmp;
184  }
185 
188  return *this;
189  }
191  _Self __tmp = *this;
192  --(*this);
193  return __tmp;
194  }
195 
196  bool operator == (const_iterator __rhs) const {
197  return _M_node == __rhs._M_node;
198  }
199  bool operator != (const_iterator __rhs) const {
200  return _M_node != __rhs._M_node;
201  }
202 };
203 
204 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
206 template <class _Value, class _Traits>
212  typedef __false_type is_POD_type;
213 };
215 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
216 
217 #if defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES)
219 template <class _Value, class _Traits>
220 inline _Value* value_type(const _STLP_PRIV _Rb_tree_iterator<_Value, _Traits>&)
221 { return (_Value*)0; }
222 inline bidirectional_iterator_tag iterator_category(const _STLP_PRIV _Rb_tree_base_iterator&)
223 { return bidirectional_iterator_tag(); }
224 inline ptrdiff_t* distance_type(const _STLP_PRIV _Rb_tree_base_iterator&)
225 { return (ptrdiff_t*) 0; }
227 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
228 
229 // Base class to help EH
230 
231 template <class _Tp, class _Alloc>
233 public:
238 private:
239  typedef _Rb_tree_base<_Tp, _Alloc> _Self;
242 
243 public:
245  return _STLP_CONVERT_ALLOCATOR(_M_header, _Tp);
246  }
247 
248 protected:
252  }
253 
254 #if !defined (_STLP_NO_MOVE_SEMANTIC)
257  _M_rebind(&src.get()._M_header._M_data);
258  src.get()._M_empty_initialize();
259  }
260 #endif
261 
263  _M_header._M_data._M_color = _S_rb_tree_red; // used to distinguish header from
264  // __root, in iterator.operator++
268  }
269 
270  void _M_rebind(_Node_base *__static_node) {
271  if (_M_header._M_data._M_parent != 0) {
273  }
274  if (_M_header._M_data._M_right == __static_node) {
276  }
277  if (_M_header._M_data._M_left == __static_node) {
279  }
280  }
281 
283 };
284 
285 #if defined (_STLP_DEBUG)
286 # define _Rb_tree _STLP_NON_DBG_NAME(Rb_tree)
287 #endif
288 
289 template <class _Key, class _Compare,
290  class _Value, class _KeyOfValue, class _Traits,
292 class _Rb_tree : public _Rb_tree_base<_Value, _Alloc> {
295 protected:
298  typedef _Node* _Link_type;
300 public:
301  typedef _Key key_type;
303  typedef typename _Traits::pointer pointer;
304  typedef const value_type* const_pointer;
305  typedef typename _Traits::reference reference;
306  typedef const value_type& const_reference;
307  typedef size_t size_type;
311 
312 protected:
313 
316  _Link_type __tmp = this->_M_header.allocate(1);
317  _STLP_TRY {
318  _Copy_Construct(&__tmp->_M_value_field, __x);
319  }
320  _STLP_UNWIND(this->_M_header.deallocate(__tmp,1))
321  _S_left(__tmp) = 0;
322  _S_right(__tmp) = 0;
323  return __tmp;
324  }
325 
327  _Base_ptr __tmp = _M_create_node(_S_value(__x));
328  _S_color(__tmp) = _S_color(__x);
329  return __tmp;
330  }
331 
332  size_type _M_node_count; // keeps track of size of tree
333  _Compare _M_key_compare;
334 
336  { return this->_M_header._M_data._M_parent; }
337  _Base_ptr _M_leftmost() const
338  { return this->_M_header._M_data._M_left; }
339  _Base_ptr _M_rightmost() const
340  { return this->_M_header._M_data._M_right; }
341 
342  _Base_ptr& _M_root()
343  { return this->_M_header._M_data._M_parent; }
344  _Base_ptr& _M_leftmost()
345  { return this->_M_header._M_data._M_left; }
346  _Base_ptr& _M_rightmost()
347  { return this->_M_header._M_data._M_right; }
348 
349  static _Base_ptr& _STLP_CALL _S_left(_Base_ptr __x)
350  { return __x->_M_left; }
352  { return __x->_M_right; }
354  { return __x->_M_parent; }
356  { return __STATIC_CAST(_Link_type, __x)->_M_value_field; }
357  static const _Key& _STLP_CALL _S_key(_Base_ptr __x)
358  { return _KeyOfValue()(_S_value(__x));}
360  { return (_Color_type&)(__x->_M_color); }
361 
363  { return _Rb_tree_node_base::_S_minimum(__x); }
364 
366  { return _Rb_tree_node_base::_S_maximum(__x); }
367 
368 public:
369  typedef typename _Traits::_NonConstTraits _NonConstTraits;
370  typedef typename _Traits::_ConstTraits _ConstTraits;
374 
375 private:
378  void _M_erase(_Base_ptr __x);
379 
380 public:
381  // allocation/deallocation
384  {}
385 
386  _Rb_tree(const _Compare& __comp)
388  {}
389 
390  _Rb_tree(const _Compare& __comp, const allocator_type& __a)
392  {}
393 
394  _Rb_tree(const _Self& __x)
397  if (__x._M_root() != 0) {
399  _M_root() = _M_copy(__x._M_root(), &this->_M_header._M_data);
402  }
403  _M_node_count = __x._M_node_count;
404  }
405 
406 #if !defined (_STLP_NO_MOVE_SEMANTIC)
411  { src.get()._M_node_count = 0; }
412 #endif
413 
414  ~_Rb_tree() { clear(); }
415  _Self& operator=(const _Self& __x);
416 
417 public:
418  // accessors:
419  _Compare key_comp() const { return _M_key_compare; }
420 
423  iterator end() { return iterator(&this->_M_header._M_data); }
424  const_iterator end() const { return const_iterator(__CONST_CAST(_Base_ptr, &this->_M_header._M_data)); }
425 
427  const_reverse_iterator rbegin() const
428  { return const_reverse_iterator(end()); }
430  const_reverse_iterator rend() const
431  { return const_reverse_iterator(begin()); }
432  bool empty() const { return _M_node_count == 0; }
433  size_type size() const { return _M_node_count; }
434  size_type max_size() const { return size_type(-1); }
435 
436  void swap(_Self& __t) {
437  if (__t.empty()) {
438  if (this->empty()) return;
439  __t._M_header.swap(this->_M_header);
440  __t._M_rebind(&this->_M_header._M_data);
441  this->_M_empty_initialize();
442  }
443  else if (this->empty()) {
444  __t.swap(*this);
445  return;
446  }
447  else {
448  this->_M_header.swap(__t._M_header);
449  this->_M_rebind(&__t._M_header._M_data);
450  __t._M_rebind(&this->_M_header._M_data);
451  }
452  _STLP_STD::swap(_M_node_count, __t._M_node_count);
453  _STLP_STD::swap(_M_key_compare, __t._M_key_compare);
454  }
455 
456 public:
457  // insert/erase
459  iterator insert_equal(const value_type& __x);
460 
461  iterator insert_unique(iterator __pos, const value_type& __x);
462  iterator insert_equal(iterator __pos, const value_type& __x);
463 
464 #if defined (_STLP_MEMBER_TEMPLATES)
465  template<class _II> void insert_equal(_II __first, _II __last) {
466  for ( ; __first != __last; ++__first)
467  insert_equal(*__first);
468  }
469  template<class _II> void insert_unique(_II __first, _II __last) {
470  for ( ; __first != __last; ++__first)
471  insert_unique(*__first);
472  }
473 #else
475  for ( ; __first != __last; ++__first)
476  insert_unique(*__first);
477  }
478  void insert_unique(const value_type* __first, const value_type* __last) {
479  for ( ; __first != __last; ++__first)
480  insert_unique(*__first);
481  }
483  for ( ; __first != __last; ++__first)
484  insert_equal(*__first);
485  }
486  void insert_equal(const value_type* __first, const value_type* __last) {
487  for ( ; __first != __last; ++__first)
488  insert_equal(*__first);
489  }
490 #endif
491 
492  void erase(iterator __pos) {
494  this->_M_header._M_data._M_parent,
495  this->_M_header._M_data._M_left,
496  this->_M_header._M_data._M_right);
498  this->_M_header.deallocate(__STATIC_CAST(_Link_type, __x), 1);
499  --_M_node_count;
500  }
501 
502  size_type erase(const key_type& __x) {
505  erase(__p.first, __p.second);
506  return __n;
507  }
508 
510  iterator __i = find(__x);
511  if (__i._M_node != &this->_M_header._M_data) {
512  erase(__i);
513  return 1;
514  }
515  return 0;
516  }
517 
518  void erase(iterator __first, iterator __last) {
519  if (__first._M_node == this->_M_header._M_data._M_left && // begin()
520  __last._M_node == &this->_M_header._M_data) // end()
521  clear();
522  else
523  while (__first != __last) erase(__first++);
524  }
525 
526  void erase(const key_type* __first, const key_type* __last) {
527  while (__first != __last) erase(*__first++);
528  }
529 
530  void clear() {
531  if (_M_node_count != 0) {
532  _M_erase(_M_root());
533  _M_leftmost() = &this->_M_header._M_data;
534  _M_root() = 0;
535  _M_rightmost() = &this->_M_header._M_data;
536  _M_node_count = 0;
537  }
538  }
539 
540 public:
541  // set operations:
543  iterator find(const _KT& __k) { return iterator(_M_find(__k)); }
545  const_iterator find(const _KT& __k) const { return const_iterator(_M_find(__k)); }
546 private:
548  _Base_ptr _M_find(const _KT& __k) const {
549  _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); // Last node which is not less than __k.
550  _Base_ptr __x = _M_root(); // Current node.
551 
552  while (__x != 0)
553  if (!_M_key_compare(_S_key(__x), __k))
554  __y = __x, __x = _S_left(__x);
555  else
556  __x = _S_right(__x);
557 
558  if (__y != &this->_M_header._M_data) {
559  if (_M_key_compare(__k, _S_key(__y))) {
560  __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data);
561  }
562  }
563  return __y;
564  }
565 
567  _Base_ptr _M_lower_bound(const _KT& __k) const {
568  _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); /* Last node which is not less than __k. */
569  _Base_ptr __x = _M_root(); /* Current node. */
570 
571  while (__x != 0)
572  if (!_M_key_compare(_S_key(__x), __k))
573  __y = __x, __x = _S_left(__x);
574  else
575  __x = _S_right(__x);
576 
577  return __y;
578  }
579 
581  _Base_ptr _M_upper_bound(const _KT& __k) const {
582  _Base_ptr __y = __CONST_CAST(_Base_ptr, &this->_M_header._M_data); /* Last node which is greater than __k. */
583  _Base_ptr __x = _M_root(); /* Current node. */
584 
585  while (__x != 0)
586  if (_M_key_compare(__k, _S_key(__x)))
587  __y = __x, __x = _S_left(__x);
588  else
589  __x = _S_right(__x);
590 
591  return __y;
592  }
593 
594 public:
596  size_type count(const _KT& __x) const {
598  return _STLP_STD::distance(__p.first, __p.second);
599  }
601  iterator lower_bound(const _KT& __x) { return iterator(_M_lower_bound(__x)); }
603  const_iterator lower_bound(const _KT& __x) const { return const_iterator(_M_lower_bound(__x)); }
605  iterator upper_bound(const _KT& __x) { return iterator(_M_upper_bound(__x)); }
607  const_iterator upper_bound(const _KT& __x) const { return const_iterator(_M_upper_bound(__x)); }
610  { return pair<iterator, iterator>(lower_bound(__x), upper_bound(__x)); }
617  __p.second = lower_bound(__x);
618  if (__p.second._M_node != &this->_M_header._M_data &&
619  !_M_key_compare(__x, _S_key(__p.second._M_node))) {
620  __p.first = __p.second++;
621  }
622  else {
623  __p.first = __p.second;
624  }
625  return __p;
626  }
630  __p.second = lower_bound(__x);
631  if (__p.second._M_node != &this->_M_header._M_data &&
632  !_M_key_compare(__x, _S_key(__p.second._M_node))) {
633  __p.first = __p.second++;
634  }
635  else {
636  __p.first = __p.second;
637  }
638  return __p;
639  }
640 
641 #if defined (_STLP_DEBUG)
642 public:
643  // Debugging.
644  bool __rb_verify() const;
645 #endif //_STLP_DEBUG
646 };
647 
648 #if defined (_STLP_DEBUG)
649 # undef _Rb_tree
650 #endif
651 
653 
655 
656 #if !defined (_STLP_LINK_TIME_INSTANTIATION)
657 # include <stl/_tree.c>
658 #endif
659 
660 #if defined (_STLP_DEBUG)
661 # include <stl/debug/_tree.h>
662 #endif
663 
665 
666 #define _STLP_TEMPLATE_HEADER template <class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, class _Alloc>
667 #define _STLP_TEMPLATE_CONTAINER _STLP_PRIV _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc>
668 #include <stl/_relops_cont.h>
669 #undef _STLP_TEMPLATE_CONTAINER
670 #undef _STLP_TEMPLATE_HEADER
671 
672 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && !defined (_STLP_NO_MOVE_SEMANTIC)
673 template <class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, class _Alloc>
674 struct __move_traits<_STLP_PRIV _Rb_tree<_Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc> >
675  : _STLP_PRIV __move_traits_help2<_Compare, _Alloc> {};
676 #endif
677 
679 
680 #endif /* _STLP_INTERNAL_TREE_H */
681 
682 // Local Variables:
683 // mode:C++
684 // End:
#define _STLP_CONVERT_ALLOCATOR(__a, _Tp)
Definition: _alloc.h:183
_Rb_tree(__move_source< _Self > src)
Definition: _tree.h:407
#define bidirectional_iterator_tag
Definition: _abbrevs.h:27
size_type size() const
Definition: _tree.h:433
_AllocProxy _M_header
Definition: _tree.h:282
void _M_rebind(_Node_base *__static_node)
Definition: _tree.h:270
const_reverse_iterator rbegin() const
Definition: _tree.h:427
_Rb_tree_iterator(const iterator &__it)
Definition: _tree.h:168
_Rb_tree(const _Compare &__comp)
Definition: _tree.h:386
_STLP_TEMPLATE_FOR_CONT_EXT _Base_ptr _M_lower_bound(const _KT &__k) const
Definition: _tree.h:567
#define swap(a, b)
Definition: qsort.c:63
_Rb_tree_iterator< _Value, _NonConstTraits > iterator
Definition: _tree.h:155
_Rb_tree(const _Compare &__comp, const allocator_type &__a)
Definition: _tree.h:390
_Base_ptr & _M_root()
Definition: _tree.h:342
return __n
Definition: _algo.h:75
_Base_ptr _M_copy(_Base_ptr __x, _Base_ptr __p)
Definition: _tree.c:624
_Rb_tree_node_base * _Base_ptr
Definition: _tree.h:296
size_type erase(const key_type &__x)
Definition: _tree.h:502
_Rb_tree_base< _Value, _Alloc > _Base
Definition: _tree.h:293
#define _STLP_DFL_TMPL_PARAM(classname, defval)
Definition: features.h:338
char typename[32]
Definition: main.c:84
static _Base_ptr _STLP_CALL _S_maximum(_Base_ptr __x)
Definition: _tree.h:98
GLsizei const GLvoid * pointer
Definition: glext.h:5848
__bool2type< pod >::_Ret is_POD_type
iterator insert_equal(const value_type &__x)
Definition: _tree.c:387
static const _Key &_STLP_CALL _S_key(_Base_ptr __x)
Definition: _tree.h:357
allocator_type get_allocator() const
Definition: _tree.h:244
#define _Alloc
Definition: _bvector.h:330
_Base_ptr & _M_leftmost()
Definition: _tree.h:344
#define __STATIC_CAST(__x, __y)
Definition: features.h:585
_Traits::_ConstTraits _ConstTraits
Definition: _tree.h:156
_STLP_TEMPLATE_FOR_CONT_EXT iterator upper_bound(const _KT &__x)
Definition: _tree.h:605
#define reverse_iterator
Definition: _abbrevs.h:34
_Base::allocator_type allocator_type
Definition: _tree.h:310
#define _STLP_TEMPLATE_FOR_CONT_EXT
Definition: features.h:623
_Base_ptr _M_rightmost() const
Definition: _tree.h:339
iterator end()
Definition: _tree.h:423
_Traits::pointer pointer
Definition: _tree.h:149
const_reverse_iterator rend() const
Definition: _tree.h:430
static _Color_type &_STLP_CALL _S_color(_Base_ptr __x)
Definition: _tree.h:359
ptrdiff_t difference_type
Definition: _tree.h:139
static _Base_ptr &_STLP_CALL _S_right(_Base_ptr __x)
Definition: _tree.h:351
_Rb_global< bool > _Rb_global_inst
Definition: _tree.h:134
iterator _M_insert(_Base_ptr __parent, const value_type &__val, _Base_ptr __on_left=0, _Base_ptr __on_right=0)
Definition: _tree.c:350
~_Rb_tree()
Definition: _tree.h:414
_Color_type _M_color
Definition: _tree.h:88
_STLP_TEMPLATE_FOR_CONT_EXT iterator lower_bound(const _KT &__x)
Definition: _tree.h:601
_STLP_TEMPLATE_FOR_CONT_EXT _Base_ptr _M_find(const _KT &__k) const
Definition: _tree.h:548
const_iterator begin() const
Definition: _tree.h:422
_STLP_TEMPLATE_FOR_CONT_EXT pair< const_iterator, const_iterator > equal_range_unique(const _KT &__x) const
Definition: _tree.h:628
_Value _M_value_field
Definition: _tree.h:106
_Base_ptr _M_right
Definition: _tree.h:91
_Rb_tree_base_iterator(_Base_ptr __x)
Definition: _tree.h:142
GLsizei GLsizei GLfloat distance
Definition: glext.h:11755
#define _STLP_MOVE_TO_PRIV_NAMESPACE
Definition: features.h:524
_Value _M_data
Definition: _alloc.h:478
_Base_ptr _M_left
Definition: _tree.h:90
_Rb_tree_base(const allocator_type &__a)
Definition: _tree.h:249
_Tp * allocate(size_type __n, size_type &__allocated_n)
Definition: _alloc.h:525
_Rb_tree_node< _Value > _Node
Definition: _tree.h:297
static _Base_ptr &_STLP_CALL _S_left(_Base_ptr __x)
Definition: _tree.h:349
_Self operator++(int)
Definition: _tree.h:180
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator upper_bound(const _KT &__x) const
Definition: _tree.h:607
_Node * _Link_type
Definition: _tree.h:298
_Base_ptr _M_node
Definition: _tree.h:140
_Alloc_traits< _Node, _Alloc >::allocator_type _M_node_allocator_type
Definition: _tree.h:240
_Rb_tree_node_base _Node_base
Definition: _tree.h:234
static _Base_ptr _STLP_CALL _M_increment(_Base_ptr)
#define _STLP_UNWIND(action)
Definition: features.h:824
void insert_unique(const_iterator __first, const_iterator __last)
Definition: _tree.h:474
_Rb_tree_node_base * _Base_ptr
Definition: _tree.h:137
static void _STLP_CALL _Rotate_left(_Base_ptr __x, _Base_ptr &__root)
_Rb_tree_node_base * _Base_ptr
Definition: _tree.h:151
bidirectional_iterator_tag _Iterator_category
Definition: _tree.h:309
_STLP_TEMPLATE_FOR_CONT_EXT size_type count(const _KT &__x) const
Definition: _tree.h:596
_STLP_TEMPLATE_FOR_CONT_EXT pair< iterator, iterator > equal_range_unique(const _KT &__x)
Definition: _tree.h:615
iterator begin()
Definition: _tree.h:421
void insert_equal(const_iterator __first, const_iterator __last)
Definition: _tree.h:482
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
_Base_ptr & _M_rightmost()
Definition: _tree.h:346
_Rb_tree_node< _Value > * _Link_type
Definition: _tree.h:152
_T1 first
Definition: _pair.h:51
static _Base_ptr _STLP_CALL _Rebalance_for_erase(_Base_ptr __z, _Base_ptr &__root, _Base_ptr &__leftmost, _Base_ptr &__rightmost)
_Base_ptr _M_parent
Definition: _tree.h:89
_Rb_tree_node< _Tp > _Node
Definition: _tree.h:235
_Value value_type
Definition: _tree.h:147
#define _STLP_MOVE_TO_STD_NAMESPACE
Definition: features.h:525
void get(int argc, const char *argv[])
Definition: cmds.c:480
void _Copy_Construct(_Tp *__p, const _Tp &__val)
Definition: _construct.h:130
bidirectional_iterator_tag iterator_category
Definition: _tree.h:138
size_type _M_node_count
Definition: _tree.h:332
allocator_type get_allocator() const
Definition: _tree.h:153
_STLP_TEMPLATE_FOR_CONT_EXT pair< iterator, iterator > equal_range(const _KT &__x)
Definition: _tree.h:609
void insert_equal(const value_type *__first, const value_type *__last)
Definition: _tree.h:486
const value_type & const_reference
Definition: _tree.h:306
_Self & operator=(const _Self &__x)
Definition: _tree.c:321
void insert_unique(const value_type *__first, const value_type *__last)
Definition: _tree.h:478
reverse_iterator rend()
Definition: _tree.h:429
_Compare key_comp() const
Definition: _tree.h:419
_STLP_INLINE_LOOP _InputIter const _Tp & __val
Definition: _algobase.h:656
_Key key_type
Definition: _tree.h:301
static _Base_ptr _STLP_CALL _S_maximum(_Base_ptr __x)
Definition: _tree.h:365
_Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc > _Self
Definition: _tree.h:294
static _Base_ptr _STLP_CALL _S_minimum(_Base_ptr __x)
Definition: _tree.h:93
#define _STLP_EXPORT_TEMPLATE_CLASS
Definition: features.h:987
reference operator *() const
Definition: _tree.h:170
_Rb_tree_iterator(_Base_ptr __x)
Definition: _tree.h:166
bool operator==(const_iterator __rhs) const
Definition: _tree.h:196
__bool2type< trivial_constructor >::_Ret has_trivial_default_constructor
reverse_iterator rbegin()
Definition: _tree.h:426
_Rb_tree_iterator< _Value, _ConstTraits > const_iterator
Definition: _tree.h:157
_STLP_MOVE_TO_PRIV_NAMESPACE const _InputIterator const input_iterator_tag &_InputIterator __it(__first)
void swap(_Self &__t)
Definition: _tree.h:436
_Traits::reference reference
Definition: _tree.h:305
_Value value_type
Definition: _tree.h:302
GLint reference
Definition: glext.h:11729
#define _STLP_PRIV
Definition: _dm.h:70
void _Destroy(_Tp *__pointer)
Definition: _construct.h:63
const value_type * const_pointer
Definition: _tree.h:304
_Rb_tree(const _Self &__x)
Definition: _tree.h:394
static void _STLP_CALL _Rotate_right(_Base_ptr __x, _Base_ptr &__root)
_STLP_TYPENAME_ON_RETURN_TYPE _MoveSourceTraits< _Tp >::_Type _AsMoveSource(_Tp &src)
GLenum src
Definition: glext.h:6340
#define _STLP_KEY_TYPE_FOR_CONT_EXT(type)
Definition: features.h:622
_STLP_DECLARE_BIDIRECTIONAL_REVERSE_ITERATORS
Definition: _tree.h:373
void swap(_Self &__x)
Definition: _alloc.h:520
pair< iterator, bool > insert_unique(const value_type &__x)
Definition: _tree.c:405
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator find(const _KT &__k) const
Definition: _tree.h:545
static _Base_ptr _STLP_CALL _M_decrement(_Base_ptr)
_Traits::_ConstTraits _ConstTraits
Definition: _tree.h:370
ptrdiff_t difference_type
Definition: _tree.h:308
static _Base_ptr &_STLP_CALL _S_parent(_Base_ptr __x)
Definition: _tree.h:353
_Rb_tree_Color_type _Color_type
Definition: _tree.h:299
_Rb_tree_node_base * _Base_ptr
Definition: _tree.h:86
const_iterator end() const
Definition: _tree.h:424
void erase(iterator __pos)
Definition: _tree.h:492
_Base_ptr _M_root() const
Definition: _tree.h:335
#define __CONST_CAST(__x, __y)
Definition: features.h:584
__bool2type< trivial_assign >::_Ret has_trivial_assignment_operator
_Rb_tree_node_base * _Base_ptr
Definition: _tree.h:115
size_type erase_unique(const key_type &__x)
Definition: _tree.h:509
#define _STLP_END_NAMESPACE
Definition: features.h:503
#define _STLP_TRY
Definition: features.h:817
__bool2type< trivial_copy >::_Ret has_trivial_copy_constructor
Definition: _pair.h:47
_STLP_TEMPLATE_FOR_CONT_EXT _Base_ptr _M_upper_bound(const _KT &__k) const
Definition: _tree.h:581
_STLP_BEGIN_NAMESPACE _STLP_MOVE_TO_PRIV_NAMESPACE typedef bool _Rb_tree_Color_type
Definition: _tree.h:77
__kernel_ptrdiff_t ptrdiff_t
Definition: linux.h:247
void erase(iterator __first, iterator __last)
Definition: _tree.h:518
static value_type &_STLP_CALL _S_value(_Base_ptr __x)
Definition: _tree.h:355
_Rb_tree_base(__move_source< _Self > src)
Definition: _tree.h:255
_T2 second
Definition: _pair.h:52
_Base_ptr _M_leftmost() const
Definition: _tree.h:337
_Base_ptr _M_clone_node(_Base_ptr __x)
Definition: _tree.h:326
void _M_erase(_Base_ptr __x)
Definition: _tree.c:655
#define _STLP_DEFINE_ARROW_OPERATOR
_Rb_tree()
Definition: _tree.h:382
_Traits::_NonConstTraits _NonConstTraits
Definition: _tree.h:154
bool operator !=(const_iterator __rhs) const
Definition: _tree.h:199
size_type max_size() const
Definition: _tree.h:434
static void _STLP_CALL _Rebalance(_Base_ptr __x, _Base_ptr &__root)
#define const
Definition: zconf.h:230
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator lower_bound(const _KT &__x) const
Definition: _tree.h:603
_Rb_tree_Color_type _Color_type
Definition: _tree.h:85
#define _STLP_BEGIN_NAMESPACE
Definition: features.h:501
_Rb_tree_iterator< _Value, _Traits > _Self
Definition: _tree.h:150
_STLP_DEFINE_ARROW_OPERATOR _Self & operator++()
Definition: _tree.h:176
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:612
static _Base_ptr _STLP_CALL _S_minimum(_Base_ptr __x)
Definition: _tree.h:362
_Self & operator--()
Definition: _tree.h:186
_Traits::pointer pointer
Definition: _tree.h:303
_Rb_tree_iterator< value_type, _ConstTraits > const_iterator
Definition: _tree.h:372
_Base_ptr _M_create_node(const value_type &__x)
Definition: _tree.h:315
_STLP_TEMPLATE_FOR_CONT_EXT iterator find(const _KT &__k)
Definition: _tree.h:543
void clear()
Definition: _tree.h:530
_Rb_tree_iterator< value_type, _NonConstTraits > iterator
Definition: _tree.h:371
_Self operator--(int)
Definition: _tree.h:190
void _M_empty_initialize()
Definition: _tree.h:262
#define _STLP_CALL
Definition: _bc.h:131
void erase(const key_type *__first, const key_type *__last)
Definition: _tree.h:526
_Traits::reference reference
Definition: _tree.h:148
__bool2type< trivial_destructor >::_Ret has_trivial_destructor
bool empty() const
Definition: _tree.h:432
_Traits::_NonConstTraits _NonConstTraits
Definition: _tree.h:369
#define __TRIVIAL_STUFF(__type)
Definition: features.h:799
#define _S_rb_tree_red
Definition: _tree.h:81
size_t size_type
Definition: _tree.h:307
_Compare _M_key_compare
Definition: _tree.h:333
#define _STLP_FORCE_ALLOCATORS(a, y)
Definition: _alloc.h:436