wpkg test coverage results

Coverage test results of the Windows Packager by Made to Order Software Corporation.

LCOV - code coverage report
Current view: top level - usr/include/c++/4.6/bits - stl_tree.h (source / functions) Hit Total Coverage
Test: coverage.info Lines: 247 300 82.3 %
Date: 2013-06-17 Functions: 827 900 91.9 %
Legend: Lines: hit not hit

          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        2782 :     _S_minimum(_Base_ptr __x)
     102             :     {
     103       15288 :       while (__x->_M_left != 0) __x = __x->_M_left;
     104        2782 :       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        2782 :     _S_maximum(_Base_ptr __x)
     116             :     {
     117       19456 :       while (__x->_M_right != 0) __x = __x->_M_right;
     118        2782 :       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     1164789 :     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     1165539 :         _Rb_tree_node(_Args&&... __args)
     138             :         : _Rb_tree_node_base(),
     139     1165539 :           _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             :       _Rb_tree_iterator()
     170             :       : _M_node() { }
     171             : 
     172             :       explicit
     173     4921008 :       _Rb_tree_iterator(_Link_type __x)
     174     4921008 :       : _M_node(__x) { }
     175             : 
     176             :       reference
     177     1732359 :       operator*() const
     178     1732359 :       { return static_cast<_Link_type>(_M_node)->_M_value_field; }
     179             : 
     180             :       pointer
     181         226 :       operator->() const
     182             :       { return std::__addressof(static_cast<_Link_type>
     183         226 :                                 (_M_node)->_M_value_field); }
     184             : 
     185             :       _Self&
     186         662 :       operator++()
     187             :       {
     188         662 :         _M_node = _Rb_tree_increment(_M_node);
     189         662 :         return *this;
     190             :       }
     191             : 
     192             :       _Self
     193             :       operator++(int)
     194             :       {
     195             :         _Self __tmp = *this;
     196             :         _M_node = _Rb_tree_increment(_M_node);
     197             :         return __tmp;
     198             :       }
     199             : 
     200             :       _Self&
     201           0 :       operator--()
     202             :       {
     203           0 :         _M_node = _Rb_tree_decrement(_M_node);
     204           0 :         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     1492890 :       operator==(const _Self& __x) const
     217     1492890 :       { return _M_node == __x._M_node; }
     218             : 
     219             :       bool
     220      310900 :       operator!=(const _Self& __x) const
     221      310900 :       { 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             :       _Rb_tree_const_iterator()
     243             :       : _M_node() { }
     244             : 
     245             :       explicit
     246     3987231 :       _Rb_tree_const_iterator(_Link_type __x)
     247     3987231 :       : _M_node(__x) { }
     248             : 
     249     1362048 :       _Rb_tree_const_iterator(const iterator& __it)
     250     1362048 :       : _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             :       operator*() const
     259             :       { return static_cast<_Link_type>(_M_node)->_M_value_field; }
     260             : 
     261             :       pointer
     262     1581197 :       operator->() const
     263             :       { return std::__addressof(static_cast<_Link_type>
     264     1581197 :                                 (_M_node)->_M_value_field); }
     265             : 
     266             :       _Self&
     267      313653 :       operator++()
     268             :       {
     269      313653 :         _M_node = _Rb_tree_increment(_M_node);
     270      313653 :         return *this;
     271             :       }
     272             : 
     273             :       _Self
     274             :       operator++(int)
     275             :       {
     276             :         _Self __tmp = *this;
     277             :         _M_node = _Rb_tree_increment(_M_node);
     278             :         return __tmp;
     279             :       }
     280             : 
     281             :       _Self&
     282      509668 :       operator--()
     283             :       {
     284      509668 :         _M_node = _Rb_tree_decrement(_M_node);
     285      509668 :         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     1355216 :       operator==(const _Self& __x) const
     298     1355216 :       { return _M_node == __x._M_node; }
     299             : 
     300             :       bool
     301     1314151 :       operator!=(const _Self& __x) const
     302     1314151 :       { 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     3569416 :       _M_get_Node_allocator()
     356     3569416 :       { return *static_cast<_Node_allocator*>(&this->_M_impl); }
     357             :       
     358             :       const _Node_allocator&
     359      484984 :       _M_get_Node_allocator() const
     360      484984 :       { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
     361             : 
     362             :       allocator_type
     363             :       get_allocator() const
     364             :       { return allocator_type(_M_get_Node_allocator()); }
     365             : 
     366             :     protected:
     367             :       _Link_type
     368     1165539 :       _M_get_node()
     369     1165539 :       { return _M_impl._Node_allocator::allocate(1); }
     370             : 
     371             :       void
     372     1164789 :       _M_put_node(_Link_type __p)
     373     1164789 :       { _M_impl._Node_allocator::deallocate(__p, 1); }
     374             : 
     375             : #ifndef __GXX_EXPERIMENTAL_CXX0X__
     376             :       _Link_type
     377             :       _M_create_node(const value_type& __x)
     378             :       {
     379             :         _Link_type __tmp = _M_get_node();
     380             :         __try
     381             :           { 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             :         return __tmp;
     389             :       }
     390             : 
     391             :       void
     392             :       _M_destroy_node(_Link_type __p)
     393             :       {
     394             :         get_allocator().destroy(std::__addressof(__p->_M_value_field));
     395             :         _M_put_node(__p);
     396             :       }
     397             : #else
     398             :       template<typename... _Args>
     399             :         _Link_type
     400     1165539 :         _M_create_node(_Args&&... __args)
     401             :         {
     402     1165539 :           _Link_type __tmp = _M_get_node();
     403             :           __try
     404             :             {
     405     1165539 :               _M_get_Node_allocator().construct(__tmp,
     406             :                                              std::forward<_Args>(__args)...);
     407             :             }
     408           0 :           __catch(...)
     409             :             {
     410           0 :               _M_put_node(__tmp);
     411           0 :               __throw_exception_again;
     412             :             }
     413     1165539 :           return __tmp;
     414             :         }
     415             : 
     416             :       void
     417     1164789 :       _M_destroy_node(_Link_type __p)
     418             :       {
     419     1164789 :         _M_get_Node_allocator().destroy(__p);
     420     1164789 :         _M_put_node(__p);
     421     1164789 :       }
     422             : #endif
     423             : 
     424             :       _Link_type
     425      212539 :       _M_clone_node(_Const_Link_type __x)
     426             :       {
     427      212539 :         _Link_type __tmp = _M_create_node(__x->_M_value_field);
     428      212539 :         __tmp->_M_color = __x->_M_color;
     429      212539 :         __tmp->_M_left = 0;
     430      212539 :         __tmp->_M_right = 0;
     431      212539 :         return __tmp;
     432             :       }
     433             : 
     434             :     protected:
     435             :       template<typename _Key_compare, 
     436             :                bool _Is_pod_comparator = __is_pod(_Key_compare)>
     437     2124908 :         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     1597848 :           _Rb_tree_impl()
     444             :           : _Node_allocator(), _M_key_compare(), _M_header(),
     445     1597848 :             _M_node_count(0)
     446     1597848 :           { _M_initialize(); }
     447             : 
     448      527810 :           _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
     449             :           : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
     450      527810 :             _M_node_count(0)
     451      527810 :           { _M_initialize(); }
     452             : 
     453             :         private:
     454             :           void
     455     2125658 :           _M_initialize()
     456             :           {
     457     2125658 :             this->_M_header._M_color = _S_red;
     458     2125658 :             this->_M_header._M_parent = 0;
     459     2125658 :             this->_M_header._M_left = &this->_M_header;
     460     2125658 :             this->_M_header._M_right = &this->_M_header;
     461     2125658 :           }         
     462             :         };
     463             : 
     464             :       _Rb_tree_impl<_Compare> _M_impl;
     465             : 
     466             :     protected:
     467             :       _Base_ptr&
     468     2519530 :       _M_root()
     469     2519530 :       { return this->_M_impl._M_header._M_parent; }
     470             : 
     471             :       _Const_Base_ptr
     472      683466 :       _M_root() const
     473      683466 :       { return this->_M_impl._M_header._M_parent; }
     474             : 
     475             :       _Base_ptr&
     476     1978359 :       _M_leftmost()
     477     1978359 :       { return this->_M_impl._M_header._M_left; }
     478             : 
     479             :       _Const_Base_ptr
     480             :       _M_leftmost() const
     481             :       { return this->_M_impl._M_header._M_left; }
     482             : 
     483             :       _Base_ptr&
     484     1877828 :       _M_rightmost()
     485     1877828 :       { return this->_M_impl._M_header._M_right; }
     486             : 
     487             :       _Const_Base_ptr
     488             :       _M_rightmost() const
     489             :       { return this->_M_impl._M_header._M_right; }
     490             : 
     491             :       _Link_type
     492     4882158 :       _M_begin()
     493     4882158 :       { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
     494             : 
     495             :       _Const_Link_type
     496      835703 :       _M_begin() const
     497             :       {
     498             :         return static_cast<_Const_Link_type>
     499      835703 :           (this->_M_impl._M_header._M_parent);
     500             :       }
     501             : 
     502             :       _Link_type
     503     5732714 :       _M_end()
     504     5732714 :       { return static_cast<_Link_type>(&this->_M_impl._M_header); }
     505             : 
     506             :       _Const_Link_type
     507      832921 :       _M_end() const
     508      832921 :       { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
     509             : 
     510             :       static const_reference
     511     7810796 :       _S_value(_Const_Link_type __x)
     512     7810796 :       { return __x->_M_value_field; }
     513             : 
     514             :       static const _Key&
     515     7810796 :       _S_key(_Const_Link_type __x)
     516     7810796 :       { return _KeyOfValue()(_S_value(__x)); }
     517             : 
     518             :       static _Link_type
     519     2513710 :       _S_left(_Base_ptr __x)
     520     2513710 :       { return static_cast<_Link_type>(__x->_M_left); }
     521             : 
     522             :       static _Const_Link_type
     523     1526897 :       _S_left(_Const_Base_ptr __x)
     524     1526897 :       { return static_cast<_Const_Link_type>(__x->_M_left); }
     525             : 
     526             :       static _Link_type
     527     4712808 :       _S_right(_Base_ptr __x)
     528     4712808 :       { return static_cast<_Link_type>(__x->_M_right); }
     529             : 
     530             :       static _Const_Link_type
     531     2219423 :       _S_right(_Const_Base_ptr __x)
     532     2219423 :       { return static_cast<_Const_Link_type>(__x->_M_right); }
     533             : 
     534             :       static const_reference
     535     3004329 :       _S_value(_Const_Base_ptr __x)
     536     3004329 :       { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
     537             : 
     538             :       static const _Key&
     539     3004329 :       _S_key(_Const_Base_ptr __x)
     540     3004329 :       { return _KeyOfValue()(_S_value(__x)); }
     541             : 
     542             :       static _Base_ptr
     543        2782 :       _S_minimum(_Base_ptr __x)
     544        2782 :       { return _Rb_tree_node_base::_S_minimum(__x); }
     545             : 
     546             :       static _Const_Base_ptr
     547             :       _S_minimum(_Const_Base_ptr __x)
     548             :       { return _Rb_tree_node_base::_S_minimum(__x); }
     549             : 
     550             :       static _Base_ptr
     551        2782 :       _S_maximum(_Base_ptr __x)
     552        2782 :       { return _Rb_tree_node_base::_S_maximum(__x); }
     553             : 
     554             :       static _Const_Base_ptr
     555             :       _S_maximum(_Const_Base_ptr __x)
     556             :       { return _Rb_tree_node_base::_S_maximum(__x); }
     557             : 
     558             :     public:
     559             :       typedef _Rb_tree_iterator<value_type>       iterator;
     560             :       typedef _Rb_tree_const_iterator<value_type> const_iterator;
     561             : 
     562             :       typedef std::reverse_iterator<iterator>       reverse_iterator;
     563             :       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
     564             : 
     565             :     private:
     566             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
     567             :       template<typename _Arg>
     568             :         iterator
     569             :         _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y, _Arg&& __v);
     570             : 
     571             :       template<typename _Arg>
     572             :         iterator
     573             :         _M_insert_lower(_Base_ptr __x, _Base_ptr __y, _Arg&& __v);
     574             : 
     575             :       template<typename _Arg>
     576             :         iterator
     577             :         _M_insert_equal_lower(_Arg&& __x);
     578             : #else
     579             :       iterator
     580             :       _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y,
     581             :                  const value_type& __v);
     582             : 
     583             :       // _GLIBCXX_RESOLVE_LIB_DEFECTS
     584             :       // 233. Insertion hints in associative containers.
     585             :       iterator
     586             :       _M_insert_lower(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
     587             : 
     588             :       iterator
     589             :       _M_insert_equal_lower(const value_type& __x);
     590             : #endif
     591             : 
     592             :       _Link_type
     593             :       _M_copy(_Const_Link_type __x, _Link_type __p);
     594             : 
     595             :       void
     596             :       _M_erase(_Link_type __x);
     597             : 
     598             :       iterator
     599             :       _M_lower_bound(_Link_type __x, _Link_type __y,
     600             :                      const _Key& __k);
     601             : 
     602             :       const_iterator
     603             :       _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
     604             :                      const _Key& __k) const;
     605             : 
     606             :       iterator
     607             :       _M_upper_bound(_Link_type __x, _Link_type __y,
     608             :                      const _Key& __k);
     609             : 
     610             :       const_iterator
     611             :       _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
     612             :                      const _Key& __k) const;
     613             : 
     614             :     public:
     615             :       // allocation/deallocation
     616     1597848 :       _Rb_tree() { }
     617             : 
     618             :       _Rb_tree(const _Compare& __comp,
     619             :                const allocator_type& __a = allocator_type())
     620             :       : _M_impl(__comp, __a) { }
     621             : 
     622      484984 :       _Rb_tree(const _Rb_tree& __x)
     623      484984 :       : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
     624             :       {
     625      484984 :         if (__x._M_root() != 0)
     626             :           {
     627        2782 :             _M_root() = _M_copy(__x._M_begin(), _M_end());
     628        2782 :             _M_leftmost() = _S_minimum(_M_root());
     629        2782 :             _M_rightmost() = _S_maximum(_M_root());
     630        2782 :             _M_impl._M_node_count = __x._M_impl._M_node_count;
     631             :           }
     632      484984 :       }
     633             : 
     634             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
     635             :       _Rb_tree(_Rb_tree&& __x);
     636             : #endif
     637             : 
     638     2124908 :       ~_Rb_tree()
     639     2124908 :       { _M_erase(_M_begin()); }
     640             : 
     641             :       _Rb_tree&
     642             :       operator=(const _Rb_tree& __x);
     643             : 
     644             :       // Accessors.
     645             :       _Compare
     646      676816 :       key_comp() const
     647      676816 :       { return _M_impl._M_key_compare; }
     648             : 
     649             :       iterator
     650      119028 :       begin()
     651             :       { 
     652             :         return iterator(static_cast<_Link_type>
     653      119028 :                         (this->_M_impl._M_header._M_left));
     654             :       }
     655             : 
     656             :       const_iterator
     657      614135 :       begin() const
     658             :       { 
     659             :         return const_iterator(static_cast<_Const_Link_type>
     660      614135 :                               (this->_M_impl._M_header._M_left));
     661             :       }
     662             : 
     663             :       iterator
     664     2363818 :       end()
     665     2363818 :       { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
     666             : 
     667             :       const_iterator
     668     2540175 :       end() const
     669             :       { 
     670             :         return const_iterator(static_cast<_Const_Link_type>
     671     2540175 :                               (&this->_M_impl._M_header));
     672             :       }
     673             : 
     674             :       reverse_iterator
     675             :       rbegin()
     676             :       { return reverse_iterator(end()); }
     677             : 
     678             :       const_reverse_iterator
     679             :       rbegin() const
     680             :       { return const_reverse_iterator(end()); }
     681             : 
     682             :       reverse_iterator
     683             :       rend()
     684             :       { return reverse_iterator(begin()); }
     685             : 
     686             :       const_reverse_iterator
     687             :       rend() const
     688             :       { return const_reverse_iterator(begin()); }
     689             : 
     690             :       bool
     691         914 :       empty() const
     692         914 :       { return _M_impl._M_node_count == 0; }
     693             : 
     694             :       size_type
     695      378742 :       size() const
     696      378742 :       { return _M_impl._M_node_count; }
     697             : 
     698             :       size_type
     699             :       max_size() const
     700             :       { return _M_get_Node_allocator().max_size(); }
     701             : 
     702             :       void
     703             :       swap(_Rb_tree& __t);      
     704             : 
     705             :       // Insert/erase.
     706             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
     707             :       template<typename _Arg>
     708             :         pair<iterator, bool>
     709             :         _M_insert_unique(_Arg&& __x);
     710             : 
     711             :       template<typename _Arg>
     712             :         iterator
     713             :         _M_insert_equal(_Arg&& __x);
     714             : 
     715             :       template<typename _Arg>
     716             :         iterator
     717             :         _M_insert_unique_(const_iterator __position, _Arg&& __x);
     718             : 
     719             :       template<typename _Arg>
     720             :         iterator
     721             :         _M_insert_equal_(const_iterator __position, _Arg&& __x);
     722             : #else
     723             :       pair<iterator, bool>
     724             :       _M_insert_unique(const value_type& __x);
     725             : 
     726             :       iterator
     727             :       _M_insert_equal(const value_type& __x);
     728             : 
     729             :       iterator
     730             :       _M_insert_unique_(const_iterator __position, const value_type& __x);
     731             : 
     732             :       iterator
     733             :       _M_insert_equal_(const_iterator __position, const value_type& __x);
     734             : #endif
     735             : 
     736             :       template<typename _InputIterator>
     737             :         void
     738             :         _M_insert_unique(_InputIterator __first, _InputIterator __last);
     739             : 
     740             :       template<typename _InputIterator>
     741             :         void
     742             :         _M_insert_equal(_InputIterator __first, _InputIterator __last);
     743             : 
     744             :     private:
     745             :       void
     746             :       _M_erase_aux(const_iterator __position);
     747             : 
     748             :       void
     749             :       _M_erase_aux(const_iterator __first, const_iterator __last);
     750             : 
     751             :     public:
     752             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
     753             :       // _GLIBCXX_RESOLVE_LIB_DEFECTS
     754             :       // DR 130. Associative erase should return an iterator.
     755             :       iterator
     756             :       erase(const_iterator __position)
     757             :       {
     758             :         const_iterator __result = __position;
     759             :         ++__result;
     760             :         _M_erase_aux(__position);
     761             :         return __result._M_const_cast();
     762             :       }
     763             : 
     764             :       // LWG 2059.
     765             :       iterator
     766         436 :       erase(iterator __position)
     767             :       {
     768         436 :         iterator __result = __position;
     769         436 :         ++__result;
     770         436 :         _M_erase_aux(__position);
     771         436 :         return __result;
     772             :       }
     773             : #else
     774             :       void
     775             :       erase(iterator __position)
     776             :       { _M_erase_aux(__position); }
     777             : 
     778             :       void
     779             :       erase(const_iterator __position)
     780             :       { _M_erase_aux(__position); }
     781             : #endif
     782             :       size_type
     783             :       erase(const key_type& __x);
     784             : 
     785             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
     786             :       // _GLIBCXX_RESOLVE_LIB_DEFECTS
     787             :       // DR 130. Associative erase should return an iterator.
     788             :       iterator
     789             :       erase(const_iterator __first, const_iterator __last)
     790             :       {
     791             :         _M_erase_aux(__first, __last);
     792             :         return __last._M_const_cast();
     793             :       }
     794             : #else
     795             :       void
     796             :       erase(iterator __first, iterator __last)
     797             :       { _M_erase_aux(__first, __last); }
     798             : 
     799             :       void
     800             :       erase(const_iterator __first, const_iterator __last)
     801             :       { _M_erase_aux(__first, __last); }
     802             : #endif
     803             :       void
     804             :       erase(const key_type* __first, const key_type* __last);
     805             : 
     806             :       void
     807     1272088 :       clear()
     808             :       {
     809     1272088 :         _M_erase(_M_begin());
     810     1272088 :         _M_leftmost() = _M_end();
     811     1272088 :         _M_root() = 0;
     812     1272088 :         _M_rightmost() = _M_end();
     813     1272088 :         _M_impl._M_node_count = 0;
     814     1272088 :       }
     815             : 
     816             :       // Set operations.
     817             :       iterator
     818             :       find(const key_type& __k);
     819             : 
     820             :       const_iterator
     821             :       find(const key_type& __k) const;
     822             : 
     823             :       size_type
     824             :       count(const key_type& __k) const;
     825             : 
     826             :       iterator
     827     1055543 :       lower_bound(const key_type& __k)
     828     1055543 :       { return _M_lower_bound(_M_begin(), _M_end(), __k); }
     829             : 
     830             :       const_iterator
     831             :       lower_bound(const key_type& __k) const
     832             :       { return _M_lower_bound(_M_begin(), _M_end(), __k); }
     833             : 
     834             :       iterator
     835             :       upper_bound(const key_type& __k)
     836             :       { return _M_upper_bound(_M_begin(), _M_end(), __k); }
     837             : 
     838             :       const_iterator
     839             :       upper_bound(const key_type& __k) const
     840             :       { return _M_upper_bound(_M_begin(), _M_end(), __k); }
     841             : 
     842             :       pair<iterator, iterator>
     843             :       equal_range(const key_type& __k);
     844             : 
     845             :       pair<const_iterator, const_iterator>
     846             :       equal_range(const key_type& __k) const;
     847             : 
     848             :       // Debugging.
     849             :       bool
     850             :       __rb_verify() const;
     851             :     };
     852             : 
     853             :   template<typename _Key, typename _Val, typename _KeyOfValue,
     854             :            typename _Compare, typename _Alloc>
     855             :     inline bool
     856             :     operator==(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
     857             :                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
     858             :     {
     859             :       return __x.size() == __y.size()
     860             :              && std::equal(__x.begin(), __x.end(), __y.begin());
     861             :     }
     862             : 
     863             :   template<typename _Key, typename _Val, typename _KeyOfValue,
     864             :            typename _Compare, typename _Alloc>
     865             :     inline bool
     866             :     operator<(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
     867             :               const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
     868             :     {
     869             :       return std::lexicographical_compare(__x.begin(), __x.end(), 
     870             :                                           __y.begin(), __y.end());
     871             :     }
     872             : 
     873             :   template<typename _Key, typename _Val, typename _KeyOfValue,
     874             :            typename _Compare, typename _Alloc>
     875             :     inline bool
     876             :     operator!=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
     877             :                const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
     878             :     { return !(__x == __y); }
     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 __y < __x; }
     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 !(__x < __y); }
     900             : 
     901             :   template<typename _Key, typename _Val, typename _KeyOfValue,
     902             :            typename _Compare, typename _Alloc>
     903             :     inline void
     904             :     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
     905             :          _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
     906             :     { __x.swap(__y); }
     907             : 
     908             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
     909             :   template<typename _Key, typename _Val, typename _KeyOfValue,
     910             :            typename _Compare, typename _Alloc>
     911       42826 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
     912             :     _Rb_tree(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&& __x)
     913       42826 :     : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
     914             :     {
     915       42826 :       if (__x._M_root() != 0)
     916             :         {
     917           0 :           _M_root() = __x._M_root();
     918           0 :           _M_leftmost() = __x._M_leftmost();
     919           0 :           _M_rightmost() = __x._M_rightmost();
     920           0 :           _M_root()->_M_parent = _M_end();
     921             : 
     922           0 :           __x._M_root() = 0;
     923           0 :           __x._M_leftmost() = __x._M_end();
     924           0 :           __x._M_rightmost() = __x._M_end();
     925             : 
     926           0 :           this->_M_impl._M_node_count = __x._M_impl._M_node_count;
     927           0 :           __x._M_impl._M_node_count = 0;
     928             :         }
     929       42826 :     }
     930             : #endif
     931             : 
     932             :   template<typename _Key, typename _Val, typename _KeyOfValue,
     933             :            typename _Compare, typename _Alloc>
     934             :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
     935      198482 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
     936             :     operator=(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x)
     937             :     {
     938      198482 :       if (this != &__x)
     939             :         {
     940             :           // Note that _Key may be a constant type.
     941      198482 :           clear();
     942             :           _M_impl._M_key_compare = __x._M_impl._M_key_compare;
     943      198482 :           if (__x._M_root() != 0)
     944             :             {
     945           0 :               _M_root() = _M_copy(__x._M_begin(), _M_end());
     946           0 :               _M_leftmost() = _S_minimum(_M_root());
     947           0 :               _M_rightmost() = _S_maximum(_M_root());
     948           0 :               _M_impl._M_node_count = __x._M_impl._M_node_count;
     949             :             }
     950             :         }
     951      198482 :       return *this;
     952             :     }
     953             : 
     954             :   template<typename _Key, typename _Val, typename _KeyOfValue,
     955             :            typename _Compare, typename _Alloc>
     956             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
     957             :     template<typename _Arg>
     958             : #endif
     959             :     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
     960      953000 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
     961             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
     962             :     _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, _Arg&& __v)
     963             : #else
     964             :     _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)
     965             : #endif
     966             :     {
     967             :       bool __insert_left = (__x != 0 || __p == _M_end()
     968             :                             || _M_impl._M_key_compare(_KeyOfValue()(__v), 
     969      953000 :                                                       _S_key(__p)));
     970             : 
     971      953000 :       _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
     972             : 
     973      953000 :       _Rb_tree_insert_and_rebalance(__insert_left, __z,
     974             :                                     const_cast<_Base_ptr>(__p),  
     975             :                                     this->_M_impl._M_header);
     976      953000 :       ++_M_impl._M_node_count;
     977      953000 :       return iterator(__z);
     978             :     }
     979             : 
     980             :   template<typename _Key, typename _Val, typename _KeyOfValue,
     981             :            typename _Compare, typename _Alloc>
     982             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
     983             :     template<typename _Arg>
     984             : #endif
     985             :     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
     986             :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
     987             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
     988             :     _M_insert_lower(_Base_ptr __x, _Base_ptr __p, _Arg&& __v)
     989             : #else
     990             :     _M_insert_lower(_Base_ptr __x, _Base_ptr __p, const _Val& __v)
     991             : #endif
     992             :     {
     993             :       bool __insert_left = (__x != 0 || __p == _M_end()
     994             :                             || !_M_impl._M_key_compare(_S_key(__p),
     995             :                                                        _KeyOfValue()(__v)));
     996             : 
     997             :       _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
     998             : 
     999             :       _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,  
    1000             :                                     this->_M_impl._M_header);
    1001             :       ++_M_impl._M_node_count;
    1002             :       return iterator(__z);
    1003             :     }
    1004             : 
    1005             :   template<typename _Key, typename _Val, typename _KeyOfValue,
    1006             :            typename _Compare, typename _Alloc>
    1007             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
    1008             :     template<typename _Arg>
    1009             : #endif
    1010             :     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
    1011             :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    1012             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
    1013             :     _M_insert_equal_lower(_Arg&& __v)
    1014             : #else
    1015             :     _M_insert_equal_lower(const _Val& __v)
    1016             : #endif
    1017             :     {
    1018             :       _Link_type __x = _M_begin();
    1019             :       _Link_type __y = _M_end();
    1020             :       while (__x != 0)
    1021             :         {
    1022             :           __y = __x;
    1023             :           __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
    1024             :                 _S_left(__x) : _S_right(__x);
    1025             :         }
    1026             :       return _M_insert_lower(__x, __y, _GLIBCXX_FORWARD(_Arg, __v));
    1027             :     }
    1028             : 
    1029             :   template<typename _Key, typename _Val, typename _KoV,
    1030             :            typename _Compare, typename _Alloc>
    1031             :     typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
    1032      113911 :     _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
    1033             :     _M_copy(_Const_Link_type __x, _Link_type __p)
    1034             :     {
    1035             :       // Structural copy.  __x and __p must be non-null.
    1036      113911 :       _Link_type __top = _M_clone_node(__x);
    1037      113911 :       __top->_M_parent = __p;
    1038             : 
    1039             :       __try
    1040             :         {
    1041      113911 :           if (__x->_M_right)
    1042       56955 :             __top->_M_right = _M_copy(_S_right(__x), __top);
    1043      113911 :           __p = __top;
    1044      113911 :           __x = _S_left(__x);
    1045             : 
    1046      212539 :           while (__x != 0)
    1047             :             {
    1048       98628 :               _Link_type __y = _M_clone_node(__x);
    1049       98628 :               __p->_M_left = __y;
    1050       98628 :               __y->_M_parent = __p;
    1051       98628 :               if (__x->_M_right)
    1052       54174 :                 __y->_M_right = _M_copy(_S_right(__x), __y);
    1053       98628 :               __p = __y;
    1054       98628 :               __x = _S_left(__x);
    1055             :             }
    1056             :         }
    1057           0 :       __catch(...)
    1058             :         {
    1059           0 :           _M_erase(__top);
    1060           0 :           __throw_exception_again;
    1061             :         }
    1062      113911 :       return __top;
    1063             :     }
    1064             : 
    1065             :   template<typename _Key, typename _Val, typename _KeyOfValue,
    1066             :            typename _Compare, typename _Alloc>
    1067             :     void
    1068     4561349 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    1069             :     _M_erase(_Link_type __x)
    1070             :     {
    1071             :       // Erase without rebalancing.
    1072     5725702 :       while (__x != 0)
    1073             :         {
    1074     1164353 :           _M_erase(_S_right(__x));
    1075     1164353 :           _Link_type __y = _S_left(__x);
    1076     1164353 :           _M_destroy_node(__x);
    1077     1164353 :           __x = __y;
    1078             :         }
    1079     4561349 :     }
    1080             : 
    1081             :   template<typename _Key, typename _Val, typename _KeyOfValue,
    1082             :            typename _Compare, typename _Alloc>
    1083             :     typename _Rb_tree<_Key, _Val, _KeyOfValue,
    1084             :                       _Compare, _Alloc>::iterator
    1085     1407911 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    1086             :     _M_lower_bound(_Link_type __x, _Link_type __y,
    1087             :                    const _Key& __k)
    1088             :     {
    1089     6305723 :       while (__x != 0)
    1090     4897812 :         if (!_M_impl._M_key_compare(_S_key(__x), __k))
    1091     1349357 :           __y = __x, __x = _S_left(__x);
    1092             :         else
    1093     3548455 :           __x = _S_right(__x);
    1094     1407911 :       return iterator(__y);
    1095             :     }
    1096             : 
    1097             :   template<typename _Key, typename _Val, typename _KeyOfValue,
    1098             :            typename _Compare, typename _Alloc>
    1099             :     typename _Rb_tree<_Key, _Val, _KeyOfValue,
    1100             :                       _Compare, _Alloc>::const_iterator
    1101      832921 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    1102             :     _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
    1103             :                    const _Key& __k) const
    1104             :     {
    1105     3745905 :       while (__x != 0)
    1106     2912984 :         if (!_M_impl._M_key_compare(_S_key(__x), __k))
    1107     1314358 :           __y = __x, __x = _S_left(__x);
    1108             :         else
    1109     1598626 :           __x = _S_right(__x);
    1110      832921 :       return const_iterator(__y);
    1111             :     }
    1112             : 
    1113             :   template<typename _Key, typename _Val, typename _KeyOfValue,
    1114             :            typename _Compare, typename _Alloc>
    1115             :     typename _Rb_tree<_Key, _Val, _KeyOfValue,
    1116             :                       _Compare, _Alloc>::iterator
    1117             :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    1118             :     _M_upper_bound(_Link_type __x, _Link_type __y,
    1119             :                    const _Key& __k)
    1120             :     {
    1121             :       while (__x != 0)
    1122             :         if (_M_impl._M_key_compare(__k, _S_key(__x)))
    1123             :           __y = __x, __x = _S_left(__x);
    1124             :         else
    1125             :           __x = _S_right(__x);
    1126             :       return iterator(__y);
    1127             :     }
    1128             : 
    1129             :   template<typename _Key, typename _Val, typename _KeyOfValue,
    1130             :            typename _Compare, typename _Alloc>
    1131             :     typename _Rb_tree<_Key, _Val, _KeyOfValue,
    1132             :                       _Compare, _Alloc>::const_iterator
    1133             :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    1134             :     _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,
    1135             :                    const _Key& __k) const
    1136             :     {
    1137             :       while (__x != 0)
    1138             :         if (_M_impl._M_key_compare(__k, _S_key(__x)))
    1139             :           __y = __x, __x = _S_left(__x);
    1140             :         else
    1141             :           __x = _S_right(__x);
    1142             :       return const_iterator(__y);
    1143             :     }
    1144             : 
    1145             :   template<typename _Key, typename _Val, typename _KeyOfValue,
    1146             :            typename _Compare, typename _Alloc>
    1147             :     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
    1148             :                            _Compare, _Alloc>::iterator,
    1149             :          typename _Rb_tree<_Key, _Val, _KeyOfValue,
    1150             :                            _Compare, _Alloc>::iterator>
    1151             :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    1152             :     equal_range(const _Key& __k)
    1153             :     {
    1154             :       _Link_type __x = _M_begin();
    1155             :       _Link_type __y = _M_end();
    1156             :       while (__x != 0)
    1157             :         {
    1158             :           if (_M_impl._M_key_compare(_S_key(__x), __k))
    1159             :             __x = _S_right(__x);
    1160             :           else if (_M_impl._M_key_compare(__k, _S_key(__x)))
    1161             :             __y = __x, __x = _S_left(__x);
    1162             :           else
    1163             :             {
    1164             :               _Link_type __xu(__x), __yu(__y);
    1165             :               __y = __x, __x = _S_left(__x);
    1166             :               __xu = _S_right(__xu);
    1167             :               return pair<iterator,
    1168             :                           iterator>(_M_lower_bound(__x, __y, __k),
    1169             :                                     _M_upper_bound(__xu, __yu, __k));
    1170             :             }
    1171             :         }
    1172             :       return pair<iterator, iterator>(iterator(__y),
    1173             :                                       iterator(__y));
    1174             :     }
    1175             : 
    1176             :   template<typename _Key, typename _Val, typename _KeyOfValue,
    1177             :            typename _Compare, typename _Alloc>
    1178             :     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
    1179             :                            _Compare, _Alloc>::const_iterator,
    1180             :          typename _Rb_tree<_Key, _Val, _KeyOfValue,
    1181             :                            _Compare, _Alloc>::const_iterator>
    1182             :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    1183             :     equal_range(const _Key& __k) const
    1184             :     {
    1185             :       _Const_Link_type __x = _M_begin();
    1186             :       _Const_Link_type __y = _M_end();
    1187             :       while (__x != 0)
    1188             :         {
    1189             :           if (_M_impl._M_key_compare(_S_key(__x), __k))
    1190             :             __x = _S_right(__x);
    1191             :           else if (_M_impl._M_key_compare(__k, _S_key(__x)))
    1192             :             __y = __x, __x = _S_left(__x);
    1193             :           else
    1194             :             {
    1195             :               _Const_Link_type __xu(__x), __yu(__y);
    1196             :               __y = __x, __x = _S_left(__x);
    1197             :               __xu = _S_right(__xu);
    1198             :               return pair<const_iterator,
    1199             :                           const_iterator>(_M_lower_bound(__x, __y, __k),
    1200             :                                           _M_upper_bound(__xu, __yu, __k));
    1201             :             }
    1202             :         }
    1203             :       return pair<const_iterator, const_iterator>(const_iterator(__y),
    1204             :                                                   const_iterator(__y));
    1205             :     }
    1206             : 
    1207             :   template<typename _Key, typename _Val, typename _KeyOfValue,
    1208             :            typename _Compare, typename _Alloc>
    1209             :     void
    1210      598131 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    1211             :     swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __t)
    1212             :     {
    1213      598131 :       if (_M_root() == 0)
    1214             :         {
    1215      598131 :           if (__t._M_root() != 0)
    1216             :             {
    1217           2 :               _M_root() = __t._M_root();
    1218           2 :               _M_leftmost() = __t._M_leftmost();
    1219           2 :               _M_rightmost() = __t._M_rightmost();
    1220           2 :               _M_root()->_M_parent = _M_end();
    1221             :               
    1222           2 :               __t._M_root() = 0;
    1223           2 :               __t._M_leftmost() = __t._M_end();
    1224           2 :               __t._M_rightmost() = __t._M_end();
    1225             :             }
    1226             :         }
    1227           0 :       else if (__t._M_root() == 0)
    1228             :         {
    1229           0 :           __t._M_root() = _M_root();
    1230           0 :           __t._M_leftmost() = _M_leftmost();
    1231           0 :           __t._M_rightmost() = _M_rightmost();
    1232           0 :           __t._M_root()->_M_parent = __t._M_end();
    1233             :           
    1234           0 :           _M_root() = 0;
    1235           0 :           _M_leftmost() = _M_end();
    1236           0 :           _M_rightmost() = _M_end();
    1237             :         }
    1238             :       else
    1239             :         {
    1240           0 :           std::swap(_M_root(),__t._M_root());
    1241           0 :           std::swap(_M_leftmost(),__t._M_leftmost());
    1242           0 :           std::swap(_M_rightmost(),__t._M_rightmost());
    1243             :           
    1244           0 :           _M_root()->_M_parent = _M_end();
    1245           0 :           __t._M_root()->_M_parent = __t._M_end();
    1246             :         }
    1247             :       // No need to swap header's color as it does not change.
    1248      598131 :       std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
    1249      598131 :       std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
    1250             :       
    1251             :       // _GLIBCXX_RESOLVE_LIB_DEFECTS
    1252             :       // 431. Swapping containers with unequal allocators.
    1253      598131 :       std::__alloc_swap<_Node_allocator>::
    1254             :         _S_do_it(_M_get_Node_allocator(), __t._M_get_Node_allocator());
    1255      598131 :     }
    1256             : 
    1257             :   template<typename _Key, typename _Val, typename _KeyOfValue,
    1258             :            typename _Compare, typename _Alloc>
    1259             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
    1260             :     template<typename _Arg>
    1261             : #endif
    1262             :     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
    1263             :                            _Compare, _Alloc>::iterator, bool>
    1264       77251 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    1265             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
    1266             :     _M_insert_unique(_Arg&& __v)
    1267             : #else
    1268             :     _M_insert_unique(const _Val& __v)
    1269             : #endif
    1270             :     {
    1271       77251 :       _Link_type __x = _M_begin();
    1272       77251 :       _Link_type __y = _M_end();
    1273       77251 :       bool __comp = true;
    1274       77251 :       while (__x != 0)
    1275             :         {
    1276           0 :           __y = __x;
    1277           0 :           __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
    1278           0 :           __x = __comp ? _S_left(__x) : _S_right(__x);
    1279             :         }
    1280       77251 :       iterator __j = iterator(__y);
    1281       77251 :       if (__comp)
    1282             :         {
    1283       77251 :           if (__j == begin())
    1284             :             return pair<iterator, bool>
    1285       77251 :               (_M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)), true);
    1286             :           else
    1287           0 :             --__j;
    1288             :         }
    1289           0 :       if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
    1290             :         return pair<iterator, bool>
    1291           0 :           (_M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v)), true);
    1292       77251 :       return pair<iterator, bool>(__j, false);
    1293             :     }
    1294             : 
    1295             :   template<typename _Key, typename _Val, typename _KeyOfValue,
    1296             :            typename _Compare, typename _Alloc>
    1297             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
    1298             :     template<typename _Arg>
    1299             : #endif
    1300             :     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
    1301             :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    1302             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
    1303             :     _M_insert_equal(_Arg&& __v)
    1304             : #else
    1305             :     _M_insert_equal(const _Val& __v)
    1306             : #endif
    1307             :     {
    1308             :       _Link_type __x = _M_begin();
    1309             :       _Link_type __y = _M_end();
    1310             :       while (__x != 0)
    1311             :         {
    1312             :           __y = __x;
    1313             :           __x = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
    1314             :                 _S_left(__x) : _S_right(__x);
    1315             :         }
    1316             :       return _M_insert_(__x, __y, _GLIBCXX_FORWARD(_Arg, __v));
    1317             :     }
    1318             : 
    1319             :   template<typename _Key, typename _Val, typename _KeyOfValue,
    1320             :            typename _Compare, typename _Alloc>
    1321             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
    1322             :     template<typename _Arg>
    1323             : #endif
    1324             :     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
    1325      953000 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    1326             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
    1327             :     _M_insert_unique_(const_iterator __position, _Arg&& __v)
    1328             : #else
    1329             :     _M_insert_unique_(const_iterator __position, const _Val& __v)
    1330             : #endif
    1331             :     {
    1332             :       // end()
    1333      953000 :       if (__position._M_node == _M_end())
    1334             :         {
    1335      378727 :           if (size() > 0
    1336             :               && _M_impl._M_key_compare(_S_key(_M_rightmost()), 
    1337             :                                         _KeyOfValue()(__v)))
    1338      301476 :             return _M_insert_(0, _M_rightmost(), _GLIBCXX_FORWARD(_Arg, __v));
    1339             :           else
    1340       77251 :             return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first;
    1341             :         }
    1342      574273 :       else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
    1343             :                                       _S_key(__position._M_node)))
    1344             :         {
    1345             :           // First, try before...
    1346      574273 :           const_iterator __before = __position;
    1347      574273 :           if (__position._M_node == _M_leftmost()) // begin()
    1348             :             return _M_insert_(_M_leftmost(), _M_leftmost(),
    1349       64605 :                               _GLIBCXX_FORWARD(_Arg, __v));
    1350      509668 :           else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), 
    1351             :                                           _KeyOfValue()(__v)))
    1352             :             {
    1353      509668 :               if (_S_right(__before._M_node) == 0)
    1354             :                 return _M_insert_(0, __before._M_node,
    1355      368861 :                                   _GLIBCXX_FORWARD(_Arg, __v));
    1356             :               else
    1357             :                 return _M_insert_(__position._M_node,
    1358             :                                   __position._M_node,
    1359      140807 :                                   _GLIBCXX_FORWARD(_Arg, __v));
    1360             :             }
    1361             :           else
    1362           0 :             return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first;
    1363             :         }
    1364           0 :       else if (_M_impl._M_key_compare(_S_key(__position._M_node),
    1365             :                                       _KeyOfValue()(__v)))
    1366             :         {
    1367             :           // ... then try after.
    1368           0 :           const_iterator __after = __position;
    1369           0 :           if (__position._M_node == _M_rightmost())
    1370             :             return _M_insert_(0, _M_rightmost(),
    1371           0 :                               _GLIBCXX_FORWARD(_Arg, __v));
    1372           0 :           else if (_M_impl._M_key_compare(_KeyOfValue()(__v),
    1373             :                                           _S_key((++__after)._M_node)))
    1374             :             {
    1375           0 :               if (_S_right(__position._M_node) == 0)
    1376             :                 return _M_insert_(0, __position._M_node,
    1377           0 :                                   _GLIBCXX_FORWARD(_Arg, __v));
    1378             :               else
    1379             :                 return _M_insert_(__after._M_node, __after._M_node,
    1380           0 :                                   _GLIBCXX_FORWARD(_Arg, __v));
    1381             :             }
    1382             :           else
    1383           0 :             return _M_insert_unique(_GLIBCXX_FORWARD(_Arg, __v)).first;
    1384             :         }
    1385             :       else
    1386             :         // Equivalent keys.
    1387      953000 :         return __position._M_const_cast();
    1388             :     }
    1389             : 
    1390             :   template<typename _Key, typename _Val, typename _KeyOfValue,
    1391             :            typename _Compare, typename _Alloc>
    1392             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
    1393             :     template<typename _Arg>
    1394             : #endif
    1395             :     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
    1396             :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    1397             : #ifdef __GXX_EXPERIMENTAL_CXX0X__
    1398             :     _M_insert_equal_(const_iterator __position, _Arg&& __v)
    1399             : #else
    1400             :     _M_insert_equal_(const_iterator __position, const _Val& __v)
    1401             : #endif
    1402             :     {
    1403             :       // end()
    1404             :       if (__position._M_node == _M_end())
    1405             :         {
    1406             :           if (size() > 0
    1407             :               && !_M_impl._M_key_compare(_KeyOfValue()(__v),
    1408             :                                          _S_key(_M_rightmost())))
    1409             :             return _M_insert_(0, _M_rightmost(),
    1410             :                               _GLIBCXX_FORWARD(_Arg, __v));
    1411             :           else
    1412             :             return _M_insert_equal(_GLIBCXX_FORWARD(_Arg, __v));
    1413             :         }
    1414             :       else if (!_M_impl._M_key_compare(_S_key(__position._M_node),
    1415             :                                        _KeyOfValue()(__v)))
    1416             :         {
    1417             :           // First, try before...
    1418             :           const_iterator __before = __position;
    1419             :           if (__position._M_node == _M_leftmost()) // begin()
    1420             :             return _M_insert_(_M_leftmost(), _M_leftmost(),
    1421             :                               _GLIBCXX_FORWARD(_Arg, __v));
    1422             :           else if (!_M_impl._M_key_compare(_KeyOfValue()(__v),
    1423             :                                            _S_key((--__before)._M_node)))
    1424             :             {
    1425             :               if (_S_right(__before._M_node) == 0)
    1426             :                 return _M_insert_(0, __before._M_node,
    1427             :                                   _GLIBCXX_FORWARD(_Arg, __v));
    1428             :               else
    1429             :                 return _M_insert_(__position._M_node,
    1430             :                                   __position._M_node,
    1431             :                                   _GLIBCXX_FORWARD(_Arg, __v));
    1432             :             }
    1433             :           else
    1434             :             return _M_insert_equal(_GLIBCXX_FORWARD(_Arg, __v));
    1435             :         }
    1436             :       else
    1437             :         {
    1438             :           // ... then try after.  
    1439             :           const_iterator __after = __position;
    1440             :           if (__position._M_node == _M_rightmost())
    1441             :             return _M_insert_(0, _M_rightmost(),
    1442             :                               _GLIBCXX_FORWARD(_Arg, __v));
    1443             :           else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node),
    1444             :                                            _KeyOfValue()(__v)))
    1445             :             {
    1446             :               if (_S_right(__position._M_node) == 0)
    1447             :                 return _M_insert_(0, __position._M_node,
    1448             :                                   _GLIBCXX_FORWARD(_Arg, __v));
    1449             :               else
    1450             :                 return _M_insert_(__after._M_node, __after._M_node,
    1451             :                                   _GLIBCXX_FORWARD(_Arg, __v));
    1452             :             }
    1453             :           else
    1454             :             return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
    1455             :         }
    1456             :     }
    1457             : 
    1458             :   template<typename _Key, typename _Val, typename _KoV,
    1459             :            typename _Cmp, typename _Alloc>
    1460             :     template<class _II>
    1461             :       void
    1462             :       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
    1463             :       _M_insert_unique(_II __first, _II __last)
    1464             :       {
    1465             :         for (; __first != __last; ++__first)
    1466             :           _M_insert_unique_(end(), *__first);
    1467             :       }
    1468             : 
    1469             :   template<typename _Key, typename _Val, typename _KoV,
    1470             :            typename _Cmp, typename _Alloc>
    1471             :     template<class _II>
    1472             :       void
    1473             :       _Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
    1474             :       _M_insert_equal(_II __first, _II __last)
    1475             :       {
    1476             :         for (; __first != __last; ++__first)
    1477             :           _M_insert_equal_(end(), *__first);
    1478             :       }
    1479             : 
    1480             :   template<typename _Key, typename _Val, typename _KeyOfValue,
    1481             :            typename _Compare, typename _Alloc>
    1482             :     void
    1483         436 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    1484             :     _M_erase_aux(const_iterator __position)
    1485             :     {
    1486             :       _Link_type __y =
    1487             :         static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
    1488             :                                 (const_cast<_Base_ptr>(__position._M_node),
    1489         436 :                                  this->_M_impl._M_header));
    1490         436 :       _M_destroy_node(__y);
    1491         436 :       --_M_impl._M_node_count;
    1492         436 :     }
    1493             : 
    1494             :   template<typename _Key, typename _Val, typename _KeyOfValue,
    1495             :            typename _Compare, typename _Alloc>
    1496             :     void
    1497             :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    1498             :     _M_erase_aux(const_iterator __first, const_iterator __last)
    1499             :     {
    1500             :       if (__first == begin() && __last == end())
    1501             :         clear();
    1502             :       else
    1503             :         while (__first != __last)
    1504             :           erase(__first++);
    1505             :     }
    1506             : 
    1507             :   template<typename _Key, typename _Val, typename _KeyOfValue,
    1508             :            typename _Compare, typename _Alloc>
    1509             :     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
    1510             :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    1511             :     erase(const _Key& __x)
    1512             :     {
    1513             :       pair<iterator, iterator> __p = equal_range(__x);
    1514             :       const size_type __old_size = size();
    1515             :       erase(__p.first, __p.second);
    1516             :       return __old_size - size();
    1517             :     }
    1518             : 
    1519             :   template<typename _Key, typename _Val, typename _KeyOfValue,
    1520             :            typename _Compare, typename _Alloc>
    1521             :     void
    1522             :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    1523             :     erase(const _Key* __first, const _Key* __last)
    1524             :     {
    1525             :       while (__first != __last)
    1526             :         erase(*__first++);
    1527             :     }
    1528             : 
    1529             :   template<typename _Key, typename _Val, typename _KeyOfValue,
    1530             :            typename _Compare, typename _Alloc>
    1531             :     typename _Rb_tree<_Key, _Val, _KeyOfValue,
    1532             :                       _Compare, _Alloc>::iterator
    1533      352368 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    1534             :     find(const _Key& __k)
    1535             :     {
    1536      352368 :       iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
    1537             :       return (__j == end()
    1538             :               || _M_impl._M_key_compare(__k,
    1539      352368 :                                         _S_key(__j._M_node))) ? end() : __j;
    1540             :     }
    1541             : 
    1542             :   template<typename _Key, typename _Val, typename _KeyOfValue,
    1543             :            typename _Compare, typename _Alloc>
    1544             :     typename _Rb_tree<_Key, _Val, _KeyOfValue,
    1545             :                       _Compare, _Alloc>::const_iterator
    1546      832921 :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    1547             :     find(const _Key& __k) const
    1548             :     {
    1549      832921 :       const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
    1550             :       return (__j == end()
    1551             :               || _M_impl._M_key_compare(__k, 
    1552      832921 :                                         _S_key(__j._M_node))) ? end() : __j;
    1553             :     }
    1554             : 
    1555             :   template<typename _Key, typename _Val, typename _KeyOfValue,
    1556             :            typename _Compare, typename _Alloc>
    1557             :     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
    1558             :     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    1559             :     count(const _Key& __k) const
    1560             :     {
    1561             :       pair<const_iterator, const_iterator> __p = equal_range(__k);
    1562             :       const size_type __n = std::distance(__p.first, __p.second);
    1563             :       return __n;
    1564             :     }
    1565             : 
    1566             :   _GLIBCXX_PURE unsigned int
    1567             :   _Rb_tree_black_count(const _Rb_tree_node_base* __node,
    1568             :                        const _Rb_tree_node_base* __root) throw ();
    1569             : 
    1570             :   template<typename _Key, typename _Val, typename _KeyOfValue,
    1571             :            typename _Compare, typename _Alloc>
    1572             :     bool
    1573             :     _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
    1574             :     {
    1575             :       if (_M_impl._M_node_count == 0 || begin() == end())
    1576             :         return _M_impl._M_node_count == 0 && begin() == end()
    1577             :                && this->_M_impl._M_header._M_left == _M_end()
    1578             :                && this->_M_impl._M_header._M_right == _M_end();
    1579             : 
    1580             :       unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
    1581             :       for (const_iterator __it = begin(); __it != end(); ++__it)
    1582             :         {
    1583             :           _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
    1584             :           _Const_Link_type __L = _S_left(__x);
    1585             :           _Const_Link_type __R = _S_right(__x);
    1586             : 
    1587             :           if (__x->_M_color == _S_red)
    1588             :             if ((__L && __L->_M_color == _S_red)
    1589             :                 || (__R && __R->_M_color == _S_red))
    1590             :               return false;
    1591             : 
    1592             :           if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
    1593             :             return false;
    1594             :           if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
    1595             :             return false;
    1596             : 
    1597             :           if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
    1598             :             return false;
    1599             :         }
    1600             : 
    1601             :       if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
    1602             :         return false;
    1603             :       if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
    1604             :         return false;
    1605             :       return true;
    1606             :     }
    1607             : 
    1608             : _GLIBCXX_END_NAMESPACE_VERSION
    1609             : } // namespace
    1610             : 
    1611             : #endif

Generated by: LCOV version 1.9

The wpkg tool is an open source tool created by Made to Order Software Corporation.