Chris@16: /////////////////////////////////////////////////////////////////////////////
Chris@16: //
Chris@16: // (C) Copyright Ion Gaztanaga 2007-2013
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0.
Chris@16: //    (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: //          http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //
Chris@16: // See http://www.boost.org/libs/intrusive for documentation.
Chris@16: //
Chris@16: /////////////////////////////////////////////////////////////////////////////
Chris@16: 
Chris@16: #ifndef BOOST_INTRUSIVE_AVLTREE_NODE_HPP
Chris@16: #define BOOST_INTRUSIVE_AVLTREE_NODE_HPP
Chris@16: 
Chris@101: #ifndef BOOST_CONFIG_HPP
Chris@101: #  include <boost/config.hpp>
Chris@101: #endif
Chris@101: 
Chris@101: #if defined(BOOST_HAS_PRAGMA_ONCE)
Chris@101: #  pragma once
Chris@101: #endif
Chris@101: 
Chris@16: #include <boost/intrusive/detail/config_begin.hpp>
Chris@101: #include <boost/intrusive/pointer_rebind.hpp>
Chris@16: #include <boost/intrusive/avltree_algorithms.hpp>
Chris@16: #include <boost/intrusive/pointer_plus_bits.hpp>
Chris@16: #include <boost/intrusive/detail/mpl.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: namespace intrusive {
Chris@16: 
Chris@16: /////////////////////////////////////////////////////////////////////////////
Chris@16: //                                                                         //
Chris@16: //                Generic node_traits for any pointer type                 //
Chris@16: //                                                                         //
Chris@16: /////////////////////////////////////////////////////////////////////////////
Chris@16: 
Chris@16: //This is the compact representation: 3 pointers
Chris@16: template<class VoidPointer>
Chris@16: struct compact_avltree_node
Chris@16: {
Chris@101:    typedef typename pointer_rebind<VoidPointer, compact_avltree_node<VoidPointer> >::type       node_ptr;
Chris@101:    typedef typename pointer_rebind<VoidPointer, const compact_avltree_node<VoidPointer> >::type const_node_ptr;
Chris@16:    enum balance { negative_t, zero_t, positive_t };
Chris@16:    node_ptr parent_, left_, right_;
Chris@16: };
Chris@16: 
Chris@16: //This is the normal representation: 3 pointers + enum
Chris@16: template<class VoidPointer>
Chris@16: struct avltree_node
Chris@16: {
Chris@101:    typedef typename pointer_rebind<VoidPointer, avltree_node<VoidPointer> >::type         node_ptr;
Chris@101:    typedef typename pointer_rebind<VoidPointer, const avltree_node<VoidPointer> >::type   const_node_ptr;
Chris@16:    enum balance { negative_t, zero_t, positive_t };
Chris@16:    node_ptr parent_, left_, right_;
Chris@16:    balance balance_;
Chris@16: };
Chris@16: 
Chris@16: //This is the default node traits implementation
Chris@16: //using a node with 3 generic pointers plus an enum
Chris@16: template<class VoidPointer>
Chris@16: struct default_avltree_node_traits_impl
Chris@16: {
Chris@16:    typedef avltree_node<VoidPointer> node;
Chris@101:    typedef typename node::node_ptr        node_ptr;
Chris@101:    typedef typename node::const_node_ptr  const_node_ptr;
Chris@16: 
Chris@16:    typedef typename node::balance balance;
Chris@16: 
Chris@16:    static node_ptr get_parent(const const_node_ptr & n)
Chris@16:    {  return n->parent_;  }
Chris@16: 
Chris@16:    static node_ptr get_parent(const node_ptr & n)
Chris@16:    {  return n->parent_;  }
Chris@16: 
Chris@16:    static void set_parent(const node_ptr & n, const node_ptr & p)
Chris@16:    {  n->parent_ = p;  }
Chris@16: 
Chris@16:    static node_ptr get_left(const const_node_ptr & n)
Chris@16:    {  return n->left_;  }
Chris@16: 
Chris@16:    static node_ptr get_left(const node_ptr & n)
Chris@16:    {  return n->left_;  }
Chris@16: 
Chris@16:    static void set_left(const node_ptr & n, const node_ptr & l)
Chris@16:    {  n->left_ = l;  }
Chris@16: 
Chris@16:    static node_ptr get_right(const const_node_ptr & n)
Chris@16:    {  return n->right_;  }
Chris@16: 
Chris@16:    static node_ptr get_right(const node_ptr & n)
Chris@16:    {  return n->right_;  }
Chris@16: 
Chris@16:    static void set_right(const node_ptr & n, const node_ptr & r)
Chris@16:    {  n->right_ = r;  }
Chris@16: 
Chris@16:    static balance get_balance(const const_node_ptr & n)
Chris@16:    {  return n->balance_;  }
Chris@16: 
Chris@16:    static balance get_balance(const node_ptr & n)
Chris@16:    {  return n->balance_;  }
Chris@16: 
Chris@16:    static void set_balance(const node_ptr & n, balance b)
Chris@16:    {  n->balance_ = b;  }
Chris@16: 
Chris@16:    static balance negative()
Chris@16:    {  return node::negative_t;  }
Chris@16: 
Chris@16:    static balance zero()
Chris@16:    {  return node::zero_t;  }
Chris@16: 
Chris@16:    static balance positive()
Chris@16:    {  return node::positive_t;  }
Chris@16: };
Chris@16: 
Chris@16: //This is the compact node traits implementation
Chris@16: //using a node with 3 generic pointers
Chris@16: template<class VoidPointer>
Chris@16: struct compact_avltree_node_traits_impl
Chris@16: {
Chris@16:    typedef compact_avltree_node<VoidPointer> node;
Chris@101:    typedef typename node::node_ptr        node_ptr;
Chris@101:    typedef typename node::const_node_ptr  const_node_ptr;
Chris@16:    typedef typename node::balance balance;
Chris@16: 
Chris@16:    typedef pointer_plus_bits<node_ptr, 2> ptr_bit;
Chris@16: 
Chris@16:    static node_ptr get_parent(const const_node_ptr & n)
Chris@16:    {  return ptr_bit::get_pointer(n->parent_);  }
Chris@16: 
Chris@16:    static void set_parent(const node_ptr & n, const node_ptr & p)
Chris@16:    {  ptr_bit::set_pointer(n->parent_, p);  }
Chris@16: 
Chris@16:    static node_ptr get_left(const const_node_ptr & n)
Chris@16:    {  return n->left_;  }
Chris@16: 
Chris@16:    static void set_left(const node_ptr & n, const node_ptr & l)
Chris@16:    {  n->left_ = l;  }
Chris@16: 
Chris@16:    static node_ptr get_right(const const_node_ptr & n)
Chris@16:    {  return n->right_;  }
Chris@16: 
Chris@16:    static void set_right(const node_ptr & n, const node_ptr & r)
Chris@16:    {  n->right_ = r;  }
Chris@16: 
Chris@16:    static balance get_balance(const const_node_ptr & n)
Chris@16:    {  return (balance)ptr_bit::get_bits(n->parent_);  }
Chris@16: 
Chris@16:    static void set_balance(const node_ptr & n, balance b)
Chris@16:    {  ptr_bit::set_bits(n->parent_, (std::size_t)b);  }
Chris@16: 
Chris@16:    static balance negative()
Chris@16:    {  return node::negative_t;  }
Chris@16: 
Chris@16:    static balance zero()
Chris@16:    {  return node::zero_t;  }
Chris@16: 
Chris@16:    static balance positive()
Chris@16:    {  return node::positive_t;  }
Chris@16: };
Chris@16: 
Chris@16: //Dispatches the implementation based on the boolean
Chris@16: template<class VoidPointer, bool Compact>
Chris@16: struct avltree_node_traits_dispatch
Chris@16:    :  public default_avltree_node_traits_impl<VoidPointer>
Chris@16: {};
Chris@16: 
Chris@16: template<class VoidPointer>
Chris@16: struct avltree_node_traits_dispatch<VoidPointer, true>
Chris@16:    :  public compact_avltree_node_traits_impl<VoidPointer>
Chris@16: {};
Chris@16: 
Chris@101: //Inherit from rbtree_node_traits_dispatch depending on the embedding capabilities
Chris@16: template<class VoidPointer, bool OptimizeSize = false>
Chris@16: struct avltree_node_traits
Chris@16:    :  public avltree_node_traits_dispatch
Chris@16:          < VoidPointer
Chris@16:          , OptimizeSize &&
Chris@16:             max_pointer_plus_bits
Chris@16:             < VoidPointer
Chris@16:             , detail::alignment_of<compact_avltree_node<VoidPointer> >::value
Chris@16:             >::value >= 2u
Chris@16:          >
Chris@16: {};
Chris@16: 
Chris@16: } //namespace intrusive
Chris@16: } //namespace boost
Chris@16: 
Chris@16: #include <boost/intrusive/detail/config_end.hpp>
Chris@16: 
Chris@16: #endif //BOOST_INTRUSIVE_AVLTREE_NODE_HPP