Subversion Repositories openrisc

// RB tree implementation -*- C++ -*-

// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009

// Free Software Foundation, Inc.

//

// This file is part of the GNU ISO C++ Library.  This library is free

// software; you can redistribute it and/or modify it under the

// terms of the GNU General Public License as published by the

// Free Software Foundation; either version 3, or (at your option)

// any later version.

// This library is distributed in the hope that it will be useful,

// but WITHOUT ANY WARRANTY; without even the implied warranty of

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional

// permissions described in the GCC Runtime Library Exception, version

// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and

// a copy of the GCC Runtime Library Exception along with this program;

// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see

// <http://www.gnu.org/licenses/>.

/*

 *

 * Copyright (c) 1996,1997

 * Silicon Graphics Computer Systems, Inc.

 *

 * Permission to use, copy, modify, distribute and sell this software

 * and its documentation for any purpose is hereby granted without fee,

 * provided that the above copyright notice appear in all copies and

 * that both that copyright notice and this permission notice appear

 * in supporting documentation.  Silicon Graphics makes no

 * representations about the suitability of this software for any

 * purpose.  It is provided "as is" without express or implied warranty.

 *

 *

 * Copyright (c) 1994

 * Hewlett-Packard Company

 *

 * Permission to use, copy, modify, distribute and sell this software

 * and its documentation for any purpose is hereby granted without fee,

 * provided that the above copyright notice appear in all copies and

 * that both that copyright notice and this permission notice appear

 * in supporting documentation.  Hewlett-Packard Company makes no

 * representations about the suitability of this software for any

 * purpose.  It is provided "as is" without express or implied warranty.

 *

 *

 */

/** @file stl_tree.h

 *  This is an internal header file, included by other library headers.

 *  You should not attempt to use it directly.

 */

#ifndef _STL_TREE_H

#define _STL_TREE_H 1

#include <bits/stl_algobase.h>

#include <bits/allocator.h>

#include <bits/stl_function.h>

#include <bits/cpp_type_traits.h>

