1 files changed, 177 insertions, 0 deletions
diff --git a/boost/intrusive/detail/rbtree_node.hpp b/boost/intrusive/detail/rbtree_node.hpp
new file mode 100644
index 0000000000..dbe0130024
--- /dev/null
+++ b/boost/intrusive/detail/rbtree_node.hpp
@@ -0,0 +1,177 @@
+/////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Olaf Krzikalla 2004-2006.
+// (C) Copyright Ion Gaztanaga  2006-2009.
+//
+// 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/intrusive for documentation.
+//
+/////////////////////////////////////////////////////////////////////////////
+
+#ifndef BOOST_INTRUSIVE_RBTREE_NODE_HPP
+#define BOOST_INTRUSIVE_RBTREE_NODE_HPP
+
+#include <boost/intrusive/detail/config_begin.hpp>
+#include <iterator>
+#include <boost/intrusive/pointer_traits.hpp>
+#include <boost/intrusive/rbtree_algorithms.hpp>
+#include <boost/intrusive/pointer_plus_bits.hpp>
+#include <boost/intrusive/detail/mpl.hpp>
+
+namespace boost {
+namespace intrusive {
+
+/////////////////////////////////////////////////////////////////////////////
+//                                                                         //
+//                Generic node_traits for any pointer type                 //
+//                                                                         //
+/////////////////////////////////////////////////////////////////////////////
+
+//This is the compact representation: 3 pointers
+template<class VoidPointer>
+struct compact_rbtree_node
+{
+   typedef typename pointer_traits
+      <VoidPointer>::template rebind_pointer
+         <compact_rbtree_node<VoidPointer> >::type node_ptr;
+   enum color { red_t, black_t };
+   node_ptr parent_, left_, right_;
+};
+
+//This is the normal representation: 3 pointers + enum
+template<class VoidPointer>
+struct rbtree_node
+{
+   typedef typename pointer_traits
+      <VoidPointer>::template rebind_pointer
+         <rbtree_node<VoidPointer> >::type   node_ptr;
+
+   enum color { red_t, black_t };
+   node_ptr parent_, left_, right_;
+   color color_;
+};
+
+//This is the default node traits implementation
+//using a node with 3 generic pointers plus an enum
+template<class VoidPointer>
+struct default_rbtree_node_traits_impl
+{
+   typedef rbtree_node<VoidPointer> node;
+
+   typedef typename pointer_traits
+      <VoidPointer>::template rebind_pointer<node>::type          node_ptr;
+   typedef typename pointer_traits
+      <VoidPointer>::template rebind_pointer<const node>::type    const_node_ptr;
+
+   typedef typename node::color color;
+
+   static const node_ptr & get_parent(const const_node_ptr & n)
+   {  return n->parent_;  }
+
+   static void set_parent(const node_ptr & n, const node_ptr & p)
+   {  n->parent_ = p;  }
+
+   static const node_ptr & get_left(const const_node_ptr & n)
+   {  return n->left_;  }
+
+   static void set_left(const node_ptr & n, const node_ptr & l)
+   {  n->left_ = l;  }
+
+   static const node_ptr & get_right(const const_node_ptr & n)
+   {  return n->right_;  }
+
+   static void set_right(const node_ptr & n, const node_ptr & r)
+   {  n->right_ = r;  }
+
+   static color get_color(const const_node_ptr & n)
+   {  return n->color_;  }
+
+   static void set_color(const node_ptr & n, color c)
+   {  n->color_ = c;  }
+
+   static color black()
+   {  return node::black_t;  }
+
+   static color red()
+   {  return node::red_t;  }
+};
+
+//This is the compact node traits implementation
+//using a node with 3 generic pointers
+template<class VoidPointer>
+struct compact_rbtree_node_traits_impl
+{
+   typedef compact_rbtree_node<VoidPointer> node;
+   typedef typename pointer_traits
+      <VoidPointer>::template rebind_pointer<node>::type          node_ptr;
+   typedef typename pointer_traits
+      <VoidPointer>::template rebind_pointer<const node>::type    const_node_ptr;
+
+   typedef pointer_plus_bits<node_ptr, 1> ptr_bit;
+
+   typedef typename node::color color;
+
+   static node_ptr get_parent(const const_node_ptr & n)
+   {  return ptr_bit::get_pointer(n->parent_);  }
+
+   static void set_parent(const node_ptr & n, const node_ptr & p)
+   {  ptr_bit::set_pointer(n->parent_, p);  }
+
+   static const node_ptr & get_left(const const_node_ptr & n)
+   {  return n->left_;  }
+
+   static void set_left(const node_ptr & n, const node_ptr & l)
+   {  n->left_ = l;  }
+
+   static const node_ptr & get_right(const const_node_ptr & n)
+   {  return n->right_;  }
+
+   static void set_right(const node_ptr & n, const node_ptr & r)
+   {  n->right_ = r;  }
+
+   static color get_color(const const_node_ptr & n)
+   {  return (color)ptr_bit::get_bits(n->parent_);  }
+
+   static void set_color(const node_ptr & n, color c)
+   {  ptr_bit::set_bits(n->parent_, c != 0);  }
+
+   static color black()
+   {  return node::black_t;  }
+
+   static color red()
+   {  return node::red_t;  }
+};
+
+//Dispatches the implementation based on the boolean
+template<class VoidPointer, bool Compact>
+struct rbtree_node_traits_dispatch
+   :  public default_rbtree_node_traits_impl<VoidPointer>
+{};
+
+template<class VoidPointer>
+struct rbtree_node_traits_dispatch<VoidPointer, true>
+   :  public compact_rbtree_node_traits_impl<VoidPointer>
+{};
+
+//Inherit from the detail::link_dispatch depending on the embedding capabilities
+template<class VoidPointer, bool OptimizeSize = false>
+struct rbtree_node_traits
+   :  public rbtree_node_traits_dispatch
+         < VoidPointer
+         ,  OptimizeSize &&
+           (max_pointer_plus_bits
+            < VoidPointer
+            , detail::alignment_of<compact_rbtree_node<VoidPointer> >::value 
+            >::value >= 1)
+         >
+{};
+
+} //namespace intrusive 
+} //namespace boost 
+
+#include <boost/intrusive/detail/config_end.hpp>
+
+#endif //BOOST_INTRUSIVE_RBTREE_NODE_HPP