diff options
author | Anas Nashif <anas.nashif@intel.com> | 2012-10-30 12:57:26 -0700 |
---|---|---|
committer | Anas Nashif <anas.nashif@intel.com> | 2012-10-30 12:57:26 -0700 |
commit | 1a78a62555be32868418fe52f8e330c9d0f95d5a (patch) | |
tree | d3765a80e7d3b9640ec2e930743630cd6b9fce2b /boost/container/detail | |
download | boost-1a78a62555be32868418fe52f8e330c9d0f95d5a.tar.gz boost-1a78a62555be32868418fe52f8e330c9d0f95d5a.tar.bz2 boost-1a78a62555be32868418fe52f8e330c9d0f95d5a.zip |
Imported Upstream version 1.49.0upstream/1.49.0
Diffstat (limited to 'boost/container/detail')
27 files changed, 7025 insertions, 0 deletions
diff --git a/boost/container/detail/adaptive_node_pool_impl.hpp b/boost/container/detail/adaptive_node_pool_impl.hpp new file mode 100644 index 0000000000..36495795fb --- /dev/null +++ b/boost/container/detail/adaptive_node_pool_impl.hpp @@ -0,0 +1,648 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2005-2011. 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_ADAPTIVE_NODE_POOL_IMPL_HPP +#define BOOST_CONTAINER_DETAIL_ADAPTIVE_NODE_POOL_IMPL_HPP + +#if (defined _MSC_VER) && (_MSC_VER >= 1200) +# pragma once +#endif + +#include "config_begin.hpp" +#include <boost/container/container_fwd.hpp> +#include <boost/container/detail/workaround.hpp> +#include <boost/container/detail/utilities.hpp> +#include <boost/intrusive/pointer_traits.hpp> +#include <boost/intrusive/set.hpp> +#include <boost/intrusive/slist.hpp> +#include <boost/container/detail/type_traits.hpp> +#include <boost/container/detail/math_functions.hpp> +#include <boost/container/detail/mpl.hpp> +#include <boost/container/detail/pool_common.hpp> +#include <boost/assert.hpp> +#include <cstddef> + +namespace boost { +namespace container { +namespace container_detail { + +template<class size_type> +struct hdr_offset_holder_t +{ + hdr_offset_holder_t(size_type offset = 0) + : hdr_offset(offset) + {} + size_type hdr_offset; +}; + +template<class VoidPointer, class SizeType> +struct adaptive_pool_types +{ + typedef VoidPointer void_pointer; + typedef typename bi::make_set_base_hook + < bi::void_pointer<void_pointer> + , bi::optimize_size<true> + , bi::constant_time_size<false> + , bi::link_mode<bi::normal_link> >::type multiset_hook_t; + + typedef hdr_offset_holder_t<SizeType> hdr_offset_holder; + + struct block_info_t + : + public hdr_offset_holder, + public multiset_hook_t + { + typedef typename node_slist<void_pointer>::node_slist_t free_nodes_t; + //An intrusive list of free node from this block + free_nodes_t free_nodes; + friend bool operator <(const block_info_t &l, const block_info_t &r) + { +// { return l.free_nodes.size() < r.free_nodes.size(); } + //Let's order blocks first by free nodes and then by address + //so that highest address fully free blocks are deallocated. + //This improves returning memory to the OS (trimming). + const bool is_less = l.free_nodes.size() < r.free_nodes.size(); + const bool is_equal = l.free_nodes.size() == r.free_nodes.size(); + return is_less || (is_equal && (&l < &r)); + } + + friend bool operator ==(const block_info_t &l, const block_info_t &r) + { return &l == &r; } + }; + typedef typename bi::make_multiset + <block_info_t, bi::base_hook<multiset_hook_t> >::type block_multiset_t; +}; + +template<class size_type> +inline size_type calculate_alignment + ( size_type overhead_percent, size_type real_node_size + , size_type hdr_size, size_type hdr_offset_size, size_type payload_per_allocation) +{ + //to-do: handle real_node_size != node_size + const size_type divisor = overhead_percent*real_node_size; + const size_type dividend = hdr_offset_size*100; + size_type elements_per_subblock = (dividend - 1)/divisor + 1; + size_type candidate_power_of_2 = + upper_power_of_2(elements_per_subblock*real_node_size + hdr_offset_size); + bool overhead_satisfied = false; + //Now calculate the wors-case overhead for a subblock + const size_type max_subblock_overhead = hdr_size + payload_per_allocation; + while(!overhead_satisfied){ + elements_per_subblock = (candidate_power_of_2 - max_subblock_overhead)/real_node_size; + const size_type overhead_size = candidate_power_of_2 - elements_per_subblock*real_node_size; + if(overhead_size*100/candidate_power_of_2 < overhead_percent){ + overhead_satisfied = true; + } + else{ + candidate_power_of_2 <<= 1; + } + } + return candidate_power_of_2; +} + +template<class size_type> +inline void calculate_num_subblocks + (size_type alignment, size_type real_node_size, size_type elements_per_block + , size_type &num_subblocks, size_type &real_num_node, size_type overhead_percent + , size_type hdr_size, size_type hdr_offset_size, size_type payload_per_allocation) +{ + size_type elements_per_subblock = (alignment - hdr_offset_size)/real_node_size; + size_type possible_num_subblock = (elements_per_block - 1)/elements_per_subblock + 1; + size_type hdr_subblock_elements = (alignment - hdr_size - payload_per_allocation)/real_node_size; + while(((possible_num_subblock-1)*elements_per_subblock + hdr_subblock_elements) < elements_per_block){ + ++possible_num_subblock; + } + elements_per_subblock = (alignment - hdr_offset_size)/real_node_size; + bool overhead_satisfied = false; + while(!overhead_satisfied){ + const size_type total_data = (elements_per_subblock*(possible_num_subblock-1) + hdr_subblock_elements)*real_node_size; + const size_type total_size = alignment*possible_num_subblock; + if((total_size - total_data)*100/total_size < overhead_percent){ + overhead_satisfied = true; + } + else{ + ++possible_num_subblock; + } + } + num_subblocks = possible_num_subblock; + real_num_node = (possible_num_subblock-1)*elements_per_subblock + hdr_subblock_elements; +} + +template<class SegmentManagerBase, bool AlignOnly = false> +class private_adaptive_node_pool_impl +{ + //Non-copyable + private_adaptive_node_pool_impl(); + private_adaptive_node_pool_impl(const private_adaptive_node_pool_impl &); + private_adaptive_node_pool_impl &operator=(const private_adaptive_node_pool_impl &); + typedef private_adaptive_node_pool_impl this_type; + + typedef typename SegmentManagerBase::void_pointer void_pointer; + static const typename SegmentManagerBase:: + size_type PayloadPerAllocation = SegmentManagerBase::PayloadPerAllocation; + typedef bool_<AlignOnly> IsAlignOnly; + typedef true_ AlignOnlyTrue; + typedef false_ AlignOnlyFalse; + + public: + typedef typename node_slist<void_pointer>::node_t node_t; + typedef typename node_slist<void_pointer>::node_slist_t free_nodes_t; + typedef typename SegmentManagerBase::multiallocation_chain multiallocation_chain; + typedef typename SegmentManagerBase::size_type size_type; + + private: + typedef typename adaptive_pool_types<void_pointer, size_type>::block_info_t block_info_t; + typedef typename adaptive_pool_types<void_pointer, size_type>::block_multiset_t block_multiset_t; + typedef typename block_multiset_t::iterator block_iterator; + typedef typename adaptive_pool_types<void_pointer, size_type>::hdr_offset_holder hdr_offset_holder; + + static const size_type MaxAlign = alignment_of<node_t>::value; + static const size_type HdrSize = ((sizeof(block_info_t)-1)/MaxAlign+1)*MaxAlign; + static const size_type HdrOffsetSize = ((sizeof(hdr_offset_holder)-1)/MaxAlign+1)*MaxAlign; + + + public: + //!Segment manager typedef + typedef SegmentManagerBase segment_manager_base_type; + + //!Constructor from a segment manager. Never throws + private_adaptive_node_pool_impl + ( segment_manager_base_type *segment_mngr_base + , size_type node_size + , size_type nodes_per_block + , size_type max_free_blocks + , unsigned char overhead_percent + ) + : m_max_free_blocks(max_free_blocks) + , m_real_node_size(lcm(node_size, size_type(alignment_of<node_t>::value))) + //Round the size to a power of two value. + //This is the total memory size (including payload) that we want to + //allocate from the general-purpose allocator + , m_real_block_alignment + (AlignOnly ? + upper_power_of_2(HdrSize + m_real_node_size*nodes_per_block) : + calculate_alignment( (size_type)overhead_percent, m_real_node_size + , HdrSize, HdrOffsetSize, PayloadPerAllocation)) + //This is the real number of nodes per block + , m_num_subblocks(0) + , m_real_num_node(AlignOnly ? (m_real_block_alignment - PayloadPerAllocation - HdrSize)/m_real_node_size : 0) + //General purpose allocator + , mp_segment_mngr_base(segment_mngr_base) + , m_block_multiset() + , m_totally_free_blocks(0) + { + if(!AlignOnly){ + calculate_num_subblocks + ( m_real_block_alignment + , m_real_node_size + , nodes_per_block + , m_num_subblocks + , m_real_num_node + , (size_type)overhead_percent + , HdrSize + , HdrOffsetSize + , PayloadPerAllocation); + } + } + + //!Destructor. Deallocates all allocated blocks. Never throws + ~private_adaptive_node_pool_impl() + { priv_clear(); } + + size_type get_real_num_node() const + { return m_real_num_node; } + + //!Returns the segment manager. Never throws + segment_manager_base_type* get_segment_manager_base()const + { return container_detail::to_raw_pointer(mp_segment_mngr_base); } + + //!Allocates array of count elements. Can throw + void *allocate_node() + { + priv_invariants(); + //If there are no free nodes we allocate a new block + if (m_block_multiset.empty()){ + priv_alloc_block(1); + } + //We take the first free node the multiset can't be empty + return priv_take_first_node(); + } + + //!Deallocates an array pointed by ptr. Never throws + void deallocate_node(void *pElem) + { + multiallocation_chain chain; + chain.push_front(void_pointer(pElem)); + this->priv_reinsert_nodes_in_block(chain, 1); + //Update free block count< + if(m_totally_free_blocks > m_max_free_blocks){ + this->priv_deallocate_free_blocks(m_max_free_blocks); + } + priv_invariants(); + } + + //!Allocates n nodes. + //!Can throw + multiallocation_chain allocate_nodes(const size_type n) + { + multiallocation_chain chain; + size_type i = 0; + try{ + priv_invariants(); + while(i != n){ + //If there are no free nodes we allocate all needed blocks + if (m_block_multiset.empty()){ + priv_alloc_block(((n - i) - 1)/m_real_num_node + 1); + } + free_nodes_t &free_nodes = m_block_multiset.begin()->free_nodes; + const size_type free_nodes_count_before = free_nodes.size(); + if(free_nodes_count_before == m_real_num_node){ + --m_totally_free_blocks; + } + const size_type num_elems = ((n-i) < free_nodes_count_before) ? (n-i) : free_nodes_count_before; + for(size_type j = 0; j != num_elems; ++j){ + void *new_node = &free_nodes.front(); + free_nodes.pop_front(); + chain.push_back(new_node); + } + + if(free_nodes.empty()){ + m_block_multiset.erase(m_block_multiset.begin()); + } + i += num_elems; + } + } + catch(...){ + this->deallocate_nodes(boost::move(chain)); + throw; + } + priv_invariants(); + return boost::move(chain); + } + + //!Deallocates a linked list of nodes. Never throws + void deallocate_nodes(multiallocation_chain nodes) + { + this->priv_reinsert_nodes_in_block(nodes, nodes.size()); + if(m_totally_free_blocks > m_max_free_blocks){ + this->priv_deallocate_free_blocks(m_max_free_blocks); + } + } + + void deallocate_free_blocks() + { this->priv_deallocate_free_blocks(0); } + + size_type num_free_nodes() + { + typedef typename block_multiset_t::const_iterator citerator; + size_type count = 0; + citerator it (m_block_multiset.begin()), itend(m_block_multiset.end()); + for(; it != itend; ++it){ + count += it->free_nodes.size(); + } + return count; + } + + void swap(private_adaptive_node_pool_impl &other) + { + BOOST_ASSERT(m_max_free_blocks == other.m_max_free_blocks); + BOOST_ASSERT(m_real_node_size == other.m_real_node_size); + BOOST_ASSERT(m_real_block_alignment == other.m_real_block_alignment); + BOOST_ASSERT(m_real_num_node == other.m_real_num_node); + std::swap(mp_segment_mngr_base, other.mp_segment_mngr_base); + std::swap(m_totally_free_blocks, other.m_totally_free_blocks); + m_block_multiset.swap(other.m_block_multiset); + } + + //Deprecated, use deallocate_free_blocks + void deallocate_free_chunks() + { this->priv_deallocate_free_blocks(0); } + + private: + void priv_deallocate_free_blocks(size_type max_free_blocks) + { + priv_invariants(); + //Now check if we've reached the free nodes limit + //and check if we have free blocks. If so, deallocate as much + //as we can to stay below the limit + for( block_iterator itend = m_block_multiset.end() + ; m_totally_free_blocks > max_free_blocks + ; --m_totally_free_blocks + ){ + BOOST_ASSERT(!m_block_multiset.empty()); + block_iterator it = itend; + --it; + BOOST_ASSERT(it->free_nodes.size() == m_real_num_node); + m_block_multiset.erase_and_dispose(it, block_destroyer(this)); + } + } + + void priv_reinsert_nodes_in_block(multiallocation_chain &chain, size_type n) + { + block_iterator block_it(m_block_multiset.end()); + while(n--){ + void *pElem = container_detail::to_raw_pointer(chain.front()); + chain.pop_front(); + priv_invariants(); + block_info_t *block_info = this->priv_block_from_node(pElem); + BOOST_ASSERT(block_info->free_nodes.size() < m_real_num_node); + //We put the node at the beginning of the free node list + node_t * to_deallocate = static_cast<node_t*>(pElem); + block_info->free_nodes.push_front(*to_deallocate); + + block_iterator this_block(block_multiset_t::s_iterator_to(*block_info)); + block_iterator next_block(this_block); + ++next_block; + + //Cache the free nodes from the block + size_type this_block_free_nodes = this_block->free_nodes.size(); + + if(this_block_free_nodes == 1){ + m_block_multiset.insert(m_block_multiset.begin(), *block_info); + } + else{ + block_iterator next_block(this_block); + ++next_block; + if(next_block != block_it){ + size_type next_free_nodes = next_block->free_nodes.size(); + if(this_block_free_nodes > next_free_nodes){ + //Now move the block to the new position + m_block_multiset.erase(this_block); + m_block_multiset.insert(*block_info); + } + } + } + //Update free block count + if(this_block_free_nodes == m_real_num_node){ + ++m_totally_free_blocks; + } + priv_invariants(); + } + } + + node_t *priv_take_first_node() + { + BOOST_ASSERT(m_block_multiset.begin() != m_block_multiset.end()); + //We take the first free node the multiset can't be empty + free_nodes_t &free_nodes = m_block_multiset.begin()->free_nodes; + node_t *first_node = &free_nodes.front(); + const size_type free_nodes_count = free_nodes.size(); + BOOST_ASSERT(0 != free_nodes_count); + free_nodes.pop_front(); + if(free_nodes_count == 1){ + m_block_multiset.erase(m_block_multiset.begin()); + } + else if(free_nodes_count == m_real_num_node){ + --m_totally_free_blocks; + } + priv_invariants(); + return first_node; + } + + class block_destroyer; + friend class block_destroyer; + + class block_destroyer + { + public: + block_destroyer(const this_type *impl) + : mp_impl(impl) + {} + + void operator()(typename block_multiset_t::pointer to_deallocate) + { return this->do_destroy(to_deallocate, IsAlignOnly()); } + + private: + void do_destroy(typename block_multiset_t::pointer to_deallocate, AlignOnlyTrue) + { + size_type free_nodes = to_deallocate->free_nodes.size(); + (void)free_nodes; + BOOST_ASSERT(free_nodes == mp_impl->m_real_num_node); + mp_impl->mp_segment_mngr_base->deallocate(to_deallocate); + } + + void do_destroy(typename block_multiset_t::pointer to_deallocate, AlignOnlyFalse) + { + size_type free_nodes = to_deallocate->free_nodes.size(); + (void)free_nodes; + BOOST_ASSERT(free_nodes == mp_impl->m_real_num_node); + BOOST_ASSERT(0 == to_deallocate->hdr_offset); + hdr_offset_holder *hdr_off_holder = mp_impl->priv_first_subblock_from_block(container_detail::to_raw_pointer(to_deallocate)); + mp_impl->mp_segment_mngr_base->deallocate(hdr_off_holder); + } + + const this_type *mp_impl; + }; + + //This macro will activate invariant checking. Slow, but helpful for debugging the code. + //#define BOOST_CONTAINER_ADAPTIVE_NODE_POOL_CHECK_INVARIANTS + void priv_invariants() + #ifdef BOOST_CONTAINER_ADAPTIVE_NODE_POOL_CHECK_INVARIANTS + #undef BOOST_CONTAINER_ADAPTIVE_NODE_POOL_CHECK_INVARIANTS + { + //We iterate through the block tree to free the memory + block_iterator it(m_block_multiset.begin()), + itend(m_block_multiset.end()), to_deallocate; + if(it != itend){ + for(++it; it != itend; ++it){ + block_iterator prev(it); + --prev; + size_type sp = prev->free_nodes.size(), + si = it->free_nodes.size(); + BOOST_ASSERT(sp <= si); + (void)sp; (void)si; + } + } + //Check that the total free nodes are correct + it = m_block_multiset.begin(); + itend = m_block_multiset.end(); + size_type total_free_nodes = 0; + for(; it != itend; ++it){ + total_free_nodes += it->free_nodes.size(); + } + BOOST_ASSERT(total_free_nodes >= m_totally_free_blocks*m_real_num_node); + + //Check that the total totally free blocks are correct + it = m_block_multiset.begin(); + itend = m_block_multiset.end(); + total_free = 0; + for(; it != itend; ++it){ + total_free += it->free_nodes.size() == m_real_num_node; + } + BOOST_ASSERT(total_free >= m_totally_free_blocks); + + if(!AlignOnly){ + //Check that header offsets are correct + it = m_block_multiset.begin(); + for(; it != itend; ++it){ + hdr_offset_holder *hdr_off_holder = priv_first_subblock_from_block(&*it); + for(size_type i = 0, max = m_num_subblocks; i < max; ++i){ + BOOST_ASSERT(hdr_off_holder->hdr_offset == size_type(reinterpret_cast<char*>(&*it)- reinterpret_cast<char*>(hdr_off_holder))); + BOOST_ASSERT(0 == ((size_type)hdr_off_holder & (m_real_block_alignment - 1))); + BOOST_ASSERT(0 == (hdr_off_holder->hdr_offset & (m_real_block_alignment - 1))); + hdr_off_holder = reinterpret_cast<hdr_offset_holder *>(reinterpret_cast<char*>(hdr_off_holder) + m_real_block_alignment); + } + } + } + } + #else + {} //empty + #endif + + //!Deallocates all used memory. Never throws + void priv_clear() + { + #ifndef NDEBUG + block_iterator it = m_block_multiset.begin(); + block_iterator itend = m_block_multiset.end(); + size_type num_free_nodes = 0; + for(; it != itend; ++it){ + //Check for memory leak + BOOST_ASSERT(it->free_nodes.size() == m_real_num_node); + ++num_free_nodes; + } + BOOST_ASSERT(num_free_nodes == m_totally_free_blocks); + #endif + //Check for memory leaks + priv_invariants(); + m_block_multiset.clear_and_dispose(block_destroyer(this)); + m_totally_free_blocks = 0; + } + + block_info_t *priv_block_from_node(void *node, AlignOnlyFalse) const + { + hdr_offset_holder *hdr_off_holder = + reinterpret_cast<hdr_offset_holder*>((std::size_t)node & size_type(~(m_real_block_alignment - 1))); + BOOST_ASSERT(0 == ((std::size_t)hdr_off_holder & (m_real_block_alignment - 1))); + BOOST_ASSERT(0 == (hdr_off_holder->hdr_offset & (m_real_block_alignment - 1))); + block_info_t *block = reinterpret_cast<block_info_t *> + (reinterpret_cast<char*>(hdr_off_holder) + hdr_off_holder->hdr_offset); + BOOST_ASSERT(block->hdr_offset == 0); + return block; + } + + block_info_t *priv_block_from_node(void *node, AlignOnlyTrue) const + { + return (block_info_t *)((std::size_t)node & std::size_t(~(m_real_block_alignment - 1))); + } + + block_info_t *priv_block_from_node(void *node) const + { return priv_block_from_node(node, IsAlignOnly()); } + + hdr_offset_holder *priv_first_subblock_from_block(block_info_t *block) const + { + hdr_offset_holder *hdr_off_holder = reinterpret_cast<hdr_offset_holder*> + (reinterpret_cast<char*>(block) - (m_num_subblocks-1)*m_real_block_alignment); + BOOST_ASSERT(hdr_off_holder->hdr_offset == size_type(reinterpret_cast<char*>(block) - reinterpret_cast<char*>(hdr_off_holder))); + BOOST_ASSERT(0 == ((std::size_t)hdr_off_holder & (m_real_block_alignment - 1))); + BOOST_ASSERT(0 == (hdr_off_holder->hdr_offset & (m_real_block_alignment - 1))); + return hdr_off_holder; + } + + //!Allocates a several blocks of nodes. Can throw + void priv_alloc_block(size_type n, AlignOnlyTrue) + { + size_type real_block_size = m_real_block_alignment - PayloadPerAllocation; + for(size_type i = 0; i != n; ++i){ + //We allocate a new NodeBlock and put it the last + //element of the tree + char *mem_address = static_cast<char*> + (mp_segment_mngr_base->allocate_aligned(real_block_size, m_real_block_alignment)); + if(!mem_address) throw std::bad_alloc(); + ++m_totally_free_blocks; + block_info_t *c_info = new(mem_address)block_info_t(); + m_block_multiset.insert(m_block_multiset.end(), *c_info); + + mem_address += HdrSize; + //We initialize all Nodes in Node Block to insert + //them in the free Node list + typename free_nodes_t::iterator prev_insert_pos = c_info->free_nodes.before_begin(); + for(size_type i = 0; i < m_real_num_node; ++i){ + prev_insert_pos = c_info->free_nodes.insert_after(prev_insert_pos, *(node_t*)mem_address); + mem_address += m_real_node_size; + } + } + } + + void priv_alloc_block(size_type n, AlignOnlyFalse) + { + size_type real_block_size = m_real_block_alignment*m_num_subblocks - PayloadPerAllocation; + size_type elements_per_subblock = (m_real_block_alignment - HdrOffsetSize)/m_real_node_size; + size_type hdr_subblock_elements = (m_real_block_alignment - HdrSize - PayloadPerAllocation)/m_real_node_size; + + for(size_type i = 0; i != n; ++i){ + //We allocate a new NodeBlock and put it the last + //element of the tree + char *mem_address = static_cast<char*> + (mp_segment_mngr_base->allocate_aligned(real_block_size, m_real_block_alignment)); + if(!mem_address) throw std::bad_alloc(); + ++m_totally_free_blocks; + + //First initialize header information on the last subblock + char *hdr_addr = mem_address + m_real_block_alignment*(m_num_subblocks-1); + block_info_t *c_info = new(hdr_addr)block_info_t(); + //Some structural checks + BOOST_ASSERT(static_cast<void*>(&static_cast<hdr_offset_holder*>(c_info)->hdr_offset) == + static_cast<void*>(c_info)); + typename free_nodes_t::iterator prev_insert_pos = c_info->free_nodes.before_begin(); + for( size_type subblock = 0, maxsubblock = m_num_subblocks - 1 + ; subblock < maxsubblock + ; ++subblock, mem_address += m_real_block_alignment){ + //Initialize header offset mark + new(mem_address) hdr_offset_holder(size_type(hdr_addr - mem_address)); + char *pNode = mem_address + HdrOffsetSize; + for(size_type i = 0; i < elements_per_subblock; ++i){ + prev_insert_pos = c_info->free_nodes.insert_after(prev_insert_pos, *new (pNode) node_t); + pNode += m_real_node_size; + } + } + { + char *pNode = hdr_addr + HdrSize; + //We initialize all Nodes in Node Block to insert + //them in the free Node list + for(size_type i = 0; i < hdr_subblock_elements; ++i){ + prev_insert_pos = c_info->free_nodes.insert_after(prev_insert_pos, *new (pNode) node_t); + pNode += m_real_node_size; + } + } + //Insert the block after the free node list is full + m_block_multiset.insert(m_block_multiset.end(), *c_info); + } + } + + //!Allocates a block of nodes. Can throw std::bad_alloc + void priv_alloc_block(size_type n) + { return priv_alloc_block(n, IsAlignOnly()); } + + private: + typedef typename boost::intrusive::pointer_traits + <void_pointer>::template rebind_pointer<segment_manager_base_type>::type segment_mngr_base_ptr_t; + const size_type m_max_free_blocks; + const size_type m_real_node_size; + //Round the size to a power of two value. + //This is the total memory size (including payload) that we want to + //allocate from the general-purpose allocator + const size_type m_real_block_alignment; + size_type m_num_subblocks; + //This is the real number of nodes per block + //const + size_type m_real_num_node; + segment_mngr_base_ptr_t mp_segment_mngr_base; //Segment manager + block_multiset_t m_block_multiset; //Intrusive block list + size_type m_totally_free_blocks; //Free blocks +}; + +} //namespace container_detail { +} //namespace container { +} //namespace boost { + +#include <boost/container/detail/config_end.hpp> + +#endif //#ifndef BOOST_CONTAINER_DETAIL_ADAPTIVE_NODE_POOL_IMPL_HPP diff --git a/boost/container/detail/advanced_insert_int.hpp b/boost/container/detail/advanced_insert_int.hpp new file mode 100644 index 0000000000..58199c7aa8 --- /dev/null +++ b/boost/container/detail/advanced_insert_int.hpp @@ -0,0 +1,428 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2008-2011. 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_ADVANCED_INSERT_INT_HPP +#define BOOST_CONTAINER_ADVANCED_INSERT_INT_HPP + +#if (defined _MSC_VER) && (_MSC_VER >= 1200) +# pragma once +#endif + +#include "config_begin.hpp" +#include <boost/container/detail/workaround.hpp> +#include <boost/container/allocator/allocator_traits.hpp> +#include <boost/move/move.hpp> +#include <iterator> //std::iterator_traits +#include <boost/assert.hpp> + +namespace boost { namespace container { namespace container_detail { + +//This class will be interface for operations dependent on FwdIt types used advanced_insert_aux_impl +template<class Iterator> +struct advanced_insert_aux_int +{ + typedef typename std::iterator_traits<Iterator>::difference_type difference_type; + virtual void copy_remaining_to(Iterator p) = 0; + virtual void uninitialized_copy_remaining_to(Iterator p) = 0; + virtual void uninitialized_copy_some_and_update(Iterator pos, difference_type division_count, bool first) = 0; + virtual void copy_some_and_update(Iterator pos, difference_type division_count, bool first) = 0; + virtual ~advanced_insert_aux_int() {} +}; + +//This class template will adapt each FwIt types to advanced_insert_aux_int +template<class A, class FwdIt, class Iterator> +struct advanced_insert_aux_proxy + : public advanced_insert_aux_int<Iterator> +{ + typedef boost::container::allocator_traits<A> alloc_traits; + typedef typename allocator_traits<A>::size_type size_type; + typedef typename allocator_traits<A>::value_type value_type; + typedef typename advanced_insert_aux_int<Iterator>::difference_type difference_type; + + advanced_insert_aux_proxy(A& a, FwdIt first, FwdIt last) + : a_(a), first_(first), last_(last) + {} + + virtual ~advanced_insert_aux_proxy() + {} + + virtual void copy_remaining_to(Iterator p) + { ::boost::copy_or_move(first_, last_, p); } + + virtual void uninitialized_copy_remaining_to(Iterator p) + { ::boost::container::uninitialized_copy_or_move_alloc(a_, first_, last_, p); } + + virtual void uninitialized_copy_some_and_update(Iterator pos, difference_type division_count, bool first_n) + { + FwdIt mid = first_; + std::advance(mid, division_count); + if(first_n){ + ::boost::container::uninitialized_copy_or_move_alloc(a_, first_, mid, pos); + first_ = mid; + } + else{ + ::boost::container::uninitialized_copy_or_move_alloc(a_, mid, last_, pos); + last_ = mid; + } + } + + virtual void copy_some_and_update(Iterator pos, difference_type division_count, bool first_n) + { + FwdIt mid = first_; + std::advance(mid, division_count); + if(first_n){ + ::boost::copy_or_move(first_, mid, pos); + first_ = mid; + } + else{ + ::boost::copy_or_move(mid, last_, pos); + last_ = mid; + } + } + A &a_; + FwdIt first_, last_; +}; + +//This class template will adapt default construction insertions to advanced_insert_aux_int +template<class A, class Iterator> +struct default_construct_aux_proxy + : public advanced_insert_aux_int<Iterator> +{ + typedef boost::container::allocator_traits<A> alloc_traits; + typedef typename allocator_traits<A>::size_type size_type; + typedef typename allocator_traits<A>::value_type value_type; + typedef typename advanced_insert_aux_int<Iterator>::difference_type difference_type; + + default_construct_aux_proxy(A &a, size_type count) + : a_(a), count_(count) + {} + + virtual ~default_construct_aux_proxy() + {} + + virtual void copy_remaining_to(Iterator) + { //This should never be called with any count + BOOST_ASSERT(count_ == 0); + } + + virtual void uninitialized_copy_remaining_to(Iterator p) + { this->priv_uninitialized_copy(p, count_); } + + virtual void uninitialized_copy_some_and_update(Iterator pos, difference_type division_count, bool first_n) + { + size_type new_count; + if(first_n){ + new_count = division_count; + } + else{ + BOOST_ASSERT(difference_type(count_)>= division_count); + new_count = count_ - division_count; + } + this->priv_uninitialized_copy(pos, new_count); + } + + virtual void copy_some_and_update(Iterator , difference_type division_count, bool first_n) + { + BOOST_ASSERT(count_ == 0); + size_type new_count; + if(first_n){ + new_count = division_count; + } + else{ + BOOST_ASSERT(difference_type(count_)>= division_count); + new_count = count_ - division_count; + } + //This function should never called with a count different to zero + BOOST_ASSERT(new_count == 0); + (void)new_count; + } + + private: + void priv_uninitialized_copy(Iterator p, const size_type n) + { + BOOST_ASSERT(n <= count_); + Iterator orig_p = p; + size_type i = 0; + try{ + for(; i < n; ++i, ++p){ + alloc_traits::construct(a_, container_detail::to_raw_pointer(&*p)); + } + } + catch(...){ + while(i--){ + alloc_traits::destroy(a_, container_detail::to_raw_pointer(&*orig_p++)); + } + throw; + } + count_ -= n; + } + A &a_; + size_type count_; +}; + +}}} //namespace boost { namespace container { namespace container_detail { + +#ifdef BOOST_CONTAINER_PERFECT_FORWARDING + +#include <boost/container/detail/variadic_templates_tools.hpp> +#include <boost/container/detail/stored_ref.hpp> +#include <boost/move/move.hpp> +#include <typeinfo> +//#include <iostream> //For debugging purposes + +namespace boost { +namespace container { +namespace container_detail { + + +//This class template will adapt emplace construction insertions of movable types +//to advanced_insert_aux_int +template<class A, class Iterator, class ...Args> +struct advanced_insert_aux_non_movable_emplace + : public advanced_insert_aux_int<Iterator> +{ + typedef boost::container::allocator_traits<A> alloc_traits; + typedef typename allocator_traits<A>::size_type size_type; + typedef typename allocator_traits<A>::value_type value_type; + typedef typename advanced_insert_aux_int<Iterator>::difference_type difference_type; + typedef typename build_number_seq<sizeof...(Args)>::type index_tuple_t; + + explicit advanced_insert_aux_non_movable_emplace(A &a, Args&&... args) + : a_(a) + , args_(args...) + , used_(false) + {} + + ~advanced_insert_aux_non_movable_emplace() + {} + + virtual void copy_remaining_to(Iterator) + //This code can't be called since value_type is not movable or copyable + { BOOST_ASSERT(false); } + + virtual void uninitialized_copy_remaining_to(Iterator p) + { this->priv_uninitialized_copy_remaining_to(index_tuple_t(), p); } + + virtual void uninitialized_copy_some_and_update(Iterator p, difference_type division_count, bool first_n) + { this->priv_uninitialized_copy_some_and_update(index_tuple_t(), p, division_count, first_n); } + + virtual void copy_some_and_update(Iterator, difference_type, bool ) + //This code can't be called since value_type is not movable or copyable + { BOOST_ASSERT(false); } + + private: + template<int ...IdxPack> + void priv_uninitialized_copy_some_and_update(const index_tuple<IdxPack...>&, Iterator p, difference_type division_count, bool first_n) + { + BOOST_ASSERT(division_count <=1); + if((first_n && division_count == 1) || (!first_n && division_count == 0)){ + if(!used_){ + alloc_traits::construct( a_ + , container_detail::to_raw_pointer(&*p) + , ::boost::container::container_detail:: + stored_ref<Args>::forward(get<IdxPack>(args_))... + ); + used_ = true; + } + } + } + + template<int ...IdxPack> + void priv_uninitialized_copy_remaining_to(const index_tuple<IdxPack...>&, Iterator p) + { + if(!used_){ + alloc_traits::construct( a_ + , container_detail::to_raw_pointer(&*p) + , ::boost::container::container_detail:: + stored_ref<Args>::forward(get<IdxPack>(args_))... + ); + used_ = true; + } + } + + protected: + A &a_; + tuple<Args&...> args_; + bool used_; +}; + +//This class template will adapt emplace construction insertions of movable types +//to advanced_insert_aux_int +template<class A, class Iterator, class ...Args> +struct advanced_insert_aux_emplace + : public advanced_insert_aux_non_movable_emplace<A, Iterator, Args...> +{ + typedef advanced_insert_aux_non_movable_emplace<A, Iterator, Args...> base_t; + typedef typename base_t::value_type value_type; + typedef typename base_t::difference_type difference_type; + typedef typename base_t::index_tuple_t index_tuple_t; + + explicit advanced_insert_aux_emplace(A &a, Args&&... args) + : base_t(a, boost::forward<Args>(args)...) + {} + + ~advanced_insert_aux_emplace() + {} + + //Override only needed functions + virtual void copy_remaining_to(Iterator p) + { this->priv_copy_remaining_to(index_tuple_t(), p); } + + virtual void copy_some_and_update(Iterator p, difference_type division_count, bool first_n) + { this->priv_copy_some_and_update(index_tuple_t(), p, division_count, first_n); } + + private: + template<int ...IdxPack> + void priv_copy_remaining_to(const index_tuple<IdxPack...>&, Iterator p) + { + if(!this->used_){ + *p = boost::move(value_type ( + ::boost::container::container_detail::stored_ref<Args>::forward(get<IdxPack>(this->args_))...)); + this->used_ = true; + } + } + + template<int ...IdxPack> + void priv_copy_some_and_update(const index_tuple<IdxPack...>&, Iterator p, difference_type division_count, bool first_n) + { + BOOST_ASSERT(division_count <=1); + if((first_n && division_count == 1) || (!first_n && division_count == 0)){ + if(!this->used_){ + *p = boost::move(value_type( + ::boost::container::container_detail::stored_ref<Args>::forward(get<IdxPack>(this->args_))...)); + this->used_ = true; + } + } + } +}; + +}}} //namespace boost { namespace container { namespace container_detail { + +#else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING + +#include <boost/container/detail/preprocessor.hpp> +#include <boost/container/detail/value_init.hpp> + +namespace boost { +namespace container { +namespace container_detail { + +#define BOOST_PP_LOCAL_MACRO(n) \ +template<class A, class Iterator BOOST_PP_ENUM_TRAILING_PARAMS(n, class P) > \ +struct BOOST_PP_CAT(BOOST_PP_CAT(advanced_insert_aux_non_movable_emplace, n), arg) \ + : public advanced_insert_aux_int<Iterator> \ +{ \ + typedef boost::container::allocator_traits<A> alloc_traits; \ + typedef typename allocator_traits<A>::size_type size_type; \ + typedef typename allocator_traits<A>::value_type value_type; \ + typedef typename advanced_insert_aux_int<Iterator>::difference_type \ + difference_type; \ + \ + BOOST_PP_CAT(BOOST_PP_CAT(advanced_insert_aux_non_movable_emplace, n), arg) \ + ( A &a BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _) ) \ + : a_(a) \ + , used_(false) \ + BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_INIT, _) \ + {} \ + \ + virtual void copy_remaining_to(Iterator) \ + { BOOST_ASSERT(false); } \ + \ + virtual void uninitialized_copy_remaining_to(Iterator p) \ + { \ + if(!used_){ \ + alloc_traits::construct \ + ( a_ \ + , container_detail::to_raw_pointer(&*p) \ + BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_MEMBER_FORWARD, _) \ + ); \ + used_ = true; \ + } \ + } \ + \ + virtual void uninitialized_copy_some_and_update \ + (Iterator p, difference_type division_count, bool first_n) \ + { \ + BOOST_ASSERT(division_count <=1); \ + if((first_n && division_count == 1) || (!first_n && division_count == 0)){ \ + if(!used_){ \ + alloc_traits::construct \ + ( a_ \ + , container_detail::to_raw_pointer(&*p) \ + BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_MEMBER_FORWARD, _) \ + ); \ + used_ = true; \ + } \ + } \ + } \ + \ + virtual void copy_some_and_update(Iterator, difference_type, bool) \ + { BOOST_ASSERT(false); } \ + \ + A &a_; \ + bool used_; \ + BOOST_PP_REPEAT(n, BOOST_CONTAINER_PP_PARAM_DEFINE, _) \ +}; \ + \ +template<class A, class Iterator BOOST_PP_ENUM_TRAILING_PARAMS(n, class P) > \ +struct BOOST_PP_CAT(BOOST_PP_CAT(advanced_insert_aux_emplace, n), arg) \ + : BOOST_PP_CAT(BOOST_PP_CAT( \ + advanced_insert_aux_non_movable_emplace, n), arg) \ + < A, Iterator BOOST_PP_ENUM_TRAILING_PARAMS(n, P) > \ +{ \ + typedef BOOST_PP_CAT(BOOST_PP_CAT( \ + advanced_insert_aux_non_movable_emplace, n), arg) \ + <A, Iterator BOOST_PP_ENUM_TRAILING_PARAMS(n, P) > base_t; \ + typedef typename base_t::value_type value_type; \ + typedef typename base_t::difference_type difference_type; \ + \ + BOOST_PP_CAT(BOOST_PP_CAT(advanced_insert_aux_emplace, n), arg) \ + ( A &a BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _) ) \ + : base_t(a BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) ) \ + {} \ + \ + virtual void copy_remaining_to(Iterator p) \ + { \ + if(!this->used_){ \ + value_type v BOOST_PP_LPAREN_IF(n) \ + BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_MEMBER_FORWARD, _) \ + BOOST_PP_RPAREN_IF(n); \ + *p = boost::move(v); \ + this->used_ = true; \ + } \ + } \ + \ + virtual void copy_some_and_update \ + (Iterator p, difference_type division_count, bool first_n) \ + { \ + BOOST_ASSERT(division_count <=1); \ + if((first_n && division_count == 1) || (!first_n && division_count == 0)){ \ + if(!this->used_){ \ + value_type v BOOST_PP_LPAREN_IF(n) \ + BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_MEMBER_FORWARD, _) \ + BOOST_PP_RPAREN_IF(n); \ + *p = boost::move(v); \ + this->used_ = true; \ + } \ + } \ + } \ +}; \ +//! + +#define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS) +#include BOOST_PP_LOCAL_ITERATE() + +}}} //namespace boost { namespace container { namespace container_detail { + +#endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING + +#include <boost/container/detail/config_end.hpp> + +#endif //#ifndef BOOST_CONTAINER_ADVANCED_INSERT_INT_HPP diff --git a/boost/container/detail/algorithms.hpp b/boost/container/detail/algorithms.hpp new file mode 100644 index 0000000000..a2713f50f1 --- /dev/null +++ b/boost/container/detail/algorithms.hpp @@ -0,0 +1,60 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2005-2011. +// +// 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_ALGORITHMS_HPP +#define BOOST_CONTAINER_DETAIL_ALGORITHMS_HPP + +#if (defined _MSC_VER) && (_MSC_VER >= 1200) +# pragma once +#endif + +#include "config_begin.hpp" +#include <boost/container/detail/workaround.hpp> + +#include <boost/type_traits/has_trivial_copy.hpp> +#include <boost/type_traits/has_trivial_assign.hpp> +#include <boost/detail/no_exceptions_support.hpp> + +#include <boost/container/detail/type_traits.hpp> +#include <boost/container/detail/mpl.hpp> +#include <boost/container/detail/iterators.hpp> + + +#include <cstring> + +namespace boost { +namespace container { + +template<class A, class T, class InpIt> +inline void construct_in_place(A &a, T* dest, InpIt source) +{ boost::container::allocator_traits<A>::construct(a, dest, *source); } +//#endif + +template<class A, class T, class U, class D> +inline void construct_in_place(A &a, T *dest, default_construct_iterator<U, D>) +{ + boost::container::allocator_traits<A>::construct(a, dest); +} + +template<class A, class T, class U, class EF, class D> +inline void construct_in_place(A &a, T *dest, emplace_iterator<U, EF, D> ei) +{ + ei.construct_in_place(a, dest); +} + +} //namespace container { +} //namespace boost { + +#include <boost/container/detail/config_end.hpp> + +#endif //#ifndef BOOST_CONTAINER_DETAIL_ALGORITHMS_HPP + diff --git a/boost/container/detail/allocation_type.hpp b/boost/container/detail/allocation_type.hpp new file mode 100644 index 0000000000..edad487c57 --- /dev/null +++ b/boost/container/detail/allocation_type.hpp @@ -0,0 +1,54 @@ +/////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2005-2011. 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_ALLOCATION_TYPE_HPP +#define BOOST_CONTAINER_ALLOCATION_TYPE_HPP + +#if (defined _MSC_VER) && (_MSC_VER >= 1200) +# pragma once +#endif + +#include "config_begin.hpp" +#include <boost/container/detail/workaround.hpp> + +namespace boost { +namespace container { + +/// @cond +enum allocation_type_v +{ + // constants for allocation commands + allocate_new_v = 0x01, + expand_fwd_v = 0x02, + expand_bwd_v = 0x04, +// expand_both = expand_fwd | expand_bwd, +// expand_or_new = allocate_new | expand_both, + shrink_in_place_v = 0x08, + nothrow_allocation_v = 0x10, + zero_memory_v = 0x20, + try_shrink_in_place_v = 0x40 +}; + +typedef int allocation_type; +/// @endcond +static const allocation_type allocate_new = (allocation_type)allocate_new_v; +static const allocation_type expand_fwd = (allocation_type)expand_fwd_v; +static const allocation_type expand_bwd = (allocation_type)expand_bwd_v; +static const allocation_type shrink_in_place = (allocation_type)shrink_in_place_v; +static const allocation_type try_shrink_in_place= (allocation_type)try_shrink_in_place_v; +static const allocation_type nothrow_allocation = (allocation_type)nothrow_allocation_v; +static const allocation_type zero_memory = (allocation_type)zero_memory_v; + +} //namespace container { +} //namespace boost { + +#include <boost/container/detail/config_end.hpp> + +#endif //BOOST_CONTAINER_ALLOCATION_TYPE_HPP diff --git a/boost/container/detail/config_begin.hpp b/boost/container/detail/config_begin.hpp new file mode 100644 index 0000000000..bd44daacfe --- /dev/null +++ b/boost/container/detail/config_begin.hpp @@ -0,0 +1,48 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2005-2011. 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_CONTAINER_DETAIL_CONFIG_INCLUDED +#define BOOST_CONTAINER_CONTAINER_DETAIL_CONFIG_INCLUDED +#include <boost/config.hpp> + +#endif //BOOST_CONTAINER_CONTAINER_DETAIL_CONFIG_INCLUDED + +#ifdef BOOST_MSVC + #ifndef _CRT_SECURE_NO_DEPRECATE + #define BOOST_CONTAINER_DETAIL_CRT_SECURE_NO_DEPRECATE + #define _CRT_SECURE_NO_DEPRECATE + #endif + #pragma warning (push) + #pragma warning (disable : 4702) // unreachable code + #pragma warning (disable : 4706) // assignment within conditional expression + #pragma warning (disable : 4127) // conditional expression is constant + #pragma warning (disable : 4146) // unary minus operator applied to unsigned type, result still unsigned + #pragma warning (disable : 4284) // odd return type for operator-> + #pragma warning (disable : 4244) // possible loss of data + #pragma warning (disable : 4251) // "identifier" : class "type" needs to have dll-interface to be used by clients of class "type2" + #pragma warning (disable : 4267) // conversion from "X" to "Y", possible loss of data + #pragma warning (disable : 4275) // non DLL-interface classkey "identifier" used as base for DLL-interface classkey "identifier" + #pragma warning (disable : 4355) // "this" : used in base member initializer list + #pragma warning (disable : 4503) // "identifier" : decorated name length exceeded, name was truncated + #pragma warning (disable : 4511) // copy constructor could not be generated + #pragma warning (disable : 4512) // assignment operator could not be generated + #pragma warning (disable : 4514) // unreferenced inline removed + #pragma warning (disable : 4521) // Disable "multiple copy constructors specified" + #pragma warning (disable : 4522) // "class" : multiple assignment operators specified + #pragma warning (disable : 4675) // "method" should be declared "static" and have exactly one parameter + #pragma warning (disable : 4710) // function not inlined + #pragma warning (disable : 4711) // function selected for automatic inline expansion + #pragma warning (disable : 4786) // identifier truncated in debug info + #pragma warning (disable : 4996) // "function": was declared deprecated + #pragma warning (disable : 4197) // top-level volatile in cast is ignored + #pragma warning (disable : 4541) // 'typeid' used on polymorphic type 'boost::exception' + // with /GR-; unpredictable behavior may result + #pragma warning (disable : 4673) // throwing '' the following types will not be considered at the catch site + #pragma warning (disable : 4671) // the copy constructor is inaccessible +#endif //BOOST_MSVC diff --git a/boost/container/detail/config_end.hpp b/boost/container/detail/config_end.hpp new file mode 100644 index 0000000000..b71fabcdae --- /dev/null +++ b/boost/container/detail/config_end.hpp @@ -0,0 +1,17 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2005-2011. 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. +// +////////////////////////////////////////////////////////////////////////////// +#if defined BOOST_MSVC + #pragma warning (pop) + #ifdef BOOST_CONTAINER_DETAIL_CRT_SECURE_NO_DEPRECATE + #undef BOOST_CONTAINER_DETAIL_CRT_SECURE_NO_DEPRECATE + #undef _CRT_SECURE_NO_DEPRECATE + #endif +#endif + diff --git a/boost/container/detail/destroyers.hpp b/boost/container/detail/destroyers.hpp new file mode 100644 index 0000000000..26ae089aa6 --- /dev/null +++ b/boost/container/detail/destroyers.hpp @@ -0,0 +1,163 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2005-2011. +// +// 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_DESTROYERS_HPP +#define BOOST_CONTAINER_DESTROYERS_HPP + +#if (defined _MSC_VER) && (_MSC_VER >= 1200) +# pragma once +#endif + +#include "config_begin.hpp" +#include <boost/container/detail/workaround.hpp> +#include <boost/container/detail/version_type.hpp> +#include <boost/container/detail/utilities.hpp> +#include <boost/container/allocator/allocator_traits.hpp> + +namespace boost { +namespace container { +namespace container_detail { + +//!A deleter for scoped_ptr that deallocates the memory +//!allocated for an array of objects using a STL allocator. +template <class Allocator> +struct scoped_array_deallocator +{ + typedef boost::container::allocator_traits<Allocator> AllocTraits; + typedef typename AllocTraits::pointer pointer; + typedef typename AllocTraits::size_type size_type; + + scoped_array_deallocator(pointer p, Allocator& a, size_type length) + : m_ptr(p), m_alloc(a), m_length(length) {} + + ~scoped_array_deallocator() + { if (m_ptr) m_alloc.deallocate(m_ptr, m_length); } + + void release() + { m_ptr = 0; } + + private: + pointer m_ptr; + Allocator& m_alloc; + size_type m_length; +}; + +template <class Allocator> +struct null_scoped_array_deallocator +{ + typedef boost::container::allocator_traits<Allocator> AllocTraits; + typedef typename AllocTraits::pointer pointer; + typedef typename AllocTraits::size_type size_type; + + null_scoped_array_deallocator(pointer, Allocator&, size_type) + {} + + void release() + {} +}; + + +//!A deleter for scoped_ptr that destroys +//!an object using a STL allocator. +template <class Allocator> +struct scoped_destructor_n +{ + typedef boost::container::allocator_traits<Allocator> AllocTraits; + typedef typename AllocTraits::pointer pointer; + typedef typename AllocTraits::value_type value_type; + typedef typename AllocTraits::size_type size_type; + + scoped_destructor_n(pointer p, Allocator& a, size_type n) + : m_p(p), m_a(a), m_n(n) + {} + + void release() + { m_p = 0; } + + void increment_size(size_type inc) + { m_n += inc; } + + ~scoped_destructor_n() + { + if(!m_p) return; + value_type *raw_ptr = container_detail::to_raw_pointer(m_p); + for(size_type i = 0; i < m_n; ++i, ++raw_ptr) + AllocTraits::destroy(m_a, raw_ptr); + } + + private: + pointer m_p; + Allocator & m_a; + size_type m_n; +}; + +//!A deleter for scoped_ptr that destroys +//!an object using a STL allocator. +template <class Allocator> +struct null_scoped_destructor_n +{ + typedef boost::container::allocator_traits<Allocator> AllocTraits; + typedef typename AllocTraits::pointer pointer; + typedef typename AllocTraits::size_type size_type; + + null_scoped_destructor_n(pointer, Allocator&, size_type) + {} + + void increment_size(size_type) + {} + + void release() + {} +}; + +template <class Allocator> +class allocator_destroyer +{ + typedef boost::container::allocator_traits<Allocator> AllocTraits; + typedef typename AllocTraits::value_type value_type; + typedef typename AllocTraits::pointer pointer; + typedef container_detail::integral_constant<unsigned, + boost::container::container_detail:: + version<Allocator>::value> alloc_version; + typedef container_detail::integral_constant<unsigned, 1> allocator_v1; + typedef container_detail::integral_constant<unsigned, 2> allocator_v2; + + private: + Allocator & a_; + + private: + void priv_deallocate(const pointer &p, allocator_v1) + { AllocTraits::deallocate(a_,p, 1); } + + void priv_deallocate(const pointer &p, allocator_v2) + { a_.deallocate_one(p); } + + public: + allocator_destroyer(Allocator &a) + : a_(a) + {} + + void operator()(const pointer &p) + { + AllocTraits::destroy(a_, container_detail::to_raw_pointer(p)); + priv_deallocate(p, alloc_version()); + } +}; + + +} //namespace container_detail { +} //namespace container { +} //namespace boost { + +#include <boost/container/detail/config_end.hpp> + +#endif //#ifndef BOOST_CONTAINER_DESTROYERS_HPP diff --git a/boost/container/detail/flat_tree.hpp b/boost/container/detail/flat_tree.hpp new file mode 100644 index 0000000000..44438386a3 --- /dev/null +++ b/boost/container/detail/flat_tree.hpp @@ -0,0 +1,822 @@ +//////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2005-2011. 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_FLAT_TREE_HPP +#define BOOST_CONTAINER_FLAT_TREE_HPP + +#if (defined _MSC_VER) && (_MSC_VER >= 1200) +# pragma once +#endif + +#include "config_begin.hpp" +#include <boost/container/detail/workaround.hpp> + +#include <boost/container/container_fwd.hpp> + +#include <algorithm> +#include <functional> +#include <utility> + +#include <boost/type_traits/has_trivial_destructor.hpp> +#include <boost/move/move.hpp> + +#include <boost/container/detail/utilities.hpp> +#include <boost/container/detail/pair.hpp> +#include <boost/container/vector.hpp> +#include <boost/container/detail/value_init.hpp> +#include <boost/container/detail/destroyers.hpp> + +namespace boost { + +namespace container { + +namespace container_detail { + +template<class Compare, class Value, class KeyOfValue> +class flat_tree_value_compare + : private Compare +{ + typedef Value first_argument_type; + typedef Value second_argument_type; + typedef bool return_type; + public: + flat_tree_value_compare() + : Compare() + {} + + flat_tree_value_compare(const Compare &pred) + : Compare(pred) + {} + + bool operator()(const Value& lhs, const Value& rhs) const + { + KeyOfValue key_extract; + return Compare::operator()(key_extract(lhs), key_extract(rhs)); + } + + const Compare &get_comp() const + { return *this; } + + Compare &get_comp() + { return *this; } +}; + +template<class Pointer> +struct get_flat_tree_iterators +{ + typedef typename container_detail:: + vector_iterator<Pointer> iterator; + typedef typename container_detail:: + vector_const_iterator<Pointer> const_iterator; + typedef std::reverse_iterator<iterator> reverse_iterator; + typedef std::reverse_iterator<const_iterator> const_reverse_iterator; +}; + +template <class Key, class Value, class KeyOfValue, + class Compare, class A> +class flat_tree +{ + typedef boost::container::vector<Value, A> vector_t; + typedef A allocator_t; + + public: + typedef flat_tree_value_compare<Compare, Value, KeyOfValue> value_compare; + + private: + struct Data + //Inherit from value_compare to do EBO + : public value_compare + { + BOOST_COPYABLE_AND_MOVABLE(Data) + + public: + Data() + : value_compare(), m_vect() + {} + + Data(const Data &d) + : value_compare(d), m_vect(d.m_vect) + {} + + Data(BOOST_RV_REF(Data) d) + : value_compare(boost::move(d)), m_vect(boost::move(d.m_vect)) + {} + + Data(const Compare &comp) + : value_compare(comp), m_vect() + {} + + Data(const Compare &comp, + const allocator_t &alloc) + : value_compare(comp), m_vect(alloc) + {} + + Data& operator=(BOOST_COPY_ASSIGN_REF(Data) d) + { + this->value_compare::operator=(d); + m_vect = d.m_vect; + return *this; + } + + Data& operator=(BOOST_RV_REF(Data) d) + { + this->value_compare::operator=(boost::move(static_cast<value_compare &>(d))); + m_vect = boost::move(d.m_vect); + return *this; + } + + void swap(Data &d) + { + value_compare& mycomp = *this, & othercomp = d; + container_detail::do_swap(mycomp, othercomp); + this->m_vect.swap(d.m_vect); + } + + vector_t m_vect; + }; + + Data m_data; + BOOST_COPYABLE_AND_MOVABLE(flat_tree) + + public: + + typedef typename vector_t::value_type value_type; + typedef typename vector_t::pointer pointer; + typedef typename vector_t::const_pointer const_pointer; + typedef typename vector_t::reference reference; + typedef typename vector_t::const_reference const_reference; + typedef Key key_type; + typedef Compare key_compare; + typedef typename vector_t::allocator_type allocator_type; + typedef typename vector_t::size_type size_type; + typedef typename vector_t::difference_type difference_type; + typedef typename vector_t::iterator iterator; + typedef typename vector_t::const_iterator const_iterator; + typedef typename vector_t::reverse_iterator reverse_iterator; + typedef typename vector_t::const_reverse_iterator const_reverse_iterator; + + //!Standard extension + typedef allocator_type stored_allocator_type; + + flat_tree() + : m_data() + { } + + explicit flat_tree(const Compare& comp) + : m_data(comp) + { } + + flat_tree(const Compare& comp, const allocator_type& a) + : m_data(comp, a) + { } + + flat_tree(const flat_tree& x) + : m_data(x.m_data) + { } + + flat_tree(BOOST_RV_REF(flat_tree) x) + : m_data(boost::move(x.m_data)) + { } + + template <class InputIterator> + flat_tree( ordered_range_t, InputIterator first, InputIterator last + , const Compare& comp = Compare() + , const allocator_type& a = allocator_type()) + : m_data(comp, a) + { this->m_data.m_vect.insert(this->m_data.m_vect.end(), first, last); } + + ~flat_tree() + { } + + flat_tree& operator=(BOOST_COPY_ASSIGN_REF(flat_tree) x) + { m_data = x.m_data; return *this; } + + flat_tree& operator=(BOOST_RV_REF(flat_tree) mx) + { m_data = boost::move(mx.m_data); return *this; } + + public: + // accessors: + Compare key_comp() const + { return this->m_data.get_comp(); } + + allocator_type get_allocator() const + { return this->m_data.m_vect.get_allocator(); } + + const stored_allocator_type &get_stored_allocator() const + { return this->m_data.m_vect.get_stored_allocator(); } + + stored_allocator_type &get_stored_allocator() + { return this->m_data.m_vect.get_stored_allocator(); } + + iterator begin() + { return this->m_data.m_vect.begin(); } + + const_iterator begin() const + { return this->cbegin(); } + + const_iterator cbegin() const + { return this->m_data.m_vect.begin(); } + + iterator end() + { return this->m_data.m_vect.end(); } + + const_iterator end() const + { return this->cend(); } + + const_iterator cend() const + { return this->m_data.m_vect.end(); } + + reverse_iterator rbegin() + { return reverse_iterator(this->end()); } + + const_reverse_iterator rbegin() const + { return this->crbegin(); } + + const_reverse_iterator crbegin() const + { return const_reverse_iterator(this->cend()); } + + reverse_iterator rend() + { return reverse_iterator(this->begin()); } + + const_reverse_iterator rend() const + { return this->crend(); } + + const_reverse_iterator crend() const + { return const_reverse_iterator(this->cbegin()); } + + bool empty() const + { return this->m_data.m_vect.empty(); } + + size_type size() const + { return this->m_data.m_vect.size(); } + + size_type max_size() const + { return this->m_data.m_vect.max_size(); } + + void swap(flat_tree& other) + { this->m_data.swap(other.m_data); } + + public: + // insert/erase + std::pair<iterator,bool> insert_unique(const value_type& val) + { + insert_commit_data data; + std::pair<iterator,bool> ret = priv_insert_unique_prepare(val, data); + if(ret.second){ + ret.first = priv_insert_commit(data, val); + } + return ret; + } + + std::pair<iterator,bool> insert_unique(BOOST_RV_REF(value_type) val) + { + insert_commit_data data; + std::pair<iterator,bool> ret = priv_insert_unique_prepare(val, data); + if(ret.second){ + ret.first = priv_insert_commit(data, boost::move(val)); + } + return ret; + } + + + iterator insert_equal(const value_type& val) + { + iterator i = this->upper_bound(KeyOfValue()(val)); + i = this->m_data.m_vect.insert(i, val); + return i; + } + + iterator insert_equal(BOOST_RV_REF(value_type) mval) + { + iterator i = this->upper_bound(KeyOfValue()(mval)); + i = this->m_data.m_vect.insert(i, boost::move(mval)); + return i; + } + + iterator insert_unique(const_iterator pos, const value_type& val) + { + insert_commit_data data; + std::pair<iterator,bool> ret = priv_insert_unique_prepare(pos, val, data); + if(ret.second){ + ret.first = priv_insert_commit(data, val); + } + return ret.first; + } + + iterator insert_unique(const_iterator pos, BOOST_RV_REF(value_type) mval) + { + insert_commit_data data; + std::pair<iterator,bool> ret = priv_insert_unique_prepare(pos, mval, data); + if(ret.second){ + ret.first = priv_insert_commit(data, boost::move(mval)); + } + return ret.first; + } + + iterator insert_equal(const_iterator pos, const value_type& val) + { + insert_commit_data data; + priv_insert_equal_prepare(pos, val, data); + return priv_insert_commit(data, val); + } + + iterator insert_equal(const_iterator pos, BOOST_RV_REF(value_type) mval) + { + insert_commit_data data; + priv_insert_equal_prepare(pos, mval, data); + return priv_insert_commit(data, boost::move(mval)); + } + + template <class InIt> + void insert_unique(InIt first, InIt last) + { + for ( ; first != last; ++first) + this->insert_unique(*first); + } + + template <class InIt> + void insert_equal(InIt first, InIt last) + { + typedef typename + std::iterator_traits<InIt>::iterator_category ItCat; + priv_insert_equal(first, last, ItCat()); + } + + #ifdef BOOST_CONTAINER_PERFECT_FORWARDING + + template <class... Args> + std::pair<iterator, bool> emplace_unique(Args&&... args) + { + value_type && val = value_type(boost::forward<Args>(args)...); + insert_commit_data data; + std::pair<iterator,bool> ret = + priv_insert_unique_prepare(val, data); + if(ret.second){ + ret.first = priv_insert_commit(data, boost::move(val)); + } + return ret; + } + + template <class... Args> + iterator emplace_hint_unique(const_iterator hint, Args&&... args) + { + value_type && val = value_type(boost::forward<Args>(args)...); + insert_commit_data data; + std::pair<iterator,bool> ret = priv_insert_unique_prepare(hint, val, data); + if(ret.second){ + ret.first = priv_insert_commit(data, boost::move(val)); + } + return ret.first; + } + + template <class... Args> + iterator emplace_equal(Args&&... args) + { + value_type &&val = value_type(boost::forward<Args>(args)...); + iterator i = this->upper_bound(KeyOfValue()(val)); + i = this->m_data.m_vect.insert(i, boost::move(val)); + return i; + } + + template <class... Args> + iterator emplace_hint_equal(const_iterator hint, Args&&... args) + { + value_type &&val = value_type(boost::forward<Args>(args)...); + insert_commit_data data; + priv_insert_equal_prepare(hint, val, data); + return priv_insert_commit(data, boost::move(val)); + } + + #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING + + #define BOOST_PP_LOCAL_MACRO(n) \ + BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ + std::pair<iterator, bool> \ + emplace_unique(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ + { \ + BOOST_PP_EXPR_IF(BOOST_PP_NOT(n), container_detail::value_init<) value_type \ + BOOST_PP_EXPR_IF(BOOST_PP_NOT(n), >) vval BOOST_PP_LPAREN_IF(n) \ + BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) BOOST_PP_RPAREN_IF(n); \ + value_type &val = vval; \ + insert_commit_data data; \ + std::pair<iterator,bool> ret = priv_insert_unique_prepare(val, data); \ + if(ret.second){ \ + ret.first = priv_insert_commit(data, boost::move(val)); \ + } \ + return ret; \ + } \ + \ + BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ + iterator emplace_hint_unique(const_iterator hint \ + BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ + { \ + BOOST_PP_EXPR_IF(BOOST_PP_NOT(n), container_detail::value_init<) value_type \ + BOOST_PP_EXPR_IF(BOOST_PP_NOT(n), >) vval BOOST_PP_LPAREN_IF(n) \ + BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) BOOST_PP_RPAREN_IF(n); \ + value_type &val = vval; \ + insert_commit_data data; \ + std::pair<iterator,bool> ret = priv_insert_unique_prepare(hint, val, data); \ + if(ret.second){ \ + ret.first = priv_insert_commit(data, boost::move(val)); \ + } \ + return ret.first; \ + } \ + \ + BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ + iterator emplace_equal(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ + { \ + BOOST_PP_EXPR_IF(BOOST_PP_NOT(n), container_detail::value_init<) value_type \ + BOOST_PP_EXPR_IF(BOOST_PP_NOT(n), >) vval BOOST_PP_LPAREN_IF(n) \ + BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) BOOST_PP_RPAREN_IF(n); \ + value_type &val = vval; \ + iterator i = this->upper_bound(KeyOfValue()(val)); \ + i = this->m_data.m_vect.insert(i, boost::move(val)); \ + return i; \ + } \ + \ + BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ + iterator emplace_hint_equal(const_iterator hint \ + BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ + { \ + BOOST_PP_EXPR_IF(BOOST_PP_NOT(n), container_detail::value_init<) value_type \ + BOOST_PP_EXPR_IF(BOOST_PP_NOT(n), >) vval BOOST_PP_LPAREN_IF(n) \ + BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _) BOOST_PP_RPAREN_IF(n); \ + value_type &val = vval; \ + insert_commit_data data; \ + priv_insert_equal_prepare(hint, val, data); \ + return priv_insert_commit(data, boost::move(val)); \ + } \ + //! + #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS) + #include BOOST_PP_LOCAL_ITERATE() + + #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING + + iterator erase(const_iterator position) + { return this->m_data.m_vect.erase(position); } + + size_type erase(const key_type& k) + { + std::pair<iterator,iterator > itp = this->equal_range(k); + size_type ret = static_cast<size_type>(itp.second-itp.first); + if (ret){ + this->m_data.m_vect.erase(itp.first, itp.second); + } + return ret; + } + + iterator erase(const_iterator first, const_iterator last) + { return this->m_data.m_vect.erase(first, last); } + + void clear() + { this->m_data.m_vect.clear(); } + + //! <b>Effects</b>: Tries to deallocate the excess of memory created + // with previous allocations. The size of the vector is unchanged + //! + //! <b>Throws</b>: If memory allocation throws, or T's copy constructor throws. + //! + //! <b>Complexity</b>: Linear to size(). + void shrink_to_fit() + { this->m_data.m_vect.shrink_to_fit(); } + + // set operations: + iterator find(const key_type& k) + { + const Compare &key_comp = this->m_data.get_comp(); + iterator i = this->lower_bound(k); + + if (i != this->end() && key_comp(k, KeyOfValue()(*i))){ + i = this->end(); + } + return i; + } + + const_iterator find(const key_type& k) const + { + const Compare &key_comp = this->m_data.get_comp(); + const_iterator i = this->lower_bound(k); + + if (i != this->end() && key_comp(k, KeyOfValue()(*i))){ + i = this->end(); + } + return i; + } + + size_type count(const key_type& k) const + { + std::pair<const_iterator, const_iterator> p = this->equal_range(k); + size_type n = p.second - p.first; + return n; + } + + iterator lower_bound(const key_type& k) + { return this->priv_lower_bound(this->begin(), this->end(), k); } + + const_iterator lower_bound(const key_type& k) const + { return this->priv_lower_bound(this->begin(), this->end(), k); } + + iterator upper_bound(const key_type& k) + { return this->priv_upper_bound(this->begin(), this->end(), k); } + + const_iterator upper_bound(const key_type& k) const + { return this->priv_upper_bound(this->begin(), this->end(), k); } + + std::pair<iterator,iterator> equal_range(const key_type& k) + { return this->priv_equal_range(this->begin(), this->end(), k); } + + std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const + { return this->priv_equal_range(this->begin(), this->end(), k); } + + size_type capacity() const + { return this->m_data.m_vect.capacity(); } + + void reserve(size_type count) + { this->m_data.m_vect.reserve(count); } + + private: + struct insert_commit_data + { + const_iterator position; + }; + + // insert/erase + void priv_insert_equal_prepare + (const_iterator pos, const value_type& val, insert_commit_data &data) + { + // N1780 + // To insert val at pos: + // if pos == end || val <= *pos + // if pos == begin || val >= *(pos-1) + // insert val before pos + // else + // insert val before upper_bound(val) + // else + // insert val before lower_bound(val) + const value_compare &value_comp = this->m_data; + + if(pos == this->cend() || !value_comp(*pos, val)){ + if (pos == this->cbegin() || !value_comp(val, pos[-1])){ + data.position = pos; + } + else{ + data.position = + this->priv_upper_bound(this->cbegin(), pos, KeyOfValue()(val)); + } + } + else{ + data.position = + this->priv_lower_bound(pos, this->cend(), KeyOfValue()(val)); + } + } + + std::pair<iterator,bool> priv_insert_unique_prepare + (const_iterator beg, const_iterator end, const value_type& val, insert_commit_data &commit_data) + { + const value_compare &value_comp = this->m_data; + commit_data.position = this->priv_lower_bound(beg, end, KeyOfValue()(val)); + return std::pair<iterator,bool> + ( *reinterpret_cast<iterator*>(&commit_data.position) + , commit_data.position == end || value_comp(val, *commit_data.position)); + } + + std::pair<iterator,bool> priv_insert_unique_prepare + (const value_type& val, insert_commit_data &commit_data) + { return priv_insert_unique_prepare(this->begin(), this->end(), val, commit_data); } + + std::pair<iterator,bool> priv_insert_unique_prepare + (const_iterator pos, const value_type& val, insert_commit_data &commit_data) + { + //N1780. Props to Howard Hinnant! + //To insert val at pos: + //if pos == end || val <= *pos + // if pos == begin || val >= *(pos-1) + // insert val before pos + // else + // insert val before upper_bound(val) + //else if pos+1 == end || val <= *(pos+1) + // insert val after pos + //else + // insert val before lower_bound(val) + const value_compare &value_comp = this->m_data; + + if(pos == this->cend() || value_comp(val, *pos)){ + if(pos != this->cbegin() && !value_comp(val, pos[-1])){ + if(value_comp(pos[-1], val)){ + commit_data.position = pos; + return std::pair<iterator,bool>(*reinterpret_cast<iterator*>(&pos), true); + } + else{ + return std::pair<iterator,bool>(*reinterpret_cast<iterator*>(&pos), false); + } + } + return this->priv_insert_unique_prepare(this->cbegin(), pos, val, commit_data); + } + + // Works, but increases code complexity + //Next check + //else if (value_comp(*pos, val) && !value_comp(pos[1], val)){ + // if(value_comp(val, pos[1])){ + // commit_data.position = pos+1; + // return std::pair<iterator,bool>(pos+1, true); + // } + // else{ + // return std::pair<iterator,bool>(pos+1, false); + // } + //} + else{ + //[... pos ... val ... ] + //The hint is before the insertion position, so insert it + //in the remaining range + return this->priv_insert_unique_prepare(pos, this->end(), val, commit_data); + } + } + + template<class Convertible> + iterator priv_insert_commit + (insert_commit_data &commit_data, BOOST_FWD_REF(Convertible) convertible) + { + return this->m_data.m_vect.insert + ( commit_data.position + , boost::forward<Convertible>(convertible)); + } + + template <class RanIt> + RanIt priv_lower_bound(RanIt first, RanIt last, + const key_type & key) const + { + const Compare &key_comp = this->m_data.get_comp(); + KeyOfValue key_extract; + difference_type len = last - first, half; + RanIt middle; + + while (len > 0) { + half = len >> 1; + middle = first; + middle += half; + + if (key_comp(key_extract(*middle), key)) { + ++middle; + first = middle; + len = len - half - 1; + } + else + len = half; + } + return first; + } + + template <class RanIt> + RanIt priv_upper_bound(RanIt first, RanIt last, + const key_type & key) const + { + const Compare &key_comp = this->m_data.get_comp(); + KeyOfValue key_extract; + difference_type len = last - first, half; + RanIt middle; + + while (len > 0) { + half = len >> 1; + middle = first; + middle += half; + + if (key_comp(key, key_extract(*middle))) { + len = half; + } + else{ + first = ++middle; + len = len - half - 1; + } + } + return first; + } + + template <class RanIt> + std::pair<RanIt, RanIt> + priv_equal_range(RanIt first, RanIt last, const key_type& key) const + { + const Compare &key_comp = this->m_data.get_comp(); + KeyOfValue key_extract; + difference_type len = last - first, half; + RanIt middle, left, right; + + while (len > 0) { + half = len >> 1; + middle = first; + middle += half; + + if (key_comp(key_extract(*middle), key)){ + first = middle; + ++first; + len = len - half - 1; + } + else if (key_comp(key, key_extract(*middle))){ + len = half; + } + else { + left = this->priv_lower_bound(first, middle, key); + first += len; + right = this->priv_upper_bound(++middle, first, key); + return std::pair<RanIt, RanIt>(left, right); + } + } + return std::pair<RanIt, RanIt>(first, first); + } + + template <class FwdIt> + void priv_insert_equal(FwdIt first, FwdIt last, std::forward_iterator_tag) + { + size_type len = static_cast<size_type>(std::distance(first, last)); + this->reserve(this->size()+len); + this->priv_insert_equal(first, last, std::input_iterator_tag()); + } + + template <class InIt> + void priv_insert_equal(InIt first, InIt last, std::input_iterator_tag) + { + for ( ; first != last; ++first) + this->insert_equal(*first); + } +}; + +template <class Key, class Value, class KeyOfValue, + class Compare, class A> +inline bool +operator==(const flat_tree<Key,Value,KeyOfValue,Compare,A>& x, + const flat_tree<Key,Value,KeyOfValue,Compare,A>& y) +{ + return x.size() == y.size() && + std::equal(x.begin(), x.end(), y.begin()); +} + +template <class Key, class Value, class KeyOfValue, + class Compare, class A> +inline bool +operator<(const flat_tree<Key,Value,KeyOfValue,Compare,A>& x, + const flat_tree<Key,Value,KeyOfValue,Compare,A>& y) +{ + return std::lexicographical_compare(x.begin(), x.end(), + y.begin(), y.end()); +} + +template <class Key, class Value, class KeyOfValue, + class Compare, class A> +inline bool +operator!=(const flat_tree<Key,Value,KeyOfValue,Compare,A>& x, + const flat_tree<Key,Value,KeyOfValue,Compare,A>& y) + { return !(x == y); } + +template <class Key, class Value, class KeyOfValue, + class Compare, class A> +inline bool +operator>(const flat_tree<Key,Value,KeyOfValue,Compare,A>& x, + const flat_tree<Key,Value,KeyOfValue,Compare,A>& y) + { return y < x; } + +template <class Key, class Value, class KeyOfValue, + class Compare, class A> +inline bool +operator<=(const flat_tree<Key,Value,KeyOfValue,Compare,A>& x, + const flat_tree<Key,Value,KeyOfValue,Compare,A>& y) + { return !(y < x); } + +template <class Key, class Value, class KeyOfValue, + class Compare, class A> +inline bool +operator>=(const flat_tree<Key,Value,KeyOfValue,Compare,A>& x, + const flat_tree<Key,Value,KeyOfValue,Compare,A>& y) + { return !(x < y); } + + +template <class Key, class Value, class KeyOfValue, + class Compare, class A> +inline void +swap(flat_tree<Key,Value,KeyOfValue,Compare,A>& x, + flat_tree<Key,Value,KeyOfValue,Compare,A>& y) + { x.swap(y); } + +} //namespace container_detail { + +} //namespace container { +/* +//!has_trivial_destructor_after_move<> == true_type +//!specialization for optimizations +template <class K, class V, class KOV, +class C, class A> +struct has_trivial_destructor_after_move<boost::container::container_detail::flat_tree<K, V, KOV, C, A> > +{ + static const bool value = has_trivial_destructor<A>::value && has_trivial_destructor<C>::value; +}; +*/ +} //namespace boost { + +#include <boost/container/detail/config_end.hpp> + +#endif // BOOST_CONTAINER_FLAT_TREE_HPP diff --git a/boost/container/detail/function_detector.hpp b/boost/container/detail/function_detector.hpp new file mode 100644 index 0000000000..c37c766844 --- /dev/null +++ b/boost/container/detail/function_detector.hpp @@ -0,0 +1,88 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2009-2011. +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +// 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_CONTAINER_DETAIL_FUNCTION_DETECTOR_HPP +#define BOOST_CONTAINER_DETAIL_FUNCTION_DETECTOR_HPP + +#include <boost/container/detail/config_begin.hpp> + +namespace boost { +namespace container { +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 container { +} //namespace function_detector { + +#define BOOST_CONTAINER_CREATE_FUNCTION_DETECTOR(Identifier, InstantiationKey) \ + namespace boost { \ + namespace container { \ + 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::container::function_detector { + +#define BOOST_CONTAINER_DETECT_FUNCTION(Class, InstantiationKey, ReturnType, Identifier, Params) \ + ::boost::container::function_detector::DetectMember_##InstantiationKey_##Identifier< Class,\ + ReturnType (Class::*)Params,\ + ReturnType (Class::*)Params const,\ + ReturnType (*)Params \ + >::check + +#include <boost/container/detail/config_end.hpp> + +#endif //@ifndef BOOST_CONTAINER_DETAIL_FUNCTION_DETECTOR_HPP diff --git a/boost/container/detail/iterators.hpp b/boost/container/detail/iterators.hpp new file mode 100644 index 0000000000..899cbe4349 --- /dev/null +++ b/boost/container/detail/iterators.hpp @@ -0,0 +1,548 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2005-2011. +// (C) Copyright Gennaro Prota 2003 - 2004. +// +// 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_ITERATORS_HPP +#define BOOST_CONTAINER_DETAIL_ITERATORS_HPP + +#if (defined _MSC_VER) && (_MSC_VER >= 1200) +# pragma once +#endif + +#include "config_begin.hpp" +#include <boost/container/detail/workaround.hpp> +#include <boost/move/move.hpp> +#include <boost/container/allocator/allocator_traits.hpp> + +#ifdef BOOST_CONTAINER_PERFECT_FORWARDING +#include <boost/container/detail/variadic_templates_tools.hpp> +#include <boost/container/detail/stored_ref.hpp> +#else +#include <boost/container/detail/preprocessor.hpp> +#endif + +#include <iterator> + +namespace boost { +namespace container { + +template <class T, class Difference = std::ptrdiff_t> +class constant_iterator + : public std::iterator + <std::random_access_iterator_tag, T, Difference, const T*, const T &> +{ + typedef constant_iterator<T, Difference> this_type; + + public: + explicit constant_iterator(const T &ref, Difference range_size) + : m_ptr(&ref), m_num(range_size){} + + //Constructors + constant_iterator() + : m_ptr(0), m_num(0){} + + constant_iterator& operator++() + { increment(); return *this; } + + constant_iterator operator++(int) + { + constant_iterator result (*this); + increment(); + return result; + } + + constant_iterator& operator--() + { decrement(); return *this; } + + constant_iterator operator--(int) + { + constant_iterator result (*this); + decrement(); + return result; + } + + friend bool operator== (const constant_iterator& i, const constant_iterator& i2) + { return i.equal(i2); } + + friend bool operator!= (const constant_iterator& i, const constant_iterator& i2) + { return !(i == i2); } + + friend bool operator< (const constant_iterator& i, const constant_iterator& i2) + { return i.less(i2); } + + friend bool operator> (const constant_iterator& i, const constant_iterator& i2) + { return i2 < i; } + + friend bool operator<= (const constant_iterator& i, const constant_iterator& i2) + { return !(i > i2); } + + friend bool operator>= (const constant_iterator& i, const constant_iterator& i2) + { return !(i < i2); } + + friend Difference operator- (const constant_iterator& i, const constant_iterator& i2) + { return i2.distance_to(i); } + + //Arithmetic + constant_iterator& operator+=(Difference off) + { this->advance(off); return *this; } + + constant_iterator operator+(Difference off) const + { + constant_iterator other(*this); + other.advance(off); + return other; + } + + friend constant_iterator operator+(Difference off, const constant_iterator& right) + { return right + off; } + + constant_iterator& operator-=(Difference off) + { this->advance(-off); return *this; } + + constant_iterator operator-(Difference off) const + { return *this + (-off); } + + const T& operator*() const + { return dereference(); } + + const T& operator[] (Difference n) const + { return dereference(); } + + const T* operator->() const + { return &(dereference()); } + + private: + const T * m_ptr; + Difference m_num; + + void increment() + { --m_num; } + + void decrement() + { ++m_num; } + + bool equal(const this_type &other) const + { return m_num == other.m_num; } + + bool less(const this_type &other) const + { return other.m_num < m_num; } + + const T & dereference() const + { return *m_ptr; } + + void advance(Difference n) + { m_num -= n; } + + Difference distance_to(const this_type &other)const + { return m_num - other.m_num; } +}; + +template <class T, class Difference = std::ptrdiff_t> +class default_construct_iterator + : public std::iterator + <std::random_access_iterator_tag, T, Difference, const T*, const T &> +{ + typedef default_construct_iterator<T, Difference> this_type; + + public: + explicit default_construct_iterator(Difference range_size) + : m_num(range_size){} + + //Constructors + default_construct_iterator() + : m_num(0){} + + default_construct_iterator& operator++() + { increment(); return *this; } + + default_construct_iterator operator++(int) + { + default_construct_iterator result (*this); + increment(); + return result; + } + + default_construct_iterator& operator--() + { decrement(); return *this; } + + default_construct_iterator operator--(int) + { + default_construct_iterator result (*this); + decrement(); + return result; + } + + friend bool operator== (const default_construct_iterator& i, const default_construct_iterator& i2) + { return i.equal(i2); } + + friend bool operator!= (const default_construct_iterator& i, const default_construct_iterator& i2) + { return !(i == i2); } + + friend bool operator< (const default_construct_iterator& i, const default_construct_iterator& i2) + { return i.less(i2); } + + friend bool operator> (const default_construct_iterator& i, const default_construct_iterator& i2) + { return i2 < i; } + + friend bool operator<= (const default_construct_iterator& i, const default_construct_iterator& i2) + { return !(i > i2); } + + friend bool operator>= (const default_construct_iterator& i, const default_construct_iterator& i2) + { return !(i < i2); } + + friend Difference operator- (const default_construct_iterator& i, const default_construct_iterator& i2) + { return i2.distance_to(i); } + + //Arithmetic + default_construct_iterator& operator+=(Difference off) + { this->advance(off); return *this; } + + default_construct_iterator operator+(Difference off) const + { + default_construct_iterator other(*this); + other.advance(off); + return other; + } + + friend default_construct_iterator operator+(Difference off, const default_construct_iterator& right) + { return right + off; } + + default_construct_iterator& operator-=(Difference off) + { this->advance(-off); return *this; } + + default_construct_iterator operator-(Difference off) const + { return *this + (-off); } + + const T& operator*() const + { return dereference(); } + + const T* operator->() const + { return &(dereference()); } + + const T& operator[] (Difference n) const + { return dereference(); } + + private: + Difference m_num; + + void increment() + { --m_num; } + + void decrement() + { ++m_num; } + + bool equal(const this_type &other) const + { return m_num == other.m_num; } + + bool less(const this_type &other) const + { return other.m_num < m_num; } + + const T & dereference() const + { + static T dummy; + return dummy; + } + + void advance(Difference n) + { m_num -= n; } + + Difference distance_to(const this_type &other)const + { return m_num - other.m_num; } +}; + +template <class T, class Difference = std::ptrdiff_t> +class repeat_iterator + : public std::iterator + <std::random_access_iterator_tag, T, Difference> +{ + typedef repeat_iterator<T, Difference> this_type; + public: + explicit repeat_iterator(T &ref, Difference range_size) + : m_ptr(&ref), m_num(range_size){} + + //Constructors + repeat_iterator() + : m_ptr(0), m_num(0){} + + this_type& operator++() + { increment(); return *this; } + + this_type operator++(int) + { + this_type result (*this); + increment(); + return result; + } + + this_type& operator--() + { increment(); return *this; } + + this_type operator--(int) + { + this_type result (*this); + increment(); + return result; + } + + friend bool operator== (const this_type& i, const this_type& i2) + { return i.equal(i2); } + + friend bool operator!= (const this_type& i, const this_type& i2) + { return !(i == i2); } + + friend bool operator< (const this_type& i, const this_type& i2) + { return i.less(i2); } + + friend bool operator> (const this_type& i, const this_type& i2) + { return i2 < i; } + + friend bool operator<= (const this_type& i, const this_type& i2) + { return !(i > i2); } + + friend bool operator>= (const this_type& i, const this_type& i2) + { return !(i < i2); } + + friend Difference operator- (const this_type& i, const this_type& i2) + { return i2.distance_to(i); } + + //Arithmetic + this_type& operator+=(Difference off) + { this->advance(off); return *this; } + + this_type operator+(Difference off) const + { + this_type other(*this); + other.advance(off); + return other; + } + + friend this_type operator+(Difference off, const this_type& right) + { return right + off; } + + this_type& operator-=(Difference off) + { this->advance(-off); return *this; } + + this_type operator-(Difference off) const + { return *this + (-off); } + + T& operator*() const + { return dereference(); } + + T& operator[] (Difference n) const + { return dereference(); } + + T *operator->() const + { return &(dereference()); } + + private: + T * m_ptr; + Difference m_num; + + void increment() + { --m_num; } + + void decrement() + { ++m_num; } + + bool equal(const this_type &other) const + { return m_num == other.m_num; } + + bool less(const this_type &other) const + { return other.m_num < m_num; } + + T & dereference() const + { return *m_ptr; } + + void advance(Difference n) + { m_num -= n; } + + Difference distance_to(const this_type &other)const + { return m_num - other.m_num; } +}; + +template <class T, class EmplaceFunctor, class Difference /*= std::ptrdiff_t*/> +class emplace_iterator + : public std::iterator + <std::random_access_iterator_tag, T, Difference, const T*, const T &> +{ + typedef emplace_iterator this_type; + + public: + typedef Difference difference_type; + explicit emplace_iterator(EmplaceFunctor&e) + : m_num(1), m_pe(&e){} + + emplace_iterator() + : m_num(0), m_pe(0){} + + this_type& operator++() + { increment(); return *this; } + + this_type operator++(int) + { + this_type result (*this); + increment(); + return result; + } + + this_type& operator--() + { decrement(); return *this; } + + this_type operator--(int) + { + this_type result (*this); + decrement(); + return result; + } + + friend bool operator== (const this_type& i, const this_type& i2) + { return i.equal(i2); } + + friend bool operator!= (const this_type& i, const this_type& i2) + { return !(i == i2); } + + friend bool operator< (const this_type& i, const this_type& i2) + { return i.less(i2); } + + friend bool operator> (const this_type& i, const this_type& i2) + { return i2 < i; } + + friend bool operator<= (const this_type& i, const this_type& i2) + { return !(i > i2); } + + friend bool operator>= (const this_type& i, const this_type& i2) + { return !(i < i2); } + + friend difference_type operator- (const this_type& i, const this_type& i2) + { return i2.distance_to(i); } + + //Arithmetic + this_type& operator+=(difference_type off) + { this->advance(off); return *this; } + + this_type operator+(difference_type off) const + { + this_type other(*this); + other.advance(off); + return other; + } + + friend this_type operator+(difference_type off, const this_type& right) + { return right + off; } + + this_type& operator-=(difference_type off) + { this->advance(-off); return *this; } + + this_type operator-(difference_type off) const + { return *this + (-off); } + + const T& operator*() const + { return dereference(); } + + const T& operator[](difference_type) const + { return dereference(); } + + const T* operator->() const + { return &(dereference()); } + + template<class A> + void construct_in_place(A &a, T* ptr) + { (*m_pe)(a, ptr); } + + private: + difference_type m_num; + EmplaceFunctor * m_pe; + + void increment() + { --m_num; } + + void decrement() + { ++m_num; } + + bool equal(const this_type &other) const + { return m_num == other.m_num; } + + bool less(const this_type &other) const + { return other.m_num < m_num; } + + const T & dereference() const + { + static T dummy; + return dummy; + } + + void advance(difference_type n) + { m_num -= n; } + + difference_type distance_to(const this_type &other)const + { return difference_type(m_num - other.m_num); } +}; + +#ifdef BOOST_CONTAINER_PERFECT_FORWARDING + +template<class ...Args> +struct emplace_functor +{ + typedef typename container_detail::build_number_seq<sizeof...(Args)>::type index_tuple_t; + + emplace_functor(Args&&... args) + : args_(args...) + {} + + template<class A, class T> + void operator()(A &a, T *ptr) + { emplace_functor::inplace_impl(a, ptr, index_tuple_t()); } + + template<class A, class T, int ...IdxPack> + void inplace_impl(A &a, T* ptr, const container_detail::index_tuple<IdxPack...>&) + { + allocator_traits<A>::construct + (a, ptr, container_detail::stored_ref<Args>::forward + (container_detail::get<IdxPack>(args_))...); + } + + container_detail::tuple<Args&...> args_; +}; + +#else + +#define BOOST_PP_LOCAL_MACRO(n) \ + BOOST_PP_EXPR_IF(n, template <) \ + BOOST_PP_ENUM_PARAMS(n, class P) \ + BOOST_PP_EXPR_IF(n, >) \ + struct BOOST_PP_CAT(BOOST_PP_CAT(emplace_functor, n), arg) \ + { \ + BOOST_PP_CAT(BOOST_PP_CAT(emplace_functor, n), arg) \ + ( BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _) ) \ + BOOST_PP_EXPR_IF(n, :) BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_INIT, _){} \ + \ + template<class A, class T> \ + void operator()(A &a, T *ptr) \ + { \ + allocator_traits<A>::construct \ + (a, ptr BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_MEMBER_FORWARD, _) );\ + } \ + BOOST_PP_REPEAT(n, BOOST_CONTAINER_PP_PARAM_DEFINE, _) \ + }; \ + //! +#define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS) +#include BOOST_PP_LOCAL_ITERATE() + +#endif + +} //namespace container { +} //namespace boost { + +#include <boost/container/detail/config_end.hpp> + +#endif //#ifndef BOOST_CONTAINER_DETAIL_ITERATORS_HPP + diff --git a/boost/container/detail/math_functions.hpp b/boost/container/detail/math_functions.hpp new file mode 100644 index 0000000000..4613573d48 --- /dev/null +++ b/boost/container/detail/math_functions.hpp @@ -0,0 +1,113 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Stephen Cleary 2000. +// (C) Copyright Ion Gaztanaga 2007-2011. +// +// 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. +// +// This file is a slightly modified file from Boost.Pool +// +////////////////////////////////////////////////////////////////////////////// + +#ifndef BOOST_CONTAINER_DETAIL_MATH_FUNCTIONS_HPP +#define BOOST_CONTAINER_DETAIL_MATH_FUNCTIONS_HPP + +#include "config_begin.hpp" +#include <climits> +#include <boost/static_assert.hpp> + +namespace boost { +namespace container { +namespace container_detail { + +// Greatest common divisor and least common multiple + +// +// gcd is an algorithm that calculates the greatest common divisor of two +// integers, using Euclid's algorithm. +// +// Pre: A > 0 && B > 0 +// Recommended: A > B +template <typename Integer> +inline Integer gcd(Integer A, Integer B) +{ + do + { + const Integer tmp(B); + B = A % B; + A = tmp; + } while (B != 0); + + return A; +} + +// +// lcm is an algorithm that calculates the least common multiple of two +// integers. +// +// Pre: A > 0 && B > 0 +// Recommended: A > B +template <typename Integer> +inline Integer lcm(const Integer & A, const Integer & B) +{ + Integer ret = A; + ret /= gcd(A, B); + ret *= B; + return ret; +} + +template <typename Integer> +inline Integer log2_ceil(const Integer & A) +{ + Integer i = 0; + Integer power_of_2 = 1; + + while(power_of_2 < A){ + power_of_2 <<= 1; + ++i; + } + return i; +} + +template <typename Integer> +inline Integer upper_power_of_2(const Integer & A) +{ + Integer power_of_2 = 1; + + while(power_of_2 < A){ + power_of_2 <<= 1; + } + return power_of_2; +} + +//This function uses binary search to discover the +//highest set bit of the integer +inline std::size_t floor_log2 (std::size_t x) +{ + const std::size_t Bits = sizeof(std::size_t)*CHAR_BIT; + const bool Size_t_Bits_Power_2= !(Bits & (Bits-1)); + BOOST_STATIC_ASSERT(((Size_t_Bits_Power_2)== true)); + + std::size_t n = x; + std::size_t log2 = 0; + + for(std::size_t shift = Bits >> 1; shift; shift >>= 1){ + std::size_t tmp = n >> shift; + if (tmp) + log2 += shift, n = tmp; + } + + return log2; +} + +} // namespace container_detail +} // namespace container +} // namespace boost + +#include <boost/container/detail/config_end.hpp> + +#endif diff --git a/boost/container/detail/mpl.hpp b/boost/container/detail/mpl.hpp new file mode 100644 index 0000000000..c2d0ce41bb --- /dev/null +++ b/boost/container/detail/mpl.hpp @@ -0,0 +1,160 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2005-2011. +// +// 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_CONTAINER_DETAIL_MPL_HPP +#define BOOST_CONTAINER_CONTAINER_DETAIL_MPL_HPP + +#if (defined _MSC_VER) && (_MSC_VER >= 1200) +# pragma once +#endif + +#include <cstddef> + +namespace boost { +namespace container { +namespace container_detail { + +template <class T, T val> +struct integral_constant +{ + static const T value = val; + typedef integral_constant<T,val> type; +}; + +template< bool C_ > +struct bool_ : integral_constant<bool, C_> +{ + static const bool value = C_; + operator bool() const { return bool_::value; } +}; + +typedef bool_<true> true_; +typedef bool_<false> false_; + +typedef true_ true_type; +typedef false_ false_type; + +typedef char yes_type; +struct no_type +{ + char padding[8]; +}; + +template <bool B, class T = void> +struct enable_if_c { + typedef T type; +}; + +template <class T> +struct enable_if_c<false, T> {}; + +template <class Cond, class T = void> +struct enable_if : public enable_if_c<Cond::value, T> {}; + +template <class Cond, class T = void> +struct disable_if : public enable_if_c<!Cond::value, T> {}; + +template <bool B, class T = void> +struct disable_if_c : public enable_if_c<!B, T> {}; + +template <class T, class U> +class is_convertible +{ + typedef char true_t; + class false_t { char dummy[2]; }; + static true_t dispatch(U); + static false_t dispatch(...); + static T trigger(); + public: + enum { value = sizeof(dispatch(trigger())) == sizeof(true_t) }; +}; + +template< + bool C + , typename T1 + , typename T2 + > +struct if_c +{ + typedef T1 type; +}; + +template< + typename T1 + , typename T2 + > +struct if_c<false,T1,T2> +{ + typedef T2 type; +}; + +template< + typename T1 + , typename T2 + , typename T3 + > +struct if_ +{ + typedef typename if_c<0 != T1::value, T2, T3>::type type; +}; + + +template <class Pair> +struct select1st +// : public std::unary_function<Pair, typename Pair::first_type> +{ + template<class OtherPair> + const typename Pair::first_type& operator()(const OtherPair& x) const + { return x.first; } + + const typename Pair::first_type& operator()(const typename Pair::first_type& x) const + { return x; } +}; + +// identity is an extension: it is not part of the standard. +template <class T> +struct identity +// : public std::unary_function<T,T> +{ + typedef T type; + const T& operator()(const T& x) const + { return x; } +}; + +template<std::size_t S> +struct ls_zeros +{ + static const std::size_t value = (S & std::size_t(1)) ? 0 : (1u + ls_zeros<(S >> 1u)>::value); +}; + +template<> +struct ls_zeros<0> +{ + static const std::size_t value = 0; +}; + +template<> +struct ls_zeros<1> +{ + static const std::size_t value = 0; +}; + +template <typename T> struct unvoid { typedef T type; }; +template <> struct unvoid<void> { struct type { }; }; +template <> struct unvoid<const void> { struct type { }; }; + +} //namespace container_detail { +} //namespace container { +} //namespace boost { + +#endif //#ifndef BOOST_CONTAINER_CONTAINER_DETAIL_MPL_HPP + diff --git a/boost/container/detail/multiallocation_chain.hpp b/boost/container/detail/multiallocation_chain.hpp new file mode 100644 index 0000000000..a67fd770bd --- /dev/null +++ b/boost/container/detail/multiallocation_chain.hpp @@ -0,0 +1,254 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2005-2011. 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_MULTIALLOCATION_CHAIN_HPP +#define BOOST_CONTAINER_DETAIL_MULTIALLOCATION_CHAIN_HPP + +#include "config_begin.hpp" +#include <boost/container/container_fwd.hpp> +#include <boost/container/detail/utilities.hpp> +#include <boost/container/detail/type_traits.hpp> +#include <boost/container/detail/transform_iterator.hpp> +#include <boost/intrusive/slist.hpp> +#include <boost/intrusive/pointer_traits.hpp> +#include <boost/type_traits/make_unsigned.hpp> +#include <boost/move/move.hpp> + +namespace boost { +namespace container { +namespace container_detail { + +template<class VoidPointer> +class basic_multiallocation_chain +{ + private: + typedef bi::slist_base_hook<bi::void_pointer<VoidPointer> + ,bi::link_mode<bi::normal_link> + > node; + + typedef typename boost::intrusive::pointer_traits + <VoidPointer>::template rebind_pointer<char>::type char_ptr; + typedef typename boost::intrusive:: + pointer_traits<char_ptr>::difference_type difference_type; + + typedef bi::slist< node + , bi::linear<true> + , bi::cache_last<true> + , bi::size_type<typename boost::make_unsigned<difference_type>::type> + > slist_impl_t; + slist_impl_t slist_impl_; + + static node & to_node(VoidPointer p) + { return *static_cast<node*>(static_cast<void*>(container_detail::to_raw_pointer(p))); } + + BOOST_MOVABLE_BUT_NOT_COPYABLE(basic_multiallocation_chain) + + public: + + + typedef VoidPointer void_pointer; + typedef typename slist_impl_t::iterator iterator; + typedef typename slist_impl_t::size_type size_type; + + basic_multiallocation_chain() + : slist_impl_() + {} + + basic_multiallocation_chain(BOOST_RV_REF(basic_multiallocation_chain) other) + : slist_impl_() + { slist_impl_.swap(other.slist_impl_); } + + basic_multiallocation_chain& operator=(BOOST_RV_REF(basic_multiallocation_chain) other) + { + basic_multiallocation_chain tmp(boost::move(other)); + this->swap(tmp); + return *this; + } + + bool empty() const + { return slist_impl_.empty(); } + + size_type size() const + { return slist_impl_.size(); } + + iterator before_begin() + { return slist_impl_.before_begin(); } + + iterator begin() + { return slist_impl_.begin(); } + + iterator end() + { return slist_impl_.end(); } + + iterator last() + { return slist_impl_.last(); } + + void clear() + { slist_impl_.clear(); } + + iterator insert_after(iterator it, void_pointer m) + { return slist_impl_.insert_after(it, to_node(m)); } + + void push_front(void_pointer m) + { return slist_impl_.push_front(to_node(m)); } + + void push_back(void_pointer m) + { return slist_impl_.push_back(to_node(m)); } + + void pop_front() + { return slist_impl_.pop_front(); } + + void *front() + { return &*slist_impl_.begin(); } + + void splice_after(iterator after_this, basic_multiallocation_chain &x, iterator before_begin, iterator before_end) + { slist_impl_.splice_after(after_this, x.slist_impl_, before_begin, before_end); } + + void splice_after(iterator after_this, basic_multiallocation_chain &x, iterator before_begin, iterator before_end, size_type n) + { slist_impl_.splice_after(after_this, x.slist_impl_, before_begin, before_end, n); } + + void splice_after(iterator after_this, basic_multiallocation_chain &x) + { slist_impl_.splice_after(after_this, x.slist_impl_); } + + void incorporate_after(iterator after_this, void_pointer begin , iterator before_end) + { slist_impl_.incorporate_after(after_this, &to_node(begin), &to_node(before_end)); } + + void incorporate_after(iterator after_this, void_pointer begin, void_pointer before_end, size_type n) + { slist_impl_.incorporate_after(after_this, &to_node(begin), &to_node(before_end), n); } + + void swap(basic_multiallocation_chain &x) + { slist_impl_.swap(x.slist_impl_); } + + static iterator iterator_to(void_pointer p) + { return slist_impl_t::s_iterator_to(to_node(p)); } + + std::pair<void_pointer, void_pointer> extract_data() + { + std::pair<void_pointer, void_pointer> ret + (slist_impl_.begin().operator->() + ,slist_impl_.last().operator->()); + slist_impl_.clear(); + return ret; + } +}; + +template<class T> +struct cast_functor +{ + typedef typename container_detail::add_reference<T>::type result_type; + template<class U> + result_type operator()(U &ptr) const + { return *static_cast<T*>(static_cast<void*>(&ptr)); } +}; + +template<class MultiallocationChain, class T> +class transform_multiallocation_chain +{ + private: + BOOST_MOVABLE_BUT_NOT_COPYABLE(transform_multiallocation_chain) + + MultiallocationChain holder_; + typedef typename MultiallocationChain::void_pointer void_pointer; + typedef typename boost::intrusive::pointer_traits + <void_pointer>::template rebind_pointer<T>::type pointer; + + static pointer cast(void_pointer p) + { + return pointer(static_cast<T*>(container_detail::to_raw_pointer(p))); + } + + public: + typedef transform_iterator + < typename MultiallocationChain::iterator + , container_detail::cast_functor <T> > iterator; + typedef typename MultiallocationChain::size_type size_type; + + transform_multiallocation_chain() + : holder_() + {} + + transform_multiallocation_chain(BOOST_RV_REF(transform_multiallocation_chain) other) + : holder_() + { this->swap(other); } + + transform_multiallocation_chain(BOOST_RV_REF(MultiallocationChain) other) + : holder_(boost::move(other)) + {} + + transform_multiallocation_chain& operator=(BOOST_RV_REF(transform_multiallocation_chain) other) + { + transform_multiallocation_chain tmp(boost::move(other)); + this->swap(tmp); + return *this; + } + + void push_front(pointer mem) + { holder_.push_front(mem); } + + void swap(transform_multiallocation_chain &other_chain) + { holder_.swap(other_chain.holder_); } + + void splice_after(iterator after_this, transform_multiallocation_chain &x, iterator before_begin, iterator before_end, size_type n) + { holder_.splice_after(after_this.base(), x.holder_, before_begin.base(), before_end.base(), n); } + + void incorporate_after(iterator after_this, void_pointer begin, void_pointer before_end, size_type n) + { holder_.incorporate_after(after_this.base(), begin, before_end, n); } + + void pop_front() + { holder_.pop_front(); } + + pointer front() + { return cast(holder_.front()); } + + bool empty() const + { return holder_.empty(); } + + iterator before_begin() + { return iterator(holder_.before_begin()); } + + iterator begin() + { return iterator(holder_.begin()); } + + iterator end() + { return iterator(holder_.end()); } + + iterator last() + { return iterator(holder_.last()); } + + size_type size() const + { return holder_.size(); } + + void clear() + { holder_.clear(); } + + iterator insert_after(iterator it, pointer m) + { return iterator(holder_.insert_after(it.base(), m)); } + + static iterator iterator_to(pointer p) + { return iterator(MultiallocationChain::iterator_to(p)); } + + std::pair<void_pointer, void_pointer> extract_data() + { return holder_.extract_data(); } + + MultiallocationChain extract_multiallocation_chain() + { + return MultiallocationChain(boost::move(holder_)); + } +}; + +}}} + +// namespace container_detail { +// namespace container { +// namespace boost { + +#include <boost/container/detail/config_end.hpp> + +#endif //BOOST_CONTAINER_DETAIL_MULTIALLOCATION_CHAIN_HPP diff --git a/boost/container/detail/node_alloc_holder.hpp b/boost/container/detail/node_alloc_holder.hpp new file mode 100644 index 0000000000..9b0a0a524b --- /dev/null +++ b/boost/container/detail/node_alloc_holder.hpp @@ -0,0 +1,488 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2005-2011. 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_ + +#if (defined _MSC_VER) && (_MSC_VER >= 1200) +# pragma once +#endif + +#include "config_begin.hpp" +#include <boost/container/detail/workaround.hpp> + +#include <utility> +#include <functional> + +#include <boost/move/move.hpp> +#include <boost/intrusive/options.hpp> + +#include <boost/container/detail/version_type.hpp> +#include <boost/container/detail/type_traits.hpp> +#include <boost/container/detail/utilities.hpp> +#include <boost/container/allocator/allocator_traits.hpp> +#include <boost/container/detail/mpl.hpp> +#include <boost/container/detail/destroyers.hpp> + +#ifndef BOOST_CONTAINER_PERFECT_FORWARDING +#include <boost/container/detail/preprocessor.hpp> +#endif + +#include <boost/container/detail/algorithms.hpp> + + +namespace boost { +namespace container { +namespace container_detail { + +//!A deleter for scoped_ptr that deallocates the memory +//!allocated for an object using a STL allocator. +template <class A> +struct scoped_deallocator +{ + typedef allocator_traits<A> allocator_traits_type; + typedef typename allocator_traits_type::pointer pointer; + typedef container_detail::integral_constant<unsigned, + boost::container::container_detail:: + version<A>::value> alloc_version; + typedef container_detail::integral_constant<unsigned, 1> allocator_v1; + typedef container_detail::integral_constant<unsigned, 2> allocator_v2; + + private: + void priv_deallocate(allocator_v1) + { m_alloc.deallocate(m_ptr, 1); } + + void priv_deallocate(allocator_v2) + { m_alloc.deallocate_one(m_ptr); } + + BOOST_MOVABLE_BUT_NOT_COPYABLE(scoped_deallocator) + + public: + + pointer m_ptr; + A& m_alloc; + + scoped_deallocator(pointer p, A& a) + : m_ptr(p), m_alloc(a) + {} + + ~scoped_deallocator() + { if (m_ptr)priv_deallocate(alloc_version()); } + + scoped_deallocator(BOOST_RV_REF(scoped_deallocator) o) + : m_ptr(o.m_ptr), m_alloc(o.m_alloc) + { o.release(); } + + pointer get() const + { return m_ptr; } + + void release() + { m_ptr = 0; } +}; + +template <class A> +class allocator_destroyer_and_chain_builder +{ + typedef allocator_traits<A> allocator_traits_type; + typedef typename allocator_traits_type::value_type value_type; + typedef typename A::multiallocation_chain multiallocation_chain; + + A & a_; + multiallocation_chain &c_; + + public: + allocator_destroyer_and_chain_builder(A &a, multiallocation_chain &c) + : a_(a), c_(c) + {} + + void operator()(const typename A::pointer &p) + { + allocator_traits<A>::destroy(a_, container_detail::to_raw_pointer(p)); + c_.push_front(p); + } +}; + +template <class A> +class allocator_multialloc_chain_node_deallocator +{ + typedef allocator_traits<A> allocator_traits_type; + typedef typename allocator_traits_type::value_type value_type; + typedef typename A::multiallocation_chain multiallocation_chain; + typedef allocator_destroyer_and_chain_builder<A> chain_builder; + + A & a_; + multiallocation_chain c_; + + public: + allocator_multialloc_chain_node_deallocator(A &a) + : a_(a), c_() + {} + + chain_builder get_chain_builder() + { return chain_builder(a_, c_); } + + ~allocator_multialloc_chain_node_deallocator() + { + if(!c_.empty()) + a_.deallocate_individual(boost::move(c_)); + } +}; + +template<class ValueCompare, class Node> +struct node_compare + : private ValueCompare +{ + typedef typename ValueCompare::key_type key_type; + typedef typename ValueCompare::value_type value_type; + typedef typename ValueCompare::key_of_value key_of_value; + + node_compare(const ValueCompare &pred) + : ValueCompare(pred) + {} + + ValueCompare &value_comp() + { return static_cast<ValueCompare &>(*this); } + + ValueCompare &value_comp() const + { return static_cast<const ValueCompare &>(*this); } + + bool operator()(const Node &a, const Node &b) const + { return ValueCompare::operator()(a.get_data(), b.get_data()); } +}; + +template<class A, class ICont, class Pred = container_detail::nat> +struct node_alloc_holder +{ + typedef allocator_traits<A> allocator_traits_type; + typedef node_alloc_holder<A, ICont> self_t; + typedef typename allocator_traits_type::value_type value_type; + 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 A ValAlloc; + typedef typename node_allocator_traits_type::pointer NodePtr; + typedef container_detail::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 container_detail::integral_constant<unsigned, 1> allocator_v1; + typedef container_detail::integral_constant<unsigned, 2> allocator_v2; + typedef container_detail::integral_constant<unsigned, + boost::container::container_detail:: + 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; + + private: + BOOST_COPYABLE_AND_MOVABLE(node_alloc_holder) + + public: + + //Constructors for sequence containers + node_alloc_holder() + : members_() + {} + + explicit node_alloc_holder(const ValAlloc &a) + : members_(a) + {} + + explicit node_alloc_holder(const node_alloc_holder &x) + : members_(NodeAllocTraits::select_on_container_copy_construction(x.node_alloc())) + {} + + explicit node_alloc_holder(BOOST_RV_REF(node_alloc_holder) x) + : members_(boost::move(x.node_alloc())) + { this->icont().swap(x.icont()); } + + //Constructors for associative containers + explicit node_alloc_holder(const ValAlloc &a, const Pred &c) + : members_(a, c) + {} + + explicit node_alloc_holder(const node_alloc_holder &x, const Pred &c) + : members_(NodeAllocTraits::select_on_container_copy_construction(x.node_alloc()), c) + {} + + explicit node_alloc_holder(const Pred &c) + : members_(c) + {} + + //helpers for move assignments + explicit node_alloc_holder(BOOST_RV_REF(node_alloc_holder) x, const Pred &c) + : members_(boost::move(x.node_alloc()), c) + { this->icont().swap(x.icont()); } + + void copy_assign_alloc(const node_alloc_holder &x) + { + container_detail::bool_<allocator_traits_type::propagate_on_container_copy_assignment::value> flag; + container_detail::assign_alloc( static_cast<NodeAlloc &>(this->members_) + , static_cast<const NodeAlloc &>(x.members_), flag); + } + + void move_assign_alloc( node_alloc_holder &x) + { + container_detail::bool_<allocator_traits_type::propagate_on_container_move_assignment::value> flag; + container_detail::move_alloc( static_cast<NodeAlloc &>(this->members_) + , static_cast<NodeAlloc &>(x.members_), 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 this->allocate_one(alloc_version()); } + + NodePtr allocate_one(allocator_v1) + { return this->node_alloc().allocate(1); } + + NodePtr allocate_one(allocator_v2) + { return this->node_alloc().allocate_one(); } + + void deallocate_one(const NodePtr &p) + { return this->deallocate_one(p, alloc_version()); } + + void deallocate_one(const NodePtr &p, allocator_v1) + { this->node_alloc().deallocate(p, 1); } + + void deallocate_one(const NodePtr &p, allocator_v2) + { this->node_alloc().deallocate_one(p); } +/* + template<class A, class Convertible1, class Convertible2> + static void construct(A &a, const NodePtr &ptr, + BOOST_RV_REF_2_TEMPL_ARGS(std::pair, Convertible1, Convertible2) value) + { + typedef typename Node::hook_type hook_type; + typedef typename Node::value_type::first_type first_type; + typedef typename Node::value_type::second_type second_type; + Node *nodeptr = container_detail::to_raw_pointer(ptr); + + //Hook constructor does not throw + allocator_traits<A>::construct(a, static_cast<hook_type*>(nodeptr)); + + //Now construct pair members_holder + value_type *valueptr = &nodeptr->get_data(); + allocator_traits<A>::construct(a, &valueptr->first, boost::move(value.first)); + BOOST_TRY{ + allocator_traits<A>::construct(a, &valueptr->second, boost::move(value.second)); + } + BOOST_CATCH(...){ + allocator_traits<A>::destroy(a, &valueptr->first); + BOOST_RETHROW + } + BOOST_CATCH_END + } +*/ + #ifdef BOOST_CONTAINER_PERFECT_FORWARDING +/* + template<class A, class ...Args> + static void construct(A &a, const NodePtr &ptr, Args &&...args) + { + } +*/ + template<class ...Args> + NodePtr create_node(Args &&...args) + { + NodePtr p = this->allocate_one(); + Deallocator node_deallocator(p, this->node_alloc()); + allocator_traits<NodeAlloc>::construct + (this->node_alloc(), container_detail::to_raw_pointer(p), boost::forward<Args>(args)...); + node_deallocator.release(); + return (p); + } + + #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING + + #define BOOST_PP_LOCAL_MACRO(n) \ + \ + BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ + NodePtr create_node(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ + { \ + NodePtr p = this->allocate_one(); \ + Deallocator node_deallocator(p, this->node_alloc()); \ + allocator_traits<NodeAlloc>::construct \ + (this->node_alloc(), container_detail::to_raw_pointer(p) \ + BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)); \ + node_deallocator.release(); \ + return (p); \ + } \ + //! + #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS) + #include BOOST_PP_LOCAL_ITERATE() + + #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING + + template<class It> + NodePtr create_node_from_it(const It &it) + { + NodePtr p = this->allocate_one(); + Deallocator node_deallocator(p, this->node_alloc()); + ::boost::container::construct_in_place(this->node_alloc(), container_detail::to_raw_pointer(p), it); + node_deallocator.release(); + return (p); + } + + void destroy_node(const NodePtr &nodep) + { + allocator_traits<NodeAlloc>::destroy(this->node_alloc(), container_detail::to_raw_pointer(nodep)); + this->deallocate_one(nodep); + } + + void swap(node_alloc_holder &x) + { + this->icont().swap(x.icont()); + container_detail::bool_<allocator_traits_type::propagate_on_container_swap::value> flag; + container_detail::swap_alloc(this->node_alloc(), x.node_alloc(), flag); + } + + template<class FwdIterator, class Inserter> + FwdIterator allocate_many_and_construct + (FwdIterator beg, difference_type n, Inserter inserter) + { + if(n){ + typedef typename NodeAlloc::multiallocation_chain multiallocation_chain; + + //Try to allocate memory in a single block + multiallocation_chain mem(this->node_alloc().allocate_individual(n)); + int constructed = 0; + Node *p = 0; + BOOST_TRY{ + for(difference_type i = 0; i < n; ++i, ++beg, --constructed){ + p = container_detail::to_raw_pointer(mem.front()); + mem.pop_front(); + //This can throw + constructed = 0; + boost::container::construct_in_place(this->node_alloc(), p, beg); + ++constructed; + //This can throw in some containers (predicate might throw) + inserter(*p); + } + } + BOOST_CATCH(...){ + if(constructed){ + allocator_traits<NodeAlloc>::destroy(this->node_alloc(), container_detail::to_raw_pointer(p)); + } + this->node_alloc().deallocate_individual(boost::move(mem)); + BOOST_RETHROW + } + BOOST_CATCH_END + } + return beg; + } + + void clear(allocator_v1) + { this->icont().clear_and_dispose(Destroyer(this->node_alloc())); } + + void clear(allocator_v2) + { + 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(boost::move(chain)); + } + + icont_iterator erase_range(const icont_iterator &first, const icont_iterator &last, allocator_v1) + { return this->icont().erase_and_dispose(first, last, Destroyer(this->node_alloc())); } + + icont_iterator erase_range(const icont_iterator &first, const icont_iterator &last, allocator_v2) + { + allocator_multialloc_chain_node_deallocator<NodeAlloc> chain_holder(this->node_alloc()); + return this->icont().erase_and_dispose(first, last, chain_holder.get_chain_builder()); + } + + template<class Key, class Comparator> + size_type erase_key(const Key& k, const Comparator &comp, allocator_v1) + { 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, allocator_v2) + { + 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 + { + cloner(node_alloc_holder &holder) + : m_holder(holder) + {} + + NodePtr operator()(const Node &other) const + { return m_holder.create_node(other.get_data()); } + + node_alloc_holder &m_holder; + }; + + struct members_holder + : public NodeAlloc + { + private: + members_holder(const members_holder&); + members_holder & operator=(const members_holder&); + + public: + members_holder() + : NodeAlloc(), m_icont() + {} + + template<class ConvertibleToAlloc> + explicit members_holder(BOOST_FWD_REF(ConvertibleToAlloc) c2alloc) + : NodeAlloc(boost::forward<ConvertibleToAlloc>(c2alloc)) + , m_icont() + {} + + template<class ConvertibleToAlloc> + members_holder(BOOST_FWD_REF(ConvertibleToAlloc) c2alloc, const Pred &c) + : NodeAlloc(boost::forward<ConvertibleToAlloc>(c2alloc)) + , m_icont(typename ICont::value_compare(c)) + {} + + explicit members_holder(const Pred &c) + : NodeAlloc() + , m_icont(typename ICont::value_compare(c)) + {} + + //The intrusive container + ICont m_icont; + }; + + ICont &non_const_icont() const + { return const_cast<ICont&>(this->members_.m_icont); } + + ICont &icont() + { return this->members_.m_icont; } + + const ICont &icont() const + { return this->members_.m_icont; } + + NodeAlloc &node_alloc() + { return static_cast<NodeAlloc &>(this->members_); } + + const NodeAlloc &node_alloc() const + { return static_cast<const NodeAlloc &>(this->members_); } + + members_holder members_; +}; + +} //namespace container_detail { +} //namespace container { +} //namespace boost { + +#include <boost/container/detail/config_end.hpp> + +#endif // BOOST_CONTAINER_DETAIL_NODE_ALLOC_HPP_ diff --git a/boost/container/detail/node_pool_impl.hpp b/boost/container/detail/node_pool_impl.hpp new file mode 100644 index 0000000000..9ee9e311c0 --- /dev/null +++ b/boost/container/detail/node_pool_impl.hpp @@ -0,0 +1,367 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2005-2011. 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_POOL_IMPL_HPP +#define BOOST_CONTAINER_DETAIL_NODE_POOL_IMPL_HPP + +#if (defined _MSC_VER) && (_MSC_VER >= 1200) +# pragma once +#endif + +#include "config_begin.hpp" +#include <boost/container/container_fwd.hpp> +#include <boost/container/detail/workaround.hpp> +#include <boost/container/detail/utilities.hpp> +#include <boost/intrusive/pointer_traits.hpp> +#include <boost/intrusive/set.hpp> +#include <boost/intrusive/slist.hpp> +#include <boost/container/detail/type_traits.hpp> +#include <boost/container/detail/math_functions.hpp> +#include <boost/container/detail/mpl.hpp> +#include <boost/container/detail/pool_common.hpp> +#include <boost/assert.hpp> +#include <cstddef> +#include <functional> //std::unary_function + +namespace boost { +namespace container { +namespace container_detail { + +template<class SegmentManagerBase> +class private_node_pool_impl +{ + //Non-copyable + private_node_pool_impl(); + private_node_pool_impl(const private_node_pool_impl &); + private_node_pool_impl &operator=(const private_node_pool_impl &); + + //A node object will hold node_t when it's not allocated + public: + typedef typename SegmentManagerBase::void_pointer void_pointer; + typedef typename node_slist<void_pointer>::slist_hook_t slist_hook_t; + typedef typename node_slist<void_pointer>::node_t node_t; + typedef typename node_slist<void_pointer>::node_slist_t free_nodes_t; + typedef typename SegmentManagerBase::multiallocation_chain multiallocation_chain; + typedef typename SegmentManagerBase::size_type size_type; + + private: + typedef typename bi::make_slist + < node_t, bi::base_hook<slist_hook_t> + , bi::linear<true> + , bi::constant_time_size<false> >::type blockslist_t; + public: + + //!Segment manager typedef + typedef SegmentManagerBase segment_manager_base_type; + + //!Constructor from a segment manager. Never throws + private_node_pool_impl(segment_manager_base_type *segment_mngr_base, size_type node_size, size_type nodes_per_block) + : m_nodes_per_block(nodes_per_block) + , m_real_node_size(lcm(node_size, size_type(alignment_of<node_t>::value))) + //General purpose allocator + , mp_segment_mngr_base(segment_mngr_base) + , m_blocklist() + , m_freelist() + //Debug node count + , m_allocated(0) + {} + + //!Destructor. Deallocates all allocated blocks. Never throws + ~private_node_pool_impl() + { this->purge_blocks(); } + + size_type get_real_num_node() const + { return m_nodes_per_block; } + + //!Returns the segment manager. Never throws + segment_manager_base_type* get_segment_manager_base()const + { return container_detail::to_raw_pointer(mp_segment_mngr_base); } + + void *allocate_node() + { return priv_alloc_node(); } + + //!Deallocates an array pointed by ptr. Never throws + void deallocate_node(void *ptr) + { priv_dealloc_node(ptr); } + + //!Allocates a singly linked list of n nodes ending in null pointer. + multiallocation_chain allocate_nodes(const size_type n) + { + //Preallocate all needed blocks to fulfill the request + size_type cur_nodes = m_freelist.size(); + if(cur_nodes < n){ + priv_alloc_block(((n - cur_nodes) - 1)/m_nodes_per_block + 1); + } + + //We just iterate the needed nodes to get the last we'll erase + typedef typename free_nodes_t::iterator free_iterator; + free_iterator before_last_new_it = m_freelist.before_begin(); + for(size_type j = 0; j != n; ++j){ + ++before_last_new_it; + } + + //Cache the first node of the allocated range before erasing + free_iterator first_node(m_freelist.begin()); + free_iterator last_node (before_last_new_it); + + //Erase the range. Since we already have the distance, this is O(1) + m_freelist.erase_after( m_freelist.before_begin() + , ++free_iterator(before_last_new_it) + , n); + + //Now take the last erased node and just splice it in the end + //of the intrusive list that will be traversed by the multialloc iterator. + multiallocation_chain chain; + chain.incorporate_after(chain.before_begin(), &*first_node, &*last_node, n); + m_allocated += n; + return boost::move(chain); + } + + void deallocate_nodes(multiallocation_chain chain) + { + typedef typename multiallocation_chain::iterator iterator; + iterator it(chain.begin()), itend(chain.end()); + while(it != itend){ + void *pElem = &*it; + ++it; + priv_dealloc_node(pElem); + } + } + + //!Deallocates all the free blocks of memory. Never throws + void deallocate_free_blocks() + { + typedef typename free_nodes_t::iterator nodelist_iterator; + typename blockslist_t::iterator bit(m_blocklist.before_begin()), + it(m_blocklist.begin()), + itend(m_blocklist.end()); + free_nodes_t backup_list; + nodelist_iterator backup_list_last = backup_list.before_begin(); + + //Execute the algorithm and get an iterator to the last value + size_type blocksize = get_rounded_size + (m_real_node_size*m_nodes_per_block, (size_type) alignment_of<node_t>::value); + + while(it != itend){ + //Collect all the nodes from the block pointed by it + //and push them in the list + free_nodes_t free_nodes; + nodelist_iterator last_it = free_nodes.before_begin(); + const void *addr = get_block_from_hook(&*it, blocksize); + + m_freelist.remove_and_dispose_if + (is_between(addr, blocksize), push_in_list(free_nodes, last_it)); + + //If the number of nodes is equal to m_nodes_per_block + //this means that the block can be deallocated + if(free_nodes.size() == m_nodes_per_block){ + //Unlink the nodes + free_nodes.clear(); + it = m_blocklist.erase_after(bit); + mp_segment_mngr_base->deallocate((void*)addr); + } + //Otherwise, insert them in the backup list, since the + //next "remove_if" does not need to check them again. + else{ + //Assign the iterator to the last value if necessary + if(backup_list.empty() && !m_freelist.empty()){ + backup_list_last = last_it; + } + //Transfer nodes. This is constant time. + backup_list.splice_after + ( backup_list.before_begin() + , free_nodes + , free_nodes.before_begin() + , last_it + , free_nodes.size()); + bit = it; + ++it; + } + } + //We should have removed all the nodes from the free list + BOOST_ASSERT(m_freelist.empty()); + + //Now pass all the node to the free list again + m_freelist.splice_after + ( m_freelist.before_begin() + , backup_list + , backup_list.before_begin() + , backup_list_last + , backup_list.size()); + } + + size_type num_free_nodes() + { return m_freelist.size(); } + + //!Deallocates all used memory. Precondition: all nodes allocated from this pool should + //!already be deallocated. Otherwise, undefined behaviour. Never throws + void purge_blocks() + { + //check for memory leaks + BOOST_ASSERT(m_allocated==0); + size_type blocksize = get_rounded_size + (m_real_node_size*m_nodes_per_block, (size_type)alignment_of<node_t>::value); + typename blockslist_t::iterator + it(m_blocklist.begin()), itend(m_blocklist.end()), aux; + + //We iterate though the NodeBlock list to free the memory + while(!m_blocklist.empty()){ + void *addr = get_block_from_hook(&m_blocklist.front(), blocksize); + m_blocklist.pop_front(); + mp_segment_mngr_base->deallocate((void*)addr); + } + //Just clear free node list + m_freelist.clear(); + } + + void swap(private_node_pool_impl &other) + { + BOOST_ASSERT(m_nodes_per_block == other.m_nodes_per_block); + BOOST_ASSERT(m_real_node_size == other.m_real_node_size); + std::swap(mp_segment_mngr_base, other.mp_segment_mngr_base); + m_blocklist.swap(other.m_blocklist); + m_freelist.swap(other.m_freelist); + std::swap(m_allocated, other.m_allocated); + } + + private: + + struct push_in_list + { + push_in_list(free_nodes_t &l, typename free_nodes_t::iterator &it) + : slist_(l), last_it_(it) + {} + + void operator()(typename free_nodes_t::pointer p) const + { + slist_.push_front(*p); + if(slist_.size() == 1){ //Cache last element + ++last_it_ = slist_.begin(); + } + } + + private: + free_nodes_t &slist_; + typename free_nodes_t::iterator &last_it_; + }; + + struct is_between + : std::unary_function<typename free_nodes_t::value_type, bool> + { + is_between(const void *addr, std::size_t size) + : beg_(static_cast<const char *>(addr)), end_(beg_+size) + {} + + bool operator()(typename free_nodes_t::const_reference v) const + { + return (beg_ <= reinterpret_cast<const char *>(&v) && + end_ > reinterpret_cast<const char *>(&v)); + } + private: + const char * beg_; + const char * end_; + }; + + //!Allocates one node, using single segregated storage algorithm. + //!Never throws + node_t *priv_alloc_node() + { + //If there are no free nodes we allocate a new block + if (m_freelist.empty()) + priv_alloc_block(); + //We take the first free node + node_t *n = (node_t*)&m_freelist.front(); + m_freelist.pop_front(); + ++m_allocated; + return n; + } + + //!Deallocates one node, using single segregated storage algorithm. + //!Never throws + void priv_dealloc_node(void *pElem) + { + //We put the node at the beginning of the free node list + node_t * to_deallocate = static_cast<node_t*>(pElem); + m_freelist.push_front(*to_deallocate); + BOOST_ASSERT(m_allocated>0); + --m_allocated; + } + + //!Allocates several blocks of nodes. Can throw + void priv_alloc_block(size_type num_blocks = 1) + { + if(!num_blocks) + return; + size_type blocksize = + get_rounded_size(m_real_node_size*m_nodes_per_block, (size_type)alignment_of<node_t>::value); + + try{ + for(size_type i = 0; i != num_blocks; ++i){ + //We allocate a new NodeBlock and put it as first + //element in the free Node list + char *pNode = reinterpret_cast<char*> + (mp_segment_mngr_base->allocate(blocksize + sizeof(node_t))); + char *pBlock = pNode; + m_blocklist.push_front(get_block_hook(pBlock, blocksize)); + + //We initialize all Nodes in Node Block to insert + //them in the free Node list + for(size_type i = 0; i < m_nodes_per_block; ++i, pNode += m_real_node_size){ + m_freelist.push_front(*new (pNode) node_t); + } + } + } + catch(...){ + //to-do: if possible, an efficient way to deallocate allocated blocks + throw; + } + } + + //!Deprecated, use deallocate_free_blocks + void deallocate_free_chunks() + { this->deallocate_free_blocks(); } + + //!Deprecated, use purge_blocks + void purge_chunks() + { this->purge_blocks(); } + + private: + //!Returns a reference to the block hook placed in the end of the block + static node_t & get_block_hook (void *block, size_type blocksize) + { + return *reinterpret_cast<node_t*>(reinterpret_cast<char*>(block) + blocksize); + } + + //!Returns the starting address of the block reference to the block hook placed in the end of the block + void *get_block_from_hook (node_t *hook, size_type blocksize) + { + return (reinterpret_cast<char*>(hook) - blocksize); + } + + private: + typedef typename boost::intrusive::pointer_traits + <void_pointer>::template rebind_pointer<segment_manager_base_type>::type segment_mngr_base_ptr_t; + + const size_type m_nodes_per_block; + const size_type m_real_node_size; + segment_mngr_base_ptr_t mp_segment_mngr_base; //Segment manager + blockslist_t m_blocklist; //Intrusive container of blocks + free_nodes_t m_freelist; //Intrusive container of free nods + size_type m_allocated; //Used nodes for debugging +}; + + +} //namespace container_detail { +} //namespace container { +} //namespace boost { + +#include <boost/container/detail/config_end.hpp> + +#endif //#ifndef BOOST_CONTAINER_DETAIL_ADAPTIVE_NODE_POOL_IMPL_HPP diff --git a/boost/container/detail/pair.hpp b/boost/container/detail/pair.hpp new file mode 100644 index 0000000000..1aeff91137 --- /dev/null +++ b/boost/container/detail/pair.hpp @@ -0,0 +1,320 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2005-2011. +// +// 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_CONTAINER_DETAIL_PAIR_HPP +#define BOOST_CONTAINER_CONTAINER_DETAIL_PAIR_HPP + +#if (defined _MSC_VER) && (_MSC_VER >= 1200) +# pragma once +#endif + +#include "config_begin.hpp" +#include <boost/container/detail/workaround.hpp> + +#include <boost/container/detail/mpl.hpp> +#include <boost/container/detail/type_traits.hpp> + +#include <utility> //std::pair + +#include <boost/move/move.hpp> +#include <boost/type_traits/is_class.hpp> + +#ifndef BOOST_CONTAINER_PERFECT_FORWARDING +#include <boost/container/detail/preprocessor.hpp> +#endif + +namespace boost { +namespace container { +namespace container_detail { + +template <class T1, class T2> +struct pair; + +template <class T> +struct is_pair +{ + static const bool value = false; +}; + +template <class T1, class T2> +struct is_pair< pair<T1, T2> > +{ + static const bool value = true; +}; + +template <class T1, class T2> +struct is_pair< std::pair<T1, T2> > +{ + static const bool value = true; +}; + +struct pair_nat; + +struct piecewise_construct_t { }; +static const piecewise_construct_t piecewise_construct = piecewise_construct_t(); + +template <class T1, class T2> +struct pair +{ + private: + BOOST_COPYABLE_AND_MOVABLE(pair) + + public: + typedef T1 first_type; + typedef T2 second_type; + + T1 first; + T2 second; + + //Default constructor + pair() + : first(), second() + {} +/* + //pair from two values + pair(const T1 &t1, const T2 &t2) + : first(t1) + , second(t2) + {} + + + //pair from two values + pair(BOOST_RV_REF(T1) t1, BOOST_RV_REF(T2) t2) + : first(::boost::move(t1)) + , second(::boost::move(t2)) + {} +*/ + template<class U, class V> + pair(BOOST_FWD_REF(U) u, BOOST_FWD_REF(V) v) + : first(::boost::forward<U>(u)) + , second(::boost::forward<V>(v)) + {} + + //pair copy assignment + pair(const pair& x) + : first(x.first), second(x.second) + {} + + template <class D, class S> + pair(const pair<D, S> &p) + : first(p.first), second(p.second) + {} + + //pair move constructor + pair(BOOST_RV_REF(pair) p) + : first(::boost::move(p.first)), second(::boost::move(p.second)) + {} + + template <class D, class S> + pair(BOOST_RV_REF_2_TEMPL_ARGS(pair, D, S) p) + : first(::boost::move(p.first)), second(::boost::move(p.second)) + {} + + //std::pair copy constructor + pair(const std::pair<T1, T2>& x) + : first(x.first), second(x.second) + {} + + template <class D, class S> + pair(const std::pair<D, S>& p) + : first(p.first), second(p.second) + {} + + //std::pair move constructor + template <class D, class S> + pair(BOOST_RV_REF_2_TEMPL_ARGS(std::pair, D, S) p) + : first(::boost::move(p.first)), second(::boost::move(p.second)) + {} + + pair(BOOST_RV_REF_2_TEMPL_ARGS(std::pair, T1, T2) p) + : first(::boost::move(p.first)), second(::boost::move(p.second)) + {} + + //piecewise_construct missing +/* + //Variadic versions + template<class U> + pair(BOOST_CONTAINER_PP_PARAM(U, u), typename container_detail::disable_if + < container_detail::is_pair< typename container_detail::remove_ref_const<U>::type >, pair_nat>::type* = 0) + : first(::boost::forward<U>(u)) + , second() + {} + + #ifdef BOOST_CONTAINER_PERFECT_FORWARDING + + template<class U, class V, class ...Args> + pair(U &&u, V &&v) + : first(::boost::forward<U>(u)) + , second(::boost::forward<V>(v), ::boost::forward<Args>(args)...) + {} + + #else + + #define BOOST_PP_LOCAL_MACRO(n) \ + template<class U, BOOST_PP_ENUM_PARAMS(n, class P)> \ + pair(BOOST_CONTAINER_PP_PARAM(U, u) \ + ,BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ + : first(::boost::forward<U>(u)) \ + , second(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)) \ + {} \ + //! + #define BOOST_PP_LOCAL_LIMITS (1, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS) + #include BOOST_PP_LOCAL_ITERATE() + #endif +*/ + //pair copy assignment + pair& operator=(BOOST_COPY_ASSIGN_REF(pair) p) + { + first = p.first; + second = p.second; + return *this; + } + + template <class D, class S> + pair& operator=(const pair<D, S>&p) + { + first = p.first; + second = p.second; + return *this; + } + + //pair move assignment + pair& operator=(BOOST_RV_REF(pair) p) + { + first = ::boost::move(p.first); + second = ::boost::move(p.second); + return *this; + } + + template <class D, class S> + pair& operator=(BOOST_RV_REF_2_TEMPL_ARGS(pair, D, S) p) + { + first = ::boost::move(p.first); + second = ::boost::move(p.second); + return *this; + } + + //std::pair copy assignment + pair& operator=(const std::pair<T1, T2> &p) + { + first = p.first; + second = p.second; + return *this; + } + + template <class D, class S> + pair& operator=(const std::pair<D, S> &p) + { + first = ::boost::move(p.first); + second = ::boost::move(p.second); + return *this; + } + + //std::pair move assignment + pair& operator=(BOOST_RV_REF_2_TEMPL_ARGS(std::pair, T1, T2) p) + { + first = ::boost::move(p.first); + second = ::boost::move(p.second); + return *this; + } + + template <class D, class S> + pair& operator=(BOOST_RV_REF_2_TEMPL_ARGS(std::pair, D, S) p) + { + first = ::boost::move(p.first); + second = ::boost::move(p.second); + return *this; + } + + //swap + void swap(pair& p) + { + using std::swap; + swap(this->first, p.first); + swap(this->second, p.second); + } +}; + +template <class T1, class T2> +inline bool operator==(const pair<T1,T2>& x, const pair<T1,T2>& y) +{ return static_cast<bool>(x.first == y.first && x.second == y.second); } + +template <class T1, class T2> +inline bool operator< (const pair<T1,T2>& x, const pair<T1,T2>& y) +{ return static_cast<bool>(x.first < y.first || + (!(y.first < x.first) && x.second < y.second)); } + +template <class T1, class T2> +inline bool operator!=(const pair<T1,T2>& x, const pair<T1,T2>& y) +{ return static_cast<bool>(!(x == y)); } + +template <class T1, class T2> +inline bool operator> (const pair<T1,T2>& x, const pair<T1,T2>& y) +{ return y < x; } + +template <class T1, class T2> +inline bool operator>=(const pair<T1,T2>& x, const pair<T1,T2>& y) +{ return static_cast<bool>(!(x < y)); } + +template <class T1, class T2> +inline bool operator<=(const pair<T1,T2>& x, const pair<T1,T2>& y) +{ return static_cast<bool>(!(y < x)); } + +template <class T1, class T2> +inline pair<T1, T2> make_pair(T1 x, T2 y) +{ return pair<T1, T2>(x, y); } + +template <class T1, class T2> +inline void swap(pair<T1, T2>& x, pair<T1, T2>& y) +{ + swap(x.first, y.first); + swap(x.second, y.second); +} + +} //namespace container_detail { +} //namespace container { + + +//Without this specialization recursive flat_(multi)map instantiation fails +//because is_enum needs to instantiate the recursive pair, leading to a compilation error). +//This breaks the cycle clearly stating that pair is not an enum avoiding any instantiation. +template<class T> +struct is_enum; + +template<class T, class U> +struct is_enum< ::boost::container::container_detail::pair<T, U> > +{ + static const bool value = false; +}; + +//This specialization is needed to avoid instantiation of pair in +//is_class, and allow recursive maps. +template <class T1, class T2> +struct is_class< ::boost::container::container_detail::pair<T1, T2> > + : public ::boost::true_type +{}; + +#ifdef BOOST_NO_RVALUE_REFERENCES + +template<class T1, class T2> +struct has_move_emulation_enabled< ::boost::container::container_detail::pair<T1, T2> > + : ::boost::true_type +{}; + +#endif + + +} //namespace boost { + +#include <boost/container/detail/config_end.hpp> + +#endif //#ifndef BOOST_CONTAINER_DETAIL_PAIR_HPP diff --git a/boost/container/detail/pool_common.hpp b/boost/container/detail/pool_common.hpp new file mode 100644 index 0000000000..c66e2cd18c --- /dev/null +++ b/boost/container/detail/pool_common.hpp @@ -0,0 +1,52 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2005-2011. 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_POOL_COMMON_HPP +#define BOOST_CONTAINER_DETAIL_NODE_POOL_COMMON_HPP + +#if (defined _MSC_VER) && (_MSC_VER >= 1200) +# pragma once +#endif + +#include "config_begin.hpp" +#include <boost/intrusive/slist.hpp> +#include <new> + +namespace boost { +namespace container { +namespace container_detail { + +template<class VoidPointer> +struct node_slist +{ + //This hook will be used to chain the individual nodes + typedef typename bi::make_slist_base_hook + <bi::void_pointer<VoidPointer>, bi::link_mode<bi::normal_link> >::type slist_hook_t; + + //A node object will hold node_t when it's not allocated + typedef slist_hook_t node_t; + + typedef typename bi::make_slist + <node_t, bi::linear<true>, bi::base_hook<slist_hook_t> >::type node_slist_t; +}; + +template<class T> +struct is_stateless_segment_manager +{ + static const bool value = false; +}; + +} //namespace container_detail { +} //namespace container { +} //namespace boost { + +#include <boost/container/detail/config_end.hpp> + +#endif //#ifndef BOOST_CONTAINER_DETAIL_ADAPTIVE_NODE_POOL_IMPL_HPP diff --git a/boost/container/detail/preprocessor.hpp b/boost/container/detail/preprocessor.hpp new file mode 100644 index 0000000000..9916fbac62 --- /dev/null +++ b/boost/container/detail/preprocessor.hpp @@ -0,0 +1,178 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2008-2011. 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_PREPROCESSOR_HPP +#define BOOST_CONTAINER_DETAIL_PREPROCESSOR_HPP + +#if (defined _MSC_VER) && (_MSC_VER >= 1200) +# pragma once +#endif + +#include <boost/container/detail/config_begin.hpp> + +#ifndef BOOST_NO_RVALUE_REFERENCES +#include <boost/container/detail/stored_ref.hpp> +#endif //#ifndef BOOST_NO_RVALUE_REFERENCES + +#include <boost/container/detail/workaround.hpp> + +#ifdef BOOST_CONTAINER_PERFECT_FORWARDING +//#error "This file is not needed when perfect forwarding is available" +#endif //BOOST_CONTAINER_PERFECT_FORWARDING + +#include <boost/preprocessor/iteration/local.hpp> +#include <boost/preprocessor/punctuation/paren_if.hpp> +#include <boost/preprocessor/punctuation/comma_if.hpp> +#include <boost/preprocessor/control/expr_if.hpp> +#include <boost/preprocessor/cat.hpp> +#include <boost/preprocessor/repetition/enum.hpp> +#include <boost/preprocessor/repetition/enum_params.hpp> +#include <boost/preprocessor/repetition/enum_trailing_params.hpp> +#include <boost/preprocessor/repetition/enum_trailing.hpp> +#include <boost/preprocessor/repetition/enum_shifted_params.hpp> +#include <boost/preprocessor/repetition/enum_shifted.hpp> +#include <boost/preprocessor/repetition/repeat.hpp> +#include <boost/preprocessor/logical/not.hpp> +#include <boost/preprocessor/arithmetic/sub.hpp> +#include <boost/preprocessor/arithmetic/add.hpp> +#include <boost/preprocessor/iteration/iterate.hpp> + +#define BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS 10 + +//Note: +//We define template parameters as const references to +//be able to bind temporaries. After that we will un-const them. +//This cast is ugly but it is necessary until "perfect forwarding" +//is achieved in C++0x. Meanwhile, if we want to be able to +//bind rvalues with non-const references, we have to be ugly +#ifndef BOOST_NO_RVALUE_REFERENCES + #define BOOST_CONTAINER_PP_PARAM_LIST(z, n, data) \ + BOOST_PP_CAT(P, n) && BOOST_PP_CAT(p, n) \ + //! +#else + #define BOOST_CONTAINER_PP_PARAM_LIST(z, n, data) \ + const BOOST_PP_CAT(P, n) & BOOST_PP_CAT(p, n) \ + //! +#endif //#ifndef BOOST_NO_RVALUE_REFERENCES + +#ifndef BOOST_NO_RVALUE_REFERENCES + #define BOOST_CONTAINER_PP_PARAM(U, u) \ + U && u \ + //! +#else + #define BOOST_CONTAINER_PP_PARAM(U, u) \ + const U & u \ + //! +#endif //#ifndef BOOST_NO_RVALUE_REFERENCES + +#ifndef BOOST_NO_RVALUE_REFERENCES + + #ifdef BOOST_MOVE_OLD_RVALUE_REF_BINDING_RULES + + #define BOOST_CONTAINER_PP_PARAM_INIT(z, n, data) \ + BOOST_PP_CAT(m_p, n) (boost::forward< BOOST_PP_CAT(P, n) >( BOOST_PP_CAT(p, n) )) \ + //! + + #else //BOOST_MOVE_OLD_RVALUE_REF_BINDING_RULES + + #define BOOST_CONTAINER_PP_PARAM_INIT(z, n, data) \ + BOOST_PP_CAT(m_p, n) (static_cast<BOOST_PP_CAT(P, n)>( BOOST_PP_CAT(p, n) )) \ + //! + + #endif //BOOST_MOVE_OLD_RVALUE_REF_BINDING_RULES + +#else //BOOST_NO_RVALUE_REFERENCES + + #define BOOST_CONTAINER_PP_PARAM_INIT(z, n, data) \ + BOOST_PP_CAT(m_p, n) (const_cast<BOOST_PP_CAT(P, n) &>(BOOST_PP_CAT(p, n))) \ + //! +#endif //#ifndef BOOST_NO_RVALUE_REFERENCES + +#ifndef BOOST_NO_RVALUE_REFERENCES + + #if defined(BOOST_MOVE_MSVC_10_MEMBER_RVALUE_REF_BUG) + + #define BOOST_CONTAINER_PP_PARAM_DEFINE(z, n, data) \ + BOOST_PP_CAT(P, n) & BOOST_PP_CAT(m_p, n); \ + //! + + #else //BOOST_MOVE_MSVC_10_MEMBER_RVALUE_REF_BUG + + #define BOOST_CONTAINER_PP_PARAM_DEFINE(z, n, data) \ + BOOST_PP_CAT(P, n) && BOOST_PP_CAT(m_p, n); \ + //! + + #endif //defined(BOOST_MOVE_MSVC_10_MEMBER_RVALUE_REF_BUG) + +#else //BOOST_NO_RVALUE_REFERENCES + + #define BOOST_CONTAINER_PP_PARAM_DEFINE(z, n, data) \ + BOOST_PP_CAT(P, n) & BOOST_PP_CAT(m_p, n); \ + //! +#endif //#ifndef BOOST_NO_RVALUE_REFERENCES + +#if !defined(BOOST_NO_RVALUE_REFERENCES) && defined(BOOST_MOVE_MSVC_10_MEMBER_RVALUE_REF_BUG) + + #define BOOST_CONTAINER_PP_MEMBER_FORWARD(z, n, data) \ + ::boost::container::container_detail::stored_ref< BOOST_PP_CAT(P, n) >::forward( BOOST_PP_CAT(this->m_p, n) ) \ + //! + +#else //!defined(BOOST_NO_RVALUE_REFERENCES) && defined(BOOST_MOVE_MSVC_10_MEMBER_RVALUE_REF_BUG) + + #define BOOST_CONTAINER_PP_MEMBER_FORWARD(z, n, data) \ + boost::forward< BOOST_PP_CAT(P, n) >( BOOST_PP_CAT(this->m_p, n) ) \ + //! + +#endif //!defined(BOOST_NO_RVALUE_REFERENCES) && defined(BOOST_MOVE_MSVC_10_MEMBER_RVALUE_REF_BUG) + +#define BOOST_CONTAINER_PP_PARAM_INC(z, n, data) \ + BOOST_PP_CAT(++this->m_p, n) \ +//! + +#define BOOST_CONTAINER_PP_IDENTITY(z, n, data) data + + +#define BOOST_CONTAINER_PP_PARAM_FORWARD(z, n, data) \ +boost::forward< BOOST_PP_CAT(P, n) >( BOOST_PP_CAT(p, n) ) \ +//! + +#define BOOST_CONTAINER_PP_DECLVAL(z, n, data) \ +boost::move_detail::declval< BOOST_PP_CAT(P, n) >() \ +//! + +#define BOOST_CONTAINER_PP_MEMBER_IT_FORWARD(z, n, data) \ +BOOST_PP_CAT(*this->m_p, n) \ +//! + +#define BOOST_CONTAINER_PP_TEMPLATE_PARAM_VOID_DEFAULT(z, n, data) \ + BOOST_PP_CAT(class P, n) = void \ +//! + +#define BOOST_CONTAINER_PP_STATIC_PARAM_REF_DECLARE(z, n, data) \ + static BOOST_PP_CAT(P, n) & BOOST_PP_CAT(p, n); \ +//! + +#define BOOST_CONTAINER_PP_PARAM_PASS(z, n, data) \ + BOOST_PP_CAT(p, n) \ +//! + +#define BOOST_CONTAINER_PP_FWD_TYPE(z, n, data) \ + typename ::boost::move_detail::forward_type< BOOST_PP_CAT(P, n) >::type \ +//! + +#include <boost/container/detail/config_end.hpp> + +//#else + +//#ifdef BOOST_CONTAINER_PERFECT_FORWARDING +//#error "This file is not needed when perfect forwarding is available" +//#endif //BOOST_CONTAINER_PERFECT_FORWARDING + +#endif //#ifndef BOOST_CONTAINER_DETAIL_PREPROCESSOR_HPP diff --git a/boost/container/detail/stored_ref.hpp b/boost/container/detail/stored_ref.hpp new file mode 100644 index 0000000000..df0faa85a0 --- /dev/null +++ b/boost/container/detail/stored_ref.hpp @@ -0,0 +1,92 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2008-2011. 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_STORED_REF_HPP +#define BOOST_CONTAINER_DETAIL_STORED_REF_HPP + +#include "config_begin.hpp" +#include <boost/container/detail/workaround.hpp> + +#ifndef BOOST_NO_RVALUE_REFERENCES + +namespace boost{ +namespace container{ +namespace container_detail{ + +template<class T> +struct stored_ref +{ + + static T && forward(T &t) + #ifdef BOOST_MOVE_OLD_RVALUE_REF_BINDING_RULES + { return t; } + #else + { return boost::move(t); } + #endif +}; + +template<class T> +struct stored_ref<const T> +{ + static const T && forward(const T &t) + #ifdef BOOST_MOVE_OLD_RVALUE_REF_BINDING_RULES + { return t; } + #else + { return static_cast<const T&&>(t); } + #endif +}; + +template<class T> +struct stored_ref<T&&> +{ + static T && forward(T &t) + #ifdef BOOST_MOVE_OLD_RVALUE_REF_BINDING_RULES + { return t; } + #else + { return boost::move(t); } + #endif +}; + +template<class T> +struct stored_ref<const T&&> +{ + static const T && forward(const T &t) + #ifdef BOOST_MOVE_OLD_RVALUE_REF_BINDING_RULES + { return t; } + #else + { return static_cast<const T &&>(t); } + #endif +}; + +template<class T> +struct stored_ref<const T&> +{ + static const T & forward(const T &t) + { return t; } +}; + +template<class T> +struct stored_ref<T&> +{ + static T & forward(T &t) + { return t; } +}; + +} //namespace container_detail{ +} //namespace container{ +} //namespace boost{ + +#else +#error "This header can be included only for compiler with rvalue references" +#endif //BOOST_NO_RVALUE_REFERENCES + +#include <boost/container/detail/config_end.hpp> + +#endif //BOOST_CONTAINER_DETAIL_STORED_REF_HPP diff --git a/boost/container/detail/transform_iterator.hpp b/boost/container/detail/transform_iterator.hpp new file mode 100644 index 0000000000..17eca9ef61 --- /dev/null +++ b/boost/container/detail/transform_iterator.hpp @@ -0,0 +1,176 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2005-2011. +// (C) Copyright Gennaro Prota 2003 - 2004. +// +// 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_TRANSFORM_ITERATORS_HPP +#define BOOST_CONTAINER_DETAIL_TRANSFORM_ITERATORS_HPP + +#if (defined _MSC_VER) && (_MSC_VER >= 1200) +# pragma once +#endif + +#include "config_begin.hpp" +#include <boost/container/detail/workaround.hpp> +#include <boost/container/detail/type_traits.hpp> +#include <iterator> + +namespace boost { +namespace container { + +template <class PseudoReference> +struct operator_arrow_proxy +{ + operator_arrow_proxy(const PseudoReference &px) + : m_value(px) + {} + + PseudoReference* operator->() const { return &m_value; } + // This function is needed for MWCW and BCC, which won't call operator-> + // again automatically per 13.3.1.2 para 8 +// operator T*() const { return &m_value; } + mutable PseudoReference m_value; +}; + +template <class T> +struct operator_arrow_proxy<T&> +{ + operator_arrow_proxy(T &px) + : m_value(px) + {} + + T* operator->() const { return const_cast<T*>(&m_value); } + // This function is needed for MWCW and BCC, which won't call operator-> + // again automatically per 13.3.1.2 para 8 +// operator T*() const { return &m_value; } + T &m_value; +}; + +template <class Iterator, class UnaryFunction> +class transform_iterator + : public UnaryFunction + , public std::iterator + < typename Iterator::iterator_category + , typename container_detail::remove_reference<typename UnaryFunction::result_type>::type + , typename Iterator::difference_type + , operator_arrow_proxy<typename UnaryFunction::result_type> + , typename UnaryFunction::result_type> +{ + public: + explicit transform_iterator(const Iterator &it, const UnaryFunction &f = UnaryFunction()) + : UnaryFunction(f), m_it(it) + {} + + explicit transform_iterator() + : UnaryFunction(), m_it() + {} + + //Constructors + transform_iterator& operator++() + { increment(); return *this; } + + transform_iterator operator++(int) + { + transform_iterator result (*this); + increment(); + return result; + } + + friend bool operator== (const transform_iterator& i, const transform_iterator& i2) + { return i.equal(i2); } + + friend bool operator!= (const transform_iterator& i, const transform_iterator& i2) + { return !(i == i2); } + +/* + friend bool operator> (const transform_iterator& i, const transform_iterator& i2) + { return i2 < i; } + + friend bool operator<= (const transform_iterator& i, const transform_iterator& i2) + { return !(i > i2); } + + friend bool operator>= (const transform_iterator& i, const transform_iterator& i2) + { return !(i < i2); } +*/ + friend typename Iterator::difference_type operator- (const transform_iterator& i, const transform_iterator& i2) + { return i2.distance_to(i); } + + //Arithmetic + transform_iterator& operator+=(typename Iterator::difference_type off) + { this->advance(off); return *this; } + + transform_iterator operator+(typename Iterator::difference_type off) const + { + transform_iterator other(*this); + other.advance(off); + return other; + } + + friend transform_iterator operator+(typename Iterator::difference_type off, const transform_iterator& right) + { return right + off; } + + transform_iterator& operator-=(typename Iterator::difference_type off) + { this->advance(-off); return *this; } + + transform_iterator operator-(typename Iterator::difference_type off) const + { return *this + (-off); } + + typename UnaryFunction::result_type operator*() const + { return dereference(); } + + operator_arrow_proxy<typename UnaryFunction::result_type> + operator->() const + { return operator_arrow_proxy<typename UnaryFunction::result_type>(dereference()); } + + Iterator & base() + { return m_it; } + + const Iterator & base() const + { return m_it; } + + private: + Iterator m_it; + + void increment() + { ++m_it; } + + void decrement() + { --m_it; } + + bool equal(const transform_iterator &other) const + { return m_it == other.m_it; } + + bool less(const transform_iterator &other) const + { return other.m_it < m_it; } + + typename UnaryFunction::result_type dereference() const + { return UnaryFunction::operator()(*m_it); } + + void advance(typename Iterator::difference_type n) + { std::advance(m_it, n); } + + typename Iterator::difference_type distance_to(const transform_iterator &other)const + { return std::distance(other.m_it, m_it); } +}; + +template <class Iterator, class UnaryFunc> +transform_iterator<Iterator, UnaryFunc> +make_transform_iterator(Iterator it, UnaryFunc fun) +{ + return transform_iterator<Iterator, UnaryFunc>(it, fun); +} + +} //namespace container { +} //namespace boost { + +#include <boost/container/detail/config_end.hpp> + +#endif //#ifndef BOOST_CONTAINER_DETAIL_TRANSFORM_ITERATORS_HPP diff --git a/boost/container/detail/tree.hpp b/boost/container/detail/tree.hpp new file mode 100644 index 0000000000..6cd91ed2a6 --- /dev/null +++ b/boost/container/detail/tree.hpp @@ -0,0 +1,1154 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2005-2011. 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_TREE_HPP +#define BOOST_CONTAINER_TREE_HPP + +#include "config_begin.hpp" +#include <boost/container/detail/workaround.hpp> +#include <boost/container/container_fwd.hpp> + +#include <boost/move/move.hpp> +#include <boost/intrusive/pointer_traits.hpp> +#include <boost/type_traits/has_trivial_destructor.hpp> +#include <boost/detail/no_exceptions_support.hpp> +#include <boost/intrusive/rbtree.hpp> + +#include <boost/container/detail/utilities.hpp> +#include <boost/container/detail/algorithms.hpp> +#include <boost/container/detail/node_alloc_holder.hpp> +#include <boost/container/detail/destroyers.hpp> +#include <boost/container/detail/pair.hpp> +#include <boost/container/detail/type_traits.hpp> +#include <boost/container/allocator/allocator_traits.hpp> +#ifndef BOOST_CONTAINER_PERFECT_FORWARDING +#include <boost/container/detail/preprocessor.hpp> +#endif + +#include <utility> //std::pair +#include <iterator> +#include <algorithm> + +namespace boost { +namespace container { +namespace container_detail { + +template<class Key, class Value, class KeyCompare, class KeyOfValue> +struct value_compare_impl + : public KeyCompare +{ + typedef Value value_type; + typedef KeyCompare key_compare; + typedef KeyOfValue key_of_value; + typedef Key key_type; + + value_compare_impl(const key_compare &kcomp) + : key_compare(kcomp) + {} + + const key_compare &key_comp() const + { return static_cast<const key_compare &>(*this); } + + key_compare &key_comp() + { return static_cast<key_compare &>(*this); } + + template<class T> + struct is_key + { + static const bool value = is_same<const T, const key_type>::value; + }; + + template<class T> + typename enable_if_c<is_key<T>::value, const key_type &>::type + key_forward(const T &key) const + { return key; } + + template<class T> + typename enable_if_c<!is_key<T>::value, const key_type &>::type + key_forward(const T &key) const + { return KeyOfValue()(key); } + + template<class KeyType, class KeyType2> + bool operator()(const KeyType &key1, const KeyType2 &key2) const + { return key_compare::operator()(this->key_forward(key1), this->key_forward(key2)); } +}; + +template<class VoidPointer> +struct rbtree_hook +{ + typedef typename container_detail::bi::make_set_base_hook + < container_detail::bi::void_pointer<VoidPointer> + , container_detail::bi::link_mode<container_detail::bi::normal_link> + , container_detail::bi::optimize_size<true> + >::type type; +}; + +template<class T> +struct rbtree_type +{ + typedef T type; +}; + +template<class T1, class T2> +struct rbtree_type< std::pair<T1, T2> > +{ + typedef pair<T1, T2> type; +}; + +template <class T, class VoidPointer> +struct rbtree_node + : public rbtree_hook<VoidPointer>::type +{ + private: + BOOST_COPYABLE_AND_MOVABLE(rbtree_node) + + public: + typedef typename rbtree_hook<VoidPointer>::type hook_type; + + typedef T value_type; + typedef typename rbtree_type<T>::type internal_type; + + typedef rbtree_node<T, VoidPointer> node_type; + + rbtree_node() + : m_data() + {} + + rbtree_node(const rbtree_node &other) + : m_data(other.m_data) + {} + + rbtree_node(BOOST_RV_REF(rbtree_node) other) + : m_data(boost::move(other.m_data)) + {} + + #ifndef BOOST_CONTAINER_PERFECT_FORWARDING + + #define BOOST_PP_LOCAL_MACRO(n) \ + template<BOOST_PP_ENUM_PARAMS(n, class P)> \ + rbtree_node(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ + : m_data(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _)) \ + {} \ + //! + #define BOOST_PP_LOCAL_LIMITS (1, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS) + #include BOOST_PP_LOCAL_ITERATE() + + #else //#ifndef BOOST_CONTAINER_PERFECT_FORWARDING + + template<class ...Args> + rbtree_node(Args &&...args) + : m_data(boost::forward<Args>(args)...) + {} + #endif//#ifndef BOOST_CONTAINER_PERFECT_FORWARDING + + rbtree_node &operator=(const rbtree_node &other) + { do_assign(other.m_data); return *this; } + + rbtree_node &operator=(BOOST_RV_REF(rbtree_node) other) + { do_move(other.m_data); return *this; } + + T &get_data() + { + T* ptr = reinterpret_cast<T*>(&this->m_data); + return *ptr; + } + + const T &get_data() const + { + const T* ptr = reinterpret_cast<const T*>(&this->m_data); + return *ptr; + } + + private: + internal_type m_data; + + template<class A, class B> + void do_assign(const std::pair<const A, B> &p) + { + const_cast<A&>(m_data.first) = p.first; + m_data.second = p.second; + } + + template<class A, class B> + void do_assign(const pair<const A, B> &p) + { + const_cast<A&>(m_data.first) = p.first; + m_data.second = p.second; + } + + template<class V> + void do_assign(const V &v) + { m_data = v; } + + template<class A, class B> + void do_move(std::pair<const A, B> &p) + { + const_cast<A&>(m_data.first) = boost::move(p.first); + m_data.second = boost::move(p.second); + } + + template<class A, class B> + void do_move(pair<const A, B> &p) + { + const_cast<A&>(m_data.first) = boost::move(p.first); + m_data.second = boost::move(p.second); + } + + template<class V> + void do_move(V &v) + { m_data = boost::move(v); } +}; + +}//namespace container_detail { + +namespace container_detail { + +template<class A, class ValueCompare> +struct intrusive_rbtree_type +{ + typedef typename boost::container:: + allocator_traits<A>::value_type value_type; + typedef typename boost::container:: + allocator_traits<A>::void_pointer void_pointer; + typedef typename boost::container:: + allocator_traits<A>::size_type size_type; + typedef typename container_detail::rbtree_node + <value_type, void_pointer> node_type; + typedef node_compare<ValueCompare, node_type> node_compare_type; + typedef typename container_detail::bi::make_rbtree + <node_type + ,container_detail::bi::compare<node_compare_type> + ,container_detail::bi::base_hook<typename rbtree_hook<void_pointer>::type> + ,container_detail::bi::constant_time_size<true> + ,container_detail::bi::size_type<size_type> + >::type container_type; + typedef container_type type ; +}; + +} //namespace container_detail { + +namespace container_detail { + +template <class Key, class Value, class KeyOfValue, + class KeyCompare, class A> +class rbtree + : protected container_detail::node_alloc_holder + < A + , typename container_detail::intrusive_rbtree_type + <A, value_compare_impl<Key, Value, KeyCompare, KeyOfValue> + >::type + , KeyCompare + > +{ + typedef typename container_detail::intrusive_rbtree_type + < A, value_compare_impl + <Key, Value, KeyCompare, KeyOfValue> + >::type Icont; + typedef container_detail::node_alloc_holder + <A, Icont, KeyCompare> AllocHolder; + typedef typename AllocHolder::NodePtr NodePtr; + typedef rbtree < Key, Value, KeyOfValue + , KeyCompare, A> ThisType; + typedef typename AllocHolder::NodeAlloc NodeAlloc; + typedef typename AllocHolder::ValAlloc ValAlloc; + typedef typename AllocHolder::Node Node; + typedef typename Icont::iterator iiterator; + typedef typename Icont::const_iterator iconst_iterator; + typedef container_detail::allocator_destroyer<NodeAlloc> Destroyer; + typedef typename AllocHolder::allocator_v1 allocator_v1; + typedef typename AllocHolder::allocator_v2 allocator_v2; + typedef typename AllocHolder::alloc_version alloc_version; + + class RecyclingCloner; + friend class RecyclingCloner; + + class RecyclingCloner + { + public: + RecyclingCloner(AllocHolder &holder, Icont &irbtree) + : m_holder(holder), m_icont(irbtree) + {} + + NodePtr operator()(const Node &other) const + { + if(NodePtr p = m_icont.unlink_leftmost_without_rebalance()){ + //First recycle a node (this can't throw) + try{ + //This can throw + *p = other; + return p; + } + catch(...){ + //If there is an exception destroy the whole source + m_holder.destroy_node(p); + while((p = m_icont.unlink_leftmost_without_rebalance())){ + m_holder.destroy_node(p); + } + throw; + } + } + else{ + return m_holder.create_node(other); + } + } + + AllocHolder &m_holder; + Icont &m_icont; + }; + + class RecyclingMoveCloner; + friend class RecyclingMoveCloner; + + class RecyclingMoveCloner + { + public: + RecyclingMoveCloner(AllocHolder &holder, Icont &irbtree) + : m_holder(holder), m_icont(irbtree) + {} + + NodePtr operator()(const Node &other) const + { + if(NodePtr p = m_icont.unlink_leftmost_without_rebalance()){ + //First recycle a node (this can't throw) + try{ + //This can throw + *p = boost::move(other); + return p; + } + catch(...){ + //If there is an exception destroy the whole source + m_holder.destroy_node(p); + while((p = m_icont.unlink_leftmost_without_rebalance())){ + m_holder.destroy_node(p); + } + throw; + } + } + else{ + return m_holder.create_node(other); + } + } + + AllocHolder &m_holder; + Icont &m_icont; + }; + + BOOST_COPYABLE_AND_MOVABLE(rbtree) + + public: + + typedef Key key_type; + typedef Value value_type; + typedef A allocator_type; + typedef KeyCompare key_compare; + typedef value_compare_impl< Key, Value + , KeyCompare, KeyOfValue> value_compare; + typedef typename boost::container:: + allocator_traits<A>::pointer pointer; + typedef typename boost::container:: + allocator_traits<A>::const_pointer const_pointer; + typedef typename boost::container:: + allocator_traits<A>::reference reference; + typedef typename boost::container:: + allocator_traits<A>::const_reference const_reference; + typedef typename boost::container:: + allocator_traits<A>::size_type size_type; + typedef typename boost::container:: + allocator_traits<A>::difference_type difference_type; + typedef difference_type rbtree_difference_type; + typedef pointer rbtree_pointer; + typedef const_pointer rbtree_const_pointer; + typedef reference rbtree_reference; + typedef const_reference rbtree_const_reference; + typedef NodeAlloc stored_allocator_type; + + private: + + template<class KeyValueCompare> + struct key_node_compare + : private KeyValueCompare + { + key_node_compare(const KeyValueCompare &comp) + : KeyValueCompare(comp) + {} + + template<class T> + struct is_node + { + static const bool value = is_same<T, Node>::value; + }; + + template<class T> + typename enable_if_c<is_node<T>::value, const value_type &>::type + key_forward(const T &node) const + { return node.get_data(); } + + template<class T> + typename enable_if_c<!is_node<T>::value, const T &>::type + key_forward(const T &key) const + { return key; } + + template<class KeyType, class KeyType2> + bool operator()(const KeyType &key1, const KeyType2 &key2) const + { return KeyValueCompare::operator()(this->key_forward(key1), this->key_forward(key2)); } + }; + + typedef key_node_compare<value_compare> KeyNodeCompare; + + public: + //rbtree const_iterator + class const_iterator + : public std::iterator + < std::bidirectional_iterator_tag + , value_type , rbtree_difference_type + , rbtree_const_pointer , rbtree_const_reference> + { + protected: + typedef typename Icont::iterator iiterator; + iiterator m_it; + explicit const_iterator(iiterator it) : m_it(it){} + void prot_incr() { ++m_it; } + void prot_decr() { --m_it; } + + private: + iiterator get() + { return this->m_it; } + + public: + friend class rbtree <Key, Value, KeyOfValue, KeyCompare, A>; + typedef rbtree_difference_type difference_type; + + //Constructors + const_iterator() + : m_it() + {} + + //Pointer like operators + const_reference operator*() const + { return m_it->get_data(); } + + const_pointer operator->() const + { return const_pointer(&m_it->get_data()); } + + //Increment / Decrement + const_iterator& operator++() + { prot_incr(); return *this; } + + const_iterator operator++(int) + { iiterator tmp = m_it; ++*this; return const_iterator(tmp); } + + const_iterator& operator--() + { prot_decr(); return *this; } + + const_iterator operator--(int) + { iiterator tmp = m_it; --*this; return const_iterator(tmp); } + + //Comparison operators + bool operator== (const const_iterator& r) const + { return m_it == r.m_it; } + + bool operator!= (const const_iterator& r) const + { return m_it != r.m_it; } + }; + + //rbtree iterator + class iterator : public const_iterator + { + private: + explicit iterator(iiterator it) + : const_iterator(it) + {} + + iiterator get() + { return this->m_it; } + + public: + friend class rbtree <Key, Value, KeyOfValue, KeyCompare, A>; + typedef rbtree_pointer pointer; + typedef rbtree_reference reference; + + //Constructors + iterator(){} + + //Pointer like operators + reference operator*() const { return this->m_it->get_data(); } + pointer operator->() const { return pointer(&this->m_it->get_data()); } + + //Increment / Decrement + iterator& operator++() + { this->prot_incr(); return *this; } + + iterator operator++(int) + { iiterator tmp = this->m_it; ++*this; return iterator(tmp); } + + iterator& operator--() + { this->prot_decr(); return *this; } + + iterator operator--(int) + { iterator tmp = *this; --*this; return tmp; } + }; + + typedef std::reverse_iterator<iterator> reverse_iterator; + typedef std::reverse_iterator<const_iterator> const_reverse_iterator; + + rbtree() + : AllocHolder(key_compare()) + {} + + rbtree(const key_compare& comp, const allocator_type& a = allocator_type()) + : AllocHolder(a, comp) + {} + + template <class InputIterator> + rbtree(InputIterator first, InputIterator last, const key_compare& comp, + const allocator_type& a, bool unique_insertion) + : AllocHolder(a, comp) + { + typedef typename std::iterator_traits<InputIterator>::iterator_category ItCat; + priv_create_and_insert_nodes(first, last, unique_insertion, alloc_version(), ItCat()); + } + + template <class InputIterator> + rbtree( ordered_range_t, InputIterator first, InputIterator last + , const key_compare& comp = key_compare(), const allocator_type& a = allocator_type()) + : AllocHolder(a, comp) + { + typedef typename std::iterator_traits<InputIterator>::iterator_category ItCat; + priv_create_and_insert_ordered_nodes(first, last, alloc_version(), ItCat()); + } + + rbtree(const rbtree& x) + : AllocHolder(x, x.key_comp()) + { + this->icont().clone_from + (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc())); + } + + rbtree(BOOST_RV_REF(rbtree) x) + : AllocHolder(boost::move(static_cast<AllocHolder&>(x)), x.key_comp()) + {} + + ~rbtree() + {} //AllocHolder clears the tree + + rbtree& operator=(BOOST_COPY_ASSIGN_REF(rbtree) x) + { + if (&x != this){ + NodeAlloc &this_alloc = this->get_stored_allocator(); + const NodeAlloc &x_alloc = x.get_stored_allocator(); + container_detail::bool_<allocator_traits<NodeAlloc>:: + propagate_on_container_copy_assignment::value> flag; + if(flag && this_alloc != x_alloc){ + this->clear(); + } + this->AllocHolder::copy_assign_alloc(x); + //Transfer all the nodes to a temporary tree + //If anything goes wrong, all the nodes will be destroyed + //automatically + Icont other_tree(boost::move(this->icont())); + + //Now recreate the source tree reusing nodes stored by other_tree + this->icont().clone_from + (x.icont() + , RecyclingCloner(*this, other_tree) + , Destroyer(this->node_alloc())); + + //If there are remaining nodes, destroy them + NodePtr p; + while((p = other_tree.unlink_leftmost_without_rebalance())){ + AllocHolder::destroy_node(p); + } + } + return *this; + } + + rbtree& operator=(BOOST_RV_REF(rbtree) x) + { + if (&x != this){ + NodeAlloc &this_alloc = this->node_alloc(); + NodeAlloc &x_alloc = x.node_alloc(); + //If allocators are equal we can just swap pointers + if(this_alloc == x_alloc){ + //Destroy and swap pointers + this->clear(); + this->icont() = boost::move(x.icont()); + //Move allocator if needed + this->AllocHolder::move_assign_alloc(x); + } + //If unequal allocators, then do a one by one move + else{ + //Transfer all the nodes to a temporary tree + //If anything goes wrong, all the nodes will be destroyed + //automatically + Icont other_tree(boost::move(this->icont())); + + //Now recreate the source tree reusing nodes stored by other_tree + this->icont().clone_from + (x.icont() + , RecyclingMoveCloner(*this, other_tree) + , Destroyer(this->node_alloc())); + + //If there are remaining nodes, destroy them + NodePtr p; + while((p = other_tree.unlink_leftmost_without_rebalance())){ + AllocHolder::destroy_node(p); + } + } + } + return *this; + } + + public: + // accessors: + value_compare value_comp() const + { return this->icont().value_comp().value_comp(); } + + key_compare key_comp() const + { return this->icont().value_comp().value_comp().key_comp(); } + + allocator_type get_allocator() const + { return allocator_type(this->node_alloc()); } + + const stored_allocator_type &get_stored_allocator() const + { return this->node_alloc(); } + + stored_allocator_type &get_stored_allocator() + { return this->node_alloc(); } + + iterator begin() + { return iterator(this->icont().begin()); } + + const_iterator begin() const + { return this->cbegin(); } + + iterator end() + { return iterator(this->icont().end()); } + + const_iterator end() const + { return this->cend(); } + + reverse_iterator rbegin() + { return reverse_iterator(end()); } + + const_reverse_iterator rbegin() const + { return this->crbegin(); } + + reverse_iterator rend() + { return reverse_iterator(begin()); } + + const_reverse_iterator rend() const + { return this->crend(); } + + //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + const_iterator cbegin() const + { return const_iterator(this->non_const_icont().begin()); } + + //! <b>Effects</b>: Returns a const_iterator to the end of the container. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + const_iterator cend() const + { return const_iterator(this->non_const_icont().end()); } + + //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning + //! of the reversed container. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + const_reverse_iterator crbegin() const + { return const_reverse_iterator(cend()); } + + //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end + //! of the reversed container. + //! + //! <b>Throws</b>: Nothing. + //! + //! <b>Complexity</b>: Constant. + const_reverse_iterator crend() const + { return const_reverse_iterator(cbegin()); } + + bool empty() const + { return !this->size(); } + + size_type size() const + { return this->icont().size(); } + + size_type max_size() const + { return AllocHolder::max_size(); } + + void swap(ThisType& x) + { AllocHolder::swap(x); } + + public: + + typedef typename Icont::insert_commit_data insert_commit_data; + + // insert/erase + std::pair<iterator,bool> insert_unique_check + (const key_type& key, insert_commit_data &data) + { + std::pair<iiterator, bool> ret = + this->icont().insert_unique_check(key, KeyNodeCompare(value_comp()), data); + return std::pair<iterator, bool>(iterator(ret.first), ret.second); + } + + std::pair<iterator,bool> insert_unique_check + (const_iterator hint, const key_type& key, insert_commit_data &data) + { + std::pair<iiterator, bool> ret = + this->icont().insert_unique_check(hint.get(), key, KeyNodeCompare(value_comp()), data); + return std::pair<iterator, bool>(iterator(ret.first), ret.second); + } + + iterator insert_unique_commit(const value_type& v, insert_commit_data &data) + { + NodePtr tmp = AllocHolder::create_node(v); + iiterator it(this->icont().insert_unique_commit(*tmp, data)); + return iterator(it); + } + + template<class MovableConvertible> + iterator insert_unique_commit + (BOOST_FWD_REF(MovableConvertible) mv, insert_commit_data &data) + { + NodePtr tmp = AllocHolder::create_node(boost::forward<MovableConvertible>(mv)); + iiterator it(this->icont().insert_unique_commit(*tmp, data)); + return iterator(it); + } + + std::pair<iterator,bool> insert_unique(const value_type& v) + { + insert_commit_data data; + std::pair<iterator,bool> ret = + this->insert_unique_check(KeyOfValue()(v), data); + if(!ret.second) + return ret; + return std::pair<iterator,bool> + (this->insert_unique_commit(v, data), true); + } + + template<class MovableConvertible> + std::pair<iterator,bool> insert_unique(BOOST_FWD_REF(MovableConvertible) mv) + { + insert_commit_data data; + std::pair<iterator,bool> ret = + this->insert_unique_check(KeyOfValue()(mv), data); + if(!ret.second) + return ret; + return std::pair<iterator,bool> + (this->insert_unique_commit(boost::forward<MovableConvertible>(mv), data), true); + } + + private: + std::pair<iterator, bool> emplace_unique_impl(NodePtr p) + { + value_type &v = p->get_data(); + insert_commit_data data; + std::pair<iterator,bool> ret = + this->insert_unique_check(KeyOfValue()(v), data); + if(!ret.second){ + Destroyer(this->node_alloc())(p); + return ret; + } + return std::pair<iterator,bool> + ( iterator(iiterator(this->icont().insert_unique_commit(*p, data))) + , true ); + } + + iterator emplace_unique_hint_impl(const_iterator hint, NodePtr p) + { + value_type &v = p->get_data(); + insert_commit_data data; + std::pair<iterator,bool> ret = + this->insert_unique_check(hint, KeyOfValue()(v), data); + if(!ret.second){ + Destroyer(this->node_alloc())(p); + return ret.first; + } + return iterator(iiterator(this->icont().insert_unique_commit(*p, data))); + } + + public: + + #ifdef BOOST_CONTAINER_PERFECT_FORWARDING + + template <class... Args> + std::pair<iterator, bool> emplace_unique(Args&&... args) + { return this->emplace_unique_impl(AllocHolder::create_node(boost::forward<Args>(args)...)); } + + template <class... Args> + iterator emplace_hint_unique(const_iterator hint, Args&&... args) + { return this->emplace_unique_hint_impl(hint, AllocHolder::create_node(boost::forward<Args>(args)...)); } + + template <class... Args> + iterator emplace_equal(Args&&... args) + { + NodePtr p(AllocHolder::create_node(boost::forward<Args>(args)...)); + return iterator(this->icont().insert_equal(this->icont().end(), *p)); + } + + template <class... Args> + iterator emplace_hint_equal(const_iterator hint, Args&&... args) + { + NodePtr p(AllocHolder::create_node(boost::forward<Args>(args)...)); + return iterator(this->icont().insert_equal(hint.get(), *p)); + } + + #else //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING + + #define BOOST_PP_LOCAL_MACRO(n) \ + BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ + std::pair<iterator, bool> emplace_unique(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ + { \ + return this->emplace_unique_impl \ + (AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _))); \ + } \ + \ + BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ + iterator emplace_hint_unique(const_iterator hint \ + BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ + { \ + return this->emplace_unique_hint_impl \ + (hint, AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _))); \ + } \ + \ + BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ + iterator emplace_equal(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ + { \ + NodePtr p(AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _))); \ + return iterator(this->icont().insert_equal(this->icont().end(), *p)); \ + } \ + \ + BOOST_PP_EXPR_IF(n, template<) BOOST_PP_ENUM_PARAMS(n, class P) BOOST_PP_EXPR_IF(n, >) \ + iterator emplace_hint_equal(const_iterator hint \ + BOOST_PP_ENUM_TRAILING(n, BOOST_CONTAINER_PP_PARAM_LIST, _)) \ + { \ + NodePtr p(AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_CONTAINER_PP_PARAM_FORWARD, _))); \ + return iterator(this->icont().insert_equal(hint.get(), *p)); \ + } \ + //! + #define BOOST_PP_LOCAL_LIMITS (0, BOOST_CONTAINER_MAX_CONSTRUCTOR_PARAMETERS) + #include BOOST_PP_LOCAL_ITERATE() + + #endif //#ifdef BOOST_CONTAINER_PERFECT_FORWARDING + + iterator insert_unique(const_iterator hint, const value_type& v) + { + insert_commit_data data; + std::pair<iterator,bool> ret = + this->insert_unique_check(hint, KeyOfValue()(v), data); + if(!ret.second) + return ret.first; + return this->insert_unique_commit(v, data); + } + + template<class MovableConvertible> + iterator insert_unique(const_iterator hint, BOOST_FWD_REF(MovableConvertible) mv) + { + insert_commit_data data; + std::pair<iterator,bool> ret = + this->insert_unique_check(hint, KeyOfValue()(mv), data); + if(!ret.second) + return ret.first; + return this->insert_unique_commit(boost::forward<MovableConvertible>(mv), data); + } + + template <class InputIterator> + void insert_unique(InputIterator first, InputIterator last) + { + if(this->empty()){ + //Insert with end hint, to achieve linear + //complexity if [first, last) is ordered + const_iterator end(this->end()); + for( ; first != last; ++first) + this->insert_unique(end, *first); + } + else{ + for( ; first != last; ++first) + this->insert_unique(*first); + } + } + + iterator insert_equal(const value_type& v) + { + NodePtr p(AllocHolder::create_node(v)); + return iterator(this->icont().insert_equal(this->icont().end(), *p)); + } + + template<class MovableConvertible> + iterator insert_equal(BOOST_FWD_REF(MovableConvertible) mv) + { + NodePtr p(AllocHolder::create_node(boost::forward<MovableConvertible>(mv))); + return iterator(this->icont().insert_equal(this->icont().end(), *p)); + } + + iterator insert_equal(const_iterator hint, const value_type& v) + { + NodePtr p(AllocHolder::create_node(v)); + return iterator(this->icont().insert_equal(hint.get(), *p)); + } + + template<class MovableConvertible> + iterator insert_equal(const_iterator hint, BOOST_FWD_REF(MovableConvertible) mv) + { + NodePtr p(AllocHolder::create_node(boost::forward<MovableConvertible>(mv))); + return iterator(this->icont().insert_equal(hint.get(), *p)); + } + + template <class InputIterator> + void insert_equal(InputIterator first, InputIterator last) + { + //Insert with end hint, to achieve linear + //complexity if [first, last) is ordered + const_iterator end(this->cend()); + for( ; first != last; ++first) + this->insert_equal(end, *first); + } + + iterator erase(const_iterator position) + { return iterator(this->icont().erase_and_dispose(position.get(), Destroyer(this->node_alloc()))); } + + size_type erase(const key_type& k) + { return AllocHolder::erase_key(k, KeyNodeCompare(value_comp()), alloc_version()); } + + iterator erase(const_iterator first, const_iterator last) + { return iterator(AllocHolder::erase_range(first.get(), last.get(), alloc_version())); } + + void clear() + { AllocHolder::clear(alloc_version()); } + + // set operations: + iterator find(const key_type& k) + { return iterator(this->icont().find(k, KeyNodeCompare(value_comp()))); } + + const_iterator find(const key_type& k) const + { return const_iterator(this->non_const_icont().find(k, KeyNodeCompare(value_comp()))); } + + size_type count(const key_type& k) const + { return size_type(this->icont().count(k, KeyNodeCompare(value_comp()))); } + + iterator lower_bound(const key_type& k) + { return iterator(this->icont().lower_bound(k, KeyNodeCompare(value_comp()))); } + + const_iterator lower_bound(const key_type& k) const + { return const_iterator(this->non_const_icont().lower_bound(k, KeyNodeCompare(value_comp()))); } + + iterator upper_bound(const key_type& k) + { return iterator(this->icont().upper_bound(k, KeyNodeCompare(value_comp()))); } + + const_iterator upper_bound(const key_type& k) const + { return const_iterator(this->non_const_icont().upper_bound(k, KeyNodeCompare(value_comp()))); } + + std::pair<iterator,iterator> equal_range(const key_type& k) + { + std::pair<iiterator, iiterator> ret = + this->icont().equal_range(k, KeyNodeCompare(value_comp())); + return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second)); + } + + std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const + { + std::pair<iiterator, iiterator> ret = + this->non_const_icont().equal_range(k, KeyNodeCompare(value_comp())); + return std::pair<const_iterator,const_iterator> + (const_iterator(ret.first), const_iterator(ret.second)); + } + + private: + //Iterator range version + template<class InpIterator> + void priv_create_and_insert_nodes + (InpIterator beg, InpIterator end, bool unique, allocator_v1, std::input_iterator_tag) + { + if(unique){ + for (; beg != end; ++beg){ + this->insert_unique(*beg); + } + } + else{ + for (; beg != end; ++beg){ + this->insert_equal(*beg); + } + } + } + + template<class InpIterator> + void priv_create_and_insert_nodes + (InpIterator beg, InpIterator end, bool unique, allocator_v2, std::input_iterator_tag) + { //Just forward to the default one + priv_create_and_insert_nodes(beg, end, unique, allocator_v1(), std::input_iterator_tag()); + } + + class insertion_functor; + friend class insertion_functor; + + class insertion_functor + { + Icont &icont_; + + public: + insertion_functor(Icont &icont) + : icont_(icont) + {} + + void operator()(Node &n) + { this->icont_.insert_equal(this->icont_.cend(), n); } + }; + + + template<class FwdIterator> + void priv_create_and_insert_nodes + (FwdIterator beg, FwdIterator end, bool unique, allocator_v2, std::forward_iterator_tag) + { + if(beg != end){ + if(unique){ + priv_create_and_insert_nodes(beg, end, unique, allocator_v2(), std::input_iterator_tag()); + } + else{ + //Optimized allocation and construction + this->allocate_many_and_construct + (beg, std::distance(beg, end), insertion_functor(this->icont())); + } + } + } + + //Iterator range version + template<class InpIterator> + void priv_create_and_insert_ordered_nodes + (InpIterator beg, InpIterator end, allocator_v1, std::input_iterator_tag) + { + const_iterator cend_n(this->cend()); + for (; beg != end; ++beg){ + this->insert_before(cend_n, *beg); + } + } + + template<class InpIterator> + void priv_create_and_insert_ordered_nodes + (InpIterator beg, InpIterator end, allocator_v2, std::input_iterator_tag) + { //Just forward to the default one + priv_create_and_insert_ordered_nodes(beg, end, allocator_v1(), std::input_iterator_tag()); + } + + class back_insertion_functor; + friend class back_insertion_functor; + + class back_insertion_functor + { + Icont &icont_; + + public: + back_insertion_functor(Icont &icont) + : icont_(icont) + {} + + void operator()(Node &n) + { this->icont_.push_back(n); } + }; + + + template<class FwdIterator> + void priv_create_and_insert_ordered_nodes + (FwdIterator beg, FwdIterator end, allocator_v2, std::forward_iterator_tag) + { + if(beg != end){ + //Optimized allocation and construction + this->allocate_many_and_construct + (beg, std::distance(beg, end), back_insertion_functor(this->icont())); + } + } +}; + +template <class Key, class Value, class KeyOfValue, + class KeyCompare, class A> +inline bool +operator==(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, + const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y) +{ + return x.size() == y.size() && + std::equal(x.begin(), x.end(), y.begin()); +} + +template <class Key, class Value, class KeyOfValue, + class KeyCompare, class A> +inline bool +operator<(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, + const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y) +{ + return std::lexicographical_compare(x.begin(), x.end(), + y.begin(), y.end()); +} + +template <class Key, class Value, class KeyOfValue, + class KeyCompare, class A> +inline bool +operator!=(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, + const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y) { + return !(x == y); +} + +template <class Key, class Value, class KeyOfValue, + class KeyCompare, class A> +inline bool +operator>(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, + const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y) { + return y < x; +} + +template <class Key, class Value, class KeyOfValue, + class KeyCompare, class A> +inline bool +operator<=(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, + const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y) { + return !(y < x); +} + +template <class Key, class Value, class KeyOfValue, + class KeyCompare, class A> +inline bool +operator>=(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, + const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y) { + return !(x < y); +} + + +template <class Key, class Value, class KeyOfValue, + class KeyCompare, class A> +inline void +swap(rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x, + rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y) +{ + x.swap(y); +} + +} //namespace container_detail { +} //namespace container { +/* +//!has_trivial_destructor_after_move<> == true_type +//!specialization for optimizations +template <class K, class V, class KOV, +class C, class A> +struct has_trivial_destructor_after_move + <boost::container::container_detail::rbtree<K, V, KOV, C, A> > +{ + static const bool value = has_trivial_destructor<A>::value && has_trivial_destructor<C>::value; +}; +*/ +} //namespace boost { + +#include <boost/container/detail/config_end.hpp> + +#endif //BOOST_CONTAINER_TREE_HPP diff --git a/boost/container/detail/type_traits.hpp b/boost/container/detail/type_traits.hpp new file mode 100644 index 0000000000..6a0b3ed58d --- /dev/null +++ b/boost/container/detail/type_traits.hpp @@ -0,0 +1,203 @@ +////////////////////////////////////////////////////////////////////////////// +// (C) Copyright John Maddock 2000. +// (C) Copyright Ion Gaztanaga 2005-2011. +// +// 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. +// +// The alignment_of implementation comes from John Maddock's boost::alignment_of code +// +////////////////////////////////////////////////////////////////////////////// + +#ifndef BOOST_CONTAINER_CONTAINER_DETAIL_TYPE_TRAITS_HPP +#define BOOST_CONTAINER_CONTAINER_DETAIL_TYPE_TRAITS_HPP + +#if (defined _MSC_VER) && (_MSC_VER >= 1200) +# pragma once +#endif + +#include "config_begin.hpp" + +#include <boost/move/move.hpp> + +namespace boost { +namespace container { +namespace container_detail { + +struct nat{}; + +//boost::alignment_of yields to 10K lines of preprocessed code, so we +//need an alternative +template <typename T> struct alignment_of; + +template <typename T> +struct alignment_of_hack +{ + char c; + T t; + alignment_of_hack(); +}; + +template <unsigned A, unsigned S> +struct alignment_logic +{ + enum{ value = A < S ? A : S }; +}; + +template< typename T > +struct alignment_of +{ + enum{ value = alignment_logic + < sizeof(alignment_of_hack<T>) - sizeof(T) + , sizeof(T)>::value }; +}; + +//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> +struct remove_reference +{ + typedef T type; +}; + +template<class T> +struct remove_reference<T&> +{ + typedef T type; +}; + +#ifndef BOOST_NO_RVALUE_REFERENCES + +template<class T> +struct remove_reference<T&&> +{ + typedef T type; +}; + +#else + +template<class T> +struct remove_reference< ::boost::rv<T> > +{ + typedef T type; +}; + +#endif + +template<class T> +struct is_reference +{ + enum { value = false }; +}; + +template<class T> +struct is_reference<T&> +{ + enum { value = true }; +}; + +template<class T> +struct is_pointer +{ + enum { value = false }; +}; + +template<class T> +struct is_pointer<T*> +{ + enum { value = true }; +}; + +template <typename T> +struct add_reference +{ + typedef T& type; +}; + +template<class T> +struct add_reference<T&> +{ + typedef T& type; +}; + +template<> +struct add_reference<void> +{ + typedef nat &type; +}; + +template<> +struct add_reference<const void> +{ + typedef const nat &type; +}; + +template <class T> +struct add_const_reference +{ typedef const T &type; }; + +template <class T> +struct add_const_reference<T&> +{ typedef T& type; }; + +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<class T> +struct remove_const +{ + typedef T type; +}; + +template<class T> +struct remove_const< const T> +{ + typedef T type; +}; + +template<class T> +struct remove_ref_const +{ + typedef typename remove_const< typename remove_reference<T>::type >::type type; +}; + +} // namespace container_detail +} //namespace container { +} //namespace boost { + +#include <boost/container/detail/config_end.hpp> + +#endif //#ifndef BOOST_CONTAINER_CONTAINER_DETAIL_TYPE_TRAITS_HPP diff --git a/boost/container/detail/utilities.hpp b/boost/container/detail/utilities.hpp new file mode 100644 index 0000000000..ee0fe993b2 --- /dev/null +++ b/boost/container/detail/utilities.hpp @@ -0,0 +1,271 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2005-2011. 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_UTILITIES_HPP +#define BOOST_CONTAINER_DETAIL_UTILITIES_HPP + +#include "config_begin.hpp" +#include <cstdio> +#include <boost/type_traits/is_fundamental.hpp> +#include <boost/type_traits/is_pointer.hpp> +#include <boost/type_traits/is_enum.hpp> +#include <boost/type_traits/is_member_pointer.hpp> +#include <boost/type_traits/is_class.hpp> +#include <boost/move/move.hpp> +#include <boost/container/detail/mpl.hpp> +#include <boost/container/detail/type_traits.hpp> +#include <boost/container/allocator/allocator_traits.hpp> +#include <algorithm> + +namespace boost { +namespace container { +namespace container_detail { + +template<class T> +const T &max_value(const T &a, const T &b) +{ return a > b ? a : b; } + +template<class T> +const T &min_value(const T &a, const T &b) +{ return a < b ? a : b; } + +template <class SizeType> +SizeType + get_next_capacity(const SizeType max_size + ,const SizeType capacity + ,const SizeType n) +{ +// if (n > max_size - capacity) +// throw std::length_error("get_next_capacity"); + + const SizeType m3 = max_size/3; + + if (capacity < m3) + return capacity + max_value(3*(capacity+1)/5, n); + + if (capacity < m3*2) + return capacity + max_value((capacity+1)/2, n); + + return max_size; +} + +template <class T> +inline T* to_raw_pointer(T* p) +{ return p; } + +template <class Pointer> +inline typename Pointer::element_type* + to_raw_pointer(const Pointer &p) +{ return boost::container::container_detail::to_raw_pointer(p.operator->()); } + +//!To avoid ADL problems with swap +template <class T> +inline void do_swap(T& x, T& y) +{ + using std::swap; + swap(x, y); +} + +template<class AllocatorType> +inline void swap_alloc(AllocatorType &, AllocatorType &, container_detail::false_type) + BOOST_CONTAINER_NOEXCEPT +{} + +template<class AllocatorType> +inline void swap_alloc(AllocatorType &l, AllocatorType &r, container_detail::true_type) +{ container_detail::do_swap(l, r); } + +template<class AllocatorType> +inline void assign_alloc(AllocatorType &, const AllocatorType &, container_detail::false_type) + BOOST_CONTAINER_NOEXCEPT +{} + +template<class AllocatorType> +inline void assign_alloc(AllocatorType &l, const AllocatorType &r, container_detail::true_type) +{ l = r; } + +template<class AllocatorType> +inline void move_alloc(AllocatorType &, AllocatorType &, container_detail::false_type) + BOOST_CONTAINER_NOEXCEPT +{} + +template<class AllocatorType> +inline void move_alloc(AllocatorType &l, AllocatorType &r, container_detail::true_type) +{ l = ::boost::move(r); } + +//Rounds "orig_size" by excess to round_to bytes +template<class SizeType> +inline SizeType get_rounded_size(SizeType orig_size, SizeType round_to) +{ + return ((orig_size-1)/round_to+1)*round_to; +} + +template <std::size_t OrigSize, std::size_t RoundTo> +struct ct_rounded_size +{ + enum { value = ((OrigSize-1)/RoundTo+1)*RoundTo }; +}; +/* +template <class _TypeT> +struct __rw_is_enum +{ + struct _C_no { }; + struct _C_yes { int _C_dummy [2]; }; + + struct _C_indirect { + // prevent classes with user-defined conversions from matching + + // use double to prevent float->int gcc conversion warnings + _C_indirect (double); +}; + +// nested struct gets rid of bogus gcc errors +struct _C_nest { + // supply first argument to prevent HP aCC warnings + static _C_no _C_is (int, ...); + static _C_yes _C_is (int, _C_indirect); + + static _TypeT _C_make_T (); +}; + +enum { + _C_val = sizeof (_C_yes) == sizeof (_C_nest::_C_is (0, _C_nest::_C_make_T ())) + && !::boost::is_fundamental<_TypeT>::value +}; + +}; +*/ + +template<class T> +struct move_const_ref_type + : if_c +// < ::boost::is_fundamental<T>::value || ::boost::is_pointer<T>::value || ::boost::is_member_pointer<T>::value || ::boost::is_enum<T>::value + < !::boost::is_class<T>::value + ,const T & + ,BOOST_CATCH_CONST_RLVALUE(T) + > +{}; + +} //namespace container_detail { + +////////////////////////////////////////////////////////////////////////////// +// +// uninitialized_move_alloc +// +////////////////////////////////////////////////////////////////////////////// + +//! <b>Effects</b>: +//! \code +//! for (; first != last; ++result, ++first) +//! allocator_traits::construct(a, &*result, boost::move(*first)); +//! \endcode +//! +//! <b>Returns</b>: result +template + <typename A, + typename I, // I models InputIterator + typename F> // F models ForwardIterator +F uninitialized_move_alloc(A &a, I f, I l, F r) +{ + while (f != l) { + allocator_traits<A>::construct(a, container_detail::to_raw_pointer(&*r), boost::move(*f)); + ++f; ++r; + } + return r; +} + +////////////////////////////////////////////////////////////////////////////// +// +// uninitialized_copy_alloc +// +////////////////////////////////////////////////////////////////////////////// + +//! <b>Effects</b>: +//! \code +//! for (; first != last; ++result, ++first) +//! allocator_traits::construct(a, &*result, *first); +//! \endcode +//! +//! <b>Returns</b>: result +template + <typename A, + typename I, // I models InputIterator + typename F> // F models ForwardIterator +F uninitialized_copy_alloc(A &a, I f, I l, F r) +{ + while (f != l) { + allocator_traits<A>::construct(a, container_detail::to_raw_pointer(&*r), *f); + ++f; ++r; + } + return r; +} + +////////////////////////////////////////////////////////////////////////////// +// +// uninitialized_copy_alloc +// +////////////////////////////////////////////////////////////////////////////// + +//! <b>Effects</b>: +//! \code +//! for (; first != last; ++result, ++first) +//! allocator_traits::construct(a, &*result, *first); +//! \endcode +//! +//! <b>Returns</b>: result +template + <typename A, + typename F, // F models ForwardIterator + typename T> +void uninitialized_fill_alloc(A &a, F f, F l, const T &t) +{ + while (f != l) { + allocator_traits<A>::construct(a, container_detail::to_raw_pointer(&*f), t); + ++f; + } +} + +////////////////////////////////////////////////////////////////////////////// +// +// uninitialized_copy_or_move_alloc +// +////////////////////////////////////////////////////////////////////////////// + +template +<typename A +,typename I // I models InputIterator +,typename F> // F models ForwardIterator +F uninitialized_copy_or_move_alloc + (A &a, I f, I l, F r + ,typename boost::container::container_detail::enable_if + < boost::move_detail::is_move_iterator<I> >::type* = 0) +{ + return ::boost::container::uninitialized_move_alloc(a, f, l, r); +} + +template +<typename A +,typename I // I models InputIterator +,typename F> // F models ForwardIterator +F uninitialized_copy_or_move_alloc + (A &a, I f, I l, F r + ,typename boost::container::container_detail::disable_if + < boost::move_detail::is_move_iterator<I> >::type* = 0) +{ + return ::boost::container::uninitialized_copy_alloc(a, f, l, r); +} + +} //namespace container { +} //namespace boost { + + +#include <boost/container/detail/config_end.hpp> + +#endif //#ifndef BOOST_CONTAINER_DETAIL_UTILITIES_HPP diff --git a/boost/container/detail/value_init.hpp b/boost/container/detail/value_init.hpp new file mode 100644 index 0000000000..afbc9c1e34 --- /dev/null +++ b/boost/container/detail/value_init.hpp @@ -0,0 +1,45 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2005-2011. +// +// 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_VALUE_INIT_HPP +#define BOOST_CONTAINER_DETAIL_VALUE_INIT_HPP + +#if (defined _MSC_VER) && (_MSC_VER >= 1200) +# pragma once +#endif + +#include "config_begin.hpp" +#include <boost/container/detail/workaround.hpp> + +namespace boost { +namespace container { +namespace container_detail { + +template<class T> +struct value_init +{ + value_init() + : m_t() + {} + + operator T &() { return m_t; } + + T m_t; +}; + +} //namespace container_detail { +} //namespace container { +} //namespace boost { + +#include <boost/container/detail/config_end.hpp> + +#endif //#ifndef BOOST_CONTAINER_DETAIL_VALUE_INIT_HPP diff --git a/boost/container/detail/variadic_templates_tools.hpp b/boost/container/detail/variadic_templates_tools.hpp new file mode 100644 index 0000000000..f21f972ab1 --- /dev/null +++ b/boost/container/detail/variadic_templates_tools.hpp @@ -0,0 +1,153 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2008-2011. 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_VARIADIC_TEMPLATES_TOOLS_HPP +#define BOOST_CONTAINER_DETAIL_VARIADIC_TEMPLATES_TOOLS_HPP + +#if (defined _MSC_VER) && (_MSC_VER >= 1200) +# pragma once +#endif + +#include "config_begin.hpp" +#include <boost/container/detail/workaround.hpp> +#include <boost/container/detail/type_traits.hpp> +#include <cstddef> //std::size_t + +namespace boost { +namespace container { +namespace container_detail { + +template<typename... Values> +class tuple; + +template<> class tuple<> +{}; + +template<typename Head, typename... Tail> +class tuple<Head, Tail...> + : private tuple<Tail...> +{ + typedef tuple<Tail...> inherited; + + public: + tuple() { } + + // implicit copy-constructor is okay + // Construct tuple from separate arguments. + tuple(typename add_const_reference<Head>::type v, + typename add_const_reference<Tail>::type... vtail) + : inherited(vtail...), m_head(v) + {} + + // Construct tuple from another tuple. + template<typename... VValues> + tuple(const tuple<VValues...>& other) + : m_head(other.head()), inherited(other.tail()) + {} + + template<typename... VValues> + tuple& operator=(const tuple<VValues...>& other) + { + m_head = other.head(); + tail() = other.tail(); + return this; + } + + typename add_reference<Head>::type head() { return m_head; } + typename add_reference<const Head>::type head() const { return m_head; } + + inherited& tail() { return *this; } + const inherited& tail() const { return *this; } + + protected: + Head m_head; +}; + + +template<typename... Values> +tuple<Values&&...> tie_forward(Values&&... values) +{ return tuple<Values&&...>(values...); } + +template<int I, typename Tuple> +struct tuple_element; + +template<int I, typename Head, typename... Tail> +struct tuple_element<I, tuple<Head, Tail...> > +{ + typedef typename tuple_element<I-1, tuple<Tail...> >::type type; +}; + +template<typename Head, typename... Tail> +struct tuple_element<0, tuple<Head, Tail...> > +{ + typedef Head type; +}; + +template<int I, typename Tuple> +class get_impl; + +template<int I, typename Head, typename... Values> +class get_impl<I, tuple<Head, Values...> > +{ + typedef typename tuple_element<I-1, tuple<Values...> >::type Element; + typedef get_impl<I-1, tuple<Values...> > Next; + + public: + typedef typename add_reference<Element>::type type; + typedef typename add_const_reference<Element>::type const_type; + static type get(tuple<Head, Values...>& t) { return Next::get(t.tail()); } + static const_type get(const tuple<Head, Values...>& t) { return Next::get(t.tail()); } +}; + +template<typename Head, typename... Values> +class get_impl<0, tuple<Head, Values...> > +{ + public: + typedef typename add_reference<Head>::type type; + typedef typename add_const_reference<Head>::type const_type; + static type get(tuple<Head, Values...>& t) { return t.head(); } + static const_type get(const tuple<Head, Values...>& t){ return t.head(); } +}; + +template<int I, typename... Values> +typename get_impl<I, tuple<Values...> >::type get(tuple<Values...>& t) +{ return get_impl<I, tuple<Values...> >::get(t); } + +template<int I, typename... Values> +typename get_impl<I, tuple<Values...> >::const_type get(const tuple<Values...>& t) +{ return get_impl<I, tuple<Values...> >::get(t); } + +//////////////////////////////////////////////////// +// Builds an index_tuple<0, 1, 2, ..., Num-1>, that will +// be used to "unpack" into comma-separated values +// in a function call. +//////////////////////////////////////////////////// + +template<int... Indexes> +struct index_tuple{}; + +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; }; + + +}}} //namespace boost { namespace container { namespace container_detail { + +#include <boost/container/detail/config_end.hpp> + +#endif //#ifndef BOOST_CONTAINER_DETAIL_VARIADIC_TEMPLATES_TOOLS_HPP diff --git a/boost/container/detail/version_type.hpp b/boost/container/detail/version_type.hpp new file mode 100644 index 0000000000..46344faca0 --- /dev/null +++ b/boost/container/detail/version_type.hpp @@ -0,0 +1,92 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2005-2011. 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. +// +////////////////////////////////////////////////////////////////////////////// +// +// This code comes from N1953 document by Howard E. Hinnant +// +////////////////////////////////////////////////////////////////////////////// + + +#ifndef BOOST_CONTAINER_DETAIL_VERSION_TYPE_HPP +#define BOOST_CONTAINER_DETAIL_VERSION_TYPE_HPP + +#include "config_begin.hpp" + +#include <boost/container/detail/mpl.hpp> +#include <boost/container/detail/type_traits.hpp> + +namespace boost{ +namespace container { +namespace container_detail { + +//using namespace boost; + +template <class T, unsigned V> +struct version_type + : public container_detail::integral_constant<unsigned, V> +{ + typedef T type; + + version_type(const version_type<T, 0>&); +}; + +namespace impl{ + +template <class T, + bool = container_detail::is_convertible<version_type<T, 0>, typename T::version>::value> +struct extract_version +{ + static const unsigned value = 1; +}; + +template <class T> +struct extract_version<T, true> +{ + static const unsigned value = T::version::value; +}; + +template <class T> +struct has_version +{ + private: + struct two {char _[2];}; + template <class U> static two test(...); + template <class U> static char test(const typename U::version*); + public: + static const bool value = sizeof(test<T>(0)) == 1; + void dummy(){} +}; + +template <class T, bool = has_version<T>::value> +struct version +{ + static const unsigned value = 1; +}; + +template <class T> +struct version<T, true> +{ + static const unsigned value = extract_version<T>::value; +}; + +} //namespace impl + +template <class T> +struct version + : public container_detail::integral_constant<unsigned, impl::version<T>::value> +{ +}; + +} //namespace container_detail { +} //namespace container { +} //namespace boost{ + +#include "config_end.hpp" + +#endif //#define BOOST_CONTAINER_DETAIL_VERSION_TYPE_HPP diff --git a/boost/container/detail/workaround.hpp b/boost/container/detail/workaround.hpp new file mode 100644 index 0000000000..45ab2f2c4d --- /dev/null +++ b/boost/container/detail/workaround.hpp @@ -0,0 +1,31 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2005-2011. 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_WORKAROUND_HPP +#define BOOST_CONTAINER_DETAIL_WORKAROUND_HPP + +#include <boost/container/detail/config_begin.hpp> + +#if !defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_NO_VARIADIC_TEMPLATES)\ + && !defined(BOOST_INTERPROCESS_DISABLE_VARIADIC_TMPL) + #define BOOST_CONTAINER_PERFECT_FORWARDING +#endif + +#if defined(BOOST_NO_NOEXCEPT) + #define BOOST_CONTAINER_NOEXCEPT + #define BOOST_CONTAINER_NOEXCEPT_IF(x) +#else + #define BOOST_CONTAINER_NOEXCEPT noexcept + #define BOOST_CONTAINER_NOEXCEPT_IF(x) noexcept(x) +#endif + +#include <boost/container/detail/config_end.hpp> + +#endif //#ifndef BOOST_CONTAINER_DETAIL_WORKAROUND_HPP |