boost/intrusive/detail/any_node_and_algorithms.hpp
///////////////////////////////////////////////////////////////////////////// // // (C) Copyright Ion Gaztanaga 2006-2008 // // 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> 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) { return node_ptr(&static_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 { 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; } #if defined(__EDG__) && defined(__STD_STRICT_ANSI) // For compilers checking the full source code at compile time, regardless // of whether the code is instantiated or not, we turn the compile error // below into a link error. static void unlink(node_ptr); static void swap_nodes(node_ptr l, node_ptr r); #else static void unlink(node_ptr) { //Auto-unlink hooks and unlink() call for safe hooks are not //available for any hooks!!! any_algorithms<VoidPointer>::unlink_not_available_for_any_hooks(); } 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 from unlink them from the container any_algorithms<VoidPointer>::swap_nodes_not_available_for_any_hooks(); } #endif }; } //namespace intrusive } //namespace boost #include <boost/intrusive/detail/config_end.hpp> #endif //BOOST_INTRUSIVE_ANY_NODE_HPP