Swiftdiff options
Diffstat (limited to '3rdParty/Boost/src/boost/intrusive')
25 files changed, 7135 insertions, 180 deletions
diff --git a/3rdParty/Boost/src/boost/intrusive/circular_slist_algorithms.hpp b/3rdParty/Boost/src/boost/intrusive/circular_slist_algorithms.hpp new file mode 100644 index 0000000..d41dac4 --- /dev/null +++ b/3rdParty/Boost/src/boost/intrusive/circular_slist_algorithms.hpp @@ -0,0 +1,403 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Olaf Krzikalla 2004-2006. +// (C) Copyright Ion Gaztanaga 2006-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_CIRCULAR_SLIST_ALGORITHMS_HPP +#define BOOST_INTRUSIVE_CIRCULAR_SLIST_ALGORITHMS_HPP + +#include <boost/intrusive/detail/config_begin.hpp> +#include <boost/intrusive/intrusive_fwd.hpp> +#include <boost/intrusive/detail/common_slist_algorithms.hpp> +#include <boost/intrusive/detail/assert.hpp> +#include <boost/intrusive/detail/utilities.hpp> +#include <cstddef> + +namespace boost { +namespace intrusive { + +//! circular_slist_algorithms provides basic algorithms to manipulate nodes +//! forming a circular singly linked list. An empty circular list is formed by a node +//! whose pointer to the next node points to itself. +//! +//! circular_slist_algorithms is configured with a NodeTraits class, which encapsulates the +//! information about the node to be manipulated. NodeTraits must support the +//! following interface: +//! +//! <b>Typedefs</b>: +//! +//! <tt>node</tt>: The type of the node that forms the circular list +//! +//! <tt>node_ptr</tt>: A pointer to a node +//! +//! <tt>const_node_ptr</tt>: A pointer to a const node +//! +//! <b>Static functions</b>: +//! +//! <tt>static node_ptr get_next(const_node_ptr n);</tt> +//! +//! <tt>static void set_next(node_ptr n, node_ptr next);</tt> +template<class NodeTraits> +class circular_slist_algorithms + /// @cond + : public detail::common_slist_algorithms<NodeTraits> + /// @endcond +{ + /// @cond + typedef detail::common_slist_algorithms<NodeTraits> base_t; + /// @endcond + public: + typedef typename NodeTraits::node node; + typedef typename NodeTraits::node_ptr node_ptr; + typedef typename NodeTraits::const_node_ptr const_node_ptr; + typedef NodeTraits node_traits; + + #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) + + //! <b>Effects</b>: Constructs an non-used list element, putting the next + //! pointer to null: + //! <tt>NodeTraits::get_next(this_node) == node_ptr()</tt> + //! + //! <b>Complexity</b>: Constant + //! + //! <b>Throws</b>: Nothing. + static void init(node_ptr this_node); + + //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list. + //! + //! <b>Effects</b>: Returns true is "this_node" is the only node of a circular list: + //! or it's a not inserted node: + //! <tt>return node_ptr() == NodeTraits::get_next(this_node) || NodeTraits::get_next(this_node) == this_node</tt> + //! + //! <b>Complexity</b>: Constant + //! + //! <b>Throws</b>: Nothing. + static bool unique(const_node_ptr this_node); + + //! <b>Effects</b>: Returns true is "this_node" has the same state as + //! if it was inited using "init(node_ptr)" + //! + //! <b>Complexity</b>: Constant + //! + //! <b>Throws</b>: Nothing. + static bool inited(const_node_ptr this_node); + + //! <b>Requires</b>: prev_node must be in a circular list or be an empty circular list. + //! + //! <b>Effects</b>: Unlinks the next node of prev_node from the circular list. + //! + //! <b>Complexity</b>: Constant + //! + //! <b>Throws</b>: Nothing. + static void unlink_after(node_ptr prev_node); + + //! <b>Requires</b>: prev_node and last_node must be in a circular list + //! or be an empty circular list. + //! + //! <b>Effects</b>: Unlinks the range (prev_node, last_node) from the circular list. + //! + //! <b>Complexity</b>: Constant + //! + //! <b>Throws</b>: Nothing. + static void unlink_after(node_ptr prev_node, node_ptr last_node); + + //! <b>Requires</b>: prev_node must be a node of a circular list. + //! + //! <b>Effects</b>: Links this_node after prev_node in the circular list. + //! + //! <b>Complexity</b>: Constant + //! + //! <b>Throws</b>: Nothing. + static void link_after(node_ptr prev_node, node_ptr this_node); + + //! <b>Requires</b>: b and e must be nodes of the same circular list or an empty range. + //! and p must be a node of a different circular list. + //! + //! <b>Effects</b>: Removes the nodes from (b, e] range from their circular list and inserts + //! them after p in p's circular list. + //! + //! <b>Complexity</b>: Constant + //! + //! <b>Throws</b>: Nothing. + static void transfer_after(node_ptr p, node_ptr b, node_ptr e); + + #endif //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) + + //! <b>Effects</b>: Constructs an empty list, making this_node the only + //! node of the circular list: + //! <tt>NodeTraits::get_next(this_node) == this_node</tt>. + //! + //! <b>Complexity</b>: Constant + //! + //! <b>Throws</b>: Nothing. + static void init_header(const node_ptr &this_node) + { NodeTraits::set_next(this_node, this_node); } + + //! <b>Requires</b>: this_node and prev_init_node must be in the same circular list. + //! + //! <b>Effects</b>: Returns the previous node of this_node in the circular list starting. + //! the search from prev_init_node. The first node checked for equality + //! is NodeTraits::get_next(prev_init_node). + //! + //! <b>Complexity</b>: Linear to the number of elements between prev_init_node and this_node. + //! + //! <b>Throws</b>: Nothing. + static node_ptr get_previous_node(const node_ptr &prev_init_node, const node_ptr &this_node) + { return base_t::get_previous_node(prev_init_node, this_node); } + + //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list. + //! + //! <b>Effects</b>: Returns the previous node of this_node in the circular list. + //! + //! <b>Complexity</b>: Linear to the number of elements in the circular list. + //! + //! <b>Throws</b>: Nothing. + static node_ptr get_previous_node(const node_ptr & this_node) + { return base_t::get_previous_node(this_node, this_node); } + + //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list. + //! + //! <b>Effects</b>: Returns the previous node of the previous node of this_node in the circular list. + //! + //! <b>Complexity</b>: Linear to the number of elements in the circular list. + //! + //! <b>Throws</b>: Nothing. + static node_ptr get_previous_previous_node(const node_ptr & this_node) + { return get_previous_previous_node(this_node, this_node); } + + //! <b>Requires</b>: this_node and p must be in the same circular list. + //! + //! <b>Effects</b>: Returns the previous node of the previous node of this_node in the + //! circular list starting. the search from p. The first node checked + //! for equality is NodeTraits::get_next((NodeTraits::get_next(p)). + //! + //! <b>Complexity</b>: Linear to the number of elements in the circular list. + //! + //! <b>Throws</b>: Nothing. + static node_ptr get_previous_previous_node(node_ptr p, const node_ptr & this_node) + { + node_ptr p_next = NodeTraits::get_next(p); + node_ptr p_next_next = NodeTraits::get_next(p_next); + while (this_node != p_next_next){ + p = p_next; + p_next = p_next_next; + p_next_next = NodeTraits::get_next(p_next); + } + return p; + } + + //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list. + //! + //! <b>Effects</b>: Returns the number of nodes in a circular list. If the circular list + //! is empty, returns 1. + //! + //! <b>Complexity</b>: Linear + //! + //! <b>Throws</b>: Nothing. + static std::size_t count(const const_node_ptr & this_node) + { + std::size_t result = 0; + const_node_ptr p = this_node; + do{ + p = NodeTraits::get_next(p); + ++result; + } while (p != this_node); + return result; + } + + //! <b>Requires</b>: this_node must be in a circular list, be an empty circular list or be inited. + //! + //! <b>Effects</b>: Unlinks the node from the circular list. + //! + //! <b>Complexity</b>: Linear to the number of elements in the circular list + //! + //! <b>Throws</b>: Nothing. + static void unlink(const node_ptr & this_node) + { + if(NodeTraits::get_next(this_node)) + base_t::unlink_after(get_previous_node(this_node)); + } + + //! <b>Requires</b>: nxt_node must be a node of a circular list. + //! + //! <b>Effects</b>: Links this_node before nxt_node in the circular list. + //! + //! <b>Complexity</b>: Linear to the number of elements in the circular list. + //! + //! <b>Throws</b>: Nothing. + static void link_before (const node_ptr & nxt_node, const node_ptr & this_node) + { base_t::link_after(get_previous_node(nxt_node), this_node); } + + //! <b>Requires</b>: this_node and other_node must be nodes inserted + //! in circular lists or be empty circular lists. + //! + //! <b>Effects</b>: Swaps the position of the nodes: this_node is inserted in + //! other_nodes position in the second circular list and the other_node is inserted + //! in this_node's position in the first circular list. + //! + //! <b>Complexity</b>: Linear to number of elements of both lists + //! + //! <b>Throws</b>: Nothing. + static void swap_nodes(const node_ptr & this_node, const node_ptr & other_node) + { + if (other_node == this_node) + return; + const node_ptr this_next = NodeTraits::get_next(this_node); + const node_ptr other_next = NodeTraits::get_next(other_node); + const bool this_null = !this_next; + const bool other_null = !other_next; + const bool this_empty = this_next == this_node; + const bool other_empty = other_next == other_node; + + if(!(other_null || other_empty)){ + NodeTraits::set_next(this_next == other_node ? other_node : get_previous_node(other_node), this_node ); + } + if(!(this_null | this_empty)){ + NodeTraits::set_next(other_next == this_node ? this_node : get_previous_node(this_node), other_node ); + } + NodeTraits::set_next(this_node, other_empty ? this_node : (other_next == this_node ? other_node : other_next) ); + NodeTraits::set_next(other_node, this_empty ? other_node : (this_next == other_node ? this_node : this_next ) ); + } + + //! <b>Effects</b>: Reverses the order of elements in the list. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: This function is linear to the contained elements. + static void reverse(const node_ptr & p) + { + node_ptr i = NodeTraits::get_next(p), e(p); + for (;;) { + node_ptr nxt(NodeTraits::get_next(i)); + if (nxt == e) + break; + base_t::transfer_after(e, i, nxt); + } + } + + //! <b>Effects</b>: Moves the node p n positions towards the end of the list. + //! + //! <b>Returns</b>: The previous node of p after the function if there has been any movement, + //! Null if n leads to no movement. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the number of elements plus the number moved positions. + static node_ptr move_backwards(const node_ptr & p, std::size_t n) + { + //Null shift, nothing to do + if(!n) return node_ptr(); + node_ptr first = NodeTraits::get_next(p); + + //count() == 1 or 2, nothing to do + if(NodeTraits::get_next(first) == p) + return node_ptr(); + + bool end_found = false; + node_ptr new_last = node_ptr(); + + //Now find the new last node according to the shift count. + //If we find p before finding the new last node + //unlink p, shortcut the search now that we know the size of the list + //and continue. + for(std::size_t i = 1; i <= n; ++i){ + new_last = first; + first = NodeTraits::get_next(first); + if(first == p){ + //Shortcut the shift with the modulo of the size of the list + n %= i; + if(!n) + return node_ptr(); + i = 0; + //Unlink p and continue the new first node search + first = NodeTraits::get_next(p); + base_t::unlink_after(new_last); + end_found = true; + } + } + + //If the p has not been found in the previous loop, find it + //starting in the new first node and unlink it + if(!end_found){ + base_t::unlink_after(base_t::get_previous_node(first, p)); + } + + //Now link p after the new last node + base_t::link_after(new_last, p); + return new_last; + } + + //! <b>Effects</b>: Moves the node p n positions towards the beginning of the list. + //! + //! <b>Returns</b>: The previous node of p after the function if there has been any movement, + //! Null if n leads equals to no movement. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the number of elements plus the number moved positions. + static node_ptr move_forward(const node_ptr & p, std::size_t n) + { + //Null shift, nothing to do + if(!n) return node_ptr(); + node_ptr first = node_traits::get_next(p); + + //count() == 1 or 2, nothing to do + if(node_traits::get_next(first) == p) return node_ptr(); + + //Iterate until p is found to know where the current last node is. + //If the shift count is less than the size of the list, we can also obtain + //the position of the new last node after the shift. + node_ptr old_last(first), next_to_it, new_last(p); + std::size_t distance = 1; + while(p != (next_to_it = node_traits::get_next(old_last))){ + if(++distance > n) + new_last = node_traits::get_next(new_last); + old_last = next_to_it; + } + //If the shift was bigger or equal than the size, obtain the equivalent + //forward shifts and find the new last node. + if(distance <= n){ + //Now find the equivalent forward shifts. + //Shortcut the shift with the modulo of the size of the list + std::size_t new_before_last_pos = (distance - (n % distance))% distance; + //If the shift is a multiple of the size there is nothing to do + if(!new_before_last_pos) return node_ptr(); + + for( new_last = p + ; new_before_last_pos-- + ; new_last = node_traits::get_next(new_last)){ + //empty + } + } + + //Now unlink p and link it after the new last node + base_t::unlink_after(old_last); + base_t::link_after(new_last, p); + return new_last; + } +}; + +/// @cond + +template<class NodeTraits> +struct get_algo<CircularSListAlgorithms, NodeTraits> +{ + typedef circular_slist_algorithms<NodeTraits> type; +}; + +/// @endcond + +} //namespace intrusive +} //namespace boost + +#include <boost/intrusive/detail/config_end.hpp> + +#endif //BOOST_INTRUSIVE_CIRCULAR_SLIST_ALGORITHMS_HPP diff --git a/3rdParty/Boost/src/boost/intrusive/detail/assert.hpp b/3rdParty/Boost/src/boost/intrusive/detail/assert.hpp new file mode 100644 index 0000000..d75d225 --- /dev/null +++ b/3rdParty/Boost/src/boost/intrusive/detail/assert.hpp @@ -0,0 +1,41 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-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_DETAIL_ASSERT_HPP +#define BOOST_INTRUSIVE_DETAIL_ASSERT_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#if !defined(BOOST_INTRUSIVE_INVARIANT_ASSERT) + #include <boost/assert.hpp> + #define BOOST_INTRUSIVE_INVARIANT_ASSERT BOOST_ASSERT +#elif defined(BOOST_INTRUSIVE_INVARIANT_ASSERT_INCLUDE) + #include BOOST_INTRUSIVE_INVARIANT_ASSERT_INCLUDE +#endif + +#if !defined(BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT) + #include <boost/assert.hpp> + #define BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT BOOST_ASSERT +#elif defined(BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT_INCLUDE) + #include BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT_INCLUDE +#endif + +#if !defined(BOOST_INTRUSIVE_SAFE_HOOK_DESTRUCTOR_ASSERT) + #include <boost/assert.hpp> + #define BOOST_INTRUSIVE_SAFE_HOOK_DESTRUCTOR_ASSERT BOOST_ASSERT +#elif defined(BOOST_INTRUSIVE_SAFE_HOOK_DESTRUCTOR_ASSERT_INCLUDE) + #include BOOST_INTRUSIVE_SAFE_HOOK_DESTRUCTOR_ASSERT_INCLUDE +#endif + +#endif //BOOST_INTRUSIVE_DETAIL_ASSERT_HPP diff --git a/3rdParty/Boost/src/boost/intrusive/detail/common_slist_algorithms.hpp b/3rdParty/Boost/src/boost/intrusive/detail/common_slist_algorithms.hpp new file mode 100644 index 0000000..0adbd50 --- /dev/null +++ b/3rdParty/Boost/src/boost/intrusive/detail/common_slist_algorithms.hpp @@ -0,0 +1,99 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (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_COMMON_SLIST_ALGORITHMS_HPP +#define BOOST_INTRUSIVE_COMMON_SLIST_ALGORITHMS_HPP + +#include <boost/intrusive/detail/config_begin.hpp> +#include <boost/intrusive/intrusive_fwd.hpp> +#include <boost/intrusive/detail/assert.hpp> +#include <cstddef> + +namespace boost { +namespace intrusive { +namespace detail { + +template<class NodeTraits> +class common_slist_algorithms +{ + public: + typedef typename NodeTraits::node node; + typedef typename NodeTraits::node_ptr node_ptr; + typedef typename NodeTraits::const_node_ptr const_node_ptr; + typedef NodeTraits node_traits; + + static node_ptr get_previous_node(node_ptr p, const node_ptr & this_node) + { + for( node_ptr p_next + ; this_node != (p_next = NodeTraits::get_next(p)) + ; p = p_next){ + //Logic error: possible use of linear lists with + //operations only permitted with lists + BOOST_INTRUSIVE_INVARIANT_ASSERT(p); + } + return p; + } + + static void init(const node_ptr & this_node) + { NodeTraits::set_next(this_node, node_ptr()); } + + static bool unique(const const_node_ptr & this_node) + { + node_ptr next = NodeTraits::get_next(this_node); + return !next || next == this_node; + } + + static bool inited(const const_node_ptr & this_node) + { return !NodeTraits::get_next(this_node); } + + static void unlink_after(const node_ptr & prev_node) + { + const_node_ptr this_node(NodeTraits::get_next(prev_node)); + NodeTraits::set_next(prev_node, NodeTraits::get_next(this_node)); + } + + static void unlink_after(const node_ptr & prev_node, const node_ptr & last_node) + { NodeTraits::set_next(prev_node, last_node); } + + static void link_after(const node_ptr & prev_node, const node_ptr & this_node) + { + NodeTraits::set_next(this_node, NodeTraits::get_next(prev_node)); + NodeTraits::set_next(prev_node, this_node); + } + + static void incorporate_after(const node_ptr & bp, const node_ptr & b, const node_ptr & be) + { + node_ptr p(NodeTraits::get_next(bp)); + NodeTraits::set_next(bp, b); + NodeTraits::set_next(be, p); + } + + static void transfer_after(const node_ptr & bp, const node_ptr & bb, const node_ptr & be) + { + if (bp != bb && bp != be && bb != be) { + node_ptr next_b = NodeTraits::get_next(bb); + node_ptr next_e = NodeTraits::get_next(be); + node_ptr next_p = NodeTraits::get_next(bp); + NodeTraits::set_next(bb, next_e); + NodeTraits::set_next(be, next_p); + NodeTraits::set_next(bp, next_b); + } + } +}; + +} //namespace detail +} //namespace intrusive +} //namespace boost + +#include <boost/intrusive/detail/config_end.hpp> + +#endif //BOOST_INTRUSIVE_COMMON_SLIST_ALGORITHMS_HPP diff --git a/3rdParty/Boost/src/boost/intrusive/detail/config_begin.hpp b/3rdParty/Boost/src/boost/intrusive/detail/config_begin.hpp index 7d15336..109a590 100644 --- a/3rdParty/Boost/src/boost/intrusive/detail/config_begin.hpp +++ b/3rdParty/Boost/src/boost/intrusive/detail/config_begin.hpp @@ -1,6 +1,6 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2006-2012 +// (C) Copyright Ion Gaztanaga 2006-2013 // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at diff --git a/3rdParty/Boost/src/boost/intrusive/detail/config_end.hpp b/3rdParty/Boost/src/boost/intrusive/detail/config_end.hpp index d653030..a081443 100644 --- a/3rdParty/Boost/src/boost/intrusive/detail/config_end.hpp +++ b/3rdParty/Boost/src/boost/intrusive/detail/config_end.hpp @@ -1,6 +1,6 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2006-2012 +// (C) Copyright Ion Gaztanaga 2006-2013 // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at diff --git a/3rdParty/Boost/src/boost/intrusive/detail/ebo_functor_holder.hpp b/3rdParty/Boost/src/boost/intrusive/detail/ebo_functor_holder.hpp new file mode 100644 index 0000000..3c2959b --- /dev/null +++ b/3rdParty/Boost/src/boost/intrusive/detail/ebo_functor_holder.hpp @@ -0,0 +1,95 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Joaquin M Lopez Munoz 2006-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_DETAIL_EBO_HOLDER_HPP +#define BOOST_INTRUSIVE_DETAIL_EBO_HOLDER_HPP + +#include <boost/intrusive/detail/config_begin.hpp> +#include <boost/intrusive/detail/mpl.hpp> + +namespace boost { +namespace intrusive { +namespace detail { + +template<typename T, bool IsEmpty = true> +class ebo_functor_holder_impl +{ + public: + ebo_functor_holder_impl() + {} + ebo_functor_holder_impl(const T& t) + : t_(t) + {} + template<class Arg1, class Arg2> + ebo_functor_holder_impl(const Arg1& arg1, const Arg2& arg2) + : t_(arg1, arg2) + {} + + T& get(){return t_;} + const T& get()const{return t_;} + + private: + T t_; +}; + +template<typename T> +class ebo_functor_holder_impl<T, false> + : public T +{ + public: + ebo_functor_holder_impl() + {} + ebo_functor_holder_impl(const T& t) + : T(t) + {} + template<class Arg1, class Arg2> + ebo_functor_holder_impl(const Arg1& arg1, const Arg2& arg2) + : T(arg1, arg2) + {} + + T& get(){return *this;} + const T& get()const{return *this;} +}; + +template<typename T> +class ebo_functor_holder + : public ebo_functor_holder_impl<T, is_unary_or_binary_function<T>::value> +{ + private: + typedef ebo_functor_holder_impl<T, is_unary_or_binary_function<T>::value> super; + + public: + ebo_functor_holder(){} + ebo_functor_holder(const T& t) + : super(t) + {} + + template<class Arg1, class Arg2> + ebo_functor_holder(const Arg1& arg1, const Arg2& arg2) + : super(arg1, arg2) + {} + + ebo_functor_holder& operator=(const ebo_functor_holder& x) + { + this->get()=x.get(); + return *this; + } +}; + + +} //namespace detail { +} //namespace intrusive { +} //namespace boost { + +#include <boost/intrusive/detail/config_end.hpp> + +#endif //#ifndef BOOST_INTRUSIVE_DETAIL_EBO_HOLDER_HPP diff --git a/3rdParty/Boost/src/boost/intrusive/detail/function_detector.hpp b/3rdParty/Boost/src/boost/intrusive/detail/function_detector.hpp new file mode 100644 index 0000000..f8eccf9 --- /dev/null +++ b/3rdParty/Boost/src/boost/intrusive/detail/function_detector.hpp @@ -0,0 +1,88 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2009-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. +// +///////////////////////////////////////////////////////////////////////////// +// This code was modified from the code posted by Alexandre Courpron in his +// article "Interface Detection" in The Code Project: +// http://www.codeproject.com/KB/architecture/Detector.aspx +/////////////////////////////////////////////////////////////////////////////// +// Copyright 2007 Alexandre Courpron +// +// Permission to use, copy, modify, redistribute and sell this software, +// provided that this copyright notice appears on all copies of the software. +/////////////////////////////////////////////////////////////////////////////// + +#ifndef BOOST_INTRUSIVE_DETAIL_FUNCTION_DETECTOR_HPP +#define BOOST_INTRUSIVE_DETAIL_FUNCTION_DETECTOR_HPP + +#include <boost/intrusive/detail/config_begin.hpp> + +namespace boost { +namespace intrusive { +namespace function_detector { + + typedef char NotFoundType; + struct StaticFunctionType { NotFoundType x [2]; }; + struct NonStaticFunctionType { NotFoundType x [3]; }; + + enum + { NotFound = 0, + StaticFunction = sizeof( StaticFunctionType ) - sizeof( NotFoundType ), + NonStaticFunction = sizeof( NonStaticFunctionType ) - sizeof( NotFoundType ) + }; + +} //namespace boost { +} //namespace intrusive { +} //namespace function_detector { + +#define BOOST_INTRUSIVE_CREATE_FUNCTION_DETECTOR(Identifier, InstantiationKey) \ + namespace boost { \ + namespace intrusive { \ + namespace function_detector { \ + template < class T, \ + class NonStaticType, \ + class NonStaticConstType, \ + class StaticType > \ + class DetectMember_##InstantiationKey_##Identifier { \ + template < NonStaticType > \ + struct TestNonStaticNonConst ; \ + \ + template < NonStaticConstType > \ + struct TestNonStaticConst ; \ + \ + template < StaticType > \ + struct TestStatic ; \ + \ + template <class U > \ + static NonStaticFunctionType Test( TestNonStaticNonConst<&U::Identifier>*, int ); \ + \ + template <class U > \ + static NonStaticFunctionType Test( TestNonStaticConst<&U::Identifier>*, int ); \ + \ + template <class U> \ + static StaticFunctionType Test( TestStatic<&U::Identifier>*, int ); \ + \ + template <class U> \ + static NotFoundType Test( ... ); \ + public : \ + static const int check = NotFound + (sizeof(Test<T>(0, 0)) - sizeof(NotFoundType));\ + };\ +}}} //namespace boost::intrusive::function_detector { + +#define BOOST_INTRUSIVE_DETECT_FUNCTION(Class, InstantiationKey, ReturnType, Identifier, Params) \ + ::boost::intrusive::function_detector::DetectMember_##InstantiationKey_##Identifier< Class,\ + ReturnType (Class::*)Params,\ + ReturnType (Class::*)Params const,\ + ReturnType (*)Params \ + >::check + +#include <boost/intrusive/detail/config_end.hpp> + +#endif //@ifndef BOOST_INTRUSIVE_DETAIL_FUNCTION_DETECTOR_HPP diff --git a/3rdParty/Boost/src/boost/intrusive/detail/generic_hook.hpp b/3rdParty/Boost/src/boost/intrusive/detail/generic_hook.hpp new file mode 100644 index 0000000..835a8c7 --- /dev/null +++ b/3rdParty/Boost/src/boost/intrusive/detail/generic_hook.hpp @@ -0,0 +1,190 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (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_GENERIC_HOOK_HPP +#define BOOST_INTRUSIVE_GENERIC_HOOK_HPP + +#include <boost/intrusive/detail/config_begin.hpp> +#include <boost/intrusive/intrusive_fwd.hpp> +#include <boost/intrusive/pointer_traits.hpp> +#include <boost/intrusive/link_mode.hpp> +#include <boost/intrusive/detail/utilities.hpp> +#include <boost/intrusive/detail/mpl.hpp> +#include <boost/intrusive/pointer_traits.hpp> +#include <boost/static_assert.hpp> + +namespace boost { +namespace intrusive { + +/// @cond + +enum base_hook_type +{ NoBaseHookId +, ListBaseHookId +, SlistBaseHookId +, RbTreeBaseHookId +, HashBaseHookId +, AvlTreeBaseHookId +, BsTreeBaseHookId +, TreapTreeBaseHookId +, AnyBaseHookId +}; + + +template <class HookTags, unsigned int> +struct hook_tags_definer{}; + +template <class HookTags> +struct hook_tags_definer<HookTags, ListBaseHookId> +{ typedef HookTags default_list_hook; }; + +template <class HookTags> +struct hook_tags_definer<HookTags, SlistBaseHookId> +{ typedef HookTags default_slist_hook; }; + +template <class HookTags> +struct hook_tags_definer<HookTags, RbTreeBaseHookId> +{ typedef HookTags default_rbtree_hook; }; + +template <class HookTags> +struct hook_tags_definer<HookTags, HashBaseHookId> +{ typedef HookTags default_hashtable_hook; }; + +template <class HookTags> +struct hook_tags_definer<HookTags, AvlTreeBaseHookId> +{ typedef HookTags default_avltree_hook; }; + +template <class HookTags> +struct hook_tags_definer<HookTags, BsTreeBaseHookId> +{ typedef HookTags default_bstree_hook; }; + +template <class HookTags> +struct hook_tags_definer<HookTags, AnyBaseHookId> +{ typedef HookTags default_any_hook; }; + +template + < class NodeTraits + , class Tag + , link_mode_type LinkMode + , base_hook_type BaseHookType + > +struct hooktags_impl +{ + static const link_mode_type link_mode = LinkMode; + typedef Tag tag; + typedef NodeTraits node_traits; + static const bool is_base_hook = !detail::is_same<Tag, member_tag>::value; + static const bool safemode_or_autounlink = is_safe_autounlink<link_mode>::value; + static const unsigned int type = BaseHookType; +}; + +/// @endcond + +template + < class GetNodeAlgorithms + , class Tag + , link_mode_type LinkMode + , base_hook_type BaseHookType + > +class generic_hook + /// @cond + //If the hook is a base hook, derive generic hook from node_holder + //so that a unique base class is created to convert from the node + //to the type. This mechanism will be used by bhtraits. + // + //If the hook is a member hook, generic hook will directly derive + //from the hook. + : public detail::if_c + < detail::is_same<Tag, member_tag>::value + , typename GetNodeAlgorithms::type::node + , node_holder<typename GetNodeAlgorithms::type::node, Tag, BaseHookType> + >::type + //If this is the a default-tagged base hook derive from a class that + //will define an special internal typedef. Containers will be able to detect this + //special typedef and obtain generic_hook's internal types in order to deduce + //value_traits for this hook. + , public hook_tags_definer + < generic_hook<GetNodeAlgorithms, Tag, LinkMode, BaseHookType> + , detail::is_same<Tag, default_tag>::value*BaseHookType> + /// @endcond +{ + /// @cond + typedef typename GetNodeAlgorithms::type node_algorithms; + typedef typename node_algorithms::node node; + typedef typename node_algorithms::node_ptr node_ptr; + typedef typename node_algorithms::const_node_ptr const_node_ptr; + + public: + + typedef hooktags_impl + < typename GetNodeAlgorithms::type::node_traits + , Tag, LinkMode, BaseHookType> hooktags; + + node_ptr this_ptr() + { return pointer_traits<node_ptr>::pointer_to(static_cast<node&>(*this)); } + + const_node_ptr this_ptr() const + { return pointer_traits<const_node_ptr>::pointer_to(static_cast<const node&>(*this)); } + + public: + /// @endcond + + generic_hook() + { + if(hooktags::safemode_or_autounlink){ + node_algorithms::init(this->this_ptr()); + } + } + + generic_hook(const generic_hook& ) + { + if(hooktags::safemode_or_autounlink){ + node_algorithms::init(this->this_ptr()); + } + } + + generic_hook& operator=(const generic_hook& ) + { return *this; } + + ~generic_hook() + { + destructor_impl + (*this, detail::link_dispatch<hooktags::link_mode>()); + } + + void swap_nodes(generic_hook &other) + { + node_algorithms::swap_nodes + (this->this_ptr(), other.this_ptr()); + } + + bool is_linked() const + { + //is_linked() can be only used in safe-mode or auto-unlink + BOOST_STATIC_ASSERT(( hooktags::safemode_or_autounlink )); + return !node_algorithms::unique(this->this_ptr()); + } + + void unlink() + { + BOOST_STATIC_ASSERT(( (int)hooktags::link_mode == (int)auto_unlink )); + node_algorithms::unlink(this->this_ptr()); + node_algorithms::init(this->this_ptr()); + } +}; + +} //namespace intrusive +} //namespace boost + +#include <boost/intrusive/detail/config_end.hpp> + +#endif //BOOST_INTRUSIVE_GENERIC_HOOK_HPP diff --git a/3rdParty/Boost/src/boost/intrusive/detail/has_member_function_callable_with.hpp b/3rdParty/Boost/src/boost/intrusive/detail/has_member_function_callable_with.hpp index 6516e28..12eec96 100644 --- a/3rdParty/Boost/src/boost/intrusive/detail/has_member_function_callable_with.hpp +++ b/3rdParty/Boost/src/boost/intrusive/detail/has_member_function_callable_with.hpp @@ -1,6 +1,6 @@ ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2011-2012. Distributed under the Boost +// (C) Copyright Ion Gaztanaga 2011-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) // @@ -18,6 +18,7 @@ #include <boost/intrusive/detail/config_begin.hpp> #include <boost/intrusive/detail/workaround.hpp> #include <boost/intrusive/detail/preprocessor.hpp> + #include <boost/intrusive/detail/mpl.hpp> #include <boost/static_assert.hpp> #include <boost/move/move.hpp> @@ -69,11 +70,11 @@ #error "BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END not defined!" #endif - #if BOOST_PP_ITERATION_START() != 0 - #error "BOOST_PP_ITERATION_START() must be zero (0)" + #if BOOST_PP_ITERATION_START() > BOOST_PP_ITERATION_FINISH() + #error "BOOST_PP_ITERATION_START() must be <= BOOST_PP_ITERATION_FINISH()" #endif - #if BOOST_PP_ITERATION() == 0 + #if BOOST_PP_ITERATION() == BOOST_PP_ITERATION_START() BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEGIN @@ -85,7 +86,7 @@ void BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME(); }; - struct Base : public Type, public BaseMixin { Base(); }; + struct Base : public ::boost::intrusive::detail::remove_cv<Type>::type, public BaseMixin { Base(); }; template <typename T, T t> class Helper{}; template <typename U> @@ -113,76 +114,7 @@ }; //! - #if !defined(_MSC_VER) || (_MSC_VER < 1600) - - #if defined(BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED) - - template<typename Fun> - struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl) - <Fun, true BOOST_PP_ENUM_TRAILING(BOOST_PP_SUB(BOOST_PP_ITERATION_FINISH(), BOOST_PP_ITERATION()), BOOST_INTRUSIVE_PP_IDENTITY, void)> - { - //Mark that we don't support 0 arg calls due to compiler ICE in GCC 3.4/4.0/4.1 and - //wrong SFINAE for GCC 4.2/4.3 - static const bool value = true; - }; - - #else //defined(BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED) - - //Special case for 0 args - template< class F - , std::size_t N = - sizeof((boost::move_detail::declval<F>(). - BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME (), 0))> - struct BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) - { - boost_intrusive_has_member_function_callable_with::yes_type dummy; - BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)(int); - }; - - //For buggy compilers like MSVC 7.1+ ((F*)0)->func() does not - //SFINAE-out the zeroarg_checker_ instantiation but sizeof yields to 0. - template<class F> - struct BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<F, 0> - { - boost_intrusive_has_member_function_callable_with::no_type dummy; - BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)(int); - }; - - template<typename Fun> - struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl) - <Fun, true BOOST_PP_ENUM_TRAILING(BOOST_PP_SUB(BOOST_PP_ITERATION_FINISH(), BOOST_PP_ITERATION()), BOOST_INTRUSIVE_PP_IDENTITY, void)> - { - template<class U> - static BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<U> - Test(BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<U>*); - - template <class U> - static boost_intrusive_has_member_function_callable_with::no_type Test(...); - - static const bool value = sizeof(Test< Fun >(0)) - == sizeof(boost_intrusive_has_member_function_callable_with::yes_type); - }; - #endif //defined(BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED) - - #else //#if !defined(_MSC_VER) || (_MSC_VER < 1600) - template<typename Fun> - struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl) - <Fun, true BOOST_PP_ENUM_TRAILING(BOOST_PP_SUB(BOOST_PP_ITERATION_FINISH(), BOOST_PP_ITERATION()), BOOST_INTRUSIVE_PP_IDENTITY, void)> - { - template<class U> - static decltype( boost::move_detail::declval<Fun>().BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME() - , boost_intrusive_has_member_function_callable_with::yes_type()) - Test(Fun*); - - template<class U> - static boost_intrusive_has_member_function_callable_with::no_type Test(...); - - static const bool value = sizeof(Test<Fun>(0)) - == sizeof(boost_intrusive_has_member_function_callable_with::yes_type); - }; - #endif //#if !defined(_MSC_VER) || (_MSC_VER < 1600) - - #else //#if !defined(BOOST_INTRUSIVE_PERFECT_FORWARDING) + #else //!defined(BOOST_INTRUSIVE_PERFECT_FORWARDING) template<typename Fun, bool HasFunc, class ...Args> struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl); @@ -194,6 +126,8 @@ static const bool value = false; }; + #ifdef BOOST_NO_CXX11_DECLTYPE + //Special case for 0 args template< class F , std::size_t N = @@ -214,14 +148,21 @@ BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)(int); }; + #endif //#ifdef BOOST_NO_CXX11_DECLTYPE + template<typename Fun> struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl) <Fun, true> { + #ifndef BOOST_NO_CXX11_DECLTYPE + template<class U, class V = decltype(boost::move_detail::declval<U>().BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME()) > + static boost_intrusive_has_member_function_callable_with::yes_type Test(U*); + #else template<class U> - static BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) + static BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) <U> Test(BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<U>*); - + #endif + template <class U> static boost_intrusive_has_member_function_callable_with::no_type Test(...); @@ -274,6 +215,89 @@ , Args... > {}; + #endif //!defined(BOOST_INTRUSIVE_PERFECT_FORWARDING) + + BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END + + #endif //BOOST_PP_ITERATION() == BOOST_PP_ITERATION_START() + + #if BOOST_PP_ITERATION() == 0 + + BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEGIN + + #if !defined(BOOST_INTRUSIVE_PERFECT_FORWARDING) + + #if !defined(_MSC_VER) || (_MSC_VER < 1600) + + #if defined(BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED) + + template<typename Fun> + struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl) + <Fun, true BOOST_PP_ENUM_TRAILING(BOOST_PP_SUB(BOOST_PP_ITERATION_FINISH(), BOOST_PP_ITERATION()), BOOST_INTRUSIVE_PP_IDENTITY, void)> + { + //Mark that we don't support 0 arg calls due to compiler ICE in GCC 3.4/4.0/4.1 and + //wrong SFINAE for GCC 4.2/4.3 + static const bool value = true; + }; + + #else //defined(BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED) + + //Special case for 0 args + template< class F + , std::size_t N = + sizeof((boost::move_detail::declval<F>(). + BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME (), 0))> + struct BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME) + { + boost_intrusive_has_member_function_callable_with::yes_type dummy; + BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)(int); + }; + + //For buggy compilers like MSVC 7.1+ ((F*)0)->func() does not + //SFINAE-out the zeroarg_checker_ instantiation but sizeof yields to 0. + template<class F> + struct BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<F, 0> + { + boost_intrusive_has_member_function_callable_with::no_type dummy; + BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)(int); + }; + + template<typename Fun> + struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl) + <Fun, true BOOST_PP_ENUM_TRAILING(BOOST_PP_SUB(BOOST_PP_ITERATION_FINISH(), BOOST_PP_ITERATION()), BOOST_INTRUSIVE_PP_IDENTITY, void)> + { + template<class U> + static BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<U> + Test(BOOST_PP_CAT(zeroarg_checker_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME)<U>*); + + template <class U> + static boost_intrusive_has_member_function_callable_with::no_type Test(...); + + static const bool value = sizeof(Test< Fun >(0)) + == sizeof(boost_intrusive_has_member_function_callable_with::yes_type); + }; + #endif //defined(BOOST_INTRUSIVE_DETAIL_HAS_MEMBER_FUNCTION_CALLABLE_WITH_0_ARGS_UNSUPPORTED) + + #else //#if !defined(_MSC_VER) || (_MSC_VER < 1600) + template<typename Fun> + struct BOOST_PP_CAT(BOOST_PP_CAT(has_member_function_callable_with_, BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME),_impl) + <Fun, true BOOST_PP_ENUM_TRAILING(BOOST_PP_SUB(BOOST_PP_ITERATION_FINISH(), BOOST_PP_ITERATION()), BOOST_INTRUSIVE_PP_IDENTITY, void)> + { + template<class U> + static decltype( boost::move_detail::declval<U>().BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME() + , boost_intrusive_has_member_function_callable_with::yes_type()) + Test(U*); + + template<class U> + static boost_intrusive_has_member_function_callable_with::no_type Test(...); + + static const bool value = sizeof(Test<Fun>(0)) + == sizeof(boost_intrusive_has_member_function_callable_with::yes_type); + }; + #endif //#if !defined(_MSC_VER) || (_MSC_VER < 1600) + + #else //#if !defined(BOOST_INTRUSIVE_PERFECT_FORWARDING) + #endif //#if !defined(BOOST_INTRUSIVE_PERFECT_FORWARDING) BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END diff --git a/3rdParty/Boost/src/boost/intrusive/detail/is_stateful_value_traits.hpp b/3rdParty/Boost/src/boost/intrusive/detail/is_stateful_value_traits.hpp new file mode 100644 index 0000000..c98f6c6 --- /dev/null +++ b/3rdParty/Boost/src/boost/intrusive/detail/is_stateful_value_traits.hpp @@ -0,0 +1,77 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2009-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_DETAIL_IS_STATEFUL_VALUE_TRAITS_HPP +#define BOOST_INTRUSIVE_DETAIL_IS_STATEFUL_VALUE_TRAITS_HPP + +#include <boost/intrusive/detail/config_begin.hpp> + +#if defined(_MSC_VER) && (_MSC_VER <= 1310) + +#include <boost/intrusive/detail/mpl.hpp> + +namespace boost { +namespace intrusive { +namespace detail { + +template<class ValueTraits> +struct is_stateful_value_traits +{ + static const bool value = !detail::is_empty_class<ValueTraits>::value; +}; + +}}} + +#else + +#include <boost/intrusive/detail/function_detector.hpp> + +BOOST_INTRUSIVE_CREATE_FUNCTION_DETECTOR(to_node_ptr, boost_intrusive) +BOOST_INTRUSIVE_CREATE_FUNCTION_DETECTOR(to_value_ptr, boost_intrusive) + +namespace boost { +namespace intrusive { +namespace detail { + +template<class ValueTraits> +struct is_stateful_value_traits +{ + typedef typename ValueTraits::node_ptr node_ptr; + typedef typename ValueTraits::pointer pointer; + typedef typename ValueTraits::value_type value_type; + typedef typename ValueTraits::const_node_ptr const_node_ptr; + typedef typename ValueTraits::const_pointer const_pointer; + + typedef ValueTraits value_traits; + + static const bool value = + (boost::intrusive::function_detector::NonStaticFunction == + (BOOST_INTRUSIVE_DETECT_FUNCTION(ValueTraits, boost_intrusive, node_ptr, to_node_ptr, (value_type&) ))) + || + (boost::intrusive::function_detector::NonStaticFunction == + (BOOST_INTRUSIVE_DETECT_FUNCTION(ValueTraits, boost_intrusive, pointer, to_value_ptr, (node_ptr) ))) + || + (boost::intrusive::function_detector::NonStaticFunction == + (BOOST_INTRUSIVE_DETECT_FUNCTION(ValueTraits, boost_intrusive, const_node_ptr, to_node_ptr, (const value_type&) ))) + || + (boost::intrusive::function_detector::NonStaticFunction == + (BOOST_INTRUSIVE_DETECT_FUNCTION(ValueTraits, boost_intrusive, const_pointer, to_value_ptr, (const_node_ptr) ))) + ; +}; + +}}} + +#endif + +#include <boost/intrusive/detail/config_end.hpp> + +#endif //@ifndef BOOST_INTRUSIVE_DETAIL_IS_STATEFUL_VALUE_TRAITS_HPP diff --git a/3rdParty/Boost/src/boost/intrusive/detail/memory_util.hpp b/3rdParty/Boost/src/boost/intrusive/detail/memory_util.hpp index 1a6431b..49b69cf 100644 --- a/3rdParty/Boost/src/boost/intrusive/detail/memory_util.hpp +++ b/3rdParty/Boost/src/boost/intrusive/detail/memory_util.hpp @@ -6,7 +6,7 @@ // ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2011-2012. Distributed under the Boost +// (C) Copyright Ion Gaztanaga 2011-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) // @@ -17,7 +17,7 @@ #ifndef BOOST_INTRUSIVE_ALLOCATOR_MEMORY_UTIL_HPP #define BOOST_INTRUSIVE_ALLOCATOR_MEMORY_UTIL_HPP -#if (defined _MSC_VER) && (_MSC_VER >= 1200) +#if defined(_MSC_VER) # pragma once #endif @@ -45,6 +45,10 @@ template <typename T> struct unvoid { typedef T type; }; template <> struct unvoid<void> { struct type { }; }; template <> struct unvoid<const void> { struct type { }; }; +template <typename T> struct unvoid_ref { typedef T &type; }; +template <> struct unvoid_ref<void> { struct type_impl { }; typedef type_impl & type; }; +template <> struct unvoid_ref<const void> { struct type_impl { }; typedef type_impl & type; }; + template <typename T> struct LowPriorityConversion { @@ -61,8 +65,7 @@ struct LowPriorityConversion static char test(int, typename X::TNAME*); \ \ template <typename X> \ - static int test(boost::intrusive::detail:: \ - LowPriorityConversion<int>, void*); \ + static int test(...); \ \ struct DefaultWrap { typedef DefaultType TNAME; }; \ \ @@ -80,8 +83,7 @@ struct LowPriorityConversion static char test(int, typename X::TNAME*); \ \ template <typename X> \ - static int test(boost::intrusive::detail:: \ - LowPriorityConversion<int>, void*); \ + static int test(...); \ \ struct DefaultWrap \ { typedef typename DefaultType::type TNAME; }; \ @@ -114,25 +116,25 @@ struct LowPriorityConversion #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME pointer_to #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEGIN namespace boost { namespace intrusive { namespace detail { #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END }}} -#define BOOST_PP_ITERATION_PARAMS_1 (3, (0, 1, <boost/intrusive/detail/has_member_function_callable_with.hpp>)) +#define BOOST_PP_ITERATION_PARAMS_1 (3, (1, 1, <boost/intrusive/detail/has_member_function_callable_with.hpp>)) #include BOOST_PP_ITERATE() #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME static_cast_from #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEGIN namespace boost { namespace intrusive { namespace detail { #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END }}} -#define BOOST_PP_ITERATION_PARAMS_1 (3, (0, 1, <boost/intrusive/detail/has_member_function_callable_with.hpp>)) +#define BOOST_PP_ITERATION_PARAMS_1 (3, (1, 1, <boost/intrusive/detail/has_member_function_callable_with.hpp>)) #include BOOST_PP_ITERATE() #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME const_cast_from #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEGIN namespace boost { namespace intrusive { namespace detail { #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END }}} -#define BOOST_PP_ITERATION_PARAMS_1 (3, (0, 1, <boost/intrusive/detail/has_member_function_callable_with.hpp>)) +#define BOOST_PP_ITERATION_PARAMS_1 (3, (1, 1, <boost/intrusive/detail/has_member_function_callable_with.hpp>)) #include BOOST_PP_ITERATE() #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_FUNCNAME dynamic_cast_from #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_BEGIN namespace boost { namespace intrusive { namespace detail { #define BOOST_INTRUSIVE_HAS_MEMBER_FUNCTION_CALLABLE_WITH_NS_END }}} -#define BOOST_PP_ITERATION_PARAMS_1 (3, (0, 1, <boost/intrusive/detail/has_member_function_callable_with.hpp>)) +#define BOOST_PP_ITERATION_PARAMS_1 (3, (1, 1, <boost/intrusive/detail/has_member_function_callable_with.hpp>)) #include BOOST_PP_ITERATE() namespace boost { @@ -141,6 +143,8 @@ namespace detail { BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(element_type) BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(difference_type) +BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(reference) +BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(value_traits_ptr) ////////////////////// //struct first_param @@ -149,7 +153,7 @@ BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(difference_type) template <typename T> struct first_param { typedef void type; }; -#if !defined(BOOST_NO_VARIADIC_TEMPLATES) +#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) template <template <typename, typename...> class TemplateClass, typename T, typename... Args> struct first_param< TemplateClass<T, Args...> > @@ -173,7 +177,7 @@ template <typename T> struct first_param #define BOOST_PP_LOCAL_LIMITS (0, BOOST_INTRUSIVE_MAX_CONSTRUCTOR_PARAMETERS) #include BOOST_PP_LOCAL_ITERATE() -#endif //!defined(BOOST_NO_VARIADIC_TEMPLATES) +#endif //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) /////////////////////////// //struct type_rebind_mode @@ -182,11 +186,7 @@ template <typename Ptr, typename T> struct type_has_rebind { template <typename X> - #if !defined (__SUNPRO_CC) static char test(int, typename X::template rebind<T>*); - #else - static char test(int, typename X::rebind<T>*); - #endif template <typename X> static int test(boost::intrusive::detail::LowPriorityConversion<int>, void*); @@ -198,11 +198,7 @@ template <typename Ptr, typename T> struct type_has_rebind_other { template <typename X> - #if !defined (__SUNPRO_CC) static char test(int, typename X::template rebind<T>::other*); - #else - static char test(int, typename X::rebind<T>::other*); - #endif template <typename X> static int test(boost::intrusive::detail::LowPriorityConversion<int>, void*); @@ -245,7 +241,7 @@ struct type_rebinder< Ptr, U, 1u > // OtherArgs>, where OtherArgs comprises zero or more type parameters. // Many pointers fit this form, hence many pointers will get a // reasonable default for rebind. -#if !defined(BOOST_NO_VARIADIC_TEMPLATES) +#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) template <template <class, class...> class Ptr, typename T, class... Tn, class U> struct type_rebinder<Ptr<T, Tn...>, U, 0u > @@ -277,7 +273,7 @@ struct type_rebinder #define BOOST_PP_LOCAL_LIMITS (0, BOOST_INTRUSIVE_MAX_CONSTRUCTOR_PARAMETERS) #include BOOST_PP_LOCAL_ITERATE() -#endif //!defined(BOOST_NO_VARIADIC_TEMPLATES) +#endif //!defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) } //namespace detail { } //namespace intrusive { diff --git a/3rdParty/Boost/src/boost/intrusive/detail/mpl.hpp b/3rdParty/Boost/src/boost/intrusive/detail/mpl.hpp index 02b1361..9dc0d52 100644 --- a/3rdParty/Boost/src/boost/intrusive/detail/mpl.hpp +++ b/3rdParty/Boost/src/boost/intrusive/detail/mpl.hpp @@ -1,6 +1,7 @@ ///////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2006-2012 +// (C) Copyright Ion Gaztanaga 2006-2014 +// (C) Copyright Microsoft Corporation 2014 // // Distributed under the Boost Software License, Version 1.0. // (See accompanying file LICENSE_1_0.txt or copy at @@ -20,6 +21,59 @@ namespace boost { namespace intrusive { namespace detail { +template <typename T, typename U> +struct is_same +{ + static const bool value = false; +}; + +template <typename T> +struct is_same<T, T> +{ + static const bool value = true; +}; + +template<typename T> +struct add_const +{ typedef const T type; }; + +template<typename T> +struct remove_const +{ typedef T type; }; + +template<typename T> +struct remove_const<const T> +{ typedef T type; }; + +template<typename T> +struct remove_cv +{ typedef T type; }; + +template<typename T> +struct remove_cv<const T> +{ typedef T type; }; + +template<typename T> +struct remove_cv<const volatile T> +{ typedef T type; }; + +template<typename T> +struct remove_cv<volatile T> +{ typedef T type; }; + +template<class T> +struct remove_reference +{ + typedef T type; +}; + +template<class T> +struct remove_reference<T&> +{ + typedef T type; +}; + + typedef char one; struct two {one _[2];}; @@ -29,6 +83,12 @@ struct bool_ static const bool value = C_; }; +template< class Integer, Integer Value > +struct integer +{ + static const Integer value = Value; +}; + typedef bool_<true> true_; typedef bool_<false> false_; @@ -58,18 +118,32 @@ struct apply typedef typename F::template apply<Param>::type type; }; +#if defined(_MSC_VER) && (_MSC_VER >= 1400) + +template <class T, class U> +struct is_convertible +{ + static const bool value = __is_convertible_to(T, U); +}; + +#else + template <class T, class U> class is_convertible { typedef char true_t; class false_t { char dummy[2]; }; - static true_t dispatch(U); + //use any_conversion as first parameter since in MSVC + //overaligned types can't go through ellipsis static false_t dispatch(...); - static const T &trigger(); + static true_t dispatch(U); + static typename remove_reference<T>::type &trigger(); public: static const bool value = sizeof(dispatch(trigger())) == sizeof(true_t); }; +#endif + template< bool C , typename T1 @@ -130,7 +204,7 @@ struct identity #define BOOST_INTRUSIVE_TT_DECL #endif -#if defined(_MSC_EXTENSIONS) && !defined(__BORLAND__) && !defined(_WIN64) && !defined(UNDER_CE) +#if defined(_MSC_EXTENSIONS) && !defined(__BORLAND__) && !defined(_WIN64) && !defined(_M_ARM) && !defined(UNDER_CE) #define BOOST_INTRUSIVE_TT_TEST_MSC_FUNC_SIGS #endif @@ -280,49 +354,6 @@ struct alignment_of >::value; }; -template <typename T, typename U> -struct is_same -{ - typedef char yes_type; - struct no_type - { - char padding[8]; - }; - - template <typename V> - static yes_type is_same_tester(V*, V*); - static no_type is_same_tester(...); - - static T *t; - static U *u; - - static const bool value = sizeof(yes_type) == sizeof(is_same_tester(t,u)); -}; - -template<typename T> -struct add_const -{ typedef const T type; }; - -template<typename T> -struct remove_const -{ typedef T type; }; - -template<typename T> -struct remove_const<const T> -{ typedef T type; }; - -template<class T> -struct remove_reference -{ - typedef T type; -}; - -template<class T> -struct remove_reference<T&> -{ - typedef T type; -}; - template<class Class> class is_empty_class { diff --git a/3rdParty/Boost/src/boost/intrusive/detail/parent_from_member.hpp b/3rdParty/Boost/src/boost/intrusive/detail/parent_from_member.hpp new file mode 100644 index 0000000..cf9f379 --- /dev/null +++ b/3rdParty/Boost/src/boost/intrusive/detail/parent_from_member.hpp @@ -0,0 +1,117 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (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_DETAIL_PARENT_FROM_MEMBER_HPP +#define BOOST_INTRUSIVE_DETAIL_PARENT_FROM_MEMBER_HPP + +#include <boost/intrusive/detail/config_begin.hpp> +#include <cstddef> + +#if defined(BOOST_MSVC) || ((defined(_WIN32) || defined(__WIN32__) || defined(WIN32)) && defined(BOOST_INTEL)) + #define BOOST_INTRUSIVE_MSVC_ABI_PTR_TO_MEMBER + #include <boost/cstdint.hpp> + #include <boost/static_assert.hpp> +#endif + +namespace boost { +namespace intrusive { +namespace detail { + +template<class Parent, class Member> +inline std::ptrdiff_t offset_from_pointer_to_member(const Member Parent::* ptr_to_member) +{ + //The implementation of a pointer to member is compiler dependent. + #if defined(BOOST_INTRUSIVE_MSVC_ABI_PTR_TO_MEMBER) + + //MSVC compliant compilers use their the first 32 bits as offset (even in 64 bit mode) + union caster_union + { + const Member Parent::* ptr_to_member; + boost::int32_t offset; + } caster; + + //MSVC ABI can use up to 3 int32 to represent pointer to member data + //with virtual base classes, in those cases there is no simple to + //obtain the address of the parent. So static assert to avoid runtime errors + BOOST_STATIC_ASSERT( sizeof(caster) == sizeof(boost::int32_t) ); + + caster.ptr_to_member = ptr_to_member; + return std::ptrdiff_t(caster.offset); + //Additional info on MSVC behaviour for the future. For 2/3 int ptr-to-member + //types dereference seems to be: + // + // vboffset = [compile_time_offset if 2-int ptr2memb] / + // [ptr2memb.i32[2] if 3-int ptr2memb]. + // vbtable = *(this + vboffset); + // adj = vbtable[ptr2memb.i32[1]]; + // var = adj + (this + vboffset) + ptr2memb.i32[0]; + // + //To reverse the operation we need to + // - obtain vboffset (in 2-int ptr2memb implementation only) + // - Go to Parent's vbtable and obtain adjustment at index ptr2memb.i32[1] + // - parent = member - adj - vboffset - ptr2memb.i32[0] + // + //Even accessing to RTTI we might not be able to obtain this information + //so anyone who thinks it's possible, please send a patch. + + //This works with gcc, msvc, ac++, ibmcpp + #elif defined(__GNUC__) || defined(__HP_aCC) || defined(BOOST_INTEL) || \ + defined(__IBMCPP__) || defined(__DECCXX) + const Parent * const parent = 0; + const char *const member = static_cast<const char*>(static_cast<const void*>(&(parent->*ptr_to_member))); + return std::ptrdiff_t(member - static_cast<const char*>(static_cast<const void*>(parent))); + #else + //This is the traditional C-front approach: __MWERKS__, __DMC__, __SUNPRO_CC + union caster_union + { + const Member Parent::* ptr_to_member; + std::ptrdiff_t offset; + } caster; + caster.ptr_to_member = ptr_to_member; + return caster.offset - 1; + #endif +} + +template<class Parent, class Member> +inline Parent *parent_from_member(Member *member, const Member Parent::* ptr_to_member) +{ + return static_cast<Parent*> + ( + static_cast<void*> + ( + static_cast<char*>(static_cast<void*>(member)) - offset_from_pointer_to_member(ptr_to_member) + ) + ); +} + +template<class Parent, class Member> +inline const Parent *parent_from_member(const Member *member, const Member Parent::* ptr_to_member) +{ + return static_cast<const Parent*> + ( + static_cast<const void*> + ( + static_cast<const char*>(static_cast<const void*>(member)) - offset_from_pointer_to_member(ptr_to_member) + ) + ); +} + +} //namespace detail { +} //namespace intrusive { +} //namespace boost { + +#ifdef BOOST_INTRUSIVE_MSVC_ABI_PTR_TO_MEMBER +#undef BOOST_INTRUSIVE_MSVC_ABI_PTR_TO_MEMBER +#endif + +#include <boost/intrusive/detail/config_end.hpp> + +#endif //#ifndef BOOST_INTRUSIVE_DETAIL_PARENT_FROM_MEMBER_HPP diff --git a/3rdParty/Boost/src/boost/intrusive/detail/preprocessor.hpp b/3rdParty/Boost/src/boost/intrusive/detail/preprocessor.hpp index 348b104..b8143a4 100644 --- a/3rdParty/Boost/src/boost/intrusive/detail/preprocessor.hpp +++ b/3rdParty/Boost/src/boost/intrusive/detail/preprocessor.hpp @@ -1,6 +1,6 @@ ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2008-2012. Distributed under the Boost +// (C) Copyright Ion Gaztanaga 2008-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) // @@ -11,7 +11,7 @@ #ifndef BOOST_INTRUSIVE_DETAIL_PREPROCESSOR_HPP #define BOOST_INTRUSIVE_DETAIL_PREPROCESSOR_HPP -#if (defined _MSC_VER) && (_MSC_VER >= 1200) +#if defined(_MSC_VER) # pragma once #endif diff --git a/3rdParty/Boost/src/boost/intrusive/detail/slist_node.hpp b/3rdParty/Boost/src/boost/intrusive/detail/slist_node.hpp new file mode 100644 index 0000000..9f57d67 --- /dev/null +++ b/3rdParty/Boost/src/boost/intrusive/detail/slist_node.hpp @@ -0,0 +1,145 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Olaf Krzikalla 2004-2006. +// (C) Copyright Ion Gaztanaga 2006-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_SLIST_NODE_HPP +#define BOOST_INTRUSIVE_SLIST_NODE_HPP + +#include <boost/intrusive/detail/config_begin.hpp> +#include <boost/intrusive/detail/utilities.hpp> +#include <boost/intrusive/detail/assert.hpp> +#include <boost/intrusive/pointer_traits.hpp> + +namespace boost { +namespace intrusive { + +template<class VoidPointer> +struct slist_node +{ + typedef typename pointer_traits + <VoidPointer>::template rebind_pointer<slist_node>::type node_ptr; + node_ptr next_; +}; + +// slist_node_traits can be used with circular_slist_algorithms and supplies +// a slist_node holding the pointers needed for a singly-linked list +// it is used by slist_base_hook and slist_member_hook +template<class VoidPointer> +struct slist_node_traits +{ + typedef slist_node<VoidPointer> node; + typedef typename pointer_traits + <VoidPointer>::template rebind_pointer<node>::type node_ptr; + typedef typename pointer_traits + <VoidPointer>::template rebind_pointer<const node>::type const_node_ptr; + + static node_ptr get_next(const const_node_ptr & n) + { return n->next_; } + + static node_ptr get_next(const node_ptr & n) + { return n->next_; } + + static void set_next(const node_ptr & n, const node_ptr & next) + { n->next_ = next; } +}; + +// slist_iterator provides some basic functions for a +// node oriented bidirectional iterator: +template<class ValueTraits, bool IsConst> +class slist_iterator +{ + protected: + typedef iiterator + <ValueTraits, IsConst, std::forward_iterator_tag> types_t; + + static const bool stateful_value_traits = types_t::stateful_value_traits; + + typedef ValueTraits value_traits; + typedef typename types_t::node_traits node_traits; + + typedef typename types_t::node node; + typedef typename types_t::node_ptr node_ptr; + typedef typename types_t::const_value_traits_ptr const_value_traits_ptr; + + public: + typedef typename types_t::iterator_traits::difference_type difference_type; + typedef typename types_t::iterator_traits::value_type value_type; + typedef typename types_t::iterator_traits::pointer pointer; + typedef typename types_t::iterator_traits::reference reference; + typedef typename types_t::iterator_traits::iterator_category iterator_category; + + slist_iterator() + {} + + explicit slist_iterator(const node_ptr & nodeptr, const const_value_traits_ptr &traits_ptr) + : members_(nodeptr, traits_ptr) + {} + + slist_iterator(slist_iterator<ValueTraits, false> const& other) + : members_(other.pointed_node(), other.get_value_traits()) + {} + + const node_ptr &pointed_node() const + { return members_.nodeptr_; } + + slist_iterator &operator=(const node_ptr &node) + { members_.nodeptr_ = node; return static_cast<slist_iterator&>(*this); } + + const_value_traits_ptr get_value_traits() const + { return members_.get_ptr(); } + + public: + slist_iterator& operator++() + { + members_.nodeptr_ = node_traits::get_next(members_.nodeptr_); + return static_cast<slist_iterator&> (*this); + } + + slist_iterator operator++(int) + { + slist_iterator result (*this); + members_.nodeptr_ = node_traits::get_next(members_.nodeptr_); + return result; + } + + friend bool operator== (const slist_iterator& l, const slist_iterator& r) + { return l.pointed_node() == r.pointed_node(); } + + friend bool operator!= (const slist_iterator& l, const slist_iterator& r) + { return !(l == r); } + + reference operator*() const + { return *operator->(); } + + pointer operator->() const + { return this->operator_arrow(detail::bool_<stateful_value_traits>()); } + + slist_iterator<ValueTraits, false> unconst() const + { return slist_iterator<ValueTraits, false>(this->pointed_node(), this->get_value_traits()); } + + private: + + pointer operator_arrow(detail::false_) const + { return ValueTraits::to_value_ptr(members_.nodeptr_); } + + pointer operator_arrow(detail::true_) const + { return this->get_value_traits()->to_value_ptr(members_.nodeptr_); } + + iiterator_members<node_ptr, const_value_traits_ptr, stateful_value_traits> members_; +}; + +} //namespace intrusive +} //namespace boost + +#include <boost/intrusive/detail/config_end.hpp> + +#endif //BOOST_INTRUSIVE_SLIST_NODE_HPP diff --git a/3rdParty/Boost/src/boost/intrusive/detail/utilities.hpp b/3rdParty/Boost/src/boost/intrusive/detail/utilities.hpp new file mode 100644 index 0000000..b893d22 --- /dev/null +++ b/3rdParty/Boost/src/boost/intrusive/detail/utilities.hpp @@ -0,0 +1,1279 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-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_DETAIL_UTILITIES_HPP +#define BOOST_INTRUSIVE_DETAIL_UTILITIES_HPP + +#include <boost/intrusive/detail/config_begin.hpp> +#include <boost/intrusive/pointer_traits.hpp> +#include <boost/intrusive/detail/parent_from_member.hpp> +#include <boost/intrusive/detail/ebo_functor_holder.hpp> +#include <boost/intrusive/link_mode.hpp> +#include <boost/intrusive/detail/mpl.hpp> +#include <boost/intrusive/detail/assert.hpp> +#include <boost/intrusive/detail/is_stateful_value_traits.hpp> +#include <boost/intrusive/detail/memory_util.hpp> +#include <boost/cstdint.hpp> +#include <cstddef> +#include <climits> +#include <iterator> +#include <boost/cstdint.hpp> +#include <boost/static_assert.hpp> +#include <boost/detail/no_exceptions_support.hpp> +#include <functional> +#include <boost/functional/hash.hpp> +#include <boost/tti/tti.hpp> + +namespace boost { +namespace intrusive { + +enum algo_types +{ + CircularListAlgorithms, + CircularSListAlgorithms, + LinearSListAlgorithms, + BsTreeAlgorithms, + RbTreeAlgorithms, + AvlTreeAlgorithms, + SgTreeAlgorithms, + SplayTreeAlgorithms, + TreapAlgorithms +}; + +template<algo_types AlgoType, class NodeTraits> +struct get_algo; + +template <link_mode_type link_mode> +struct is_safe_autounlink +{ + static const bool value = + (int)link_mode == (int)auto_unlink || + (int)link_mode == (int)safe_link; +}; + +namespace detail { + +template <class T> +struct internal_member_value_traits +{ + template <class U> static detail::one test(...); + template <class U> static detail::two test(typename U::member_value_traits* = 0); + static const bool value = sizeof(test<T>(0)) == sizeof(detail::two); +}; + +#define BOOST_INTRUSIVE_INTERNAL_STATIC_BOOL_IS_TRUE(TRAITS_PREFIX, TYPEDEF_TO_FIND) \ +template <class T>\ +struct TRAITS_PREFIX##_bool\ +{\ + template<bool Add>\ + struct two_or_three {one _[2 + Add];};\ + template <class U> static one test(...);\ + template <class U> static two_or_three<U::TYPEDEF_TO_FIND> test (int);\ + static const std::size_t value = sizeof(test<T>(0));\ +};\ +\ +template <class T>\ +struct TRAITS_PREFIX##_bool_is_true\ +{\ + static const bool value = TRAITS_PREFIX##_bool<T>::value > sizeof(one)*2;\ +};\ +// + +BOOST_INTRUSIVE_INTERNAL_STATIC_BOOL_IS_TRUE(internal_base_hook, hooktags::is_base_hook) +BOOST_INTRUSIVE_INTERNAL_STATIC_BOOL_IS_TRUE(internal_any_hook, is_any_hook) +BOOST_INTRUSIVE_INTERNAL_STATIC_BOOL_IS_TRUE(resizable, resizable) + +template <class T> +inline T* to_raw_pointer(T* p) +{ return p; } + +template <class Pointer> +inline typename boost::intrusive::pointer_traits<Pointer>::element_type* +to_raw_pointer(const Pointer &p) +{ return boost::intrusive::detail::to_raw_pointer(p.operator->()); } + +//This functor compares a stored value +//and the one passed as an argument +template<class ConstReference> +class equal_to_value +{ + ConstReference t_; + + public: + equal_to_value(ConstReference t) + : t_(t) + {} + + bool operator()(ConstReference t)const + { return t_ == t; } +}; + +class null_disposer +{ + public: + template <class Pointer> + void operator()(Pointer) + {} +}; + +template<class NodeAlgorithms> +class init_disposer +{ + typedef typename NodeAlgorithms::node_ptr node_ptr; + + public: + void operator()(const node_ptr & p) + { NodeAlgorithms::init(p); } +}; + +template<bool ConstantSize, class SizeType, class Tag = void> +struct size_holder +{ + static const bool constant_time_size = ConstantSize; + typedef SizeType size_type; + + SizeType get_size() const + { return size_; } + + void set_size(SizeType size) + { size_ = size; } + + void decrement() + { --size_; } + + void increment() + { ++size_; } + + void increase(SizeType n) + { size_ += n; } + + void decrease(SizeType n) + { size_ -= n; } + + SizeType size_; +}; + +template<class SizeType, class Tag> +struct size_holder<false, SizeType, Tag> +{ + static const bool constant_time_size = false; + typedef SizeType size_type; + + size_type get_size() const + { return 0; } + + void set_size(size_type) + {} + + void decrement() + {} + + void increment() + {} + + void increase(SizeType) + {} + + void decrease(SizeType) + {} +}; + +template<class KeyValueCompare, class ValueTraits> +struct key_nodeptr_comp + : private detail::ebo_functor_holder<KeyValueCompare> +{ + typedef ValueTraits value_traits; + typedef typename value_traits::value_type value_type; + typedef typename value_traits::node_ptr node_ptr; + typedef typename value_traits::const_node_ptr const_node_ptr; + typedef detail::ebo_functor_holder<KeyValueCompare> base_t; + key_nodeptr_comp(KeyValueCompare kcomp, const ValueTraits *traits) + : base_t(kcomp), traits_(traits) + {} + + template<class T> + struct is_node_ptr + { + static const bool value = is_same<T, const_node_ptr>::value || is_same<T, node_ptr>::value; + }; + + template<class T> + const value_type & key_forward + (const T &node, typename enable_if_c<is_node_ptr<T>::value>::type * = 0) const + { return *traits_->to_value_ptr(node); } + + template<class T> + const T & key_forward(const T &key, typename enable_if_c<!is_node_ptr<T>::value>::type* = 0) const + { return key; } + + + template<class KeyType, class KeyType2> + bool operator()(const KeyType &key1, const KeyType2 &key2) const + { return base_t::get()(this->key_forward(key1), this->key_forward(key2)); } + + const ValueTraits *const traits_; +}; + +template<class F, class ValueTraits, algo_types AlgoType> +struct node_cloner + : private detail::ebo_functor_holder<F> +{ + typedef ValueTraits value_traits; + typedef typename value_traits::node_traits node_traits; + typedef typename node_traits::node_ptr node_ptr; + typedef detail::ebo_functor_holder<F> base_t; + typedef typename get_algo< AlgoType + , node_traits>::type node_algorithms; + static const bool safemode_or_autounlink = + is_safe_autounlink<value_traits::link_mode>::value; + typedef typename value_traits::value_type value_type; + typedef typename value_traits::pointer pointer; + typedef typename node_traits::node node; + typedef typename value_traits::const_node_ptr const_node_ptr; + typedef typename value_traits::reference reference; + typedef typename value_traits::const_reference const_reference; + + node_cloner(F f, const ValueTraits *traits) + : base_t(f), traits_(traits) + {} + + // tree-based containers use this method, which is proxy-reference friendly + node_ptr operator()(const node_ptr & p) + { + const_reference v = *traits_->to_value_ptr(p); + node_ptr n = traits_->to_node_ptr(*base_t::get()(v)); + //Cloned node must be in default mode if the linking mode requires it + if(safemode_or_autounlink) + BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(n)); + return n; + } + + // hashtables use this method, which is proxy-reference unfriendly + node_ptr operator()(const node &to_clone) + { + const value_type &v = + *traits_->to_value_ptr + (pointer_traits<const_node_ptr>::pointer_to(to_clone)); + node_ptr n = traits_->to_node_ptr(*base_t::get()(v)); + //Cloned node must be in default mode if the linking mode requires it + if(safemode_or_autounlink) + BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(n)); + return n; + } + + const ValueTraits * const traits_; +}; + +template<class F, class ValueTraits, algo_types AlgoType> +struct node_disposer + : private detail::ebo_functor_holder<F> +{ + typedef ValueTraits value_traits; + typedef typename value_traits::node_traits node_traits; + typedef typename node_traits::node_ptr node_ptr; + typedef detail::ebo_functor_holder<F> base_t; + typedef typename get_algo< AlgoType + , node_traits>::type node_algorithms; + static const bool safemode_or_autounlink = + is_safe_autounlink<value_traits::link_mode>::value; + + node_disposer(F f, const ValueTraits *cont) + : base_t(f), traits_(cont) + {} + + void operator()(const node_ptr & p) + { + if(safemode_or_autounlink) + node_algorithms::init(p); + base_t::get()(traits_->to_value_ptr(p)); + } + const ValueTraits * const traits_; +}; + +template<class VoidPointer> +struct dummy_constptr +{ + typedef typename boost::intrusive::pointer_traits<VoidPointer>:: + template rebind_pointer<const void>::type ConstVoidPtr; + + explicit dummy_constptr(ConstVoidPtr) + {} + + dummy_constptr() + {} + + ConstVoidPtr get_ptr() const + { return ConstVoidPtr(); } +}; + +template<class VoidPointer> +struct constptr +{ + typedef typename boost::intrusive::pointer_traits<VoidPointer>:: + template rebind_pointer<const void>::type ConstVoidPtr; + + constptr() + {} + + explicit constptr(const ConstVoidPtr &ptr) + : const_void_ptr_(ptr) + {} + + const void *get_ptr() const + { return boost::intrusive::detail::to_raw_pointer(const_void_ptr_); } + + ConstVoidPtr const_void_ptr_; +}; + +template <class VoidPointer, bool store_ptr> +struct select_constptr +{ + typedef typename detail::if_c + < store_ptr + , constptr<VoidPointer> + , dummy_constptr<VoidPointer> + >::type type; +}; + +template<class T, bool Add> +struct add_const_if_c +{ + typedef typename detail::if_c + < Add + , typename detail::add_const<T>::type + , T + >::type type; +}; + +template <link_mode_type LinkMode> +struct link_dispatch +{}; + +template<class Hook> +void destructor_impl(Hook &hook, detail::link_dispatch<safe_link>) +{ //If this assertion raises, you might have destroyed an object + //while it was still inserted in a container that is alive. + //If so, remove the object from the container before destroying it. + (void)hook; BOOST_INTRUSIVE_SAFE_HOOK_DESTRUCTOR_ASSERT(!hook.is_linked()); +} + +template<class Hook> +void destructor_impl(Hook &hook, detail::link_dispatch<auto_unlink>) +{ hook.unlink(); } + +template<class Hook> +void destructor_impl(Hook &, detail::link_dispatch<normal_link>) +{} + +/////////////////////////// +// floor_log2 Dispatcher +//////////////////////////// + +#if defined(_MSC_VER) && (_MSC_VER >= 1300) + + }}} //namespace boost::intrusive::detail + + //Use _BitScanReverseXX intrinsics + + #if defined(_M_X64) || defined(_M_AMD64) || defined(_M_IA64) //64 bit target + #define BOOST_INTRUSIVE_BSR_INTRINSIC_64_BIT + #endif + + #ifndef __INTRIN_H_ // Avoid including any windows system header + #ifdef __cplusplus + extern "C" { + #endif // __cplusplus + + #if defined(BOOST_INTRUSIVE_BSR_INTRINSIC_64_BIT) //64 bit target + unsigned char _BitScanReverse64(unsigned long *index, unsigned __int64 mask); + #pragma intrinsic(_BitScanReverse64) + #else //32 bit target + unsigned char _BitScanReverse(unsigned long *index, unsigned long mask); + #pragma intrinsic(_BitScanReverse) + #endif + + #ifdef __cplusplus + } + #endif // __cplusplus + #endif // __INTRIN_H_ + + #ifdef BOOST_INTRUSIVE_BSR_INTRINSIC_64_BIT + #define BOOST_INTRUSIVE_BSR_INTRINSIC _BitScanReverse64 + #undef BOOST_INTRUSIVE_BSR_INTRINSIC_64_BIT + #else + #define BOOST_INTRUSIVE_BSR_INTRINSIC _BitScanReverse + #endif + + namespace boost { + namespace intrusive { + namespace detail { + + inline std::size_t floor_log2 (std::size_t x) + { + unsigned long log2; + BOOST_INTRUSIVE_BSR_INTRINSIC( &log2, (unsigned long)x ); + return log2; + } + + #undef BOOST_INTRUSIVE_BSR_INTRINSIC + +#elif defined(__GNUC__) && ((__GNUC__ >= 4) || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)) //GCC >=3.4 + + //Compile-time error in case of missing specialization + template<class Uint> + struct builtin_clz_dispatch; + + #if defined(BOOST_HAS_LONG_LONG) + template<> + struct builtin_clz_dispatch<unsigned long long> + { + static unsigned long long call(unsigned long long n) + { return __builtin_clzll(n); } + }; + #endif + + template<> + struct builtin_clz_dispatch<unsigned long> + { + static unsigned long call(unsigned long n) + { return __builtin_clzl(n); } + }; + + template<> + struct builtin_clz_dispatch<unsigned int> + { + static unsigned int call(unsigned int n) + { return __builtin_clz(n); } + }; + + inline std::size_t floor_log2(std::size_t n) + { + return sizeof(std::size_t)*CHAR_BIT - std::size_t(1) - builtin_clz_dispatch<std::size_t>::call(n); + } + +#else //Portable methods + +//////////////////////////// +// Generic method +//////////////////////////// + + inline std::size_t floor_log2_get_shift(std::size_t n, true_ )//power of two size_t + { return n >> 1; } + + inline std::size_t floor_log2_get_shift(std::size_t n, false_ )//non-power of two size_t + { return (n >> 1) + ((n & 1u) & (n != 1)); } + + template<std::size_t N> + inline std::size_t floor_log2 (std::size_t x, integer<std::size_t, N>) + { + const std::size_t Bits = N; + const bool Size_t_Bits_Power_2= !(Bits & (Bits-1)); + + std::size_t n = x; + std::size_t log2 = 0; + + std::size_t remaining_bits = Bits; + std::size_t shift = floor_log2_get_shift(remaining_bits, bool_<Size_t_Bits_Power_2>()); + while(shift){ + std::size_t tmp = n >> shift; + if (tmp){ + log2 += shift, n = tmp; + } + shift = floor_log2_get_shift(shift, bool_<Size_t_Bits_Power_2>()); + } + + return log2; + } + + //////////////////////////// + // DeBruijn method + //////////////////////////// + + //Taken from: + //http://stackoverflow.com/questions/11376288/fast-computing-of-log2-for-64-bit-integers + //Thanks to Desmond Hume + + inline std::size_t floor_log2 (std::size_t v, integer<std::size_t, 32>) + { + static const int MultiplyDeBruijnBitPosition[32] = + { + 0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30, + 8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31 + }; + + v |= v >> 1; + v |= v >> 2; + v |= v >> 4; + v |= v >> 8; + v |= v >> 16; + + return MultiplyDeBruijnBitPosition[(std::size_t)(v * 0x07C4ACDDU) >> 27]; + } + + inline std::size_t floor_log2 (std::size_t v, integer<std::size_t, 64>) + { + static const std::size_t MultiplyDeBruijnBitPosition[64] = { + 63, 0, 58, 1, 59, 47, 53, 2, + 60, 39, 48, 27, 54, 33, 42, 3, + 61, 51, 37, 40, 49, 18, 28, 20, + 55, 30, 34, 11, 43, 14, 22, 4, + 62, 57, 46, 52, 38, 26, 32, 41, + 50, 36, 17, 19, 29, 10, 13, 21, + 56, 45, 25, 31, 35, 16, 9, 12, + 44, 24, 15, 8, 23, 7, 6, 5}; + + v |= v >> 1; + v |= v >> 2; + v |= v >> 4; + v |= v >> 8; + v |= v >> 16; + v |= v >> 32; + return MultiplyDeBruijnBitPosition[((std::size_t)((v - (v >> 1))*0x07EDD5E59A4E28C2ULL)) >> 58]; + } + + + inline std::size_t floor_log2 (std::size_t x) + { + const std::size_t Bits = sizeof(std::size_t)*CHAR_BIT; + return floor_log2(x, integer<std::size_t, Bits>()); + } + +#endif + +//Thanks to Laurent de Soras in +//http://www.flipcode.com/archives/Fast_log_Function.shtml +inline float fast_log2 (float val) +{ + union caster_t + { + boost::uint32_t x; + float val; + } caster; + + caster.val = val; + boost::uint32_t x = caster.x; + const int log_2 = int((x >> 23) & 255) - 128; + x &= ~(boost::uint32_t(255u) << 23u); + x += boost::uint32_t(127) << 23u; + caster.x = x; + val = caster.val; + //1+log2(m), m ranging from 1 to 2 + //3rd degree polynomial keeping first derivate continuity. + //For less precision the line can be commented out + val = ((-1.f/3.f) * val + 2.f) * val - (2.f/3.f); + return (val + log_2); +} + +inline std::size_t ceil_log2 (std::size_t x) +{ + return static_cast<std::size_t>((x & (x-1)) != 0) + floor_log2(x); +} + +template<class SizeType, std::size_t N> +struct numbits_eq +{ + static const bool value = sizeof(SizeType)*CHAR_BIT == N; +}; + +template<class SizeType, class Enabler = void > +struct sqrt2_pow_max; + +template <class SizeType> +struct sqrt2_pow_max<SizeType, typename enable_if< numbits_eq<SizeType, 32> >::type> +{ + static const boost::uint32_t value = 0xb504f334; + static const std::size_t pow = 31; +}; + +#ifndef BOOST_NO_INT64_T + +template <class SizeType> +struct sqrt2_pow_max<SizeType, typename enable_if< numbits_eq<SizeType, 64> >::type> +{ + static const boost::uint64_t value = 0xb504f333f9de6484ull; + static const std::size_t pow = 63; +}; + +#endif //BOOST_NO_INT64_T + +// Returns floor(pow(sqrt(2), x * 2 + 1)). +// Defined for X from 0 up to the number of bits in size_t minus 1. +inline std::size_t sqrt2_pow_2xplus1 (std::size_t x) +{ + const std::size_t value = (std::size_t)sqrt2_pow_max<std::size_t>::value; + const std::size_t pow = (std::size_t)sqrt2_pow_max<std::size_t>::pow; + return (value >> (pow - x)) + 1; +} + +template<class Container, class Disposer> +class exception_disposer +{ + Container *cont_; + Disposer &disp_; + + exception_disposer(const exception_disposer&); + exception_disposer &operator=(const exception_disposer&); + + public: + exception_disposer(Container &cont, Disposer &disp) + : cont_(&cont), disp_(disp) + {} + + void release() + { cont_ = 0; } + + ~exception_disposer() + { + if(cont_){ + cont_->clear_and_dispose(disp_); + } + } +}; + +template<class Container, class Disposer, class SizeType> +class exception_array_disposer +{ + Container *cont_; + Disposer &disp_; + SizeType &constructed_; + + exception_array_disposer(const exception_array_disposer&); + exception_array_disposer &operator=(const exception_array_disposer&); + + public: + + exception_array_disposer + (Container &cont, Disposer &disp, SizeType &constructed) + : cont_(&cont), disp_(disp), constructed_(constructed) + {} + + void release() + { cont_ = 0; } + + ~exception_array_disposer() + { + SizeType n = constructed_; + if(cont_){ + while(n--){ + cont_[n].clear_and_dispose(disp_); + } + } + } +}; + +template<class ValueTraits, bool IsConst> +struct node_to_value + : public detail::select_constptr + < typename pointer_traits + <typename ValueTraits::pointer>::template rebind_pointer<void>::type + , is_stateful_value_traits<ValueTraits>::value + >::type +{ + static const bool stateful_value_traits = is_stateful_value_traits<ValueTraits>::value; + typedef typename detail::select_constptr + < typename pointer_traits + <typename ValueTraits::pointer>:: + template rebind_pointer<void>::type + , stateful_value_traits >::type Base; + + typedef ValueTraits value_traits; + typedef typename value_traits::value_type value_type; + typedef typename value_traits::node_traits::node node; + typedef typename detail::add_const_if_c + <value_type, IsConst>::type vtype; + typedef typename detail::add_const_if_c + <node, IsConst>::type ntype; + typedef typename pointer_traits + <typename ValueTraits::pointer>:: + template rebind_pointer<ntype>::type npointer; + typedef typename pointer_traits<npointer>:: + template rebind_pointer<const ValueTraits>::type const_value_traits_ptr; + + node_to_value(const const_value_traits_ptr &ptr) + : Base(ptr) + {} + + typedef vtype & result_type; + typedef ntype & first_argument_type; + + const_value_traits_ptr get_value_traits() const + { return pointer_traits<const_value_traits_ptr>::static_cast_from(Base::get_ptr()); } + + result_type to_value(first_argument_type arg, false_) const + { return *(value_traits::to_value_ptr(pointer_traits<npointer>::pointer_to(arg))); } + + result_type to_value(first_argument_type arg, true_) const + { return *(this->get_value_traits()->to_value_ptr(pointer_traits<npointer>::pointer_to(arg))); } + + result_type operator()(first_argument_type arg) const + { return this->to_value(arg, bool_<stateful_value_traits>()); } +}; + +//This is not standard, but should work with all compilers +union max_align +{ + char char_; + short short_; + int int_; + long long_; + #ifdef BOOST_HAS_LONG_LONG + long long long_long_; + #endif + float float_; + double double_; + long double long_double_; + void * void_ptr_; +}; + +template<class T, std::size_t N> +class array_initializer +{ + public: + template<class CommonInitializer> + array_initializer(const CommonInitializer &init) + { + char *init_buf = (char*)rawbuf; + std::size_t i = 0; + BOOST_TRY{ + for(; i != N; ++i){ + new(init_buf)T(init); + init_buf += sizeof(T); + } + } + BOOST_CATCH(...){ + while(i--){ + init_buf -= sizeof(T); + ((T*)init_buf)->~T(); + } + BOOST_RETHROW; + } + BOOST_CATCH_END + } + + operator T* () + { return (T*)(rawbuf); } + + operator const T*() const + { return (const T*)(rawbuf); } + + ~array_initializer() + { + char *init_buf = (char*)rawbuf + N*sizeof(T); + for(std::size_t i = 0; i != N; ++i){ + init_buf -= sizeof(T); + ((T*)init_buf)->~T(); + } + } + + private: + detail::max_align rawbuf[(N*sizeof(T)-1)/sizeof(detail::max_align)+1]; +}; + + + + +template<class It> +class reverse_iterator + : public std::iterator< + typename std::iterator_traits<It>::iterator_category, + typename std::iterator_traits<It>::value_type, + typename std::iterator_traits<It>::difference_type, + typename std::iterator_traits<It>::pointer, + typename std::iterator_traits<It>::reference> +{ + public: + typedef typename std::iterator_traits<It>::pointer pointer; + typedef typename std::iterator_traits<It>::reference reference; + typedef typename std::iterator_traits<It>::difference_type difference_type; + typedef It iterator_type; + + reverse_iterator(){} + + explicit reverse_iterator(It r) + : m_current(r) + {} + + template<class OtherIt> + reverse_iterator(const reverse_iterator<OtherIt>& r) + : m_current(r.base()) + {} + + It base() const + { return m_current; } + + reference operator*() const + { It temp(m_current); --temp; return *temp; } + + pointer operator->() const + { It temp(m_current); --temp; return temp.operator->(); } + + reference operator[](difference_type off) const + { return this->m_current[-off]; } + + reverse_iterator& operator++() + { --m_current; return *this; } + + reverse_iterator operator++(int) + { + reverse_iterator temp = *this; + --m_current; + return temp; + } + + reverse_iterator& operator--() + { + ++m_current; + return *this; + } + + reverse_iterator operator--(int) + { + reverse_iterator temp(*this); + ++m_current; + return temp; + } + + friend bool operator==(const reverse_iterator& l, const reverse_iterator& r) + { return l.m_current == r.m_current; } + + friend bool operator!=(const reverse_iterator& l, const reverse_iterator& r) + { return l.m_current != r.m_current; } + + friend bool operator<(const reverse_iterator& l, const reverse_iterator& r) + { return l.m_current < r.m_current; } + + friend bool operator<=(const reverse_iterator& l, const reverse_iterator& r) + { return l.m_current <= r.m_current; } + + friend bool operator>(const reverse_iterator& l, const reverse_iterator& r) + { return l.m_current > r.m_current; } + + friend bool operator>=(const reverse_iterator& l, const reverse_iterator& r) + { return l.m_current >= r.m_current; } + + reverse_iterator& operator+=(difference_type off) + { m_current -= off; return *this; } + + friend reverse_iterator operator+(const reverse_iterator & l, difference_type off) + { + reverse_iterator tmp(l.m_current); + tmp.m_current -= off; + return tmp; + } + + reverse_iterator& operator-=(difference_type off) + { m_current += off; return *this; } + + friend reverse_iterator operator-(const reverse_iterator & l, difference_type off) + { + reverse_iterator tmp(l.m_current); + tmp.m_current += off; + return tmp; + } + + friend difference_type operator-(const reverse_iterator& l, const reverse_iterator& r) + { return r.m_current - l.m_current; } + + private: + It m_current; // the wrapped iterator +}; + +template<class ConstNodePtr> +struct uncast_types +{ + typedef typename pointer_traits<ConstNodePtr>::element_type element_type; + typedef typename remove_const<element_type>::type non_const_type; + typedef typename pointer_traits<ConstNodePtr>:: + template rebind_pointer<non_const_type>::type non_const_pointer; + typedef pointer_traits<non_const_pointer> non_const_traits; +}; + +template<class ConstNodePtr> +static typename uncast_types<ConstNodePtr>::non_const_pointer + uncast(const ConstNodePtr & ptr) +{ + return uncast_types<ConstNodePtr>::non_const_traits::const_cast_from(ptr); +} + +// trivial header node holder +template < typename NodeTraits > +struct default_header_holder : public NodeTraits::node +{ + typedef NodeTraits node_traits; + typedef typename node_traits::node node; + typedef typename node_traits::node_ptr node_ptr; + typedef typename node_traits::const_node_ptr const_node_ptr; + + default_header_holder() : node() {} + + const_node_ptr get_node() const + { return pointer_traits< const_node_ptr >::pointer_to(*static_cast< const node* >(this)); } + + node_ptr get_node() + { return pointer_traits< node_ptr >::pointer_to(*static_cast< node* >(this)); } + + // (unsafe) downcast used to implement container-from-iterator + static default_header_holder* get_holder(const node_ptr &p) + { return static_cast< default_header_holder* >(boost::intrusive::detail::to_raw_pointer(p)); } +}; + +// type function producing the header node holder +template < typename Value_Traits, typename HeaderHolder > +struct get_header_holder_type +{ + typedef HeaderHolder type; +}; +template < typename Value_Traits > +struct get_header_holder_type< Value_Traits, void > +{ + typedef default_header_holder< typename Value_Traits::node_traits > type; +}; + +} //namespace detail + +template<class Node, class Tag, unsigned int> +struct node_holder + : public Node +{}; + +template<class T, class NodePtr, class Tag, unsigned int Type> +struct bhtraits_base +{ + public: + typedef NodePtr node_ptr; + typedef typename pointer_traits<node_ptr>::element_type node; + typedef node_holder<node, Tag, Type> node_holder_type; + typedef T value_type; + typedef typename pointer_traits<node_ptr>:: + template rebind_pointer<const node>::type const_node_ptr; + typedef typename pointer_traits<node_ptr>:: + template rebind_pointer<T>::type pointer; + typedef typename pointer_traits<node_ptr>:: + template rebind_pointer<const T>::type const_pointer; + //typedef typename pointer_traits<pointer>::reference reference; + //typedef typename pointer_traits<const_pointer>::reference const_reference; + typedef T & reference; + typedef const T & const_reference; + typedef node_holder_type & node_holder_reference; + typedef const node_holder_type & const_node_holder_reference; + typedef node& node_reference; + typedef const node & const_node_reference; + + static pointer to_value_ptr(const node_ptr & n) + { + return pointer_traits<pointer>::pointer_to + (static_cast<reference>(static_cast<node_holder_reference>(*n))); + } + + static const_pointer to_value_ptr(const const_node_ptr & n) + { + return pointer_traits<const_pointer>::pointer_to + (static_cast<const_reference>(static_cast<const_node_holder_reference>(*n))); + } + + static node_ptr to_node_ptr(reference value) + { + return pointer_traits<node_ptr>::pointer_to + (static_cast<node_reference>(static_cast<node_holder_reference>(value))); + } + + static const_node_ptr to_node_ptr(const_reference value) + { + return pointer_traits<const_node_ptr>::pointer_to + (static_cast<const_node_reference>(static_cast<const_node_holder_reference>(value))); + } +}; + +template<class T, class NodeTraits, link_mode_type LinkMode, class Tag, unsigned int Type> +struct bhtraits + : public bhtraits_base<T, typename NodeTraits::node_ptr, Tag, Type> +{ + static const link_mode_type link_mode = LinkMode; + typedef NodeTraits node_traits; +}; + +/* +template<class T, class NodePtr, typename pointer_traits<NodePtr>::element_type T::* P> +struct mhtraits_base +{ + public: + typedef typename pointer_traits<NodePtr>::element_type node; + typedef T value_type; + typedef NodePtr node_ptr; + typedef typename pointer_traits<node_ptr>:: + template rebind_pointer<const node>::type const_node_ptr; + typedef typename pointer_traits<node_ptr>:: + template rebind_pointer<T>::type pointer; + typedef typename pointer_traits<node_ptr>:: + template rebind_pointer<const T>::type const_pointer; + typedef T & reference; + typedef const T & const_reference; + typedef node& node_reference; + typedef const node & const_node_reference; + + static node_ptr to_node_ptr(reference value) + { + return pointer_traits<node_ptr>::pointer_to + (static_cast<node_reference>(value.*P)); + } + + static const_node_ptr to_node_ptr(const_reference value) + { + return pointer_traits<const_node_ptr>::pointer_to + (static_cast<const_node_reference>(value.*P)); + } + + static pointer to_value_ptr(const node_ptr & n) + { + return pointer_traits<pointer>::pointer_to + (*detail::parent_from_member<T, node> + (boost::intrusive::detail::to_raw_pointer(n), P)); + } + + static const_pointer to_value_ptr(const const_node_ptr & n) + { + return pointer_traits<const_pointer>::pointer_to + (*detail::parent_from_member<T, node> + (boost::intrusive::detail::to_raw_pointer(n), P)); + } +}; + + +template<class T, class NodeTraits, typename NodeTraits::node T::* P, link_mode_type LinkMode> +struct mhtraits + : public mhtraits_base<T, typename NodeTraits::node_ptr, P> +{ + static const link_mode_type link_mode = LinkMode; + typedef NodeTraits node_traits; +}; +*/ + + +template<class T, class Hook, Hook T::* P> +struct mhtraits +{ + public: + typedef Hook hook_type; + typedef typename hook_type::hooktags::node_traits node_traits; + typedef typename node_traits::node node; + typedef T value_type; + typedef typename node_traits::node_ptr node_ptr; + typedef typename node_traits::const_node_ptr const_node_ptr; + typedef typename pointer_traits<node_ptr>:: + template rebind_pointer<T>::type pointer; + typedef typename pointer_traits<node_ptr>:: + template rebind_pointer<const T>::type const_pointer; + typedef T & reference; + typedef const T & const_reference; + typedef node& node_reference; + typedef const node & const_node_reference; + typedef hook_type& hook_reference; + typedef const hook_type & const_hook_reference; + + static const link_mode_type link_mode = Hook::hooktags::link_mode; + + static node_ptr to_node_ptr(reference value) + { + return pointer_traits<node_ptr>::pointer_to + (static_cast<node_reference>(static_cast<hook_reference>(value.*P))); + } + + static const_node_ptr to_node_ptr(const_reference value) + { + return pointer_traits<const_node_ptr>::pointer_to + (static_cast<const_node_reference>(static_cast<const_hook_reference>(value.*P))); + } + + static pointer to_value_ptr(const node_ptr & n) + { + return pointer_traits<pointer>::pointer_to + (*detail::parent_from_member<T, Hook> + (static_cast<Hook*>(boost::intrusive::detail::to_raw_pointer(n)), P)); + } + + static const_pointer to_value_ptr(const const_node_ptr & n) + { + return pointer_traits<const_pointer>::pointer_to + (*detail::parent_from_member<T, Hook> + (static_cast<const Hook*>(boost::intrusive::detail::to_raw_pointer(n)), P)); + } +}; + + +template<class Functor> +struct fhtraits +{ + public: + typedef typename Functor::hook_type hook_type; + typedef typename Functor::hook_ptr hook_ptr; + typedef typename Functor::const_hook_ptr const_hook_ptr; + typedef typename hook_type::hooktags::node_traits node_traits; + typedef typename node_traits::node node; + typedef typename Functor::value_type value_type; + typedef typename node_traits::node_ptr node_ptr; + typedef typename node_traits::const_node_ptr const_node_ptr; + typedef typename pointer_traits<node_ptr>:: + template rebind_pointer<value_type>::type pointer; + typedef typename pointer_traits<node_ptr>:: + template rebind_pointer<const value_type>::type const_pointer; + typedef value_type & reference; + typedef const value_type & const_reference; + static const link_mode_type link_mode = hook_type::hooktags::link_mode; + + static node_ptr to_node_ptr(reference value) + { return static_cast<node*>(boost::intrusive::detail::to_raw_pointer(Functor::to_hook_ptr(value))); } + + static const_node_ptr to_node_ptr(const_reference value) + { return static_cast<const node*>(boost::intrusive::detail::to_raw_pointer(Functor::to_hook_ptr(value))); } + + static pointer to_value_ptr(const node_ptr & n) + { return Functor::to_value_ptr(to_hook_ptr(n)); } + + static const_pointer to_value_ptr(const const_node_ptr & n) + { return Functor::to_value_ptr(to_hook_ptr(n)); } + + private: + static hook_ptr to_hook_ptr(const node_ptr & n) + { return hook_ptr(&*static_cast<hook_type*>(&*n)); } + + static const_hook_ptr to_hook_ptr(const const_node_ptr & n) + { return const_hook_ptr(&*static_cast<const hook_type*>(&*n)); } +}; + +template<class ValueTraits> +struct value_traits_pointers +{ + typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT + (boost::intrusive::detail:: + , ValueTraits, value_traits_ptr + , typename pointer_traits<typename ValueTraits::node_traits::node_ptr>::template + rebind_pointer<ValueTraits>::type) value_traits_ptr; + + typedef typename pointer_traits<value_traits_ptr>::template + rebind_pointer<ValueTraits const>::type const_value_traits_ptr; +}; + +template<class ValueTraits, bool IsConst, class Category> +struct iiterator +{ + typedef ValueTraits value_traits; + typedef typename value_traits::node_traits node_traits; + typedef typename node_traits::node node; + typedef typename node_traits::node_ptr node_ptr; + typedef ::boost::intrusive::pointer_traits<node_ptr> nodepointer_traits_t; + typedef typename nodepointer_traits_t::template + rebind_pointer<void>::type void_pointer; + typedef typename ValueTraits::value_type value_type; + typedef typename ValueTraits::pointer nonconst_pointer; + typedef typename ValueTraits::const_pointer yesconst_pointer; + typedef typename ::boost::intrusive::pointer_traits + <nonconst_pointer>::reference nonconst_reference; + typedef typename ::boost::intrusive::pointer_traits + <yesconst_pointer>::reference yesconst_reference; + typedef typename nodepointer_traits_t::difference_type difference_type; + typedef typename detail::if_c + <IsConst, yesconst_pointer, nonconst_pointer>::type pointer; + typedef typename detail::if_c + <IsConst, yesconst_reference, nonconst_reference>::type reference; + typedef std::iterator + < Category + , value_type + , difference_type + , pointer + , reference + > iterator_traits; + typedef typename value_traits_pointers + <ValueTraits>::value_traits_ptr value_traits_ptr; + typedef typename value_traits_pointers + <ValueTraits>::const_value_traits_ptr const_value_traits_ptr; + static const bool stateful_value_traits = + detail::is_stateful_value_traits<value_traits>::value; +}; + +template<class NodePtr, class StoredPointer, bool StatefulValueTraits = true> +struct iiterator_members +{ + + iiterator_members() + {} + + iiterator_members(const NodePtr &n_ptr, const StoredPointer &data) + : nodeptr_(n_ptr), ptr_(data) + {} + + StoredPointer get_ptr() const + { return ptr_; } + + NodePtr nodeptr_; + StoredPointer ptr_; +}; + +template<class NodePtr, class StoredPointer> +struct iiterator_members<NodePtr, StoredPointer, false> +{ + iiterator_members() + {} + + iiterator_members(const NodePtr &n_ptr, const StoredPointer &) + : nodeptr_(n_ptr) + {} + + StoredPointer get_ptr() const + { return StoredPointer(); } + + NodePtr nodeptr_; +}; + +template<class Less, class T> +struct get_less +{ + typedef Less type; +}; + +template<class T> +struct get_less<void, T> +{ + typedef ::std::less<T> type; +}; + +template<class EqualTo, class T> +struct get_equal_to +{ + typedef EqualTo type; +}; + +template<class T> +struct get_equal_to<void, T> +{ + typedef ::std::equal_to<T> type; +}; + +template<class Hash, class T> +struct get_hash +{ + typedef Hash type; +}; + +template<class T> +struct get_hash<void, T> +{ + typedef ::boost::hash<T> type; +}; + +struct empty{}; + +} //namespace intrusive +} //namespace boost + +#include <boost/intrusive/detail/config_end.hpp> + +#endif //BOOST_INTRUSIVE_DETAIL_UTILITIES_HPP diff --git a/3rdParty/Boost/src/boost/intrusive/detail/workaround.hpp b/3rdParty/Boost/src/boost/intrusive/detail/workaround.hpp index 87cab4b..71a50c8 100644 --- a/3rdParty/Boost/src/boost/intrusive/detail/workaround.hpp +++ b/3rdParty/Boost/src/boost/intrusive/detail/workaround.hpp @@ -1,6 +1,6 @@ ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2005-2012. Distributed under the Boost +// (C) Copyright Ion Gaztanaga 2005-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) // @@ -13,10 +13,14 @@ #include <boost/intrusive/detail/config_begin.hpp> -#if !defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_NO_VARIADIC_TEMPLATES) +#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) #define BOOST_INTRUSIVE_PERFECT_FORWARDING #endif +//Macros for documentation purposes. For code, expands to the argument +#define BOOST_INTRUSIVE_IMPDEF(TYPE) TYPE +#define BOOST_INTRUSIVE_SEEDOC(TYPE) TYPE + #include <boost/intrusive/detail/config_end.hpp> #endif //#ifndef BOOST_INTRUSIVE_DETAIL_WRKRND_HPP diff --git a/3rdParty/Boost/src/boost/intrusive/intrusive_fwd.hpp b/3rdParty/Boost/src/boost/intrusive/intrusive_fwd.hpp new file mode 100644 index 0000000..b988ae5 --- /dev/null +++ b/3rdParty/Boost/src/boost/intrusive/intrusive_fwd.hpp @@ -0,0 +1,725 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (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_FWD_HPP +#define BOOST_INTRUSIVE_FWD_HPP + +//! \file +//! This header file forward declares most Intrusive classes. +//! +//! It forward declares the following containers and hooks: +//! - boost::intrusive::slist / boost::intrusive::slist_base_hook / boost::intrusive::slist_member_hook +//! - boost::intrusive::list / boost::intrusive::list_base_hook / boost::intrusive::list_member_hook +//! - boost::intrusive::bstree / boost::intrusive::bs_set / boost::intrusive::bs_multiset / +//! boost::intrusive::bs_set_base_hook / boost::intrusive::bs_set_member_hook +//! - boost::intrusive::rbtree / boost::intrusive::set / boost::intrusive::multiset / +//! boost::intrusive::set_base_hook / boost::intrusive::set_member_hook +//! - boost::intrusive::avltree / boost::intrusive::avl_set / boost::intrusive::avl_multiset / +//! boost::intrusive::avl_set_base_hook / boost::intrusive::avl_set_member_hook +//! - boost::intrusive::splaytree / boost::intrusive::splay_set / boost::intrusive::splay_multiset +//! - boost::intrusive::sgtree / boost::intrusive::sg_set / boost::intrusive::sg_multiset +//! - boost::intrusive::treap / boost::intrusive::treap_set / boost::intrusive::treap_multiset +//! - boost::intrusive::hashtable / boost::intrusive::unordered_set / boost::intrusive::unordered_multiset / +//! boost::intrusive::unordered_set_base_hook / boost::intrusive::unordered_set_member_hook / +//! - boost::intrusive::any_base_hook / boost::intrusive::any_member_hook +//! +//! It forward declares the following container or hook options: +//! - boost::intrusive::constant_time_size / boost::intrusive::size_type / boost::intrusive::compare / boost::intrusive::equal +//! - boost::intrusive::floating_point / boost::intrusive::priority / boost::intrusive::hash +//! - boost::intrusive::value_traits / boost::intrusive::member_hook / boost::intrusive::function_hook / boost::intrusive::base_hook +//! - boost::intrusive::void_pointer / boost::intrusive::tag / boost::intrusive::link_mode +//! - boost::intrusive::optimize_size / boost::intrusive::linear / boost::intrusive::cache_last +//! - boost::intrusive::bucket_traits / boost::intrusive::store_hash / boost::intrusive::optimize_multikey +//! - boost::intrusive::power_2_buckets / boost::intrusive::cache_begin / boost::intrusive::compare_hash / boost::intrusive::incremental +//! +//! It forward declares the following value traits utilities: +//! - boost::intrusive::value_traits / boost::intrusive::derivation_value_traits / +//! boost::intrusive::trivial_value_traits +//! +//! Finally it forward declares the following general purpose utilities: +//! - boost::intrusive::pointer_plus_bits / boost::intrusive::priority_compare. + +#if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) + +#include <cstddef> +#include <boost/intrusive/link_mode.hpp> +#include <boost/intrusive/detail/workaround.hpp> + +namespace boost { +namespace intrusive { + +//////////////////////////// +// Node algorithms +//////////////////////////// + +//Algorithms predeclarations +template<class NodeTraits> +class circular_list_algorithms; + +template<class NodeTraits> +class circular_slist_algorithms; + +template<class NodeTraits> +class linear_slist_algorithms; + +template<class NodeTraits> +class bstree_algorithms; + +template<class NodeTraits> +class rbtree_algorithms; + +template<class NodeTraits> +class avltree_algorithms; + +template<class NodeTraits> +class sgtree_algorithms; + +template<class NodeTraits> +class splaytree_algorithms; + +template<class NodeTraits> +class treap_algorithms; + +//////////////////////////// +// Containers +//////////////////////////// + +//slist +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class T + , class O1 = void + , class O2 = void + , class O3 = void + , class O4 = void + , class O5 = void + , class O6 = void + > +#else +template<class T, class ...Options> +#endif +class slist; + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class O1 = void + , class O2 = void + , class O3 = void + > +#else +template<class ...Options> +#endif +class slist_base_hook; + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class O1 = void + , class O2 = void + , class O3 = void + > +#else +template<class ...Options> +#endif +class slist_member_hook; + +//list +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class T + , class O1 = void + , class O2 = void + , class O3 = void + , class O4 = void + > +#else +template<class T, class ...Options> +#endif +class list; + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class O1 = void + , class O2 = void + , class O3 = void + > +#else +template<class ...Options> +#endif +class list_base_hook; + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class O1 = void + , class O2 = void + , class O3 = void + > +#else +template<class ...Options> +#endif +class list_member_hook; + +//rbtree/set/multiset +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class T + , class O1 = void + , class O2 = void + , class O3 = void + , class O4 = void + , class O5 = void + > +#else +template<class T, class ...Options> +#endif +class rbtree; + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class T + , class O1 = void + , class O2 = void + , class O3 = void + , class O4 = void + , class O5 = void + > +#else +template<class T, class ...Options> +#endif +class set; + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class T + , class O1 = void + , class O2 = void + , class O3 = void + , class O4 = void + , class O5 = void + > +#else +template<class T, class ...Options> +#endif +class multiset; + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class O1 = void + , class O2 = void + , class O3 = void + , class O4 = void + > +#else +template<class ...Options> +#endif +class set_base_hook; + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class O1 = void + , class O2 = void + , class O3 = void + , class O4 = void + > +#else +template<class ...Options> +#endif +class set_member_hook; + +//splaytree/splay_set/splay_multiset +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class T + , class O1 = void + , class O2 = void + , class O3 = void + , class O4 = void + , class O5 = void + > +#else +template<class T, class ...Options> +#endif +class splaytree; + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class T + , class O1 = void + , class O2 = void + , class O3 = void + , class O4 = void + , class O5 = void + > +#else +template<class T, class ...Options> +#endif +class splay_set; + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class T + , class O1 = void + , class O2 = void + , class O3 = void + , class O4 = void + , class O5 = void + > +#else +template<class T, class ...Options> +#endif +class splay_multiset; + +//avltree/avl_set/avl_multiset +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class T + , class O1 = void + , class O2 = void + , class O3 = void + , class O4 = void + , class O5 = void + > +#else +template<class T, class ...Options> +#endif +class avltree; + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class T + , class O1 = void + , class O2 = void + , class O3 = void + , class O4 = void + , class O5 = void + > +#else +template<class T, class ...Options> +#endif +class avl_set; + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class T + , class O1 = void + , class O2 = void + , class O3 = void + , class O4 = void + , class O5 = void + > +#else +template<class T, class ...Options> +#endif +class avl_multiset; + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class O1 = void + , class O2 = void + , class O3 = void + , class O4 = void + > +#else +template<class ...Options> +#endif +class avl_set_base_hook; + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class O1 = void + , class O2 = void + , class O3 = void + , class O4 = void + > +#else +template<class ...Options> +#endif +class avl_set_member_hook; + + +//treap/treap_set/treap_multiset +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class T + , class O1 = void + , class O2 = void + , class O3 = void + , class O4 = void + , class O5 = void + > +#else +template<class T, class ...Options> +#endif +class treap; + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class T + , class O1 = void + , class O2 = void + , class O3 = void + , class O4 = void + , class O5 = void + > +#else +template<class T, class ...Options> +#endif +class treap_set; + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class T + , class O1 = void + , class O2 = void + , class O3 = void + , class O4 = void + , class O5 = void + > +#else +template<class T, class ...Options> +#endif +class treap_multiset; + +//sgtree/sg_set/sg_multiset +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class T + , class O1 = void + , class O2 = void + , class O3 = void + , class O4 = void + , class O5 = void + > +#else +template<class T, class ...Options> +#endif +class sgtree; + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class T + , class O1 = void + , class O2 = void + , class O3 = void + , class O4 = void + , class O5 = void + > +#else +template<class T, class ...Options> +#endif +class sg_set; + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class T + , class O1 = void + , class O2 = void + , class O3 = void + , class O4 = void + , class O5 = void + > +#else +template<class T, class ...Options> +#endif +class sg_multiset; + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class T + , class O1 = void + , class O2 = void + , class O3 = void + , class O4 = void + , class O5 = void + > +#else +template<class T, class ...Options> +#endif +class bstree; + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class T + , class O1 = void + , class O2 = void + , class O3 = void + , class O4 = void + , class O5 = void + > +#else +template<class T, class ...Options> +#endif +class bs_set; + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class T + , class O1 = void + , class O2 = void + , class O3 = void + , class O4 = void + , class O5 = void + > +#else +template<class T, class ...Options> +#endif +class bs_multiset; + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class O1 = void + , class O2 = void + , class O3 = void + > +#else +template<class ...Options> +#endif +class bs_set_base_hook; + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class O1 = void + , class O2 = void + , class O3 = void + > +#else +template<class ...Options> +#endif +class bs_set_member_hook; + +//hashtable/unordered_set/unordered_multiset + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class T + , class O1 = void + , class O2 = void + , class O3 = void + , class O4 = void + , class O5 = void + , class O6 = void + , class O7 = void + , class O8 = void + , class O9 = void + , class O10 = void + > +#else +template<class T, class ...Options> +#endif +class hashtable; + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class T + , class O1 = void + , class O2 = void + , class O3 = void + , class O4 = void + , class O5 = void + , class O6 = void + , class O7 = void + , class O8 = void + , class O9 = void + , class O10 = void + > +#else +template<class T, class ...Options> +#endif +class unordered_set; + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class T + , class O1 = void + , class O2 = void + , class O3 = void + , class O4 = void + , class O5 = void + , class O6 = void + , class O7 = void + , class O8 = void + , class O9 = void + , class O10 = void + > +#else +template<class T, class ...Options> +#endif +class unordered_multiset; + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class O1 = void + , class O2 = void + , class O3 = void + , class O4 = void + > +#else +template<class ...Options> +#endif +class unordered_set_base_hook; + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class O1 = void + , class O2 = void + , class O3 = void + , class O4 = void + > +#else +template<class ...Options> +#endif +class unordered_set_member_hook; + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class O1 = void + , class O2 = void + , class O3 = void + > +#else +template<class ...Options> +#endif +class any_base_hook; + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template + < class O1 = void + , class O2 = void + , class O3 = void + > +#else +template<class ...Options> +#endif +class any_member_hook; + +//Options + +template<bool Enabled> +struct constant_time_size; + +template<typename SizeType> +struct size_type; + +template<typename Compare> +struct compare; + +template<bool Enabled> +struct floating_point; + +template<typename Equal> +struct equal; + +template<typename Priority> +struct priority; + +template<typename Hash> +struct hash; + +template<typename ValueTraits> struct value_traits; + +template< typename Parent + , typename MemberHook + , MemberHook Parent::* PtrToMember> +struct member_hook; + +template<typename Functor> +struct function_hook; + +template<typename BaseHook> +struct base_hook; + +template<typename VoidPointer> +struct void_pointer; + +template<typename Tag> +struct tag; + +template<link_mode_type LinkType> +struct link_mode; + +template<bool Enabled> struct +optimize_size; + +template<bool Enabled> +struct linear; + +template<bool Enabled> +struct cache_last; + +template<typename BucketTraits> +struct bucket_traits; + +template<bool Enabled> +struct store_hash; + +template<bool Enabled> +struct optimize_multikey; + +template<bool Enabled> +struct power_2_buckets; + +template<bool Enabled> +struct cache_begin; + +template<bool Enabled> +struct compare_hash; + +template<bool Enabled> +struct incremental; + +//Value traits + +template<typename ValueTraits> +struct value_traits; + +template< typename Parent + , typename MemberHook + , MemberHook Parent::* PtrToMember> +struct member_hook; + +template< typename Functor> +struct function_hook; + +template<typename BaseHook> +struct base_hook; + +template<class T, class NodeTraits, link_mode_type LinkMode = safe_link> +struct derivation_value_traits; + +template<class NodeTraits, link_mode_type LinkMode = normal_link> +struct trivial_value_traits; + +//Additional utilities + +template<typename VoidPointer, std::size_t Alignment> +struct max_pointer_plus_bits; + +template<std::size_t Alignment> +struct max_pointer_plus_bits<void *, Alignment>; + +template<typename Pointer, std::size_t NumBits> +struct pointer_plus_bits; + +template<typename T, std::size_t NumBits> +struct pointer_plus_bits<T *, NumBits>; + +template<typename Ptr> +struct pointer_traits; + +template<typename T> +struct pointer_traits<T *>; + +} //namespace intrusive { +} //namespace boost { + +#endif //#if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) + +#endif //#ifndef BOOST_INTRUSIVE_FWD_HPP diff --git a/3rdParty/Boost/src/boost/intrusive/linear_slist_algorithms.hpp b/3rdParty/Boost/src/boost/intrusive/linear_slist_algorithms.hpp new file mode 100644 index 0000000..86f9bb3 --- /dev/null +++ b/3rdParty/Boost/src/boost/intrusive/linear_slist_algorithms.hpp @@ -0,0 +1,338 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Olaf Krzikalla 2004-2006. +// (C) Copyright Ion Gaztanaga 2006-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_LINEAR_SLIST_ALGORITHMS_HPP +#define BOOST_INTRUSIVE_LINEAR_SLIST_ALGORITHMS_HPP + +#include <boost/intrusive/detail/config_begin.hpp> +#include <boost/intrusive/intrusive_fwd.hpp> +#include <boost/intrusive/detail/common_slist_algorithms.hpp> +#include <boost/intrusive/detail/utilities.hpp> +#include <cstddef> +#include <utility> + +namespace boost { +namespace intrusive { + +//! linear_slist_algorithms provides basic algorithms to manipulate nodes +//! forming a linear singly linked list. +//! +//! linear_slist_algorithms is configured with a NodeTraits class, which encapsulates the +//! information about the node to be manipulated. NodeTraits must support the +//! following interface: +//! +//! <b>Typedefs</b>: +//! +//! <tt>node</tt>: The type of the node that forms the linear list +//! +//! <tt>node_ptr</tt>: A pointer to a node +//! +//! <tt>const_node_ptr</tt>: A pointer to a const node +//! +//! <b>Static functions</b>: +//! +//! <tt>static node_ptr get_next(const_node_ptr n);</tt> +//! +//! <tt>static void set_next(node_ptr n, node_ptr next);</tt> +template<class NodeTraits> +class linear_slist_algorithms + /// @cond + : public detail::common_slist_algorithms<NodeTraits> + /// @endcond +{ + /// @cond + typedef detail::common_slist_algorithms<NodeTraits> base_t; + /// @endcond + public: + typedef typename NodeTraits::node node; + typedef typename NodeTraits::node_ptr node_ptr; + typedef typename NodeTraits::const_node_ptr const_node_ptr; + typedef NodeTraits node_traits; + + #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) + + //! <b>Effects</b>: Constructs an non-used list element, putting the next + //! pointer to null: + //! <tt>NodeTraits::get_next(this_node) == node_ptr()</tt> + //! + //! <b>Complexity</b>: Constant + //! + //! <b>Throws</b>: Nothing. + static void init(const node_ptr & this_node); + + //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list. + //! + //! <b>Effects</b>: Returns true is "this_node" is the only node of a circular list: + //! or it's a not inserted node: + //! <tt>return node_ptr() == NodeTraits::get_next(this_node) || NodeTraits::get_next(this_node) == this_node</tt> + //! + //! <b>Complexity</b>: Constant + //! + //! <b>Throws</b>: Nothing. + static bool unique(const_node_ptr this_node); + + //! <b>Effects</b>: Returns true is "this_node" has the same state as if + //! it was inited using "init(node_ptr)" + //! + //! <b>Complexity</b>: Constant + //! + //! <b>Throws</b>: Nothing. + static bool inited(const_node_ptr this_node); + + //! <b>Requires</b>: prev_node must be in a circular list or be an empty circular list. + //! + //! <b>Effects</b>: Unlinks the next node of prev_node from the circular list. + //! + //! <b>Complexity</b>: Constant + //! + //! <b>Throws</b>: Nothing. + static void unlink_after(const node_ptr & prev_node); + + //! <b>Requires</b>: prev_node and last_node must be in a circular list + //! or be an empty circular list. + //! + //! <b>Effects</b>: Unlinks the range (prev_node, last_node) from the linear list. + //! + //! <b>Complexity</b>: Constant + //! + //! <b>Throws</b>: Nothing. + static void unlink_after(const node_ptr & prev_node, const node_ptr & last_node); + + //! <b>Requires</b>: prev_node must be a node of a linear list. + //! + //! <b>Effects</b>: Links this_node after prev_node in the linear list. + //! + //! <b>Complexity</b>: Constant + //! + //! <b>Throws</b>: Nothing. + static void link_after(const node_ptr & prev_node, const node_ptr & this_node); + + //! <b>Requires</b>: b and e must be nodes of the same linear list or an empty range. + //! and p must be a node of a different linear list. + //! + //! <b>Effects</b>: Removes the nodes from (b, e] range from their linear list and inserts + //! them after p in p's linear list. + //! + //! <b>Complexity</b>: Constant + //! + //! <b>Throws</b>: Nothing. + static void transfer_after(const node_ptr & p, const node_ptr & b, const node_ptr & e); + + #endif //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) + + //! <b>Effects</b>: Constructs an empty list, making this_node the only + //! node of the circular list: + //! <tt>NodeTraits::get_next(this_node) == this_node</tt>. + //! + //! <b>Complexity</b>: Constant + //! + //! <b>Throws</b>: Nothing. + static void init_header(const node_ptr & this_node) + { NodeTraits::set_next(this_node, node_ptr ()); } + + //! <b>Requires</b>: this_node and prev_init_node must be in the same linear list. + //! + //! <b>Effects</b>: Returns the previous node of this_node in the linear list starting. + //! the search from prev_init_node. The first node checked for equality + //! is NodeTraits::get_next(prev_init_node). + //! + //! <b>Complexity</b>: Linear to the number of elements between prev_init_node and this_node. + //! + //! <b>Throws</b>: Nothing. + static node_ptr get_previous_node(const node_ptr & prev_init_node, const node_ptr & this_node) + { return base_t::get_previous_node(prev_init_node, this_node); } + + //! <b>Requires</b>: this_node must be in a linear list or be an empty linear list. + //! + //! <b>Effects</b>: Returns the number of nodes in a linear list. If the linear list + //! is empty, returns 1. + //! + //! <b>Complexity</b>: Linear + //! + //! <b>Throws</b>: Nothing. + static std::size_t count(const const_node_ptr & this_node) + { + std::size_t result = 0; + const_node_ptr p = this_node; + do{ + p = NodeTraits::get_next(p); + ++result; + } while (p); + return result; + } + + //! <b>Requires</b>: this_node and other_node must be nodes inserted + //! in linear lists or be empty linear lists. + //! + //! <b>Effects</b>: Moves all the nodes previously chained after this_node after other_node + //! and vice-versa. + //! + //! <b>Complexity</b>: Constant + //! + //! <b>Throws</b>: Nothing. + static void swap_trailing_nodes(const node_ptr & this_node, const node_ptr & other_node) + { + node_ptr this_nxt = NodeTraits::get_next(this_node); + node_ptr other_nxt = NodeTraits::get_next(other_node); + NodeTraits::set_next(this_node, other_nxt); + NodeTraits::set_next(other_node, this_nxt); + } + + //! <b>Effects</b>: Reverses the order of elements in the list. + //! + //! <b>Returns</b>: The new first node of the list. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: This function is linear to the contained elements. + static node_ptr reverse(const node_ptr & p) + { + if(!p) return node_ptr(); + node_ptr i = NodeTraits::get_next(p); + node_ptr first(p); + while(i){ + node_ptr nxti(NodeTraits::get_next(i)); + base_t::unlink_after(p); + NodeTraits::set_next(i, first); + first = i; + i = nxti; + } + return first; + } + + //! <b>Effects</b>: Moves the first n nodes starting at p to the end of the list. + //! + //! <b>Returns</b>: A pair containing the new first and last node of the list or + //! if there has been any movement, a null pair if n leads to no movement. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the number of elements plus the number moved positions. + static std::pair<node_ptr, node_ptr> move_first_n_backwards(const node_ptr & p, std::size_t n) + { + std::pair<node_ptr, node_ptr> ret; + //Null shift, or count() == 0 or 1, nothing to do + if(!n || !p || !NodeTraits::get_next(p)){ + return ret; + } + + node_ptr first = p; + bool end_found = false; + node_ptr new_last = node_ptr(); + node_ptr old_last = node_ptr(); + + //Now find the new last node according to the shift count. + //If we find 0 before finding the new last node + //unlink p, shortcut the search now that we know the size of the list + //and continue. + for(std::size_t i = 1; i <= n; ++i){ + new_last = first; + first = NodeTraits::get_next(first); + if(first == node_ptr()){ + //Shortcut the shift with the modulo of the size of the list + n %= i; + if(!n) return ret; + old_last = new_last; + i = 0; + //Unlink p and continue the new first node search + first = p; + //unlink_after(new_last); + end_found = true; + } + } + + //If the p has not been found in the previous loop, find it + //starting in the new first node and unlink it + if(!end_found){ + old_last = base_t::get_previous_node(first, node_ptr()); + } + + //Now link p after the new last node + NodeTraits::set_next(old_last, p); + NodeTraits::set_next(new_last, node_ptr()); + ret.first = first; + ret.second = new_last; + return ret; + } + + //! <b>Effects</b>: Moves the first n nodes starting at p to the beginning of the list. + //! + //! <b>Returns</b>: A pair containing the new first and last node of the list or + //! if there has been any movement, a null pair if n leads to no movement. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the number of elements plus the number moved positions. + static std::pair<node_ptr, node_ptr> move_first_n_forward(const node_ptr & p, std::size_t n) + { + std::pair<node_ptr, node_ptr> ret; + //Null shift, or count() == 0 or 1, nothing to do + if(!n || !p || !NodeTraits::get_next(p)) + return ret; + + node_ptr first = p; + + //Iterate until p is found to know where the current last node is. + //If the shift count is less than the size of the list, we can also obtain + //the position of the new last node after the shift. + node_ptr old_last(first), next_to_it, new_last(p); + std::size_t distance = 1; + while(!!(next_to_it = node_traits::get_next(old_last))){ + if(distance++ > n) + new_last = node_traits::get_next(new_last); + old_last = next_to_it; + } + //If the shift was bigger or equal than the size, obtain the equivalent + //forward shifts and find the new last node. + if(distance <= n){ + //Now find the equivalent forward shifts. + //Shortcut the shift with the modulo of the size of the list + std::size_t new_before_last_pos = (distance - (n % distance))% distance; + //If the shift is a multiple of the size there is nothing to do + if(!new_before_last_pos) + return ret; + + for( new_last = p + ; --new_before_last_pos + ; new_last = node_traits::get_next(new_last)){ + //empty + } + } + + //Get the first new node + node_ptr new_first(node_traits::get_next(new_last)); + //Now put the old beginning after the old end + NodeTraits::set_next(old_last, p); + NodeTraits::set_next(new_last, node_ptr()); + ret.first = new_first; + ret.second = new_last; + return ret; + } +}; + +/// @cond + +template<class NodeTraits> +struct get_algo<LinearSListAlgorithms, NodeTraits> +{ + typedef linear_slist_algorithms<NodeTraits> type; +}; + +/// @endcond + +} //namespace intrusive +} //namespace boost + +#include <boost/intrusive/detail/config_end.hpp> + +#endif //BOOST_INTRUSIVE_LINEAR_SLIST_ALGORITHMS_HPP diff --git a/3rdParty/Boost/src/boost/intrusive/link_mode.hpp b/3rdParty/Boost/src/boost/intrusive/link_mode.hpp new file mode 100644 index 0000000..73d3044 --- /dev/null +++ b/3rdParty/Boost/src/boost/intrusive/link_mode.hpp @@ -0,0 +1,46 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-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_VALUE_LINK_TYPE_HPP +#define BOOST_INTRUSIVE_VALUE_LINK_TYPE_HPP + +namespace boost { +namespace intrusive { + +//!This enumeration defines the type of value_traits that can be defined +//!for Boost.Intrusive containers +enum link_mode_type{ + //!If this linking policy is specified in a value_traits class + //!as the link_mode, containers + //!configured with such value_traits won't set the hooks + //!of the erased values to a default state. Containers also won't + //!check that the hooks of the new values are default initialized. + normal_link, + + //!If this linking policy is specified in a value_traits class + //!as the link_mode, containers + //!configured with such value_traits will set the hooks + //!of the erased values to a default state. Containers also will + //!check that the hooks of the new values are default initialized. + safe_link, + + //!Same as "safe_link" but the user type is an auto-unlink + //!type, so the containers with constant-time size features won't be + //!compatible with value_traits configured with this policy. + //!Containers also know that the a value can be silently erased from + //!the container without using any function provided by the containers. + auto_unlink +}; +} //namespace intrusive +} //namespace boost + +#endif //BOOST_INTRUSIVE_VALUE_LINK_TYPE_HPP diff --git a/3rdParty/Boost/src/boost/intrusive/options.hpp b/3rdParty/Boost/src/boost/intrusive/options.hpp new file mode 100644 index 0000000..83eff09 --- /dev/null +++ b/3rdParty/Boost/src/boost/intrusive/options.hpp @@ -0,0 +1,386 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (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_OPTIONS_HPP +#define BOOST_INTRUSIVE_OPTIONS_HPP + +#include <boost/intrusive/detail/config_begin.hpp> +#include <boost/intrusive/intrusive_fwd.hpp> +#include <boost/intrusive/link_mode.hpp> +#include <boost/intrusive/pack_options.hpp> +#include <boost/intrusive/detail/mpl.hpp> +#include <boost/intrusive/detail/utilities.hpp> +#include <boost/static_assert.hpp> + +namespace boost { +namespace intrusive { + +#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED + +//typedef void default_tag; +struct default_tag; +struct member_tag; + +namespace detail{ + +struct default_hook_tag{}; + +#define BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER) \ +struct BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER : public default_hook_tag\ +{\ + template <class T>\ + struct apply\ + { typedef typename T::BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER type; };\ +}\ + +BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(default_list_hook); +BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(default_slist_hook); +BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(default_rbtree_hook); +BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(default_hashtable_hook); +BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(default_avltree_hook); +BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(default_bstree_hook); + +#undef BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION + +template <class T, class BaseHook> +struct concrete_hook_base_value_traits +{ + typedef typename BaseHook::hooktags tags; + typedef bhtraits + < T + , typename tags::node_traits + , tags::link_mode + , typename tags::tag + , tags::type> type; +}; + +template <class BaseHook> +struct concrete_hook_base_node_traits +{ typedef typename BaseHook::hooktags::node_traits type; }; + +template <class T, class AnyToSomeHook_ProtoValueTraits> +struct any_hook_base_value_traits +{ + //AnyToSomeHook value_traits derive from a generic_hook + //The generic_hook is configured with any_node_traits + //and AnyToSomeHook::value_traits with the correct + //node traits for the container, so use node_traits + //from AnyToSomeHook_ProtoValueTraits and the rest of + //elements from the hooktags member of the generic_hook + typedef AnyToSomeHook_ProtoValueTraits proto_value_traits; + typedef bhtraits + < T + , typename proto_value_traits::node_traits + , proto_value_traits::hooktags::link_mode + , typename proto_value_traits::hooktags::tag + , proto_value_traits::hooktags::type + > type; +}; + +template <class BaseHook> +struct any_hook_base_node_traits +{ typedef typename BaseHook::node_traits type; }; + +template<class T, class BaseHook> +struct get_base_value_traits +{ + typedef typename detail::eval_if_c + < internal_any_hook_bool_is_true<BaseHook>::value + , any_hook_base_value_traits<T, BaseHook> + , concrete_hook_base_value_traits<T, BaseHook> + >::type type; +}; + +template<class BaseHook> +struct get_base_node_traits +{ + typedef typename detail::eval_if_c + < internal_any_hook_bool_is_true<BaseHook>::value + , any_hook_base_node_traits<BaseHook> + , concrete_hook_base_node_traits<BaseHook> + >::type type; +}; + +template<class T, class MemberHook> +struct get_member_value_traits +{ + typedef typename MemberHook::member_value_traits type; +}; + +template<class MemberHook> +struct get_member_node_traits +{ + typedef typename MemberHook::member_value_traits::node_traits type; +}; + +template<class T, class SupposedValueTraits> +struct get_value_traits +{ + typedef typename detail::eval_if_c + <detail::is_convertible<SupposedValueTraits*, detail::default_hook_tag*>::value + ,detail::apply<SupposedValueTraits, T> + ,detail::identity<SupposedValueTraits> + >::type supposed_value_traits; + + //...if it's a default hook + typedef typename detail::eval_if_c + < internal_base_hook_bool_is_true<supposed_value_traits>::value + //...get it's internal value traits using + //the provided T value type. + , get_base_value_traits<T, supposed_value_traits> + //...else use its internal value traits tag + //(member hooks and custom value traits are in this group) + , detail::eval_if_c + < internal_member_value_traits<supposed_value_traits>::value + , get_member_value_traits<T, supposed_value_traits> + , detail::identity<supposed_value_traits> + > + >::type type; +}; + +template<class ValueTraits> +struct get_explicit_node_traits +{ + typedef typename ValueTraits::node_traits type; +}; + +template<class SupposedValueTraits> +struct get_node_traits +{ + typedef SupposedValueTraits supposed_value_traits; + //...if it's a base hook + typedef typename detail::eval_if_c + < internal_base_hook_bool_is_true<supposed_value_traits>::value + //...get it's internal value traits using + //the provided T value type. + , get_base_node_traits<supposed_value_traits> + //...else use its internal value traits tag + //(member hooks and custom value traits are in this group) + , detail::eval_if_c + < internal_member_value_traits<supposed_value_traits>::value + , get_member_node_traits<supposed_value_traits> + , get_explicit_node_traits<supposed_value_traits> + > + >::type type; +}; + +} //namespace detail{ + +#endif //BOOST_INTRUSIVE_DOXYGEN_INVOKED + +//!This option setter specifies if the intrusive +//!container stores its size as a member to +//!obtain constant-time size() member. +BOOST_INTRUSIVE_OPTION_CONSTANT(constant_time_size, bool, Enabled, constant_time_size) + +//!This option setter specifies a container header holder type +BOOST_INTRUSIVE_OPTION_TYPE(header_holder_type, HeaderHolder, HeaderHolder, header_holder_type) + +//!This option setter specifies the type that +//!the container will use to store its size. +BOOST_INTRUSIVE_OPTION_TYPE(size_type, SizeType, SizeType, size_type) + +//!This option setter specifies the strict weak ordering +//!comparison functor for the value type +BOOST_INTRUSIVE_OPTION_TYPE(compare, Compare, Compare, compare) + +//!This option setter for scapegoat containers specifies if +//!the intrusive scapegoat container should use a non-variable +//!alpha value that does not need floating-point operations. +//! +//!If activated, the fixed alpha value is 1/sqrt(2). This +//!option also saves some space in the container since +//!the alpha value and some additional data does not need +//!to be stored in the container. +//! +//!If the user only needs an alpha value near 1/sqrt(2), this +//!option also improves performance since avoids logarithm +//!and division operations when rebalancing the tree. +BOOST_INTRUSIVE_OPTION_CONSTANT(floating_point, bool, Enabled, floating_point) + +//!This option setter specifies the equality +//!functor for the value type +BOOST_INTRUSIVE_OPTION_TYPE(equal, Equal, Equal, equal) + +//!This option setter specifies the equality +//!functor for the value type +BOOST_INTRUSIVE_OPTION_TYPE(priority, Priority, Priority, priority) + +//!This option setter specifies the hash +//!functor for the value type +BOOST_INTRUSIVE_OPTION_TYPE(hash, Hash, Hash, hash) + +//!This option setter specifies the relationship between the type +//!to be managed by the container (the value type) and the node to be +//!used in the node algorithms. It also specifies the linking policy. +BOOST_INTRUSIVE_OPTION_TYPE(value_traits, ValueTraits, ValueTraits, proto_value_traits) + +//#define BOOST_INTRUSIVE_COMMA , +//#define BOOST_INTRUSIVE_LESS < +//#define BOOST_INTRUSIVE_MORE > +//BOOST_INTRUSIVE_OPTION_TYPE (member_hook, Parent BOOST_INTRUSIVE_COMMA class MemberHook BOOST_INTRUSIVE_COMMA MemberHook Parent::* PtrToMember , mhtraits BOOST_INTRUSIVE_LESS Parent BOOST_INTRUSIVE_COMMA MemberHook BOOST_INTRUSIVE_COMMA PtrToMember BOOST_INTRUSIVE_MORE , proto_value_traits) +//template< class Parent , class MemberHook , MemberHook Parent::* PtrToMember> +//struct member_hook { +// template<class Base> struct pack : Base { +// typedef mhtraits < Parent , MemberHook , PtrToMember > proto_value_traits; +// }; +//}; +// +//#undef BOOST_INTRUSIVE_COMMA +//#undef BOOST_INTRUSIVE_LESS +//#undef BOOST_INTRUSIVE_MORE + +//!This option setter specifies the member hook the +//!container must use. +template< typename Parent + , typename MemberHook + , MemberHook Parent::* PtrToMember> +struct member_hook +{ +// @cond +// typedef typename MemberHook::hooktags::node_traits node_traits; +// typedef typename node_traits::node node_type; +// typedef node_type Parent::* Ptr2MemNode; +// typedef mhtraits +// < Parent +// , node_traits +// //This cast is really ugly but necessary to reduce template bloat. +// //Since we control the layout between the hook and the node, and there is +// //always single inheritance, the offset of the node is exactly the offset of +// //the hook. Since the node type is shared between all member hooks, this saves +// //quite a lot of symbol stuff. +// , (Ptr2MemNode)PtrToMember +// , MemberHook::hooktags::link_mode> member_value_traits; + typedef mhtraits <Parent, MemberHook, PtrToMember> member_value_traits; + template<class Base> + struct pack : Base + { + typedef member_value_traits proto_value_traits; + }; +/// @endcond +}; + +//!This option setter specifies the function object that will +//!be used to convert between values to be inserted in a container +//!and the hook to be used for that purpose. +BOOST_INTRUSIVE_OPTION_TYPE(function_hook, Functor, fhtraits<Functor>, proto_value_traits) + +//!This option setter specifies that the container +//!must use the specified base hook +BOOST_INTRUSIVE_OPTION_TYPE(base_hook, BaseHook, BaseHook, proto_value_traits) + +//!This option setter specifies the type of +//!a void pointer. This will instruct the hook +//!to use this type of pointer instead of the +//!default one +BOOST_INTRUSIVE_OPTION_TYPE(void_pointer, VoidPointer, VoidPointer, void_pointer) + +//!This option setter specifies the type of +//!the tag of a base hook. A type cannot have two +//!base hooks of the same type, so a tag can be used +//!to differentiate two base hooks with otherwise same type +BOOST_INTRUSIVE_OPTION_TYPE(tag, Tag, Tag, tag) + +//!This option setter specifies the link mode +//!(normal_link, safe_link or auto_unlink) +BOOST_INTRUSIVE_OPTION_CONSTANT(link_mode, link_mode_type, LinkType, link_mode) + +//!This option setter specifies if the hook +//!should be optimized for size instead of for speed. +BOOST_INTRUSIVE_OPTION_CONSTANT(optimize_size, bool, Enabled, optimize_size) + +//!This option setter specifies if the slist container should +//!use a linear implementation instead of a circular one. +BOOST_INTRUSIVE_OPTION_CONSTANT(linear, bool, Enabled, linear) + +//!If true, slist also stores a pointer to the last element of the singly linked list. +//!This allows O(1) swap and splice_after(iterator, slist &) for circular slists and makes +//!possible new functions like push_back(reference) and back(). +BOOST_INTRUSIVE_OPTION_CONSTANT(cache_last, bool, Enabled, cache_last) + +//!This option setter specifies the bucket traits +//!class for unordered associative containers. When this option is specified, +//!instead of using the default bucket traits, a user defined holder will be defined +BOOST_INTRUSIVE_OPTION_TYPE(bucket_traits, BucketTraits, BucketTraits, bucket_traits) + +//!This option setter specifies if the unordered hook +//!should offer room to store the hash value. +//!Storing the hash in the hook will speed up rehashing +//!processes in applications where rehashing is frequent, +//!rehashing might throw or the value is heavy to hash. +BOOST_INTRUSIVE_OPTION_CONSTANT(store_hash, bool, Enabled, store_hash) + +//!This option setter specifies if the unordered hook +//!should offer room to store another link to another node +//!with the same key. +//!Storing this link will speed up lookups and insertions on +//!unordered_multiset containers with a great number of elements +//!with the same key. +BOOST_INTRUSIVE_OPTION_CONSTANT(optimize_multikey, bool, Enabled, optimize_multikey) + +//!This option setter specifies if the bucket array will be always power of two. +//!This allows using masks instead of the default modulo operation to determine +//!the bucket number from the hash value, leading to better performance. +//!In debug mode, if power of two buckets mode is activated, the bucket length +//!will be checked to through assertions to assure the bucket length is power of two. +BOOST_INTRUSIVE_OPTION_CONSTANT(power_2_buckets, bool, Enabled, power_2_buckets) + +//!This option setter specifies if the container will cache a pointer to the first +//!non-empty bucket so that begin() is always constant-time. +//!This is specially helpful when we can have containers with a few elements +//!but with big bucket arrays (that is, hashtables with low load factors). +BOOST_INTRUSIVE_OPTION_CONSTANT(cache_begin, bool, Enabled, cache_begin) + +//!This option setter specifies if the container will compare the hash value +//!before comparing objects. This option can't be specified if store_hash<> +//!is not true. +//!This is specially helpful when we have containers with a high load factor. +//!and the comparison function is much more expensive that comparing already +//!stored hash values. +BOOST_INTRUSIVE_OPTION_CONSTANT(compare_hash, bool, Enabled, compare_hash) + +//!This option setter specifies if the hash container will use incremental +//!hashing. With incremental hashing the cost of hash table expansion is spread +//!out across each hash table insertion operation, as opposed to be incurred all at once. +//!Therefore linear hashing is well suited for interactive applications or real-time +//!appplications where the worst-case insertion time of non-incremental hash containers +//!(rehashing the whole bucket array) is not admisible. +BOOST_INTRUSIVE_OPTION_CONSTANT(incremental, bool, Enabled, incremental) + +/// @cond + +struct none +{ + template<class Base> + struct pack : Base + {}; +}; + +struct hook_defaults +{ + typedef void* void_pointer; + static const link_mode_type link_mode = safe_link; + typedef default_tag tag; + static const bool optimize_size = false; + static const bool store_hash = false; + static const bool linear = false; + static const bool optimize_multikey = false; +}; + +/// @endcond + +} //namespace intrusive { +} //namespace boost { + +#include <boost/intrusive/detail/config_end.hpp> + +#endif //#ifndef BOOST_INTRUSIVE_OPTIONS_HPP diff --git a/3rdParty/Boost/src/boost/intrusive/pack_options.hpp b/3rdParty/Boost/src/boost/intrusive/pack_options.hpp new file mode 100644 index 0000000..7d282dd --- /dev/null +++ b/3rdParty/Boost/src/boost/intrusive/pack_options.hpp @@ -0,0 +1,370 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2013-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_PACK_OPTIONS_HPP +#define BOOST_INTRUSIVE_PACK_OPTIONS_HPP + +#include <boost/intrusive/detail/config_begin.hpp> + +namespace boost { +namespace intrusive { + +#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) + +template<class Prev, class Next> +struct do_pack +{ + //Use "pack" member template to pack options + typedef typename Next::template pack<Prev> type; +}; + +template<class Prev> +struct do_pack<Prev, void> +{ + //Avoid packing "void" to shorten template names + typedef Prev type; +}; + +template + < class DefaultOptions + , class O1 = void + , class O2 = void + , class O3 = void + , class O4 = void + , class O5 = void + , class O6 = void + , class O7 = void + , class O8 = void + , class O9 = void + , class O10 = void + , class O11 = void + > +struct pack_options +{ + // join options + typedef + typename do_pack + < typename do_pack + < typename do_pack + < typename do_pack + < typename do_pack + < typename do_pack + < typename do_pack + < typename do_pack + < typename do_pack + < typename do_pack + < typename do_pack + < DefaultOptions + , O1 + >::type + , O2 + >::type + , O3 + >::type + , O4 + >::type + , O5 + >::type + , O6 + >::type + , O7 + >::type + , O8 + >::type + , O9 + >::type + , O10 + >::type + , O11 + >::type + type; +}; +#else + +//index_tuple +template<int... Indexes> +struct index_tuple{}; + +//build_number_seq +template<std::size_t Num, typename Tuple = index_tuple<> > +struct build_number_seq; + +template<std::size_t Num, int... Indexes> +struct build_number_seq<Num, index_tuple<Indexes...> > + : build_number_seq<Num - 1, index_tuple<Indexes..., sizeof...(Indexes)> > +{}; + +template<int... Indexes> +struct build_number_seq<0, index_tuple<Indexes...> > +{ typedef index_tuple<Indexes...> type; }; + +template<class ...Types> +struct typelist +{}; + +//invert_typelist +template<class T> +struct invert_typelist; + +template<int I, typename Tuple> +struct typelist_element; + +template<int I, typename Head, typename... Tail> +struct typelist_element<I, typelist<Head, Tail...> > +{ + typedef typename typelist_element<I-1, typelist<Tail...> >::type type; +}; + +template<typename Head, typename... Tail> +struct typelist_element<0, typelist<Head, Tail...> > +{ + typedef Head type; +}; + +template<int ...Ints, class ...Types> +typelist<typename typelist_element<(sizeof...(Types) - 1) - Ints, typelist<Types...> >::type...> + inverted_typelist(index_tuple<Ints...>, typelist<Types...>) +{ + return typelist<typename typelist_element<(sizeof...(Types) - 1) - Ints, typelist<Types...> >::type...>(); +} + +//sizeof_typelist +template<class Typelist> +struct sizeof_typelist; + +template<class ...Types> +struct sizeof_typelist< typelist<Types...> > +{ + static const std::size_t value = sizeof...(Types); +}; + +//invert_typelist_impl +template<class Typelist, class Indexes> +struct invert_typelist_impl; + + +template<class Typelist, int ...Ints> +struct invert_typelist_impl< Typelist, index_tuple<Ints...> > +{ + static const std::size_t last_idx = sizeof_typelist<Typelist>::value - 1; + typedef typelist + <typename typelist_element<last_idx - Ints, Typelist>::type...> type; +}; + +template<class Typelist, int Int> +struct invert_typelist_impl< Typelist, index_tuple<Int> > +{ + typedef Typelist type; +}; + +template<class Typelist> +struct invert_typelist_impl< Typelist, index_tuple<> > +{ + typedef Typelist type; +}; + +//invert_typelist +template<class Typelist> +struct invert_typelist; + +template<class ...Types> +struct invert_typelist< typelist<Types...> > +{ + typedef typelist<Types...> typelist_t; + typedef typename build_number_seq<sizeof...(Types)>::type indexes_t; + typedef typename invert_typelist_impl<typelist_t, indexes_t>::type type; +}; + +//Do pack +template<class Typelist> +struct do_pack; + +template<> +struct do_pack<typelist<> >; + +template<class Prev> +struct do_pack<typelist<Prev> > +{ + typedef Prev type; +}; + +template<class Prev, class Last> +struct do_pack<typelist<Prev, Last> > +{ + typedef typename Prev::template pack<Last> type; +}; + +template<class Prev, class ...Others> +struct do_pack<typelist<Prev, Others...> > +{ + typedef typename Prev::template pack + <typename do_pack<typelist<Others...> >::type> type; +}; + + +template<class DefaultOptions, class ...Options> +struct pack_options +{ + typedef typelist<DefaultOptions, Options...> typelist_t; + typedef typename invert_typelist<typelist_t>::type inverted_typelist; + typedef typename do_pack<inverted_typelist>::type type; +}; + +#endif //!defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) + +#define BOOST_INTRUSIVE_OPTION_TYPE(OPTION_NAME, TYPE, TYPEDEF_EXPR, TYPEDEF_NAME) \ +template< class TYPE> \ +struct OPTION_NAME \ +{ \ + template<class Base> \ + struct pack : Base \ + { \ + typedef TYPEDEF_EXPR TYPEDEF_NAME; \ + }; \ +}; \ +// + +#define BOOST_INTRUSIVE_OPTION_CONSTANT(OPTION_NAME, TYPE, VALUE, CONSTANT_NAME) \ +template< TYPE VALUE> \ +struct OPTION_NAME \ +{ \ + template<class Base> \ + struct pack : Base \ + { \ + static const TYPE CONSTANT_NAME = VALUE; \ + }; \ +}; \ +// + +#else //#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED + +//! This class is a utility that takes: +//! - a default options class defining initial static constant +//! and typedefs +//! - several options defined with BOOST_INTRUSIVE_OPTION_CONSTANT and +//! BOOST_INTRUSIVE_OPTION_TYPE +//! +//! and packs them together in a new type that defines all options as +//! member typedefs or static constant values. Given options of form: +//! +//! \code +//! BOOST_INTRUSIVE_OPTION_TYPE(my_pointer, VoidPointer, VoidPointer, my_pointer_type) +//! BOOST_INTRUSIVE_OPTION_CONSTANT(incremental, bool, Enabled, is_incremental) +//! \endcode +//! +//! the following expression +//! +//! \code +//! +//! struct default_options +//! { +//! typedef long int_type; +//! static const int int_constant = -1; +//! }; +//! +//! pack_options< default_options, my_pointer<void*>, incremental<true> >::type +//! \endcode +//! +//! will create a type that will contain the following typedefs/constants +//! +//! \code +//! struct unspecified_type +//! { +//! //Default options +//! typedef long int_type; +//! static const int int_constant = -1; +//! +//! //Packed options (will ovewrite any default option) +//! typedef void* my_pointer_type; +//! static const bool is_incremental = true; +//! }; +//! \endcode +//! +//! If an option is specified in the default options argument and later +//! redefined as an option, the last definition will prevail. +template<class DefaultOptions, class ...Options> +struct pack_options +{ + typedef unspecified_type type; +}; + +//! Defines an option class of name OPTION_NAME that can be used to specify a type +//! of type TYPE... +//! +//! \code +//! struct OPTION_NAME<class TYPE> +//! { /*unspecified_content*/ }; +//! \endcode +//! +//! ...that after being combined with +//! <code>boost::intrusive::pack_options</code>, +//! will typedef TYPE as a typedef of name TYPEDEF_NAME. Example: +//! +//! \code +//! //[includes and namespaces omitted for brevity] +//! +//! //This macro will create the following class: +//! // template<class VoidPointer> +//! // struct my_pointer +//! // { unspecified_content }; +//! BOOST_INTRUSIVE_OPTION_TYPE(my_pointer, VoidPointer, boost::remove_pointer<VoidPointer>::type, my_pointer_type) +//! +//! struct empty_default{}; +//! +//! typedef pack_options< empty_default, typename my_pointer<void*> >::type::my_pointer_type type; +//! +//! BOOST_STATIC_ASSERT(( boost::is_same<type, void>::value )); +//! +//! \endcode +#define BOOST_INTRUSIVE_OPTION_TYPE(OPTION_NAME, TYPE, TYPEDEF_EXPR, TYPEDEF_NAME) + +//! Defines an option class of name OPTION_NAME that can be used to specify a constant +//! of type TYPE with value VALUE... +//! +//! \code +//! struct OPTION_NAME<TYPE VALUE> +//! { /*unspecified_content*/ }; +//! \endcode +//! +//! ...that after being combined with +//! <code>boost::intrusive::pack_options</code>, +//! will contain a CONSTANT_NAME static constant of value VALUE. Example: +//! +//! \code +//! //[includes and namespaces omitted for brevity] +//! +//! //This macro will create the following class: +//! // template<bool Enabled> +//! // struct incremental +//! // { unspecified_content }; +//! BOOST_INTRUSIVE_OPTION_CONSTANT(incremental, bool, Enabled, is_incremental) +//! +//! struct empty_default{}; +//! +//! const bool is_incremental = pack_options< empty_default, incremental<true> >::type::is_incremental; +//! +//! BOOST_STATIC_ASSERT(( is_incremental == true )); +//! +//! \endcode +#define BOOST_INTRUSIVE_OPTION_CONSTANT(OPTION_NAME, TYPE, VALUE, CONSTANT_NAME) + +#endif //#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED + + +} //namespace intrusive { +} //namespace boost { + +#include <boost/intrusive/detail/config_end.hpp> + +#endif //#ifndef BOOST_INTRUSIVE_PACK_OPTIONS_HPP diff --git a/3rdParty/Boost/src/boost/intrusive/pointer_traits.hpp b/3rdParty/Boost/src/boost/intrusive/pointer_traits.hpp index 98ca6b9..fe898f6 100644 --- a/3rdParty/Boost/src/boost/intrusive/pointer_traits.hpp +++ b/3rdParty/Boost/src/boost/intrusive/pointer_traits.hpp @@ -6,7 +6,7 @@ // ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2011-2012. Distributed under the Boost +// (C) Copyright Ion Gaztanaga 2011-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) // @@ -17,14 +17,15 @@ #ifndef BOOST_INTRUSIVE_POINTER_TRAITS_HPP #define BOOST_INTRUSIVE_POINTER_TRAITS_HPP -#if (defined _MSC_VER) && (_MSC_VER >= 1200) +#if defined(_MSC_VER) # pragma once #endif #include <boost/intrusive/detail/config_begin.hpp> +#include <boost/intrusive/intrusive_fwd.hpp> #include <boost/intrusive/detail/workaround.hpp> #include <boost/intrusive/detail/memory_util.hpp> -#include <boost/type_traits/integral_constant.hpp> +#include <boost/intrusive/detail/mpl.hpp> #include <cstddef> namespace boost { @@ -59,9 +60,7 @@ struct pointer_traits //!shall be used instead of rebind<U> to obtain a pointer to U. template <class U> using rebind = unspecified; - //!Ptr::rebind<U> if such a type exists; otherwise, SomePointer<U, Args> if Ptr is - //!a class template instantiation of the form SomePointer<T, Args>, where Args is zero or - //!more type arguments ; otherwise, the instantiation of rebind is ill-formed. + //!Ptr::reference if such a type exists (non-standard extension); otherwise, element_type & //! typedef element_type &reference; #else @@ -73,18 +72,19 @@ struct pointer_traits // typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT (boost::intrusive::detail::, Ptr, difference_type, std::ptrdiff_t) difference_type; - // - typedef typename boost::intrusive::detail::unvoid<element_type>::type& reference; + + typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT + (boost::intrusive::detail::, Ptr, reference, typename boost::intrusive::detail::unvoid_ref<element_type>::type) reference; // template <class U> struct rebind_pointer { typedef typename boost::intrusive::detail::type_rebinder<Ptr, U>::type type; }; - #if !defined(BOOST_NO_TEMPLATE_ALIASES) + #if !defined(BOOST_NO_CXX11_TEMPLATE_ALIASES) template <class U> using rebind = typename boost::intrusive::detail::type_rebinder<Ptr, U>::type; #endif - #endif //#if !defined(BOOST_NO_TEMPLATE_ALIASES) + #endif //#if !defined(BOOST_NO_CXX11_TEMPLATE_ALIASES) //! <b>Remark</b>: If element_type is (possibly cv-qualified) void, r type is unspecified; otherwise, //! it is element_type &. @@ -97,8 +97,8 @@ struct pointer_traits //tries to converts &r to pointer. const bool value = boost::intrusive::detail:: has_member_function_callable_with_pointer_to - <Ptr, typename boost::intrusive::detail::unvoid<element_type &>::type>::value; - ::boost::integral_constant<bool, value> flag; + <Ptr, reference>::value; + boost::intrusive::detail::bool_<value> flag; return pointer_traits::priv_pointer_to(flag, r); } @@ -112,7 +112,7 @@ struct pointer_traits const bool value = boost::intrusive::detail:: has_member_function_callable_with_static_cast_from <Ptr, const UPtr>::value; - ::boost::integral_constant<bool, value> flag; + boost::intrusive::detail::bool_<value> flag; return pointer_traits::priv_static_cast_from(flag, uptr); } @@ -126,7 +126,7 @@ struct pointer_traits const bool value = boost::intrusive::detail:: has_member_function_callable_with_const_cast_from <Ptr, const UPtr>::value; - ::boost::integral_constant<bool, value> flag; + boost::intrusive::detail::bool_<value> flag; return pointer_traits::priv_const_cast_from(flag, uptr); } @@ -140,7 +140,7 @@ struct pointer_traits const bool value = boost::intrusive::detail:: has_member_function_callable_with_dynamic_cast_from <Ptr, const UPtr>::value; - ::boost::integral_constant<bool, value> flag; + boost::intrusive::detail::bool_<value> flag; return pointer_traits::priv_dynamic_cast_from(flag, uptr); } @@ -157,38 +157,46 @@ struct pointer_traits { return pointer_traits::to_raw_pointer(p.operator->()); } //priv_pointer_to - static pointer priv_pointer_to(boost::true_type, typename boost::intrusive::detail::unvoid<element_type>::type& r) - { return Ptr::pointer_to(r); } + static pointer priv_pointer_to(boost::intrusive::detail::true_, reference r) + { return Ptr::pointer_to(r); } - static pointer priv_pointer_to(boost::false_type, typename boost::intrusive::detail::unvoid<element_type>::type& r) - { return pointer(boost::intrusive::detail::addressof(r)); } + static pointer priv_pointer_to(boost::intrusive::detail::false_, reference r) + { return pointer(boost::intrusive::detail::addressof(r)); } //priv_static_cast_from template<class UPtr> - static pointer priv_static_cast_from(boost::true_type, const UPtr &uptr) + static pointer priv_static_cast_from(boost::intrusive::detail::true_, const UPtr &uptr) { return Ptr::static_cast_from(uptr); } template<class UPtr> - static pointer priv_static_cast_from(boost::false_type, const UPtr &uptr) + static pointer priv_static_cast_from(boost::intrusive::detail::false_, const UPtr &uptr) { return pointer_to(*static_cast<element_type*>(to_raw_pointer(uptr))); } //priv_const_cast_from template<class UPtr> - static pointer priv_const_cast_from(boost::true_type, const UPtr &uptr) + static pointer priv_const_cast_from(boost::intrusive::detail::true_, const UPtr &uptr) { return Ptr::const_cast_from(uptr); } template<class UPtr> - static pointer priv_const_cast_from(boost::false_type, const UPtr &uptr) + static pointer priv_const_cast_from(boost::intrusive::detail::false_, const UPtr &uptr) { return pointer_to(const_cast<element_type&>(*uptr)); } //priv_dynamic_cast_from template<class UPtr> - static pointer priv_dynamic_cast_from(boost::true_type, const UPtr &uptr) + static pointer priv_dynamic_cast_from(boost::intrusive::detail::true_, const UPtr &uptr) { return Ptr::dynamic_cast_from(uptr); } template<class UPtr> - static pointer priv_dynamic_cast_from(boost::false_type, const UPtr &uptr) - { return pointer_to(*dynamic_cast<element_type*>(&*uptr)); } + static pointer priv_dynamic_cast_from(boost::intrusive::detail::false_, const UPtr &uptr) + { + element_type *p = dynamic_cast<element_type*>(&*uptr); + if(!p){ + return pointer(); + } + else{ + return pointer_to(*p); + } + } ///@endcond }; @@ -224,8 +232,8 @@ struct pointer_traits<T*> //!shall be used instead of rebind<U> to obtain a pointer to U. template <class U> using rebind = U*; #else - typedef typename boost::intrusive::detail::unvoid<element_type>::type& reference; - #if !defined(BOOST_NO_TEMPLATE_ALIASES) + typedef typename boost::intrusive::detail::unvoid_ref<element_type>::type reference; + #if !defined(BOOST_NO_CXX11_TEMPLATE_ALIASES) template <class U> using rebind = U*; #endif #endif diff --git a/3rdParty/Boost/src/boost/intrusive/slist.hpp b/3rdParty/Boost/src/boost/intrusive/slist.hpp new file mode 100644 index 0000000..74d14c1 --- /dev/null +++ b/3rdParty/Boost/src/boost/intrusive/slist.hpp @@ -0,0 +1,2199 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Olaf Krzikalla 2004-2006. +// (C) Copyright Ion Gaztanaga 2006-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_SLIST_HPP +#define BOOST_INTRUSIVE_SLIST_HPP + +#include <boost/intrusive/detail/config_begin.hpp> +#include <boost/intrusive/intrusive_fwd.hpp> +#include <boost/static_assert.hpp> +#include <boost/intrusive/detail/assert.hpp> +#include <boost/intrusive/slist_hook.hpp> +#include <boost/intrusive/circular_slist_algorithms.hpp> +#include <boost/intrusive/linear_slist_algorithms.hpp> +#include <boost/intrusive/pointer_traits.hpp> +#include <boost/intrusive/link_mode.hpp> +#include <boost/intrusive/options.hpp> +#include <boost/intrusive/detail/utilities.hpp> +#include <iterator> +#include <functional> +#include <algorithm> +#include <cstddef> //std::size_t +#include <utility> //std::pair +#include <boost/move/move.hpp> + +namespace boost { +namespace intrusive { + +/// @cond + +template<class HeaderHolder, class NodePtr, bool> +struct header_holder_plus_last +{ + HeaderHolder header_holder_; + NodePtr last_; +}; + +template<class HeaderHolder, class NodePtr> +struct header_holder_plus_last<HeaderHolder, NodePtr, false> +{ + HeaderHolder header_holder_; +}; + +struct slist_defaults +{ + typedef detail::default_slist_hook proto_value_traits; + static const bool constant_time_size = true; + static const bool linear = false; + typedef std::size_t size_type; + static const bool cache_last = false; + typedef void header_holder_type; +}; + +struct slist_bool_flags +{ + static const std::size_t linear_pos = 1u; + static const std::size_t constant_time_size_pos = 2u; + static const std::size_t cache_last_pos = 4u; +}; + + +/// @endcond + +//! The class template slist is an intrusive container, that encapsulates +//! a singly-linked list. You can use such a list to squeeze the last bit +//! of performance from your application. Unfortunately, the little gains +//! come with some huge drawbacks. A lot of member functions can't be +//! implemented as efficiently as for standard containers. To overcome +//! this limitation some other member functions with rather unusual semantics +//! have to be introduced. +//! +//! The template parameter \c T is the type to be managed by the container. +//! The user can specify additional options and if no options are provided +//! default options are used. +//! +//! The container supports the following options: +//! \c base_hook<>/member_hook<>/value_traits<>, +//! \c constant_time_size<>, \c size_type<>, +//! \c linear<> and \c cache_last<>. +//! +//! The iterators of slist are forward iterators. slist provides a static +//! function called "previous" to compute the previous iterator of a given iterator. +//! This function has linear complexity. To improve the usability esp. with +//! the '*_after' functions, ++end() == begin() and previous(begin()) == end() +//! are defined. An new special function "before_begin()" is defined, which returns +//! an iterator that points one less the beginning of the list: ++before_begin() == begin() +#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) +template<class T, class ...Options> +#else +template<class ValueTraits, class SizeType, std::size_t BoolFlags, typename HeaderHolder> +#endif +class slist_impl +{ + //Public typedefs + public: + typedef ValueTraits value_traits; + typedef typename value_traits::pointer pointer; + typedef typename value_traits::const_pointer const_pointer; + typedef typename pointer_traits<pointer>::element_type value_type; + typedef typename pointer_traits<pointer>::reference reference; + typedef typename pointer_traits<const_pointer>::reference const_reference; + typedef typename pointer_traits<pointer>::difference_type difference_type; + typedef SizeType size_type; + typedef slist_iterator<value_traits, false> iterator; + typedef slist_iterator<value_traits, true> const_iterator; + typedef typename value_traits::node_traits node_traits; + typedef typename node_traits::node node; + typedef typename node_traits::node_ptr node_ptr; + typedef typename node_traits::const_node_ptr const_node_ptr; + typedef HeaderHolder header_holder_type; + + static const bool constant_time_size = 0 != (BoolFlags & slist_bool_flags::constant_time_size_pos); + static const bool stateful_value_traits = detail::is_stateful_value_traits<value_traits>::value; + static const bool linear = 0 != (BoolFlags & slist_bool_flags::linear_pos); + static const bool cache_last = 0 != (BoolFlags & slist_bool_flags::cache_last_pos); + static const bool has_container_from_iterator = + boost::is_same< header_holder_type, detail::default_header_holder< node_traits > >::value; + + typedef typename detail::if_c + < linear + , linear_slist_algorithms<node_traits> + , circular_slist_algorithms<node_traits> + >::type node_algorithms; + + /// @cond + private: + typedef detail::size_holder<constant_time_size, size_type> size_traits; + + //noncopyable + BOOST_MOVABLE_BUT_NOT_COPYABLE(slist_impl) + + static const bool safemode_or_autounlink = is_safe_autounlink<value_traits::link_mode>::value; + + //Constant-time size is incompatible with auto-unlink hooks! + BOOST_STATIC_ASSERT(!(constant_time_size && ((int)value_traits::link_mode == (int)auto_unlink))); + //Linear singly linked lists are incompatible with auto-unlink hooks! + BOOST_STATIC_ASSERT(!(linear && ((int)value_traits::link_mode == (int)auto_unlink))); + //A list with cached last node is incompatible with auto-unlink hooks! + BOOST_STATIC_ASSERT(!(cache_last && ((int)value_traits::link_mode == (int)auto_unlink))); + + node_ptr get_end_node() + { return node_ptr(linear ? node_ptr() : this->get_root_node()); } + + const_node_ptr get_end_node() const + { + return const_node_ptr + (linear ? const_node_ptr() : this->get_root_node()); } + + node_ptr get_root_node() + { return data_.root_plus_size_.header_holder_.get_node(); } + + const_node_ptr get_root_node() const + { return data_.root_plus_size_.header_holder_.get_node(); } + + node_ptr get_last_node() + { return this->get_last_node(detail::bool_<cache_last>()); } + + const_node_ptr get_last_node() const + { return this->get_last_node(detail::bool_<cache_last>()); } + + void set_last_node(const node_ptr &n) + { return this->set_last_node(n, detail::bool_<cache_last>()); } + + static node_ptr get_last_node(detail::bool_<false>) + { + //This function shall not be used if cache_last is not true + BOOST_INTRUSIVE_INVARIANT_ASSERT(cache_last); + return node_ptr(); + } + + static void set_last_node(const node_ptr &, detail::bool_<false>) + { + //This function shall not be used if cache_last is not true + BOOST_INTRUSIVE_INVARIANT_ASSERT(cache_last); + } + + node_ptr get_last_node(detail::bool_<true>) + { return node_ptr(data_.root_plus_size_.last_); } + + const_node_ptr get_last_node(detail::bool_<true>) const + { return const_node_ptr(data_.root_plus_size_.last_); } + + void set_last_node(const node_ptr & n, detail::bool_<true>) + { data_.root_plus_size_.last_ = n; } + + void set_default_constructed_state() + { + node_algorithms::init_header(this->get_root_node()); + this->priv_size_traits().set_size(size_type(0)); + if(cache_last){ + this->set_last_node(this->get_root_node()); + } + } + + typedef header_holder_plus_last<header_holder_type, node_ptr, cache_last> header_holder_plus_last_t; + struct root_plus_size + : public size_traits + , public header_holder_plus_last_t + {}; + + struct data_t + : public slist_impl::value_traits + { + typedef typename slist_impl::value_traits value_traits; + explicit data_t(const value_traits &val_traits) + : value_traits(val_traits) + {} + + root_plus_size root_plus_size_; + } data_; + + size_traits &priv_size_traits() + { return data_.root_plus_size_; } + + const size_traits &priv_size_traits() const + { return data_.root_plus_size_; } + + const value_traits &priv_value_traits() const + { return data_; } + + value_traits &priv_value_traits() + { return data_; } + + typedef typename boost::intrusive::value_traits_pointers + <ValueTraits>::const_value_traits_ptr const_value_traits_ptr; + + const_value_traits_ptr priv_value_traits_ptr() const + { return pointer_traits<const_value_traits_ptr>::pointer_to(this->priv_value_traits()); } + + /// @endcond + + public: + + ///@cond + + //! <b>Requires</b>: f and before_l belong to another slist. + //! + //! <b>Effects</b>: Transfers the range [f, before_l] to this + //! list, after the element pointed by prev_pos. + //! No destructors or copy constructors are called. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the number of elements transferred + //! if constant_time_size is true. Constant-time otherwise. + //! + //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this + //! list. Iterators of this list and all the references are not invalidated. + //! + //! <b>Warning</b>: Experimental function, don't use it! + slist_impl( const node_ptr & f, const node_ptr & before_l + , size_type n, const value_traits &v_traits = value_traits()) + : data_(v_traits) + { + if(n){ + this->priv_size_traits().set_size(n); + if(cache_last){ + this->set_last_node(before_l); + } + node_traits::set_next(this->get_root_node(), f); + node_traits::set_next(before_l, this->get_end_node()); + } + else{ + this->set_default_constructed_state(); + } + } + + ///@endcond + + //! <b>Effects</b>: constructs an empty list. + //! + //! <b>Complexity</b>: Constant + //! + //! <b>Throws</b>: If value_traits::node_traits::node + //! constructor throws (this does not happen with predefined Boost.Intrusive hooks). + explicit slist_impl(const value_traits &v_traits = value_traits()) + : data_(v_traits) + { this->set_default_constructed_state(); } + + //! <b>Requires</b>: Dereferencing iterator must yield an lvalue of type value_type. + //! + //! <b>Effects</b>: Constructs a list equal to [b ,e). + //! + //! <b>Complexity</b>: Linear in std::distance(b, e). No copy constructors are called. + //! + //! <b>Throws</b>: If value_traits::node_traits::node + //! constructor throws (this does not happen with predefined Boost.Intrusive hooks). + template<class Iterator> + slist_impl(Iterator b, Iterator e, const value_traits &v_traits = value_traits()) + : data_(v_traits) + { + this->set_default_constructed_state(); + //nothrow, no need to rollback to release elements on exception + this->insert_after(this->cbefore_begin(), b, e); + } + + //! <b>Effects</b>: to-do + //! + slist_impl(BOOST_RV_REF(slist_impl) x) + : data_(::boost::move(x.priv_value_traits())) + { + this->priv_size_traits().set_size(size_type(0)); + node_algorithms::init_header(this->get_root_node()); + //nothrow, no need to rollback to release elements on exception + this->swap(x); + } + + //! <b>Effects</b>: to-do + //! + slist_impl& operator=(BOOST_RV_REF(slist_impl) x) + { this->swap(x); return *this; } + + //! <b>Effects</b>: If it's a safe-mode + //! or auto-unlink value, the destructor does nothing + //! (ie. no code is generated). Otherwise it detaches all elements from this. + //! In this case the objects in the list are not deleted (i.e. no destructors + //! are called), but the hooks according to the value_traits template parameter + //! are set to their default value. + //! + //! <b>Complexity</b>: Linear to the number of elements in the list, if + //! it's a safe-mode or auto-unlink value. Otherwise constant. + ~slist_impl() + { + if(is_safe_autounlink<ValueTraits::link_mode>::value){ + this->clear(); + node_algorithms::init(this->get_root_node()); + } + } + + //! <b>Effects</b>: Erases all the elements of the container. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the number of elements of the list. + //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise. + //! + //! <b>Note</b>: Invalidates the iterators (but not the references) to the erased elements. + void clear() + { + if(safemode_or_autounlink){ + this->clear_and_dispose(detail::null_disposer()); + } + else{ + this->set_default_constructed_state(); + } + } + + //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. + //! + //! <b>Effects</b>: Erases all the elements of the container + //! Disposer::operator()(pointer) is called for the removed elements. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the number of elements of the list. + //! + //! <b>Note</b>: Invalidates the iterators to the erased elements. + template <class Disposer> + void clear_and_dispose(Disposer disposer) + { + const_iterator it(this->begin()), itend(this->end()); + while(it != itend){ + node_ptr to_erase(it.pointed_node()); + ++it; + if(safemode_or_autounlink) + node_algorithms::init(to_erase); + disposer(priv_value_traits().to_value_ptr(to_erase)); + } + this->set_default_constructed_state(); + } + + //! <b>Requires</b>: value must be an lvalue. + //! + //! <b>Effects</b>: Inserts the value in the front of the list. + //! No copy constructors are called. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + //! + //! <b>Note</b>: Does not affect the validity of iterators and references. + void push_front(reference value) + { + node_ptr to_insert = priv_value_traits().to_node_ptr(value); + if(safemode_or_autounlink) + BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::inited(to_insert)); + if(cache_last){ + if(this->empty()){ + this->set_last_node(to_insert); + } + } + node_algorithms::link_after(this->get_root_node(), to_insert); + this->priv_size_traits().increment(); + } + + //! <b>Requires</b>: value must be an lvalue. + //! + //! <b>Effects</b>: Inserts the value in the back of the list. + //! No copy constructors are called. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + //! + //! <b>Note</b>: Does not affect the validity of iterators and references. + //! This function is only available is cache_last<> is true. + void push_back(reference value) + { + BOOST_STATIC_ASSERT((cache_last)); + node_ptr n = priv_value_traits().to_node_ptr(value); + if(safemode_or_autounlink) + BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::inited(n)); + node_algorithms::link_after(this->get_last_node(), n); + if(cache_last){ + this->set_last_node(n); + } + this->priv_size_traits().increment(); + } + + //! <b>Effects</b>: Erases the first element of the list. + //! No destructors are called. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + //! + //! <b>Note</b>: Invalidates the iterators (but not the references) to the erased element. + void pop_front() + { return this->pop_front_and_dispose(detail::null_disposer()); } + + //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. + //! + //! <b>Effects</b>: Erases the first element of the list. + //! Disposer::operator()(pointer) is called for the removed element. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + //! + //! <b>Note</b>: Invalidates the iterators to the erased element. + template<class Disposer> + void pop_front_and_dispose(Disposer disposer) + { + node_ptr to_erase = node_traits::get_next(this->get_root_node()); + node_algorithms::unlink_after(this->get_root_node()); + this->priv_size_traits().decrement(); + if(safemode_or_autounlink) + node_algorithms::init(to_erase); + disposer(priv_value_traits().to_value_ptr(to_erase)); + if(cache_last){ + if(this->empty()){ + this->set_last_node(this->get_root_node()); + } + } + } + + //! <b>Effects</b>: Returns a reference to the first element of the list. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + reference front() + { return *this->priv_value_traits().to_value_ptr(node_traits::get_next(this->get_root_node())); } + + //! <b>Effects</b>: Returns a const_reference to the first element of the list. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + const_reference front() const + { return *this->priv_value_traits().to_value_ptr(detail::uncast(node_traits::get_next(this->get_root_node()))); } + + //! <b>Effects</b>: Returns a reference to the last element of the list. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + //! + //! <b>Note</b>: Does not affect the validity of iterators and references. + //! This function is only available is cache_last<> is true. + reference back() + { + BOOST_STATIC_ASSERT((cache_last)); + return *this->priv_value_traits().to_value_ptr(this->get_last_node()); + } + + //! <b>Effects</b>: Returns a const_reference to the last element of the list. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + //! + //! <b>Note</b>: Does not affect the validity of iterators and references. + //! This function is only available is cache_last<> is true. + const_reference back() const + { + BOOST_STATIC_ASSERT((cache_last)); + return *this->priv_value_traits().to_value_ptr(this->get_last_node()); + } + + //! <b>Effects</b>: Returns an iterator to the first element contained in the list. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + iterator begin() + { return iterator (node_traits::get_next(this->get_root_node()), this->priv_value_traits_ptr()); } + + //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + const_iterator begin() const + { return const_iterator (node_traits::get_next(this->get_root_node()), this->priv_value_traits_ptr()); } + + //! <b>Effects</b>: Returns a const_iterator to the first element contained in the list. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + const_iterator cbegin() const + { return const_iterator(node_traits::get_next(this->get_root_node()), this->priv_value_traits_ptr()); } + + //! <b>Effects</b>: Returns an iterator to the end of the list. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + iterator end() + { return iterator(this->get_end_node(), this->priv_value_traits_ptr()); } + + //! <b>Effects</b>: Returns a const_iterator to the end of the list. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + const_iterator end() const + { return const_iterator(detail::uncast(this->get_end_node()), this->priv_value_traits_ptr()); } + + //! <b>Effects</b>: Returns a const_iterator to the end of the list. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + const_iterator cend() const + { return this->end(); } + + //! <b>Effects</b>: Returns an iterator that points to a position + //! before the first element. Equivalent to "end()" + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + iterator before_begin() + { return iterator(this->get_root_node(), this->priv_value_traits_ptr()); } + + //! <b>Effects</b>: Returns an iterator that points to a position + //! before the first element. Equivalent to "end()" + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + const_iterator before_begin() const + { return const_iterator(detail::uncast(this->get_root_node()), this->priv_value_traits_ptr()); } + + //! <b>Effects</b>: Returns an iterator that points to a position + //! before the first element. Equivalent to "end()" + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + const_iterator cbefore_begin() const + { return this->before_begin(); } + + //! <b>Effects</b>: Returns an iterator to the last element contained in the list. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + //! + //! <b>Note</b>: This function is present only if cached_last<> option is true. + iterator last() + { + //This function shall not be used if cache_last is not true + BOOST_INTRUSIVE_INVARIANT_ASSERT(cache_last); + return iterator (this->get_last_node(), this->priv_value_traits_ptr()); + } + + //! <b>Effects</b>: Returns a const_iterator to the last element contained in the list. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + //! + //! <b>Note</b>: This function is present only if cached_last<> option is true. + const_iterator last() const + { + //This function shall not be used if cache_last is not true + BOOST_INTRUSIVE_INVARIANT_ASSERT(cache_last); + return const_iterator (this->get_last_node(), this->priv_value_traits_ptr()); + } + + //! <b>Effects</b>: Returns a const_iterator to the last element contained in the list. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + //! + //! <b>Note</b>: This function is present only if cached_last<> option is true. + const_iterator clast() const + { return const_iterator(this->get_last_node(), this->priv_value_traits_ptr()); } + + //! <b>Precondition</b>: end_iterator must be a valid end iterator + //! of slist. + //! + //! <b>Effects</b>: Returns a const reference to the slist associated to the end iterator + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + static slist_impl &container_from_end_iterator(iterator end_iterator) + { return slist_impl::priv_container_from_end_iterator(end_iterator); } + + //! <b>Precondition</b>: end_iterator must be a valid end const_iterator + //! of slist. + //! + //! <b>Effects</b>: Returns a const reference to the slist associated to the end iterator + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + static const slist_impl &container_from_end_iterator(const_iterator end_iterator) + { return slist_impl::priv_container_from_end_iterator(end_iterator); } + + //! <b>Effects</b>: Returns the number of the elements contained in the list. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the number of elements contained in the list. + //! if constant_time_size is false. Constant time otherwise. + //! + //! <b>Note</b>: Does not affect the validity of iterators and references. + size_type size() const + { + if(constant_time_size) + return this->priv_size_traits().get_size(); + else + return node_algorithms::count(this->get_root_node()) - 1; + } + + //! <b>Effects</b>: Returns true if the list contains no elements. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + //! + //! <b>Note</b>: Does not affect the validity of iterators and references. + bool empty() const + { return node_algorithms::unique(this->get_root_node()); } + + //! <b>Effects</b>: Swaps the elements of x and *this. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the number of elements of both lists. + //! Constant-time if linear<> and/or cache_last<> options are used. + //! + //! <b>Note</b>: Does not affect the validity of iterators and references. + void swap(slist_impl& other) + { + if(cache_last){ + priv_swap_cache_last(this, &other); + } + else{ + this->priv_swap_lists(this->get_root_node(), other.get_root_node(), detail::bool_<linear>()); + } + if(constant_time_size){ + size_type backup = this->priv_size_traits().get_size(); + this->priv_size_traits().set_size(other.priv_size_traits().get_size()); + other.priv_size_traits().set_size(backup); + } + } + + //! <b>Effects</b>: Moves backwards all the elements, so that the first + //! element becomes the second, the second becomes the third... + //! the last element becomes the first one. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the number of elements plus the number shifts. + //! + //! <b>Note</b>: Iterators Does not affect the validity of iterators and references. + void shift_backwards(size_type n = 1) + { this->priv_shift_backwards(n, detail::bool_<linear>()); } + + //! <b>Effects</b>: Moves forward all the elements, so that the second + //! element becomes the first, the third becomes the second... + //! the first element becomes the last one. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the number of elements plus the number shifts. + //! + //! <b>Note</b>: Does not affect the validity of iterators and references. + void shift_forward(size_type n = 1) + { this->priv_shift_forward(n, detail::bool_<linear>()); } + + //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. + //! Cloner should yield to nodes equivalent to the original nodes. + //! + //! <b>Effects</b>: Erases all the elements from *this + //! calling Disposer::operator()(pointer), clones all the + //! elements from src calling Cloner::operator()(const_reference ) + //! and inserts them on *this. + //! + //! If cloner throws, all cloned elements are unlinked and disposed + //! calling Disposer::operator()(pointer). + //! + //! <b>Complexity</b>: Linear to erased plus inserted elements. + //! + //! <b>Throws</b>: If cloner throws. + template <class Cloner, class Disposer> + void clone_from(const slist_impl &src, Cloner cloner, Disposer disposer) + { + this->clear_and_dispose(disposer); + detail::exception_disposer<slist_impl, Disposer> + rollback(*this, disposer); + const_iterator prev(this->cbefore_begin()); + const_iterator b(src.begin()), e(src.end()); + for(; b != e; ++b){ + prev = this->insert_after(prev, *cloner(*b)); + } + rollback.release(); + } + + //! <b>Requires</b>: value must be an lvalue and prev_p must point to an element + //! contained by the list or to end(). + //! + //! <b>Effects</b>: Inserts the value after the position pointed by prev_p. + //! No copy constructor is called. + //! + //! <b>Returns</b>: An iterator to the inserted element. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + //! + //! <b>Note</b>: Does not affect the validity of iterators and references. + iterator insert_after(const_iterator prev_p, reference value) + { + node_ptr n = priv_value_traits().to_node_ptr(value); + if(safemode_or_autounlink) + BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::inited(n)); + node_ptr prev_n(prev_p.pointed_node()); + node_algorithms::link_after(prev_n, n); + if(cache_last && (this->get_last_node() == prev_n)){ + this->set_last_node(n); + } + this->priv_size_traits().increment(); + return iterator (n, this->priv_value_traits_ptr()); + } + + //! <b>Requires</b>: Dereferencing iterator must yield + //! an lvalue of type value_type and prev_p must point to an element + //! contained by the list or to the end node. + //! + //! <b>Effects</b>: Inserts the [f, l) + //! after the position prev_p. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the number of elements inserted. + //! + //! <b>Note</b>: Does not affect the validity of iterators and references. + template<class Iterator> + void insert_after(const_iterator prev_p, Iterator f, Iterator l) + { + //Insert first nodes avoiding cache and size checks + size_type count = 0; + node_ptr prev_n(prev_p.pointed_node()); + for (; f != l; ++f, ++count){ + const node_ptr n = priv_value_traits().to_node_ptr(*f); + if(safemode_or_autounlink) + BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::inited(n)); + node_algorithms::link_after(prev_n, n); + prev_n = n; + } + //Now fix special cases if needed + if(cache_last && (this->get_last_node() == prev_p.pointed_node())){ + this->set_last_node(prev_n); + } + if(constant_time_size){ + this->priv_size_traits().increase(count); + } + } + + //! <b>Requires</b>: value must be an lvalue and p must point to an element + //! contained by the list or to end(). + //! + //! <b>Effects</b>: Inserts the value before the position pointed by p. + //! No copy constructor is called. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the number of elements before p. + //! Constant-time if cache_last<> is true and p == end(). + //! + //! <b>Note</b>: Does not affect the validity of iterators and references. + iterator insert(const_iterator p, reference value) + { return this->insert_after(this->previous(p), value); } + + //! <b>Requires</b>: Dereferencing iterator must yield + //! an lvalue of type value_type and p must point to an element + //! contained by the list or to the end node. + //! + //! <b>Effects</b>: Inserts the pointed by b and e + //! before the position p. No copy constructors are called. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the number of elements inserted plus linear + //! to the elements before b. + //! Linear to the number of elements to insert if cache_last<> option is true and p == end(). + //! + //! <b>Note</b>: Does not affect the validity of iterators and references. + template<class Iterator> + void insert(const_iterator p, Iterator b, Iterator e) + { return this->insert_after(this->previous(p), b, e); } + + //! <b>Effects</b>: Erases the element after the element pointed by prev of + //! the list. No destructors are called. + //! + //! <b>Returns</b>: the first element remaining beyond the removed elements, + //! or end() if no such element exists. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + //! + //! <b>Note</b>: Invalidates the iterators (but not the references) to the + //! erased element. + iterator erase_after(const_iterator prev) + { return this->erase_after_and_dispose(prev, detail::null_disposer()); } + + //! <b>Effects</b>: Erases the range (before_f, l) from + //! the list. No destructors are called. + //! + //! <b>Returns</b>: the first element remaining beyond the removed elements, + //! or end() if no such element exists. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the number of erased elements if it's a safe-mode + //! , auto-unlink value or constant-time size is activated. Constant time otherwise. + //! + //! <b>Note</b>: Invalidates the iterators (but not the references) to the + //! erased element. + iterator erase_after(const_iterator before_f, const_iterator l) + { + if(safemode_or_autounlink || constant_time_size){ + return this->erase_after_and_dispose(before_f, l, detail::null_disposer()); + } + else{ + const node_ptr bfp = before_f.pointed_node(); + const node_ptr lp = l.pointed_node(); + if(cache_last){ + if(lp == this->get_end_node()){ + this->set_last_node(bfp); + } + } + node_algorithms::unlink_after(bfp, lp); + return l.unconst(); + } + } + + //! <b>Effects</b>: Erases the range (before_f, l) from + //! the list. n must be std::distance(before_f, l) - 1. + //! No destructors are called. + //! + //! <b>Returns</b>: the first element remaining beyond the removed elements, + //! or end() if no such element exists. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: constant-time if link_mode is normal_link. + //! Linear to the elements (l - before_f) otherwise. + //! + //! <b>Note</b>: Invalidates the iterators (but not the references) to the + //! erased element. + iterator erase_after(const_iterator before_f, const_iterator l, size_type n) + { + BOOST_INTRUSIVE_INVARIANT_ASSERT(std::distance(++const_iterator(before_f), l) == difference_type(n)); + if(safemode_or_autounlink){ + return this->erase_after(before_f, l); + } + else{ + const node_ptr bfp = before_f.pointed_node(); + const node_ptr lp = l.pointed_node(); + if(cache_last){ + if((lp == this->get_end_node())){ + this->set_last_node(bfp); + } + } + node_algorithms::unlink_after(bfp, lp); + if(constant_time_size){ + this->priv_size_traits().decrease(n); + } + return l.unconst(); + } + } + + //! <b>Effects</b>: Erases the element pointed by i of the list. + //! No destructors are called. + //! + //! <b>Returns</b>: the first element remaining beyond the removed element, + //! or end() if no such element exists. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the elements before i. + //! + //! <b>Note</b>: Invalidates the iterators (but not the references) to the + //! erased element. + iterator erase(const_iterator i) + { return this->erase_after(this->previous(i)); } + + //! <b>Requires</b>: f and l must be valid iterator to elements in *this. + //! + //! <b>Effects</b>: Erases the range pointed by b and e. + //! No destructors are called. + //! + //! <b>Returns</b>: the first element remaining beyond the removed elements, + //! or end() if no such element exists. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the elements before l. + //! + //! <b>Note</b>: Invalidates the iterators (but not the references) to the + //! erased elements. + iterator erase(const_iterator f, const_iterator l) + { return this->erase_after(this->previous(f), l); } + + //! <b>Effects</b>: Erases the range [f, l) from + //! the list. n must be std::distance(f, l). + //! No destructors are called. + //! + //! <b>Returns</b>: the first element remaining beyond the removed elements, + //! or end() if no such element exists. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: linear to the elements before f if link_mode is normal_link + //! and constant_time_size is activated. Linear to the elements before l otherwise. + //! + //! <b>Note</b>: Invalidates the iterators (but not the references) to the + //! erased element. + iterator erase(const_iterator f, const_iterator l, size_type n) + { return this->erase_after(this->previous(f), l, n); } + + //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. + //! + //! <b>Effects</b>: Erases the element after the element pointed by prev of + //! the list. + //! Disposer::operator()(pointer) is called for the removed element. + //! + //! <b>Returns</b>: the first element remaining beyond the removed elements, + //! or end() if no such element exists. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + //! + //! <b>Note</b>: Invalidates the iterators to the erased element. + template<class Disposer> + iterator erase_after_and_dispose(const_iterator prev, Disposer disposer) + { + const_iterator it(prev); + ++it; + node_ptr to_erase(it.pointed_node()); + ++it; + node_ptr prev_n(prev.pointed_node()); + node_algorithms::unlink_after(prev_n); + if(cache_last && (to_erase == this->get_last_node())){ + this->set_last_node(prev_n); + } + if(safemode_or_autounlink) + node_algorithms::init(to_erase); + disposer(priv_value_traits().to_value_ptr(to_erase)); + this->priv_size_traits().decrement(); + return it.unconst(); + } + + /// @cond + + template<class Disposer> + static iterator s_erase_after_and_dispose(const_iterator prev, Disposer disposer) + { + BOOST_STATIC_ASSERT(((!cache_last)&&(!constant_time_size)&&(!stateful_value_traits))); + const_iterator it(prev); + ++it; + node_ptr to_erase(it.pointed_node()); + ++it; + node_ptr prev_n(prev.pointed_node()); + node_algorithms::unlink_after(prev_n); + if(safemode_or_autounlink) + node_algorithms::init(to_erase); + disposer(value_traits::to_value_ptr(to_erase)); + return it.unconst(); + } + + static iterator s_erase_after(const_iterator prev) + { return s_erase_after_and_dispose(prev, detail::null_disposer()); } + + /// @endcond + + //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. + //! + //! <b>Effects</b>: Erases the range (before_f, l) from + //! the list. + //! Disposer::operator()(pointer) is called for the removed elements. + //! + //! <b>Returns</b>: the first element remaining beyond the removed elements, + //! or end() if no such element exists. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Lineal to the elements (l - before_f + 1). + //! + //! <b>Note</b>: Invalidates the iterators to the erased element. + template<class Disposer> + iterator erase_after_and_dispose(const_iterator before_f, const_iterator l, Disposer disposer) + { + node_ptr bfp(before_f.pointed_node()), lp(l.pointed_node()); + node_ptr fp(node_traits::get_next(bfp)); + node_algorithms::unlink_after(bfp, lp); + while(fp != lp){ + node_ptr to_erase(fp); + fp = node_traits::get_next(fp); + if(safemode_or_autounlink) + node_algorithms::init(to_erase); + disposer(priv_value_traits().to_value_ptr(to_erase)); + this->priv_size_traits().decrement(); + } + if(cache_last && (node_traits::get_next(bfp) == this->get_end_node())){ + this->set_last_node(bfp); + } + return l.unconst(); + } + + //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. + //! + //! <b>Effects</b>: Erases the element pointed by i of the list. + //! No destructors are called. + //! Disposer::operator()(pointer) is called for the removed element. + //! + //! <b>Returns</b>: the first element remaining beyond the removed element, + //! or end() if no such element exists. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the elements before i. + //! + //! <b>Note</b>: Invalidates the iterators (but not the references) to the + //! erased element. + template<class Disposer> + iterator erase_and_dispose(const_iterator i, Disposer disposer) + { return this->erase_after_and_dispose(this->previous(i), disposer); } + + #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) + template<class Disposer> + iterator erase_and_dispose(iterator i, Disposer disposer) + { return this->erase_and_dispose(const_iterator(i), disposer); } + #endif + + //! <b>Requires</b>: f and l must be valid iterator to elements in *this. + //! Disposer::operator()(pointer) shouldn't throw. + //! + //! <b>Effects</b>: Erases the range pointed by b and e. + //! No destructors are called. + //! Disposer::operator()(pointer) is called for the removed elements. + //! + //! <b>Returns</b>: the first element remaining beyond the removed elements, + //! or end() if no such element exists. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the number of erased elements plus linear + //! to the elements before f. + //! + //! <b>Note</b>: Invalidates the iterators (but not the references) to the + //! erased elements. + template<class Disposer> + iterator erase_and_dispose(const_iterator f, const_iterator l, Disposer disposer) + { return this->erase_after_and_dispose(this->previous(f), l, disposer); } + + //! <b>Requires</b>: Dereferencing iterator must yield + //! an lvalue of type value_type. + //! + //! <b>Effects</b>: Clears the list and inserts the range pointed by b and e. + //! No destructors or copy constructors are called. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the number of elements inserted plus + //! linear to the elements contained in the list if it's a safe-mode + //! or auto-unlink value. + //! Linear to the number of elements inserted in the list otherwise. + //! + //! <b>Note</b>: Invalidates the iterators (but not the references) + //! to the erased elements. + template<class Iterator> + void assign(Iterator b, Iterator e) + { + this->clear(); + this->insert_after(this->cbefore_begin(), b, e); + } + + //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. + //! + //! <b>Requires</b>: Dereferencing iterator must yield + //! an lvalue of type value_type. + //! + //! <b>Effects</b>: Clears the list and inserts the range pointed by b and e. + //! No destructors or copy constructors are called. + //! Disposer::operator()(pointer) is called for the removed elements. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the number of elements inserted plus + //! linear to the elements contained in the list. + //! + //! <b>Note</b>: Invalidates the iterators (but not the references) + //! to the erased elements. + template<class Iterator, class Disposer> + void dispose_and_assign(Disposer disposer, Iterator b, Iterator e) + { + this->clear_and_dispose(disposer); + this->insert_after(this->cbefore_begin(), b, e, disposer); + } + + //! <b>Requires</b>: prev must point to an element contained by this list or + //! to the before_begin() element + //! + //! <b>Effects</b>: Transfers all the elements of list x to this list, after the + //! the element pointed by prev. No destructors or copy constructors are called. + //! + //! <b>Returns</b>: Nothing. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: In general, linear to the elements contained in x. + //! Constant-time if cache_last<> option is true and also constant-time if + //! linear<> option is true "this" is empty and "l" is not used. + //! + //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this + //! list. Iterators of this list and all the references are not invalidated. + //! + //! <b>Additional note</b>: If the optional parameter "l" is provided, it will be + //! assigned to the last spliced element or prev if x is empty. + //! This iterator can be used as new "prev" iterator for a new splice_after call. + //! that will splice new values after the previously spliced values. + void splice_after(const_iterator prev, slist_impl &x, const_iterator *l = 0) + { + if(x.empty()){ + if(l) *l = prev; + } + else if(linear && this->empty()){ + this->swap(x); + if(l) *l = this->previous(this->cend()); + } + else{ + const_iterator last_x(x.previous(x.end())); //<- constant time if cache_last is active + node_ptr prev_n(prev.pointed_node()); + node_ptr last_x_n(last_x.pointed_node()); + if(cache_last){ + x.set_last_node(x.get_root_node()); + if(node_traits::get_next(prev_n) == this->get_end_node()){ + this->set_last_node(last_x_n); + } + } + node_algorithms::transfer_after( prev_n, x.before_begin().pointed_node(), last_x_n); + this->priv_size_traits().increase(x.priv_size_traits().get_size()); + x.priv_size_traits().set_size(size_type(0)); + if(l) *l = last_x; + } + } + + //! <b>Requires</b>: prev must point to an element contained by this list or + //! to the before_begin() element. prev_ele must point to an element contained in list + //! x or must be x.before_begin(). + //! + //! <b>Effects</b>: Transfers the element after prev_ele, from list x to this list, + //! after the element pointed by prev. No destructors or copy constructors are called. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + //! + //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this + //! list. Iterators of this list and all the references are not invalidated. + void splice_after(const_iterator prev_pos, slist_impl &x, const_iterator prev_ele) + { + const_iterator elem = prev_ele; + this->splice_after(prev_pos, x, prev_ele, ++elem, 1); + } + + //! <b>Requires</b>: prev_pos must be a dereferenceable iterator in *this or be + //! before_begin(), and before_f and before_l belong to x and + //! ++before_f != x.end() && before_l != x.end(). + //! + //! <b>Effects</b>: Transfers the range (before_f, before_l] from list x to this + //! list, after the element pointed by prev_pos. + //! No destructors or copy constructors are called. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the number of elements transferred + //! if constant_time_size is true. Constant-time otherwise. + //! + //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this + //! list. Iterators of this list and all the references are not invalidated. + void splice_after(const_iterator prev_pos, slist_impl &x, const_iterator before_f, const_iterator before_l) + { + if(constant_time_size) + this->splice_after(prev_pos, x, before_f, before_l, std::distance(before_f, before_l)); + else + this->priv_splice_after + (prev_pos.pointed_node(), x, before_f.pointed_node(), before_l.pointed_node()); + } + + //! <b>Requires</b>: prev_pos must be a dereferenceable iterator in *this or be + //! before_begin(), and before_f and before_l belong to x and + //! ++before_f != x.end() && before_l != x.end() and + //! n == std::distance(before_f, before_l). + //! + //! <b>Effects</b>: Transfers the range (before_f, before_l] from list x to this + //! list, after the element pointed by p. No destructors or copy constructors are called. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant time. + //! + //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this + //! list. Iterators of this list and all the references are not invalidated. + void splice_after(const_iterator prev_pos, slist_impl &x, const_iterator before_f, const_iterator before_l, size_type n) + { + BOOST_INTRUSIVE_INVARIANT_ASSERT(std::distance(before_f, before_l) == difference_type(n)); + this->priv_splice_after + (prev_pos.pointed_node(), x, before_f.pointed_node(), before_l.pointed_node()); + if(constant_time_size){ + this->priv_size_traits().increase(n); + x.priv_size_traits().decrease(n); + } + } + + //! <b>Requires</b>: it is an iterator to an element in *this. + //! + //! <b>Effects</b>: Transfers all the elements of list x to this list, before the + //! the element pointed by it. No destructors or copy constructors are called. + //! + //! <b>Returns</b>: Nothing. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the elements contained in x plus linear to + //! the elements before it. + //! Linear to the elements before it if cache_last<> option is true. + //! Constant-time if cache_last<> option is true and it == end(). + //! + //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this + //! list. Iterators of this list and all the references are not invalidated. + //! + //! <b>Additional note</b>: If the optional parameter "l" is provided, it will be + //! assigned to the last spliced element or prev if x is empty. + //! This iterator can be used as new "prev" iterator for a new splice_after call. + //! that will splice new values after the previously spliced values. + void splice(const_iterator it, slist_impl &x, const_iterator *l = 0) + { this->splice_after(this->previous(it), x, l); } + + //! <b>Requires</b>: it p must be a valid iterator of *this. + //! elem must point to an element contained in list + //! x. + //! + //! <b>Effects</b>: Transfers the element elem, from list x to this list, + //! before the element pointed by pos. No destructors or copy constructors are called. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the elements before pos and before elem. + //! Linear to the elements before elem if cache_last<> option is true and pos == end(). + //! + //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this + //! list. Iterators of this list and all the references are not invalidated. + void splice(const_iterator pos, slist_impl &x, const_iterator elem) + { return this->splice_after(this->previous(pos), x, x.previous(elem)); } + + //! <b>Requires</b>: pos must be a dereferenceable iterator in *this + //! and f and f belong to x and f and f a valid range on x. + //! + //! <b>Effects</b>: Transfers the range [f, l) from list x to this + //! list, before the element pointed by pos. + //! No destructors or copy constructors are called. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the sum of elements before pos, f, and l + //! plus linear to the number of elements transferred if constant_time_size is true. + //! Linear to the sum of elements before f, and l + //! plus linear to the number of elements transferred if constant_time_size is true + //! if cache_last<> is true and pos == end() + //! + //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this + //! list. Iterators of this list and all the references are not invalidated. + void splice(const_iterator pos, slist_impl &x, const_iterator f, const_iterator l) + { return this->splice_after(this->previous(pos), x, x.previous(f), x.previous(l)); } + + //! <b>Requires</b>: pos must be a dereferenceable iterator in *this + //! and f and l belong to x and f and l a valid range on x. + //! n == std::distance(f, l). + //! + //! <b>Effects</b>: Transfers the range [f, l) from list x to this + //! list, before the element pointed by pos. + //! No destructors or copy constructors are called. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the sum of elements before pos, f, and l. + //! Linear to the sum of elements before f and l + //! if cache_last<> is true and pos == end(). + //! + //! <b>Note</b>: Iterators of values obtained from list x now point to elements of this + //! list. Iterators of this list and all the references are not invalidated. + void splice(const_iterator pos, slist_impl &x, const_iterator f, const_iterator l, size_type n) + { return this->splice_after(this->previous(pos), x, x.previous(f), x.previous(l), n); } + + //! <b>Effects</b>: This function sorts the list *this according to std::less<value_type>. + //! The sort is stable, that is, the relative order of equivalent elements is preserved. + //! + //! <b>Throws</b>: If value_traits::node_traits::node + //! constructor throws (this does not happen with predefined Boost.Intrusive hooks) + //! or the predicate throws. Basic guarantee. + //! + //! <b>Complexity</b>: The number of comparisons is approximately N log N, where N + //! is the list's size. + //! + //! <b>Note</b>: Iterators and references are not invalidated + template<class Predicate> + void sort(Predicate p) + { + if (node_traits::get_next(node_traits::get_next(this->get_root_node())) + != this->get_root_node()) { + + slist_impl carry(this->priv_value_traits()); + detail::array_initializer<slist_impl, 64> counter(this->priv_value_traits()); + int fill = 0; + const_iterator last_inserted; + while(!this->empty()){ + last_inserted = this->cbegin(); + carry.splice_after(carry.cbefore_begin(), *this, this->cbefore_begin()); + int i = 0; + while(i < fill && !counter[i].empty()) { + carry.swap(counter[i]); + carry.merge(counter[i++], p, &last_inserted); + } + BOOST_INTRUSIVE_INVARIANT_ASSERT(counter[i].empty()); + const_iterator last_element(carry.previous(last_inserted, carry.end())); + + if(constant_time_size){ + counter[i].splice_after( counter[i].cbefore_begin(), carry + , carry.cbefore_begin(), last_element + , carry.size()); + } + else{ + counter[i].splice_after( counter[i].cbefore_begin(), carry + , carry.cbefore_begin(), last_element); + } + if(i == fill) + ++fill; + } + + for (int i = 1; i < fill; ++i) + counter[i].merge(counter[i-1], p, &last_inserted); + --fill; + const_iterator last_element(counter[fill].previous(last_inserted, counter[fill].end())); + if(constant_time_size){ + this->splice_after( cbefore_begin(), counter[fill], counter[fill].cbefore_begin() + , last_element, counter[fill].size()); + } + else{ + this->splice_after( cbefore_begin(), counter[fill], counter[fill].cbefore_begin() + , last_element); + } + } + } + + //! <b>Requires</b>: p must be a comparison function that induces a strict weak + //! ordering and both *this and x must be sorted according to that ordering + //! The lists x and *this must be distinct. + //! + //! <b>Effects</b>: This function removes all of x's elements and inserts them + //! in order into *this. The merge is stable; that is, if an element from *this is + //! equivalent to one from x, then the element from *this will precede the one from x. + //! + //! <b>Throws</b>: If value_traits::node_traits::node + //! constructor throws (this does not happen with predefined Boost.Intrusive hooks) + //! or std::less<value_type> throws. Basic guarantee. + //! + //! <b>Complexity</b>: This function is linear time: it performs at most + //! size() + x.size() - 1 comparisons. + //! + //! <b>Note</b>: Iterators and references are not invalidated. + void sort() + { this->sort(std::less<value_type>()); } + + //! <b>Requires</b>: p must be a comparison function that induces a strict weak + //! ordering and both *this and x must be sorted according to that ordering + //! The lists x and *this must be distinct. + //! + //! <b>Effects</b>: This function removes all of x's elements and inserts them + //! in order into *this. The merge is stable; that is, if an element from *this is + //! equivalent to one from x, then the element from *this will precede the one from x. + //! + //! <b>Returns</b>: Nothing. + //! + //! <b>Throws</b>: If the predicate throws. Basic guarantee. + //! + //! <b>Complexity</b>: This function is linear time: it performs at most + //! size() + x.size() - 1 comparisons. + //! + //! <b>Note</b>: Iterators and references are not invalidated. + //! + //! <b>Additional note</b>: If optional "l" argument is passed, it is assigned + //! to an iterator to the last transferred value or end() is x is empty. + template<class Predicate> + void merge(slist_impl& x, Predicate p, const_iterator *l = 0) + { + const_iterator e(this->cend()), ex(x.cend()), bb(this->cbefore_begin()), + bb_next; + if(l) *l = e.unconst(); + while(!x.empty()){ + const_iterator ibx_next(x.cbefore_begin()), ibx(ibx_next++); + while (++(bb_next = bb) != e && !p(*ibx_next, *bb_next)){ + bb = bb_next; + } + if(bb_next == e){ + //Now transfer the rest to the end of the container + this->splice_after(bb, x, l); + break; + } + else{ + size_type n(0); + do{ + ibx = ibx_next; ++n; + } while(++(ibx_next = ibx) != ex && p(*ibx_next, *bb_next)); + this->splice_after(bb, x, x.before_begin(), ibx, n); + if(l) *l = ibx; + } + } + } + + //! <b>Effects</b>: This function removes all of x's elements and inserts them + //! in order into *this according to std::less<value_type>. The merge is stable; + //! that is, if an element from *this is equivalent to one from x, then the element + //! from *this will precede the one from x. + //! + //! <b>Throws</b>: if std::less<value_type> throws. Basic guarantee. + //! + //! <b>Complexity</b>: This function is linear time: it performs at most + //! size() + x.size() - 1 comparisons. + //! + //! <b>Note</b>: Iterators and references are not invalidated + void merge(slist_impl& x) + { this->merge(x, std::less<value_type>()); } + + //! <b>Effects</b>: Reverses the order of elements in the list. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: This function is linear to the contained elements. + //! + //! <b>Note</b>: Iterators and references are not invalidated + void reverse() + { + if(cache_last && !this->empty()){ + this->set_last_node(node_traits::get_next(this->get_root_node())); + } + this->priv_reverse(detail::bool_<linear>()); + } + + //! <b>Effects</b>: Removes all the elements that compare equal to value. + //! No destructors are called. + //! + //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee. + //! + //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality. + //! + //! <b>Note</b>: The relative order of elements that are not removed is unchanged, + //! and iterators to elements that are not removed remain valid. This function is + //! linear time: it performs exactly size() comparisons for equality. + void remove(const_reference value) + { this->remove_if(detail::equal_to_value<const_reference>(value)); } + + //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. + //! + //! <b>Effects</b>: Removes all the elements that compare equal to value. + //! Disposer::operator()(pointer) is called for every removed element. + //! + //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee. + //! + //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality. + //! + //! <b>Note</b>: The relative order of elements that are not removed is unchanged, + //! and iterators to elements that are not removed remain valid. + template<class Disposer> + void remove_and_dispose(const_reference value, Disposer disposer) + { this->remove_and_dispose_if(detail::equal_to_value<const_reference>(value), disposer); } + + //! <b>Effects</b>: Removes all the elements for which a specified + //! predicate is satisfied. No destructors are called. + //! + //! <b>Throws</b>: If pred throws. Basic guarantee. + //! + //! <b>Complexity</b>: Linear time. It performs exactly size() calls to the predicate. + //! + //! <b>Note</b>: The relative order of elements that are not removed is unchanged, + //! and iterators to elements that are not removed remain valid. + template<class Pred> + void remove_if(Pred pred) + { this->remove_and_dispose_if(pred, detail::null_disposer()); } + + //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. + //! + //! <b>Effects</b>: Removes all the elements for which a specified + //! predicate is satisfied. + //! Disposer::operator()(pointer) is called for every removed element. + //! + //! <b>Throws</b>: If pred throws. Basic guarantee. + //! + //! <b>Complexity</b>: Linear time. It performs exactly size() comparisons for equality. + //! + //! <b>Note</b>: The relative order of elements that are not removed is unchanged, + //! and iterators to elements that are not removed remain valid. + template<class Pred, class Disposer> + void remove_and_dispose_if(Pred pred, Disposer disposer) + { + const_iterator bcur(this->before_begin()), cur(this->begin()), e(this->end()); + + while(cur != e){ + if (pred(*cur)){ + cur = this->erase_after_and_dispose(bcur, disposer); + } + else{ + bcur = cur; + ++cur; + } + } + if(cache_last){ + this->set_last_node(bcur.pointed_node()); + } + } + + //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent + //! elements that are equal from the list. No destructors are called. + //! + //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee. + //! + //! <b>Complexity</b>: Linear time (size()-1) comparisons calls to pred()). + //! + //! <b>Note</b>: The relative order of elements that are not removed is unchanged, + //! and iterators to elements that are not removed remain valid. + void unique() + { this->unique_and_dispose(std::equal_to<value_type>(), detail::null_disposer()); } + + //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent + //! elements that satisfy some binary predicate from the list. + //! No destructors are called. + //! + //! <b>Throws</b>: If the predicate throws. Basic guarantee. + //! + //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons. + //! + //! <b>Note</b>: The relative order of elements that are not removed is unchanged, + //! and iterators to elements that are not removed remain valid. + template<class BinaryPredicate> + void unique(BinaryPredicate pred) + { this->unique_and_dispose(pred, detail::null_disposer()); } + + //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. + //! + //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent + //! elements that satisfy some binary predicate from the list. + //! Disposer::operator()(pointer) is called for every removed element. + //! + //! <b>Throws</b>: If std::equal_to<value_type> throws. Basic guarantee. + //! + //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons. + //! + //! <b>Note</b>: The relative order of elements that are not removed is unchanged, + //! and iterators to elements that are not removed remain valid. + template<class Disposer> + void unique_and_dispose(Disposer disposer) + { this->unique(std::equal_to<value_type>(), disposer); } + + //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. + //! + //! <b>Effects</b>: Removes adjacent duplicate elements or adjacent + //! elements that satisfy some binary predicate from the list. + //! Disposer::operator()(pointer) is called for every removed element. + //! + //! <b>Throws</b>: If the predicate throws. Basic guarantee. + //! + //! <b>Complexity</b>: Linear time (size()-1) comparisons equality comparisons. + //! + //! <b>Note</b>: The relative order of elements that are not removed is unchanged, + //! and iterators to elements that are not removed remain valid. + template<class BinaryPredicate, class Disposer> + void unique_and_dispose(BinaryPredicate pred, Disposer disposer) + { + const_iterator end_n(this->cend()); + const_iterator bcur(this->cbegin()); + if(bcur != end_n){ + const_iterator cur(bcur); + ++cur; + while(cur != end_n) { + if (pred(*bcur, *cur)){ + cur = this->erase_after_and_dispose(bcur, disposer); + } + else{ + bcur = cur; + ++cur; + } + } + if(cache_last){ + this->set_last_node(bcur.pointed_node()); + } + } + } + + //! <b>Requires</b>: value must be a reference to a value inserted in a list. + //! + //! <b>Effects</b>: This function returns a const_iterator pointing to the element + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant time. + //! + //! <b>Note</b>: Iterators and references are not invalidated. + //! This static function is available only if the <i>value traits</i> + //! is stateless. + static iterator s_iterator_to(reference value) + { + BOOST_STATIC_ASSERT((!stateful_value_traits)); + return iterator (value_traits::to_node_ptr(value), const_value_traits_ptr()); + } + + //! <b>Requires</b>: value must be a const reference to a value inserted in a list. + //! + //! <b>Effects</b>: This function returns an iterator pointing to the element. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant time. + //! + //! <b>Note</b>: Iterators and references are not invalidated. + //! This static function is available only if the <i>value traits</i> + //! is stateless. + static const_iterator s_iterator_to(const_reference value) + { + BOOST_STATIC_ASSERT((!stateful_value_traits)); + reference r =*pointer_traits<pointer>::const_cast_from(pointer_traits<const_pointer>::pointer_to(value)); + return const_iterator(value_traits::to_node_ptr(r), const_value_traits_ptr()); + } + + //! <b>Requires</b>: value must be a reference to a value inserted in a list. + //! + //! <b>Effects</b>: This function returns a const_iterator pointing to the element + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant time. + //! + //! <b>Note</b>: Iterators and references are not invalidated. + iterator iterator_to(reference value) + { + BOOST_INTRUSIVE_INVARIANT_ASSERT(linear || !node_algorithms::inited(this->priv_value_traits().to_node_ptr(value))); + return iterator (this->priv_value_traits().to_node_ptr(value), this->priv_value_traits_ptr()); + } + + //! <b>Requires</b>: value must be a const reference to a value inserted in a list. + //! + //! <b>Effects</b>: This function returns an iterator pointing to the element. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant time. + //! + //! <b>Note</b>: Iterators and references are not invalidated. + const_iterator iterator_to(const_reference value) const + { + reference r =*pointer_traits<pointer>::const_cast_from(pointer_traits<const_pointer>::pointer_to(value)); + BOOST_INTRUSIVE_INVARIANT_ASSERT (linear || !node_algorithms::inited(this->priv_value_traits().to_node_ptr(r))); + return const_iterator(this->priv_value_traits().to_node_ptr(r), this->priv_value_traits_ptr()); + } + + //! <b>Returns</b>: The iterator to the element before i in the list. + //! Returns the end-iterator, if either i is the begin-iterator or the + //! list is empty. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the number of elements before i. + //! Constant if cache_last<> is true and i == end(). + iterator previous(iterator i) + { return this->previous(this->cbefore_begin(), i); } + + //! <b>Returns</b>: The const_iterator to the element before i in the list. + //! Returns the end-const_iterator, if either i is the begin-const_iterator or + //! the list is empty. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the number of elements before i. + //! Constant if cache_last<> is true and i == end(). + const_iterator previous(const_iterator i) const + { return this->previous(this->cbefore_begin(), i); } + + //! <b>Returns</b>: The iterator to the element before i in the list, + //! starting the search on element after prev_from. + //! Returns the end-iterator, if either i is the begin-iterator or the + //! list is empty. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the number of elements before i. + //! Constant if cache_last<> is true and i == end(). + iterator previous(const_iterator prev_from, iterator i) + { return this->previous(prev_from, const_iterator(i)).unconst(); } + + //! <b>Returns</b>: The const_iterator to the element before i in the list, + //! starting the search on element after prev_from. + //! Returns the end-const_iterator, if either i is the begin-const_iterator or + //! the list is empty. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the number of elements before i. + //! Constant if cache_last<> is true and i == end(). + const_iterator previous(const_iterator prev_from, const_iterator i) const + { + if(cache_last && (i.pointed_node() == this->get_end_node())){ + return const_iterator(detail::uncast(this->get_last_node()), this->priv_value_traits_ptr()); + } + return const_iterator + (node_algorithms::get_previous_node + (prev_from.pointed_node(), i.pointed_node()), this->priv_value_traits_ptr()); + } + + ///@cond + + //! <b>Requires</b>: prev_pos must be a dereferenceable iterator in *this or be + //! before_begin(), and f and before_l belong to another slist. + //! + //! <b>Effects</b>: Transfers the range [f, before_l] to this + //! list, after the element pointed by prev_pos. + //! No destructors or copy constructors are called. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Linear to the number of elements transferred + //! if constant_time_size is true. Constant-time otherwise. + //! + //! <b>Note</b>: Iterators of values obtained from the list that owned f and before_l now + //! point to elements of this list. Iterators of this list and all the references are not invalidated. + //! + //! <b>Warning</b>: Experimental function, don't use it! + void incorporate_after(const_iterator prev_pos, const node_ptr & f, const node_ptr & before_l) + { + if(constant_time_size) + this->incorporate_after(prev_pos, f, before_l, std::distance(f, before_l)+1); + else + this->priv_incorporate_after(prev_pos.pointed_node(), f, before_l); + } + + //! <b>Requires</b>: prev_pos must be a dereferenceable iterator in *this or be + //! before_begin(), and f and before_l belong to another slist. + //! n == std::distance(f, before_l) + 1. + //! + //! <b>Effects</b>: Transfers the range [f, before_l] to this + //! list, after the element pointed by prev_pos. + //! No destructors or copy constructors are called. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant time. + //! + //! <b>Note</b>: Iterators of values obtained from the list that owned f and before_l now + //! point to elements of this list. Iterators of this list and all the references are not invalidated. + //! + //! <b>Warning</b>: Experimental function, don't use it! + void incorporate_after(const_iterator prev_pos, const node_ptr & f, const node_ptr & before_l, size_type n) + { + if(n){ + BOOST_INTRUSIVE_INVARIANT_ASSERT(n > 0); + BOOST_INTRUSIVE_INVARIANT_ASSERT + (size_type(std::distance + ( iterator(f, this->priv_value_traits_ptr()) + , iterator(before_l, this->priv_value_traits_ptr()))) + +1 == n); + this->priv_incorporate_after(prev_pos.pointed_node(), f, before_l); + if(constant_time_size){ + this->priv_size_traits().increase(n); + } + } + } + + ///@endcond + + private: + void priv_splice_after(const node_ptr & prev_pos_n, slist_impl &x, const node_ptr & before_f_n, const node_ptr & before_l_n) + { + if (cache_last && (before_f_n != before_l_n)){ + if(prev_pos_n == this->get_last_node()){ + this->set_last_node(before_l_n); + } + if(&x != this && node_traits::get_next(before_l_n) == x.get_end_node()){ + x.set_last_node(before_f_n); + } + } + node_algorithms::transfer_after(prev_pos_n, before_f_n, before_l_n); + } + + void priv_incorporate_after(const node_ptr & prev_pos_n, const node_ptr & first_n, const node_ptr & before_l_n) + { + if(cache_last){ + if(prev_pos_n == this->get_last_node()){ + this->set_last_node(before_l_n); + } + } + node_algorithms::incorporate_after(prev_pos_n, first_n, before_l_n); + } + + void priv_reverse(detail::bool_<false>) + { node_algorithms::reverse(this->get_root_node()); } + + void priv_reverse(detail::bool_<true>) + { + node_ptr new_first = node_algorithms::reverse + (node_traits::get_next(this->get_root_node())); + node_traits::set_next(this->get_root_node(), new_first); + } + + void priv_shift_backwards(size_type n, detail::bool_<false>) + { + node_ptr l = node_algorithms::move_forward(this->get_root_node(), (std::size_t)n); + if(cache_last && l){ + this->set_last_node(l); + } + } + + void priv_shift_backwards(size_type n, detail::bool_<true>) + { + std::pair<node_ptr, node_ptr> ret( + node_algorithms::move_first_n_forward + (node_traits::get_next(this->get_root_node()), (std::size_t)n)); + if(ret.first){ + node_traits::set_next(this->get_root_node(), ret.first); + if(cache_last){ + this->set_last_node(ret.second); + } + } + } + + void priv_shift_forward(size_type n, detail::bool_<false>) + { + node_ptr l = node_algorithms::move_backwards(this->get_root_node(), (std::size_t)n); + if(cache_last && l){ + this->set_last_node(l); + } + } + + void priv_shift_forward(size_type n, detail::bool_<true>) + { + std::pair<node_ptr, node_ptr> ret( + node_algorithms::move_first_n_backwards + (node_traits::get_next(this->get_root_node()), (std::size_t)n)); + if(ret.first){ + node_traits::set_next(this->get_root_node(), ret.first); + if(cache_last){ + this->set_last_node(ret.second); + } + } + } + + static void priv_swap_cache_last(slist_impl *this_impl, slist_impl *other_impl) + { + bool other_was_empty = false; + if(this_impl->empty()){ + //Check if both are empty or + if(other_impl->empty()) + return; + //If this is empty swap pointers + slist_impl *tmp = this_impl; + this_impl = other_impl; + other_impl = tmp; + other_was_empty = true; + } + else{ + other_was_empty = other_impl->empty(); + } + + //Precondition: this is not empty + node_ptr other_old_last(other_impl->get_last_node()); + node_ptr other_bfirst(other_impl->get_root_node()); + node_ptr this_bfirst(this_impl->get_root_node()); + node_ptr this_old_last(this_impl->get_last_node()); + + //Move all nodes from this to other's beginning + node_algorithms::transfer_after(other_bfirst, this_bfirst, this_old_last); + other_impl->set_last_node(this_old_last); + + if(other_was_empty){ + this_impl->set_last_node(this_bfirst); + } + else{ + //Move trailing nodes from other to this + node_algorithms::transfer_after(this_bfirst, this_old_last, other_old_last); + this_impl->set_last_node(other_old_last); + } + } + + //circular version + static void priv_swap_lists(const node_ptr & this_node, const node_ptr & other_node, detail::bool_<false>) + { node_algorithms::swap_nodes(this_node, other_node); } + + //linear version + static void priv_swap_lists(const node_ptr & this_node, const node_ptr & other_node, detail::bool_<true>) + { node_algorithms::swap_trailing_nodes(this_node, other_node); } + + static slist_impl &priv_container_from_end_iterator(const const_iterator &end_iterator) + { + //Obtaining the container from the end iterator is not possible with linear + //singly linked lists (because "end" is represented by the null pointer) + BOOST_STATIC_ASSERT(!linear); + BOOST_STATIC_ASSERT((has_container_from_iterator)); + node_ptr p = end_iterator.pointed_node(); + header_holder_type* h = header_holder_type::get_holder(p); + header_holder_plus_last_t* hpl = detail::parent_from_member< header_holder_plus_last_t, header_holder_type> + (h, &header_holder_plus_last_t::header_holder_); + root_plus_size* r = static_cast< root_plus_size* >(hpl); + data_t *d = detail::parent_from_member<data_t, root_plus_size> + ( r, &data_t::root_plus_size_); + slist_impl *s = detail::parent_from_member<slist_impl, data_t>(d, &slist_impl::data_); + return *s; + } +}; + +#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) +template<class T, class ...Options> +#else +template<class ValueTraits, class SizeType, std::size_t BoolFlags, typename HeaderHolder> +#endif +inline bool operator< +#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) +(const slist_impl<T, Options...> &x, const slist_impl<T, Options...> &y) +#else +( const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &x +, const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &y) +#endif +{ return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } + +#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) +template<class T, class ...Options> +#else +template<class ValueTraits, class SizeType, std::size_t BoolFlags, typename HeaderHolder> +#endif +bool operator== +#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) +(const slist_impl<T, Options...> &x, const slist_impl<T, Options...> &y) +#else +( const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &x +, const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &y) +#endif +{ + typedef slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> slist_type; + typedef typename slist_type::const_iterator const_iterator; + const bool C = slist_type::constant_time_size; + if(C && x.size() != y.size()){ + return false; + } + const_iterator end1 = x.end(); + + const_iterator i1 = x.begin(); + const_iterator i2 = y.begin(); + if(C){ + while (i1 != end1 && *i1 == *i2) { + ++i1; + ++i2; + } + return i1 == end1; + } + else{ + const_iterator end2 = y.end(); + while (i1 != end1 && i2 != end2 && *i1 == *i2) { + ++i1; + ++i2; + } + return i1 == end1 && i2 == end2; + } +} + +#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) +template<class T, class ...Options> +#else +template<class ValueTraits, class SizeType, std::size_t BoolFlags, typename HeaderHolder> +#endif +inline bool operator!= +#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) +(const slist_impl<T, Options...> &x, const slist_impl<T, Options...> &y) +#else +( const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &x +, const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &y) +#endif +{ return !(x == y); } + +#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) +template<class T, class ...Options> +#else +template<class ValueTraits, class SizeType, std::size_t BoolFlags, typename HeaderHolder> +#endif +inline bool operator> +#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) +(const slist_impl<T, Options...> &x, const slist_impl<T, Options...> &y) +#else +( const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &x +, const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &y) +#endif +{ return y < x; } + +#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) +template<class T, class ...Options> +#else +template<class ValueTraits, class SizeType, std::size_t BoolFlags, typename HeaderHolder> +#endif +inline bool operator<= +#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) +(const slist_impl<T, Options...> &x, const slist_impl<T, Options...> &y) +#else +( const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &x +, const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &y) +#endif +{ return !(y < x); } + +#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) +template<class T, class ...Options> +#else +template<class ValueTraits, class SizeType, std::size_t BoolFlags, typename HeaderHolder> +#endif +inline bool operator>= +#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) +(const slist_impl<T, Options...> &x, const slist_impl<T, Options...> &y) +#else +( const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &x +, const slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &y) +#endif +{ return !(x < y); } + +#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) +template<class T, class ...Options> +#else +template<class ValueTraits, class SizeType, std::size_t BoolFlags, typename HeaderHolder> +#endif +inline void swap +#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) +(slist_impl<T, Options...> &x, slist_impl<T, Options...> &y) +#else +( slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &x +, slist_impl<ValueTraits, SizeType, BoolFlags, HeaderHolder> &y) +#endif +{ x.swap(y); } + +//! Helper metafunction to define a \c slist that yields to the same type when the +//! same options (either explicitly or implicitly) are used. +#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template<class T, class ...Options> +#else +template<class T, class O1 = void, class O2 = void, class O3 = void, class O4 = void, class O5 = void, class O6 = void> +#endif +struct make_slist +{ + /// @cond + typedef typename pack_options + < slist_defaults, + #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) + O1, O2, O3, O4, O5, O6 + #else + Options... + #endif + >::type packed_options; + typedef typename detail::get_value_traits + <T, typename packed_options::proto_value_traits>::type value_traits; + typedef typename detail::get_header_holder_type + < value_traits, typename packed_options::header_holder_type >::type header_holder_type; + typedef slist_impl + < value_traits + , typename packed_options::size_type + , (std::size_t(packed_options::linear)*slist_bool_flags::linear_pos) + |(std::size_t(packed_options::constant_time_size)*slist_bool_flags::constant_time_size_pos) + |(std::size_t(packed_options::cache_last)*slist_bool_flags::cache_last_pos) + , header_holder_type + > implementation_defined; + /// @endcond + typedef implementation_defined type; +}; + + +#ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED + +#if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template<class T, class O1, class O2, class O3, class O4, class O5, class O6> +#else +template<class T, class ...Options> +#endif +class slist + : public make_slist<T, + #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) + O1, O2, O3, O4, O5, O6 + #else + Options... + #endif + >::type +{ + typedef typename make_slist + <T, + #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) + O1, O2, O3, O4, O5, O6 + #else + Options... + #endif + >::type Base; + //Assert if passed value traits are compatible with the type + BOOST_STATIC_ASSERT((detail::is_same<typename Base::value_traits::value_type, T>::value)); + BOOST_MOVABLE_BUT_NOT_COPYABLE(slist) + + public: + typedef typename Base::value_traits value_traits; + typedef typename Base::iterator iterator; + typedef typename Base::const_iterator const_iterator; + typedef typename Base::size_type size_type; + typedef typename Base::node_ptr node_ptr; + + explicit slist(const value_traits &v_traits = value_traits()) + : Base(v_traits) + {} + + struct incorporate_t{}; + + slist( const node_ptr & f, const node_ptr & before_l + , size_type n, const value_traits &v_traits = value_traits()) + : Base(f, before_l, n, v_traits) + {} + + template<class Iterator> + slist(Iterator b, Iterator e, const value_traits &v_traits = value_traits()) + : Base(b, e, v_traits) + {} + + slist(BOOST_RV_REF(slist) x) + : Base(::boost::move(static_cast<Base&>(x))) + {} + + slist& operator=(BOOST_RV_REF(slist) x) + { return static_cast<slist &>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); } + + static slist &container_from_end_iterator(iterator end_iterator) + { return static_cast<slist &>(Base::container_from_end_iterator(end_iterator)); } + + static const slist &container_from_end_iterator(const_iterator end_iterator) + { return static_cast<const slist &>(Base::container_from_end_iterator(end_iterator)); } +}; + +#endif + +} //namespace intrusive +} //namespace boost + +#include <boost/intrusive/detail/config_end.hpp> + +#endif //BOOST_INTRUSIVE_SLIST_HPP diff --git a/3rdParty/Boost/src/boost/intrusive/slist_hook.hpp b/3rdParty/Boost/src/boost/intrusive/slist_hook.hpp new file mode 100644 index 0000000..a9d5be6 --- /dev/null +++ b/3rdParty/Boost/src/boost/intrusive/slist_hook.hpp @@ -0,0 +1,294 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Olaf Krzikalla 2004-2006. +// (C) Copyright Ion Gaztanaga 2006-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_SLIST_HOOK_HPP +#define BOOST_INTRUSIVE_SLIST_HOOK_HPP + +#include <boost/intrusive/detail/config_begin.hpp> +#include <boost/intrusive/intrusive_fwd.hpp> +#include <boost/intrusive/detail/utilities.hpp> +#include <boost/intrusive/detail/slist_node.hpp> +#include <boost/intrusive/circular_slist_algorithms.hpp> +#include <boost/intrusive/link_mode.hpp> +#include <boost/intrusive/options.hpp> +#include <boost/intrusive/detail/generic_hook.hpp> + +namespace boost { +namespace intrusive { + +/// @cond +template<class VoidPointer> +struct get_slist_node_algo +{ + typedef circular_slist_algorithms<slist_node_traits<VoidPointer> > type; +}; + +/// @endcond + +//! Helper metafunction to define a \c slist_base_hook that yields to the same +//! type when the same options (either explicitly or implicitly) are used. +#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template<class ...Options> +#else +template<class O1 = void, class O2 = void, class O3 = void> +#endif +struct make_slist_base_hook +{ + /// @cond + typedef typename pack_options + < hook_defaults, + #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) + O1, O2, O3 + #else + Options... + #endif + >::type packed_options; + + typedef generic_hook + < get_slist_node_algo<typename packed_options::void_pointer> + , typename packed_options::tag + , packed_options::link_mode + , SlistBaseHookId + > implementation_defined; + /// @endcond + typedef implementation_defined type; +}; + +//! Derive a class from slist_base_hook in order to store objects in +//! in an list. slist_base_hook holds the data necessary to maintain the +//! list and provides an appropriate value_traits class for list. +//! +//! The hook admits the following options: \c tag<>, \c void_pointer<> and +//! \c link_mode<>. +//! +//! \c tag<> 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 \c list_base_hook, then each \c list_base_hook needs its +//! unique tag. +//! +//! \c link_mode<> will specify the linking mode of the hook (\c normal_link, +//! \c auto_unlink or \c safe_link). +//! +//! \c void_pointer<> is the pointer type that will be used internally in the hook +//! and the container configured to use this hook. +#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template<class ...Options> +#else +template<class O1, class O2, class O3> +#endif +class slist_base_hook + : public make_slist_base_hook< + #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) + O1, O2, O3 + #else + Options... + #endif + >::type +{ + #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) + public: + //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link + //! initializes the node to an unlinked state. + //! + //! <b>Throws</b>: Nothing. + slist_base_hook(); + + //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link + //! initializes the node to an unlinked state. The argument is ignored. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Rationale</b>: Providing a copy-constructor + //! makes classes using the hook STL-compliant without forcing the + //! user to do some additional work. \c swap can be used to emulate + //! move-semantics. + slist_base_hook(const slist_base_hook& ); + + //! <b>Effects</b>: Empty function. The argument is ignored. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Rationale</b>: Providing an assignment operator + //! makes classes using the hook STL-compliant without forcing the + //! user to do some additional work. \c swap can be used to emulate + //! move-semantics. + slist_base_hook& operator=(const slist_base_hook& ); + + //! <b>Effects</b>: If link_mode is \c normal_link, the destructor does + //! nothing (ie. no code is generated). If link_mode is \c safe_link and the + //! object is stored in an slist an assertion is raised. If link_mode is + //! \c auto_unlink and \c is_linked() is true, the node is unlinked. + //! + //! <b>Throws</b>: Nothing. + ~slist_base_hook(); + + //! <b>Effects</b>: 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. + //! + //! <b>Complexity</b>: Constant + //! + //! <b>Throws</b>: Nothing. + void swap_nodes(slist_base_hook &other); + + //! <b>Precondition</b>: link_mode must be \c safe_link or \c auto_unlink. + //! + //! <b>Returns</b>: true, if the node belongs to a container, false + //! otherwise. This function can be used to test whether \c slist::iterator_to + //! will return a valid iterator. + //! + //! <b>Complexity</b>: Constant + bool is_linked() const; + + //! <b>Effects</b>: Removes the node if it's inserted in a container. + //! This function is only allowed if link_mode is \c auto_unlink. + //! + //! <b>Throws</b>: Nothing. + void unlink(); + #endif +}; + +//! Helper metafunction to define a \c slist_member_hook that yields to the same +//! type when the same options (either explicitly or implicitly) are used. +#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template<class ...Options> +#else +template<class O1 = void, class O2 = void, class O3 = void> +#endif +struct make_slist_member_hook +{ + /// @cond + typedef typename pack_options + < hook_defaults, + #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) + O1, O2, O3 + #else + Options... + #endif + >::type packed_options; + + typedef generic_hook + < get_slist_node_algo<typename packed_options::void_pointer> + , member_tag + , packed_options::link_mode + , NoBaseHookId + > implementation_defined; + /// @endcond + typedef implementation_defined type; +}; + +//! Put a public data member slist_member_hook in order to store objects of this class in +//! an list. slist_member_hook holds the data necessary for maintaining the list and +//! provides an appropriate value_traits class for list. +//! +//! The hook admits the following options: \c void_pointer<> and +//! \c link_mode<>. +//! +//! \c link_mode<> will specify the linking mode of the hook (\c normal_link, +//! \c auto_unlink or \c safe_link). +//! +//! \c void_pointer<> is the pointer type that will be used internally in the hook +//! and the container configured to use this hook. +#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) +template<class ...Options> +#else +template<class O1, class O2, class O3> +#endif +class slist_member_hook + : public make_slist_member_hook< + #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) + O1, O2, O3 + #else + Options... + #endif + >::type +{ + #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) + public: + //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link + //! initializes the node to an unlinked state. + //! + //! <b>Throws</b>: Nothing. + slist_member_hook(); + + //! <b>Effects</b>: If link_mode is \c auto_unlink or \c safe_link + //! initializes the node to an unlinked state. The argument is ignored. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Rationale</b>: Providing a copy-constructor + //! makes classes using the hook STL-compliant without forcing the + //! user to do some additional work. \c swap can be used to emulate + //! move-semantics. + slist_member_hook(const slist_member_hook& ); + + //! <b>Effects</b>: Empty function. The argument is ignored. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Rationale</b>: Providing an assignment operator + //! makes classes using the hook STL-compliant without forcing the + //! user to do some additional work. \c swap can be used to emulate + //! move-semantics. + slist_member_hook& operator=(const slist_member_hook& ); + + //! <b>Effects</b>: If link_mode is \c normal_link, the destructor does + //! nothing (ie. no code is generated). If link_mode is \c safe_link and the + //! object is stored in an slist an assertion is raised. If link_mode is + //! \c auto_unlink and \c is_linked() is true, the node is unlinked. + //! + //! <b>Throws</b>: Nothing. + ~slist_member_hook(); + + //! <b>Effects</b>: 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. + //! + //! <b>Complexity</b>: Constant + //! + //! <b>Throws</b>: Nothing. + void swap_nodes(slist_member_hook &other); + + //! <b>Precondition</b>: link_mode must be \c safe_link or \c auto_unlink. + //! + //! <b>Returns</b>: true, if the node belongs to a container, false + //! otherwise. This function can be used to test whether \c slist::iterator_to + //! will return a valid iterator. + //! + //! <b>Complexity</b>: Constant + bool is_linked() const; + + //! <b>Effects</b>: Removes the node if it's inserted in a container. + //! This function is only allowed if link_mode is \c auto_unlink. + //! + //! <b>Throws</b>: Nothing. + void unlink(); + #endif +}; + +} //namespace intrusive +} //namespace boost + +#include <boost/intrusive/detail/config_end.hpp> + +#endif //BOOST_INTRUSIVE_SLIST_HOOK_HPP |