_tree.h

realview22.rar

/***************************************************************************
 *
 * _tree.h - Declarations for the Standard Library tree classes
 *
 * This is an internal header file used to implement the C++ Standard
 * Library. It should never be #included directly by a program.
 *
 * $Id: _tree.h,v 1.2 2002/01/11 09:12:13 vkorstan Exp $
 *
 ***************************************************************************
 *
 * 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.
 *
 ***************************************************************************
 *
 * Copyright (c) 1994-2001 Rogue Wave Software, Inc.  All Rights Reserved.
 *
 * This computer software is owned by Rogue Wave Software, Inc. and is
 * protected by U.S. copyright laws and other laws and by international
 * treaties.  This computer software is furnished by Rogue Wave Software,
 * Inc. pursuant to a written license agreement and may be used, copied,
 * transmitted, and stored only in accordance with the terms of such
 * license and with the inclusion of the above copyright notice.  This
 * computer software or any other copies thereof may not be provided or
 * otherwise made available to any other person.
 *
 * U.S. Government Restricted Rights.  This computer software is provided
 * with Restricted Rights.  Use, duplication, or disclosure by the
 * Government is subject to restrictions as set forth in subparagraph (c)
 * (1) (ii) of The Rights in Technical Data and Computer Software clause
 * at DFARS 252.227-7013 or subparagraphs (c) (1) and (2) of the
 * Commercial Computer Software--Restricted Rights at 48 CFR 52.227-19,
 * as applicable.  Manufacturer is Rogue Wave Software, Inc., 5500
 * Flatiron Parkway, Boulder, Colorado 80301 USA.
 *
 **************************************************************************/

/*
**
** 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.
** 
*/

#ifndef _RWSTD_TREE_H_INCLUDED
#define _RWSTD_TREE_H_INCLUDED


#include <rw/_algobase.h>
#include <rw/_iterator.h>
#include <rw/_defs.h>


_RWSTD_NAMESPACE_BEGIN (__rw)

template <class _Alloc, class _Val, class _Key, class _KeyOf>
struct __rw_rb_tree_node {

    enum _C_color_t { _C_red, _C_black };

    typedef _Val&                                          reference;
    typedef _Alloc                                         allocator_type;

    typedef _RWSTD_REBIND (allocator_type, __rw_rb_tree_node) _C_node_alloc_t;
    typedef _RWSTD_REBIND (allocator_type, _Key)              _C_key_alloc_t;

    typedef _TYPENAME _C_node_alloc_t::pointer             _C_link_t;
    typedef _TYPENAME _C_key_alloc_t::const_reference      _C_const_key_ref;

    _C_color_t   _C_color_field; 
    _C_link_t    _C_parent_link;
    _C_link_t    _C_left_link;
    _C_link_t    _C_right_link;
    _Val         _C_value_field;

    static _C_link_t _C_minimum (_C_link_t __x) {
        _RWSTD_ASSERT (0 != (void*)__x);
        while ((void*)__x->_C_left())
            __x = __x->_C_left();
        return __x;
    }
    
    static _C_link_t _C_maximum (_C_link_t __x) {
        _RWSTD_ASSERT (0 != (void*)__x);
        while ((void*)__x->_C_right())
            __x = __x->_C_right();
        return __x;
    }

    _C_link_t& _C_left() {
        return _C_left_link;
    }
    
    _C_link_t& _C_right () {
        return _C_right_link;
    }
    
    _C_link_t& _C_parent () {
      return _C_parent_link;
    }
    
    reference _C_value () {
        return _C_value_field;
    }
    
    _C_const_key_ref _C_key () {
        return _KeyOf()(_C_value_field);
    }
    
    _C_color_t& _C_color () {
        return _C_color_field;
    }
    
};


template <class _TypeT, class _DiffT,
          class _Pointer, class _Reference, class _Node>
