X-Git-Url: http://g0dil.de/git?a=blobdiff_plain;f=senf%2Fboost_intrusive%2Fislist_hook.hpp;fp=senf%2Fboost_intrusive%2Fislist_hook.hpp;h=206103de26054e460af66d34adbc0c24f0bdbba6;hb=8f1ff66f5b7d10cfc6d35fb72267bc2fb3b588f7;hp=0000000000000000000000000000000000000000;hpb=fbd3d0ff298683f08b59f25288d8c243e03b206c;p=senf.git diff --git a/senf/boost_intrusive/islist_hook.hpp b/senf/boost_intrusive/islist_hook.hpp new file mode 100644 index 0000000..206103d --- /dev/null +++ b/senf/boost_intrusive/islist_hook.hpp @@ -0,0 +1,715 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Olaf Krzikalla 2004-2006. +// (C) Copyright Ion Gaztañaga 2006-2007 +// +// 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_ISLIST_HOOK_HPP +#define BOOST_INTRUSIVE_ISLIST_HOOK_HPP + +#include "detail/config_begin.hpp" +#include "detail/utilities.hpp" +#include "detail/pointer_type.hpp" +#include "detail/pointer_to_other.hpp" +#include "detail/slist_node.hpp" +#include "slist_algorithms.hpp" +#include "linking_policy.hpp" +#include +#include + +namespace boost { +namespace intrusive { + +//! Derive a class from islist_base_hook in order to store objects in +//! in an islist. islist_base_hook holds the data necessary to maintain the +//! list and provides an appropriate value_traits class for islist. +//! +//! The first integer template argument defines a tag to identify the node. +//! The same tag value can be used in different classes, but if a class is +//! derived from more than one islist_base_hook, then each islist_base_hook needs its +//! unique tag. +//! +//! The second boolean template parameter will activate the safe-mode checks +//! if it's configured as "true". +//! +//! The third argument is the pointer type that will be used internally in the hook +//! and the islist configured from this hook. +template +class islist_base_hook + : private detail::slist_node_traits::node +{ + public: + typedef detail::slist_node_traits node_traits; + enum { linking_policy = SafeMode? safe_mode_link : normal_link}; + + private: + typedef slist_algorithms node_algorithms; + + public: + typedef typename node_traits::node node; + typedef islist_base_hook + this_type; + typedef typename boost::pointer_to_other + ::type node_ptr; + typedef typename boost::pointer_to_other + ::type const_node_ptr; + typedef typename boost::pointer_to_other + ::type this_type_ptr; + typedef typename boost::pointer_to_other + ::type const_this_type_ptr; + + private: + node_ptr this_as_node() + { return node_ptr(static_cast(this)); } + + const_node_ptr this_as_node() const + { return const_node_ptr(static_cast(this)); } + + public: + + //! Effects: If SafeMode is true initializes the node + //! to an unlinked state. + //! + //! Throws: Nothing. + islist_base_hook() + : node_traits::node() + { + if(SafeMode){ + node_algorithms::init(this_as_node()); + } + } + + //! Effects: If SafeMode is true initializes the node + //! to an unlinked state. The argument is ignored. + //! + //! Throws: Nothing. + //! + //! Rationale: Providing a copy-constructor + //! makes classes using islist_base_hook STL-compliant without forcing the + //! user to do some additional work. "swap" can be used to emulate + //! move-semantics. + islist_base_hook(const islist_base_hook& ) + : node_traits::node() + { + if(SafeMode){ + node_algorithms::init(this_as_node()); + } + } + + //! Effects: If SafeMode is true, an assertion is raised + //! if the node is still linked. After that, the node is initialized + //! to an unlinked state. The argument is ignored. + //! + //! Throws: Nothing. + //! + //! Rationale: Providing an assignment operator + //! makes classes using islist_base_hook STL-compliant without forcing the + //! user to do some additional work. "swap" can be used to emulate + //! move-semantics. + islist_base_hook& operator=(const islist_base_hook& ) + { + if(SafeMode){ + BOOST_ASSERT(!this->linked()); + } + return *this; + } + + //! Effects: If SafeMode is set to false, the destructor does + //! nothing (ie. no code is generated). If SafeMode is true and the + //! object is stored in an islist an assertion is raised. + //! + //! Throws: Nothing. + ~islist_base_hook() + { + if(SafeMode){ + BOOST_ASSERT(!this->linked()); + } + } + + //! Effects: Swapping two nodes swaps the position of the elements + //! related to those nodes in one or two containers. That is, if the node + //! this is part of the element e1, the node x is part of the element e2 + //! and both elements are included in the containers s1 and s2, then after + //! the swap-operation e1 is in s2 at the position of e2 and e2 is in s1 + //! at the position of e1. If one element is not in a container, then + //! after the swap-operation the other element is not in a container. + //! Iterators to e1 and e2 related to those nodes are invalidated. + //! + //! Complexity: Linear + //! + //! Throws: Nothing. + void swap_nodes(islist_base_hook& other) + { node_algorithms::swap_nodes(this_as_node(), other.this_as_node()); } + + //! Precondition: The hook must be in safe-mode. + //! + //! Returns: true, if the node belongs to a container, false + //! otherwise. This function can be used to test whether islist::current + //! will return a valid iterator. + //! + //! Complexity: Constant + bool linked() const + { + //linked() can be only used in safe-mode + BOOST_ASSERT(SafeMode); + return !node_algorithms::unique(this_as_node()); + } + + //! The value_traits class is used as the first template argument for islist. + //! The template argument T defines the class type stored in islist. Objects + //! of type T and of types derived from T can be stored. T doesn't need to be + //! copy-constructible or assignable. + template + struct value_traits + : detail::derivation_value_traits + {}; + + //! Effects: Converts a pointer to a node into + //! a pointer to the hook that holds that node. + //! + //! Throws: Nothing. + static this_type_ptr to_hook_ptr(node_ptr p) + { + using boost::get_pointer; + return this_type_ptr(static_cast (get_pointer(p))); + } + + //! Effects: Converts a const pointer to a node stored in a container into + //! a const pointer to the hook that holds that node. + //! + //! Throws: Nothing. + static const_this_type_ptr to_hook_ptr(const_node_ptr p) + { + using boost::get_pointer; + return this_type_ptr(static_cast (get_pointer(p))); + } + + //! Effects: Returns a pointer to the node that this hook holds. + //! + //! Throws: Nothing. + node_ptr to_node_ptr() + { return this_as_node(); } + + //! Effects: Returns a const pointer to the node that this hook holds. + //! + //! Throws: Nothing. + const_node_ptr to_node_ptr() const + { return this_as_node(); } +}; + + +//! Derive a class from islist_auto_base_hook in order to store objects in +//! in an islist. islist_auto_base_hook holds the data necessary to maintain the +//! list and provides an appropriate value_traits class for islist. +//! +//! The difference between islist_auto_base_hook and islist_base_hook is that +//! islist_auto_base_hook removes itself automatically from the container +//! in the assignment operator and the destructor. It also provides a new +//! "unlink" method so that the user can unlink its class without using +//! the container. +//! +//! islist_auto_base_hook can only be used with non constant-time islists. +//! +//! The first integer template argument defines a tag to identify the node. +//! The same tag value can be used in different classes, but if a class is +//! derived from more than one islist_auto_base_hook, then each islist_auto_base_hook needs its +//! unique tag. +//! +//! The second argument is the pointer type that will be used internally in the hook +//! and the islist configured from this hook. +template +class islist_auto_base_hook + : private detail::slist_node_traits::node +{ + public: + typedef detail::slist_node_traits node_traits; + enum { linking_policy = auto_unlink }; + + private: + typedef slist_algorithms node_algorithms; + + public: + typedef islist_auto_base_hook + this_type; + typedef typename node_traits::node node; + typedef typename boost::pointer_to_other + ::type node_ptr; + typedef typename boost::pointer_to_other + ::type const_node_ptr; + typedef typename boost::pointer_to_other + ::type this_type_ptr; + typedef typename boost::pointer_to_other + ::type const_this_type_ptr; + + private: + node_ptr this_as_node() + { return node_ptr(static_cast(this)); } + + const_node_ptr this_as_node() const + { return const_node_ptr(static_cast(this)); } + + public: + + //! Effects: Initializes the node + //! to an unlinked state. + //! + //! Throws: Nothing. + islist_auto_base_hook() + : node_traits::node() + { node_algorithms::init(this_as_node()); } + + //! Effects: Initializes the node + //! to an unlinked state. The argument is ignored. + //! + //! Throws: Nothing. + //! + //! Rationale: Providing a copy-constructor + //! makes classes using islist_auto_base_hook STL-compliant without forcing the + //! user to do some additional work. + islist_auto_base_hook(const islist_auto_base_hook& ) + : node_traits::node() + { node_algorithms::init(this_as_node()); } + + //! Effects: Removes the node if it's inserted in a container. + //! The argument is ignored. + //! + //! Throws: Nothing. + //! + //! Rationale: Providing an assignment operator + //! makes classes using islist_auto_base_hook STL-compliant without forcing the + //! user to do some additional work. + islist_auto_base_hook& operator=(const islist_auto_base_hook& ) + { this->unlink(); return *this; } + + //! Effects: Removes the node if it's inserted in a container. + //! + //! Throws: Nothing. + ~islist_auto_base_hook() + { this->unlink(); } + + //! Effects: Swapping two nodes swaps the position of the elements + //! related to those nodes in one or two containers. That is, if the node + //! this is part of the element e1, the node x is part of the element e2 + //! and both elements are included in the containers s1 and s2, then after + //! the swap-operation e1 is in s2 at the position of e2 and e2 is in s1 + //! at the position of e1. If one element is not in a container, then + //! after the swap-operation the other element is not in a container. + //! Iterators to e1 and e2 related to those nodes are invalidated. + //! + //! Complexity: Linear + //! + //! Throws: Nothing. + void swap_nodes(islist_auto_base_hook& other) + { node_algorithms::swap_nodes(this_as_node(), other.this_as_node()); } + + //! Returns: true, if the node belongs to a container, false + //! otherwise. This function can be used to test whether islist::current + //! will return a valid iterator. + //! + //! Complexity: Constant + bool linked() const + { return !node_algorithms::unique(this_as_node()); } + + //! Effects: Removes the node if it's inserted in a container. + //! + //! Throws: Nothing. + void unlink() + { + node_algorithms::unlink(this_as_node()); + node_algorithms::init(this_as_node()); + } + + //! The value_traits class is used as the first template argument for islist. + //! The template argument T defines the class type stored in islist. Objects + //! of type T and of types derived from T can be stored. T doesn't need to be + //! copy-constructible or assignable. + template + struct value_traits + : detail::derivation_value_traits + {}; + + //! Effects: Converts a pointer to a node into + //! a pointer to the hook that holds that node. + //! + //! Throws: Nothing. + static this_type_ptr to_hook_ptr(node_ptr p) + { + using boost::get_pointer; + return this_type_ptr(static_cast (get_pointer(p))); + } + + //! Effects: Converts a const pointer to a node stored in a container into + //! a const pointer to the hook that holds that node. + //! + //! Throws: Nothing. + static const_this_type_ptr to_hook_ptr(const_node_ptr p) + { + using boost::get_pointer; + return this_type_ptr(static_cast (get_pointer(p))); + } + + //! Effects: Returns a pointer to the node that this hook holds. + //! + //! Throws: Nothing. + node_ptr to_node_ptr() + { return this_as_node(); } + + //! Effects: Returns a const pointer to the node that this hook holds. + //! + //! Throws: Nothing. + const_node_ptr to_node_ptr() const + { return this_as_node(); } +}; + + +//! Put a public data member islist_member_hook in order to store objects of this class in +//! an islist. islist_member_hook holds the data necessary for maintaining the list and +//! provides an appropriate value_traits class for islist. +//! +//! The template argument T defines the class type stored in islist. Objects of type +//! T and of types derived from T can be stored. T doesn't need to be +//! copy-constructible or assignable. +//! +//! The second boolean template parameter will activate the safe-mode checks +//! if it's configured as "true". +//! +//! The third argument is the pointer type that will be used internally in the hook +//! and the islist configured from this hook. +template +class islist_member_hook + : private detail::slist_node_traits::node +{ + public: + typedef detail::slist_node_traits node_traits; + enum { linking_policy = SafeMode? safe_mode_link : normal_link}; + + private: + typedef slist_algorithms node_algorithms; + + public: + typedef typename node_traits::node node; + typedef islist_member_hook this_type; + typedef typename boost::pointer_to_other + ::type node_ptr; + typedef typename boost::pointer_to_other + ::type const_node_ptr; + typedef typename boost::pointer_to_other + ::type this_type_ptr; + typedef typename boost::pointer_to_other + ::type const_this_type_ptr; + + private: + node_ptr this_as_node() + { return node_ptr(static_cast(this)); } + + const_node_ptr this_as_node() const + { return const_node_ptr(static_cast(this)); } + + public: + //! Effects: If SafeMode is true initializes the node + //! to an unlinked state. + //! + //! Throws: Nothing. + islist_member_hook() + : node_traits::node() + { + if(SafeMode){ + node_algorithms::init(this_as_node()); + } + } + + //! Effects: If SafeMode is true initializes the node + //! to an unlinked state. The argument is ignored. + //! + //! Throws: Nothing. + //! + //! Rationale: Providing a copy-constructor + //! makes classes using islist_member_hook STL-compliant without forcing the + //! user to do some additional work. "swap" can be used to emulate + //! move-semantics. + islist_member_hook(const islist_member_hook& ) + : node_traits::node() + { + if(SafeMode){ + node_algorithms::init(this_as_node()); + } + } + + //! Effects: If SafeMode is true, an assertion is raised + //! if the node is still linked. After that, the node is initialized + //! to an unlinked state. The argument is ignored. + //! + //! Throws: Nothing. + //! + //! Rationale: Providing an assignment operator + //! makes classes using islist_member_hook STL-compliant without forcing the + //! user to do some additional work. "swap" can be used to emulate + //! move-semantics. + islist_member_hook& operator=(const islist_member_hook& ) + { + if(SafeMode){ + BOOST_ASSERT(!this->linked()); + } + return *this; + } + + //! Effects: If SafeMode is set to false, the destructor does + //! nothing (ie. no code is generated). If SafeMode is true and the + //! object is stored in an islist an assertion is raised. + //! + //! Throws: Nothing. + ~islist_member_hook() + { + if(SafeMode){ + BOOST_ASSERT(!this->linked()); + } + } + + //! Effects: Swapping two nodes swaps the position of the elements + //! related to those nodes in one or two containers. That is, if the node + //! this is part of the element e1, the node x is part of the element e2 + //! and both elements are included in the containers s1 and s2, then after + //! the swap-operation e1 is in s2 at the position of e2 and e2 is in s1 + //! at the position of e1. If one element is not in a container, then + //! after the swap-operation the other element is not in a container. + //! Iterators to e1 and e2 related to those nodes are invalidated. + //! + //! Complexity: Linear + //! + //! Throws: Nothing. + void swap_nodes(islist_member_hook& other) + { node_algorithms::swap_nodes(this_as_node(), other.this_as_node()); } + + //! Precondition: The hook must be in safe-mode. + //! + //! Returns: true, if the node belongs to a container, false + //! otherwise. This function can be used to test whether islist::current + //! will return a valid iterator. + //! + //! Complexity: Constant + bool linked() const + { + //We must be in safe-mode to know if we are really linked + //Otherwise, this would lead to an unknown state + BOOST_ASSERT(SafeMode); + return !node_algorithms::unique(this_as_node()); + } + + //! The value_traits class is used as the first template argument for islist. + //! The template argument is a pointer to member pointing to the node in + //! the class. Objects of type T and of types derived from T can be stored. + //! T doesn't need to be copy-constructible or assignable. + template + struct value_traits + : detail::member_value_traits + {}; + + //! Effects: Converts a pointer to a node into + //! a pointer to the hook that holds that node. + //! + //! Throws: Nothing. + static this_type_ptr to_hook_ptr(node_ptr p) + { + using boost::get_pointer; + return this_type_ptr(static_cast (get_pointer(p))); + } + + //! Effects: Converts a const pointer to a node stored in a container into + //! a const pointer to the hook that holds that node. + //! + //! Throws: Nothing. + static const_this_type_ptr to_hook_ptr(const_node_ptr p) + { + using boost::get_pointer; + return this_type_ptr(static_cast (get_pointer(p))); + } + + //! Effects: Returns a pointer to the node that this hook holds. + //! + //! Throws: Nothing. + node_ptr to_node_ptr() + { return this_as_node(); } + + //! Effects: Returns a const pointer to the node that this hook holds. + //! + //! Throws: Nothing. + const_node_ptr to_node_ptr() const + { return this_as_node(); } +}; + + +//! Put a public data member islist_auto_member_hook in order to store objects of this class in +//! an islist. islist_auto_member_hook holds the data necessary for maintaining the list and +//! provides an appropriate value_traits class for islist. +//! +//! The difference between islist_auto_member_hook and islist_member_hook is that +//! islist_auto_member_hook removes itself automatically from the container +//! in the assignment operator and the destructor. It also provides a new +//! "unlink" method so that the user can unlink its class without using +//! the container. +//! +//! islist_auto_member_hook can only be used with non constant-time islists. +//! +//! The first template argument T defines the class type stored in islist. Objects of +//! type T and of types derived from T can be stored. T doesn't need to be +//! copy-constructible or assignable. +//! +//! The second argument is the pointer type that will be used internally in the hook +//! and the islist configured from this hook. +template +class islist_auto_member_hook + : private detail::slist_node_traits::node +{ + public: + typedef detail::slist_node_traits node_traits; + enum { linking_policy = auto_unlink }; + + private: + typedef slist_algorithms node_algorithms; + + public: + typedef typename node_traits::node node; + typedef islist_auto_member_hook this_type; + typedef typename boost::pointer_to_other + ::type node_ptr; + typedef typename boost::pointer_to_other + ::type const_node_ptr; + typedef typename boost::pointer_to_other + ::type this_type_ptr; + typedef typename boost::pointer_to_other + ::type const_this_type_ptr; + + private: + node_ptr this_as_node() + { return node_ptr(static_cast(this)); } + + const_node_ptr this_as_node() const + { return const_node_ptr(static_cast(this)); } + + public: + //! Effects: Initializes the node + //! to an unlinked state. + //! + //! Throws: Nothing. + islist_auto_member_hook() + : node_traits::node() + { node_algorithms::init(this_as_node()); } + + //! Effects: Initializes the node + //! to an unlinked state. The argument is ignored. + //! + //! Throws: Nothing. + //! + //! Rationale: Providing a copy-constructor + //! makes classes using islist_auto_base_hook STL-compliant without forcing the + //! user to do some additional work. + islist_auto_member_hook(const islist_auto_member_hook& ) + : node_traits::node() + { node_algorithms::init(this_as_node()); } + + //! Effects: Removes the node if it's inserted in a container. + //! The argument is ignored. + //! + //! Throws: Nothing. + //! + //! Rationale: Providing an assignment operator + //! makes classes using islist_auto_base_hook STL-compliant without forcing the + //! user to do some additional work. + islist_auto_member_hook& operator=(const islist_auto_member_hook& ) + { this->unlink(); return *this; } + + //! Effects: If SafeMode is set to false, the destructor does + //! nothing (ie. no code is generated). If SafeMode is true and the + //! object is stored in an islist an assertion is raised. + //! + //! Throws: Nothing. + ~islist_auto_member_hook() + { this->unlink(); } + + //! Effects: Swapping two nodes swaps the position of the elements + //! related to those nodes in one or two containers. That is, if the node + //! this is part of the element e1, the node x is part of the element e2 + //! and both elements are included in the containers s1 and s2, then after + //! the swap-operation e1 is in s2 at the position of e2 and e2 is in s1 + //! at the position of e1. If one element is not in a container, then + //! after the swap-operation the other element is not in a container. + //! Iterators to e1 and e2 related to those nodes are invalidated. + //! + //! Complexity: Constant + //! + //! Throws: Nothing. + void swap_nodes(islist_auto_member_hook& other) + { node_algorithms::swap_nodes(this_as_node(), other.this_as_node()); } + + //! Returns: true, if the node belongs to a container, false + //! otherwise. This function can be used to test whether islist::current + //! will return a valid iterator. + //! + //! Complexity: Constant + bool linked() const + { return !node_algorithms::unique(this_as_node()); } + + //! The value_traits class is used as the first template argument for islist. + //! The template argument is a pointer to member pointing to the node in + //! the class. Objects of type T and of types derived from T can be stored. + //! T doesn't need to be copy-constructible or assignable. + template + struct value_traits + : detail::member_value_traits + {}; + + //! Effects: Removes the node if it's inserted in a container. + //! + //! Throws: Nothing. + void unlink() + { + node_algorithms::unlink(this_as_node()); + node_algorithms::init(this_as_node()); + } + + //! Effects: Converts a pointer to a node into + //! a pointer to the hook that holds that node. + //! + //! Throws: Nothing. + static this_type_ptr to_hook_ptr(node_ptr p) + { + using boost::get_pointer; + return this_type_ptr(static_cast (get_pointer(p))); + } + + //! Effects: Converts a const pointer to a node stored in a container into + //! a const pointer to the hook that holds that node. + //! + //! Throws: Nothing. + static const_this_type_ptr to_hook_ptr(const_node_ptr p) + { + using boost::get_pointer; + return const_this_type_ptr(static_cast (get_pointer(p))); + } + + //! Effects: Returns a pointer to the node that this hook holds. + //! + //! Throws: Nothing. + node_ptr to_node_ptr() + { return this_as_node(); } + + //! Effects: Returns a const pointer to the node that this hook holds. + //! + //! Throws: Nothing. + const_node_ptr to_node_ptr() const + { return this_as_node(); } +}; + +} //namespace intrusive +} //namespace boost + +#include + +#endif //BOOST_INTRUSIVE_ISLIST_HOOK_HPP