Branch data Line data Source code
1 : : // RB tree implementation -*- C++ -*-
2 : :
3 : : // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007
4 : : // Free Software Foundation, Inc.
5 : : //
6 : : // This file is part of the GNU ISO C++ Library. This library is free
7 : : // software; you can redistribute it and/or modify it under the
8 : : // terms of the GNU General Public License as published by the
9 : : // Free Software Foundation; either version 2, or (at your option)
10 : : // any later version.
11 : :
12 : : // This library is distributed in the hope that it will be useful,
13 : : // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 : : // GNU General Public License for more details.
16 : :
17 : : // You should have received a copy of the GNU General Public License along
18 : : // with this library; see the file COPYING. If not, write to the Free
19 : : // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
20 : : // USA.
21 : :
22 : : // As a special exception, you may use this file as part of a free software
23 : : // library without restriction. Specifically, if other files instantiate
24 : : // templates or use macros or inline functions from this file, or you compile
25 : : // this file and link it with other files to produce an executable, this
26 : : // file does not by itself cause the resulting executable to be covered by
27 : : // the GNU General Public License. This exception does not however
28 : : // invalidate any other reasons why the executable file might be covered by
29 : : // the GNU General Public License.
30 : :
31 : : /*
32 : : *
33 : : * Copyright (c) 1996,1997
34 : : * Silicon Graphics Computer Systems, Inc.
35 : : *
36 : : * Permission to use, copy, modify, distribute and sell this software
37 : : * and its documentation for any purpose is hereby granted without fee,
38 : : * provided that the above copyright notice appear in all copies and
39 : : * that both that copyright notice and this permission notice appear
40 : : * in supporting documentation. Silicon Graphics makes no
41 : : * representations about the suitability of this software for any
42 : : * purpose. It is provided "as is" without express or implied warranty.
43 : : *
44 : : *
45 : : * Copyright (c) 1994
46 : : * Hewlett-Packard Company
47 : : *
48 : : * Permission to use, copy, modify, distribute and sell this software
49 : : * and its documentation for any purpose is hereby granted without fee,
50 : : * provided that the above copyright notice appear in all copies and
51 : : * that both that copyright notice and this permission notice appear
52 : : * in supporting documentation. Hewlett-Packard Company makes no
53 : : * representations about the suitability of this software for any
54 : : * purpose. It is provided "as is" without express or implied warranty.
55 : : *
56 : : *
57 : : */
58 : :
59 : : /** @file stl_tree.h
60 : : * This is an internal header file, included by other library headers.
61 : : * You should not attempt to use it directly.
62 : : */
63 : :
64 : : #ifndef _STL_TREE_H
65 : : #define _STL_TREE_H 1
66 : :
67 : : #include <bits/stl_algobase.h>
68 : : #include <bits/allocator.h>
69 : : #include <bits/stl_function.h>
70 : : #include <bits/cpp_type_traits.h>
71 : :
72 : : _GLIBCXX_BEGIN_NAMESPACE(std)
73 : :
74 : : // Red-black tree class, designed for use in implementing STL
75 : : // associative containers (set, multiset, map, and multimap). The
76 : : // insertion and deletion algorithms are based on those in Cormen,
77 : : // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
78 : : // 1990), except that
79 : : //
80 : : // (1) the header cell is maintained with links not only to the root
81 : : // but also to the leftmost node of the tree, to enable constant
82 : : // time begin(), and to the rightmost node of the tree, to enable
83 : : // linear time performance when used with the generic set algorithms
84 : : // (set_union, etc.)
85 : : //
86 : : // (2) when a node being deleted has two children its successor node
87 : : // is relinked into its place, rather than copied, so that the only
88 : : // iterators invalidated are those referring to the deleted node.
89 : :
90 : : enum _Rb_tree_color { _S_red = false, _S_black = true };
91 : :
92 : : struct _Rb_tree_node_base
93 : : {
94 : : typedef _Rb_tree_node_base* _Base_ptr;
95 : : typedef const _Rb_tree_node_base* _Const_Base_ptr;
96 : :
97 : : _Rb_tree_color _M_color;
98 : : _Base_ptr _M_parent;
99 : : _Base_ptr _M_left;
100 : : _Base_ptr _M_right;
101 : :
102 : : static _Base_ptr
103 : : _S_minimum(_Base_ptr __x)
104 : : {
105 [ # # ]: 0 : while (__x->_M_left != 0) __x = __x->_M_left;
106 : 0 : return __x;
107 : : }
108 : :
109 : : static _Const_Base_ptr
110 : : _S_minimum(_Const_Base_ptr __x)
111 : : {
112 : : while (__x->_M_left != 0) __x = __x->_M_left;
113 : : return __x;
114 : : }
115 : :
116 : : static _Base_ptr
117 : : _S_maximum(_Base_ptr __x)
118 : : {
119 [ # # ]: 0 : while (__x->_M_right != 0) __x = __x->_M_right;
120 : 0 : return __x;
121 : : }
122 : :
123 : : static _Const_Base_ptr
124 : : _S_maximum(_Const_Base_ptr __x)
125 : : {
126 : : while (__x->_M_right != 0) __x = __x->_M_right;
127 : : return __x;
128 : : }
129 : : };
130 : :
131 : : template<typename _Val>
132 : : struct _Rb_tree_node : public _Rb_tree_node_base
133 : : {
134 : : typedef _Rb_tree_node<_Val>* _Link_type;
135 : : _Val _M_value_field;
136 : : };
137 : :
138 : : _Rb_tree_node_base*
139 : : _Rb_tree_increment(_Rb_tree_node_base* __x);
140 : :
141 : : const _Rb_tree_node_base*
142 : : _Rb_tree_increment(const _Rb_tree_node_base* __x);
143 : :
144 : : _Rb_tree_node_base*
145 : : _Rb_tree_decrement(_Rb_tree_node_base* __x);
146 : :
147 : : const _Rb_tree_node_base*
148 : : _Rb_tree_decrement(const _Rb_tree_node_base* __x);
149 : :
150 : : template<typename _Tp>
151 : : struct _Rb_tree_iterator
152 : : {
153 : : typedef _Tp value_type;
154 : : typedef _Tp& reference;
155 : : typedef _Tp* pointer;
156 : :
157 : : typedef bidirectional_iterator_tag iterator_category;
158 : : typedef ptrdiff_t difference_type;
159 : :
160 : : typedef _Rb_tree_iterator<_Tp> _Self;
161 : : typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
162 : : typedef _Rb_tree_node<_Tp>* _Link_type;
163 : :
164 : : _Rb_tree_iterator()
165 : : : _M_node() { }
166 : :
167 : : explicit
168 : : _Rb_tree_iterator(_Link_type __x)
169 : 10052 : : _M_node(__x) { }
170 : :
171 : : reference
172 : : operator*() const
173 : 5623 : { return static_cast<_Link_type>(_M_node)->_M_value_field; }
174 : :
175 : : pointer
176 : : operator->() const
177 : : { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
178 : :
179 : : _Self&
180 : : operator++()
181 : : {
182 : : _M_node = _Rb_tree_increment(_M_node);
183 : : return *this;
184 : : }
185 : :
186 : : _Self
187 : : operator++(int)
188 : : {
189 : : _Self __tmp = *this;
190 : : _M_node = _Rb_tree_increment(_M_node);
191 : : return __tmp;
192 : : }
193 : :
194 : : _Self&
195 : : operator--()
196 : : {
197 : 0 : _M_node = _Rb_tree_decrement(_M_node);
198 : 0 : return *this;
199 : : }
200 : :
201 : : _Self
202 : : operator--(int)
203 : : {
204 : : _Self __tmp = *this;
205 : : _M_node = _Rb_tree_decrement(_M_node);
206 : : return __tmp;
207 : : }
208 : :
209 : : bool
210 : : operator==(const _Self& __x) const
211 : 4435 : { return _M_node == __x._M_node; }
212 : :
213 : : bool
214 : : operator!=(const _Self& __x) const
215 : : { return _M_node != __x._M_node; }
216 : :
217 : : _Base_ptr _M_node;
218 : : };
219 : :
220 : : template<typename _Tp>
221 : : struct _Rb_tree_const_iterator
222 : : {
223 : : typedef _Tp value_type;
224 : : typedef const _Tp& reference;
225 : : typedef const _Tp* pointer;
226 : :
227 : : typedef _Rb_tree_iterator<_Tp> iterator;
228 : :
229 : : typedef bidirectional_iterator_tag iterator_category;
230 : : typedef ptrdiff_t difference_type;
231 : :
232 : : typedef _Rb_tree_const_iterator<_Tp> _Self;
233 : : typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
234 : : typedef const _Rb_tree_node<_Tp>* _Link_type;
235 : :
236 : : _Rb_tree_const_iterator()
237 : : : _M_node() { }
238 : :
239 : : explicit
240 : : _Rb_tree_const_iterator(_Link_type __x)
241 : : : _M_node(__x) { }
242 : :
243 : : _Rb_tree_const_iterator(const iterator& __it)
244 : 1532 : : _M_node(__it._M_node) { }
245 : :
246 : : reference
247 : : operator*() const
248 : : { return static_cast<_Link_type>(_M_node)->_M_value_field; }
249 : :
250 : : pointer
251 : : operator->() const
252 : : { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
253 : :
254 : : _Self&
255 : : operator++()
256 : : {
257 : 0 : _M_node = _Rb_tree_increment(_M_node);
258 : 0 : return *this;
259 : : }
260 : :
261 : : _Self
262 : : operator++(int)
263 : : {
264 : : _Self __tmp = *this;
265 : : _M_node = _Rb_tree_increment(_M_node);
266 : : return __tmp;
267 : : }
268 : :
269 : : _Self&
270 : : operator--()
271 : : {
272 : 624 : _M_node = _Rb_tree_decrement(_M_node);
273 : 624 : return *this;
274 : : }
275 : :
276 : : _Self
277 : : operator--(int)
278 : : {
279 : : _Self __tmp = *this;
280 : : _M_node = _Rb_tree_decrement(_M_node);
281 : : return __tmp;
282 : : }
283 : :
284 : : bool
285 : : operator==(const _Self& __x) const
286 : : { return _M_node == __x._M_node; }
287 : :
288 : : bool
289 : : operator!=(const _Self& __x) const
290 : : { return _M_node != __x._M_node; }
291 : :
292 : : _Base_ptr _M_node;
293 : : };
294 : :
295 : : template<typename _Val>
296 : : inline bool
297 : : operator==(const _Rb_tree_iterator<_Val>& __x,
298 : : const _Rb_tree_const_iterator<_Val>& __y)
299 : : { return __x._M_node == __y._M_node; }
300 : :
301 : : template<typename _Val>
302 : : inline bool
303 : : operator!=(const _Rb_tree_iterator<_Val>& __x,
304 : : const _Rb_tree_const_iterator<_Val>& __y)
305 : : { return __x._M_node != __y._M_node; }
306 : :
307 : : void
308 : : _Rb_tree_insert_and_rebalance(const bool __insert_left,
309 : : _Rb_tree_node_base* __x,
310 : : _Rb_tree_node_base* __p,
311 : : _Rb_tree_node_base& __header);
312 : :
313 : : _Rb_tree_node_base*
314 : : _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
315 : : _Rb_tree_node_base& __header);
316 : :
317 : :
318 : : template<typename _Key, typename _Val, typename _KeyOfValue,
319 : : typename _Compare, typename _Alloc = allocator<_Val> >
320 : : class _Rb_tree
321 : : {
322 : : typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
323 : : _Node_allocator;
324 : :
325 : : protected:
326 : : typedef _Rb_tree_node_base* _Base_ptr;
327 : : typedef const _Rb_tree_node_base* _Const_Base_ptr;
328 : :
329 : : public:
330 : : typedef _Key key_type;
331 : : typedef _Val value_type;
332 : : typedef value_type* pointer;
333 : : typedef const value_type* const_pointer;
334 : : typedef value_type& reference;
335 : : typedef const value_type& const_reference;
336 : : typedef _Rb_tree_node<_Val>* _Link_type;
337 : : typedef const _Rb_tree_node<_Val>* _Const_Link_type;
338 : : typedef size_t size_type;
339 : : typedef ptrdiff_t difference_type;
340 : : typedef _Alloc allocator_type;
341 : :
342 : : _Node_allocator&
343 : : _M_get_Node_allocator()
344 : : { return *static_cast<_Node_allocator*>(&this->_M_impl); }
345 : :
346 : : const _Node_allocator&
347 : : _M_get_Node_allocator() const
348 : 3164 : { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
349 : :
350 : : allocator_type
351 : : get_allocator() const
352 : 3064 : { return allocator_type(_M_get_Node_allocator()); }
353 : :
354 : : protected:
355 : : _Link_type
356 : : _M_get_node()
357 : 3064 : { return _M_impl._Node_allocator::allocate(1); }
358 : :
359 : : void
360 : : _M_put_node(_Link_type __p)
361 : 1532 : { _M_impl._Node_allocator::deallocate(__p, 1); }
362 : :
363 : : _Link_type
364 : 112 : _M_create_node(const value_type& __x)
365 : : {
366 : 1532 : _Link_type __tmp = _M_get_node();
367 : : try
368 : 3064 : { get_allocator().construct(&__tmp->_M_value_field, __x); }
369 : 0 : catch(...)
370 : : {
371 : : _M_put_node(__tmp);
372 : 0 : __throw_exception_again;
373 : : }
374 : 969 : return __tmp;
375 : : }
376 : :
377 : : _Link_type
378 : : _M_clone_node(_Const_Link_type __x)
379 : : {
380 : 0 : _Link_type __tmp = _M_create_node(__x->_M_value_field);
381 : 0 : __tmp->_M_color = __x->_M_color;
382 : 0 : __tmp->_M_left = 0;
383 : 0 : __tmp->_M_right = 0;
384 : 0 : return __tmp;
385 : : }
386 : :
387 : : void
388 : : _M_destroy_node(_Link_type __p)
389 : : {
390 : 3064 : get_allocator().destroy(&__p->_M_value_field);
391 : : _M_put_node(__p);
392 : : }
393 : :
394 : : protected:
395 : : template<typename _Key_compare,
396 : : bool _Is_pod_comparator = __is_pod(_Key_compare)>
397 : : struct _Rb_tree_impl : public _Node_allocator
398 : 1130 : {
399 : : _Key_compare _M_key_compare;
400 : : _Rb_tree_node_base _M_header;
401 : : size_type _M_node_count; // Keeps track of size of tree.
402 : :
403 : : _Rb_tree_impl()
404 : : : _Node_allocator(), _M_key_compare(), _M_header(),
405 : 2060 : _M_node_count(0)
406 : : { _M_initialize(); }
407 : :
408 : : _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
409 : : : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
410 : 200 : _M_node_count(0)
411 : : { _M_initialize(); }
412 : :
413 : : private:
414 : : void
415 : : _M_initialize()
416 : : {
417 : 1130 : this->_M_header._M_color = _S_red;
418 : 1130 : this->_M_header._M_parent = 0;
419 : 1130 : this->_M_header._M_left = &this->_M_header;
420 : 50 : this->_M_header._M_right = &this->_M_header;
421 : : }
422 : : };
423 : :
424 : : _Rb_tree_impl<_Compare> _M_impl;
425 : :
426 : : protected:
427 : : _Base_ptr&
428 : : _M_root()
429 : 930 : { return this->_M_impl._M_header._M_parent; }
430 : :
431 : : _Const_Base_ptr
432 : : _M_root() const
433 : 100 : { return this->_M_impl._M_header._M_parent; }
434 : :
435 : : _Base_ptr&
436 : : _M_leftmost()
437 : 1959 : { return this->_M_impl._M_header._M_left; }
438 : :
439 : : _Const_Base_ptr
440 : : _M_leftmost() const
441 : : { return this->_M_impl._M_header._M_left; }
442 : :
443 : : _Base_ptr&
444 : : _M_rightmost()
445 : 1402 : { return this->_M_impl._M_header._M_right; }
446 : :
447 : : _Const_Base_ptr
448 : : _M_rightmost() const
449 : : { return this->_M_impl._M_header._M_right; }
450 : :
451 : : _Link_type
452 : : _M_begin()
453 : 3548 : { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
454 : :
455 : : _Const_Link_type
456 : : _M_begin() const
457 : : {
458 : : return static_cast<_Const_Link_type>
459 : 0 : (this->_M_impl._M_header._M_parent);
460 : : }
461 : :
462 : : _Link_type
463 : : _M_end()
464 : 8503 : { return static_cast<_Link_type>(&this->_M_impl._M_header); }
465 : :
466 : : _Const_Link_type
467 : : _M_end() const
468 : : { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
469 : :
470 : : static const_reference
471 : : _S_value(_Const_Link_type __x)
472 : 10190 : { return __x->_M_value_field; }
473 : :
474 : : static const _Key&
475 : : _S_key(_Const_Link_type __x)
476 : 20380 : { return _KeyOfValue()(_S_value(__x)); }
477 : :
478 : : static _Link_type
479 : : _S_left(_Base_ptr __x)
480 : 7069 : { return static_cast<_Link_type>(__x->_M_left); }
481 : :
482 : : static _Const_Link_type
483 : : _S_left(_Const_Base_ptr __x)
484 : 0 : { return static_cast<_Const_Link_type>(__x->_M_left); }
485 : :
486 : : static _Link_type
487 : : _S_right(_Base_ptr __x)
488 : 6185 : { return static_cast<_Link_type>(__x->_M_right); }
489 : :
490 : : static _Const_Link_type
491 : : _S_right(_Const_Base_ptr __x)
492 : 624 : { return static_cast<_Const_Link_type>(__x->_M_right); }
493 : :
494 : : static const_reference
495 : : _S_value(_Const_Base_ptr __x)
496 : 2458 : { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
497 : :
498 : : static const _Key&
499 : : _S_key(_Const_Base_ptr __x)
500 : 4916 : { return _KeyOfValue()(_S_value(__x)); }
501 : :
502 : : static _Base_ptr
503 : : _S_minimum(_Base_ptr __x)
504 : 0 : { return _Rb_tree_node_base::_S_minimum(__x); }
505 : :
506 : : static _Const_Base_ptr
507 : : _S_minimum(_Const_Base_ptr __x)
508 : : { return _Rb_tree_node_base::_S_minimum(__x); }
509 : :
510 : : static _Base_ptr
511 : : _S_maximum(_Base_ptr __x)
512 : 0 : { return _Rb_tree_node_base::_S_maximum(__x); }
513 : :
514 : : static _Const_Base_ptr
515 : : _S_maximum(_Const_Base_ptr __x)
516 : : { return _Rb_tree_node_base::_S_maximum(__x); }
517 : :
518 : : public:
519 : : typedef _Rb_tree_iterator<value_type> iterator;
520 : : typedef _Rb_tree_const_iterator<value_type> const_iterator;
521 : :
522 : : typedef std::reverse_iterator<iterator> reverse_iterator;
523 : : typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
524 : :
525 : : private:
526 : : iterator
527 : : _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y,
528 : : const value_type& __v);
529 : :
530 : : // _GLIBCXX_RESOLVE_LIB_DEFECTS
531 : : // 233. Insertion hints in associative containers.
532 : : iterator
533 : : _M_insert_lower(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
534 : :
535 : : iterator
536 : : _M_insert_equal_lower(const value_type& __x);
537 : :
538 : : _Link_type
539 : : _M_copy(_Const_Link_type __x, _Link_type __p);
540 : :
541 : : void
542 : : _M_erase(_Link_type __x);
543 : :
544 : : iterator
545 : : _M_lower_bound(_Link_type __x, _Link_type __y,
546 : : const _Key& __k);
547 : :
548 : : const_iterator
549 : : _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
550 : : const _Key& __k) const;
551 : :
552 : : iterator
553 : : _M_upper_bound(_Link_type __x, _Link_type __y,
554 : : const _Key& __k);
555 : :
556 : : const_iterator
557 : : _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
558 : : const _Key& __k) const;
559 : :
560 : : public:
561 : : // allocation/deallocation
562 : 1030 : _Rb_tree() { }
563 : :
564 : : _Rb_tree(const _Compare& __comp,
565 : : const allocator_type& __a = allocator_type())
566 : : : _M_impl(__comp, __a) { }
567 : :
568 : : _Rb_tree(const _Rb_tree& __x)
569 : 100 : : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
570 : : {
571 [ - + ]: 100 : if (__x._M_root() != 0)
572 : : {
573 : 0 : _M_root() = _M_copy(__x._M_begin(), _M_end());
574 : 0 : _M_leftmost() = _S_minimum(_M_root());
575 : 0 : _M_rightmost() = _S_maximum(_M_root());
576 : 0 : _M_impl._M_node_count = __x._M_impl._M_node_count;
577 : : }
578 : : }
579 : :
580 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
581 : : _Rb_tree(_Rb_tree&& __x);
582 : : #endif
583 : :
584 : : ~_Rb_tree()
585 : 1130 : { _M_erase(_M_begin()); }
586 : :
587 : : _Rb_tree&
588 : : operator=(const _Rb_tree& __x);
589 : :
590 : : // Accessors.
591 : : _Compare
592 : : key_comp() const
593 : 2425 : { return _M_impl._M_key_compare; }
594 : :
595 : : iterator
596 : : begin()
597 : : {
598 : : return iterator(static_cast<_Link_type>
599 : 1074 : (this->_M_impl._M_header._M_left));
600 : : }
601 : :
602 : : const_iterator
603 : : begin() const
604 : : {
605 : : return const_iterator(static_cast<_Const_Link_type>
606 : : (this->_M_impl._M_header._M_left));
607 : : }
608 : :
609 : : iterator
610 : : end()
611 : 7796 : { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
612 : :
613 : : const_iterator
614 : : end() const
615 : : {
616 : : return const_iterator(static_cast<_Const_Link_type>
617 : : (&this->_M_impl._M_header));
618 : : }
619 : :
620 : : reverse_iterator
621 : : rbegin()
622 : : { return reverse_iterator(end()); }
623 : :
624 : : const_reverse_iterator
625 : : rbegin() const
626 : : { return const_reverse_iterator(end()); }
627 : :
628 : : reverse_iterator
629 : : rend()
630 : : { return reverse_iterator(begin()); }
631 : :
632 : : const_reverse_iterator
633 : : rend() const
634 : : { return const_reverse_iterator(begin()); }
635 : :
636 : : bool
637 : : empty() const
638 : : { return _M_impl._M_node_count == 0; }
639 : :
640 : : size_type
641 : : size() const
642 : 773 : { return _M_impl._M_node_count; }
643 : :
644 : : size_type
645 : : max_size() const
646 : : { return get_allocator().max_size(); }
647 : :
648 : : void
649 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
650 : : swap(_Rb_tree&& __t);
651 : : #else
652 : : swap(_Rb_tree& __t);
653 : : #endif
654 : :
655 : : // Insert/erase.
656 : : pair<iterator, bool>
657 : : _M_insert_unique(const value_type& __x);
658 : :
659 : : iterator
660 : : _M_insert_equal(const value_type& __x);
661 : :
662 : : iterator
663 : : _M_insert_unique_(const_iterator __position, const value_type& __x);
664 : :
665 : : iterator
666 : : _M_insert_equal_(const_iterator __position, const value_type& __x);
667 : :
668 : : template<typename _InputIterator>
669 : : void
670 : : _M_insert_unique(_InputIterator __first, _InputIterator __last);
671 : :
672 : : template<typename _InputIterator>
673 : : void
674 : : _M_insert_equal(_InputIterator __first, _InputIterator __last);
675 : :
676 : : void
677 : : erase(iterator __position);
678 : :
679 : : void
680 : : erase(const_iterator __position);
681 : :
682 : : size_type
683 : : erase(const key_type& __x);
684 : :
685 : : void
686 : : erase(iterator __first, iterator __last);
687 : :
688 : : void
689 : : erase(const_iterator __first, const_iterator __last);
690 : :
691 : : void
692 : : erase(const key_type* __first, const key_type* __last);
693 : :
694 : : void
695 : : clear()
696 : : {
697 : 930 : _M_erase(_M_begin());
698 : 930 : _M_leftmost() = _M_end();
699 : 930 : _M_root() = 0;
700 : 930 : _M_rightmost() = _M_end();
701 : 930 : _M_impl._M_node_count = 0;
702 : : }
703 : :
704 : : // Set operations.
705 : : iterator
706 : : find(const key_type& __k);
707 : :
708 : : const_iterator
709 : : find(const key_type& __k) const;
710 : :
711 : : size_type
712 : : count(const key_type& __k) const;
713 : :
714 : : iterator
715 : : lower_bound(const key_type& __k)
716 : 3198 : { return _M_lower_bound(_M_begin(), _M_end(), __k); }
717 : :
718 : : const_iterator
719 : : lower_bound(const key_type& __k) const
720 : : { return _M_lower_bound(_M_begin(), _M_end(), __k); }
721 : :
722 : : iterator
723 : : upper_bound(const key_type& __k)
724 : : { return _M_upper_bound(_M_begin(), _M_end(), __k); }
725 : :
726 : : const_iterator
727 : : upper_bound(const key_type& __k) const
728 : : { return _M_upper_bound(_M_begin(), _M_end(), __k); }
729 : :
730 : : pair<iterator, iterator>
731 : : equal_range(const key_type& __k);
732 : :
733 : : pair<const_iterator, const_iterator>
734 : : equal_range(const key_type& __k) const;
735 : :
736 : : // Debugging.
737 : : bool
738 : : __rb_verify() const;
739 : : };
740 : :
741 : : template<typename _Key, typename _Val, typename _KeyOfValue,
742 : : typename _Compare, typename _Alloc>
743 : : inline bool
744 : : operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
745 : : const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
746 : : {
747 : : return __x.size() == __y.size()
748 : : && std::equal(__x.begin(), __x.end(), __y.begin());
749 : : }
750 : :
751 : : template<typename _Key, typename _Val, typename _KeyOfValue,
752 : : typename _Compare, typename _Alloc>
753 : : inline bool
754 : : operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
755 : : const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
756 : : {
757 : : return std::lexicographical_compare(__x.begin(), __x.end(),
758 : : __y.begin(), __y.end());
759 : : }
760 : :
761 : : template<typename _Key, typename _Val, typename _KeyOfValue,
762 : : typename _Compare, typename _Alloc>
763 : : inline bool
764 : : operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
765 : : const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
766 : : { return !(__x == __y); }
767 : :
768 : : template<typename _Key, typename _Val, typename _KeyOfValue,
769 : : typename _Compare, typename _Alloc>
770 : : inline bool
771 : : operator>(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
772 : : const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
773 : : { return __y < __x; }
774 : :
775 : : template<typename _Key, typename _Val, typename _KeyOfValue,
776 : : typename _Compare, typename _Alloc>
777 : : inline bool
778 : : operator<=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
779 : : const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
780 : : { return !(__y < __x); }
781 : :
782 : : template<typename _Key, typename _Val, typename _KeyOfValue,
783 : : typename _Compare, typename _Alloc>
784 : : inline bool
785 : : operator>=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
786 : : const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
787 : : { return !(__x < __y); }
788 : :
789 : : template<typename _Key, typename _Val, typename _KeyOfValue,
790 : : typename _Compare, typename _Alloc>
791 : : inline void
792 : : swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
793 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
794 : : { __x.swap(__y); }
795 : :
796 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
797 : : template<typename _Key, typename _Val, typename _KeyOfValue,
798 : : typename _Compare, typename _Alloc>
799 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
800 : : _Rb_tree(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __x)
801 : : : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
802 : : {
803 : : if (__x._M_root() != 0)
804 : : {
805 : : _M_root() = __x._M_root();
806 : : _M_leftmost() = __x._M_leftmost();
807 : : _M_rightmost() = __x._M_rightmost();
808 : : _M_root()->_M_parent = _M_end();
809 : :
810 : : __x._M_root() = 0;
811 : : __x._M_leftmost() = __x._M_end();
812 : : __x._M_rightmost() = __x._M_end();
813 : :
814 : : this->_M_impl._M_node_count = __x._M_impl._M_node_count;
815 : : __x._M_impl._M_node_count = 0;
816 : : }
817 : : }
818 : : #endif
819 : :
820 : : template<typename _Key, typename _Val, typename _KeyOfValue,
821 : : typename _Compare, typename _Alloc>
822 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
823 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
824 : : operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
825 : : {
826 : : if (this != &__x)
827 : : {
828 : : // Note that _Key may be a constant type.
829 : : clear();
830 : : _M_impl._M_key_compare = __x._M_impl._M_key_compare;
831 : : if (__x._M_root() != 0)
832 : : {
833 : : _M_root() = _M_copy(__x._M_begin(), _M_end());
834 : : _M_leftmost() = _S_minimum(_M_root());
835 : : _M_rightmost() = _S_maximum(_M_root());
836 : : _M_impl._M_node_count = __x._M_impl._M_node_count;
837 : : }
838 : : }
839 : : return *this;
840 : : }
841 : :
842 : : template<typename _Key, typename _Val, typename _KeyOfValue,
843 : : typename _Compare, typename _Alloc>
844 : : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
845 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
846 : 1532 : _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)
847 : : {
848 : : bool __insert_left = (__x != 0 || __p == _M_end()
849 : : || _M_impl._M_key_compare(_KeyOfValue()(__v),
850 [ + + ]: 2021 : _S_key(__p)));
[ + + - + ]
[ + + ]
[ + + - + ]
[ + + ]
[ + + - + ]
851 : :
852 : 969 : _Link_type __z = _M_create_node(__v);
853 : :
854 : 1532 : _Rb_tree_insert_and_rebalance(__insert_left, __z,
855 : : const_cast<_Base_ptr>(__p),
856 : : this->_M_impl._M_header);
857 : 1532 : ++_M_impl._M_node_count;
858 : 1532 : return iterator(__z);
859 : : }
860 : :
861 : : template<typename _Key, typename _Val, typename _KeyOfValue,
862 : : typename _Compare, typename _Alloc>
863 : : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
864 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
865 : : _M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
866 : : {
867 : : bool __insert_left = (__x != 0 || __p == _M_end()
868 : : || !_M_impl._M_key_compare(_S_key(__p),
869 : : _KeyOfValue()(__v)));
870 : :
871 : : _Link_type __z = _M_create_node(__v);
872 : :
873 : : _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
874 : : this->_M_impl._M_header);
875 : : ++_M_impl._M_node_count;
876 : : return iterator(__z);
877 : : }
878 : :
879 : : template<typename _Key, typename _Val, typename _KeyOfValue,
880 : : typename _Compare, typename _Alloc>
881 : : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
882 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
883 : : _M_insert_equal_lower(const _Val& __v)
884 : : {
885 : : _Link_type __x = _M_begin();
886 : : _Link_type __y = _M_end();
887 : : while (__x != 0)
888 : : {
889 : : __y = __x;
890 : : __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
891 : : _S_left(__x) : _S_right(__x);
892 : : }
893 : : return _M_insert_lower(__x, __y, __v);
894 : : }
895 : :
896 : : template<typename _Key, typename _Val, typename _KoV,
897 : : typename _Compare, typename _Alloc>
898 : : typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
899 : : _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
900 : 0 : _M_copy(_Const_Link_type __x, _Link_type __p)
901 : : {
902 : : // Structural copy. __x and __p must be non-null.
903 : 0 : _Link_type __top = _M_clone_node(__x);
904 : 0 : __top->_M_parent = __p;
905 : :
906 : : try
907 : : {
908 [ # # ]: 0 : if (__x->_M_right)
909 : 0 : __top->_M_right = _M_copy(_S_right(__x), __top);
910 : 0 : __p = __top;
911 : 0 : __x = _S_left(__x);
912 : :
913 [ # # ]: 0 : while (__x != 0)
914 : : {
915 : 0 : _Link_type __y = _M_clone_node(__x);
916 : 0 : __p->_M_left = __y;
917 : 0 : __y->_M_parent = __p;
918 [ # # ]: 0 : if (__x->_M_right)
919 : 0 : __y->_M_right = _M_copy(_S_right(__x), __y);
920 : 0 : __p = __y;
921 : 0 : __x = _S_left(__x);
922 : : }
923 : : }
924 : 0 : catch(...)
925 : : {
926 : 0 : _M_erase(__top);
927 : 0 : __throw_exception_again;
928 : : }
929 : 0 : return __top;
930 : : }
931 : :
932 : : template<typename _Key, typename _Val, typename _KeyOfValue,
933 : : typename _Compare, typename _Alloc>
934 : : void
935 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
936 : 3592 : _M_erase(_Link_type __x)
937 : : {
938 : : // Erase without rebalancing.
939 [ + + ][ + + ]: 5124 : while (__x != 0)
[ + + ]
940 : : {
941 : 1532 : _M_erase(_S_right(__x));
942 : 3064 : _Link_type __y = _S_left(__x);
943 : : _M_destroy_node(__x);
944 : 1532 : __x = __y;
945 : : }
946 : 3592 : }
947 : :
948 : : template<typename _Key, typename _Val, typename _KeyOfValue,
949 : : typename _Compare, typename _Alloc>
950 : : typename _Rb_tree<_Key, _Val, _KeyOfValue,
951 : : _Compare, _Alloc>::iterator
952 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
953 : : _M_lower_bound(_Link_type __x, _Link_type __y,
954 : : const _Key& __k)
955 : : {
956 [ + + ][ + + ]: 13738 : while (__x != 0)
[ + + ][ + + ]
[ + + ]
957 [ + + + + : 10190 : if (!_M_impl._M_key_compare(_S_key(__x), __k))
+ + + + +
+ ]
958 : 5537 : __y = __x, __x = _S_left(__x);
959 : : else
960 : 4653 : __x = _S_right(__x);
961 : 3548 : return iterator(__y);
962 : : }
963 : :
964 : : template<typename _Key, typename _Val, typename _KeyOfValue,
965 : : typename _Compare, typename _Alloc>
966 : : typename _Rb_tree<_Key, _Val, _KeyOfValue,
967 : : _Compare, _Alloc>::const_iterator
968 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
969 : : _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
970 : : const _Key& __k) const
971 : : {
972 : : while (__x != 0)
973 : : if (!_M_impl._M_key_compare(_S_key(__x), __k))
974 : : __y = __x, __x = _S_left(__x);
975 : : else
976 : : __x = _S_right(__x);
977 : : return const_iterator(__y);
978 : : }
979 : :
980 : : template<typename _Key, typename _Val, typename _KeyOfValue,
981 : : typename _Compare, typename _Alloc>
982 : : typename _Rb_tree<_Key, _Val, _KeyOfValue,
983 : : _Compare, _Alloc>::iterator
984 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
985 : : _M_upper_bound(_Link_type __x, _Link_type __y,
986 : : const _Key& __k)
987 : : {
988 : : while (__x != 0)
989 : : if (_M_impl._M_key_compare(__k, _S_key(__x)))
990 : : __y = __x, __x = _S_left(__x);
991 : : else
992 : : __x = _S_right(__x);
993 : : return iterator(__y);
994 : : }
995 : :
996 : : template<typename _Key, typename _Val, typename _KeyOfValue,
997 : : typename _Compare, typename _Alloc>
998 : : typename _Rb_tree<_Key, _Val, _KeyOfValue,
999 : : _Compare, _Alloc>::const_iterator
1000 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1001 : : _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
1002 : : const _Key& __k) const
1003 : : {
1004 : : while (__x != 0)
1005 : : if (_M_impl._M_key_compare(__k, _S_key(__x)))
1006 : : __y = __x, __x = _S_left(__x);
1007 : : else
1008 : : __x = _S_right(__x);
1009 : : return const_iterator(__y);
1010 : : }
1011 : :
1012 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1013 : : typename _Compare, typename _Alloc>
1014 : : pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1015 : : _Compare, _Alloc>::iterator,
1016 : : typename _Rb_tree<_Key, _Val, _KeyOfValue,
1017 : : _Compare, _Alloc>::iterator>
1018 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1019 : : equal_range(const _Key& __k)
1020 : : {
1021 : : _Link_type __x = _M_begin();
1022 : : _Link_type __y = _M_end();
1023 : : while (__x != 0)
1024 : : {
1025 : : if (_M_impl._M_key_compare(_S_key(__x), __k))
1026 : : __x = _S_right(__x);
1027 : : else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1028 : : __y = __x, __x = _S_left(__x);
1029 : : else
1030 : : {
1031 : : _Link_type __xu(__x), __yu(__y);
1032 : : __y = __x, __x = _S_left(__x);
1033 : : __xu = _S_right(__xu);
1034 : : return pair<iterator,
1035 : : iterator>(_M_lower_bound(__x, __y, __k),
1036 : : _M_upper_bound(__xu, __yu, __k));
1037 : : }
1038 : : }
1039 : : return pair<iterator, iterator>(iterator(__y),
1040 : : iterator(__y));
1041 : : }
1042 : :
1043 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1044 : : typename _Compare, typename _Alloc>
1045 : : pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1046 : : _Compare, _Alloc>::const_iterator,
1047 : : typename _Rb_tree<_Key, _Val, _KeyOfValue,
1048 : : _Compare, _Alloc>::const_iterator>
1049 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1050 : : equal_range(const _Key& __k) const
1051 : : {
1052 : : _Const_Link_type __x = _M_begin();
1053 : : _Const_Link_type __y = _M_end();
1054 : : while (__x != 0)
1055 : : {
1056 : : if (_M_impl._M_key_compare(_S_key(__x), __k))
1057 : : __x = _S_right(__x);
1058 : : else if (_M_impl._M_key_compare(__k, _S_key(__x)))
1059 : : __y = __x, __x = _S_left(__x);
1060 : : else
1061 : : {
1062 : : _Const_Link_type __xu(__x), __yu(__y);
1063 : : __y = __x, __x = _S_left(__x);
1064 : : __xu = _S_right(__xu);
1065 : : return pair<const_iterator,
1066 : : const_iterator>(_M_lower_bound(__x, __y, __k),
1067 : : _M_upper_bound(__xu, __yu, __k));
1068 : : }
1069 : : }
1070 : : return pair<const_iterator, const_iterator>(const_iterator(__y),
1071 : : const_iterator(__y));
1072 : : }
1073 : :
1074 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1075 : : typename _Compare, typename _Alloc>
1076 : : void
1077 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1078 : : #ifdef __GXX_EXPERIMENTAL_CXX0X__
1079 : : swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __t)
1080 : : #else
1081 : : swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
1082 : : #endif
1083 : : {
1084 : : if (_M_root() == 0)
1085 : : {
1086 : : if (__t._M_root() != 0)
1087 : : {
1088 : : _M_root() = __t._M_root();
1089 : : _M_leftmost() = __t._M_leftmost();
1090 : : _M_rightmost() = __t._M_rightmost();
1091 : : _M_root()->_M_parent = _M_end();
1092 : :
1093 : : __t._M_root() = 0;
1094 : : __t._M_leftmost() = __t._M_end();
1095 : : __t._M_rightmost() = __t._M_end();
1096 : : }
1097 : : }
1098 : : else if (__t._M_root() == 0)
1099 : : {
1100 : : __t._M_root() = _M_root();
1101 : : __t._M_leftmost() = _M_leftmost();
1102 : : __t._M_rightmost() = _M_rightmost();
1103 : : __t._M_root()->_M_parent = __t._M_end();
1104 : :
1105 : : _M_root() = 0;
1106 : : _M_leftmost() = _M_end();
1107 : : _M_rightmost() = _M_end();
1108 : : }
1109 : : else
1110 : : {
1111 : : std::swap(_M_root(),__t._M_root());
1112 : : std::swap(_M_leftmost(),__t._M_leftmost());
1113 : : std::swap(_M_rightmost(),__t._M_rightmost());
1114 : :
1115 : : _M_root()->_M_parent = _M_end();
1116 : : __t._M_root()->_M_parent = __t._M_end();
1117 : : }
1118 : : // No need to swap header's color as it does not change.
1119 : : std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
1120 : : std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
1121 : :
1122 : : // _GLIBCXX_RESOLVE_LIB_DEFECTS
1123 : : // 431. Swapping containers with unequal allocators.
1124 : : std::__alloc_swap<_Node_allocator>::
1125 : : _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator());
1126 : : }
1127 : :
1128 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1129 : : typename _Compare, typename _Alloc>
1130 : : pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
1131 : : _Compare, _Alloc>::iterator, bool>
1132 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1133 : 537 : _M_insert_unique(const _Val& __v)
1134 : : {
1135 : 537 : _Link_type __x = _M_begin();
1136 : 537 : _Link_type __y = _M_end();
1137 : 537 : bool __comp = true;
1138 [ - + ][ - + ]: 537 : while (__x != 0)
[ - + ]
1139 : : {
1140 : 0 : __y = __x;
1141 : 0 : __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
1142 [ # # ][ # # ]: 0 : __x = __comp ? _S_left(__x) : _S_right(__x);
[ # # ]
1143 : : }
1144 : : iterator __j = iterator(__y);
1145 [ + - ][ + - ]: 537 : if (__comp)
[ + - ]
1146 : : {
1147 [ + - ][ + - ]: 537 : if (__j == begin())
[ + - ]
1148 : 537 : return pair<iterator, bool>(_M_insert_(__x, __y, __v), true);
1149 : : else
1150 : : --__j;
1151 : : }
1152 [ # # # # : 0 : if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
# # ]
1153 : 0 : return pair<iterator, bool>(_M_insert_(__x, __y, __v), true);
1154 : 537 : return pair<iterator, bool>(__j, false);
1155 : : }
1156 : :
1157 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1158 : : typename _Compare, typename _Alloc>
1159 : : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1160 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1161 : : _M_insert_equal(const _Val& __v)
1162 : : {
1163 : : _Link_type __x = _M_begin();
1164 : : _Link_type __y = _M_end();
1165 : : while (__x != 0)
1166 : : {
1167 : : __y = __x;
1168 : : __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
1169 : : _S_left(__x) : _S_right(__x);
1170 : : }
1171 : : return _M_insert_(__x, __y, __v);
1172 : : }
1173 : :
1174 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1175 : : typename _Compare, typename _Alloc>
1176 : : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1177 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1178 : 1532 : _M_insert_unique_(const_iterator __position, const _Val& __v)
1179 : : {
1180 : : // end()
1181 [ + + ][ + + ]: 1532 : if (__position._M_node == _M_end())
[ + + ]
1182 : : {
1183 [ + + + - ]: 1009 : if (size() > 0
[ + + ]
[ + + + - ]
[ + + ]
[ + + + - ]
[ + + ]
1184 : : && _M_impl._M_key_compare(_S_key(_M_rightmost()),
1185 : : _KeyOfValue()(__v)))
1186 : 236 : return _M_insert_(0, _M_rightmost(), __v);
1187 : : else
1188 : 537 : return _M_insert_unique(__v).first;
1189 : : }
1190 [ + - + - : 759 : else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
+ - ]
1191 : : _S_key(__position._M_node)))
1192 : : {
1193 : : // First, try before...
1194 : 759 : const_iterator __before = __position;
1195 [ + + ][ + + ]: 759 : if (__position._M_node == _M_leftmost()) // begin()
[ + + ]
1196 : 135 : return _M_insert_(_M_leftmost(), _M_leftmost(), __v);
1197 [ + - + - : 624 : else if (_M_impl._M_key_compare(_S_key((--__before)._M_node),
+ - ]
1198 : : _KeyOfValue()(__v)))
1199 : : {
1200 [ + + ][ + + ]: 624 : if (_S_right(__before._M_node) == 0)
[ + + ]
1201 : 253 : return _M_insert_(0, __before._M_node, __v);
1202 : : else
1203 : : return _M_insert_(__position._M_node,
1204 : 371 : __position._M_node, __v);
1205 : : }
1206 : : else
1207 : 0 : return _M_insert_unique(__v).first;
1208 : : }
1209 [ # # # # : 0 : else if (_M_impl._M_key_compare(_S_key(__position._M_node),
# # ]
1210 : : _KeyOfValue()(__v)))
1211 : : {
1212 : : // ... then try after.
1213 : 0 : const_iterator __after = __position;
1214 [ # # ][ # # ]: 0 : if (__position._M_node == _M_rightmost())
[ # # ]
1215 : 0 : return _M_insert_(0, _M_rightmost(), __v);
1216 [ # # # # : 0 : else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
# # ]
1217 : : _S_key((++__after)._M_node)))
1218 : : {
1219 [ # # ][ # # ]: 0 : if (_S_right(__position._M_node) == 0)
[ # # ]
1220 : 0 : return _M_insert_(0, __position._M_node, __v);
1221 : : else
1222 : 0 : return _M_insert_(__after._M_node, __after._M_node, __v);
1223 : : }
1224 : : else
1225 : 0 : return _M_insert_unique(__v).first;
1226 : : }
1227 : : else
1228 : : // Equivalent keys.
1229 : : return iterator(static_cast<_Link_type>
1230 : 1532 : (const_cast<_Base_ptr>(__position._M_node)));
1231 : : }
1232 : :
1233 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1234 : : typename _Compare, typename _Alloc>
1235 : : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
1236 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1237 : : _M_insert_equal_(const_iterator __position, const _Val& __v)
1238 : : {
1239 : : // end()
1240 : : if (__position._M_node == _M_end())
1241 : : {
1242 : : if (size() > 0
1243 : : && !_M_impl._M_key_compare(_KeyOfValue()(__v),
1244 : : _S_key(_M_rightmost())))
1245 : : return _M_insert_(0, _M_rightmost(), __v);
1246 : : else
1247 : : return _M_insert_equal(__v);
1248 : : }
1249 : : else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
1250 : : _KeyOfValue()(__v)))
1251 : : {
1252 : : // First, try before...
1253 : : const_iterator __before = __position;
1254 : : if (__position._M_node == _M_leftmost()) // begin()
1255 : : return _M_insert_(_M_leftmost(), _M_leftmost(), __v);
1256 : : else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
1257 : : _S_key((--__before)._M_node)))
1258 : : {
1259 : : if (_S_right(__before._M_node) == 0)
1260 : : return _M_insert_(0, __before._M_node, __v);
1261 : : else
1262 : : return _M_insert_(__position._M_node,
1263 : : __position._M_node, __v);
1264 : : }
1265 : : else
1266 : : return _M_insert_equal(__v);
1267 : : }
1268 : : else
1269 : : {
1270 : : // ... then try after.
1271 : : const_iterator __after = __position;
1272 : : if (__position._M_node == _M_rightmost())
1273 : : return _M_insert_(0, _M_rightmost(), __v);
1274 : : else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
1275 : : _KeyOfValue()(__v)))
1276 : : {
1277 : : if (_S_right(__position._M_node) == 0)
1278 : : return _M_insert_(0, __position._M_node, __v);
1279 : : else
1280 : : return _M_insert_(__after._M_node, __after._M_node, __v);
1281 : : }
1282 : : else
1283 : : return _M_insert_equal_lower(__v);
1284 : : }
1285 : : }
1286 : :
1287 : : template<typename _Key, typename _Val, typename _KoV,
1288 : : typename _Cmp, typename _Alloc>
1289 : : template<class _II>
1290 : : void
1291 : : _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1292 : : _M_insert_unique(_II __first, _II __last)
1293 : : {
1294 : : for (; __first != __last; ++__first)
1295 : : _M_insert_unique_(end(), *__first);
1296 : : }
1297 : :
1298 : : template<typename _Key, typename _Val, typename _KoV,
1299 : : typename _Cmp, typename _Alloc>
1300 : : template<class _II>
1301 : : void
1302 : : _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
1303 : : _M_insert_equal(_II __first, _II __last)
1304 : : {
1305 : : for (; __first != __last; ++__first)
1306 : : _M_insert_equal_(end(), *__first);
1307 : : }
1308 : :
1309 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1310 : : typename _Compare, typename _Alloc>
1311 : : inline void
1312 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1313 : : erase(iterator __position)
1314 : : {
1315 : : _Link_type __y =
1316 : : static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
1317 : : (__position._M_node,
1318 : : this->_M_impl._M_header));
1319 : : _M_destroy_node(__y);
1320 : : --_M_impl._M_node_count;
1321 : : }
1322 : :
1323 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1324 : : typename _Compare, typename _Alloc>
1325 : : inline void
1326 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1327 : : erase(const_iterator __position)
1328 : : {
1329 : : _Link_type __y =
1330 : : static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
1331 : : (const_cast<_Base_ptr>(__position._M_node),
1332 : : this->_M_impl._M_header));
1333 : : _M_destroy_node(__y);
1334 : : --_M_impl._M_node_count;
1335 : : }
1336 : :
1337 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1338 : : typename _Compare, typename _Alloc>
1339 : : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1340 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1341 : : erase(const _Key& __x)
1342 : : {
1343 : : pair<iterator, iterator> __p = equal_range(__x);
1344 : : const size_type __old_size = size();
1345 : : erase(__p.first, __p.second);
1346 : : return __old_size - size();
1347 : : }
1348 : :
1349 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1350 : : typename _Compare, typename _Alloc>
1351 : : void
1352 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1353 : : erase(iterator __first, iterator __last)
1354 : : {
1355 : : if (__first == begin() && __last == end())
1356 : : clear();
1357 : : else
1358 : : while (__first != __last)
1359 : : erase(__first++);
1360 : : }
1361 : :
1362 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1363 : : typename _Compare, typename _Alloc>
1364 : : void
1365 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1366 : : erase(const_iterator __first, const_iterator __last)
1367 : : {
1368 : : if (__first == begin() && __last == end())
1369 : : clear();
1370 : : else
1371 : : while (__first != __last)
1372 : : erase(__first++);
1373 : : }
1374 : :
1375 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1376 : : typename _Compare, typename _Alloc>
1377 : : void
1378 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1379 : : erase(const _Key* __first, const _Key* __last)
1380 : : {
1381 : : while (__first != __last)
1382 : : erase(*__first++);
1383 : : }
1384 : :
1385 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1386 : : typename _Compare, typename _Alloc>
1387 : : typename _Rb_tree<_Key, _Val, _KeyOfValue,
1388 : : _Compare, _Alloc>::iterator
1389 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1390 : : find(const _Key& __k)
1391 : : {
1392 : 350 : iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
1393 : : return (__j == end()
1394 : : || _M_impl._M_key_compare(__k,
1395 [ + - - + ]: 700 : _S_key(__j._M_node))) ? end() : __j;
[ + - - + ]
1396 : : }
1397 : :
1398 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1399 : : typename _Compare, typename _Alloc>
1400 : : typename _Rb_tree<_Key, _Val, _KeyOfValue,
1401 : : _Compare, _Alloc>::const_iterator
1402 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1403 : : find(const _Key& __k) const
1404 : : {
1405 : : const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
1406 : : return (__j == end()
1407 : : || _M_impl._M_key_compare(__k,
1408 : : _S_key(__j._M_node))) ? end() : __j;
1409 : : }
1410 : :
1411 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1412 : : typename _Compare, typename _Alloc>
1413 : : typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
1414 : : _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
1415 : : count(const _Key& __k) const
1416 : : {
1417 : : pair<const_iterator, const_iterator> __p = equal_range(__k);
1418 : : const size_type __n = std::distance(__p.first, __p.second);
1419 : : return __n;
1420 : : }
1421 : :
1422 : : unsigned int
1423 : : _Rb_tree_black_count(const _Rb_tree_node_base* __node,
1424 : : const _Rb_tree_node_base* __root);
1425 : :
1426 : : template<typename _Key, typename _Val, typename _KeyOfValue,
1427 : : typename _Compare, typename _Alloc>
1428 : : bool
1429 : : _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
1430 : : {
1431 : : if (_M_impl._M_node_count == 0 || begin() == end())
1432 : : return _M_impl._M_node_count == 0 && begin() == end()
1433 : : && this->_M_impl._M_header._M_left == _M_end()
1434 : : && this->_M_impl._M_header._M_right == _M_end();
1435 : :
1436 : : unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
1437 : : for (const_iterator __it = begin(); __it != end(); ++__it)
1438 : : {
1439 : : _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
1440 : : _Const_Link_type __L = _S_left(__x);
1441 : : _Const_Link_type __R = _S_right(__x);
1442 : :
1443 : : if (__x->_M_color == _S_red)
1444 : : if ((__L && __L->_M_color == _S_red)
1445 : : || (__R && __R->_M_color == _S_red))
1446 : : return false;
1447 : :
1448 : : if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
1449 : : return false;
1450 : : if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
1451 : : return false;
1452 : :
1453 : : if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
1454 : : return false;
1455 : : }
1456 : :
1457 : : if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
1458 : : return false;
1459 : : if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
1460 : : return false;
1461 : : return true;
1462 : : }
1463 : :
1464 : : _GLIBCXX_END_NAMESPACE
1465 : :
1466 : : #endif
|
