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

/////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Ion Gaztanaga 2007-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_AVLTREE_NODE_HPP
#define BOOST_INTRUSIVE_AVLTREE_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/avltree_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_avltree_node
{
   typedef typename pointer_rebind<VoidPointer, compact_avltree_node<VoidPointer> >::type       node_ptr;
   typedef typename pointer_rebind<VoidPointer, const compact_avltree_node<VoidPointer> >::type const_node_ptr;
   enum balance { negative_t, zero_t, positive_t };
   node_ptr parent_, left_, right_;
};

//This is the normal representation: 3 pointers + enum
template<class VoidPointer>
struct avltree_node
{
   typedef typename pointer_rebind<VoidPointer, avltree_node<VoidPointer> >::type         node_ptr;
   typedef typename pointer_rebind<VoidPointer, const avltree_node<VoidPointer> >::type   const_node_ptr;
   enum balance { negative_t, zero_t, positive_t };
   node_ptr parent_, left_, right_;
   balance balance_;
};

//This is the default node traits implementation
//using a node with 3 generic pointers plus an enum
template<class VoidPointer>
struct default_avltree_node_traits_impl
{
   typedef avltree_node<VoidPointer>      node;
   typedef typename node::node_ptr        node_ptr;
   typedef typename node::const_node_ptr  const_node_ptr;

   typedef typename node::balance balance;

   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 balance get_balance(const const_node_ptr & n)
   {  return n->balance_;  }

   BOOST_INTRUSIVE_FORCEINLINE static balance get_balance(const node_ptr & n)
   {  return n->balance_;  }

   BOOST_INTRUSIVE_FORCEINLINE static void set_balance(const node_ptr & n, balance b)
   {  n->balance_ = b;  }

   BOOST_INTRUSIVE_FORCEINLINE static balance negative()
   {  return node::negative_t;  }

   BOOST_INTRUSIVE_FORCEINLINE static balance zero()
   {  return node::zero_t;  }

   BOOST_INTRUSIVE_FORCEINLINE static balance positive()
   {  return node::positive_t;  }
};

//This is the compact node traits implementation
//using a node with 3 generic pointers
template<class VoidPointer>
struct compact_avltree_node_traits_impl
{
   typedef compact_avltree_node<VoidPointer> node;
   typedef typename node::node_ptr           node_ptr;
   typedef typename node::const_node_ptr     const_node_ptr;
   typedef typename node::balance balance;

   typedef pointer_plus_bits<node_ptr, 2> ptr_bit;

   BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_parent(const 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 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 void set_right(node_ptr n, node_ptr r)
   {  n->right_ = r;  }

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

   BOOST_INTRUSIVE_FORCEINLINE static void set_balance(const node_ptr & n, balance b)
   {  ptr_bit::set_bits(n->parent_, (std::size_t)b);  }

   BOOST_INTRUSIVE_FORCEINLINE static balance negative()
   {  return node::negative_t;  }

   BOOST_INTRUSIVE_FORCEINLINE static balance zero()
   {  return node::zero_t;  }

   BOOST_INTRUSIVE_FORCEINLINE static balance positive()
   {  return node::positive_t;  }
};

//Dispatches the implementation based on the boolean
template<class VoidPointer, bool Compact>
struct avltree_node_traits_dispatch
   :  public default_avltree_node_traits_impl<VoidPointer>
{};

template<class VoidPointer>
struct avltree_node_traits_dispatch<VoidPointer, true>
   :  public compact_avltree_node_traits_impl<VoidPointer>
{};

//Inherit from rbtree_node_traits_dispatch depending on the embedding capabilities
template<class VoidPointer, bool OptimizeSize = false>
struct avltree_node_traits
   :  public avltree_node_traits_dispatch
         < VoidPointer
         , OptimizeSize &&
            max_pointer_plus_bits
            < VoidPointer
            , detail::alignment_of<compact_avltree_node<VoidPointer> >::value
            >::value >= 2u
         >
{};

} //namespace intrusive
} //namespace boost

#include <boost/intrusive/detail/config_end.hpp>

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