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