_GLIBCXX_BEGIN_NAMESPACE(std)

  // Red-black tree class, designed for use in implementing STL

  // associative containers (set, multiset, map, and multimap). The

  // insertion and deletion algorithms are based on those in Cormen,

  // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,

  // 1990), except that

  //

  // (1) the header cell is maintained with links not only to the root

  // but also to the leftmost node of the tree, to enable constant

  // time begin(), and to the rightmost node of the tree, to enable

  // linear time performance when used with the generic set algorithms

  // (set_union, etc.)

  // 

  // (2) when a node being deleted has two children its successor node

  // is relinked into its place, rather than copied, so that the only

  // iterators invalidated are those referring to the deleted node.

  enum _Rb_tree_color { _S_red = false, _S_black = true };

  struct _Rb_tree_node_base

  {

    typedef _Rb_tree_node_base* _Base_ptr;

    typedef const _Rb_tree_node_base* _Const_Base_ptr;

    _Rb_tree_color      _M_color;

    _Base_ptr           _M_parent;

    _Base_ptr           _M_left;

    _Base_ptr           _M_right;

    static _Base_ptr

    _S_minimum(_Base_ptr __x)

    {

      while (__x->_M_left != 0) __x = __x->_M_left;

      return __x;

    }

    static _Const_Base_ptr

    _S_minimum(_Const_Base_ptr __x)

    {

      while (__x->_M_left != 0) __x = __x->_M_left;

      return __x;

    }

    static _Base_ptr

    _S_maximum(_Base_ptr __x)

    {

      while (__x->_M_right != 0) __x = __x->_M_right;

      return __x;

    }

    static _Const_Base_ptr

    _S_maximum(_Const_Base_ptr __x)

    {

      while (__x->_M_right != 0) __x = __x->_M_right;

      return __x;

    }

  };

  template<typename _Val>

    struct _Rb_tree_node : public _Rb_tree_node_base

    {

      typedef _Rb_tree_node<_Val>* _Link_type;

      _Val _M_value_field;

#ifdef __GXX_EXPERIMENTAL_CXX0X__

      template<typename... _Args>

        _Rb_tree_node(_Args&&... __args)

        : _Rb_tree_node_base(),

          _M_value_field(std::forward<_Args>(__args)...) { }

#endif

    };

  _GLIBCXX_PURE _Rb_tree_node_base*

  _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();

  _GLIBCXX_PURE const _Rb_tree_node_base*

  _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ();

  _GLIBCXX_PURE _Rb_tree_node_base*

  _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();

  _GLIBCXX_PURE const _Rb_tree_node_base*

  _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();

  template<typename _Tp>

    struct _Rb_tree_iterator

    {

      typedef _Tp  value_type;

      typedef _Tp& reference;

      typedef _Tp* pointer;

      typedef bidirectional_iterator_tag iterator_category;

      typedef ptrdiff_t                  difference_type;

      typedef _Rb_tree_iterator<_Tp>        _Self;

      typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;

      typedef _Rb_tree_node<_Tp>*           _Link_type;

      _Rb_tree_iterator()

      : _M_node() { }

      explicit

      _Rb_tree_iterator(_Link_type __x)

      : _M_node(__x) { }

      reference

      operator*() const

      { return static_cast<_Link_type>(_M_node)->_M_value_field; }

      pointer

      operator->() const

      { return &static_cast<_Link_type>(_M_node)->_M_value_field; }

      _Self&

      operator++()

      {

        _M_node = _Rb_tree_increment(_M_node);

        return *this;

      }

      _Self

      operator++(int)

      {

        _Self __tmp = *this;

        _M_node = _Rb_tree_increment(_M_node);

        return __tmp;

      }

      _Self&

      operator--()

      {

        _M_node = _Rb_tree_decrement(_M_node);

        return *this;

      }

      _Self

      operator--(int)

      {

        _Self __tmp = *this;

        _M_node = _Rb_tree_decrement(_M_node);

        return __tmp;

      }

      bool

      operator==(const _Self& __x) const

      { return _M_node == __x._M_node; }

      bool

      operator!=(const _Self& __x) const

      { return _M_node != __x._M_node; }

      _Base_ptr _M_node;

  };

  template<typename _Tp>

    struct _Rb_tree_const_iterator

    {

      typedef _Tp        value_type;

      typedef const _Tp& reference;

      typedef const _Tp* pointer;

      typedef _Rb_tree_iterator<_Tp> iterator;

      typedef bidirectional_iterator_tag iterator_category;

      typedef ptrdiff_t                  difference_type;

      typedef _Rb_tree_const_iterator<_Tp>        _Self;

      typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;

      typedef const _Rb_tree_node<_Tp>*           _Link_type;

      _Rb_tree_const_iterator()

      : _M_node() { }

      explicit

      _Rb_tree_const_iterator(_Link_type __x)

      : _M_node(__x) { }

      _Rb_tree_const_iterator(const iterator& __it)

      : _M_node(__it._M_node) { }

      reference

      operator*() const

      { return static_cast<_Link_type>(_M_node)->_M_value_field; }

      pointer

      operator->() const

      { return &static_cast<_Link_type>(_M_node)->_M_value_field; }

      _Self&

      operator++()

      {

        _M_node = _Rb_tree_increment(_M_node);

        return *this;

      }

      _Self

      operator++(int)

      {

        _Self __tmp = *this;

        _M_node = _Rb_tree_increment(_M_node);

        return __tmp;

      }

      _Self&

      operator--()

      {

        _M_node = _Rb_tree_decrement(_M_node);

        return *this;

      }

      _Self

      operator--(int)

      {

        _Self __tmp = *this;

        _M_node = _Rb_tree_decrement(_M_node);

        return __tmp;

      }

      bool

      operator==(const _Self& __x) const

      { return _M_node == __x._M_node; }

      bool

      operator!=(const _Self& __x) const

      { return _M_node != __x._M_node; }

      _Base_ptr _M_node;

    };

  template<typename _Val>

    inline bool

    operator==(const _Rb_tree_iterator<_Val>& __x,

               const _Rb_tree_const_iterator<_Val>& __y)

    { return __x._M_node == __y._M_node; }

  template<typename _Val>

    inline bool

    operator!=(const _Rb_tree_iterator<_Val>& __x,

               const _Rb_tree_const_iterator<_Val>& __y)

    { return __x._M_node != __y._M_node; }

  void

  _Rb_tree_insert_and_rebalance(const bool __insert_left,

                                _Rb_tree_node_base* __x,

                                _Rb_tree_node_base* __p,

                                _Rb_tree_node_base& __header) throw ();

  _Rb_tree_node_base*

  _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,

                               _Rb_tree_node_base& __header) throw ();

  template<typename _Key, typename _Val, typename _KeyOfValue,

           typename _Compare, typename _Alloc = allocator<_Val> >

    class _Rb_tree

    {

      typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other

              _Node_allocator;

    protected:

      typedef _Rb_tree_node_base* _Base_ptr;

      typedef const _Rb_tree_node_base* _Const_Base_ptr;

    public:

      typedef _Key key_type;

      typedef _Val value_type;

      typedef value_type* pointer;

      typedef const value_type* const_pointer;

      typedef value_type& reference;

      typedef const value_type& const_reference;

      typedef _Rb_tree_node<_Val>* _Link_type;

      typedef const _Rb_tree_node<_Val>* _Const_Link_type;

      typedef size_t size_type;

      typedef ptrdiff_t difference_type;

      typedef _Alloc allocator_type;

      _Node_allocator&

      _M_get_Node_allocator()

      { return *static_cast<_Node_allocator*>(&this->_M_impl); }

      const _Node_allocator&

      _M_get_Node_allocator() const

      { return *static_cast<const _Node_allocator*>(&this->_M_impl); }

      allocator_type

      get_allocator() const

      { return allocator_type(_M_get_Node_allocator()); }

    protected:

      _Link_type

      _M_get_node()

      { return _M_impl._Node_allocator::allocate(1); }

      void

      _M_put_node(_Link_type __p)

      { _M_impl._Node_allocator::deallocate(__p, 1); }

#ifndef __GXX_EXPERIMENTAL_CXX0X__

      _Link_type

      _M_create_node(const value_type& __x)

      {

        _Link_type __tmp = _M_get_node();

        __try

          { get_allocator().construct(&__tmp->_M_value_field, __x); }

        __catch(...)

          {

            _M_put_node(__tmp);

            __throw_exception_again;

          }

        return __tmp;

      }

      void

      _M_destroy_node(_Link_type __p)

      {

        get_allocator().destroy(&__p->_M_value_field);

        _M_put_node(__p);

      }

#else

      template<typename... _Args>

        _Link_type

        _M_create_node(_Args&&... __args)

        {

          _Link_type __tmp = _M_get_node();

          __try

            {

              _M_get_Node_allocator().construct(__tmp,

                                             std::forward<_Args>(__args)...);

            }

          __catch(...)

            {

              _M_put_node(__tmp);

              __throw_exception_again;

            }

          return __tmp;

        }

      void

      _M_destroy_node(_Link_type __p)

      {

        _M_get_Node_allocator().destroy(__p);

        _M_put_node(__p);

      }

#endif

      _Link_type

      _M_clone_node(_Const_Link_type __x)

      {

        _Link_type __tmp = _M_create_node(__x->_M_value_field);

        __tmp->_M_color = __x->_M_color;

        __tmp->_M_left = 0;

        __tmp->_M_right = 0;

        return __tmp;

      }

    protected:

      template<typename _Key_compare,

               bool _Is_pod_comparator = __is_pod(_Key_compare)>

        struct _Rb_tree_impl : public _Node_allocator

        {

          _Key_compare          _M_key_compare;

          _Rb_tree_node_base    _M_header;

          size_type             _M_node_count; // Keeps track of size of tree.

          _Rb_tree_impl()

          : _Node_allocator(), _M_key_compare(), _M_header(),

            _M_node_count(0)

          { _M_initialize(); }

          _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)

          : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),

            _M_node_count(0)

          { _M_initialize(); }

        private:

          void

          _M_initialize()

          {

            this->_M_header._M_color = _S_red;

            this->_M_header._M_parent = 0;

            this->_M_header._M_left = &this->_M_header;

            this->_M_header._M_right = &this->_M_header;

          }

        };

      _Rb_tree_impl<_Compare> _M_impl;

    protected:

      _Base_ptr&

      _M_root()

      { return this->_M_impl._M_header._M_parent; }

      _Const_Base_ptr

      _M_root() const

      { return this->_M_impl._M_header._M_parent; }

      _Base_ptr&

      _M_leftmost()

      { return this->_M_impl._M_header._M_left; }

      _Const_Base_ptr

      _M_leftmost() const

      { return this->_M_impl._M_header._M_left; }

      _Base_ptr&

      _M_rightmost()

      { return this->_M_impl._M_header._M_right; }

      _Const_Base_ptr

      _M_rightmost() const

      { return this->_M_impl._M_header._M_right; }

      _Link_type

      _M_begin()

      { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }

      _Const_Link_type

      _M_begin() const

      {

        return static_cast<_Const_Link_type>

          (this->_M_impl._M_header._M_parent);

      }

      _Link_type

      _M_end()

      { return static_cast<_Link_type>(&this->_M_impl._M_header); }

      _Const_Link_type

      _M_end() const

      { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }

      static const_reference

      _S_value(_Const_Link_type __x)

      { return __x->_M_value_field; }

      static const _Key&

      _S_key(_Const_Link_type __x)

      { return _KeyOfValue()(_S_value(__x)); }

      static _Link_type

      _S_left(_Base_ptr __x)

      { return static_cast<_Link_type>(__x->_M_left); }

      static _Const_Link_type

      _S_left(_Const_Base_ptr __x)

      { return static_cast<_Const_Link_type>(__x->_M_left); }

      static _Link_type

      _S_right(_Base_ptr __x)

      { return static_cast<_Link_type>(__x->_M_right); }

      static _Const_Link_type

      _S_right(_Const_Base_ptr __x)

      { return static_cast<_Const_Link_type>(__x->_M_right); }

      static const_reference

      _S_value(_Const_Base_ptr __x)

      { return static_cast<_Const_Link_type>(__x)->_M_value_field; }

      static const _Key&

      _S_key(_Const_Base_ptr __x)

      { return _KeyOfValue()(_S_value(__x)); }

      static _Base_ptr

      _S_minimum(_Base_ptr __x)

      { return _Rb_tree_node_base::_S_minimum(__x); }

      static _Const_Base_ptr

      _S_minimum(_Const_Base_ptr __x)

      { return _Rb_tree_node_base::_S_minimum(__x); }

      static _Base_ptr

      _S_maximum(_Base_ptr __x)

      { return _Rb_tree_node_base::_S_maximum(__x); }

      static _Const_Base_ptr

      _S_maximum(_Const_Base_ptr __x)

      { return _Rb_tree_node_base::_S_maximum(__x); }

    public:

      typedef _Rb_tree_iterator<value_type>       iterator;

      typedef _Rb_tree_const_iterator<value_type> const_iterator;

      typedef std::reverse_iterator<iterator>       reverse_iterator;

      typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    private:

      iterator

      _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y,

                 const value_type& __v);

      // _GLIBCXX_RESOLVE_LIB_DEFECTS

      // 233. Insertion hints in associative containers.

      iterator

      _M_insert_lower(_Base_ptr __x, _Base_ptr __y, const value_type& __v);

      iterator

      _M_insert_equal_lower(const value_type& __x);

      _Link_type

      _M_copy(_Const_Link_type __x, _Link_type __p);

      void

      _M_erase(_Link_type __x);

      iterator

      _M_lower_bound(_Link_type __x, _Link_type __y,

                     const _Key& __k);

      const_iterator

      _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,

                     const _Key& __k) const;

      iterator

      _M_upper_bound(_Link_type __x, _Link_type __y,

                     const _Key& __k);

      const_iterator

      _M_upper_bound(_Const_Link_type __x, _Const_Link_type __y,

                     const _Key& __k) const;

    public:

      // allocation/deallocation

      _Rb_tree() { }

      _Rb_tree(const _Compare& __comp,

               const allocator_type& __a = allocator_type())

      : _M_impl(__comp, __a) { }

      _Rb_tree(const _Rb_tree& __x)

      : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())

      {

        if (__x._M_root() != 0)

          {

            _M_root() = _M_copy(__x._M_begin(), _M_end());

            _M_leftmost() = _S_minimum(_M_root());

            _M_rightmost() = _S_maximum(_M_root());

            _M_impl._M_node_count = __x._M_impl._M_node_count;

          }

      }