class __rw_tree_iter
    : public _STD::iterator <_STD::bidirectional_iterator_tag,
                            _TypeT, _DiffT, _Pointer, _Reference>
{
    typedef _STD::iterator <_STD::bidirectional_iterator_tag,
                           _TypeT, _DiffT, _Pointer, _Reference> _C_iter_base;
public:

    typedef _TYPENAME _C_iter_base::value_type        value_type;
    typedef _TYPENAME _C_iter_base::difference_type   difference_type;
    typedef _TYPENAME _C_iter_base::pointer           pointer;
    typedef _TYPENAME _C_iter_base::reference         reference;
    typedef _TYPENAME _C_iter_base::iterator_category iterator_category;
    typedef _Node                                     _C_node_t;
    typedef _TYPENAME _C_node_t::allocator_type       allocator_type;
    typedef _TYPENAME _C_node_t::_C_link_t            _C_link_t;

    typedef const value_type*                         const_pointer; 
    typedef const value_type&                         const_reference; 

    typedef __rw_tree_iter<_TypeT, _DiffT, value_type*, value_type&, _C_node_t>
    _C_iterator;

    _C_link_t _C_node;

    __rw_tree_iter () {}

    // no copy ctor other than the one below is defined
    // will use a compiler generated one if __rw_tree_iter != _C_iterator
    __rw_tree_iter (const _C_iterator &__rhs)
        : _C_node (__rhs._C_node) { }

#ifndef _RWSTD_NO_MEMBER_TEMPLATES

    template <class _Ptr, class _Ref>
    __rw_tree_iter (const __rw_tree_iter<_TypeT, _DiffT, _Ptr, _Ref, _Node>&
                    __rhs)
        : _C_node (__rhs._C_node) { }

#endif   // _RWSTD_NO_MEMBER_TEMPLATES

    __rw_tree_iter (_C_link_t __x)
        : _C_node(__x) {}        

#ifdef SNI
    difference_type operator- (const __rw_tree_iter&) const {
        return 0;
    }
#endif
    
    __rw_tree_iter& operator++ () {
        if ((void*)_C_node->_C_right()) {
            _C_node = _C_node->_C_right();
            while ((void*)_C_node->_C_left())
                _C_node = _C_node->_C_left();
        }
        else {
            _C_link_t __y = _C_node->_C_parent();
            while (_C_node == __y->_C_right()) {
                _C_node = __y; __y = __y->_C_parent();
            }
            if (_C_node->_C_right() != __y) // Necessary because of rightmost.
                _C_node = __y;
        }
        return *this;
    }
    
    __rw_tree_iter& operator-- () {
        if (_C_node->_C_color() == _C_node_t::_C_red
            && _C_node->_C_parent()->_C_parent() == _C_node)  
            //
            // Check for header.
            //
            _C_node = _C_node->_C_right();   // Return rightmost.
        else if ((void*)_C_node->_C_left()) {
            _C_link_t __y = _C_node->_C_left();
            while ((void*)__y->_C_right())
                __y = __y->_C_right();
            _C_node = __y;
        }
        else {
          _C_link_t __y = _C_node->_C_parent();
          while (_C_node == __y->_C_left()) {
            _C_node = __y; __y = __y->_C_parent();
          }
          _C_node = __y;
        }
        return *this;
    }

    __rw_tree_iter operator++ (int) {
        __rw_tree_iter __tmp = *this;
        return ++*this, __tmp;
    }
    
    __rw_tree_iter operator-- (int) {
        __rw_tree_iter __tmp = *this;
        return --*this, __tmp;
    }

    reference operator* () const {
        return _C_node->_C_value();
    }

    _RWSTD_OPERATOR_ARROW (pointer operator-> () const);
};


#define _RWSTD_TREE_ITER(n) \
        __rw_tree_iter <_TypeT, _DiffT, _Ptr##n, _Ref##n, _Node>

