[ceph.git] / ceph / src / boost / boost / intrusive / detail / rbtree_node.hpp

/////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Olaf Krzikalla 2004-2006.
// (C) Copyright Ion Gaztanaga  2006-2013.
//
// 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

#ifndef BOOST_CONFIG_HPP
#  include <boost/config.hpp>
#endif

#if defined(BOOST_HAS_PRAGMA_ONCE)
#  pragma once
#endif

#include <boost/intrusive/detail/config_begin.hpp>
#include <boost/intrusive/detail/workaround.hpp>
#include <boost/intrusive/pointer_rebind.hpp>
#include <boost/intrusive/rbtree_algorithms.hpp>
#include <boost/intrusive/pointer_plus_bits.hpp>
#include <boost/intrusive/detail/mpl.hpp>
#include <boost/intrusive/detail/tree_node.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 compact_rbtree_node<VoidPointer> node;
   typedef typename pointer_rebind<VoidPointer, node >::type         node_ptr;
   typedef typename pointer_rebind<VoidPointer, const node >::type   const_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 rbtree_node<VoidPointer> node;
   typedef typename pointer_rebind<VoidPointer, node >::type         node_ptr;
   typedef typename pointer_rebind<VoidPointer, const node >::type   const_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 node::node_ptr        node_ptr;
   typedef typename node::const_node_ptr  const_node_ptr;

   typedef typename node::color color;

   BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n)
   {  return n->parent_;  }

   BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const node_ptr & n)
   {  return n->parent_;  }

   BOOST_INTRUSIVE_FORCEINLINE static void set_parent(node_ptr n, node_ptr p)
   {  n->parent_ = p;  }

   BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n)
   {  return n->left_;  }

   BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const node_ptr & n)
   {  return n->left_;  }

   BOOST_INTRUSIVE_FORCEINLINE static void set_left(node_ptr n, node_ptr l)
   {  n->left_ = l;  }

   BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n)
   {  return n->right_;  }

   BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const node_ptr & n)
   {  return n->right_;  }

   BOOST_INTRUSIVE_FORCEINLINE static void set_right(node_ptr n, node_ptr r)
   {  n->right_ = r;  }

   BOOST_INTRUSIVE_FORCEINLINE static color get_color(const const_node_ptr & n)
   {  return n->color_;  }

   BOOST_INTRUSIVE_FORCEINLINE static color get_color(const node_ptr & n)
   {  return n->color_;  }

   BOOST_INTRUSIVE_FORCEINLINE static void set_color(const node_ptr & n, color c)
   {  n->color_ = c;  }

   BOOST_INTRUSIVE_FORCEINLINE static color black()
   {  return node::black_t;  }

   BOOST_INTRUSIVE_FORCEINLINE 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 node::node_ptr        node_ptr;
   typedef typename node::const_node_ptr  const_node_ptr;

   typedef pointer_plus_bits<node_ptr, 1> ptr_bit;

   typedef typename node::color color;

   BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n)
   {  return ptr_bit::get_pointer(n->parent_);  }

   BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const node_ptr & n)
   {  return ptr_bit::get_pointer(n->parent_);  }

   BOOST_INTRUSIVE_FORCEINLINE static void set_parent(node_ptr n, node_ptr p)
   {  ptr_bit::set_pointer(n->parent_, p);  }

   BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n)
   {  return n->left_;  }

   BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const node_ptr & n)
   {  return n->left_;  }

   BOOST_INTRUSIVE_FORCEINLINE static void set_left(node_ptr n, node_ptr l)
   {  n->left_ = l;  }

   BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n)
   {  return n->right_;  }

   BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const node_ptr & n)
   {  return n->right_;  }

   BOOST_INTRUSIVE_FORCEINLINE static void set_right(node_ptr n, node_ptr r)
   {  n->right_ = r;  }

   BOOST_INTRUSIVE_FORCEINLINE static color get_color(const const_node_ptr & n)
   {  return (color)ptr_bit::get_bits(n->parent_);  }

   BOOST_INTRUSIVE_FORCEINLINE static color get_color(const node_ptr & n)
   {  return (color)ptr_bit::get_bits(n->parent_);  }

   BOOST_INTRUSIVE_FORCEINLINE static void set_color(const node_ptr & n, color c)
   {  ptr_bit::set_bits(n->parent_, c != 0);  }

   BOOST_INTRUSIVE_FORCEINLINE static color black()
   {  return node::black_t;  }

   BOOST_INTRUSIVE_FORCEINLINE 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 rbtree_node_traits_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