#ifdef __GXX_EXPERIMENTAL_CXX0X__

      _Rb_tree(_Rb_tree&& __x);

#endif

      ~_Rb_tree()

      { _M_erase(_M_begin()); }

      _Rb_tree&

      operator=(const _Rb_tree& __x);

      // Accessors.

      _Compare

      key_comp() const

      { return _M_impl._M_key_compare; }

      iterator

      begin()

      {

        return iterator(static_cast<_Link_type>

                        (this->_M_impl._M_header._M_left));

      }

      const_iterator

      begin() const

      {

        return const_iterator(static_cast<_Const_Link_type>

                              (this->_M_impl._M_header._M_left));

      }

      iterator

      end()

      { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }

      const_iterator

      end() const

      {

        return const_iterator(static_cast<_Const_Link_type>

                              (&this->_M_impl._M_header));

      }

      reverse_iterator

      rbegin()

      { return reverse_iterator(end()); }

      const_reverse_iterator

      rbegin() const

      { return const_reverse_iterator(end()); }

      reverse_iterator

      rend()

      { return reverse_iterator(begin()); }

      const_reverse_iterator

      rend() const

      { return const_reverse_iterator(begin()); }

      bool

      empty() const

      { return _M_impl._M_node_count == 0; }

      size_type

      size() const

      { return _M_impl._M_node_count; }

      size_type

      max_size() const

      { return _M_get_Node_allocator().max_size(); }

      void

      swap(_Rb_tree& __t);

      // Insert/erase.

      pair<iterator, bool>

      _M_insert_unique(const value_type& __x);

      iterator

      _M_insert_equal(const value_type& __x);

      iterator

      _M_insert_unique_(const_iterator __position, const value_type& __x);

      iterator

      _M_insert_equal_(const_iterator __position, const value_type& __x);

      template<typename _InputIterator>

        void

        _M_insert_unique(_InputIterator __first, _InputIterator __last);

      template<typename _InputIterator>

        void

        _M_insert_equal(_InputIterator __first, _InputIterator __last);

#ifdef __GXX_EXPERIMENTAL_CXX0X__

      // _GLIBCXX_RESOLVE_LIB_DEFECTS

      // DR 130. Associative erase should return an iterator.

      iterator

      erase(iterator __position);

      // _GLIBCXX_RESOLVE_LIB_DEFECTS

      // DR 130. Associative erase should return an iterator.

      const_iterator

      erase(const_iterator __position);

#else

      void

      erase(iterator __position);

      void

      erase(const_iterator __position);

#endif

      size_type

      erase(const key_type& __x);

#ifdef __GXX_EXPERIMENTAL_CXX0X__

      // _GLIBCXX_RESOLVE_LIB_DEFECTS