ord_index_node.hpp

来自「Boost provides free peer-reviewed portab」· HPP 代码 · 共 651 行 · 第 1/2 页

/* Copyright 2003-2008 Joaquin M Lopez Munoz.
 * Distributed under the Boost Software License, Version 1.0.
 * (See accompanying file LICENSE_1_0.txt or copy at
 * http://www.boost.org/LICENSE_1_0.txt)
 *
 * See http://www.boost.org/libs/multi_index for library home page.
 *
 * The internal implementation of red-black trees is based on that of SGI STL
 * stl_tree.h file: 
 *
 * 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.
 *
 */

#ifndef BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_NODE_HPP
#define BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_NODE_HPP

#if defined(_MSC_VER)&&(_MSC_VER>=1200)
#pragma once
#endif

#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
#include <cstddef>
#include <boost/detail/allocator_utilities.hpp>
#include <boost/multi_index/detail/prevent_eti.hpp>

#if !defined(BOOST_MULTI_INDEX_DISABLE_COMPRESSED_ORDERED_INDEX_NODES)
#include <boost/mpl/and.hpp>
#include <boost/mpl/if.hpp>
#include <boost/multi_index/detail/uintptr_type.hpp>
#include <boost/type_traits/alignment_of.hpp>
#include <boost/type_traits/is_same.hpp>
#endif

namespace boost{

namespace multi_index{

namespace detail{

/* definition of red-black nodes for ordered_index */

enum ordered_index_color{red=false,black=true};
enum ordered_index_side{to_left=false,to_right=true};

template<typename Allocator>
struct ordered_index_node_impl; /* fwd decl. */

template<typename Allocator>
struct ordered_index_node_std_base
{
  typedef typename prevent_eti<
    Allocator,
    typename boost::detail::allocator::rebind_to<
      Allocator,
      ordered_index_node_impl<Allocator>
    >::type
  >::type::pointer                                pointer;
  typedef typename prevent_eti<
    Allocator,
    typename boost::detail::allocator::rebind_to<
      Allocator,
      ordered_index_node_impl<Allocator>
    >::type
  >::type::const_pointer                          const_pointer;
  typedef ordered_index_color&                    color_ref;
  typedef pointer&                                parent_ref;

  ordered_index_color& color(){return color_;}
  ordered_index_color  color()const{return color_;}
  pointer&             parent(){return parent_;}
  pointer              parent()const{return parent_;}
  pointer&             left(){return left_;}
  pointer              left()const{return left_;}
  pointer&             right(){return right_;}
  pointer              right()const{return right_;}

private:
  ordered_index_color color_; 
  pointer             parent_;
  pointer             left_;
  pointer             right_;
};

#if !defined(BOOST_MULTI_INDEX_DISABLE_COMPRESSED_ORDERED_INDEX_NODES)
/* If ordered_index_node_impl has even alignment, we can use the least
 * significant bit of one of the ordered_index_node_impl pointers to
 * store color information. This typically reduces the size of
 * ordered_index_node_impl by 25%.
 */

#if defined(BOOST_MSVC)
/* This code casts pointers to an integer type that has been computed
 * to be large enough to hold the pointer, however the metaprogramming
 * logic is not always spotted by the VC++ code analyser that issues a
 * long list of warnings.
 */

#pragma warning(push)
#pragma warning(disable:4312 4311)
#endif

template<typename Allocator>
struct ordered_index_node_compressed_base
{
  typedef ordered_index_node_impl<Allocator>*       pointer;
  typedef const ordered_index_node_impl<Allocator>* const_pointer;

  struct color_ref
  {
    color_ref(uintptr_type* r_):r(r_){}
    
    operator ordered_index_color()const
    {
      return ordered_index_color(*r&uintptr_type(1));
    }
    
    color_ref& operator=(ordered_index_color c)
    {
      *r&=~uintptr_type(1);
      *r|=uintptr_type(c);
      return *this;
    }
    
    color_ref& operator=(const color_ref& x)
    {
      return operator=(x.operator ordered_index_color());
    }
    
  private:
    uintptr_type* r;
  };
  
  struct parent_ref
  {
    parent_ref(uintptr_type* r_):r(r_){}
    