Commit	Line	Data
7c673cae FG	1	/////////////////////////////////////////////////////////////////////////////
	2	//
	3	// (C) Copyright Olaf Krzikalla 2004-2006.
	4	// (C) Copyright Ion Gaztanaga 2006-2013.
	5	//
	6	// Distributed under the Boost Software License, Version 1.0.
	7	// (See accompanying file LICENSE_1_0.txt or copy at
	8	// http://www.boost.org/LICENSE_1_0.txt)
	9	//
	10	// See http://www.boost.org/libs/intrusive for documentation.
	11	//
	12	/////////////////////////////////////////////////////////////////////////////
	13
	14	#ifndef BOOST_INTRUSIVE_RBTREE_NODE_HPP
	15	#define BOOST_INTRUSIVE_RBTREE_NODE_HPP
	16
	17	#ifndef BOOST_CONFIG_HPP
	18	# include <boost/config.hpp>
	19	#endif
	20
	21	#if defined(BOOST_HAS_PRAGMA_ONCE)
	22	# pragma once
	23	#endif
	24
	25	#include <boost/intrusive/detail/config_begin.hpp>
	26	#include <boost/intrusive/detail/workaround.hpp>
	27	#include <boost/intrusive/pointer_rebind.hpp>
	28	#include <boost/intrusive/rbtree_algorithms.hpp>
	29	#include <boost/intrusive/pointer_plus_bits.hpp>
	30	#include <boost/intrusive/detail/mpl.hpp>
	31	#include <boost/intrusive/detail/tree_node.hpp>
	32
	33	namespace boost {
	34	namespace intrusive {
	35
	36	/////////////////////////////////////////////////////////////////////////////
	37	// //
	38	// Generic node_traits for any pointer type //
	39	// //
	40	/////////////////////////////////////////////////////////////////////////////
	41
	42	//This is the compact representation: 3 pointers
	43	template<class VoidPointer>
	44	struct compact_rbtree_node
	45	{
	46	typedef compact_rbtree_node<VoidPointer> node;
	47	typedef typename pointer_rebind<VoidPointer, node >::type node_ptr;
	48	typedef typename pointer_rebind<VoidPointer, const node >::type const_node_ptr;
	49	enum color { red_t, black_t };
	50	node_ptr parent_, left_, right_;
	51	};
	52
	53	//This is the normal representation: 3 pointers + enum
	54	template<class VoidPointer>
	55	struct rbtree_node
	56	{
	57	typedef rbtree_node<VoidPointer> node;
	58	typedef typename pointer_rebind<VoidPointer, node >::type node_ptr;
	59	typedef typename pointer_rebind<VoidPointer, const node >::type const_node_ptr;
	60
	61	enum color { red_t, black_t };
	62	node_ptr parent_, left_, right_;
	63	color color_;
	64	};
65
66	//This is the default node traits implementation
67	//using a node with 3 generic pointers plus an enum
68	template<class VoidPointer>
69	struct default_rbtree_node_traits_impl
70	{
71	typedef rbtree_node<VoidPointer> node;
72	typedef typename node::node_ptr node_ptr;
73	typedef typename node::const_node_ptr const_node_ptr;
74
75	typedef typename node::color color;
76
77	BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n)
78	{ return n->parent_; }
79
80	BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const node_ptr & n)
81	{ return n->parent_; }
82
92f5a8d4	83	BOOST_INTRUSIVE_FORCEINLINE static void set_parent(node_ptr n, node_ptr p)
7c673cae FG	84	{ n->parent_ = p; }
	85
	86	BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n)
	87	{ return n->left_; }
	88
	89	BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const node_ptr & n)
	90	{ return n->left_; }
	91
92f5a8d4	92	BOOST_INTRUSIVE_FORCEINLINE static void set_left(node_ptr n, node_ptr l)
7c673cae FG	93	{ n->left_ = l; }
	94
	95	BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n)
	96	{ return n->right_; }
	97
	98	BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const node_ptr & n)
	99	{ return n->right_; }
	100
