summaryrefslogtreecommitdiff
path: root/boost/intrusive/detail/rbtree_node.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/intrusive/detail/rbtree_node.hpp')
-rw-r--r--boost/intrusive/detail/rbtree_node.hpp177
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 0000000..dbe0130
--- /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