diff options
Diffstat (limited to 'src/third_party/boost-1.69.0/boost/container/detail/node_alloc_holder.hpp')
| -rw-r--r-- | src/third_party/boost-1.69.0/boost/container/detail/node_alloc_holder.hpp | 471 |
1 files changed, 471 insertions, 0 deletions
diff --git a/src/third_party/boost-1.69.0/boost/container/detail/node_alloc_holder.hpp b/src/third_party/boost-1.69.0/boost/container/detail/node_alloc_holder.hpp new file mode 100644 index 00000000000..a103e63c9a6 --- /dev/null +++ b/src/third_party/boost-1.69.0/boost/container/detail/node_alloc_holder.hpp @@ -0,0 +1,471 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (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) +// +// See http://www.boost.org/libs/container for documentation. +// +////////////////////////////////////////////////////////////////////////////// + +#ifndef BOOST_CONTAINER_DETAIL_NODE_ALLOC_HPP_ +#define BOOST_CONTAINER_DETAIL_NODE_ALLOC_HPP_ + +#ifndef BOOST_CONFIG_HPP +# include <boost/config.hpp> +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + +#include <boost/container/detail/config_begin.hpp> +#include <boost/container/detail/workaround.hpp> + +// container +#include <boost/container/allocator_traits.hpp> +// container/detail +#include <boost/container/detail/addressof.hpp> +#include <boost/container/detail/alloc_helpers.hpp> +#include <boost/container/detail/allocator_version_traits.hpp> +#include <boost/container/detail/construct_in_place.hpp> +#include <boost/container/detail/destroyers.hpp> +#include <boost/move/detail/iterator_to_raw_pointer.hpp> +#include <boost/container/detail/mpl.hpp> +#include <boost/container/detail/placement_new.hpp> +#include <boost/move/detail/to_raw_pointer.hpp> +#include <boost/container/detail/type_traits.hpp> +#include <boost/container/detail/version_type.hpp> +// intrusive +#include <boost/intrusive/detail/mpl.hpp> +#include <boost/intrusive/options.hpp> +// move +#include <boost/move/utility_core.hpp> +#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) +#include <boost/move/detail/fwd_macros.hpp> +#endif +// other +#include <boost/core/no_exceptions_support.hpp> + + +namespace boost { +namespace container { +namespace dtl { + +BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(key_compare) +BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(key_equal) +BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(hasher) +BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(predicate_type) + +template<class Allocator, class ICont> +struct node_alloc_holder + : public allocator_traits<Allocator>::template + portable_rebind_alloc<typename ICont::value_type>::type //NodeAlloc +{ + //If the intrusive container is an associative container, obtain the predicate, which will + //be of type node_compare<>. If not an associative container val_compare will be a "nat" type. + typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT + ( boost::container::dtl:: + , ICont, key_compare, dtl::nat) intrusive_val_compare; + //In that case obtain the value predicate from the node predicate via predicate_type + //if intrusive_val_compare is node_compare<>, nat otherwise + typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT + ( boost::container::dtl:: + , intrusive_val_compare + , predicate_type, dtl::nat) val_compare; + + //If the intrusive container is a hash container, obtain the predicate, which will + //be of type node_compare<>. If not an associative container val_equal will be a "nat" type. + typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT + (boost::container::dtl:: + , ICont, key_equal, dtl::nat2) intrusive_val_equal; + typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT + (boost::container::dtl:: + , ICont, hasher, dtl::nat3) intrusive_val_hasher; + //In that case obtain the value predicate from the node predicate via predicate_type + //if intrusive_val_compare is node_compare<>, nat otherwise + typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT + (boost::container::dtl:: + , intrusive_val_equal + , predicate_type, dtl::nat2) val_equal; + typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT + (boost::container::dtl:: + , intrusive_val_hasher + , predicate_type, dtl::nat3) val_hasher; + + typedef allocator_traits<Allocator> allocator_traits_type; + typedef typename allocator_traits_type::value_type val_type; + typedef ICont intrusive_container; + typedef typename ICont::value_type Node; + typedef typename allocator_traits_type::template + portable_rebind_alloc<Node>::type NodeAlloc; + typedef allocator_traits<NodeAlloc> node_allocator_traits_type; + typedef dtl::allocator_version_traits<NodeAlloc> node_allocator_version_traits_type; + typedef Allocator ValAlloc; + typedef typename node_allocator_traits_type::pointer NodePtr; + typedef dtl::scoped_deallocator<NodeAlloc> Deallocator; + typedef typename node_allocator_traits_type::size_type size_type; + typedef typename node_allocator_traits_type::difference_type difference_type; + typedef dtl::integral_constant<unsigned, + boost::container::dtl:: + version<NodeAlloc>::value> alloc_version; + typedef typename ICont::iterator icont_iterator; + typedef typename ICont::const_iterator icont_citerator; + typedef allocator_destroyer<NodeAlloc> Destroyer; + typedef allocator_traits<NodeAlloc> NodeAllocTraits; + typedef allocator_version_traits<NodeAlloc> AllocVersionTraits; + + private: + BOOST_COPYABLE_AND_MOVABLE(node_alloc_holder) + + public: + + //Constructors for sequence containers + node_alloc_holder() + {} + + explicit node_alloc_holder(const ValAlloc &a) + : NodeAlloc(a) + {} + + //Constructors for associative containers + node_alloc_holder(const val_compare &c, const ValAlloc &a) + : NodeAlloc(a), m_icont(typename ICont::key_compare(c)) + {} + + node_alloc_holder(const val_hasher &hf, const val_equal &eql, const ValAlloc &a) + : NodeAlloc(a) + , m_icont(typename ICont::bucket_traits() + , typename ICont::hasher(hf) + , typename ICont::key_equal(eql)) + {} + + node_alloc_holder(const val_hasher &hf, const ValAlloc &a) + : NodeAlloc(a) + , m_icont(typename ICont::bucket_traits() + , typename ICont::hasher(hf) + , typename ICont::key_equal()) + {} + + node_alloc_holder(const val_hasher &hf) + : m_icont(typename ICont::bucket_traits() + , typename ICont::hasher(hf) + , typename ICont::key_equal()) + {} + + explicit node_alloc_holder(const node_alloc_holder &x) + : NodeAlloc(NodeAllocTraits::select_on_container_copy_construction(x.node_alloc())) + {} + + node_alloc_holder(const node_alloc_holder &x, const val_compare &c) + : NodeAlloc(NodeAllocTraits::select_on_container_copy_construction(x.node_alloc())) + , m_icont(typename ICont::key_compare(c)) + {} + + node_alloc_holder(const node_alloc_holder &x, const val_hasher &hf, const val_equal &eql) + : NodeAlloc(NodeAllocTraits::select_on_container_copy_construction(x.node_alloc())) + , m_icont( typename ICont::bucket_traits() + , typename ICont::hasher(hf) + , typename ICont::key_equal(eql)) + {} + + node_alloc_holder(const val_hasher &hf, const val_equal &eql) + : m_icont(typename ICont::bucket_traits() + , typename ICont::hasher(hf) + , typename ICont::key_equal(eql)) + {} + + explicit node_alloc_holder(BOOST_RV_REF(node_alloc_holder) x) + : NodeAlloc(boost::move(x.node_alloc())) + { this->icont().swap(x.icont()); } + + explicit node_alloc_holder(const val_compare &c) + : m_icont(typename ICont::key_compare(c)) + {} + + //helpers for move assignments + explicit node_alloc_holder(BOOST_RV_REF(node_alloc_holder) x, const val_compare &c) + : NodeAlloc(boost::move(x.node_alloc())), m_icont(typename ICont::key_compare(c)) + { this->icont().swap(x.icont()); } + + explicit node_alloc_holder(BOOST_RV_REF(node_alloc_holder) x, const val_hasher &hf, const val_equal &eql) + : NodeAlloc(boost::move(x.node_alloc())) + , m_icont( typename ICont::bucket_traits() + , typename ICont::hasher(hf) + , typename ICont::key_equal(eql)) + { this->icont().swap(x.icont()); } + + void copy_assign_alloc(const node_alloc_holder &x) + { + dtl::bool_<allocator_traits_type::propagate_on_container_copy_assignment::value> flag; + dtl::assign_alloc( static_cast<NodeAlloc &>(*this) + , static_cast<const NodeAlloc &>(x), flag); + } + + void move_assign_alloc( node_alloc_holder &x) + { + dtl::bool_<allocator_traits_type::propagate_on_container_move_assignment::value> flag; + dtl::move_alloc( static_cast<NodeAlloc &>(*this) + , static_cast<NodeAlloc &>(x), flag); + } + + ~node_alloc_holder() + { this->clear(alloc_version()); } + + size_type max_size() const + { return allocator_traits_type::max_size(this->node_alloc()); } + + NodePtr allocate_one() + { return AllocVersionTraits::allocate_one(this->node_alloc()); } + + void deallocate_one(const NodePtr &p) + { AllocVersionTraits::deallocate_one(this->node_alloc(), p); } + + #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + + template<class ...Args> + NodePtr create_node(Args &&...args) + { + NodePtr p = this->allocate_one(); + BOOST_TRY{ + ::new(boost::movelib::iterator_to_raw_pointer(p), boost_container_new_t()) Node; + allocator_traits<NodeAlloc>::construct + (this->node_alloc() + , p->get_real_data_ptr(), boost::forward<Args>(args)...); + } + BOOST_CATCH(...) { + p->destroy_header(); + this->node_alloc().deallocate(p, 1); + BOOST_RETHROW + } + BOOST_CATCH_END + return (p); + } + + #else //defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + + #define BOOST_CONTAINER_NODE_ALLOC_HOLDER_CONSTRUCT_IMPL(N) \ + BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ + NodePtr create_node(BOOST_MOVE_UREF##N)\ + {\ + NodePtr p = this->allocate_one();\ + BOOST_TRY{\ + ::new(boost::movelib::iterator_to_raw_pointer(p), boost_container_new_t()) Node;\ + allocator_traits<NodeAlloc>::construct\ + ( this->node_alloc()\ + , p->get_real_data_ptr()\ + BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ + }\ + BOOST_CATCH(...) {\ + p->destroy_header();\ + this->node_alloc().deallocate(p, 1);\ + BOOST_RETHROW\ + }\ + BOOST_CATCH_END\ + return (p);\ + }\ + // + BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_NODE_ALLOC_HOLDER_CONSTRUCT_IMPL) + #undef BOOST_CONTAINER_NODE_ALLOC_HOLDER_CONSTRUCT_IMPL + + #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + + template<class It> + NodePtr create_node_from_it(const It &it) + { + NodePtr p = this->allocate_one(); + BOOST_TRY{ + ::new(boost::movelib::iterator_to_raw_pointer(p), boost_container_new_t()) Node; + ::boost::container::construct_in_place(this->node_alloc(), p->get_real_data_ptr(), it); + } + BOOST_CATCH(...) { + p->destroy_header(); + this->node_alloc().deallocate(p, 1); + BOOST_RETHROW + } + BOOST_CATCH_END + return (p); + } + + template<class KeyConvertible> + NodePtr create_node_from_key(BOOST_FWD_REF(KeyConvertible) key) + { + NodePtr p = this->allocate_one(); + BOOST_TRY{ + ::new(boost::movelib::iterator_to_raw_pointer(p), boost_container_new_t()) Node; + NodeAlloc &na = this->node_alloc(); + node_allocator_traits_type::construct + (na, dtl::addressof(p->get_real_data().first), boost::forward<KeyConvertible>(key)); + BOOST_TRY{ + node_allocator_traits_type::construct(na, dtl::addressof(p->get_real_data().second)); + } + BOOST_CATCH(...){ + node_allocator_traits_type::destroy(na, dtl::addressof(p->get_real_data().first)); + BOOST_RETHROW; + } + BOOST_CATCH_END + } + BOOST_CATCH(...) { + p->destroy_header(); + this->node_alloc().deallocate(p, 1); + BOOST_RETHROW + } + BOOST_CATCH_END + return (p); + } + + void destroy_node(const NodePtr &nodep) + { + allocator_traits<NodeAlloc>::destroy(this->node_alloc(), boost::movelib::to_raw_pointer(nodep)); + this->deallocate_one(nodep); + } + + void swap(node_alloc_holder &x) + { + this->icont().swap(x.icont()); + dtl::bool_<allocator_traits_type::propagate_on_container_swap::value> flag; + dtl::swap_alloc(this->node_alloc(), x.node_alloc(), flag); + } + + template<class FwdIterator, class Inserter> + void allocate_many_and_construct + (FwdIterator beg, difference_type n, Inserter inserter) + { + if(n){ + typedef typename node_allocator_version_traits_type::multiallocation_chain multiallocation_chain_t; + + //Try to allocate memory in a single block + typedef typename multiallocation_chain_t::iterator multialloc_iterator_t; + multiallocation_chain_t chain; + NodeAlloc &nalloc = this->node_alloc(); + node_allocator_version_traits_type::allocate_individual(nalloc, n, chain); + multialloc_iterator_t itbeg = chain.begin(); + multialloc_iterator_t itlast = chain.last(); + chain.clear(); + + Node *p = 0; + BOOST_TRY{ + Deallocator node_deallocator(NodePtr(), nalloc); + dtl::scoped_destructor<NodeAlloc> sdestructor(nalloc, 0); + while(n){ + --n; + p = boost::movelib::iterator_to_raw_pointer(itbeg); + ++itbeg; //Increment iterator before overwriting pointed memory + //This does not throw + p = ::new(p, boost_container_new_t()) Node; + node_deallocator.set(p); + //This can throw + boost::container::construct_in_place(nalloc, p->get_real_data_ptr(), beg); + sdestructor.set(p); + ++beg; + //This can throw in some containers (predicate might throw). + //(sdestructor will destruct the node and node_deallocator will deallocate it in case of exception) + inserter(*p); + sdestructor.set(0); + } + sdestructor.release(); + node_deallocator.release(); + } + BOOST_CATCH(...){ + p->destroy_header(); + chain.incorporate_after(chain.last(), &*itbeg, &*itlast, n); + node_allocator_version_traits_type::deallocate_individual(this->node_alloc(), chain); + BOOST_RETHROW + } + BOOST_CATCH_END + } + } + + void clear(version_1) + { this->icont().clear_and_dispose(Destroyer(this->node_alloc())); } + + void clear(version_2) + { + typename NodeAlloc::multiallocation_chain chain; + allocator_destroyer_and_chain_builder<NodeAlloc> builder(this->node_alloc(), chain); + this->icont().clear_and_dispose(builder); + //BOOST_STATIC_ASSERT((::boost::has_move_emulation_enabled<typename NodeAlloc::multiallocation_chain>::value == true)); + if(!chain.empty()) + this->node_alloc().deallocate_individual(chain); + } + + icont_iterator erase_range(const icont_iterator &first, const icont_iterator &last, version_1) + { return this->icont().erase_and_dispose(first, last, Destroyer(this->node_alloc())); } + + icont_iterator erase_range(const icont_iterator &first, const icont_iterator &last, version_2) + { + typedef typename NodeAlloc::multiallocation_chain multiallocation_chain; + NodeAlloc & nalloc = this->node_alloc(); + multiallocation_chain chain; + allocator_destroyer_and_chain_builder<NodeAlloc> chain_builder(nalloc, chain); + icont_iterator ret_it = this->icont().erase_and_dispose(first, last, chain_builder); + nalloc.deallocate_individual(chain); + return ret_it; + } + + template<class Key, class Comparator> + size_type erase_key(const Key& k, const Comparator &comp, version_1) + { return this->icont().erase_and_dispose(k, comp, Destroyer(this->node_alloc())); } + + template<class Key, class Comparator> + size_type erase_key(const Key& k, const Comparator &comp, version_2) + { + allocator_multialloc_chain_node_deallocator<NodeAlloc> chain_holder(this->node_alloc()); + return this->icont().erase_and_dispose(k, comp, chain_holder.get_chain_builder()); + } + + protected: + struct cloner + { + explicit cloner(node_alloc_holder &holder) + : m_holder(holder) + {} + + NodePtr operator()(const Node &other) const + { return m_holder.create_node(other.get_real_data()); } + + node_alloc_holder &m_holder; + }; + + struct move_cloner + { + move_cloner(node_alloc_holder &holder) + : m_holder(holder) + {} + + NodePtr operator()(Node &other) + { //Use get_real_data() instead of get_real_data to allow moving const key in [multi]map + return m_holder.create_node(::boost::move(other.get_real_data())); + } + + node_alloc_holder &m_holder; + }; + + ICont &non_const_icont() const + { return const_cast<ICont&>(this->m_icont); } + + NodeAlloc &node_alloc() + { return static_cast<NodeAlloc &>(*this); } + + const NodeAlloc &node_alloc() const + { return static_cast<const NodeAlloc &>(*this); } + + public: + ICont &icont() + { return this->m_icont; } + + const ICont &icont() const + { return this->m_icont; } + + private: + //The intrusive container + ICont m_icont; +}; + +} //namespace dtl { +} //namespace container { +} //namespace boost { + +#include <boost/container/detail/config_end.hpp> + +#endif // BOOST_CONTAINER_DETAIL_NODE_ALLOC_HPP_ |