template <class _TypeT, class _DiffT,
          class _Ptr1, class _Ref1, class _Ptr2, class _Ref2, class _Node>
inline bool
operator== (const _RWSTD_TREE_ITER(1)  &__x, const _RWSTD_TREE_ITER(2)  &__y)
{
    return __x._C_node == __y._C_node;
}

template <class _TypeT, class _DiffT,
          class _Ptr1, class _Ref1, class _Ptr2, class _Ref2, class _Node>
inline bool
operator!= (const _RWSTD_TREE_ITER(1) &__x, const _RWSTD_TREE_ITER(2) &__y)
{
    return !(__x == __y);
}


#undef _RWSTD_TREE_ITER


template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
class __rb_tree : private _Alloc
{
protected:
    
    typedef __rw_rb_tree_node<_Alloc,_Val,_Key,_KeyOf> _C_node_t; 
    typedef _RWSTD_ALLOC_TYPE (_Alloc,_Val)            _C_val_alloc_t;
    typedef _TYPENAME _C_node_t::_C_key_alloc_t        _C_key_alloc_t;
    typedef _TYPENAME _C_node_t::_C_node_alloc_t       _C_node_alloc_t;
    typedef _TYPENAME _C_node_t::_C_link_t             _C_link_t;

public:
    
    typedef _Key                                       key_type;
    typedef _Val                                       value_type;
    typedef _Alloc                                     allocator_type;
      
    typedef _TYPENAME _C_val_alloc_t::pointer          pointer;
    typedef _TYPENAME _C_val_alloc_t::const_pointer    const_pointer;
    typedef _TYPENAME _Alloc::size_type                size_type;
    typedef _TYPENAME _Alloc::difference_type          difference_type;
    typedef _TYPENAME _C_val_alloc_t::reference        reference;
    typedef _TYPENAME _C_val_alloc_t::const_reference  const_reference;
    
protected:

    struct _C_rb_tree_node_buffer;
    friend struct _C_rb_tree_node_buffer;

    // for brevity, long name preserved for ABI compatibility
    typedef _C_rb_tree_node_buffer _C_node_buf;
    
    typedef _RWSTD_REBIND(allocator_type,_C_node_buf) _C_buf_alloc_t;
    typedef _TYPENAME _C_buf_alloc_t::pointer _C_buf_ptr_t;

    typedef __rw_tree_iter<value_type, difference_type, pointer,
                              reference, _C_node_t>        _C_tree_iter;

    typedef __rw_tree_iter<value_type, difference_type, const_pointer,
                              const_reference, _C_node_t>  _C_tree_citer;

public:

#ifndef _RWSTD_NO_DEBUG_ITER

    typedef __rw_debug_iter <__rb_tree, _C_tree_iter, _C_tree_iter>
    iterator;

    typedef __rw_debug_iter <__rb_tree, _C_tree_citer, _C_tree_iter>
    const_iterator;

    iterator _C_make_iter (_C_link_t __node) {
        return iterator (*this, _C_tree_iter (__node));
    }

    const_iterator _C_make_iter (const _C_link_t __node) const {
        return const_iterator (*this, _C_tree_citer (__node));
    }

#else   // if defined (_RWSTD_NO_DEBUG_ITER)

    typedef _C_tree_iter         iterator;
    typedef _C_tree_citer        const_iterator;

    iterator _C_make_iter (_C_link_t __node) {
        return iterator (__node);
    }

    const_iterator _C_make_iter (const _C_link_t __node) const {
        return const_iterator (__node);
    }

#endif   // _RWSTD_NO_DEBUG_ITER

protected:

    struct _C_rb_tree_node_buffer {
        _C_buf_ptr_t _C_next_buffer;
        size_type    size;
        _C_link_t    _C_buffer;
    };
    
    _C_buf_ptr_t _C_buf_list;
    _C_link_t    _C_free_list;
    _C_link_t    _C_next_avail;
    _C_link_t    _C_last;
    