92f5a8d4	101	BOOST_INTRUSIVE_FORCEINLINE static void set_right(node_ptr n, node_ptr r)
7c673cae FG	102	{ n->right_ = r; }
	103
	104	BOOST_INTRUSIVE_FORCEINLINE static color get_color(const const_node_ptr & n)
	105	{ return n->color_; }
	106
	107	BOOST_INTRUSIVE_FORCEINLINE static color get_color(const node_ptr & n)
	108	{ return n->color_; }
	109
	110	BOOST_INTRUSIVE_FORCEINLINE static void set_color(const node_ptr & n, color c)
	111	{ n->color_ = c; }
	112
	113	BOOST_INTRUSIVE_FORCEINLINE static color black()
	114	{ return node::black_t; }
	115
	116	BOOST_INTRUSIVE_FORCEINLINE static color red()
	117	{ return node::red_t; }
	118	};
	119
	120	//This is the compact node traits implementation
	121	//using a node with 3 generic pointers
	122	template<class VoidPointer>
	123	struct compact_rbtree_node_traits_impl
	124	{
	125	typedef compact_rbtree_node<VoidPointer> node;
	126	typedef typename node::node_ptr node_ptr;
	127	typedef typename node::const_node_ptr const_node_ptr;
	128
	129	typedef pointer_plus_bits<node_ptr, 1> ptr_bit;
	130
	131	typedef typename node::color color;
	132
	133	BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const const_node_ptr & n)
	134	{ return ptr_bit::get_pointer(n->parent_); }
	135
	136	BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const node_ptr & n)
	137	{ return ptr_bit::get_pointer(n->parent_); }
	138
92f5a8d4	139	BOOST_INTRUSIVE_FORCEINLINE static void set_parent(node_ptr n, node_ptr p)
7c673cae FG	140	{ ptr_bit::set_pointer(n->parent_, p); }
	141
	142	BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const const_node_ptr & n)
	143	{ return n->left_; }
	144
	145	BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_left(const node_ptr & n)
	146	{ return n->left_; }
	147
92f5a8d4	148	BOOST_INTRUSIVE_FORCEINLINE static void set_left(node_ptr n, node_ptr l)
7c673cae FG	149	{ n->left_ = l; }
	150
	151	BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const const_node_ptr & n)
	152	{ return n->right_; }
	153
	154	BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_right(const node_ptr & n)
	155	{ return n->right_; }
	156
92f5a8d4	157	BOOST_INTRUSIVE_FORCEINLINE static void set_right(node_ptr n, node_ptr r)
7c673cae FG	158	{ n->right_ = r; }
	159
	160	BOOST_INTRUSIVE_FORCEINLINE static color get_color(const const_node_ptr & n)
	161	{ return (color)ptr_bit::get_bits(n->parent_); }
	162
	163	BOOST_INTRUSIVE_FORCEINLINE static color get_color(const node_ptr & n)
	164	{ return (color)ptr_bit::get_bits(n->parent_); }
	165
	166	BOOST_INTRUSIVE_FORCEINLINE static void set_color(const node_ptr & n, color c)
	167	{ ptr_bit::set_bits(n->parent_, c != 0); }
	168
	169	BOOST_INTRUSIVE_FORCEINLINE static color black()
	170	{ return node::black_t; }
	171
	172	BOOST_INTRUSIVE_FORCEINLINE static color red()
	173	{ return node::red_t; }
	174	};
	175
	176	//Dispatches the implementation based on the boolean
	177	template<class VoidPointer, bool Compact>
	178	struct rbtree_node_traits_dispatch
	179	: public default_rbtree_node_traits_impl<VoidPointer>
	180	{};
	181
	182	template<class VoidPointer>
	183	struct rbtree_node_traits_dispatch<VoidPointer, true>
	184	: public compact_rbtree_node_traits_impl<VoidPointer>
	185	{};
	186
	187	//Inherit from rbtree_node_traits_dispatch depending on the embedding capabilities
	188	template<class VoidPointer, bool OptimizeSize = false>
	189	struct rbtree_node_traits
	190	: public rbtree_node_traits_dispatch
	191	< VoidPointer
	192	, OptimizeSize &&
	193	(max_pointer_plus_bits
	194	< VoidPointer
	195	, detail::alignment_of<compact_rbtree_node<VoidPointer> >::value
	196	>::value >= 1)
	197	>
	198	{};
	199
	200	} //namespace intrusive
	201	} //namespace boost
	202
	203	#include <boost/intrusive/detail/config_end.hpp>
	204
	205	#endif //BOOST_INTRUSIVE_RBTREE_NODE_HPP