X-Git-Url: http://g0dil.de/git?a=blobdiff_plain;f=boost_ext%2Fboost%2Fmulti_index%2Fdetail%2Ford_index_node.hpp;fp=boost_ext%2Fboost%2Fmulti_index%2Fdetail%2Ford_index_node.hpp;h=b4193d248f7a56882d5d343371cf8cbd102d8ec4;hb=4123b4fe58a7fd4659fa01476581690b47c83600;hp=0000000000000000000000000000000000000000;hpb=79564b90f6c9f7cd0bc5b11a6146bb7067b11a75;p=senf.git

diff --git a/boost_ext/boost/multi_index/detail/ord_index_node.hpp b/boost_ext/boost/multi_index/detail/ord_index_node.hpp
new file mode 100644
index 0000000..b4193d2
--- /dev/null
+++ b/boost_ext/boost/multi_index/detail/ord_index_node.hpp
@@ -0,0 +1,650 @@
+/* Copyright 2003-2007 Joaquín M López Muñoz.
+ * 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;
+  }
+
+  static void rebalance(pointer x,parent_ref root)
+  {
+    x->color()=red;
+    while(x!=root&&x->parent()->color()==red){
+      if(x->parent()==x->parent()->parent()->left()){
+        pointer y=x->parent()->parent()->right();
+        if(y!=pointer(0)&&y->color()==red){
+          x->parent()->color()=black;
+          y->color()=black;
+          x->parent()->parent()->color()=red;
+          x=x->parent()->parent();
+        }
+        else{
+          if(x==x->parent()->right()){
+            x=x->parent();
+            rotate_left(x,root);
+          }
+          x->parent()->color()=black;
+          x->parent()->parent()->color()=red;
+          rotate_right(x->parent()->parent(),root);
+        }
+      }
+      else{
+        pointer y=x->parent()->parent()->left();
+        if(y!=pointer(0)&&y->color()==red){
+          x->parent()->color()=black;
+          y->color()=black;
+          x->parent()->parent()->color()=red;
+          x=x->parent()->parent();
+        }
+        else{
+          if(x==x->parent()->left()){
+            x=x->parent();
+            rotate_right(x,root);
+          }
+          x->parent()->color()=black;
+          x->parent()->parent()->color()=red;
+          rotate_left(x->parent()->parent(),root);
+        }
+      }
+    }
+    root->color()=black;
+  }
+
+  static void link(
+    pointer x,ordered_index_side side,pointer position,pointer header)
+  {
+    if(side==to_left){
+      position->left()=x;  /* also makes leftmost=x when parent==header */
+      if(position==header){
+        header->parent()=x;
+        header->right()=x;
+      }
+      else if(position==header->left()){
+        header->left()=x;  /* maintain leftmost pointing to min node */
+      }
+    }
+    else{
+      position->right()=x;
+      if(position==header->right()){
+        header->right()=x; /* maintain rightmost pointing to max node */
+      }
+    }
+    x->parent()=position;
+    x->left()=pointer(0);
+    x->right()=pointer(0);
+    ordered_index_node_impl::rebalance(x,header->parent());
+  }
+
+  static pointer rebalance_for_erase(
+    pointer z,parent_ref root,pointer& leftmost,pointer& rightmost)
+  {
+    pointer y=z;
+    pointer x=pointer(0);
+    pointer x_parent=pointer(0);
+    if(y->left()==pointer(0)){    /* z has at most one non-null child. y==z. */
+      x=y->right();               /* x might be null */
+    }
+    else{
+      if(y->right()==pointer(0)){ /* z has exactly one non-null child. y==z. */
+        x=y->left();              /* x is not null */
+      }
+      else{                       /* z has two non-null children.  Set y to */
+        y=y->right();             /* z's successor. x might be null.        */
+        while(y->left()!=pointer(0))y=y->left();
+        x=y->right();
+      }
+    }
+    if(y!=z){
+      z->left()->parent()=y;   /* relink y in place of z. y is z's successor */
+      y->left()=z->left();
+      if(y!=z->right()){
+        x_parent=y->parent();
+        if(x!=pointer(0))x->parent()=y->parent();
+        y->parent()->left()=x; /* y must be a child of left */
+        y->right()=z->right();
+        z->right()->parent()=y;
+      }
+      else{
+        x_parent=y;
+      }
+
+      if(root==z)                    root=y;
+      else if(z->parent()->left()==z)z->parent()->left()=y;
+      else                           z->parent()->right()=y;
+      y->parent()=z->parent();
+      ordered_index_color c=y->color();
+      y->color()=z->color();
+      z->color()=c;
+      y=z;                    /* y now points to node to be actually deleted */
+    }
+    else{                     /* y==z */
+      x_parent=y->parent();
+      if(x!=pointer(0))x->parent()=y->parent();   
+      if(root==z){
+        root=x;
+      }
+      else{
+        if(z->parent()->left()==z)z->parent()->left()=x;
+        else                      z->parent()->right()=x;
+      }
+      if(leftmost==z){
+        if(z->right()==pointer(0)){ /* z->left() must be null also */
+          leftmost=z->parent();
+        }
+        else{              
+          leftmost=minimum(x);      /* makes leftmost==header if z==root */
+        }
+      }
+      if(rightmost==z){
+        if(z->left()==pointer(0)){  /* z->right() must be null also */
+          rightmost=z->parent();
+        }
+        else{                   /* x==z->left() */
+          rightmost=maximum(x); /* makes rightmost==header if z==root */
+        }
+      }
+    }
+    if(y->color()!=red){
+      while(x!=root&&(x==pointer(0)|| x->color()==black)){
+        if(x==x_parent->left()){
+          pointer w=x_parent->right();
+          if(w->color()==red){
+            w->color()=black;
+            x_parent->color()=red;
+            rotate_left(x_parent,root);
+            w=x_parent->right();
+          }
+          if((w->left()==pointer(0)||w->left()->color()==black) &&
+             (w->right()==pointer(0)||w->right()->color()==black)){
+            w->color()=red;
+            x=x_parent;
+            x_parent=x_parent->parent();
+          } 
+          else{
+            if(w->right()==pointer(0 )
+                || w->right()->color()==black){
+              if(w->left()!=pointer(0)) w->left()->color()=black;
+              w->color()=red;
+              rotate_right(w,root);
+              w=x_parent->right();
+            }
+            w->color()=x_parent->color();
+            x_parent->color()=black;
+            if(w->right()!=pointer(0))w->right()->color()=black;
+            rotate_left(x_parent,root);
+            break;
+          }
+        } 
+        else{                   /* same as above,with right <-> left */
+          pointer w=x_parent->left();
+          if(w->color()==red){
+            w->color()=black;
+            x_parent->color()=red;
+            rotate_right(x_parent,root);
+            w=x_parent->left();
+          }
+          if((w->right()==pointer(0)||w->right()->color()==black) &&
+             (w->left()==pointer(0)||w->left()->color()==black)){
+            w->color()=red;
+            x=x_parent;
+            x_parent=x_parent->parent();
+          }
+          else{
+            if(w->left()==pointer(0)||w->left()->color()==black){
+              if(w->right()!=pointer(0))w->right()->color()=black;
+              w->color()=red;
+              rotate_left(w,root);
+              w=x_parent->left();
+            }
+            w->color()=x_parent->color();
+            x_parent->color()=black;
+            if(w->left()!=pointer(0))w->left()->color()=black;
+            rotate_right(x_parent,root);
+            break;
+          }
+        }
+      }
+      if(x!=pointer(0))x->color()=black;
+    }
+    return y;
+  }
+
+  static void restore(pointer x,pointer position,pointer header)
+  {
+    if(position->left()==pointer(0)||position->left()==header){
+      link(x,to_left,position,header);
+    }
+    else{
+      decrement(position);
+      link(x,to_right,position,header);
+    }
+  }
+
+#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
+  /* invariant stuff */
+
+  static std::size_t black_count(pointer node,pointer root)
+  {
+    if(node==pointer(0))return 0;
+    std::size_t sum=0;
+    for(;;){
+      if(node->color()==black)++sum;
+      if(node==root)break;
+      node=node->parent();
+    } 
+    return sum;
+  }
+#endif
+};
+
+template<typename Super>
+struct ordered_index_node_trampoline:
+  prevent_eti<
+    Super,
+    ordered_index_node_impl<
+      typename boost::detail::allocator::rebind_to<
+        typename Super::allocator_type,
+        void
+      >::type
+    >
+  >::type
+{
+  typedef typename prevent_eti<
+    Super,
+    ordered_index_node_impl<
+      typename boost::detail::allocator::rebind_to<
+        typename Super::allocator_type,
+        void
+      >::type
+    >
+  >::type impl_type;
+};
+
+template<typename Super>
+struct ordered_index_node:Super,ordered_index_node_trampoline<Super>
+{
+private:
+  typedef ordered_index_node_trampoline<Super> trampoline;
+
+public:
+  typedef typename trampoline::impl_type     impl_type;
+  typedef typename trampoline::color_ref     impl_color_ref;
+  typedef typename trampoline::parent_ref    impl_parent_ref;
+  typedef typename trampoline::pointer       impl_pointer;
+  typedef typename trampoline::const_pointer const_impl_pointer;
+
+  impl_color_ref      color(){return trampoline::color();}
+  ordered_index_color color()const{return trampoline::color();}
+  impl_parent_ref     parent(){return trampoline::parent();}
+  impl_pointer        parent()const{return trampoline::parent();}
+  impl_pointer&       left(){return trampoline::left();}
+  impl_pointer        left()const{return trampoline::left();}
+  impl_pointer&       right(){return trampoline::right();}
+  impl_pointer        right()const{return trampoline::right();}
+
+  impl_pointer impl()
+  {
+    return static_cast<impl_pointer>(
+      static_cast<impl_type*>(static_cast<trampoline*>(this)));
+  }
+
+  const_impl_pointer impl()const
+  {
+    return static_cast<const_impl_pointer>(
+      static_cast<const impl_type*>(static_cast<const trampoline*>(this)));
+  }
+
+  static ordered_index_node* from_impl(impl_pointer x)
+  {
+    return static_cast<ordered_index_node*>(
+      static_cast<trampoline*>(&*x));
+  }
+
+  static const ordered_index_node* from_impl(const_impl_pointer x)
+  {
+    return static_cast<const ordered_index_node*>(
+      static_cast<const trampoline*>(&*x));
+  }
+
+  /* interoperability with bidir_node_iterator */
+
+  static void increment(ordered_index_node*& x)
+  {
+    impl_pointer xi=x->impl();
+    trampoline::increment(xi);
+    x=from_impl(xi);
+  }
+
+  static void decrement(ordered_index_node*& x)
+  {
+    impl_pointer xi=x->impl();
+    trampoline::decrement(xi);
+    x=from_impl(xi);
+  }
+};
+
+} /* namespace multi_index::detail */
+
+} /* namespace multi_index */
+
+} /* namespace boost */
+
+#endif