ReactOS 0.4.15-dev-7834-g00c4b3d
_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
35Red-black tree class, designed for use in implementing STL
36associative containers (set, multiset, map, and multimap). The
37insertion and deletion algorithms are based on those in Cormen,
38Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),
39except that
40
41(1) the header cell is maintained with links not only to the root
42but also to the leftmost node of the tree, to enable constant time
43begin(), and to the rightmost node of the tree, to enable linear time
44performance when used with the generic set algorithms (set_union,
45etc.);
46
47(2) when a node being deleted has two children its successor node is
48relinked into its place, rather than copied, so that the only
49iterators 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
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
104template <class _Value>
108};
109
111
112template <class _Dummy>
114public:
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
141 _Rb_tree_base_iterator() : _M_node(0) {}
142 _Rb_tree_base_iterator(_Base_ptr __x) : _M_node(__x) {}
143};
144
145template <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)
206template <class _Value, class _Traits>
213};
215#endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
216
217#if defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES)
219template <class _Value, class _Traits>
221{ return (_Value*)0; }
222inline bidirectional_iterator_tag iterator_category(const _STLP_PRIV _Rb_tree_base_iterator&)
223{ return bidirectional_iterator_tag(); }
224inline 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
231template <class _Tp, class _Alloc>
233public:
238private:
242
243public:
244 allocator_type get_allocator() const {
246 }
247
248protected:
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
289template <class _Key, class _Compare,
290 class _Value, class _KeyOfValue, class _Traits,
292class _Rb_tree : public _Rb_tree_base<_Value, _Alloc> {
295protected:
300public:
301 typedef _Key key_type;
303 typedef typename _Traits::pointer pointer;
304 typedef const value_type* const_pointer;
305 typedef typename _Traits::reference reference;
307 typedef size_t size_type;
311
312protected:
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
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
368public:
369 typedef typename _Traits::_NonConstTraits _NonConstTraits;
370 typedef typename _Traits::_ConstTraits _ConstTraits;
374
375private:
378 void _M_erase(_Base_ptr __x);
379
380public:
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 }
404 }
405
406#if !defined (_STLP_NO_MOVE_SEMANTIC)
411 { src.get()._M_node_count = 0; }
412#endif
413
415 _Self& operator=(const _Self& __x);
416
417public:
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
456public:
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);
497 _STLP_STD::_Destroy(&_S_value(__x));
498 this->_M_header.deallocate(__STATIC_CAST(_Link_type, __x), 1);
500 }
501
504 size_type __n = _STLP_STD::distance(__p.first, __p.second);
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
540public:
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)); }
546private:
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))) {
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
594public:
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)
642public:
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)
673template <class _Key, class _Compare, class _Value, class _KeyOfValue, class _Traits, class _Alloc>
674struct __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 reverse_iterator
Definition: _abbrevs.h:34
#define bidirectional_iterator_tag
Definition: _abbrevs.h:27
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
return __n
Definition: _algo.h:75
_STLP_INLINE_LOOP _InputIter const _Tp & __val
Definition: _algobase.h:656
#define _STLP_CONVERT_ALLOCATOR(__a, _Tp)
Definition: _alloc.h:183
#define _STLP_FORCE_ALLOCATORS(a, y)
Definition: _alloc.h:436
#define _STLP_CALL
Definition: _bc.h:131
#define _Alloc
Definition: _bvector.h:330
void _Copy_Construct(_Tp *__p, const _Tp &__val)
Definition: _construct.h:130
#define _STLP_PRIV
Definition: _dm.h:70
_STLP_MOVE_TO_PRIV_NAMESPACE const _InputIterator const input_iterator_tag &_InputIterator __it(__first)
_STLP_TYPENAME_ON_RETURN_TYPE _MoveSourceTraits< _Tp >::_Type _AsMoveSource(_Tp &src)
#define _STLP_DEFINE_ARROW_OPERATOR
_STLP_BEGIN_NAMESPACE _STLP_MOVE_TO_PRIV_NAMESPACE typedef bool _Rb_tree_Color_type
Definition: _tree.h:77
_Rb_global< bool > _Rb_global_inst
Definition: _tree.h:134
#define _S_rb_tree_red
Definition: _tree.h:81
void get(int argc, const char *argv[])
Definition: cmds.c:480
_Rb_tree_node_base * _Base_ptr
Definition: _tree.h:115
static _Base_ptr _STLP_CALL _Rebalance_for_erase(_Base_ptr __z, _Base_ptr &__root, _Base_ptr &__leftmost, _Base_ptr &__rightmost)
static void _STLP_CALL _Rotate_left(_Base_ptr __x, _Base_ptr &__root)
static _Base_ptr _STLP_CALL _M_decrement(_Base_ptr)
static void _STLP_CALL _Rebalance(_Base_ptr __x, _Base_ptr &__root)
static _Base_ptr _STLP_CALL _M_increment(_Base_ptr)
static void _STLP_CALL _Rotate_right(_Base_ptr __x, _Base_ptr &__root)
_Rb_tree_base(const allocator_type &__a)
Definition: _tree.h:249
_Alloc_traits< _Node, _Alloc >::allocator_type _M_node_allocator_type
Definition: _tree.h:240
void _M_rebind(_Node_base *__static_node)
Definition: _tree.h:270
void _M_empty_initialize()
Definition: _tree.h:262
_Rb_tree_node_base _Node_base
Definition: _tree.h:234
_Alloc allocator_type
Definition: _tree.h:237
_Rb_tree_node< _Tp > _Node
Definition: _tree.h:235
_Rb_tree_base(__move_source< _Self > src)
Definition: _tree.h:255
_AllocProxy _M_header
Definition: _tree.h:282
_Key key_type
Definition: _tree.h:301
ptrdiff_t difference_type
Definition: _tree.h:308
_Rb_tree< _Key, _Compare, _Value, _KeyOfValue, _Traits, _Alloc > _Self
Definition: _tree.h:294
_Rb_tree_Color_type _Color_type
Definition: _tree.h:299
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator lower_bound(const _KT &__x) const
Definition: _tree.h:603
_STLP_TEMPLATE_FOR_CONT_EXT iterator lower_bound(const _KT &__x)
Definition: _tree.h:601
_Rb_tree(const _Compare &__comp)
Definition: _tree.h:386
_Rb_tree(__move_source< _Self > src)
Definition: _tree.h:407
_Traits::_NonConstTraits _NonConstTraits
Definition: _tree.h:369
reverse_iterator rend()
Definition: _tree.h:429
_Base_ptr _M_leftmost() const
Definition: _tree.h:337
_STLP_TEMPLATE_FOR_CONT_EXT pair< const_iterator, const_iterator > equal_range(const _KT &__x) const
Definition: _tree.h:612
_Base_ptr _M_rightmost() const
Definition: _tree.h:339
const_reverse_iterator rbegin() const
Definition: _tree.h:427
_Compare key_comp() const
Definition: _tree.h:419
allocator_type get_allocator() const
Definition: _tree.h:153
_Rb_tree()
Definition: _tree.h:382
void clear()
Definition: _tree.h:530
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator upper_bound(const _KT &__x) const
Definition: _tree.h:607
_STLP_TEMPLATE_FOR_CONT_EXT pair< iterator, iterator > equal_range(const _KT &__x)
Definition: _tree.h:609
const_iterator begin() const
Definition: _tree.h:422
size_t size_type
Definition: _tree.h:307
size_type _M_node_count
Definition: _tree.h:332
_Value value_type
Definition: _tree.h:302
_Base_ptr _M_clone_node(_Base_ptr __x)
Definition: _tree.h:326
_Base_ptr _M_create_node(const value_type &__x)
Definition: _tree.h:315
_Base_ptr & _M_leftmost()
Definition: _tree.h:344
_STLP_TEMPLATE_FOR_CONT_EXT iterator find(const _KT &__k)
Definition: _tree.h:543
size_type size() const
Definition: _tree.h:433
const_reverse_iterator rend() const
Definition: _tree.h:430
void erase(const key_type *__first, const key_type *__last)
Definition: _tree.h:526
~_Rb_tree()
Definition: _tree.h:414
iterator begin()
Definition: _tree.h:421
void erase(iterator __first, iterator __last)
Definition: _tree.h:518
void insert_equal(const_iterator __first, const_iterator __last)
Definition: _tree.h:482
_STLP_TEMPLATE_FOR_CONT_EXT size_type count(const _KT &__x) const
Definition: _tree.h:596
void swap(_Self &__t)
Definition: _tree.h:436
_STLP_TEMPLATE_FOR_CONT_EXT _Base_ptr _M_lower_bound(const _KT &__k) const
Definition: _tree.h:567
static _Base_ptr _STLP_CALL _S_minimum(_Base_ptr __x)
Definition: _tree.h:362
_STLP_TEMPLATE_FOR_CONT_EXT _Base_ptr _M_find(const _KT &__k) const
Definition: _tree.h:548
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator find(const _KT &__k) const
Definition: _tree.h:545
_STLP_TEMPLATE_FOR_CONT_EXT pair< iterator, iterator > equal_range_unique(const _KT &__x)
Definition: _tree.h:615
reverse_iterator rbegin()
Definition: _tree.h:426
_Compare _M_key_compare
Definition: _tree.h:333
iterator insert_equal(const value_type &__x)
Definition: _tree.c:387
_STLP_TEMPLATE_FOR_CONT_EXT iterator upper_bound(const _KT &__x)
Definition: _tree.h:605
iterator _M_insert(_Base_ptr __parent, const value_type &__val, _Base_ptr __on_left=0, _Base_ptr __on_right=0)
Definition: _tree.c:350
_Traits::reference reference
Definition: _tree.h:305
_Rb_tree_iterator< value_type, _ConstTraits > const_iterator
Definition: _tree.h:372
_Traits::_ConstTraits _ConstTraits
Definition: _tree.h:370
static value_type &_STLP_CALL _S_value(_Base_ptr __x)
Definition: _tree.h:355
_STLP_TEMPLATE_FOR_CONT_EXT pair< const_iterator, const_iterator > equal_range_unique(const _KT &__x) const
Definition: _tree.h:628
_Base_ptr & _M_root()
Definition: _tree.h:342
_Base::allocator_type allocator_type
Definition: _tree.h:310
_Rb_tree_node_base * _Base_ptr
Definition: _tree.h:296
_STLP_DECLARE_BIDIRECTIONAL_REVERSE_ITERATORS
Definition: _tree.h:373
iterator end()
Definition: _tree.h:423
bidirectional_iterator_tag _Iterator_category
Definition: _tree.h:309
_Traits::pointer pointer
Definition: _tree.h:303
pair< iterator, bool > insert_unique(const value_type &__x)
Definition: _tree.c:405
_Base_ptr & _M_rightmost()
Definition: _tree.h:346
void insert_unique(const_iterator __first, const_iterator __last)
Definition: _tree.h:474
const value_type * const_pointer
Definition: _tree.h:304
size_type erase_unique(const key_type &__x)
Definition: _tree.h:509
static _Base_ptr &_STLP_CALL _S_right(_Base_ptr __x)
Definition: _tree.h:351
static _Base_ptr &_STLP_CALL _S_parent(_Base_ptr __x)
Definition: _tree.h:353
void _M_erase(_Base_ptr __x)
Definition: _tree.c:655
size_type erase(const key_type &__x)
Definition: _tree.h:502
_Rb_tree(const _Self &__x)
Definition: _tree.h:394
void insert_equal(const value_type *__first, const value_type *__last)
Definition: _tree.h:486
static _Color_type &_STLP_CALL _S_color(_Base_ptr __x)
Definition: _tree.h:359
_Self & operator=(const _Self &__x)
Definition: _tree.c:321
_Rb_tree(const _Compare &__comp, const allocator_type &__a)
Definition: _tree.h:390
_Base_ptr _M_root() const
Definition: _tree.h:335
const value_type & const_reference
Definition: _tree.h:306
static _Base_ptr &_STLP_CALL _S_left(_Base_ptr __x)
Definition: _tree.h:349
void insert_unique(const value_type *__first, const value_type *__last)
Definition: _tree.h:478
_STLP_TEMPLATE_FOR_CONT_EXT _Base_ptr _M_upper_bound(const _KT &__k) const
Definition: _tree.h:581
_Node * _Link_type
Definition: _tree.h:298
static _Base_ptr _STLP_CALL _S_maximum(_Base_ptr __x)
Definition: _tree.h:365
static const _Key &_STLP_CALL _S_key(_Base_ptr __x)
Definition: _tree.h:357
size_type max_size() const
Definition: _tree.h:434
const_iterator end() const
Definition: _tree.h:424
_Rb_tree_base< _Value, _Alloc > _Base
Definition: _tree.h:293
_Base_ptr _M_copy(_Base_ptr __x, _Base_ptr __p)
Definition: _tree.c:624
bool empty() const
Definition: _tree.h:432
void erase(iterator __pos)
Definition: _tree.h:492
_Rb_tree_iterator< value_type, _NonConstTraits > iterator
Definition: _tree.h:371
_Rb_tree_node< _Value > _Node
Definition: _tree.h:297
void swap(_Self &__x)
Definition: _alloc.h:520
_Value _M_data
Definition: _alloc.h:478
_Tp * allocate(size_type __n, size_type &__allocated_n)
Definition: _alloc.h:525
int _Value
Definition: setjmp.h:214
static TAGID TAGID find
Definition: db.cpp:155
__kernel_ptrdiff_t ptrdiff_t
Definition: linux.h:247
#define _STLP_UNWIND(action)
Definition: features.h:824
#define _STLP_TEMPLATE_FOR_CONT_EXT
Definition: features.h:623
#define __TRIVIAL_STUFF(__type)
Definition: features.h:799
#define _STLP_MOVE_TO_STD_NAMESPACE
Definition: features.h:525
#define _STLP_DFL_TMPL_PARAM(classname, defval)
Definition: features.h:338
#define __STATIC_CAST(__x, __y)
Definition: features.h:585
#define _STLP_TRY
Definition: features.h:817
#define __CONST_CAST(__x, __y)
Definition: features.h:584
#define _STLP_KEY_TYPE_FOR_CONT_EXT(type)
Definition: features.h:622
#define _STLP_EXPORT_TEMPLATE_CLASS
Definition: features.h:987
#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
GLenum src
Definition: glext.h:6340
_Rb_tree_node_base * _Base_ptr
Definition: _tree.h:137
_Base_ptr _M_node
Definition: _tree.h:140
ptrdiff_t difference_type
Definition: _tree.h:139
bidirectional_iterator_tag iterator_category
Definition: _tree.h:138
_Rb_tree_base_iterator(_Base_ptr __x)
Definition: _tree.h:142
bool operator!=(const_iterator __rhs) const
Definition: _tree.h:199
_Traits::pointer pointer
Definition: _tree.h:149
reference operator*() const
Definition: _tree.h:170
_Rb_tree_node< _Value > * _Link_type
Definition: _tree.h:152
_Self operator--(int)
Definition: _tree.h:190
_Traits::_ConstTraits _ConstTraits
Definition: _tree.h:156
_Self operator++(int)
Definition: _tree.h:180
_Rb_tree_iterator< _Value, _Traits > _Self
Definition: _tree.h:150
_Rb_tree_iterator< _Value, _NonConstTraits > iterator
Definition: _tree.h:155
_Rb_tree_iterator(_Base_ptr __x)
Definition: _tree.h:166
_Rb_tree_node_base * _Base_ptr
Definition: _tree.h:151
_Traits::_NonConstTraits _NonConstTraits
Definition: _tree.h:154
bool operator==(const_iterator __rhs) const
Definition: _tree.h:196
_Value value_type
Definition: _tree.h:147
_Traits::reference reference
Definition: _tree.h:148
_Rb_tree_iterator< _Value, _ConstTraits > const_iterator
Definition: _tree.h:157
_Rb_tree_iterator(const iterator &__it)
Definition: _tree.h:168
_STLP_DEFINE_ARROW_OPERATOR _Self & operator++()
Definition: _tree.h:176
_Self & operator--()
Definition: _tree.h:186
_Base_ptr _M_parent
Definition: _tree.h:89
_Rb_tree_Color_type _Color_type
Definition: _tree.h:85
_Rb_tree_node_base * _Base_ptr
Definition: _tree.h:86
_Base_ptr _M_right
Definition: _tree.h:91
static _Base_ptr _STLP_CALL _S_maximum(_Base_ptr __x)
Definition: _tree.h:98
_Base_ptr _M_left
Definition: _tree.h:90
_Color_type _M_color
Definition: _tree.h:88
static _Base_ptr _STLP_CALL _S_minimum(_Base_ptr __x)
Definition: _tree.h:93
_Value _M_value_field
Definition: _tree.h:106
__bool2type< pod >::_Ret is_POD_type
__bool2type< trivial_destructor >::_Ret has_trivial_destructor
__bool2type< trivial_constructor >::_Ret has_trivial_default_constructor
__bool2type< trivial_copy >::_Ret has_trivial_copy_constructor
__bool2type< trivial_assign >::_Ret has_trivial_assignment_operator
Definition: _pair.h:47
_T2 second
Definition: _pair.h:52
_T1 first
Definition: _pair.h:51
#define const
Definition: zconf.h:233