///////////////////////////////////////////////////////////////////////////// | |
// | |
// (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_ANY_NODE_HPP | |
#define BOOST_INTRUSIVE_ANY_NODE_HPP | |
#include <boost/intrusive/detail/config_begin.hpp> | |
#include <iterator> | |
#include <boost/intrusive/detail/assert.hpp> | |
#include <boost/intrusive/detail/pointer_to_other.hpp> | |
#include <cstddef> | |
#include <boost/intrusive/detail/mpl.hpp> | |
#include <boost/pointer_cast.hpp> | |
namespace boost { | |
namespace intrusive { | |
template<class VoidPointer> | |
struct any_node | |
{ | |
typedef typename boost::pointer_to_other | |
<VoidPointer, any_node>::type node_ptr; | |
node_ptr node_ptr_1; | |
node_ptr node_ptr_2; | |
node_ptr node_ptr_3; | |
std::size_t size_t_1; | |
}; | |
template<class VoidPointer> | |
struct any_list_node_traits | |
{ | |
typedef any_node<VoidPointer> node; | |
typedef typename boost::pointer_to_other | |
<VoidPointer, node>::type node_ptr; | |
typedef typename boost::pointer_to_other | |
<VoidPointer, const node>::type const_node_ptr; | |
static node_ptr get_next(const_node_ptr n) | |
{ return n->node_ptr_1; } | |
static void set_next(node_ptr n, node_ptr next) | |
{ n->node_ptr_1 = next; } | |
static node_ptr get_previous(const_node_ptr n) | |
{ return n->node_ptr_2; } | |
static void set_previous(node_ptr n, node_ptr prev) | |
{ n->node_ptr_2 = prev; } | |
}; | |
template<class VoidPointer> | |
struct any_slist_node_traits | |
{ | |
typedef any_node<VoidPointer> node; | |
typedef typename boost::pointer_to_other | |
<VoidPointer, node>::type node_ptr; | |
typedef typename boost::pointer_to_other | |
<VoidPointer, const node>::type const_node_ptr; | |
static node_ptr get_next(const_node_ptr n) | |
{ return n->node_ptr_1; } | |
static void set_next(node_ptr n, node_ptr next) | |
{ n->node_ptr_1 = next; } | |
}; | |
template<class VoidPointer> | |
struct any_unordered_node_traits | |
: public any_slist_node_traits<VoidPointer> | |
{ | |
typedef any_slist_node_traits<VoidPointer> reduced_slist_node_traits; | |
typedef typename reduced_slist_node_traits::node node; | |
typedef typename reduced_slist_node_traits::node_ptr node_ptr; | |
typedef typename reduced_slist_node_traits::const_node_ptr const_node_ptr; | |
static const bool store_hash = true; | |
static const bool optimize_multikey = true; | |
static node_ptr get_next(const_node_ptr n) | |
{ | |
using ::boost::static_pointer_cast; | |
return static_pointer_cast<node>(n->node_ptr_1); | |
} | |
static void set_next(node_ptr n, node_ptr next) | |
{ n->node_ptr_1 = next; } | |
static node_ptr get_prev_in_group(const_node_ptr n) | |
{ return n->node_ptr_2; } | |
static void set_prev_in_group(node_ptr n, node_ptr prev) | |
{ n->node_ptr_2 = prev; } | |
static std::size_t get_hash(const_node_ptr n) | |
{ return n->size_t_1; } | |
static void set_hash(node_ptr n, std::size_t h) | |
{ n->size_t_1 = h; } | |
}; | |
template<class VoidPointer> | |
struct any_rbtree_node_traits | |
{ | |
typedef any_node<VoidPointer> node; | |
typedef typename boost::pointer_to_other | |
<VoidPointer, node>::type node_ptr; | |
typedef typename boost::pointer_to_other | |
<VoidPointer, const node>::type const_node_ptr; | |
typedef std::size_t color; | |
static node_ptr get_parent(const_node_ptr n) | |
{ return n->node_ptr_1; } | |
static void set_parent(node_ptr n, node_ptr p) | |
{ n->node_ptr_1 = p; } | |
static node_ptr get_left(const_node_ptr n) | |
{ return n->node_ptr_2; } | |
static void set_left(node_ptr n, node_ptr l) | |
{ n->node_ptr_2 = l; } | |
static node_ptr get_right(const_node_ptr n) | |
{ return n->node_ptr_3; } | |
static void set_right(node_ptr n, node_ptr r) | |
{ n->node_ptr_3 = r; } | |
static color get_color(const_node_ptr n) | |
{ return n->size_t_1; } | |
static void set_color(node_ptr n, color c) | |
{ n->size_t_1 = c; } | |
static color black() | |
{ return 0u; } | |
static color red() | |
{ return 1u; } | |
}; | |
template<class VoidPointer> | |
struct any_avltree_node_traits | |
{ | |
typedef any_node<VoidPointer> node; | |
typedef typename boost::pointer_to_other | |
<VoidPointer, node>::type node_ptr; | |
typedef typename boost::pointer_to_other | |
<VoidPointer, const node>::type const_node_ptr; | |
typedef std::size_t balance; | |
static node_ptr get_parent(const_node_ptr n) | |
{ return n->node_ptr_1; } | |
static void set_parent(node_ptr n, node_ptr p) | |
{ n->node_ptr_1 = p; } | |
static node_ptr get_left(const_node_ptr n) | |
{ return n->node_ptr_2; } | |
static void set_left(node_ptr n, node_ptr l) | |
{ n->node_ptr_2 = l; } | |
static node_ptr get_right(const_node_ptr n) | |
{ return n->node_ptr_3; } | |
static void set_right(node_ptr n, node_ptr r) | |
{ n->node_ptr_3 = r; } | |
static balance get_balance(const_node_ptr n) | |
{ return n->size_t_1; } | |
static void set_balance(node_ptr n, balance b) | |
{ n->size_t_1 = b; } | |
static balance negative() | |
{ return 0u; } | |
static balance zero() | |
{ return 1u; } | |
static balance positive() | |
{ return 2u; } | |
}; | |
template<class VoidPointer> | |
struct any_tree_node_traits | |
{ | |
typedef any_node<VoidPointer> node; | |
typedef typename boost::pointer_to_other | |
<VoidPointer, node>::type node_ptr; | |
typedef typename boost::pointer_to_other | |
<VoidPointer, const node>::type const_node_ptr; | |
static node_ptr get_parent(const_node_ptr n) | |
{ return n->node_ptr_1; } | |
static void set_parent(node_ptr n, node_ptr p) | |
{ n->node_ptr_1 = p; } | |
static node_ptr get_left(const_node_ptr n) | |
{ return n->node_ptr_2; } | |
static void set_left(node_ptr n, node_ptr l) | |
{ n->node_ptr_2 = l; } | |
static node_ptr get_right(const_node_ptr n) | |
{ return n->node_ptr_3; } | |
static void set_right(node_ptr n, node_ptr r) | |
{ n->node_ptr_3 = r; } | |
}; | |
template<class VoidPointer> | |
class any_node_traits | |
{ | |
public: | |
typedef any_node<VoidPointer> node; | |
typedef typename boost::pointer_to_other | |
<VoidPointer, node>::type node_ptr; | |
typedef typename boost::pointer_to_other | |
<VoidPointer, const node>::type const_node_ptr; | |
}; | |
template<class VoidPointer> | |
class any_algorithms | |
{ | |
template <class T> | |
static void function_not_available_for_any_hooks(typename detail::enable_if<detail::is_same<T, bool> >::type) | |
{} | |
public: | |
typedef any_node<VoidPointer> node; | |
typedef typename boost::pointer_to_other | |
<VoidPointer, node>::type node_ptr; | |
typedef typename boost::pointer_to_other | |
<VoidPointer, const node>::type const_node_ptr; | |
typedef any_node_traits<VoidPointer> node_traits; | |
//! <b>Requires</b>: node must not be part of any tree. | |
//! | |
//! <b>Effects</b>: After the function unique(node) == true. | |
//! | |
//! <b>Complexity</b>: Constant. | |
//! | |
//! <b>Throws</b>: Nothing. | |
//! | |
//! <b>Nodes</b>: If node is inserted in a tree, this function corrupts the tree. | |
static void init(node_ptr node) | |
{ node->node_ptr_1 = 0; }; | |
//! <b>Effects</b>: Returns true if node is in the same state as if called init(node) | |
//! | |
//! <b>Complexity</b>: Constant. | |
//! | |
//! <b>Throws</b>: Nothing. | |
static bool inited(const_node_ptr node) | |
{ return !node->node_ptr_1; }; | |
static bool unique(const_node_ptr node) | |
{ return 0 == node->node_ptr_1; } | |
static void unlink(node_ptr) | |
{ | |
//Auto-unlink hooks and unlink() are not available for any hooks | |
any_algorithms<VoidPointer>::template function_not_available_for_any_hooks<node_ptr>(); | |
} | |
static void swap_nodes(node_ptr l, node_ptr r) | |
{ | |
//Any nodes have no swap_nodes capability because they don't know | |
//what algorithm they must use to unlink the node from the container | |
any_algorithms<VoidPointer>::template function_not_available_for_any_hooks<node_ptr>(); | |
} | |
}; | |
} //namespace intrusive | |
} //namespace boost | |
#include <boost/intrusive/detail/config_end.hpp> | |
#endif //BOOST_INTRUSIVE_ANY_NODE_HPP |