    void _C_add_new_buffer () {
        _RWSTD_C::size_t __next_buffer_size = 0;
        if ((void*)_C_buf_list) {
            __next_buffer_size = 
                _RW::__rw_new_capacity(_C_buf_list->size,this);
        }
        else {
            __next_buffer_size = 
                _RW::__rw_new_capacity(0,this);
        }          
        _C_buf_ptr_t __tmp = 
            _C_buf_alloc_t(*this).
                allocate(_RWSTD_STATIC_CAST(size_type,1), (void*)_C_buf_list);
#ifndef _RWSTD_NO_EXCEPTIONS
        try {
            __tmp->_C_buffer = 
                _C_node_alloc_t(*this).
                    allocate(__next_buffer_size, (void*)_C_last);
        } catch(...) {
            _C_buf_alloc_t(*this).deallocate(__tmp,1);
            throw;
        } 
#else
        __tmp->_C_buffer = 
            _C_node_alloc_t(*this).allocate(__next_buffer_size,_C_last);
#endif //  _RWSTD_NO_EXCEPTIONS     
        __tmp->_C_next_buffer   = _C_buf_list;
        __tmp->size             = __next_buffer_size;
        _C_buf_list             = __tmp;
        _C_next_avail           = _C_buf_list->_C_buffer;
        _C_last                 = _C_next_avail + __next_buffer_size;
    }
    void _C_deallocate_buffers ();
    
    // 
    // Return a node from the free list or new storage
    //
    _C_link_t _C_get_link() {
        _C_link_t __tmp = _C_free_list;
        _C_link_t __tmp2 = (void*)_C_free_list ? 
            (_C_free_list = _RWSTD_STATIC_CAST(_C_link_t,(_C_free_list->_C_right_link)), __tmp) 
            : (_C_next_avail == _C_last ? (_C_add_new_buffer(), _C_next_avail++) 
               : _C_next_avail++);
        __tmp2->_C_parent_link = NULL;
        __tmp2->_C_left_link = NULL;
        __tmp2->_C_right_link = NULL;
        __tmp2->_C_color_field = _C_node_t::_C_red;
        return __tmp2;
    }

    //
    // Return a node from the free list or new storage with
    // the _Val __v constructed on it.  Every call to _C_get_node
    // must eventually be followed by a call to _C_put_node.
    //
    _C_link_t _C_get_node (const _Val& __v) {
        _C_link_t __tmp2 = _C_get_link();
#ifndef _RWSTD_NO_EXCEPTIONS
        try {
            _RWSTD_VALUE_ALLOC
                (_C_val_alloc_t, 
                 construct(_RWSTD_VALUE_ALLOC (_C_val_alloc_t,
                                               address(__tmp2->_C_value())),
                                               __v));
        } catch(...) {
            _C_put_node(__tmp2,false);
            throw;
        }      
#else
        _RWSTD_VALUE_ALLOC
            (_C_val_alloc_t, 
             construct(_RWSTD_VALUE_ALLOC (_C_val_alloc_t,
                                           address(__tmp2->_C_value())), __v));
#endif // _RWSTD_NO_EXCEPTIONS
        return __tmp2;
    }
    _C_link_t _C_get_node () {
        return _C_get_link();
    }
    
    // 
    // Return a node to the free list and destroy the value in it.
    //
    void _C_put_node (_C_link_t __p, bool do_destroy = true) { 
        __p->_C_right_link = _C_free_list; 
        if (do_destroy)  {
            _RWSTD_VALUE_ALLOC (_C_val_alloc_t, 
                                destroy (_RWSTD_VALUE_ALLOC (_C_val_alloc_t,
                                                   address (__p->_C_value()))));
        }
        _C_free_list = __p; 
    }
    
protected:

    _C_link_t  _C_header;  

    _C_link_t& _C_root      () const { return _C_header->_C_parent (); }