    operator pointer()const
    {
      return (pointer)(void*)(*r&~uintptr_type(1));
    }
    
    parent_ref& operator=(pointer p)
    {
      *r=((uintptr_type)(void*)p)|(*r&uintptr_type(1));
      return *this;
    }
    
    parent_ref& operator=(const parent_ref& x)
    {
      return operator=(x.operator pointer());
    }

    pointer operator->()const
    {
      return operator pointer();
    }

  private:
    uintptr_type* r;
  };
  
  color_ref           color(){return color_ref(&parentcolor_);}
  ordered_index_color color()const
  {
    return ordered_index_color(parentcolor_&std::size_t(1ul));
  }

  parent_ref parent(){return parent_ref(&parentcolor_);}
  pointer    parent()const
  {
    return (pointer)(void*)(parentcolor_&~uintptr_type(1));
  }

  pointer& left(){return left_;}
  pointer  left()const{return left_;}
  pointer& right(){return right_;}
  pointer  right()const{return right_;}

private:
  uintptr_type parentcolor_;
  pointer      left_;
  pointer      right_;
};
#if defined(BOOST_MSVC)
#pragma warning(pop)
#endif
#endif

template<typename Allocator>
struct ordered_index_node_impl_base:

#if !defined(BOOST_MULTI_INDEX_DISABLE_COMPRESSED_ORDERED_INDEX_NODES)
  mpl::if_c<
    !(has_uintptr_type::value)||
    (alignment_of<ordered_index_node_compressed_base<Allocator> >::value%2)||
    !(is_same<
      typename prevent_eti<
        Allocator,
        typename boost::detail::allocator::rebind_to<
          Allocator,
          ordered_index_node_impl<Allocator>
        >::type
      >::type::pointer,
      ordered_index_node_impl<Allocator>*>::value),
    ordered_index_node_std_base<Allocator>,
    ordered_index_node_compressed_base<Allocator>
  >::type
#else
  ordered_index_node_std_base<Allocator>
#endif

{};

template<typename Allocator>
struct ordered_index_node_impl:ordered_index_node_impl_base<Allocator>
{
private:
  typedef ordered_index_node_impl_base<Allocator> super;

public:
  typedef typename super::color_ref               color_ref;
  typedef typename super::parent_ref              parent_ref;
  typedef typename super::pointer                 pointer;
  typedef typename super::const_pointer           const_pointer;

  /* interoperability with bidir_node_iterator */

  static void increment(pointer& x)
  {
    if(x->right()!=pointer(0)){
      x=x->right();
      while(x->left()!=pointer(0))x=x->left();
    }
    else{
      pointer y=x->parent();
      while(x==y->right()){
        x=y;
        y=y->parent();
      }
      if(x->right()!=y)x=y;
    }
  }

  static void decrement(pointer& x)
  {
    if(x->color()==red&&x->parent()->parent()==x){
      x=x->right();
    }
    else if(x->left()!=pointer(0)){
      pointer y=x->left();
      while(y->right()!=pointer(0))y=y->right();
      x=y;
    }else{
      pointer y=x->parent();
      while(x==y->left()){
        x=y;
        y=y->parent();
      }
      x=y;
    }
  }

  /* algorithmic stuff */

  static void rotate_left(pointer x,parent_ref root)
  {
    pointer y=x->right();
    x->right()=y->left();
    if(y->left()!=pointer(0))y->left()->parent()=x;
    y->parent()=x->parent();
    
    if(x==root)                    root=y;
    else if(x==x->parent()->left())x->parent()->left()=y;
    else                           x->parent()->right()=y;
    y->left()=x;
    x->parent()=y;
  }

  static pointer minimum(pointer x)
  {
    while(x->left()!=pointer(0))x=x->left();
    return x;
  }

  static pointer maximum(pointer x)
  {
    while(x->right()!=pointer(0))x=x->right();
    return x;
  }

  static void rotate_right(pointer x,parent_ref root)
  {
    pointer y=x->left();
    x->left()=y->right();
    if(y->right()!=pointer(0))y->right()->parent()=x;
    y->parent()=x->parent();

    if(x==root)                     root=y;
    else if(x==x->parent()->right())x->parent()->right()=y;
    else                            x->parent()->left()=y;
    y->right()=x;
    x->parent()=y;
  }