From d9ec475d945d3035377a0d89ed42e382d8988891 Mon Sep 17 00:00:00 2001 From: DongHun Kwak Date: Thu, 6 Oct 2016 10:33:54 +0900 Subject: Imported Upstream version 1.60.0 Change-Id: Ie709530d6d5841088ceaba025cbe175a4ef43050 Signed-off-by: DongHun Kwak --- boost/container/adaptive_pool.hpp | 34 +- boost/container/allocator.hpp | 43 +- boost/container/allocator_traits.hpp | 2 +- boost/container/container_fwd.hpp | 40 +- boost/container/deque.hpp | 91 ++++- boost/container/detail/adaptive_node_pool.hpp | 1 - boost/container/detail/alloc_lib.h | 122 +++--- boost/container/detail/alloc_lib_auto_link.hpp | 24 -- boost/container/detail/auto_link.hpp | 11 +- boost/container/detail/block_list.hpp | 139 +++++++ boost/container/detail/block_slist.hpp | 157 +++++++ boost/container/detail/config_begin.hpp | 1 + boost/container/detail/copy_move_algo.hpp | 8 +- boost/container/detail/dispatch_uses_allocator.hpp | 293 +++++++++++++ boost/container/detail/dlmalloc.hpp | 103 +++++ boost/container/detail/flat_tree.hpp | 30 +- boost/container/detail/mutex.hpp | 4 +- boost/container/detail/pair.hpp | 72 +--- boost/container/detail/pool_common_alloc.hpp | 12 +- boost/container/detail/pool_resource.hpp | 191 +++++++++ boost/container/detail/std_fwd.hpp | 30 +- boost/container/detail/tree.hpp | 37 +- boost/container/detail/type_traits.hpp | 2 + .../container/detail/variadic_templates_tools.hpp | 2 +- boost/container/detail/workaround.hpp | 21 +- boost/container/flat_map.hpp | 21 +- boost/container/flat_set.hpp | 6 +- boost/container/list.hpp | 111 +++-- boost/container/map.hpp | 6 +- boost/container/new_allocator.hpp | 4 + boost/container/node_allocator.hpp | 24 +- boost/container/pmr/deque.hpp | 43 ++ boost/container/pmr/flat_map.hpp | 63 +++ boost/container/pmr/flat_set.hpp | 59 +++ boost/container/pmr/global_resource.hpp | 66 +++ boost/container/pmr/list.hpp | 43 ++ boost/container/pmr/map.hpp | 63 +++ boost/container/pmr/memory_resource.hpp | 101 +++++ boost/container/pmr/monotonic_buffer_resource.hpp | 180 ++++++++ boost/container/pmr/polymorphic_allocator.hpp | 166 ++++++++ boost/container/pmr/pool_options.hpp | 52 +++ boost/container/pmr/resource_adaptor.hpp | 193 +++++++++ boost/container/pmr/set.hpp | 59 +++ boost/container/pmr/slist.hpp | 43 ++ boost/container/pmr/small_vector.hpp | 43 ++ boost/container/pmr/stable_vector.hpp | 43 ++ boost/container/pmr/string.hpp | 48 +++ boost/container/pmr/synchronized_pool_resource.hpp | 138 +++++++ .../container/pmr/unsynchronized_pool_resource.hpp | 194 +++++++++ boost/container/pmr/vector.hpp | 43 ++ boost/container/scoped_allocator.hpp | 452 ++------------------- boost/container/scoped_allocator_fwd.hpp | 31 +- boost/container/set.hpp | 9 +- boost/container/slist.hpp | 49 +-- boost/container/small_vector.hpp | 17 +- boost/container/stable_vector.hpp | 86 ++-- boost/container/static_vector.hpp | 8 +- boost/container/string.hpp | 176 ++++++-- boost/container/uses_allocator.hpp | 169 ++++++++ boost/container/uses_allocator_fwd.hpp | 73 ++++ boost/container/vector.hpp | 284 +++++++------ 61 files changed, 3653 insertions(+), 983 deletions(-) delete mode 100644 boost/container/detail/alloc_lib_auto_link.hpp create mode 100644 boost/container/detail/block_list.hpp create mode 100644 boost/container/detail/block_slist.hpp create mode 100644 boost/container/detail/dispatch_uses_allocator.hpp create mode 100644 boost/container/detail/dlmalloc.hpp create mode 100644 boost/container/detail/pool_resource.hpp create mode 100644 boost/container/pmr/deque.hpp create mode 100644 boost/container/pmr/flat_map.hpp create mode 100644 boost/container/pmr/flat_set.hpp create mode 100644 boost/container/pmr/global_resource.hpp create mode 100644 boost/container/pmr/list.hpp create mode 100644 boost/container/pmr/map.hpp create mode 100644 boost/container/pmr/memory_resource.hpp create mode 100644 boost/container/pmr/monotonic_buffer_resource.hpp create mode 100644 boost/container/pmr/polymorphic_allocator.hpp create mode 100644 boost/container/pmr/pool_options.hpp create mode 100644 boost/container/pmr/resource_adaptor.hpp create mode 100644 boost/container/pmr/set.hpp create mode 100644 boost/container/pmr/slist.hpp create mode 100644 boost/container/pmr/small_vector.hpp create mode 100644 boost/container/pmr/stable_vector.hpp create mode 100644 boost/container/pmr/string.hpp create mode 100644 boost/container/pmr/synchronized_pool_resource.hpp create mode 100644 boost/container/pmr/unsynchronized_pool_resource.hpp create mode 100644 boost/container/pmr/vector.hpp create mode 100644 boost/container/uses_allocator.hpp create mode 100644 boost/container/uses_allocator_fwd.hpp (limited to 'boost/container') diff --git a/boost/container/adaptive_pool.hpp b/boost/container/adaptive_pool.hpp index 59ba37bc93..ac3d86709e 100644 --- a/boost/container/adaptive_pool.hpp +++ b/boost/container/adaptive_pool.hpp @@ -27,7 +27,7 @@ #include #include #include -#include +#include #include #include @@ -164,7 +164,7 @@ class adaptive_pool return pointer(static_cast(singleton_t::instance().allocate_node())); } else{ - return static_cast(boost_cont_malloc(count*sizeof(T))); + return static_cast(dlmalloc_malloc(count*sizeof(T))); } } @@ -180,7 +180,7 @@ class adaptive_pool singleton_t::instance().deallocate_node(ptr); } else{ - boost_cont_free(ptr); + dlmalloc_free(ptr); } } @@ -198,7 +198,7 @@ class adaptive_pool //!Returns maximum the number of objects the previously allocated memory //!pointed by p can hold. size_type size(pointer p) const BOOST_NOEXCEPT_OR_NOTHROW - { return boost_cont_size(p); } + { return dlmalloc_size(p); } //!Allocates just one object. Memory allocated with this function //!must be deallocated only with deallocate_one(). @@ -251,17 +251,17 @@ class adaptive_pool void allocate_many(size_type elem_size, std::size_t n_elements, multiallocation_chain &chain) { BOOST_STATIC_ASSERT(( Version > 1 ));/* - boost_cont_memchain ch; + dlmalloc_memchain ch; BOOST_CONTAINER_MEMCHAIN_INIT(&ch); - if(BOOST_UNLIKELY(!boost_cont_multialloc_nodes(n_elements, elem_size*sizeof(T), DL_MULTIALLOC_DEFAULT_CONTIGUOUS, &ch))){ + if(BOOST_UNLIKELY(!dlmalloc_multialloc_nodes(n_elements, elem_size*sizeof(T), DL_MULTIALLOC_DEFAULT_CONTIGUOUS, &ch))){ boost::container::throw_bad_alloc(); } chain.incorporate_after(chain.before_begin() ,(T*)BOOST_CONTAINER_MEMCHAIN_FIRSTMEM(&ch) ,(T*)BOOST_CONTAINER_MEMCHAIN_LASTMEM(&ch) ,BOOST_CONTAINER_MEMCHAIN_SIZE(&ch) );*/ - if(BOOST_UNLIKELY(!boost_cont_multialloc_nodes - (n_elements, elem_size*sizeof(T), DL_MULTIALLOC_DEFAULT_CONTIGUOUS, reinterpret_cast(&chain)))){ + if(BOOST_UNLIKELY(!dlmalloc_multialloc_nodes + (n_elements, elem_size*sizeof(T), DL_MULTIALLOC_DEFAULT_CONTIGUOUS, reinterpret_cast(&chain)))){ boost::container::throw_bad_alloc(); } } @@ -271,29 +271,29 @@ class adaptive_pool void allocate_many(const size_type *elem_sizes, size_type n_elements, multiallocation_chain &chain) { BOOST_STATIC_ASSERT(( Version > 1 ));/* - boost_cont_memchain ch; + dlmalloc_memchain ch; BOOST_CONTAINER_MEMCHAIN_INIT(&ch); - if(BOOST_UNLIKELY(!boost_cont_multialloc_arrays(n_elements, elem_sizes, sizeof(T), DL_MULTIALLOC_DEFAULT_CONTIGUOUS, &ch))){ + if(BOOST_UNLIKELY(!dlmalloc_multialloc_arrays(n_elements, elem_sizes, sizeof(T), DL_MULTIALLOC_DEFAULT_CONTIGUOUS, &ch))){ boost::container::throw_bad_alloc(); } chain.incorporate_after(chain.before_begin() ,(T*)BOOST_CONTAINER_MEMCHAIN_FIRSTMEM(&ch) ,(T*)BOOST_CONTAINER_MEMCHAIN_LASTMEM(&ch) ,BOOST_CONTAINER_MEMCHAIN_SIZE(&ch) );*/ - if(BOOST_UNLIKELY(!boost_cont_multialloc_arrays - (n_elements, elem_sizes, sizeof(T), DL_MULTIALLOC_DEFAULT_CONTIGUOUS, reinterpret_cast(&chain)))){ + if(BOOST_UNLIKELY(!dlmalloc_multialloc_arrays + (n_elements, elem_sizes, sizeof(T), DL_MULTIALLOC_DEFAULT_CONTIGUOUS, reinterpret_cast(&chain)))){ boost::container::throw_bad_alloc(); } } void deallocate_many(multiallocation_chain &chain) BOOST_NOEXCEPT_OR_NOTHROW {/* - boost_cont_memchain ch; + dlmalloc_memchain ch; void *beg(&*chain.begin()), *last(&*chain.last()); size_t size(chain.size()); BOOST_CONTAINER_MEMCHAIN_INIT_FROM(&ch, beg, last, size); - boost_cont_multidealloc(&ch);*/ - boost_cont_multidealloc(reinterpret_cast(&chain)); + dlmalloc_multidealloc(&ch);*/ + dlmalloc_multidealloc(reinterpret_cast(&chain)); } //!Deallocates all free blocks of the pool @@ -326,7 +326,7 @@ class adaptive_pool ,size_type &prefer_in_recvd_out_size, pointer &reuse_ptr) { std::size_t const preferred_size = prefer_in_recvd_out_size; - boost_cont_command_ret_t ret = {0 , 0}; + dlmalloc_command_ret_t ret = {0 , 0}; if(BOOST_UNLIKELY(limit_size > this->max_size() || preferred_size > this->max_size())){ return pointer(); } @@ -335,7 +335,7 @@ class adaptive_pool std::size_t r_size; { void* reuse_ptr_void = reuse_ptr; - ret = boost_cont_allocation_command(command, sizeof(T), l_size, p_size, &r_size, reuse_ptr_void); + ret = dlmalloc_allocation_command(command, sizeof(T), l_size, p_size, &r_size, reuse_ptr_void); reuse_ptr = ret.second ? static_cast(reuse_ptr_void) : 0; } prefer_in_recvd_out_size = r_size/sizeof(T); diff --git a/boost/container/allocator.hpp b/boost/container/allocator.hpp index 9f757c73e8..2fb44b73d3 100644 --- a/boost/container/allocator.hpp +++ b/boost/container/allocator.hpp @@ -24,12 +24,14 @@ #include #include #include -#include +#include #include #include #include #include +//!\file + namespace boost { namespace container { @@ -86,21 +88,18 @@ class allocator #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED -//!\file //! This class is an extended STL-compatible that offers advanced allocation mechanism //!(in-place expansion, shrinking, burst-allocation...) //! //! This allocator is a wrapper around a modified DLmalloc. -#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED -template -#else //! If Version is 1, the allocator is a STL conforming allocator. If Version is 2, //! the allocator offers advanced expand in place and burst allocation capabilities. -// +//! //! AllocationDisableMask works only if Version is 2 and it can be an inclusive OR //! of allocation types the user wants to disable. -template -#endif //#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED +template< class T + , unsigned Version BOOST_CONTAINER_DOCONLY(=2) + , unsigned int AllocationDisableMask BOOST_CONTAINER_DOCONLY(=0)> class allocator { typedef unsigned int allocation_type; @@ -186,7 +185,7 @@ class allocator (void)hint; if(count > this->max_size()) boost::container::throw_bad_alloc(); - void *ret = boost_cont_malloc(count*sizeof(T)); + void *ret = dlmalloc_malloc(count*sizeof(T)); if(!ret) boost::container::throw_bad_alloc(); return static_cast(ret); @@ -195,7 +194,7 @@ class allocator //!Deallocates previously allocated memory. //!Never throws void deallocate(pointer ptr, size_type) BOOST_NOEXCEPT_OR_NOTHROW - { boost_cont_free(ptr); } + { dlmalloc_free(ptr); } //!Returns the maximum number of elements that could be allocated. //!Never throws @@ -243,7 +242,7 @@ class allocator size_type size(pointer p) const BOOST_NOEXCEPT_OR_NOTHROW { BOOST_STATIC_ASSERT(( Version > 1 )); - return boost_cont_size(p); + return dlmalloc_size(p); } //!Allocates just one object. Memory allocated with this function @@ -289,16 +288,16 @@ class allocator void allocate_many(size_type elem_size, std::size_t n_elements, multiallocation_chain &chain) { BOOST_STATIC_ASSERT(( Version > 1 ));/* - boost_cont_memchain ch; + dlmalloc_memchain ch; BOOST_CONTAINER_MEMCHAIN_INIT(&ch); - if(!boost_cont_multialloc_nodes(n_elements, elem_size*sizeof(T), DL_MULTIALLOC_DEFAULT_CONTIGUOUS, &ch)){ + if(!dlmalloc_multialloc_nodes(n_elements, elem_size*sizeof(T), DL_MULTIALLOC_DEFAULT_CONTIGUOUS, &ch)){ boost::container::throw_bad_alloc(); } chain.incorporate_after(chain.before_begin() ,(T*)BOOST_CONTAINER_MEMCHAIN_FIRSTMEM(&ch) ,(T*)BOOST_CONTAINER_MEMCHAIN_LASTMEM(&ch) ,BOOST_CONTAINER_MEMCHAIN_SIZE(&ch) );*/ - if(!boost_cont_multialloc_nodes(n_elements, elem_size*sizeof(T), DL_MULTIALLOC_DEFAULT_CONTIGUOUS, reinterpret_cast(&chain))){ + if(!dlmalloc_multialloc_nodes(n_elements, elem_size*sizeof(T), DL_MULTIALLOC_DEFAULT_CONTIGUOUS, reinterpret_cast(&chain))){ boost::container::throw_bad_alloc(); } } @@ -309,9 +308,9 @@ class allocator void allocate_many(const size_type *elem_sizes, size_type n_elements, multiallocation_chain &chain) { BOOST_STATIC_ASSERT(( Version > 1 )); - boost_cont_memchain ch; + dlmalloc_memchain ch; BOOST_CONTAINER_MEMCHAIN_INIT(&ch); - if(!boost_cont_multialloc_arrays(n_elements, elem_sizes, sizeof(T), DL_MULTIALLOC_DEFAULT_CONTIGUOUS, &ch)){ + if(!dlmalloc_multialloc_arrays(n_elements, elem_sizes, sizeof(T), DL_MULTIALLOC_DEFAULT_CONTIGUOUS, &ch)){ boost::container::throw_bad_alloc(); } chain.incorporate_after(chain.before_begin() @@ -319,7 +318,7 @@ class allocator ,(T*)BOOST_CONTAINER_MEMCHAIN_LASTMEM(&ch) ,BOOST_CONTAINER_MEMCHAIN_SIZE(&ch) ); /* - if(!boost_cont_multialloc_arrays(n_elements, elem_sizes, sizeof(T), DL_MULTIALLOC_DEFAULT_CONTIGUOUS, reinterpret_cast(&chain))){ + if(!dlmalloc_multialloc_arrays(n_elements, elem_sizes, sizeof(T), DL_MULTIALLOC_DEFAULT_CONTIGUOUS, reinterpret_cast(&chain))){ boost::container::throw_bad_alloc(); }*/ } @@ -330,12 +329,12 @@ class allocator void deallocate_many(multiallocation_chain &chain) BOOST_NOEXCEPT_OR_NOTHROW { BOOST_STATIC_ASSERT(( Version > 1 )); - boost_cont_memchain ch; + dlmalloc_memchain ch; void *beg(&*chain.begin()), *last(&*chain.last()); size_t size(chain.size()); BOOST_CONTAINER_MEMCHAIN_INIT_FROM(&ch, beg, last, size); - boost_cont_multidealloc(&ch); - //boost_cont_multidealloc(reinterpret_cast(&chain)); + dlmalloc_multidealloc(&ch); + //dlmalloc_multidealloc(reinterpret_cast(&chain)); } private: @@ -346,7 +345,7 @@ class allocator ,pointer &reuse_ptr) { std::size_t const preferred_size = prefer_in_recvd_out_size; - boost_cont_command_ret_t ret = {0 , 0}; + dlmalloc_command_ret_t ret = {0 , 0}; if((limit_size > this->max_size()) | (preferred_size > this->max_size())){ return pointer(); } @@ -355,7 +354,7 @@ class allocator std::size_t r_size; { void* reuse_ptr_void = reuse_ptr; - ret = boost_cont_allocation_command(command, sizeof(T), l_size, p_size, &r_size, reuse_ptr_void); + ret = dlmalloc_allocation_command(command, sizeof(T), l_size, p_size, &r_size, reuse_ptr_void); reuse_ptr = ret.second ? static_cast(reuse_ptr_void) : 0; } prefer_in_recvd_out_size = r_size/sizeof(T); diff --git a/boost/container/allocator_traits.hpp b/boost/container/allocator_traits.hpp index 2c7900ea72..b515af6180 100644 --- a/boost/container/allocator_traits.hpp +++ b/boost/container/allocator_traits.hpp @@ -445,7 +445,7 @@ struct allocator_traits template static void priv_construct(container_detail::false_type, Allocator &, T *p, const ::boost::container::default_init_t&) - { ::new((void*)p) T; } + { ::new((void*)p, boost_container_new_t()) T; } static bool priv_storage_is_unpropagable(container_detail::true_type, const Allocator &a, pointer p) { return a.storage_is_unpropagable(p); } diff --git a/boost/container/container_fwd.hpp b/boost/container/container_fwd.hpp index a9b421c2b2..e85a6ce952 100644 --- a/boost/container/container_fwd.hpp +++ b/boost/container/container_fwd.hpp @@ -24,6 +24,7 @@ //! - boost::container::vector //! - boost::container::stable_vector //! - boost::container::static_vector +//! - boost::container::small_vector //! - boost::container::slist //! - boost::container::list //! - boost::container::set @@ -38,11 +39,19 @@ //! - boost::container::string //! - boost::container::wstring //! -//! It forward declares the following allocators: +//! Forward declares the following allocators: //! - boost::container::allocator //! - boost::container::node_allocator //! - boost::container::adaptive_pool //! +//! Forward declares the following polymorphic resource classes: +//! - boost::container::pmr::memory_resource +//! - boost::container::pmr::polymorphic_allocator +//! - boost::container::pmr::monotonic_buffer_resource +//! - boost::container::pmr::pool_options +//! - boost::container::pmr::unsynchronized_pool_resource +//! - boost::container::pmr::synchronized_pool_resource +//! //! And finally it defines the following types #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED @@ -54,11 +63,18 @@ namespace boost{ namespace intrusive{ +namespace detail{ //Create namespace to avoid compilation errors -}} +}}} namespace boost{ namespace container{ namespace container_detail{ namespace bi = boost::intrusive; + namespace bid = boost::intrusive::detail; +}}} + +namespace boost{ namespace container{ namespace pmr{ + namespace bi = boost::intrusive; + namespace bid = boost::intrusive::detail; }}} #include @@ -210,6 +226,26 @@ template , std::size_t Version = 2> class node_allocator; +namespace pmr { + +class memory_resource; + +template +class polymorphic_allocator; + +class monotonic_buffer_resource; + +struct pool_options; + +template +class resource_adaptor_imp; + +class unsynchronized_pool_resource; + +class synchronized_pool_resource; + +} //namespace pmr { + #else //! Default options for tree-based associative containers diff --git a/boost/container/deque.hpp b/boost/container/deque.hpp index bdfecc1212..f53f34ae98 100644 --- a/boost/container/deque.hpp +++ b/boost/container/deque.hpp @@ -1,6 +1,6 @@ ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2005-2013. Distributed under the Boost +// (C) Copyright Ion Gaztanaga 2005-2015. 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) // @@ -1140,7 +1140,10 @@ class deque : protected deque_base //! //! Complexity: Constant. reference front() BOOST_NOEXCEPT_OR_NOTHROW - { return *this->members_.m_start; } + { + BOOST_ASSERT(!this->empty()); + return *this->members_.m_start; + } //! Requires: !empty() //! @@ -1151,7 +1154,10 @@ class deque : protected deque_base //! //! Complexity: Constant. const_reference front() const BOOST_NOEXCEPT_OR_NOTHROW - { return *this->members_.m_start; } + { + BOOST_ASSERT(!this->empty()); + return *this->members_.m_start; + } //! Requires: !empty() //! @@ -1162,7 +1168,10 @@ class deque : protected deque_base //! //! Complexity: Constant. reference back() BOOST_NOEXCEPT_OR_NOTHROW - { return *(end()-1); } + { + BOOST_ASSERT(!this->empty()); + return *(end()-1); + } //! Requires: !empty() //! @@ -1173,7 +1182,10 @@ class deque : protected deque_base //! //! Complexity: Constant. const_reference back() const BOOST_NOEXCEPT_OR_NOTHROW - { return *(cend()-1); } + { + BOOST_ASSERT(!this->empty()); + return *(cend()-1); + } //! Requires: size() > n. //! @@ -1184,7 +1196,10 @@ class deque : protected deque_base //! //! Complexity: Constant. reference operator[](size_type n) BOOST_NOEXCEPT_OR_NOTHROW - { return this->members_.m_start[difference_type(n)]; } + { + BOOST_ASSERT(this->size() > n); + return this->members_.m_start[difference_type(n)]; + } //! Requires: size() > n. //! @@ -1195,7 +1210,10 @@ class deque : protected deque_base //! //! Complexity: Constant. const_reference operator[](size_type n) const BOOST_NOEXCEPT_OR_NOTHROW - { return this->members_.m_start[difference_type(n)]; } + { + BOOST_ASSERT(this->size() > n); + return this->members_.m_start[difference_type(n)]; + } //! Requires: size() >= n. //! @@ -1243,7 +1261,10 @@ class deque : protected deque_base //! //! Note: Non-standard extension size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW - { return this->priv_index_of(p); } + { + //Range checked priv_index_of + return this->priv_index_of(p); + } //! Requires: begin() <= p <= end(). //! @@ -1256,7 +1277,10 @@ class deque : protected deque_base //! //! Note: Non-standard extension size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW - { return this->priv_index_of(p); } + { + //Range checked priv_index_of + return this->priv_index_of(p); + } //! Requires: size() > n. //! @@ -1267,7 +1291,10 @@ class deque : protected deque_base //! //! Complexity: Constant. reference at(size_type n) - { this->priv_range_check(n); return (*this)[n]; } + { + this->priv_throw_if_out_of_range(n); + return (*this)[n]; + } //! Requires: size() > n. //! @@ -1278,7 +1305,10 @@ class deque : protected deque_base //! //! Complexity: Constant. const_reference at(size_type n) const - { this->priv_range_check(n); return (*this)[n]; } + { + this->priv_throw_if_out_of_range(n); + return (*this)[n]; + } ////////////////////////////////////////////// // @@ -1344,6 +1374,7 @@ class deque : protected deque_base template iterator emplace(const_iterator p, BOOST_FWD_REF(Args)... args) { + BOOST_ASSERT(this->priv_in_range_or_end(p)); if(p == this->cbegin()){ this->emplace_front(boost::forward(args)...); return this->begin(); @@ -1394,6 +1425,7 @@ class deque : protected deque_base BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N\ iterator emplace(const_iterator p BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ {\ + BOOST_ASSERT(this->priv_in_range_or_end(p));\ if(p == this->cbegin()){\ this->emplace_front(BOOST_MOVE_FWD##N);\ return this->begin();\ @@ -1494,6 +1526,7 @@ class deque : protected deque_base //! Complexity: Linear to n. iterator insert(const_iterator pos, size_type n, const value_type& x) { + //Range check of p is done by insert() typedef constant_iterator c_it; return this->insert(pos, c_it(x, n), c_it()); } @@ -1519,6 +1552,7 @@ class deque : protected deque_base #endif ) { + BOOST_ASSERT(this->priv_in_range_or_end(pos)); size_type n = 0; iterator it(pos.unconst()); for(;first != last; ++first, ++n){ @@ -1541,7 +1575,10 @@ class deque : protected deque_base //! //! Complexity: Linear to distance [il.begin(), il.end()). iterator insert(const_iterator pos, std::initializer_list il) - { return insert(pos, il.begin(), il.end()); } + { + //Range check os pos is done in insert() + return insert(pos, il.begin(), il.end()); + } #endif #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) @@ -1556,6 +1593,7 @@ class deque : protected deque_base #endif ) { + BOOST_ASSERT(this->priv_in_range_or_end(p)); container_detail::insert_range_proxy proxy(first); return priv_insert_aux_impl(p, boost::container::iterator_distance(first, last), proxy); } @@ -1568,6 +1606,7 @@ class deque : protected deque_base //! Complexity: Constant time. void pop_front() BOOST_NOEXCEPT_OR_NOTHROW { + BOOST_ASSERT(!this->empty()); if (this->members_.m_start.m_cur != this->members_.m_start.m_last - 1) { allocator_traits_type::destroy ( this->alloc() @@ -1586,6 +1625,7 @@ class deque : protected deque_base //! Complexity: Constant time. void pop_back() BOOST_NOEXCEPT_OR_NOTHROW { + BOOST_ASSERT(!this->empty()); if (this->members_.m_finish.m_cur != this->members_.m_finish.m_first) { --this->members_.m_finish.m_cur; allocator_traits_type::destroy @@ -1607,6 +1647,7 @@ class deque : protected deque_base //! Constant if pos is the first or the last element. iterator erase(const_iterator pos) BOOST_NOEXCEPT_OR_NOTHROW { + BOOST_ASSERT(this->priv_in_range(pos)); iterator next = pos.unconst(); ++next; size_type index = pos - this->members_.m_start; @@ -1631,6 +1672,8 @@ class deque : protected deque_base //! if(pos is near the beginning). iterator erase(const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW { + BOOST_ASSERT(first == last || + (first < last && this->priv_in_range(first) && this->priv_in_range_or_end(last))); if (first == this->members_.m_start && last == this->members_.m_finish) { this->clear(); return this->members_.m_finish; @@ -1764,12 +1807,26 @@ class deque : protected deque_base } } - void priv_range_check(size_type n) const - { if (n >= this->size()) throw_out_of_range("deque::at out of range"); } + void priv_throw_if_out_of_range(size_type n) const + { + if (n >= this->size()) + throw_out_of_range("deque::at out of range"); + } + + bool priv_in_range(const_iterator pos) const + { + return (this->begin() <= pos) && (pos < this->end()); + } + + bool priv_in_range_or_end(const_iterator pos) const + { + return (this->begin() <= pos) && (pos <= this->end()); + } template iterator priv_insert(const_iterator p, BOOST_FWD_REF(U) x) { + BOOST_ASSERT(this->priv_in_range_or_end(p)); if (p == cbegin()){ this->push_front(::boost::forward(x)); return begin(); @@ -1994,8 +2051,7 @@ class deque : protected deque_base } template - typename iterator_enable_if_tag::type - priv_range_initialize(InIt first, InIt last) + void priv_range_initialize(InIt first, InIt last, typename iterator_enable_if_tag::type* =0) { this->priv_initialize_map(0); BOOST_TRY { @@ -2010,8 +2066,7 @@ class deque : protected deque_base } template - typename iterator_disable_if_tag::type - priv_range_initialize(FwdIt first, FwdIt last) + void priv_range_initialize(FwdIt first, FwdIt last, typename iterator_disable_if_tag::type* =0) { size_type n = 0; n = boost::container::iterator_distance(first, last); diff --git a/boost/container/detail/adaptive_node_pool.hpp b/boost/container/detail/adaptive_node_pool.hpp index 4a1f07c4a8..20696100f5 100644 --- a/boost/container/detail/adaptive_node_pool.hpp +++ b/boost/container/detail/adaptive_node_pool.hpp @@ -23,7 +23,6 @@ #include #include -#include #include #include #include diff --git a/boost/container/detail/alloc_lib.h b/boost/container/detail/alloc_lib.h index 4802d9d814..950ff722a5 100644 --- a/boost/container/detail/alloc_lib.h +++ b/boost/container/detail/alloc_lib.h @@ -15,27 +15,6 @@ #ifdef _MSC_VER #pragma warning (push) #pragma warning (disable : 4127) - -/* - we need to import/export our code only if the user has specifically - asked for it by defining either BOOST_ALL_DYN_LINK if they want all boost - libraries to be dynamically linked, or BOOST_CONTAINER_DYN_LINK - if they want just this one to be dynamically liked: -*/ -#if defined(BOOST_ALL_DYN_LINK) || defined(BOOST_CONTAINER_DYN_LINK) - -/* export if this is our own source, otherwise import: */ -#ifdef BOOST_CONTAINER_SOURCE -# define BOOST_CONTAINER_DECL __declspec(dllexport) -#else -# define BOOST_CONTAINER_DECL __declspec(dllimport) -#endif /* BOOST_CONTAINER_SOURCE */ -#endif /* DYN_LINK */ -#endif /* _MSC_VER */ - -/* if BOOST_CONTAINER_DECL isn't defined yet define it now: */ -#ifndef BOOST_CONTAINER_DECL -#define BOOST_CONTAINER_DECL #endif #ifdef __cplusplus @@ -215,14 +194,6 @@ typedef struct boost_cont_memchain_impl }while(0)\ /**/ -BOOST_CONTAINER_DECL size_t boost_cont_size(const void *p); - -BOOST_CONTAINER_DECL void* boost_cont_malloc(size_t bytes); - -BOOST_CONTAINER_DECL void boost_cont_free(void* mem); - -BOOST_CONTAINER_DECL void* boost_cont_memalign(size_t bytes, size_t alignment); - /*!Indicates the all elements allocated by boost_cont_multialloc_nodes or boost_cont_multialloc_arrays must be contiguous.*/ #define DL_MULTIALLOC_ALL_CONTIGUOUS ((size_t)(-1)) @@ -231,22 +202,6 @@ BOOST_CONTAINER_DECL void* boost_cont_memalign(size_t bytes, size_t alignment); should be selected by those functions.*/ #define DL_MULTIALLOC_DEFAULT_CONTIGUOUS ((size_t)(0)) -BOOST_CONTAINER_DECL int boost_cont_multialloc_nodes - (size_t n_elements, size_t elem_size, size_t contiguous_elements, boost_cont_memchain *pchain); - -BOOST_CONTAINER_DECL int boost_cont_multialloc_arrays - (size_t n_elements, const size_t *sizes, size_t sizeof_element, size_t contiguous_elements, boost_cont_memchain *pchain); - -BOOST_CONTAINER_DECL void boost_cont_multidealloc(boost_cont_memchain *pchain); - -BOOST_CONTAINER_DECL size_t boost_cont_footprint(); - -BOOST_CONTAINER_DECL size_t boost_cont_allocated_memory(); - -BOOST_CONTAINER_DECL size_t boost_cont_chunksize(const void *p); - -BOOST_CONTAINER_DECL int boost_cont_all_deallocated(); - typedef struct boost_cont_malloc_stats_impl { size_t max_system_bytes; @@ -254,26 +209,6 @@ typedef struct boost_cont_malloc_stats_impl size_t in_use_bytes; } boost_cont_malloc_stats_t; -BOOST_CONTAINER_DECL boost_cont_malloc_stats_t boost_cont_malloc_stats(); - -BOOST_CONTAINER_DECL size_t boost_cont_in_use_memory(); - -BOOST_CONTAINER_DECL int boost_cont_trim(size_t pad); - -BOOST_CONTAINER_DECL int boost_cont_mallopt - (int parameter_number, int parameter_value); - -BOOST_CONTAINER_DECL int boost_cont_grow - (void* oldmem, size_t minbytes, size_t maxbytes, size_t *received); - -BOOST_CONTAINER_DECL int boost_cont_shrink - (void* oldmem, size_t minbytes, size_t maxbytes, size_t *received, int do_commit); - -BOOST_CONTAINER_DECL void* boost_cont_alloc - (size_t minbytes, size_t preferred_bytes, size_t *received_bytes); - -BOOST_CONTAINER_DECL int boost_cont_malloc_check(); - typedef unsigned int allocation_type; enum @@ -303,7 +238,50 @@ typedef struct boost_cont_command_ret_impl int second; }boost_cont_command_ret_t; -BOOST_CONTAINER_DECL boost_cont_command_ret_t boost_cont_allocation_command +size_t boost_cont_size(const void *p); + +void* boost_cont_malloc(size_t bytes); + +void boost_cont_free(void* mem); + +void* boost_cont_memalign(size_t bytes, size_t alignment); + +int boost_cont_multialloc_nodes + (size_t n_elements, size_t elem_size, size_t contiguous_elements, boost_cont_memchain *pchain); + +int boost_cont_multialloc_arrays + (size_t n_elements, const size_t *sizes, size_t sizeof_element, size_t contiguous_elements, boost_cont_memchain *pchain); + +void boost_cont_multidealloc(boost_cont_memchain *pchain); + +size_t boost_cont_footprint(); + +size_t boost_cont_allocated_memory(); + +size_t boost_cont_chunksize(const void *p); + +int boost_cont_all_deallocated(); + +boost_cont_malloc_stats_t boost_cont_malloc_stats(); + +size_t boost_cont_in_use_memory(); + +int boost_cont_trim(size_t pad); + +int boost_cont_mallopt(int parameter_number, int parameter_value); + +int boost_cont_grow + (void* oldmem, size_t minbytes, size_t maxbytes, size_t *received); + +int boost_cont_shrink + (void* oldmem, size_t minbytes, size_t maxbytes, size_t *received, int do_commit); + +void* boost_cont_alloc + (size_t minbytes, size_t preferred_bytes, size_t *received_bytes); + +int boost_cont_malloc_check(); + +boost_cont_command_ret_t boost_cont_allocation_command ( allocation_type command , size_t sizeof_object , size_t limit_objects @@ -312,7 +290,17 @@ BOOST_CONTAINER_DECL boost_cont_command_ret_t boost_cont_allocation_command , void *reuse_ptr ); -BOOST_CONTAINER_DECL int boost_cont_mallopt(int param_number, int value); +void *boost_cont_sync_create(); + +void boost_cont_sync_destroy(void *sync); + +int boost_cont_sync_lock(void *sync); + +void boost_cont_sync_unlock(void *sync); + +int boost_cont_global_sync_lock(); + +void boost_cont_global_sync_unlock(); #ifdef __cplusplus } //extern "C" { diff --git a/boost/container/detail/alloc_lib_auto_link.hpp b/boost/container/detail/alloc_lib_auto_link.hpp deleted file mode 100644 index aea99a65c3..0000000000 --- a/boost/container/detail/alloc_lib_auto_link.hpp +++ /dev/null @@ -1,24 +0,0 @@ -////////////////////////////////////////////////////////////////////////////// -// -// (C) Copyright Ion Gaztanaga 2005-2013. Distributed under the Boost -// Software License, Version 1.0. (See accompanying file -// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -// -// See http://www.boost.org/libs/container for documentation. -// -////////////////////////////////////////////////////////////////////////////// -#ifndef BOOST_CONTAINER_DETAIL_BOOST_CONT_EXT_AUTO_LINK_HPP -#define BOOST_CONTAINER_DETAIL_BOOST_CONT_EXT_AUTO_LINK_HPP - -#ifndef BOOST_CONFIG_HPP -# include -#endif - -#if defined(BOOST_HAS_PRAGMA_ONCE) -# pragma once -#endif - -#include -#include - -#endif //#ifndef BOOST_CONTAINER_DETAIL_BOOST_CONT_EXT_AUTO_LINK_HPP diff --git a/boost/container/detail/auto_link.hpp b/boost/container/detail/auto_link.hpp index da078e8342..264b1ba112 100644 --- a/boost/container/detail/auto_link.hpp +++ b/boost/container/detail/auto_link.hpp @@ -18,6 +18,13 @@ # pragma once #endif +//Define BOOST_CONTAINER_DYNAMIC_LINKING which is independent from BOOST_*_NO_LIB +//and is needed is some tests that need to disable some checks (like operator new replacements) +//that don't work across DLL boundaries +#if defined(BOOST_ALL_DYN_LINK) || defined(BOOST_CONTAINER_DYN_LINK) +# define BOOST_CONTAINER_DYNAMIC_LINKING +#endif + // // Automatically link to the correct build variant where possible. // @@ -27,12 +34,14 @@ // once it's done with it: // #define BOOST_LIB_NAME boost_container + // // If we're importing code from a dll, then tell auto_link.hpp about it: // -#if defined(BOOST_ALL_DYN_LINK) || defined(BOOST_CONTAINER_DYN_LINK) +#if defined(BOOST_CONTAINER_DYNAMIC_LINKING) # define BOOST_DYN_LINK #endif + // // And include the header that does the work: // diff --git a/boost/container/detail/block_list.hpp b/boost/container/detail/block_list.hpp new file mode 100644 index 0000000000..1a6057cb4a --- /dev/null +++ b/boost/container/detail/block_list.hpp @@ -0,0 +1,139 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2015-2015. 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_BLOCK_LIST_HEADER +#define BOOST_CONTAINER_DETAIL_BLOCK_LIST_HEADER + +#ifndef BOOST_CONFIG_HPP +# include +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + +#include +#include +#include +#include +#include +#include +#include +#include + +#include + +namespace boost { +namespace container { +namespace pmr { + +struct list_node +{ + list_node *next; + list_node *previous; +}; + +struct list_node_traits +{ + typedef list_node node; + typedef list_node* node_ptr; + typedef const list_node* const_node_ptr; + + static node_ptr get_next(const_node_ptr n) + { return n->next; } + + static node_ptr get_previous(const_node_ptr n) + { return n->previous; } + + static void set_next(const node_ptr & n, const node_ptr & next) + { n->next = next; } + + static void set_previous(const node_ptr & n, const node_ptr & previous) + { n->previous = previous; } +}; + +struct block_list_header + : public list_node +{ + std::size_t size; +}; + +typedef bi::circular_list_algorithms list_algo; + + +template +class block_list_base +{ + list_node m_list; + + static const std::size_t MaxAlignMinus1 = memory_resource::max_align-1u; + + public: + + static const std::size_t header_size = std::size_t(sizeof(DerivedFromBlockListHeader) + MaxAlignMinus1) & std::size_t(~MaxAlignMinus1); + + explicit block_list_base() + { list_algo::init_header(&m_list); } + + #if !defined(BOOST_NO_CXX11_DELETED_FUNCTIONS) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) + block_list_base(const block_list_base&) = delete; + block_list_base operator=(const block_list_base&) = delete; + #else + private: + block_list_base (const block_list_base&); + block_list_base operator=(const block_list_base&); + public: + #endif + + ~block_list_base() + {} + + void *allocate(std::size_t size, memory_resource &mr) + { + if((size_t(-1) - header_size) < size) + throw_bad_alloc(); + void *p = mr.allocate(size+header_size); + block_list_header &mb = *::new((void*)p) DerivedFromBlockListHeader; + mb.size = size+header_size; + list_algo::link_after(&m_list, &mb); + return (char *)p + header_size; + } + + void deallocate(void *p, memory_resource &mr) BOOST_NOEXCEPT + { + DerivedFromBlockListHeader *pheader = static_cast + (static_cast((char*)p - header_size)); + list_algo::unlink(pheader); + const std::size_t size = pheader->size; + static_cast(pheader)->~DerivedFromBlockListHeader(); + mr.deallocate(pheader, size, memory_resource::max_align); + } + + void release(memory_resource &mr) BOOST_NOEXCEPT + { + list_node *n = list_algo::node_traits::get_next(&m_list); + while(n != &m_list){ + DerivedFromBlockListHeader &d = static_cast(*n); + n = list_algo::node_traits::get_next(n); + std::size_t size = d.size; + d.~DerivedFromBlockListHeader(); + mr.deallocate(reinterpret_cast(&d), size, memory_resource::max_align); + } + list_algo::init_header(&m_list); + } +}; + +} //namespace pmr { +} //namespace container { +} //namespace boost { + +#include + +#endif //BOOST_CONTAINER_DETAIL_BLOCK_LIST_HEADER diff --git a/boost/container/detail/block_slist.hpp b/boost/container/detail/block_slist.hpp new file mode 100644 index 0000000000..278e6414a7 --- /dev/null +++ b/boost/container/detail/block_slist.hpp @@ -0,0 +1,157 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2015-2015. 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_BLOCK_SLIST_HEADER +#define BOOST_CONTAINER_DETAIL_BLOCK_SLIST_HEADER + +#ifndef BOOST_CONFIG_HPP +# include +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + + +#include +#include +#include +#include +#include + +#include +#include +#include + +#include + +namespace boost { +namespace container { +namespace pmr { + +struct slist_node +{ + slist_node *next; +}; + +struct slist_node_traits +{ + typedef slist_node node; + typedef slist_node* node_ptr; + typedef const slist_node* const_node_ptr; + + static node_ptr get_next(const_node_ptr n) + { return n->next; } + + static void set_next(const node_ptr & n, const node_ptr & next) + { n->next = next; } +}; + +struct block_slist_header + : public slist_node +{ + std::size_t size; +}; + +typedef bi::linear_slist_algorithms slist_algo; + +template +class block_slist_base +{ + slist_node m_slist; + + static const std::size_t MaxAlignMinus1 = memory_resource::max_align-1u; + + public: + + static const std::size_t header_size = std::size_t(sizeof(DerivedFromBlockSlistHeader) + MaxAlignMinus1) & std::size_t(~MaxAlignMinus1); + + explicit block_slist_base() + { slist_algo::init_header(&m_slist); } + + #if !defined(BOOST_NO_CXX11_DELETED_FUNCTIONS) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) + block_slist_base(const block_slist_base&) = delete; + block_slist_base operator=(const block_slist_base&) = delete; + #else + private: + block_slist_base (const block_slist_base&); + block_slist_base operator=(const block_slist_base&); + public: + #endif + + ~block_slist_base() + {} + + void *allocate(std::size_t size, memory_resource &mr) + { + if((size_t(-1) - header_size) < size) + throw_bad_alloc(); + void *p = mr.allocate(size+header_size); + block_slist_header &mb = *::new((void*)p) DerivedFromBlockSlistHeader; + mb.size = size+header_size; + slist_algo::link_after(&m_slist, &mb); + return (char *)p + header_size; + } + + void release(memory_resource &mr) BOOST_NOEXCEPT + { + slist_node *n = slist_algo::node_traits::get_next(&m_slist); + while(n){ + DerivedFromBlockSlistHeader &d = static_cast(*n); + n = slist_algo::node_traits::get_next(n); + std::size_t size = d.block_slist_header::size; + d.~DerivedFromBlockSlistHeader(); + mr.deallocate(reinterpret_cast(&d), size, memory_resource::max_align); + } + slist_algo::init_header(&m_slist); + } +}; + +class block_slist + : public block_slist_base<> +{ + memory_resource &m_upstream_rsrc; + + public: + + explicit block_slist(memory_resource &upstream_rsrc) + : block_slist_base<>(), m_upstream_rsrc(upstream_rsrc) + {} + + #if !defined(BOOST_NO_CXX11_DELETED_FUNCTIONS) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) + block_slist(const block_slist&) = delete; + block_slist operator=(const block_slist&) = delete; + #else + private: + block_slist (const block_slist&); + block_slist operator=(const block_slist&); + public: + #endif + + ~block_slist() + { this->release(); } + + void *allocate(std::size_t size) + { return this->block_slist_base<>::allocate(size, m_upstream_rsrc); } + + void release() BOOST_NOEXCEPT + { return this->block_slist_base<>::release(m_upstream_rsrc); } + + memory_resource& upstream_resource() const BOOST_NOEXCEPT + { return m_upstream_rsrc; } +}; + +} //namespace pmr { +} //namespace container { +} //namespace boost { + +#include + +#endif //BOOST_CONTAINER_DETAIL_BLOCK_SLIST_HEADER diff --git a/boost/container/detail/config_begin.hpp b/boost/container/detail/config_begin.hpp index 3f509e320b..7e3e03fa64 100644 --- a/boost/container/detail/config_begin.hpp +++ b/boost/container/detail/config_begin.hpp @@ -25,6 +25,7 @@ #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 : 4284) // odd return type for operator-> + #pragma warning (disable : 4290) // C++ exception specification ignored except to indicate a function is not __declspec(nothrow) #pragma warning (disable : 4324) // structure was padded due to __declspec(align( #pragma warning (disable : 4345) // behavior change: an object of POD type constructed with an initializer of the form () will be default-initialized #pragma warning (disable : 4355) // "this" : used in base member initializer list diff --git a/boost/container/detail/copy_move_algo.hpp b/boost/container/detail/copy_move_algo.hpp index 23fa730838..f590a8aaf3 100644 --- a/boost/container/detail/copy_move_algo.hpp +++ b/boost/container/detail/copy_move_algo.hpp @@ -252,15 +252,15 @@ struct disable_if_memzero_initializable template struct enable_if_trivially_destructible - : enable_if_c < false/*container_detail::is_trivially_destructible - ::value_type>::value*/ + : enable_if_c < container_detail::is_trivially_destructible + ::value_type>::value , R> {}; template struct disable_if_trivially_destructible - : enable_if_c ::value_type>::value*/ + : enable_if_c ::value_type>::value , R> {}; diff --git a/boost/container/detail/dispatch_uses_allocator.hpp b/boost/container/detail/dispatch_uses_allocator.hpp new file mode 100644 index 0000000000..3000f7cb27 --- /dev/null +++ b/boost/container/detail/dispatch_uses_allocator.hpp @@ -0,0 +1,293 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2015-2015. 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_DISPATCH_USES_ALLOCATOR_HPP +#define BOOST_CONTAINER_DISPATCH_USES_ALLOCATOR_HPP + +#if defined (_MSC_VER) +# pragma once +#endif + +#include +#include + +#include +#include + +#include +#include +#include +#include + +#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) +#include +#endif +#include + +#include + +namespace boost { namespace container { + +namespace container_detail { + + +// Check if we can detect is_convertible using advanced SFINAE expressions +#if !defined(BOOST_NO_CXX11_DECLTYPE) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + + //! Code inspired by Mathias Gaunard's is_convertible.cpp found in the Boost mailing list + //! http://boost.2283326.n4.nabble.com/type-traits-is-constructible-when-decltype-is-supported-td3575452.html + //! Thanks Mathias! + + //With variadic templates, we need a single class to implement the trait + template + struct is_constructible + { + typedef char yes_type; + struct no_type + { char padding[2]; }; + + template + struct dummy; + + template + static decltype(X(boost::move_detail::declval()...), true_type()) test(int); + + template + static no_type test(...); + + static const bool value = sizeof(test(0)) == sizeof(yes_type); + }; + + template + struct is_constructible_with_allocator_prefix + : is_constructible + {}; + +#else // #if !defined(BOOST_NO_SFINAE_EXPR) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + + //Without advanced SFINAE expressions, we can't use is_constructible + //so backup to constructible_with_allocator_xxx + + #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + + template + struct is_constructible_with_allocator_prefix + : constructible_with_allocator_prefix + {}; + + template + struct is_constructible_with_allocator_suffix + : constructible_with_allocator_suffix + {}; + + #else // #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + + template + struct is_constructible_with_allocator_prefix + : constructible_with_allocator_prefix + {}; + + template + struct is_constructible_with_allocator_suffix + : constructible_with_allocator_suffix + {}; + + #endif // #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + +#endif // #if !defined(BOOST_NO_SFINAE_EXPR) + +#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + +template < typename ConstructAlloc + , typename ArgAlloc + , typename T + , class ...Args + > +inline typename container_detail::enable_if_and + < void + , container_detail::is_not_pair + , container_detail::not_< uses_allocator > + >::type dispatch_uses_allocator + ( ConstructAlloc & construct_alloc, BOOST_FWD_REF(ArgAlloc) arg_alloc, T* p, BOOST_FWD_REF(Args)...args) +{ + (void)arg_alloc; + allocator_traits::construct(construct_alloc, p, ::boost::forward(args)...); +} + +// allocator_arg_t +template < typename ConstructAlloc + , typename ArgAlloc + , typename T + , class ...Args + > +inline typename container_detail::enable_if_and + < void + , container_detail::is_not_pair + , uses_allocator + , is_constructible_with_allocator_prefix + >::type dispatch_uses_allocator + ( ConstructAlloc& construct_alloc, BOOST_FWD_REF(ArgAlloc) arg_alloc, T* p, BOOST_FWD_REF(Args) ...args) +{ + allocator_traits::construct + ( construct_alloc, p, allocator_arg + , ::boost::forward(arg_alloc), ::boost::forward(args)...); +} + +// allocator suffix +template < typename ConstructAlloc + , typename ArgAlloc + , typename T + , class ...Args + > +inline typename container_detail::enable_if_and + < void + , container_detail::is_not_pair + , uses_allocator + , container_detail::not_ > + >::type dispatch_uses_allocator + ( ConstructAlloc& construct_alloc, BOOST_FWD_REF(ArgAlloc) arg_alloc, T* p, BOOST_FWD_REF(Args)...args) +{ + allocator_traits::construct + (construct_alloc, p, ::boost::forward(args)..., ::boost::forward(arg_alloc)); +} + +#else //#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + +#define BOOST_CONTAINER_SCOPED_ALLOCATOR_DISPATCH_USES_ALLOCATOR_CODE(N) \ + template \ + inline typename container_detail::enable_if_and\ + < void\ + , container_detail::is_not_pair\ + , container_detail::not_ >\ + >::type\ + dispatch_uses_allocator\ + (ConstructAlloc &construct_alloc, BOOST_FWD_REF(ArgAlloc) arg_alloc, T* p BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ + {\ + (void)arg_alloc;\ + allocator_traits::construct(construct_alloc, p BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ + }\ +// +BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_SCOPED_ALLOCATOR_DISPATCH_USES_ALLOCATOR_CODE) +#undef BOOST_CONTAINER_SCOPED_ALLOCATOR_DISPATCH_USES_ALLOCATOR_CODE + +#define BOOST_CONTAINER_SCOPED_ALLOCATOR_DISPATCH_USES_ALLOCATOR_CODE(N) \ + template < typename ConstructAlloc, typename ArgAlloc, typename T BOOST_MOVE_I##N BOOST_MOVE_CLASS##N >\ + inline typename container_detail::enable_if_and\ + < void\ + , container_detail::is_not_pair\ + , uses_allocator\ + , is_constructible_with_allocator_prefix\ + >::type\ + dispatch_uses_allocator\ + (ConstructAlloc& construct_alloc, BOOST_FWD_REF(ArgAlloc) arg_alloc, T* p BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ + {\ + allocator_traits::construct\ + (construct_alloc, p, allocator_arg, ::boost::forward(arg_alloc) BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ + }\ +// +BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_SCOPED_ALLOCATOR_DISPATCH_USES_ALLOCATOR_CODE) +#undef BOOST_CONTAINER_SCOPED_ALLOCATOR_DISPATCH_USES_ALLOCATOR_CODE + +#define BOOST_CONTAINER_SCOPED_ALLOCATOR_DISPATCH_USES_ALLOCATOR_CODE(N) \ + template < typename ConstructAlloc, typename ArgAlloc, typename T BOOST_MOVE_I##N BOOST_MOVE_CLASS##N >\ + inline typename container_detail::enable_if_and\ + < void\ + , container_detail::is_not_pair\ + , uses_allocator\ + , container_detail::not_ >\ + >::type\ + dispatch_uses_allocator\ + (ConstructAlloc& construct_alloc, BOOST_FWD_REF(ArgAlloc) arg_alloc, T* p BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ + {\ + allocator_traits::construct\ + (construct_alloc, p BOOST_MOVE_I##N BOOST_MOVE_FWD##N, ::boost::forward(arg_alloc));\ + }\ +// +BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_SCOPED_ALLOCATOR_DISPATCH_USES_ALLOCATOR_CODE) +#undef BOOST_CONTAINER_SCOPED_ALLOCATOR_DISPATCH_USES_ALLOCATOR_CODE + +#endif //#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) + +template < typename ConstructAlloc + , typename ArgAlloc + , typename Pair + > inline +BOOST_CONTAINER_DOC1ST(void, typename container_detail::enable_if >::type) + dispatch_uses_allocator + ( ConstructAlloc & construct_alloc + , ArgAlloc & arg_alloc + , Pair* p) +{ + (dispatch_uses_allocator)(construct_alloc, arg_alloc, container_detail::addressof(p->first)); + BOOST_TRY{ + (dispatch_uses_allocator)(construct_alloc, arg_alloc, container_detail::addressof(p->second)); + } + BOOST_CATCH(...) { + allocator_traits::destroy(construct_alloc, container_detail::addressof(p->first)); + BOOST_RETHROW + } + BOOST_CATCH_END +} + + +template < typename ConstructAlloc + , typename ArgAlloc + , class Pair, class U, class V> +BOOST_CONTAINER_DOC1ST(void, typename container_detail::enable_if >::type) + dispatch_uses_allocator + ( ConstructAlloc & construct_alloc + , ArgAlloc & arg_alloc + , Pair* p, BOOST_FWD_REF(U) x, BOOST_FWD_REF(V) y) +{ + (dispatch_uses_allocator)(construct_alloc, arg_alloc, container_detail::addressof(p->first), ::boost::forward(x)); + BOOST_TRY{ + (dispatch_uses_allocator)(construct_alloc, arg_alloc, container_detail::addressof(p->second), ::boost::forward(y)); + } + BOOST_CATCH(...){ + allocator_traits::destroy(construct_alloc, container_detail::addressof(p->first)); + BOOST_RETHROW + } + BOOST_CATCH_END +} + +template < typename ConstructAlloc + , typename ArgAlloc + , class Pair, class Pair2> +BOOST_CONTAINER_DOC1ST(void, typename container_detail::enable_if< container_detail::is_pair >::type) + dispatch_uses_allocator + (ConstructAlloc & construct_alloc + , ArgAlloc & arg_alloc + , Pair* p, Pair2& x) +{ (dispatch_uses_allocator)(construct_alloc, arg_alloc, p, x.first, x.second); } + +template < typename ConstructAlloc + , typename ArgAlloc + , class Pair, class Pair2> +typename container_detail::enable_if_and + < void + , container_detail::is_pair + , container_detail::not_ > >::type //This is needed for MSVC10 and ambiguous overloads + dispatch_uses_allocator + (ConstructAlloc & construct_alloc + , ArgAlloc & arg_alloc + , Pair* p, BOOST_RV_REF_BEG Pair2 BOOST_RV_REF_END x) +{ (dispatch_uses_allocator)(construct_alloc, arg_alloc, p, ::boost::move(x.first), ::boost::move(x.second)); } + +//template +//void dispatch_uses_allocator( ConstructAlloc & construct_alloc, ArgAlloc & arg_alloc +// , pair* p, piecewise_construct_t, tuple x, tuple y); + +} //namespace container_detail + +}} // namespace boost { namespace container { + +#include + +#endif // BOOST_CONTAINER_DISPATCH_USES_ALLOCATOR_HPP diff --git a/boost/container/detail/dlmalloc.hpp b/boost/container/detail/dlmalloc.hpp new file mode 100644 index 0000000000..15086c399f --- /dev/null +++ b/boost/container/detail/dlmalloc.hpp @@ -0,0 +1,103 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2015-2015. 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_ALLOC_LIB_HPP +#define BOOST_CONTAINER_DETAIL_ALLOC_LIB_HPP + +#ifndef BOOST_CONFIG_HPP +# include +#endif + +#if defined(BOOST_HAS_PRAGMA_ONCE) +# pragma once +#endif + +#include +#include +#include + +#include + +namespace boost{ +namespace container{ + +typedef boost_cont_command_ret_t dlmalloc_command_ret_t; +typedef boost_cont_memchain dlmalloc_memchain; +typedef boost_cont_memchain_it dlmalloc_memchain_it; +typedef boost_cont_malloc_stats_t dlmalloc_malloc_stats_t; + +BOOST_CONTAINER_DECL size_t dlmalloc_size(const void *p); + +BOOST_CONTAINER_DECL void* dlmalloc_malloc(size_t bytes); + +BOOST_CONTAINER_DECL void dlmalloc_free(void* mem); + +BOOST_CONTAINER_DECL void* dlmalloc_memalign(size_t bytes, size_t alignment); + +BOOST_CONTAINER_DECL int dlmalloc_multialloc_nodes + (size_t n_elements, size_t elem_size, size_t contiguous_elements, boost_cont_memchain *pchain); + +BOOST_CONTAINER_DECL int dlmalloc_multialloc_arrays + (size_t n_elements, const size_t *sizes, size_t sizeof_element, size_t contiguous_elements, boost_cont_memchain *pchain); + +BOOST_CONTAINER_DECL void dlmalloc_multidealloc(boost_cont_memchain *pchain); + +BOOST_CONTAINER_DECL size_t dlmalloc_footprint(); + +BOOST_CONTAINER_DECL size_t dlmalloc_allocated_memory(); + +BOOST_CONTAINER_DECL size_t dlmalloc_chunksize(const void *p); + +BOOST_CONTAINER_DECL int dlmalloc_all_deallocated(); + +BOOST_CONTAINER_DECL boost_cont_malloc_stats_t dlmalloc_malloc_stats(); + +BOOST_CONTAINER_DECL size_t dlmalloc_in_use_memory(); + +BOOST_CONTAINER_DECL int dlmalloc_trim(size_t pad); + +BOOST_CONTAINER_DECL int dlmalloc_mallopt(int parameter_number, int parameter_value); + +BOOST_CONTAINER_DECL int dlmalloc_grow(void* oldmem, size_t minbytes, size_t maxbytes, size_t *received); + +BOOST_CONTAINER_DECL int dlmalloc_shrink(void* oldmem, size_t minbytes, size_t maxbytes, size_t *received, int do_commit); + +BOOST_CONTAINER_DECL void* dlmalloc_alloc(size_t minbytes, size_t preferred_bytes, size_t *received_bytes); + +BOOST_CONTAINER_DECL int dlmalloc_malloc_check(); + +BOOST_CONTAINER_DECL boost_cont_command_ret_t dlmalloc_allocation_command + ( allocation_type command + , size_t sizeof_object + , size_t limit_objects + , size_t preferred_objects + , size_t *received_objects + , void *reuse_ptr + ); + +BOOST_CONTAINER_DECL int dlmalloc_mallopt(int param_number, int value); + +BOOST_CONTAINER_DECL void *dlmalloc_sync_create(); + +BOOST_CONTAINER_DECL void dlmalloc_sync_destroy(void *sync); + +BOOST_CONTAINER_DECL bool dlmalloc_sync_lock(void *sync); + +BOOST_CONTAINER_DECL void dlmalloc_sync_unlock(void *sync); + +BOOST_CONTAINER_DECL bool dlmalloc_global_sync_lock(); + +BOOST_CONTAINER_DECL void dlmalloc_global_sync_unlock(); + +} //namespace container{ +} //namespace boost{ + +#include + +#endif //BOOST_CONTAINER_DETAIL_ALLOC_LIB_HPP diff --git a/boost/container/detail/flat_tree.hpp b/boost/container/detail/flat_tree.hpp index f27421125f..4c48c8b7d3 100644 --- a/boost/container/detail/flat_tree.hpp +++ b/boost/container/detail/flat_tree.hpp @@ -1,6 +1,6 @@ //////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2005-2013. Distributed under the Boost +// (C) Copyright Ion Gaztanaga 2005-2015. 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) // @@ -376,35 +376,39 @@ class flat_tree return i; } - iterator insert_unique(const_iterator pos, const value_type& val) + iterator insert_unique(const_iterator hint, const value_type& val) { + BOOST_ASSERT(this->priv_in_range_or_end(hint)); std::pair ret; insert_commit_data data; - return this->priv_insert_unique_prepare(pos, val, data) + return this->priv_insert_unique_prepare(hint, val, data) ? this->priv_insert_commit(data, val) : iterator(vector_iterator_get_ptr(data.position)); } - iterator insert_unique(const_iterator pos, BOOST_RV_REF(value_type) val) + iterator insert_unique(const_iterator hint, BOOST_RV_REF(value_type) val) { + BOOST_ASSERT(this->priv_in_range_or_end(hint)); std::pair ret; insert_commit_data data; - return this->priv_insert_unique_prepare(pos, val, data) + return this->priv_insert_unique_prepare(hint, val, data) ? this->priv_insert_commit(data, boost::move(val)) : iterator(vector_iterator_get_ptr(data.position)); } - iterator insert_equal(const_iterator pos, const value_type& val) + iterator insert_equal(const_iterator hint, const value_type& val) { + BOOST_ASSERT(this->priv_in_range_or_end(hint)); insert_commit_data data; - this->priv_insert_equal_prepare(pos, val, data); + this->priv_insert_equal_prepare(hint, val, data); return this->priv_insert_commit(data, val); } - iterator insert_equal(const_iterator pos, BOOST_RV_REF(value_type) mval) + iterator insert_equal(const_iterator hint, BOOST_RV_REF(value_type) mval) { + BOOST_ASSERT(this->priv_in_range_or_end(hint)); insert_commit_data data; - this->priv_insert_equal_prepare(pos, mval, data); + this->priv_insert_equal_prepare(hint, mval, data); return this->priv_insert_commit(data, boost::move(mval)); } @@ -524,6 +528,7 @@ class flat_tree template iterator emplace_hint_unique(const_iterator hint, BOOST_FWD_REF(Args)... args) { + //hint checked in insert_unique typename aligned_storage::value>::type v; value_type &val = *static_cast(static_cast(&v)); stored_allocator_type &a = this->get_stored_allocator(); @@ -546,6 +551,7 @@ class flat_tree template iterator emplace_hint_equal(const_iterator hint, BOOST_FWD_REF(Args)... args) { + //hint checked in insert_equal typename aligned_storage::value>::type v; value_type &val = *static_cast(static_cast(&v)); stored_allocator_type &a = this->get_stored_allocator(); @@ -732,6 +738,12 @@ class flat_tree { x.swap(y); } private: + + bool priv_in_range_or_end(const_iterator pos) const + { + return (this->begin() <= pos) && (pos <= this->end()); + } + struct insert_commit_data { const_iterator position; diff --git a/boost/container/detail/mutex.hpp b/boost/container/detail/mutex.hpp index f8efa7fe6b..82e8810d0a 100644 --- a/boost/container/detail/mutex.hpp +++ b/boost/container/detail/mutex.hpp @@ -107,7 +107,7 @@ #elif (defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__))) /* Custom spin locks for older gcc on x86 */ - static FORCEINLINE int boost_container_x86_cas_lock(int *sl) { + static inline int boost_container_x86_cas_lock(int *sl) { int ret; int val = 1; int cmp = 0; @@ -118,7 +118,7 @@ return ret; } - static FORCEINLINE void boost_container_x86_clear_lock(int* sl) { + static inline void boost_container_x86_clear_lock(int* sl) { assert(*sl != 0); int prev = 0; int ret; diff --git a/boost/container/detail/pair.hpp b/boost/container/detail/pair.hpp index 35e8846caa..17766f35cb 100644 --- a/boost/container/detail/pair.hpp +++ b/boost/container/detail/pair.hpp @@ -27,52 +27,12 @@ #include #include #include -#include +#include #include //swap #include //pair #include -/* -namespace boost{ - -template -inline rv< std::pair > &move(std::pair &r) -{ - return reinterpret_cast< rv< std::pair > &>(r); -} - -template -inline rv< std::pair > &move(rv< std::pair > &r) -{ - return r; -} - -template -inline typename ::boost::move_detail::enable_if_and - < T & - , boost::container::container_detail::is_std_pair - , ::boost::move_detail::is_rv - >::type - forward(const typename ::boost::move_detail::identity::type &x) BOOST_NOEXCEPT -{ - return const_cast(x); -} - -template -inline typename ::boost::move_detail::enable_if_and - < const T & - , boost::container::container_detail::is_std_pair - , ::boost::move_detail::is_not_rv - >::type - forward(const typename ::boost::move_detail::identity::type &x) BOOST_NOEXCEPT -{ - return x; -} - -} //namespace boost { -*/ - namespace boost { namespace container { namespace container_detail { @@ -118,36 +78,6 @@ struct is_std_pair< std::pair > struct pair_nat; -struct piecewise_construct_t { }; -static const piecewise_construct_t piecewise_construct = piecewise_construct_t(); - -/* -template -struct pair -{ - template pair(pair&& p); - template - pair(piecewise_construct_t, tuple first_args, - tuple second_args); - - template pair& operator=(const pair& p); - pair& operator=(pair&& p) noexcept(is_nothrow_move_assignable::value && - is_nothrow_move_assignable::value); - template pair& operator=(pair&& p); - - void swap(pair& p) noexcept(noexcept(swap(first, p.first)) && - noexcept(swap(second, p.second))); -}; - -template bool operator==(const pair&, const pair&); -template bool operator!=(const pair&, const pair&); -template bool operator< (const pair&, const pair&); -template bool operator> (const pair&, const pair&); -template bool operator>=(const pair&, const pair&); -template bool operator<=(const pair&, const pair&); -*/ - - template struct pair { diff --git a/boost/container/detail/pool_common_alloc.hpp b/boost/container/detail/pool_common_alloc.hpp index 72e9c8d278..3a3c80a78f 100644 --- a/boost/container/detail/pool_common_alloc.hpp +++ b/boost/container/detail/pool_common_alloc.hpp @@ -25,7 +25,7 @@ #include #include -#include +#include #include namespace boost{ @@ -44,15 +44,15 @@ struct fake_segment_manager typedef boost::container::container_detail:: basic_multiallocation_chain multiallocation_chain; static void deallocate(void_pointer p) - { boost_cont_free(p); } + { dlmalloc_free(p); } static void deallocate_many(multiallocation_chain &chain) { std::size_t size = chain.size(); std::pair ptrs = chain.extract_data(); - boost_cont_memchain dlchain; + dlmalloc_memchain dlchain; BOOST_CONTAINER_MEMCHAIN_INIT_FROM(&dlchain, ptrs.first, ptrs.second, size); - boost_cont_multidealloc(&dlchain); + dlmalloc_multidealloc(&dlchain); } typedef std::ptrdiff_t difference_type; @@ -60,7 +60,7 @@ struct fake_segment_manager static void *allocate_aligned(std::size_t nbytes, std::size_t alignment) { - void *ret = boost_cont_memalign(nbytes, alignment); + void *ret = dlmalloc_memalign(nbytes, alignment); if(!ret) boost::container::throw_bad_alloc(); return ret; @@ -68,7 +68,7 @@ struct fake_segment_manager static void *allocate(std::size_t nbytes) { - void *ret = boost_cont_malloc(nbytes); + void *ret = dlmalloc_malloc(nbytes); if(!ret) boost::container::throw_bad_alloc(); return ret; diff --git a/boost/container/detail/pool_resource.hpp b/boost/container/detail/pool_resource.hpp new file mode 100644 index 0000000000..e5f59f5186 --- /dev/null +++ b/boost/container/detail/pool_resource.hpp @@ -0,0 +1,191 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2015-2015. 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_POOL_RESOURCE_HPP +#define BOOST_CONTAINER_POOL_RESOURCE_HPP + +#if defined (_MSC_VER) +# pragma once +#endif + +#include +#include +#include +#include +#include + +#include + +namespace boost { +namespace container { +namespace pmr { + +#if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) + +class pool_data_t; + +static const std::size_t pool_options_minimum_max_blocks_per_chunk = 1u; +static const std::size_t pool_options_default_max_blocks_per_chunk = 32u; +static const std::size_t pool_options_minimum_largest_required_pool_block = + memory_resource::max_align > 2*sizeof(void*) ? memory_resource::max_align : 2*sizeof(void*); +static const std::size_t pool_options_default_largest_required_pool_block = + pool_options_minimum_largest_required_pool_block > 4096u + ? pool_options_minimum_largest_required_pool_block : 4096u; + +#endif //BOOST_CONTAINER_DOXYGEN_INVOKED + +class pool_resource +{ + typedef block_list_base<> block_list_base_t; + + pool_options m_options; + memory_resource& m_upstream; + block_list_base_t m_oversized_list; + pool_data_t *m_pool_data; + std::size_t m_pool_count; + + static void priv_limit_option(std::size_t &val, std::size_t min, std::size_t max); + static std::size_t priv_pool_index(std::size_t block_size); + static std::size_t priv_pool_block(std::size_t index); + + void priv_fix_options(); + void priv_init_pools(); + void priv_constructor_body(); + + public: + + //! Requires: `upstream` is the address of a valid memory resource. + //! + //! Effects: Constructs a pool resource object that will obtain memory + //! from upstream whenever the pool resource is unable to satisfy a memory + //! request from its own internal data structures. The resulting object will hold + //! a copy of upstream, but will not own the resource to which upstream points. + //! [ Note: The intention is that calls to upstream->allocate() will be + //! substantially fewer than calls to this->allocate() in most cases. - end note + //! The behavior of the pooling mechanism is tuned according to the value of + //! the opts argument. + //! + //! Throws: Nothing unless upstream->allocate() throws. It is unspecified if + //! or under what conditions this constructor calls upstream->allocate(). + pool_resource(const pool_options& opts, memory_resource* upstream) BOOST_NOEXCEPT; + + //! Effects: Same as + //! `pool_resource(pool_options(), get_default_resource())`. + pool_resource() BOOST_NOEXCEPT; + + //! Effects: Same as + //! `pool_resource(pool_options(), upstream)`. + explicit pool_resource(memory_resource* upstream) BOOST_NOEXCEPT; + + //! Effects: Same as + //! `pool_resource(opts, get_default_resource())`. + explicit pool_resource(const pool_options& opts) BOOST_NOEXCEPT; + + #if !defined(BOOST_NO_CXX11_DELETED_FUNCTIONS) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) + pool_resource(const pool_resource&) = delete; + pool_resource operator=(const pool_resource&) = delete; + #else + private: + pool_resource (const pool_resource&); + pool_resource operator=(const pool_resource&); + public: + #endif + + //! Effects: Calls + //! `this->release()`. + virtual ~pool_resource(); + + //! Effects: Calls Calls `upstream_resource()->deallocate()` as necessary + //! to release all allocated memory. [ Note: memory is released back to + //! `upstream_resource()` even if deallocate has not been called for some + //! of the allocated blocks. - end note ] + void release(); + + //! Returns: The value of the upstream argument provided to the + //! constructor of this object. + memory_resource* upstream_resource() const; + + //! Returns: The options that control the pooling behavior of this resource. + //! The values in the returned struct may differ from those supplied to the pool + //! resource constructor in that values of zero will be replaced with + //! implementation-defined defaults and sizes may be rounded to unspecified granularity. + pool_options options() const; + + public: //public so that [un]synchronized_pool_resource can use them + + //! Returns: A pointer to allocated storage with a size of at least `bytes`. + //! The size and alignment of the allocated memory shall meet the requirements for + //! a class derived from `memory_resource`. + //! + //! Effects: If the pool selected for a block of size bytes is unable to + //! satisfy the memory request from its own internal data structures, it will call + //! `upstream_resource()->allocate()` to obtain more memory. If `bytes` is larger + //! than that which the largest pool can handle, then memory will be allocated + //! using `upstream_resource()->allocate()`. + //! + //! Throws: Nothing unless `upstream_resource()->allocate()` throws. + virtual void* do_allocate(std::size_t bytes, std::size_t alignment); + + //! Effects: Return the memory at p to the pool. It is unspecified if or under + //! what circumstances this operation will result in a call to + //! `upstream_resource()->deallocate()`. + //! + //! Throws: Nothing. + virtual void do_deallocate(void* p, std::size_t bytes, std::size_t alignment); + + //! Returns: + //! `this == dynamic_cast(&other)`. + virtual bool do_is_equal(const memory_resource& other) const BOOST_NOEXCEPT; + + //Non-standard observers + public: + //! Returns: The number of pools that will be used in the pool resource. + //! + //! Note: Non-standard extension. + std::size_t pool_count() const; + + //! Returns: The index of the pool that will be used to serve the allocation of `bytes`. + //! from the pool specified by `pool_index`. Returns `pool_count()` if `bytes` is bigger + //! than `options().largest_required_pool_block` (no pool will be used to serve this). + //! + //! Note: Non-standard extension. + std::size_t pool_index(std::size_t bytes) const; + + //! Requires: `pool_idx < pool_index()` + //! + //! Returns: The number blocks that will be allocated in the next chunk + //! from the pool specified by `pool_idx`. + //! + //! Note: Non-standard extension. + std::size_t pool_next_blocks_per_chunk(std::size_t pool_idx) const; + + //! Requires: `pool_idx < pool_index()` + //! + //! Returns: The number of bytes of the block that the specified `pool_idx` pool manages. + //! + //! Note: Non-standard extension. + std::size_t pool_block(std::size_t pool_idx) const; + + //! Requires: `pool_idx < pool_index()` + //! + //! Returns: The number of blocks that the specified `pool_idx` pool has cached + //! and will be served without calling the upstream_allocator. + //! + //! Note: Non-standard extension. + std::size_t pool_cached_blocks(std::size_t pool_idx) const; +}; + +} //namespace pmr { +} //namespace container { +} //namespace boost { + +#include + +#endif //BOOST_CONTAINER_POOL_RESOURCE_HPP diff --git a/boost/container/detail/std_fwd.hpp b/boost/container/detail/std_fwd.hpp index 1277df071f..09678123ff 100644 --- a/boost/container/detail/std_fwd.hpp +++ b/boost/container/detail/std_fwd.hpp @@ -23,26 +23,8 @@ // Standard predeclarations ////////////////////////////////////////////////////////////////////////////// -#if defined(_LIBCPP_VERSION) - #define BOOST_CONTAINER_CLANG_INLINE_STD_NS - #pragma GCC diagnostic push - #if defined(__clang__) - #pragma GCC diagnostic ignored "-Wc++11-extensions" - #endif - #define BOOST_CONTAINER_STD_NS_BEG _LIBCPP_BEGIN_NAMESPACE_STD - #define BOOST_CONTAINER_STD_NS_END _LIBCPP_END_NAMESPACE_STD -#elif defined(BOOST_GNU_STDLIB) && defined(_GLIBCXX_BEGIN_NAMESPACE_VERSION) //GCC >= 4.6 - #define BOOST_CONTAINER_STD_NS_BEG namespace std _GLIBCXX_VISIBILITY(default) { _GLIBCXX_BEGIN_NAMESPACE_VERSION - #define BOOST_CONTAINER_STD_NS_END _GLIBCXX_END_NAMESPACE_VERSION } // namespace -#elif defined(BOOST_GNU_STDLIB) && defined(_GLIBCXX_BEGIN_NAMESPACE) //GCC >= 4.2 - #define BOOST_CONTAINER_STD_NS_BEG _GLIBCXX_BEGIN_NAMESPACE(std) - #define BOOST_CONTAINER_STD_NS_END _GLIBCXX_END_NAMESPACE -#else - #define BOOST_CONTAINER_STD_NS_BEG namespace std{ - #define BOOST_CONTAINER_STD_NS_END } -#endif - -BOOST_CONTAINER_STD_NS_BEG +#include +BOOST_MOVE_STD_NS_BEG template class allocator; @@ -66,11 +48,9 @@ class insert_iterator; struct allocator_arg_t; -BOOST_CONTAINER_STD_NS_END +struct piecewise_construct_t; -#ifdef BOOST_CONTAINER_CLANG_INLINE_STD_NS - #pragma GCC diagnostic pop - #undef BOOST_CONTAINER_CLANG_INLINE_STD_NS -#endif //BOOST_CONTAINER_CLANG_INLINE_STD_NS +BOOST_MOVE_STD_NS_END +#include #endif //#ifndef BOOST_CONTAINER_DETAIL_STD_FWD_HPP diff --git a/boost/container/detail/tree.hpp b/boost/container/detail/tree.hpp index c90202973a..c2d6b1d17d 100644 --- a/boost/container/detail/tree.hpp +++ b/boost/container/detail/tree.hpp @@ -1,6 +1,6 @@ ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2005-2013. Distributed under the Boost +// (C) Copyright Ion Gaztanaga 2005-2015. 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) // @@ -413,8 +413,11 @@ struct key_node_compare { return node.get_data(); } template - typename enable_if_c::value, const T &>::type - key_forward(const T &key) const + #if defined(BOOST_MOVE_HELPERS_RETURN_SFINAE_BROKEN) + const T &key_forward(const T &key, typename enable_if_c::value>::type* =0) const + #else + typename enable_if_c::value, const T &>::type key_forward(const T &key) const + #endif { return key; } template @@ -811,6 +814,7 @@ class tree std::pair insert_unique_check (const_iterator hint, const key_type& key, insert_commit_data &data) { + BOOST_ASSERT((priv_is_linked)(hint)); std::pair ret = this->icont().insert_unique_check(hint.get(), key, KeyNodeCompare(value_comp()), data); return std::pair(iterator(ret.first), ret.second); @@ -861,6 +865,15 @@ class tree private: + bool priv_is_linked(const_iterator const position) const + { + iiterator const cur(position.get()); + return cur == this->icont().end() || + cur == this->icont().root() || + iiterator(cur).go_parent().go_left() == cur || + iiterator(cur).go_parent().go_right() == cur; + } + template void push_back_impl(BOOST_FWD_REF(MovableConvertible) v) { @@ -888,6 +901,7 @@ class tree iterator emplace_unique_hint_impl(const_iterator hint, NodePtr p) { + BOOST_ASSERT((priv_is_linked)(hint)); value_type &v = p->get_data(); insert_commit_data data; std::pair ret = @@ -924,6 +938,7 @@ class tree template iterator emplace_hint_equal(const_iterator hint, BOOST_FWD_REF(Args)... args) { + BOOST_ASSERT((priv_is_linked)(hint)); NodePtr tmp(AllocHolder::create_node(boost::forward(args)...)); scoped_destroy_deallocator destroy_deallocator(tmp, this->node_alloc()); iterator ret(this->icont().insert_equal(hint.get(), *tmp)); @@ -955,6 +970,7 @@ class tree BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ iterator emplace_hint_equal(const_iterator hint BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ {\ + BOOST_ASSERT((priv_is_linked)(hint));\ NodePtr tmp(AllocHolder::create_node(BOOST_MOVE_FWD##N));\ scoped_destroy_deallocator destroy_deallocator(tmp, this->node_alloc());\ iterator ret(this->icont().insert_equal(hint.get(), *tmp));\ @@ -969,6 +985,7 @@ class tree iterator insert_unique(const_iterator hint, const value_type& v) { + BOOST_ASSERT((priv_is_linked)(hint)); insert_commit_data data; std::pair ret = this->insert_unique_check(hint, KeyOfValue()(v), data); @@ -980,6 +997,7 @@ class tree template iterator insert_unique(const_iterator hint, BOOST_FWD_REF(MovableConvertible) v) { + BOOST_ASSERT((priv_is_linked)(hint)); insert_commit_data data; std::pair ret = this->insert_unique_check(hint, KeyOfValue()(v), data); @@ -1016,6 +1034,7 @@ class tree iterator insert_equal(const_iterator hint, const value_type& v) { + BOOST_ASSERT((priv_is_linked)(hint)); NodePtr tmp(AllocHolder::create_node(v)); scoped_destroy_deallocator destroy_deallocator(tmp, this->node_alloc()); iterator ret(this->icont().insert_equal(hint.get(), *tmp)); @@ -1026,6 +1045,7 @@ class tree template iterator insert_equal(const_iterator hint, BOOST_FWD_REF(MovableConvertible) v) { + BOOST_ASSERT((priv_is_linked)(hint)); NodePtr tmp(AllocHolder::create_node(boost::forward(v))); scoped_destroy_deallocator destroy_deallocator(tmp, this->node_alloc()); iterator ret(this->icont().insert_equal(hint.get(), *tmp)); @@ -1041,13 +1061,20 @@ class tree } iterator erase(const_iterator position) - { return iterator(this->icont().erase_and_dispose(position.get(), Destroyer(this->node_alloc()))); } + { + BOOST_ASSERT(position != this->cend() && (priv_is_linked)(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())); } + { + BOOST_ASSERT(first == last || (first != this->cend() && (priv_is_linked)(first))); + BOOST_ASSERT(first == last || (priv_is_linked)(last)); + return iterator(AllocHolder::erase_range(first.get(), last.get(), alloc_version())); + } void clear() { AllocHolder::clear(alloc_version()); } diff --git a/boost/container/detail/type_traits.hpp b/boost/container/detail/type_traits.hpp index e02709ac6e..e1453a6594 100644 --- a/boost/container/detail/type_traits.hpp +++ b/boost/container/detail/type_traits.hpp @@ -30,6 +30,8 @@ namespace boost { namespace container { namespace container_detail { +using ::boost::move_detail::enable_if; +using ::boost::move_detail::enable_if_and; using ::boost::move_detail::is_same; using ::boost::move_detail::is_different; using ::boost::move_detail::is_pointer; diff --git a/boost/container/detail/variadic_templates_tools.hpp b/boost/container/detail/variadic_templates_tools.hpp index ec8b8ceef0..d8c8443038 100644 --- a/boost/container/detail/variadic_templates_tools.hpp +++ b/boost/container/detail/variadic_templates_tools.hpp @@ -54,7 +54,7 @@ class tuple // Construct tuple from another tuple. template tuple(const tuple& other) - : m_head(other.head()), inherited(other.tail()) + : inherited(other.tail()), m_head(other.head()) {} template diff --git a/boost/container/detail/workaround.hpp b/boost/container/detail/workaround.hpp index 026e65d6bb..e1f6156964 100644 --- a/boost/container/detail/workaround.hpp +++ b/boost/container/detail/workaround.hpp @@ -19,8 +19,6 @@ # pragma once #endif -#include - #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)\ && !defined(BOOST_INTERPROCESS_DISABLE_VARIADIC_TMPL) #define BOOST_CONTAINER_PERFECT_FORWARDING @@ -59,6 +57,23 @@ #define BOOST_CONTAINER_DOCIGN(T) T #define BOOST_CONTAINER_DOCONLY(T) -#include +/* + we need to import/export our code only if the user has specifically + asked for it by defining either BOOST_ALL_DYN_LINK if they want all boost + libraries to be dynamically linked, or BOOST_CONTAINER_DYN_LINK + if they want just this one to be dynamically liked: +*/ +#if defined(BOOST_ALL_DYN_LINK) || defined(BOOST_CONTAINER_DYN_LINK) + + /* export if this is our own source, otherwise import: */ + #ifdef BOOST_CONTAINER_SOURCE + # define BOOST_CONTAINER_DECL BOOST_SYMBOL_EXPORT + #else + # define BOOST_CONTAINER_DECL BOOST_SYMBOL_IMPORT + + #endif /* BOOST_CONTAINER_SOURCE */ +#else + #define BOOST_CONTAINER_DECL +#endif /* DYN_LINK */ #endif //#ifndef BOOST_CONTAINER_DETAIL_WORKAROUND_HPP diff --git a/boost/container/flat_map.hpp b/boost/container/flat_map.hpp index ef0e1cb252..afd5a52d33 100644 --- a/boost/container/flat_map.hpp +++ b/boost/container/flat_map.hpp @@ -593,9 +593,12 @@ class flat_map //! //! Complexity: Logarithmic. mapped_type &operator[](key_type &&k) ; - + #elif defined(BOOST_MOVE_HELPERS_RETURN_SFINAE_BROKEN) + //in compilers like GCC 3.4, we can't catch temporaries + mapped_type& operator[](const key_type &k) { return this->priv_subscript(k); } + mapped_type& operator[](BOOST_RV_REF(key_type) k) { return this->priv_subscript(::boost::move(k)); } #else - BOOST_MOVE_CONVERSION_AWARE_CATCH( operator[] , key_type, mapped_type&, this->priv_subscript) + BOOST_MOVE_CONVERSION_AWARE_CATCH( operator[] , key_type, mapped_type&, this->priv_subscript) #endif //! @copydoc ::boost::container::flat_set::nth(size_type) @@ -958,7 +961,7 @@ class flat_map //! Returns: A const_iterator pointing to an element with the key //! equivalent to x, or end() if such an element is not found. //! - //! Complexity: Logarithmic.s + //! Complexity: Logarithmic. const_iterator find(const key_type& x) const { return container_detail::force_copy(m_flat_tree.find(x)); } @@ -971,40 +974,40 @@ class flat_map //! Returns: An iterator pointing to the first element with key not less //! than k, or a.end() if such an element is not found. //! - //! Complexity: Logarithmic + //! Complexity: Logarithmic. iterator lower_bound(const key_type& x) { return container_detail::force_copy(m_flat_tree.lower_bound(x)); } //! Returns: A const iterator pointing to the first element with key not //! less than k, or a.end() if such an element is not found. //! - //! Complexity: Logarithmic + //! Complexity: Logarithmic. const_iterator lower_bound(const key_type& x) const { return container_detail::force_copy(m_flat_tree.lower_bound(x)); } //! Returns: An iterator pointing to the first element with key not less //! than x, or end() if such an element is not found. //! - //! Complexity: Logarithmic + //! Complexity: Logarithmic. iterator upper_bound(const key_type& x) { return container_detail::force_copy(m_flat_tree.upper_bound(x)); } //! Returns: A const iterator pointing to the first element with key not //! less than x, or end() if such an element is not found. //! - //! Complexity: Logarithmic + //! Complexity: Logarithmic. const_iterator upper_bound(const key_type& x) const { return container_detail::force_copy(m_flat_tree.upper_bound(x)); } //! Effects: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). //! - //! Complexity: Logarithmic + //! Complexity: Logarithmic. std::pair equal_range(const key_type& x) { return container_detail::force_copy >(m_flat_tree.lower_bound_range(x)); } //! Effects: Equivalent to std::make_pair(this->lower_bound(k), this->upper_bound(k)). //! - //! Complexity: Logarithmic + //! Complexity: Logarithmic. std::pair equal_range(const key_type& x) const { return container_detail::force_copy >(m_flat_tree.lower_bound_range(x)); } diff --git a/boost/container/flat_set.hpp b/boost/container/flat_set.hpp index 8f592798d2..a99e70786a 100644 --- a/boost/container/flat_set.hpp +++ b/boost/container/flat_set.hpp @@ -968,17 +968,17 @@ class flat_multiset : base_t(static_cast(x)) {} - //! @copydoc ::boost::container::flat_set(flat_set &&) + //! @copydoc ::boost::container::flat_set::flat_set(flat_set &&) flat_multiset(BOOST_RV_REF(flat_multiset) x) : base_t(boost::move(static_cast(x))) {} - //! @copydoc ::boost::container::flat_set(const flat_set &, const allocator_type &) + //! @copydoc ::boost::container::flat_set::flat_set(const flat_set &, const allocator_type &) flat_multiset(const flat_multiset& x, const allocator_type &a) : base_t(static_cast(x), a) {} - //! @copydoc ::boost::container::flat_set(flat_set &&, const allocator_type &) + //! @copydoc ::boost::container::flat_set::flat_set(flat_set &&, const allocator_type &) flat_multiset(BOOST_RV_REF(flat_multiset) x, const allocator_type &a) : base_t(BOOST_MOVE_BASE(base_t, x), a) {} diff --git a/boost/container/list.hpp b/boost/container/list.hpp index 5135eaecee..8236ff7939 100644 --- a/boost/container/list.hpp +++ b/boost/container/list.hpp @@ -1,6 +1,6 @@ ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2005-2013. Distributed under the Boost +// (C) Copyright Ion Gaztanaga 2005-2015. 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) // @@ -651,7 +651,10 @@ class list //! //! Complexity: Constant. reference front() BOOST_NOEXCEPT_OR_NOTHROW - { return *this->begin(); } + { + BOOST_ASSERT(!this->empty()); + return *this->begin(); + } //! Requires: !empty() //! @@ -662,7 +665,10 @@ class list //! //! Complexity: Constant. const_reference front() const BOOST_NOEXCEPT_OR_NOTHROW - { return *this->begin(); } + { + BOOST_ASSERT(!this->empty()); + return *this->begin(); + } //! Requires: !empty() //! @@ -673,7 +679,10 @@ class list //! //! Complexity: Constant. reference back() BOOST_NOEXCEPT_OR_NOTHROW - { return *(--this->end()); } + { + BOOST_ASSERT(!this->empty()); + return *(--this->end()); + } //! Requires: !empty() //! @@ -684,7 +693,10 @@ class list //! //! Complexity: Constant. const_reference back() const BOOST_NOEXCEPT_OR_NOTHROW - { return *(--this->end()); } + { + BOOST_ASSERT(!this->empty()); + return *(--this->end()); + } ////////////////////////////////////////////// // @@ -724,10 +736,11 @@ class list //! //! Complexity: Constant template - iterator emplace(const_iterator p, BOOST_FWD_REF(Args)... args) + iterator emplace(const_iterator position, BOOST_FWD_REF(Args)... args) { + BOOST_ASSERT((priv_is_linked)(position)); NodePtr pnode(AllocHolder::create_node(boost::forward(args)...)); - return iterator(this->icont().insert(p.get(), *pnode)); + return iterator(this->icont().insert(position.get(), *pnode)); } #else // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) @@ -742,10 +755,11 @@ class list { this->emplace(this->cbegin() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);}\ \ BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ - iterator emplace(const_iterator p BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ + iterator emplace(const_iterator position BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ {\ + BOOST_ASSERT(position == this->cend() || (--(++position) == position) );\ NodePtr pnode (AllocHolder::create_node(BOOST_MOVE_FWD##N));\ - return iterator(this->icont().insert(p.get(), *pnode));\ + return iterator(this->icont().insert(position.get(), *pnode));\ }\ // BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_LIST_EMPLACE_CODE) @@ -828,10 +842,11 @@ class list //! Throws: If memory allocation throws or T's copy constructor throws. //! //! Complexity: Linear to n. - iterator insert(const_iterator p, size_type n, const T& x) + iterator insert(const_iterator position, size_type n, const T& x) { + //range check is done by insert typedef constant_iterator cvalue_iterator; - return this->insert(p, cvalue_iterator(x, n), cvalue_iterator()); + return this->insert(position, cvalue_iterator(x, n), cvalue_iterator()); } //! Requires: p must be a valid iterator of *this. @@ -856,6 +871,7 @@ class list #endif ) { + BOOST_ASSERT((priv_is_linked)(p)); const typename Icont::iterator ipos(p.get()); iterator ret_it(ipos); if(first != last){ @@ -870,7 +886,7 @@ class list #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) template - iterator insert(const_iterator p, FwdIt first, FwdIt last + iterator insert(const_iterator position, FwdIt first, FwdIt last , typename container_detail::enable_if_c < !container_detail::is_convertible::value && !(container_detail::is_input_iterator::value @@ -879,9 +895,10 @@ class list >::type * = 0 ) { + BOOST_ASSERT((priv_is_linked)(position)); //Optimized allocation and construction - insertion_functor func(this->icont(), p.get()); - iterator before_p(p.get()); + insertion_functor func(this->icont(), position.get()); + iterator before_p(position.get()); --before_p; this->allocate_many_and_construct(first, boost::container::iterator_distance(first, last), func); return ++before_p; @@ -900,7 +917,10 @@ class list //! //! Complexity: Linear to distance [il.begin(), il.end()). iterator insert(const_iterator p, std::initializer_list il) - { return insert(p, il.begin(), il.end()); } + { + //position range check is done by insert() + return insert(p, il.begin(), il.end()); + } #endif //! Effects: Removes the first element from the list. @@ -909,7 +929,10 @@ class list //! //! Complexity: Amortized constant time. void pop_front() BOOST_NOEXCEPT_OR_NOTHROW - { this->erase(this->cbegin()); } + { + BOOST_ASSERT(!this->empty()); + this->erase(this->cbegin()); + } //! Effects: Removes the last element from the list. //! @@ -917,7 +940,11 @@ class list //! //! Complexity: Amortized constant time. void pop_back() BOOST_NOEXCEPT_OR_NOTHROW - { const_iterator tmp = this->cend(); this->erase(--tmp); } + { + BOOST_ASSERT(!this->empty()); + const_iterator tmp = this->cend(); + this->erase(--tmp); + } //! Requires: p must be a valid iterator of *this. //! @@ -927,7 +954,10 @@ class list //! //! Complexity: Amortized constant time. iterator erase(const_iterator p) BOOST_NOEXCEPT_OR_NOTHROW - { return iterator(this->icont().erase_and_dispose(p.get(), Destroyer(this->node_alloc()))); } + { + BOOST_ASSERT(p != this->cend() && (priv_is_linked)(p)); + return iterator(this->icont().erase_and_dispose(p.get(), Destroyer(this->node_alloc()))); + } //! Requires: first and last must be valid iterator to elements in *this. //! @@ -937,7 +967,11 @@ class list //! //! Complexity: Linear to the distance between first and last. iterator erase(const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW - { return iterator(AllocHolder::erase_range(first.get(), last.get(), alloc_version())); } + { + BOOST_ASSERT(first == last || (first != this->cend() && (priv_is_linked)(first))); + BOOST_ASSERT(first == last || (priv_is_linked)(last)); + return iterator(AllocHolder::erase_range(first.get(), last.get(), alloc_version())); + } //! Effects: Swaps the contents of *this and x. //! @@ -947,7 +981,12 @@ class list void swap(list& x) BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_swap::value || allocator_traits_type::is_always_equal::value) - { AllocHolder::swap(x); } + { + BOOST_ASSERT(allocator_traits_type::propagate_on_container_swap::value || + allocator_traits_type::is_always_equal::value || + this->get_stored_allocator() == x.get_stored_allocator()); + AllocHolder::swap(x); + } //! Effects: Erases all the elements of the list. //! @@ -977,6 +1016,7 @@ class list //! this list. Iterators of this list and all the references are not invalidated. void splice(const_iterator p, list& x) BOOST_NOEXCEPT_OR_NOTHROW { + BOOST_ASSERT((priv_is_linked)(p)); BOOST_ASSERT(this != &x); BOOST_ASSERT(this->node_alloc() == x.node_alloc()); this->icont().splice(p.get(), x.icont()); @@ -995,7 +1035,10 @@ class list //! Note: Iterators of values obtained from list x now point to elements of //! this list. Iterators of this list and all the references are not invalidated. void splice(const_iterator p, BOOST_RV_REF(list) x) BOOST_NOEXCEPT_OR_NOTHROW - { this->splice(p, static_cast(x)); } + { + //Checks done in splice + this->splice(p, static_cast(x)); + } //! Requires: p must point to an element contained //! by this list. i must point to an element contained in list x. @@ -1013,7 +1056,7 @@ class list //! list. Iterators of this list and all the references are not invalidated. void splice(const_iterator p, list &x, const_iterator i) BOOST_NOEXCEPT_OR_NOTHROW { - //BOOST_ASSERT(this != &x); + BOOST_ASSERT((priv_is_linked)(p)); BOOST_ASSERT(this->node_alloc() == x.node_alloc()); this->icont().splice(p.get(), x.icont(), i.get()); } @@ -1033,7 +1076,11 @@ class list //! Note: Iterators of values obtained from list x now point to elements of this //! list. Iterators of this list and all the references are not invalidated. void splice(const_iterator p, BOOST_RV_REF(list) x, const_iterator i) BOOST_NOEXCEPT_OR_NOTHROW - { this->splice(p, static_cast(x), i); } + { + BOOST_ASSERT(this != &x); + //Additional checks done in splice() + this->splice(p, static_cast(x), i); + } //! Requires: p must point to an element contained //! by this list. first and last must point to elements contained in list x. @@ -1050,6 +1097,9 @@ class list //! list. Iterators of this list and all the references are not invalidated. void splice(const_iterator p, list &x, const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW { + BOOST_ASSERT((priv_is_linked)(p)); + BOOST_ASSERT(first == last || (first != x.cend() && x.priv_is_linked(first))); + BOOST_ASSERT(first == last || x.priv_is_linked(last)); BOOST_ASSERT(this->node_alloc() == x.node_alloc()); this->icont().splice(p.get(), x.icont(), first.get(), last.get()); } @@ -1068,7 +1118,11 @@ class list //! Note: Iterators of values obtained from list x now point to elements of this //! list. Iterators of this list and all the references are not invalidated. void splice(const_iterator p, BOOST_RV_REF(list) x, const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW - { this->splice(p, static_cast(x), first, last); } + { + BOOST_ASSERT(this != &x); + //Additional checks done in splice() + this->splice(p, static_cast(x), first, last); + } //! Requires: p must point to an element contained //! by this list. first and last must point to elements contained in list x. @@ -1318,6 +1372,13 @@ class list #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED private: + static bool priv_is_linked(const_iterator const position) + { + const_iterator cur(position); + //This list is circular including end nodes + return (--(++cur)) == position && (++(--cur)) == position; + } + bool priv_try_shrink(size_type new_size) { const size_type len = this->size(); @@ -1348,12 +1409,14 @@ class list iterator priv_insert(const_iterator p, const T &x) { + BOOST_ASSERT((priv_is_linked)(p)); NodePtr tmp = AllocHolder::create_node(x); return iterator(this->icont().insert(p.get(), *tmp)); } iterator priv_insert(const_iterator p, BOOST_RV_REF(T) x) { + BOOST_ASSERT((priv_is_linked)(p)); NodePtr tmp = AllocHolder::create_node(boost::move(x)); return iterator(this->icont().insert(p.get(), *tmp)); } diff --git a/boost/container/map.hpp b/boost/container/map.hpp index 4dc6096e1e..8173181221 100644 --- a/boost/container/map.hpp +++ b/boost/container/map.hpp @@ -481,8 +481,12 @@ class map //! //! Complexity: Logarithmic. mapped_type& operator[](key_type &&k); + #elif defined(BOOST_MOVE_HELPERS_RETURN_SFINAE_BROKEN) + //in compilers like GCC 3.4, we can't catch temporaries + mapped_type& operator[](const key_type &k) { return this->priv_subscript(k); } + mapped_type& operator[](BOOST_RV_REF(key_type) k) { return this->priv_subscript(::boost::move(k)); } #else - BOOST_MOVE_CONVERSION_AWARE_CATCH( operator[] , key_type, mapped_type&, this->priv_subscript) + BOOST_MOVE_CONVERSION_AWARE_CATCH( operator[] , key_type, mapped_type&, this->priv_subscript) #endif //! Returns: A reference to the element whose key is equivalent to x. diff --git a/boost/container/new_allocator.hpp b/boost/container/new_allocator.hpp index 1ac15d8a25..6a1d8c76e3 100644 --- a/boost/container/new_allocator.hpp +++ b/boost/container/new_allocator.hpp @@ -29,6 +29,8 @@ namespace boost { namespace container { +/// @cond + template struct new_allocator_bool { static const bool value = Value; }; @@ -36,6 +38,8 @@ struct new_allocator_bool template class new_allocator; +/// @endcond + //! Specialization of new_allocator for void types template<> class new_allocator diff --git a/boost/container/node_allocator.hpp b/boost/container/node_allocator.hpp index c3d809078f..d92577e741 100644 --- a/boost/container/node_allocator.hpp +++ b/boost/container/node_allocator.hpp @@ -26,7 +26,7 @@ #include #include #include -#include +#include #include #include @@ -157,7 +157,7 @@ class node_allocator return pointer(static_cast(singleton_t::instance().allocate_node())); } else{ - void *ret = boost_cont_malloc(count*sizeof(T)); + void *ret = dlmalloc_malloc(count*sizeof(T)); if(BOOST_UNLIKELY(!ret)) boost::container::throw_bad_alloc(); return static_cast(ret); @@ -176,7 +176,7 @@ class node_allocator singleton_t::instance().deallocate_node(ptr); } else{ - boost_cont_free(ptr); + dlmalloc_free(ptr); } } @@ -204,7 +204,7 @@ class node_allocator size_type size(pointer p) const BOOST_NOEXCEPT_OR_NOTHROW { BOOST_STATIC_ASSERT(( Version > 1 )); - return boost_cont_size(p); + return dlmalloc_size(p); } //!Allocates just one object. Memory allocated with this function @@ -259,9 +259,9 @@ class node_allocator void allocate_many(size_type elem_size, std::size_t n_elements, multiallocation_chain &chain) { BOOST_STATIC_ASSERT(( Version > 1 )); - boost_cont_memchain ch; + dlmalloc_memchain ch; BOOST_CONTAINER_MEMCHAIN_INIT(&ch); - if(BOOST_UNLIKELY(!boost_cont_multialloc_nodes(n_elements, elem_size*sizeof(T), DL_MULTIALLOC_DEFAULT_CONTIGUOUS, &ch))){ + if(BOOST_UNLIKELY(!dlmalloc_multialloc_nodes(n_elements, elem_size*sizeof(T), DL_MULTIALLOC_DEFAULT_CONTIGUOUS, &ch))){ boost::container::throw_bad_alloc(); } chain.incorporate_after( chain.before_begin() @@ -275,8 +275,8 @@ class node_allocator void allocate_many(const size_type *elem_sizes, size_type n_elements, multiallocation_chain &chain) { BOOST_STATIC_ASSERT(( Version > 1 )); - boost_cont_memchain ch; - boost_cont_multialloc_arrays(n_elements, elem_sizes, sizeof(T), DL_MULTIALLOC_DEFAULT_CONTIGUOUS, &ch); + dlmalloc_memchain ch; + dlmalloc_multialloc_arrays(n_elements, elem_sizes, sizeof(T), DL_MULTIALLOC_DEFAULT_CONTIGUOUS, &ch); if(BOOST_UNLIKELY(BOOST_CONTAINER_MEMCHAIN_EMPTY(&ch))){ boost::container::throw_bad_alloc(); } @@ -292,9 +292,9 @@ class node_allocator void *first = &*chain.begin(); void *last = &*chain.last(); size_t num = chain.size(); - boost_cont_memchain ch; + dlmalloc_memchain ch; BOOST_CONTAINER_MEMCHAIN_INIT_FROM(&ch, first, last, num); - boost_cont_multidealloc(&ch); + dlmalloc_multidealloc(&ch); } //!Swaps allocators. Does not throw. If each allocator is placed in a @@ -319,7 +319,7 @@ class node_allocator ,pointer &reuse) { std::size_t const preferred_size = prefer_in_recvd_out_size; - boost_cont_command_ret_t ret = {0 , 0}; + dlmalloc_command_ret_t ret = {0 , 0}; if((limit_size > this->max_size()) | (preferred_size > this->max_size())){ return pointer(); } @@ -328,7 +328,7 @@ class node_allocator std::size_t r_size; { void* reuse_ptr_void = reuse; - ret = boost_cont_allocation_command(command, sizeof(T), l_size, p_size, &r_size, reuse_ptr_void); + ret = dlmalloc_allocation_command(command, sizeof(T), l_size, p_size, &r_size, reuse_ptr_void); reuse = static_cast(reuse_ptr_void); } prefer_in_recvd_out_size = r_size/sizeof(T); diff --git a/boost/container/pmr/deque.hpp b/boost/container/pmr/deque.hpp new file mode 100644 index 0000000000..744758606c --- /dev/null +++ b/boost/container/pmr/deque.hpp @@ -0,0 +1,43 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2015-2015. 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_PMR_DEQUE_HPP +#define BOOST_CONTAINER_PMR_DEQUE_HPP + +#if defined (_MSC_VER) +# pragma once +#endif + +#include +#include + +namespace boost { +namespace container { +namespace pmr { + +#if !defined(BOOST_NO_CXX11_TEMPLATE_ALIASES) + +template +using deque = boost::container::deque>; + +#endif + +template +struct deque_of +{ + typedef boost::container::deque + < T, polymorphic_allocator > type; +}; + +} //namespace pmr { +} //namespace container { +} //namespace boost { + +#endif //BOOST_CONTAINER_PMR_DEQUE_HPP diff --git a/boost/container/pmr/flat_map.hpp b/boost/container/pmr/flat_map.hpp new file mode 100644 index 0000000000..786c190b05 --- /dev/null +++ b/boost/container/pmr/flat_map.hpp @@ -0,0 +1,63 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2015-2015. 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_PMR_FLAT_MAP_HPP +#define BOOST_CONTAINER_PMR_FLAT_MAP_HPP + +#if defined (_MSC_VER) +# pragma once +#endif + +#include +#include + +namespace boost { +namespace container { +namespace pmr { + +#if !defined(BOOST_NO_CXX11_TEMPLATE_ALIASES) + +template + ,class Options = tree_assoc_defaults > +using flat_map = boost::container::flat_map > >; + +template + ,class Options = tree_assoc_defaults > +using flat_multimap = boost::container::flat_multimap > >; + +#endif + +template + ,class Options = tree_assoc_defaults > +struct flat_map_of +{ + typedef boost::container::flat_map > > type; +}; + +template + ,class Options = tree_assoc_defaults > +struct flat_multimap_of +{ + typedef boost::container::flat_multimap > > type; +}; + +} //namespace pmr { +} //namespace container { +} //namespace boost { + +#endif //BOOST_CONTAINER_PMR_FLAT_MAP_HPP diff --git a/boost/container/pmr/flat_set.hpp b/boost/container/pmr/flat_set.hpp new file mode 100644 index 0000000000..5c3ad1e09e --- /dev/null +++ b/boost/container/pmr/flat_set.hpp @@ -0,0 +1,59 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2015-2015. 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_PMR_SET_HPP +#define BOOST_CONTAINER_PMR_SET_HPP + +#if defined (_MSC_VER) +# pragma once +#endif + +#include +#include + +namespace boost { +namespace container { +namespace pmr { + +#if !defined(BOOST_NO_CXX11_TEMPLATE_ALIASES) + +template + ,class Options = tree_assoc_defaults > +using flat_set = boost::container::flat_set >; + +template + ,class Options = tree_assoc_defaults > +using flat_multiset = boost::container::flat_multiset >; + +#endif + +template + ,class Options = tree_assoc_defaults > +struct flat_set_of +{ + typedef boost::container::flat_set > type; +}; + +template + ,class Options = tree_assoc_defaults > +struct flat_multiset_of +{ + typedef boost::container::flat_multiset > type; +}; + +} //namespace pmr { +} //namespace container { +} //namespace boost { + +#endif //BOOST_CONTAINER_PMR_SET_HPP diff --git a/boost/container/pmr/global_resource.hpp b/boost/container/pmr/global_resource.hpp new file mode 100644 index 0000000000..219309b072 --- /dev/null +++ b/boost/container/pmr/global_resource.hpp @@ -0,0 +1,66 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2015-2015. 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_PMR_GLOBAL_RESOURCE_HPP +#define BOOST_CONTAINER_PMR_GLOBAL_RESOURCE_HPP + +#if defined (_MSC_VER) +# pragma once +#endif + +#include +#include +#include + +#include + +namespace boost { +namespace container { +namespace pmr { + +/// @cond +class memory_resource; +/// @endcond + +//! Returns: A pointer to a static-duration object of a type derived from +//! memory_resource that can serve as a resource for allocating memory using +//! global `operator new` and global `operator delete`. The same value is returned every time this function +//! is called. For return value p and memory resource r, p->is_equal(r) returns &r == p. +BOOST_CONTAINER_DECL memory_resource* new_delete_resource() BOOST_NOEXCEPT; + +//! Returns: A pointer to a static-duration object of a type derived from +//! memory_resource for which allocate() always throws bad_alloc and for which +//! deallocate() has no effect. The same value is returned every time this function +//! is called. For return value p and memory resource r, p->is_equal(r) returns &r == p. +BOOST_CONTAINER_DECL memory_resource* null_memory_resource() BOOST_NOEXCEPT; + +//! Effects: If r is non-null, sets the value of the default memory resource +//! pointer to r, otherwise sets the default memory resource pointer to new_delete_resource(). +//! +//! Postconditions: get_default_resource() == r. +//! +//! Returns: The previous value of the default memory resource pointer. +//! +//! Remarks: Calling the set_default_resource and get_default_resource functions shall +//! not incur a data race. A call to the set_default_resource function shall synchronize +//! with subsequent calls to the set_default_resource and get_default_resource functions. +BOOST_CONTAINER_DECL memory_resource* set_default_resource(memory_resource* r) BOOST_NOEXCEPT; + +//! Returns: The current value of the default +//! memory resource pointer. +BOOST_CONTAINER_DECL memory_resource* get_default_resource() BOOST_NOEXCEPT; + +} //namespace pmr { +} //namespace container { +} //namespace boost { + +#include + +#endif //BOOST_CONTAINER_PMR_GLOBAL_RESOURCE_HPP diff --git a/boost/container/pmr/list.hpp b/boost/container/pmr/list.hpp new file mode 100644 index 0000000000..5967f452be --- /dev/null +++ b/boost/container/pmr/list.hpp @@ -0,0 +1,43 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2015-2015. 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_PMR_LIST_HPP +#define BOOST_CONTAINER_PMR_LIST_HPP + +#if defined (_MSC_VER) +# pragma once +#endif + +#include +#include + +namespace boost { +namespace container { +namespace pmr { + +#if !defined(BOOST_NO_CXX11_TEMPLATE_ALIASES) + +template +using list = boost::container::list>; + +#endif + +template +struct list_of +{ + typedef boost::container::list + < T, polymorphic_allocator > type; +}; + +} //namespace pmr { +} //namespace container { +} //namespace boost { + +#endif //BOOST_CONTAINER_PMR_VECTOR_HPP diff --git a/boost/container/pmr/map.hpp b/boost/container/pmr/map.hpp new file mode 100644 index 0000000000..fdada0e420 --- /dev/null +++ b/boost/container/pmr/map.hpp @@ -0,0 +1,63 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2015-2015. 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_PMR_MAP_HPP +#define BOOST_CONTAINER_PMR_MAP_HPP + +#if defined (_MSC_VER) +# pragma once +#endif + +#include +#include + +namespace boost { +namespace container { +namespace pmr { + +#if !defined(BOOST_NO_CXX11_TEMPLATE_ALIASES) + +template + ,class Options = tree_assoc_defaults > +using map = boost::container::map >, Options>; + +template + ,class Options = tree_assoc_defaults > +using multimap = boost::container::multimap >, Options>; + +#endif + +template + ,class Options = tree_assoc_defaults > +struct map_of +{ + typedef boost::container::map >, Options> type; +}; + +template + ,class Options = tree_assoc_defaults > +struct multimap_of +{ + typedef boost::container::multimap >, Options> type; +}; + +} //namespace pmr { +} //namespace container { +} //namespace boost { + +#endif //BOOST_CONTAINER_PMR_MAP_HPP diff --git a/boost/container/pmr/memory_resource.hpp b/boost/container/pmr/memory_resource.hpp new file mode 100644 index 0000000000..72338a7559 --- /dev/null +++ b/boost/container/pmr/memory_resource.hpp @@ -0,0 +1,101 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2015-2015. 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_PMR_MEMORY_RESOURCE_HPP +#define BOOST_CONTAINER_PMR_MEMORY_RESOURCE_HPP + +#if defined (_MSC_VER) +# pragma once +#endif + +#include +#include +#include +#include + +namespace boost { +namespace container { +namespace pmr { + +//! The memory_resource class is an abstract interface to an +//! unbounded set of classes encapsulating memory resources. +class memory_resource +{ + public: + // For exposition only + static BOOST_CONSTEXPR_OR_CONST std::size_t max_align = + boost::move_detail::alignment_of::value; + + //! Effects: Destroys + //! this memory_resource. + virtual ~memory_resource(){} + + //! Effects: Equivalent to + //! `return do_allocate(bytes, alignment);` + void* allocate(std::size_t bytes, std::size_t alignment = max_align) + { return this->do_allocate(bytes, alignment); } + + //! Effects: Equivalent to + //! `return do_deallocate(bytes, alignment);` + void deallocate(void* p, std::size_t bytes, std::size_t alignment = max_align) + { return this->do_deallocate(p, bytes, alignment); } + + //! Effects: Equivalent to + //! `return return do_is_equal(other);` + bool is_equal(const memory_resource& other) const BOOST_NOEXCEPT + { return this->do_is_equal(other); } + + //! Returns: + //! `&a == &b || a.is_equal(b)`. + friend bool operator==(const memory_resource& a, const memory_resource& b) BOOST_NOEXCEPT + { return &a == &b || a.is_equal(b); } + + //! Returns: + //! !(a == b). + friend bool operator!=(const memory_resource& a, const memory_resource& b) BOOST_NOEXCEPT + { return !(a == b); } + + protected: + //! Requires: Alignment shall be a power of two. + //! + //! Returns: A derived class shall implement this function to return a pointer + //! to allocated storage with a size of at least bytes. The returned storage is + //! aligned to the specified alignment, if such alignment is supported; otherwise + //! it is aligned to max_align. + //! + //! Throws: A derived class implementation shall throw an appropriate exception if + //! it is unable to allocate memory with the requested size and alignment. + virtual void* do_allocate(std::size_t bytes, std::size_t alignment) = 0; + + //! Requires: p shall have been returned from a prior call to + //! `allocate(bytes, alignment)` on a memory resource equal to *this, and the storage + //! at p shall not yet have been deallocated. + //! + //! Effects: A derived class shall implement this function to dispose of allocated storage. + //! + //! Throws: Nothing. + virtual void do_deallocate(void* p, std::size_t bytes, std::size_t alignment) = 0; + + //! Returns: A derived class shall implement this function to return true if memory + //! allocated from this can be deallocated from other and vice-versa; otherwise it shall + //! return false. [Note: The most-derived type of other might not match the type of this. + //! For a derived class, D, a typical implementation of this function will compute + //! `dynamic_cast(&other)` and go no further (i.e., return false) + //! if it returns nullptr. - end note]. + virtual bool do_is_equal(const memory_resource& other) const BOOST_NOEXCEPT = 0; +}; + +} //namespace pmr { +} //namespace container { +} //namespace boost { + +#include + +#endif //BOOST_CONTAINER_PMR_MEMORY_RESOURCE_HPP diff --git a/boost/container/pmr/monotonic_buffer_resource.hpp b/boost/container/pmr/monotonic_buffer_resource.hpp new file mode 100644 index 0000000000..dfffe87dc3 --- /dev/null +++ b/boost/container/pmr/monotonic_buffer_resource.hpp @@ -0,0 +1,180 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2015-2015. 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_PMR_MONOTONIC_BUFFER_RESOURCE_HPP +#define BOOST_CONTAINER_PMR_MONOTONIC_BUFFER_RESOURCE_HPP + +#if defined (_MSC_VER) +# pragma once +#endif + +#include +#include +#include +#include +#include + +#include + +namespace boost { +namespace container { +namespace pmr { + +//! A monotonic_buffer_resource is a special-purpose memory resource intended for +//! very fast memory allocations in situations where memory is used to build up a +//! few objects and then is released all at once when the memory resource object +//! is destroyed. It has the following qualities: +//! +//! - A call to deallocate has no effect, thus the amount of memory consumed +//! increases monotonically until the resource is destroyed. +//! +//! - The program can supply an initial buffer, which the allocator uses to satisfy +//! memory requests. +//! +//! - When the initial buffer (if any) is exhausted, it obtains additional buffers +//! from an upstream memory resource supplied at construction. Each additional +//! buffer is larger than the previous one, following a geometric progression. +//! +//! - It is intended for access from one thread of control at a time. Specifically, +//! calls to allocate and deallocate do not synchronize with one another. +//! +//! - It owns the allocated memory and frees it on destruction, even if deallocate has +//! not been called for some of the allocated blocks. +class BOOST_CONTAINER_DECL monotonic_buffer_resource + : public memory_resource +{ + block_slist m_memory_blocks; + void* m_current_buffer; + std::size_t m_current_buffer_size; + std::size_t m_next_buffer_size; + + /// @cond + void increase_next_buffer(); + void increase_next_buffer_at_least_to(std::size_t minimum_size); + void *allocate_from_current(std::size_t aligner, std::size_t bytes); + /// @endcond + + public: + + //! The number of bytes that will be requested by the default in the first call + //! to the upstream allocator + //! + //! Note: Non-standard extension. + static const std::size_t initial_next_buffer_size = 32u*sizeof(void*); + + //! Requires: `upstream` shall be the address of a valid memory resource or `nullptr` + //! + //! Effects: If `upstream` is not nullptr, sets the internal resource to `upstream`, + //! to get_default_resource() otherwise. + //! Sets the internal `current_buffer` to `nullptr` and the internal `next_buffer_size` to an + //! implementation-defined size. + explicit monotonic_buffer_resource(memory_resource* upstream = 0) BOOST_NOEXCEPT; + + //! Requires: `upstream` shall be the address of a valid memory resource or `nullptr` + //! and `initial_size` shall be greater than zero. + //! + //! Effects: If `upstream` is not nullptr, sets the internal resource to `upstream`, + //! to get_default_resource() otherwise. Sets the internal `current_buffer` to `nullptr` and + //! `next_buffer_size` to at least `initial_size`. + explicit monotonic_buffer_resource(std::size_t initial_size, memory_resource* upstream = 0) BOOST_NOEXCEPT; + + //! Requires: `upstream` shall be the address of a valid memory resource or `nullptr`, + //! `buffer_size` shall be no larger than the number of bytes in buffer. + //! + //! Effects: If `upstream` is not nullptr, sets the internal resource to `upstream`, + //! to get_default_resource() otherwise. Sets the internal `current_buffer` to `buffer`, + //! and `next_buffer_size` to `buffer_size` (but not less than an implementation-defined size), + //! then increases `next_buffer_size` by an implementation-defined growth factor (which need not be integral). + monotonic_buffer_resource(void* buffer, std::size_t buffer_size, memory_resource* upstream = 0) BOOST_NOEXCEPT; + + #if !defined(BOOST_NO_CXX11_DELETED_FUNCTIONS) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) + monotonic_buffer_resource(const monotonic_buffer_resource&) = delete; + monotonic_buffer_resource operator=(const monotonic_buffer_resource&) = delete; + #else + private: + monotonic_buffer_resource (const monotonic_buffer_resource&); + monotonic_buffer_resource operator=(const monotonic_buffer_resource&); + public: + #endif + + //! Effects: Calls + //! `this->release()`. + virtual ~monotonic_buffer_resource(); + + //! Effects: `upstream_resource()->deallocate()` as necessary to release all allocated memory. + //! [Note: memory is released back to `upstream_resource()` even if some blocks that were allocated + //! from this have not been deallocated from this. - end note] + void release() BOOST_NOEXCEPT; + + //! Returns: The value of + //! the internal resource. + memory_resource* upstream_resource() const BOOST_NOEXCEPT; + + //! Returns: + //! The number of bytes of storage available for the specified alignment and + //! the number of bytes wasted due to the requested alignment. + //! + //! Note: Non-standard extension. + std::size_t remaining_storage(std::size_t alignment, std::size_t &wasted_due_to_alignment) const BOOST_NOEXCEPT; + + //! Returns: + //! The number of bytes of storage available for the specified alignment. + //! + //! Note: Non-standard extension. + std::size_t remaining_storage(std::size_t alignment = 1u) const BOOST_NOEXCEPT; + + //! Returns: + //! The number of bytes of storage available for the specified alignment. + //! + //! Note: Non-standard extension. + const void *current_buffer() const BOOST_NOEXCEPT; + + //! Returns: + //! The number of bytes that will be requested for the next buffer once the + //! current one is exhausted. + //! + //! Note: Non-standard extension. + std::size_t next_buffer_size() const BOOST_NOEXCEPT; + + protected: + + //! Returns: A pointer to allocated storage with a size of at least `bytes`. The size + //! and alignment of the allocated memory shall meet the requirements for a class derived + //! from `memory_resource`. + //! + //! Effects: If the unused space in the internal `current_buffer` can fit a block with the specified + //! bytes and alignment, then allocate the return block from the internal `current_buffer`; otherwise sets + //! the internal `current_buffer` to `upstream_resource()->allocate(n, m)`, where `n` is not less than + //! `max(bytes, next_buffer_size)` and `m` is not less than alignment, and increase + //! `next_buffer_size` by an implementation-defined growth factor (which need not be integral), + //! then allocate the return block from the newly-allocated internal `current_buffer`. + //! + //! Throws: Nothing unless `upstream_resource()->allocate()` throws. + virtual void* do_allocate(std::size_t bytes, std::size_t alignment); + + //! Effects: None + //! + //! Throws: Nothing + //! + //! Remarks: Memory used by this resource increases monotonically until its destruction. + virtual void do_deallocate(void* p, std::size_t bytes, std::size_t alignment) BOOST_NOEXCEPT; + + //! Returns: + //! `this == dynamic_cast(&other)`. + virtual bool do_is_equal(const memory_resource& other) const BOOST_NOEXCEPT; +}; + +} //namespace pmr { +} //namespace container { +} //namespace boost { + +#include + +#endif //BOOST_CONTAINER_PMR_MONOTONIC_BUFFER_RESOURCE_HPP diff --git a/boost/container/pmr/polymorphic_allocator.hpp b/boost/container/pmr/polymorphic_allocator.hpp new file mode 100644 index 0000000000..d189b3a311 --- /dev/null +++ b/boost/container/pmr/polymorphic_allocator.hpp @@ -0,0 +1,166 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2015-2015. 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_PMR_POLYMORPHIC_ALLOCATOR_HPP +#define BOOST_CONTAINER_PMR_POLYMORPHIC_ALLOCATOR_HPP + +#if defined (_MSC_VER) +# pragma once +#endif + +#include +#include +#include +#include +#include +#include +#include + +#include + +namespace boost { +namespace container { +namespace pmr { + +//! A specialization of class template `polymorphic_allocator` conforms to the Allocator requirements. +//! Constructed with different memory resources, different instances of the same specialization of +//! `polymorphic_allocator` can exhibit entirely different allocation behavior. This runtime +//! polymorphism allows objects that use polymorphic_allocator to behave as if they used different +//! allocator types at run time even though they use the same static allocator type. +template +class polymorphic_allocator +{ + public: + typedef T value_type; + + //! Effects: Sets m_resource to + //! `get_default_resource()`. + polymorphic_allocator() BOOST_NOEXCEPT + : m_resource(::boost::container::pmr::get_default_resource()) + {} + + //! Requires: r is non-null. + //! + //! Effects: Sets m_resource to r. + //! + //! Throws: Nothing + //! + //! Notes: This constructor provides an implicit conversion from memory_resource*. + //! Non-standard extension: if r is null m_resource is set to get_default_resource(). + polymorphic_allocator(memory_resource* r) + : m_resource(r ? r : ::boost::container::pmr::get_default_resource()) + {} + + //! Effects: Sets m_resource to + //! other.resource(). + polymorphic_allocator(const polymorphic_allocator& other) + : m_resource(other.m_resource) + {} + + //! Effects: Sets m_resource to + //! other.resource(). + template + polymorphic_allocator(const polymorphic_allocator& other) BOOST_NOEXCEPT + : m_resource(other.resource()) + {} + + //! Effects: Sets m_resource to + //! other.resource(). + polymorphic_allocator& operator=(const polymorphic_allocator& other) + { m_resource = other.m_resource; return *this; } + + //! Returns: Equivalent to + //! `static_cast(m_resource->allocate(n * sizeof(T), alignof(T)))`. + T* allocate(size_t n) + { return static_cast(m_resource->allocate(n*sizeof(T), ::boost::move_detail::alignment_of::value)); } + + //! Requires: p was allocated from a memory resource, x, equal to *m_resource, + //! using `x.allocate(n * sizeof(T), alignof(T))`. + //! + //! Effects: Equivalent to m_resource->deallocate(p, n * sizeof(T), alignof(T)). + //! + //! Throws: Nothing. + void deallocate(T* p, size_t n) + { m_resource->deallocate(p, n*sizeof(T), ::boost::move_detail::alignment_of::value); } + + #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) + //! Requires: Uses-allocator construction of T with allocator + //! `this->resource()` and constructor arguments `std::forward(args)...` + //! is well-formed. [Note: uses-allocator construction is always well formed for + //! types that do not use allocators. - end note] + //! + //! Effects: Construct a T object at p by uses-allocator construction with allocator + //! `this->resource()` and constructor arguments `std::forward(args)...`. + //! + //! Throws: Nothing unless the constructor for T throws. + template < typename U, class ...Args> + void construct(U* p, BOOST_FWD_REF(Args)...args) + { + new_allocator na; + container_detail::dispatch_uses_allocator + (na, this->resource(), p, ::boost::forward(args)...); + } + + #else // #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) + + //Disable this overload if the first argument is pair as some compilers have + //overload selection problems when the first parameter is a pair. + #define BOOST_CONTAINER_PMR_POLYMORPHIC_ALLOCATOR_CONSTRUCT_CODE(N) \ + template < typename U BOOST_MOVE_I##N BOOST_MOVE_CLASSQ##N >\ + void construct(U* p BOOST_MOVE_I##N BOOST_MOVE_UREFQ##N)\ + {\ + new_allocator na;\ + container_detail::dispatch_uses_allocator\ + (na, this->resource(), p BOOST_MOVE_I##N BOOST_MOVE_FWDQ##N);\ + }\ + // + BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_PMR_POLYMORPHIC_ALLOCATOR_CONSTRUCT_CODE) + #undef BOOST_CONTAINER_PMR_POLYMORPHIC_ALLOCATOR_CONSTRUCT_CODE + + #endif //#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) + + //! Effects: + //! p->~U(). + template + void destroy(U* p) + { (void)p; p->~U(); } + + //! Returns: Equivalent to + //! `polymorphic_allocator()`. + polymorphic_allocator select_on_container_copy_construction() const + { return polymorphic_allocator(); } + + //! Returns: + //! m_resource. + memory_resource* resource() const + { return m_resource; } + + private: + memory_resource* m_resource; +}; + +//! Returns: +//! `*a.resource() == *b.resource()`. +template +bool operator==(const polymorphic_allocator& a, const polymorphic_allocator& b) BOOST_NOEXCEPT +{ return *a.resource() == *b.resource(); } + + +//! Returns: +//! `! (a == b)`. +template +bool operator!=(const polymorphic_allocator& a, const polymorphic_allocator& b) BOOST_NOEXCEPT +{ return *a.resource() != *b.resource(); } + +} //namespace pmr { +} //namespace container { +} //namespace boost { + +#endif //BOOST_CONTAINER_PMR_POLYMORPHIC_ALLOCATOR_HPP diff --git a/boost/container/pmr/pool_options.hpp b/boost/container/pmr/pool_options.hpp new file mode 100644 index 0000000000..e9f72896b1 --- /dev/null +++ b/boost/container/pmr/pool_options.hpp @@ -0,0 +1,52 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2015-2015. 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_PMR_POOL_OPTIONS_HPP +#define BOOST_CONTAINER_PMR_POOL_OPTIONS_HPP + +#if defined (_MSC_VER) +# pragma once +#endif + +#include + +namespace boost { +namespace container { +namespace pmr { + +//! The members of pool_options comprise a set of constructor options for pool resources. +//! The effect of each option on the pool resource behavior is described below: +//! +//! - `std::size_t max_blocks_per_chunk`: The maximum number of blocks that will be allocated +//! at once from the upstream memory resource to replenish a pool. If the value of +//! `max_blocks_per_chunk` is zero or is greater than an implementation-defined limit, +//! that limit is used instead. The implementation may choose to use a smaller value +//! than is specified in this field and may use different values for different pools. +//! +//! - `std::size_t largest_required_pool_block`: The largest allocation size that is required +//! to be fulfilled using the pooling mechanism. Attempts to allocate a single block +//! larger than this threshold will be allocated directly from the upstream memory +//! resource. If largest_required_pool_block is zero or is greater than an +//! implementation-defined limit, that limit is used instead. The implementation may +//! choose a pass-through threshold larger than specified in this field. +struct pool_options +{ + pool_options() + : max_blocks_per_chunk(0u), largest_required_pool_block(0u) + {} + std::size_t max_blocks_per_chunk; + std::size_t largest_required_pool_block; +}; + +} //namespace pmr { +} //namespace container { +} //namespace boost { + +#endif //BOOST_CONTAINER_PMR_POOL_OPTIONS_HPP diff --git a/boost/container/pmr/resource_adaptor.hpp b/boost/container/pmr/resource_adaptor.hpp new file mode 100644 index 0000000000..deece632e8 --- /dev/null +++ b/boost/container/pmr/resource_adaptor.hpp @@ -0,0 +1,193 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2015-2015. 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_PMR_RESOURCE_ADAPTOR_HPP +#define BOOST_CONTAINER_PMR_RESOURCE_ADAPTOR_HPP + +#if defined (_MSC_VER) +# pragma once +#endif + +#include +#include +#include +#include +#include + +namespace boost { +namespace container { +namespace pmr { + +//! An instance of resource_adaptor is an adaptor that wraps a memory_resource interface +//! around Allocator. In order that resource_adaptor> and resource_adaptor> are the same +//! type for any allocator template X and types T and U, resource_adaptor is rendered as +//! an alias to this class template such that Allocator is rebound to a char value type in every +//! specialization of the class template. The requirements on this class template are defined below. +//! In addition to the Allocator requirements, the parameter to resource_adaptor shall meet +//! the following additional requirements: +//! +//! - `typename allocator_traits:: pointer` shall be identical to +//! `typename allocator_traits:: value_type*`. +//! +//! - `typename allocator_traits:: const_pointer` shall be identical to +//! `typename allocator_traits:: value_type const*`. +//! +//! - `typename allocator_traits:: void_pointer` shall be identical to `void*`. +//! +//! - `typename allocator_traits:: const_void_pointer` shall be identical to `void const*`. +template +class resource_adaptor_imp + : public memory_resource + #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED + , private ::boost::intrusive::detail::ebo_functor_holder + #endif +{ + #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED + Allocator m_alloc; + #else + BOOST_COPYABLE_AND_MOVABLE(resource_adaptor_imp) + typedef ::boost::intrusive::detail::ebo_functor_holder ebo_alloc_t; + void static_assert_if_not_char_allocator() const + { + //This class can only be used with allocators type char + BOOST_STATIC_ASSERT((container_detail::is_same::value)); + } + #endif + + public: + typedef Allocator allocator_type; + + //! Effects: Default constructs + //! m_alloc. + resource_adaptor_imp() + { this->static_assert_if_not_char_allocator(); } + + //! Effects: Copy constructs + //! m_alloc. + resource_adaptor_imp(const resource_adaptor_imp &other) + : ebo_alloc_t(other.ebo_alloc_t::get()) + {} + + //! Effects: Move constructs + //! m_alloc. + resource_adaptor_imp(BOOST_RV_REF(resource_adaptor_imp) other) + : ebo_alloc_t(::boost::move(other.get())) + {} + + //! Effects: Initializes m_alloc with + //! a2. + explicit resource_adaptor_imp(const Allocator& a2) + : ebo_alloc_t(a2) + { this->static_assert_if_not_char_allocator(); } + + //! Effects: Initializes m_alloc with + //! a2. + explicit resource_adaptor_imp(BOOST_RV_REF(Allocator) a2) + : ebo_alloc_t(::boost::move(a2)) + { this->static_assert_if_not_char_allocator(); } + + //! Effects: Copy assigns + //! m_alloc. + resource_adaptor_imp& operator=(BOOST_COPY_ASSIGN_REF(resource_adaptor_imp) other) + { this->ebo_alloc_t::get() = other.ebo_alloc_t::get(); return *this; } + + //! Effects: Move assigns + //! m_alloc. + resource_adaptor_imp& operator=(BOOST_RV_REF(resource_adaptor_imp) other) + { this->ebo_alloc_t::get() = ::boost::move(other.ebo_alloc_t::get()); return *this; } + + //! Effects: Returns m_alloc. + allocator_type &get_allocator() + { return this->ebo_alloc_t::get(); } + + //! Effects: Returns m_alloc. + const allocator_type &get_allocator() const + { return this->ebo_alloc_t::get(); } + + protected: + //! Returns: Allocated memory obtained by calling m_alloc.allocate. The size and alignment + //! of the allocated memory shall meet the requirements for a class derived from memory_resource. + virtual void* do_allocate(size_t bytes, size_t alignment) + { (void)alignment; return this->ebo_alloc_t::get().allocate(bytes); } + + //! Requires: p was previously allocated using A.allocate, where A == m_alloc, and not + //! subsequently deallocated. + //! + //! Effects: Returns memory to the allocator using m_alloc.deallocate(). + virtual void do_deallocate(void* p, size_t bytes, size_t alignment) + { (void)alignment; this->ebo_alloc_t::get().deallocate((char*)p, bytes); } + + //! Let p be dynamic_cast(&other). + //! + //! Returns: false if p is null, otherwise the value of m_alloc == p->m_alloc. + virtual bool do_is_equal(const memory_resource& other) const BOOST_NOEXCEPT + { + const resource_adaptor_imp* p = dynamic_cast(&other); + return p && p->ebo_alloc_t::get() == this->ebo_alloc_t::get(); + } +}; + +#if !defined(BOOST_NO_CXX11_TEMPLATE_ALIASES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) + +//! `resource_adaptor` is rendered as an alias to resource_adaptor_imp class template +//! such that Allocator is rebound to a char value type. +template +using resource_adaptor = resource_adaptor_imp + ::template rebind_alloc >; + +#else + +template +class resource_adaptor + : public resource_adaptor_imp + ::template portable_rebind_alloc::type> +{ + typedef resource_adaptor_imp + ::template portable_rebind_alloc::type> base_t; + + BOOST_COPYABLE_AND_MOVABLE(resource_adaptor) + + public: + resource_adaptor() + : base_t() + {} + + resource_adaptor(const resource_adaptor &other) + : base_t(other) + {} + + resource_adaptor(BOOST_RV_REF(resource_adaptor) other) + : base_t(BOOST_MOVE_BASE(base_t, other)) + {} + + explicit resource_adaptor(const Allocator& a2) + : base_t(a2) + {} + + explicit resource_adaptor(BOOST_RV_REF(Allocator) a2) + : base_t(BOOST_MOVE_BASE(base_t, a2)) + {} + + resource_adaptor& operator=(BOOST_COPY_ASSIGN_REF(resource_adaptor) other) + { return static_cast(this->base_t::operator=(other)); } + + resource_adaptor& operator=(BOOST_RV_REF(resource_adaptor) other) + { return static_cast(this->base_t::operator=(BOOST_MOVE_BASE(base_t, other))); } + + //get_allocator and protected functions are properly inherited +}; + +#endif + +} //namespace pmr { +} //namespace container { +} //namespace boost { + +#endif //BOOST_CONTAINER_PMR_RESOURCE_ADAPTOR_HPP diff --git a/boost/container/pmr/set.hpp b/boost/container/pmr/set.hpp new file mode 100644 index 0000000000..6f2c3bfb29 --- /dev/null +++ b/boost/container/pmr/set.hpp @@ -0,0 +1,59 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2015-2015. 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_PMR_SET_HPP +#define BOOST_CONTAINER_PMR_SET_HPP + +#if defined (_MSC_VER) +# pragma once +#endif + +#include +#include + +namespace boost { +namespace container { +namespace pmr { + +#if !defined(BOOST_NO_CXX11_TEMPLATE_ALIASES) + +template + ,class Options = tree_assoc_defaults > +using set = boost::container::set, Options>; + +template + ,class Options = tree_assoc_defaults > +using multiset = boost::container::multiset, Options>; + +#endif + +template + ,class Options = tree_assoc_defaults > +struct set_of +{ + typedef boost::container::set, Options> type; +}; + +template + ,class Options = tree_assoc_defaults > +struct multiset_of +{ + typedef boost::container::multiset, Options> type; +}; + +} //namespace pmr { +} //namespace container { +} //namespace boost { + +#endif //BOOST_CONTAINER_PMR_SET_HPP diff --git a/boost/container/pmr/slist.hpp b/boost/container/pmr/slist.hpp new file mode 100644 index 0000000000..4ee76c62ef --- /dev/null +++ b/boost/container/pmr/slist.hpp @@ -0,0 +1,43 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2015-2015. 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_PMR_SLIST_HPP +#define BOOST_CONTAINER_PMR_SLIST_HPP + +#if defined (_MSC_VER) +# pragma once +#endif + +#include +#include + +namespace boost { +namespace container { +namespace pmr { + +#if !defined(BOOST_NO_CXX11_TEMPLATE_ALIASES) + +template +using slist = boost::container::slist>; + +#endif + +template +struct slist_of +{ + typedef boost::container::slist + < T, polymorphic_allocator > type; +}; + +} //namespace pmr { +} //namespace container { +} //namespace boost { + +#endif //BOOST_CONTAINER_PMR_VECTOR_HPP diff --git a/boost/container/pmr/small_vector.hpp b/boost/container/pmr/small_vector.hpp new file mode 100644 index 0000000000..a79d5a075e --- /dev/null +++ b/boost/container/pmr/small_vector.hpp @@ -0,0 +1,43 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2015-2015. 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_PMR_SMALL_VECTOR_HPP +#define BOOST_CONTAINER_PMR_SMALL_VECTOR_HPP + +#if defined (_MSC_VER) +# pragma once +#endif + +#include +#include + +namespace boost { +namespace container { +namespace pmr { + +#if !defined(BOOST_NO_CXX11_TEMPLATE_ALIASES) + +template +using small_vector = boost::container::small_vector>; + +#endif + +template +struct small_vector_of +{ + typedef boost::container::small_vector + < T, N, polymorphic_allocator > type; +}; + +} //namespace pmr { +} //namespace container { +} //namespace boost { + +#endif //BOOST_CONTAINER_PMR_SMALL_VECTOR_HPP diff --git a/boost/container/pmr/stable_vector.hpp b/boost/container/pmr/stable_vector.hpp new file mode 100644 index 0000000000..07a2059d87 --- /dev/null +++ b/boost/container/pmr/stable_vector.hpp @@ -0,0 +1,43 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2015-2015. 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_PMR_STABLE_VECTOR_HPP +#define BOOST_CONTAINER_PMR_STABLE_VECTOR_HPP + +#if defined (_MSC_VER) +# pragma once +#endif + +#include +#include + +namespace boost { +namespace container { +namespace pmr { + +#if !defined(BOOST_NO_CXX11_TEMPLATE_ALIASES) + +template +using stable_vector = boost::container::stable_vector>; + +#endif + +template +struct stable_vector_of +{ + typedef boost::container::stable_vector + < T, polymorphic_allocator > type; +}; + +} //namespace pmr { +} //namespace container { +} //namespace boost { + +#endif //BOOST_CONTAINER_PMR_STABLE_VECTOR_HPP diff --git a/boost/container/pmr/string.hpp b/boost/container/pmr/string.hpp new file mode 100644 index 0000000000..2e879e3054 --- /dev/null +++ b/boost/container/pmr/string.hpp @@ -0,0 +1,48 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2015-2015. 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_PMR_STRING_HPP +#define BOOST_CONTAINER_PMR_STRING_HPP + +#if defined (_MSC_VER) +# pragma once +#endif + +#include +#include + +namespace boost { +namespace container { +namespace pmr { + +#if !defined(BOOST_NO_CXX11_TEMPLATE_ALIASES) + +template > +using basic_string = + boost::container::basic_string >; + +#endif + +template > +struct basic_string_of +{ + typedef boost::container::basic_string + > type; +}; + +typedef basic_string_of::type string; + +typedef basic_string_of::type wstring; + +} //namespace pmr { +} //namespace container { +} //namespace boost { + +#endif //BOOST_CONTAINER_PMR_STRING_HPP diff --git a/boost/container/pmr/synchronized_pool_resource.hpp b/boost/container/pmr/synchronized_pool_resource.hpp new file mode 100644 index 0000000000..e4d4dd54a1 --- /dev/null +++ b/boost/container/pmr/synchronized_pool_resource.hpp @@ -0,0 +1,138 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2015-2015. 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_PMR_SYNCHRONIZED_POOL_RESOURCE_HPP +#define BOOST_CONTAINER_PMR_SYNCHRONIZED_POOL_RESOURCE_HPP + +#if defined (_MSC_VER) +# pragma once +#endif + +#include +#include +#include +#include +#include + +#include + +namespace boost { +namespace container { +namespace pmr { + +//! A synchronized_pool_resource is a general-purpose memory resources having +//! the following qualities: +//! +//! - Each resource owns the allocated memory, and frees it on destruction, +//! even if deallocate has not been called for some of the allocated blocks. +//! +//! - A pool resource consists of a collection of pools, serving +//! requests for different block sizes. Each individual pool manages a +//! collection of chunks that are in turn divided into blocks of uniform size, +//! returned via calls to do_allocate. Each call to do_allocate(size, alignment) +//! is dispatched to the pool serving the smallest blocks accommodating at +//! least size bytes. +//! +//! - When a particular pool is exhausted, allocating a block from that pool +//! results in the allocation of an additional chunk of memory from the upstream +//! allocator (supplied at construction), thus replenishing the pool. With +//! each successive replenishment, the chunk size obtained increases +//! geometrically. [ Note: By allocating memory in chunks, the pooling strategy +//! increases the chance that consecutive allocations will be close together +//! in memory. - end note ] +//! +//! - Allocation requests that exceed the largest block size of any pool are +//! fulfilled directly from the upstream allocator. +//! +//! - A pool_options struct may be passed to the pool resource constructors to +//! tune the largest block size and the maximum chunk size. +//! +//! A synchronized_pool_resource may be accessed from multiple threads without +//! external synchronization and may have thread-specific pools to reduce +//! synchronization costs. +class BOOST_CONTAINER_DECL synchronized_pool_resource + : public memory_resource +{ + pool_resource m_pool_resource; + void *m_opaque_sync; + + public: + + //! @copydoc ::boost::container::pmr::unsynchronized_pool_resource::unsynchronized_pool_resource(const pool_options&,memory_resource*) + synchronized_pool_resource(const pool_options& opts, memory_resource* upstream) BOOST_NOEXCEPT; + + //! @copydoc ::boost::container::pmr::unsynchronized_pool_resource::unsynchronized_pool_resource() + synchronized_pool_resource() BOOST_NOEXCEPT; + + //! @copydoc ::boost::container::pmr::unsynchronized_pool_resource::unsynchronized_pool_resource(memory_resource*) + explicit synchronized_pool_resource(memory_resource* upstream) BOOST_NOEXCEPT; + + //! @copydoc ::boost::container::pmr::unsynchronized_pool_resource::unsynchronized_pool_resource(const pool_options&) + explicit synchronized_pool_resource(const pool_options& opts) BOOST_NOEXCEPT; + + #if !defined(BOOST_NO_CXX11_DELETED_FUNCTIONS) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) + synchronized_pool_resource(const synchronized_pool_resource&) = delete; + synchronized_pool_resource operator=(const synchronized_pool_resource&) = delete; + #else + private: + synchronized_pool_resource (const synchronized_pool_resource&); + synchronized_pool_resource operator=(const synchronized_pool_resource&); + public: + #endif + + //! @copydoc ::boost::container::pmr::unsynchronized_pool_resource::~unsynchronized_pool_resource() + virtual ~synchronized_pool_resource(); + + //! @copydoc ::boost::container::pmr::unsynchronized_pool_resource::release() + void release(); + + //! @copydoc ::boost::container::pmr::unsynchronized_pool_resource::upstream_resource()const + memory_resource* upstream_resource() const; + + //! @copydoc ::boost::container::pmr::unsynchronized_pool_resource::options()const + pool_options options() const; + + protected: + + //! @copydoc ::boost::container::pmr::unsynchronized_pool_resource::do_allocate() + virtual void* do_allocate(std::size_t bytes, std::size_t alignment); + + //! @copydoc ::boost::container::pmr::unsynchronized_pool_resource::do_deallocate(void*,std::size_t,std::size_t) + virtual void do_deallocate(void* p, std::size_t bytes, std::size_t alignment); + + //! @copydoc ::boost::container::pmr::unsynchronized_pool_resource::do_is_equal(const memory_resource&)const + virtual bool do_is_equal(const memory_resource& other) const BOOST_NOEXCEPT; + + //Non-standard observers + public: + + //! @copydoc ::boost::container::pmr::unsynchronized_pool_resource::pool_count() + std::size_t pool_count() const; + + //! @copydoc ::boost::container::pmr::unsynchronized_pool_resource::pool_index(std::size_t)const + std::size_t pool_index(std::size_t bytes) const; + + //! @copydoc ::boost::container::pmr::unsynchronized_pool_resource::pool_next_blocks_per_chunk(std::size_t)const + std::size_t pool_next_blocks_per_chunk(std::size_t pool_idx) const; + + //! @copydoc ::boost::container::pmr::unsynchronized_pool_resource::pool_block(std::size_t)const + std::size_t pool_block(std::size_t pool_idx) const; + + //! @copydoc ::boost::container::pmr::unsynchronized_pool_resource::pool_cached_blocks(std::size_t)const + std::size_t pool_cached_blocks(std::size_t pool_idx) const; +}; + +} //namespace pmr { +} //namespace container { +} //namespace boost { + +#include + +#endif //BOOST_CONTAINER_PMR_SYNCHRONIZED_POOL_RESOURCE_HPP diff --git a/boost/container/pmr/unsynchronized_pool_resource.hpp b/boost/container/pmr/unsynchronized_pool_resource.hpp new file mode 100644 index 0000000000..21d30b1ebc --- /dev/null +++ b/boost/container/pmr/unsynchronized_pool_resource.hpp @@ -0,0 +1,194 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2015-2015. 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_PMR_UNSYNCHRONIZED_POOL_RESOURCE_HPP +#define BOOST_CONTAINER_PMR_UNSYNCHRONIZED_POOL_RESOURCE_HPP + +#if defined (_MSC_VER) +# pragma once +#endif + +#include +#include +#include +#include +#include + +#include + +namespace boost { +namespace container { +namespace pmr { + +//! A unsynchronized_pool_resource is a general-purpose memory resources having +//! the following qualities: +//! +//! - Each resource owns the allocated memory, and frees it on destruction, +//! even if deallocate has not been called for some of the allocated blocks. +//! +//! - A pool resource consists of a collection of pools, serving +//! requests for different block sizes. Each individual pool manages a +//! collection of chunks that are in turn divided into blocks of uniform size, +//! returned via calls to do_allocate. Each call to do_allocate(size, alignment) +//! is dispatched to the pool serving the smallest blocks accommodating at +//! least size bytes. +//! +//! - When a particular pool is exhausted, allocating a block from that pool +//! results in the allocation of an additional chunk of memory from the upstream +//! allocator (supplied at construction), thus replenishing the pool. With +//! each successive replenishment, the chunk size obtained increases +//! geometrically. [ Note: By allocating memory in chunks, the pooling strategy +//! increases the chance that consecutive allocations will be close together +//! in memory. - end note ] +//! +//! - Allocation requests that exceed the largest block size of any pool are +//! fulfilled directly from the upstream allocator. +//! +//! - A pool_options struct may be passed to the pool resource constructors to +//! tune the largest block size and the maximum chunk size. +//! +//! An unsynchronized_pool_resource class may not be accessed from multiple threads +//! simultaneously and thus avoids the cost of synchronization entirely in +//! single-threaded applications. +class BOOST_CONTAINER_DECL unsynchronized_pool_resource + : public memory_resource +{ + pool_resource m_resource; + + public: + + //! Requires: `upstream` is the address of a valid memory resource. + //! + //! Effects: Constructs a pool resource object that will obtain memory + //! from upstream whenever the pool resource is unable to satisfy a memory + //! request from its own internal data structures. The resulting object will hold + //! a copy of upstream, but will not own the resource to which upstream points. + //! [ Note: The intention is that calls to upstream->allocate() will be + //! substantially fewer than calls to this->allocate() in most cases. - end note + //! The behavior of the pooling mechanism is tuned according to the value of + //! the opts argument. + //! + //! Throws: Nothing unless upstream->allocate() throws. It is unspecified if + //! or under what conditions this constructor calls upstream->allocate(). + unsynchronized_pool_resource(const pool_options& opts, memory_resource* upstream) BOOST_NOEXCEPT; + + //! Effects: Same as + //! `unsynchronized_pool_resource(pool_options(), get_default_resource())`. + unsynchronized_pool_resource() BOOST_NOEXCEPT; + + //! Effects: Same as + //! `unsynchronized_pool_resource(pool_options(), upstream)`. + explicit unsynchronized_pool_resource(memory_resource* upstream) BOOST_NOEXCEPT; + + //! Effects: Same as + //! `unsynchronized_pool_resource(opts, get_default_resource())`. + explicit unsynchronized_pool_resource(const pool_options& opts) BOOST_NOEXCEPT; + + #if !defined(BOOST_NO_CXX11_DELETED_FUNCTIONS) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) + unsynchronized_pool_resource(const unsynchronized_pool_resource&) = delete; + unsynchronized_pool_resource operator=(const unsynchronized_pool_resource&) = delete; + #else + private: + unsynchronized_pool_resource (const unsynchronized_pool_resource&); + unsynchronized_pool_resource operator=(const unsynchronized_pool_resource&); + public: + #endif + + //! Effects: Calls + //! `this->release()`. + virtual ~unsynchronized_pool_resource(); + + //! Effects: Calls Calls `upstream_resource()->deallocate()` as necessary + //! to release all allocated memory. [ Note: memory is released back to + //! `upstream_resource()` even if deallocate has not been called for some + //! of the allocated blocks. - end note ] + void release(); + + //! Returns: The value of the upstream argument provided to the + //! constructor of this object. + memory_resource* upstream_resource() const; + + //! Returns: The options that control the pooling behavior of this resource. + //! The values in the returned struct may differ from those supplied to the pool + //! resource constructor in that values of zero will be replaced with + //! implementation-defined defaults and sizes may be rounded to unspecified granularity. + pool_options options() const; + + protected: + + //! Returns: A pointer to allocated storage with a size of at least `bytes`. + //! The size and alignment of the allocated memory shall meet the requirements for + //! a class derived from `memory_resource`. + //! + //! Effects: If the pool selected for a block of size bytes is unable to + //! satisfy the memory request from its own internal data structures, it will call + //! `upstream_resource()->allocate()` to obtain more memory. If `bytes` is larger + //! than that which the largest pool can handle, then memory will be allocated + //! using `upstream_resource()->allocate()`. + //! + //! Throws: Nothing unless `upstream_resource()->allocate()` throws. + virtual void* do_allocate(std::size_t bytes, std::size_t alignment); + + //! Effects: Return the memory at p to the pool. It is unspecified if or under + //! what circumstances this operation will result in a call to + //! `upstream_resource()->deallocate()`. + //! + //! Throws: Nothing. + virtual void do_deallocate(void* p, std::size_t bytes, std::size_t alignment); + + //! Returns: + //! `this == dynamic_cast(&other)`. + virtual bool do_is_equal(const memory_resource& other) const BOOST_NOEXCEPT; + + //Non-standard observers + public: + //! Returns: The number of pools that will be used in the pool resource. + //! + //! Note: Non-standard extension. + std::size_t pool_count() const; + + //! Returns: The index of the pool that will be used to serve the allocation of `bytes`. + //! Returns `pool_count()` if `bytes` is bigger + //! than `options().largest_required_pool_block` (no pool will be used to serve this). + //! + //! Note: Non-standard extension. + std::size_t pool_index(std::size_t bytes) const; + + //! Requires: `pool_idx < pool_index()` + //! + //! Returns: The number blocks that will be allocated in the next chunk + //! from the pool specified by `pool_idx`. + //! + //! Note: Non-standard extension. + std::size_t pool_next_blocks_per_chunk(std::size_t pool_idx) const; + + //! Requires: `pool_idx < pool_index()` + //! + //! Returns: The number of bytes of the block that the specified `pool_idx` pool manages. + //! + //! Note: Non-standard extension. + std::size_t pool_block(std::size_t pool_idx) const; + + //! Requires: `pool_idx < pool_index()` + //! + //! Returns: The number of blocks that the specified `pool_idx` pool has cached + //! and will be served without calling the upstream_allocator. + //! + //! Note: Non-standard extension. + std::size_t pool_cached_blocks(std::size_t pool_idx) const; +}; + +} //namespace pmr { +} //namespace container { +} //namespace boost { + +#include + +#endif //BOOST_CONTAINER_PMR_UNSYNCHRONIZED_POOL_RESOURCE_HPP diff --git a/boost/container/pmr/vector.hpp b/boost/container/pmr/vector.hpp new file mode 100644 index 0000000000..cef6ae5b94 --- /dev/null +++ b/boost/container/pmr/vector.hpp @@ -0,0 +1,43 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2015-2015. 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_PMR_VECTOR_HPP +#define BOOST_CONTAINER_PMR_VECTOR_HPP + +#if defined (_MSC_VER) +# pragma once +#endif + +#include +#include + +namespace boost { +namespace container { +namespace pmr { + +#if !defined(BOOST_NO_CXX11_TEMPLATE_ALIASES) + +template +using vector = boost::container::vector>; + +#endif + +template +struct vector_of +{ + typedef boost::container::vector + < T, polymorphic_allocator > type; +}; + +} //namespace pmr { +} //namespace container { +} //namespace boost { + +#endif //BOOST_CONTAINER_PMR_VECTOR_HPP diff --git a/boost/container/scoped_allocator.hpp b/boost/container/scoped_allocator.hpp index 0724f948fb..6a041a653d 100644 --- a/boost/container/scoped_allocator.hpp +++ b/boost/container/scoped_allocator.hpp @@ -18,7 +18,7 @@ #define BOOST_CONTAINER_ALLOCATOR_SCOPED_ALLOCATOR_HPP #if defined (_MSC_VER) -# pragma once +# pragma once #endif #include @@ -26,8 +26,8 @@ #include #include +#include -#include #include #include #include @@ -42,143 +42,6 @@ namespace boost { namespace container { -//! Remark: if a specialization constructible_with_allocator_suffix::value is true, indicates that T may be constructed -//! with an allocator as its last constructor argument. Ideally, all constructors of T (including the -//! copy and move constructors) should have a variant that accepts a final argument of -//! allocator_type. -//! -//! Requires: if a specialization constructible_with_allocator_suffix::value is true, T must have a nested type, -//! allocator_type and at least one constructor for which allocator_type is the last -//! parameter. If not all constructors of T can be called with a final allocator_type argument, -//! and if T is used in a context where a container must call such a constructor, then the program is -//! ill-formed. -//! -//! -//! template > -//! class Z { -//! public: -//! typedef Allocator allocator_type; -//! -//! // Default constructor with optional allocator suffix -//! Z(const allocator_type& a = allocator_type()); -//! -//! // Copy constructor and allocator-extended copy constructor -//! Z(const Z& zz); -//! Z(const Z& zz, const allocator_type& a); -//! }; -//! -//! // Specialize trait for class template Z -//! template > -//! struct constructible_with_allocator_suffix > -//! { static const bool value = true; }; -//! -//! -//! Note: This trait is a workaround inspired by "N2554: The Scoped A Model (Rev 2)" -//! (Pablo Halpern, 2008-02-29) to backport the scoped allocator model to C++03, as -//! in C++03 there is no mechanism to detect if a type can be constructed from arbitrary arguments. -//! Applications aiming portability with several compilers should always define this trait. -//! -//! In conforming C++11 compilers or compilers supporting SFINAE expressions -//! (when BOOST_NO_SFINAE_EXPR is NOT defined), this trait is ignored and C++11 rules will be used -//! to detect if a type should be constructed with suffix or prefix allocator arguments. -template -struct constructible_with_allocator_suffix -{ static const bool value = false; }; - -//! Remark: if a specialization constructible_with_allocator_prefix::value is true, indicates that T may be constructed -//! with allocator_arg and T::allocator_type as its first two constructor arguments. -//! Ideally, all constructors of T (including the copy and move constructors) should have a variant -//! that accepts these two initial arguments. -//! -//! Requires: specialization constructible_with_allocator_prefix::value is true, T must have a nested type, -//! allocator_type and at least one constructor for which allocator_arg_t is the first -//! parameter and allocator_type is the second parameter. If not all constructors of T can be -//! called with these initial arguments, and if T is used in a context where a container must call such -//! a constructor, then the program is ill-formed. -//! -//! -//! template > -//! class Y { -//! public: -//! typedef Allocator allocator_type; -//! -//! // Default constructor with and allocator-extended default constructor -//! Y(); -//! Y(allocator_arg_t, const allocator_type& a); -//! -//! // Copy constructor and allocator-extended copy constructor -//! Y(const Y& yy); -//! Y(allocator_arg_t, const allocator_type& a, const Y& yy); -//! -//! // Variadic constructor and allocator-extended variadic constructor -//! template Y(Args&& args...); -//! template -//! Y(allocator_arg_t, const allocator_type& a, BOOST_FWD_REF(Args)... args); -//! }; -//! -//! // Specialize trait for class template Y -//! template > -//! struct constructible_with_allocator_prefix > -//! { static const bool value = true; }; -//! -//! -//! -//! Note: This trait is a workaround inspired by "N2554: The Scoped Allocator Model (Rev 2)" -//! (Pablo Halpern, 2008-02-29) to backport the scoped allocator model to C++03, as -//! in C++03 there is no mechanism to detect if a type can be constructed from arbitrary arguments. -//! Applications aiming portability with several compilers should always define this trait. -//! -//! In conforming C++11 compilers or compilers supporting SFINAE expressions -//! (when BOOST_NO_SFINAE_EXPR is NOT defined), this trait is ignored and C++11 rules will be used -//! to detect if a type should be constructed with suffix or prefix allocator arguments. -template -struct constructible_with_allocator_prefix -{ static const bool value = false; }; - -#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED - -namespace container_detail { - -template -struct uses_allocator_imp -{ - // Use SFINAE (Substitution Failure Is Not An Error) to detect the - // presence of an 'allocator_type' nested type convertilble from Allocator. - private: - typedef char yes_type; - struct no_type{ char dummy[2]; }; - - // Match this function if TypeT::allocator_type exists and is - // implicitly convertible from Allocator - template - static yes_type test(typename U::allocator_type); - - // Match this function if TypeT::allocator_type does not exist or is - // not convertible from Allocator. - template - static no_type test(...); - static Allocator alloc; // Declared but not defined - - public: - static const bool value = sizeof(test(alloc)) == sizeof(yes_type); -}; - -} //namespace container_detail { - -#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED - -//! Remark: Automatically detects if T has a nested allocator_type that is convertible from -//! Allocator. Meets the BinaryTypeTrait requirements ([meta.rqmts] 20.4.1). A program may -//! specialize this type to define uses_allocator::value as true for a T of user-defined type if T does not -//! have a nested allocator_type but is nonetheless constructible using the specified Allocator. -//! -//! Result: uses_allocator::value== true if Convertible, -//! false otherwise. -template -struct uses_allocator - : container_detail::uses_allocator_imp -{}; - #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED namespace container_detail { @@ -249,198 +112,17 @@ struct outermost_allocator {}; template -typename container_detail::outermost_allocator_imp::type & +typename outermost_allocator::type & get_outermost_allocator(Allocator &a) -{ return container_detail::outermost_allocator_imp::get(a); } +{ return outermost_allocator::get(a); } template -const typename container_detail::outermost_allocator_imp::type & +const typename outermost_allocator::type & get_outermost_allocator(const Allocator &a) -{ return container_detail::outermost_allocator_imp::get(a); } +{ return outermost_allocator::get(a); } namespace container_detail { -// Check if we can detect is_convertible using advanced SFINAE expressions -#if !defined(BOOST_NO_CXX11_DECLTYPE) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) - - //! Code inspired by Mathias Gaunard's is_convertible.cpp found in the Boost mailing list - //! http://boost.2283326.n4.nabble.com/type-traits-is-constructible-when-decltype-is-supported-td3575452.html - //! Thanks Mathias! - - //With variadic templates, we need a single class to implement the trait - template - struct is_constructible - { - typedef char yes_type; - struct no_type - { char padding[2]; }; - - template - struct dummy; - - template - static decltype(X(boost::move_detail::declval()...), true_type()) test(int); - - template - static no_type test(...); - - static const bool value = sizeof(test(0)) == sizeof(yes_type); - }; - - template - struct is_constructible_with_allocator_prefix - : is_constructible - {}; - -#else // #if !defined(BOOST_NO_SFINAE_EXPR) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) - - //Without advanced SFINAE expressions, we can't use is_constructible - //so backup to constructible_with_allocator_xxx - - #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) - - template - struct is_constructible_with_allocator_prefix - : constructible_with_allocator_prefix - {}; - - template - struct is_constructible_with_allocator_suffix - : constructible_with_allocator_suffix - {}; - - #else // #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) - - template - struct is_constructible_with_allocator_prefix - : constructible_with_allocator_prefix - {}; - - template - struct is_constructible_with_allocator_suffix - : constructible_with_allocator_suffix - {}; - - #endif // #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) - -#endif // #if !defined(BOOST_NO_SFINAE_EXPR) - -#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) - -// allocator_arg_t -template < typename OutermostAlloc - , typename InnerAlloc - , typename T - , class ...Args - > -inline void dispatch_allocator_prefix_suffix - ( true_type use_alloc_prefix, OutermostAlloc& outermost_alloc - , InnerAlloc& inner_alloc, T* p, BOOST_FWD_REF(Args) ...args) -{ - (void)use_alloc_prefix; - allocator_traits::construct - ( outermost_alloc, p, allocator_arg, inner_alloc, ::boost::forward(args)...); -} - -// allocator suffix -template < typename OutermostAlloc - , typename InnerAlloc - , typename T - , class ...Args - > -inline void dispatch_allocator_prefix_suffix - ( false_type use_alloc_prefix, OutermostAlloc& outermost_alloc - , InnerAlloc &inner_alloc, T* p, BOOST_FWD_REF(Args)...args) -{ - (void)use_alloc_prefix; - allocator_traits::construct - (outermost_alloc, p, ::boost::forward(args)..., inner_alloc); -} - -template < typename OutermostAlloc - , typename InnerAlloc - , typename T - , class ...Args - > -inline void dispatch_uses_allocator - ( true_type uses_allocator, OutermostAlloc& outermost_alloc - , InnerAlloc& inner_alloc, T* p, BOOST_FWD_REF(Args)...args) -{ - (void)uses_allocator; - //BOOST_STATIC_ASSERT((is_constructible_with_allocator_prefix::value || - // is_constructible_with_allocator_suffix::value )); - dispatch_allocator_prefix_suffix - ( bool_< is_constructible_with_allocator_prefix::value>() - , outermost_alloc, inner_alloc, p, ::boost::forward(args)...); -} - -template < typename OutermostAlloc - , typename InnerAlloc - , typename T - , class ...Args - > -inline void dispatch_uses_allocator - ( false_type uses_allocator, OutermostAlloc & outermost_alloc - , InnerAlloc & inner_alloc - ,T* p, BOOST_FWD_REF(Args)...args) -{ - (void)uses_allocator; (void)inner_alloc; - allocator_traits::construct - (outermost_alloc, p, ::boost::forward(args)...); -} - -#else //#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) - -#define BOOST_CONTAINER_SCOPED_ALLOCATOR_DISPATCH_USES_ALLOCATOR_CODE(N) \ -template < typename OutermostAlloc, typename InnerAlloc, typename T\ - BOOST_MOVE_I##N BOOST_MOVE_CLASS##N > \ -inline void dispatch_allocator_prefix_suffix\ - (true_type use_alloc_prefix, OutermostAlloc& outermost_alloc,\ - InnerAlloc& inner_alloc, T* p BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ -{\ - (void)use_alloc_prefix,\ - allocator_traits::construct\ - (outermost_alloc, p, allocator_arg, inner_alloc BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ -}\ -\ -template < typename OutermostAlloc, typename InnerAlloc, typename T\ - BOOST_MOVE_I##N BOOST_MOVE_CLASS##N >\ -inline void dispatch_allocator_prefix_suffix\ - (false_type use_alloc_prefix, OutermostAlloc& outermost_alloc,\ - InnerAlloc& inner_alloc, T* p BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ -{\ - (void)use_alloc_prefix;\ - allocator_traits::construct\ - (outermost_alloc, p BOOST_MOVE_I##N BOOST_MOVE_FWD##N, inner_alloc);\ -}\ -\ -template < typename OutermostAlloc, typename InnerAlloc, typename T\ - BOOST_MOVE_I##N BOOST_MOVE_CLASS##N >\ -inline void dispatch_uses_allocator\ - (true_type uses_allocator, OutermostAlloc& outermost_alloc,\ - InnerAlloc& inner_alloc, T* p BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ -{\ - (void)uses_allocator;\ - dispatch_allocator_prefix_suffix\ - ( bool_< is_constructible_with_allocator_prefix::value >()\ - , outermost_alloc, inner_alloc, p BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ -}\ -\ -template < typename OutermostAlloc, typename InnerAlloc, typename T\ - BOOST_MOVE_I##N BOOST_MOVE_CLASS##N >\ -inline void dispatch_uses_allocator\ - (false_type uses_allocator, OutermostAlloc &outermost_alloc,\ - InnerAlloc &inner_alloc, T* p BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ -{\ - (void)uses_allocator; (void)inner_alloc;\ - allocator_traits::construct(outermost_alloc, p BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ -}\ -// -BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_SCOPED_ALLOCATOR_DISPATCH_USES_ALLOCATOR_CODE) -#undef BOOST_CONTAINER_SCOPED_ALLOCATOR_DISPATCH_USES_ALLOCATOR_CODE - -#endif //#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) - #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) template @@ -923,24 +605,24 @@ class scoped_allocator_adaptor typedef typename outer_traits_type::void_pointer void_pointer; typedef typename outer_traits_type::const_void_pointer const_void_pointer; //! Type: A type with a constant boolean value == true if - //!`allocator_traits::propagate_on_container_copy_assignment::value` is + //!`allocator_traits:: propagate_on_container_copy_assignment::value` is //! true for any Allocator in the set of OuterAlloc and InnerAllocs..., false otherwise. typedef typename base_type:: propagate_on_container_copy_assignment propagate_on_container_copy_assignment; //! Type: A type with a constant boolean value == true if - //!`allocator_traits::propagate_on_container_move_assignment::value` is + //!`allocator_traits:: propagate_on_container_move_assignment::value` is //! true for any Allocator in the set of OuterAlloc and InnerAllocs..., false otherwise. typedef typename base_type:: propagate_on_container_move_assignment propagate_on_container_move_assignment; //! Type: A type with a constant boolean value == true if - //! `allocator_traits::propagate_on_container_swap::value` is + //! `allocator_traits:: propagate_on_container_swap::value` is //! true for any Allocator in the set of OuterAlloc and InnerAllocs..., false otherwise. typedef typename base_type:: propagate_on_container_swap propagate_on_container_swap; //! Type: A type with a constant boolean value == true if - //!`allocator_traits::is_always_equal::value` is + //!`allocator_traits:: is_always_equal::value` is //! true for all Allocator in the set of OuterAlloc and InnerAllocs..., false otherwise. typedef typename base_type:: is_always_equal is_always_equal; @@ -1053,12 +735,12 @@ class scoped_allocator_adaptor #endif //BOOST_CONTAINER_DOXYGEN_INVOKED //! Returns: - //! allocator_traits::max_size(outer_allocator()). + //! allocator_traits:: max_size(outer_allocator()). size_type max_size() const BOOST_NOEXCEPT_OR_NOTHROW { return outer_traits_type::max_size(this->outer_allocator()); } //! Effects: - //! calls OUTERMOST_ALLOC_TRAITS(*this)::destroy(OUTERMOST(*this), p). + //! calls OUTERMOST_ALLOC_TRAITS(*this):: destroy(OUTERMOST(*this), p). template void destroy(T* p) BOOST_NOEXCEPT_OR_NOTHROW { @@ -1099,12 +781,12 @@ class scoped_allocator_adaptor //! Effects: //! 1) If uses_allocator::value is false calls - //! OUTERMOST_ALLOC_TRAITS(*this)::construct - //! (OUTERMOST(*this), p, std::forward(args)...). + //! OUTERMOST_ALLOC_TRAITS(*this):: + //! construct(OUTERMOST(*this), p, std::forward(args)...). //! //! 2) Otherwise, if uses_allocator::value is true and - //! is_constructible::value is true, calls - //! OUTERMOST_ALLOC_TRAITS(*this)::construct(OUTERMOST(*this), p, allocator_arg, + //! is_constructible:: value is true, calls + //! OUTERMOST_ALLOC_TRAITS(*this):: construct(OUTERMOST(*this), p, allocator_arg, //! inner_allocator(), std::forward(args)...). //! //! [Note: In compilers without advanced decltype SFINAE support, is_constructible can't @@ -1112,13 +794,13 @@ class scoped_allocator_adaptor //! constructible_with_allocator_prefix::value. -end note] //! //! 3) Otherwise, if uses_allocator::value is true and - //! is_constructible::value is true, calls - //! OUTERMOST_ALLOC_TRAITS(*this)::construct(OUTERMOST(*this), p, + //! is_constructible:: value is true, calls + //! OUTERMOST_ALLOC_TRAITS(*this):: construct(OUTERMOST(*this), p, //! std::forward(args)..., inner_allocator()). //! //! [Note: In compilers without advanced decltype SFINAE support, is_constructible can't be //! implemented so that condition will be replaced by - //! constructible_with_allocator_suffix::value. -end note] + //! constructible_with_allocator_suffix:: value. -end note] //! //! 4) Otherwise, the program is ill-formed. //! @@ -1126,18 +808,11 @@ class scoped_allocator_adaptor //! to true but the specific constructor does not take an allocator. This definition prevents a silent //! failure to pass an inner allocator to a contained element. -end note] template < typename T, class ...Args> - #if defined(BOOST_CONTAINER_DOXYGEN_INVOKED) - void - #else - typename container_detail::enable_if >::type - #endif - construct(T* p, BOOST_FWD_REF(Args)...args) + void construct(T* p, BOOST_FWD_REF(Args)...args) { container_detail::dispatch_uses_allocator - ( container_detail::bool_::value>() - , get_outermost_allocator(this->outer_allocator()) - , this->inner_allocator() - , p, ::boost::forward(args)...); + ( (get_outermost_allocator)(this->outer_allocator()) + , this->inner_allocator(), p, ::boost::forward(args)...); } #else // #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) @@ -1146,12 +821,10 @@ class scoped_allocator_adaptor //overload selection problems when the first parameter is a pair. #define BOOST_CONTAINER_SCOPED_ALLOCATOR_CONSTRUCT_CODE(N) \ template < typename T BOOST_MOVE_I##N BOOST_MOVE_CLASSQ##N >\ - typename container_detail::enable_if< container_detail::is_not_pair >::type\ - construct(T* p BOOST_MOVE_I##N BOOST_MOVE_UREFQ##N)\ + void construct(T* p BOOST_MOVE_I##N BOOST_MOVE_UREFQ##N)\ {\ container_detail::dispatch_uses_allocator\ - ( container_detail::bool_::value>()\ - , get_outermost_allocator(this->outer_allocator())\ + ( (get_outermost_allocator)(this->outer_allocator())\ , this->inner_allocator(), p BOOST_MOVE_I##N BOOST_MOVE_FWDQ##N);\ }\ // @@ -1160,81 +833,7 @@ class scoped_allocator_adaptor #endif // #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) || defined(BOOST_CONTAINER_DOXYGEN_INVOKED) - template - void construct(std::pair* p) - { this->construct_pair(p); } - - template - void construct(container_detail::pair* p) - { this->construct_pair(p); } - - template - void construct(std::pair* p, BOOST_FWD_REF(U) x, BOOST_FWD_REF(V) y) - { this->construct_pair(p, ::boost::forward(x), ::boost::forward(y)); } - - template - void construct(container_detail::pair* p, BOOST_FWD_REF(U) x, BOOST_FWD_REF(V) y) - { this->construct_pair(p, ::boost::forward(x), ::boost::forward(y)); } - - template - void construct(std::pair* p, const std::pair& x) - { this->construct_pair(p, x); } - - template - void construct( container_detail::pair* p - , const container_detail::pair& x) - { this->construct_pair(p, x); } - - template - void construct( std::pair* p - , BOOST_RV_REF_BEG std::pair BOOST_RV_REF_END x) - { this->construct_pair(p, ::boost::move(x)); } - - template - void construct( container_detail::pair* p - , BOOST_RV_REF_BEG container_detail::pair BOOST_RV_REF_END x) - { this->construct_pair(p, ::boost::move(x)); } - #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED - private: - template - void construct_pair(Pair* p) - { - this->construct(container_detail::addressof(p->first)); - BOOST_TRY{ - this->construct(container_detail::addressof(p->second)); - } - BOOST_CATCH(...){ - this->destroy(container_detail::addressof(p->first)); - BOOST_RETHROW - } - BOOST_CATCH_END - } - - template - void construct_pair(Pair* p, BOOST_FWD_REF(U) x, BOOST_FWD_REF(V) y) - { - this->construct(container_detail::addressof(p->first), ::boost::forward(x)); - BOOST_TRY{ - this->construct(container_detail::addressof(p->second), ::boost::forward(y)); - } - BOOST_CATCH(...){ - this->destroy(container_detail::addressof(p->first)); - BOOST_RETHROW - } - BOOST_CATCH_END - } - - template - void construct_pair(Pair* p, const Pair2& pr) - { this->construct_pair(p, pr.first, pr.second); } - - template - void construct_pair(Pair* p, BOOST_RV_REF(Pair2) pr) - { this->construct_pair(p, ::boost::move(pr.first), ::boost::move(pr.second)); } - - //template - //void construct(pair* p, piecewise_construct_t, tuple x, tuple y); public: //Internal function @@ -1246,6 +845,8 @@ class scoped_allocator_adaptor #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED }; +/// @cond + template struct scoped_allocator_operator_equal { @@ -1278,6 +879,7 @@ struct scoped_allocator_operator_equal { return true; } }; +/// @endcond template inline bool operator==(const scoped_allocator_adaptor& a diff --git a/boost/container/scoped_allocator_fwd.hpp b/boost/container/scoped_allocator_fwd.hpp index 003ed9f7f7..cddf7fad15 100644 --- a/boost/container/scoped_allocator_fwd.hpp +++ b/boost/container/scoped_allocator_fwd.hpp @@ -1,6 +1,6 @@ ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2011-2013. Distributed under the Boost +// (C) Copyright Ion Gaztanaga 2015-2015. Distributed under the Boost // Software License, Version 1.0. (See accompanying file // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) // @@ -13,7 +13,6 @@ //! \file //! This header file forward declares boost::container::scoped_allocator_adaptor -//! and defines the following types: #ifndef BOOST_CONFIG_HPP # include @@ -26,6 +25,7 @@ #include #include #include +#include #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) #include @@ -59,38 +59,11 @@ namespace boost { namespace container { #endif - template - struct std_allocator_arg_holder - { - static ::std::allocator_arg_t *dummy; - }; - - template - ::std::allocator_arg_t *std_allocator_arg_holder::dummy; #else //BOOST_CONTAINER_DOXYGEN_INVOKED #endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED -//! The allocator_arg_t struct is an empty structure type used as a unique type to -//! disambiguate constructor and function overloading. Specifically, several types -//! have constructors with allocator_arg_t as the first argument, immediately followed -//! by an argument of a type that satisfies Allocator requirements -typedef const std::allocator_arg_t & allocator_arg_t; - -//! A instance of type allocator_arg_t -//! -static allocator_arg_t allocator_arg = BOOST_CONTAINER_DOC1ST(unspecified, *std_allocator_arg_holder<>::dummy); - -template -struct constructible_with_allocator_suffix; - -template -struct constructible_with_allocator_prefix; - -template -struct uses_allocator; - }} // namespace boost { namespace container { #include diff --git a/boost/container/set.hpp b/boost/container/set.hpp index 79fa1aec66..ca05cac1f7 100644 --- a/boost/container/set.hpp +++ b/boost/container/set.hpp @@ -253,6 +253,9 @@ class set { return static_cast(this->base_t::operator=(BOOST_MOVE_BASE(base_t, x))); } #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) + //! Effects: Copy all elements from il to *this. + //! + //! Complexity: Linear in il.size(). set& operator=(std::initializer_list il) { this->clear(); @@ -851,17 +854,17 @@ class multiset : base_t(static_cast(x)) {} - //! @copydoc ::boost::container::set(set &&) + //! @copydoc ::boost::container::set::set(set &&) multiset(BOOST_RV_REF(multiset) x) : base_t(BOOST_MOVE_BASE(base_t, x)) {} - //! @copydoc ::boost::container::set(const set &, const allocator_type &) + //! @copydoc ::boost::container::set::set(const set &, const allocator_type &) multiset(const multiset& x, const allocator_type &a) : base_t(static_cast(x), a) {} - //! @copydoc ::boost::container::set(set &&, const allocator_type &) + //! @copydoc ::boost::container::set::set(set &&, const allocator_type &) multiset(BOOST_RV_REF(multiset) x, const allocator_type &a) : base_t(BOOST_MOVE_BASE(base_t, x), a) {} diff --git a/boost/container/slist.hpp b/boost/container/slist.hpp index 2b53df132f..8e7aa20030 100644 --- a/boost/container/slist.hpp +++ b/boost/container/slist.hpp @@ -1,6 +1,6 @@ ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2004-2013. Distributed under the Boost +// (C) Copyright Ion Gaztanaga 2004-2015. 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) // @@ -684,7 +684,10 @@ class slist //! //! Complexity: Constant. reference front() - { return *this->begin(); } + { + BOOST_ASSERT(!this->empty()); + return *this->begin(); + } //! Requires: !empty() //! @@ -695,7 +698,10 @@ class slist //! //! Complexity: Constant. const_reference front() const - { return *this->begin(); } + { + BOOST_ASSERT(!this->empty()); + return *this->begin(); + } ////////////////////////////////////////////// // @@ -897,7 +903,10 @@ class slist //! //! Complexity: Amortized constant time. void pop_front() - { this->icont().pop_front_and_dispose(Destroyer(this->node_alloc())); } + { + BOOST_ASSERT(!this->empty()); + this->icont().pop_front_and_dispose(Destroyer(this->node_alloc())); + } //! Effects: Erases the element after the element pointed by prev_p //! of the list. @@ -939,7 +948,12 @@ class slist void swap(slist& x) BOOST_NOEXCEPT_IF( allocator_traits_type::propagate_on_container_swap::value || allocator_traits_type::is_always_equal::value) - { AllocHolder::swap(x); } + { + BOOST_ASSERT(allocator_traits_type::propagate_on_container_swap::value || + allocator_traits_type::is_always_equal::value || + this->get_stored_allocator() == x.get_stored_allocator()); + AllocHolder::swap(x); + } //! Effects: Erases all the elements of the list. //! @@ -1652,22 +1666,15 @@ struct has_trivial_destructor_after_move > namespace container { -#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED - }} //namespace boost{ namespace container { +#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED + // Specialization of insert_iterator so that insertions will be constant // time rather than linear time. -#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED - -#if defined(__clang__) && defined(_LIBCPP_VERSION) - #define BOOST_CONTAINER_CLANG_INLINE_STD_NS - #pragma GCC diagnostic push - #pragma GCC diagnostic ignored "-Wc++11-extensions" -#endif - -BOOST_CONTAINER_STD_NS_BEG +#include +BOOST_CONTAINER_DOC1ST(namespace std {, BOOST_MOVE_STD_NS_BEG) template class insert_iterator > @@ -1700,14 +1707,8 @@ class insert_iterator > insert_iterator& operator++(int){ return *this; } }; -BOOST_CONTAINER_STD_NS_END - -#ifdef BOOST_CONTAINER_CLANG_INLINE_STD_NS - #pragma GCC diagnostic pop - #undef BOOST_CONTAINER_CLANG_INLINE_STD_NS -#endif //BOOST_CONTAINER_CLANG_INLINE_STD_NS - -#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED +BOOST_CONTAINER_DOC1ST( }, BOOST_MOVE_STD_NS_END) +#include #include diff --git a/boost/container/small_vector.hpp b/boost/container/small_vector.hpp index a9f7522205..4dab684764 100644 --- a/boost/container/small_vector.hpp +++ b/boost/container/small_vector.hpp @@ -117,9 +117,9 @@ class small_vector_allocator typedef typename allocator_traits::propagate_on_container_copy_assignment propagate_on_container_copy_assignment; typedef typename allocator_traits::propagate_on_container_move_assignment propagate_on_container_move_assignment; typedef typename allocator_traits::propagate_on_container_swap propagate_on_container_swap; - //! An integral constant with member `::value == false` + //! An integral constant with member `value == false` typedef BOOST_CONTAINER_IMPDEF(container_detail::bool_) is_always_equal; - //! An integral constant with member `::value == true` + //! An integral constant with member `value == true` typedef BOOST_CONTAINER_IMPDEF(container_detail::bool_) is_partially_propagable; BOOST_CONTAINER_DOCIGN(typedef container_detail::version_type version;) @@ -289,20 +289,25 @@ class small_vector_allocator //! This class consists of common code from all small_vector types that don't depend on the //! "N" template parameter. This class is non-copyable and non-destructible, so this class tipically //! used as reference argument to functions that read or write small vectors. Since `small_vector` -//! derives from `small_vector_base`, the conversion to `small_vector_base` is implicit: -//! +//! derives from `small_vector_base`, the conversion to `small_vector_base` is implicit +//! 
 //!
 //! //Clients can pass any small_vector.
 //! void read_any_small_vector_of_foo(const small_vector_base &in_parameter);
+//!
 //! void modify_any_small_vector_of_foo(small_vector_base &out_parameter);
-//! 
+//!
 //! void some_function()
 //! {
+//! 
 //!    small_vector myvector;
+//!
 //!    read_any_small_vector_of_foo(myvector);   // Reads myvector
+//!
 //!    modify_any_small_vector_of_foo(myvector); // Modifies myvector
+//! 
 //! }
-//! 
+//!
//! //! All `boost::container:vector` member functions are inherited. See `vector` documentation for details. //! diff --git a/boost/container/stable_vector.hpp b/boost/container/stable_vector.hpp index 6aca69bde6..a332dbc66c 100644 --- a/boost/container/stable_vector.hpp +++ b/boost/container/stable_vector.hpp @@ -1,6 +1,6 @@ ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2008-2013. Distributed under the Boost +// (C) Copyright Ion Gaztanaga 2008-2015. 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) // @@ -1196,7 +1196,10 @@ class stable_vector //! //! Complexity: Constant. reference front() BOOST_NOEXCEPT_OR_NOTHROW - { return static_cast(*this->index.front()).value; } + { + BOOST_ASSERT(!this->empty()); + return static_cast(*this->index.front()).value; + } //! Requires: !empty() //! @@ -1207,7 +1210,10 @@ class stable_vector //! //! Complexity: Constant. const_reference front() const BOOST_NOEXCEPT_OR_NOTHROW - { return static_cast(*this->index.front()).value; } + { + BOOST_ASSERT(!this->empty()); + return static_cast(*this->index.front()).value; + } //! Requires: !empty() //! @@ -1218,7 +1224,10 @@ class stable_vector //! //! Complexity: Constant. reference back() BOOST_NOEXCEPT_OR_NOTHROW - { return static_cast(*this->index[this->size()-1u]).value; } + { + BOOST_ASSERT(!this->empty()); + return static_cast(*this->index[this->size()-1u]).value; + } //! Requires: !empty() //! @@ -1229,7 +1238,10 @@ class stable_vector //! //! Complexity: Constant. const_reference back() const BOOST_NOEXCEPT_OR_NOTHROW - { return static_cast(*this->index[this->size()-1u]).value; } + { + BOOST_ASSERT(!this->empty()); + return static_cast(*this->index[this->size()-1u]).value; + } //! Requires: size() > n. //! @@ -1241,7 +1253,7 @@ class stable_vector //! Complexity: Constant. reference operator[](size_type n) BOOST_NOEXCEPT_OR_NOTHROW { - BOOST_ASSERT(n < this->size()); + BOOST_ASSERT(this->size() > n); return static_cast(*this->index[n]).value; } @@ -1255,7 +1267,7 @@ class stable_vector //! Complexity: Constant. const_reference operator[](size_type n) const BOOST_NOEXCEPT_OR_NOTHROW { - BOOST_ASSERT(n < this->size()); + BOOST_ASSERT(this->size() > n); return static_cast(*this->index[n]).value; } @@ -1386,6 +1398,7 @@ class stable_vector template iterator emplace(const_iterator p, Args && ...args) { + BOOST_ASSERT(this->priv_in_range_or_end(p)); size_type pos_n = p - cbegin(); typedef emplace_functor EmplaceFunctor; typedef emplace_iterator EmplaceIterator; @@ -1410,6 +1423,7 @@ class stable_vector BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ iterator emplace(const_iterator p BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ {\ + BOOST_ASSERT(this->priv_in_range_or_end(p));\ typedef emplace_functor##N\ BOOST_MOVE_LT##N BOOST_MOVE_TARG##N BOOST_MOVE_GT##N EmplaceFunctor;\ typedef emplace_iterator EmplaceIterator;\ @@ -1483,6 +1497,7 @@ class stable_vector //! Complexity: Linear to n. iterator insert(const_iterator p, size_type n, const T& t) { + BOOST_ASSERT(this->priv_in_range_or_end(p)); STABLE_VECTOR_CHECK_INVARIANT; typedef constant_iterator cvalue_iterator; return this->insert(p, cvalue_iterator(t, n), cvalue_iterator()); @@ -1499,6 +1514,7 @@ class stable_vector //! Complexity: Linear to distance [il.begin(), il.end()). iterator insert(const_iterator p, std::initializer_list il) { + //Position checks done by insert() STABLE_VECTOR_CHECK_INVARIANT; return insert(p, il.begin(), il.end()); } @@ -1515,17 +1531,19 @@ class stable_vector //! //! Complexity: Linear to distance [first, last). template - #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) - typename container_detail::disable_if_or - < iterator - , container_detail::is_convertible - , container_detail::is_not_input_iterator - >::type - #else - iterator - #endif - insert(const_iterator p, InputIterator first, InputIterator last) - { + iterator insert(const_iterator p, InputIterator first, InputIterator last + #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED) + //Put this as argument instead of the return type as old GCC's like 3.4 + //detect this and the next disable_if_or as overloads + , typename container_detail::disable_if_or + < void + , container_detail::is_convertible + , container_detail::is_not_input_iterator + >::type* = 0 + #endif + ) + { + BOOST_ASSERT(this->priv_in_range_or_end(p)); STABLE_VECTOR_CHECK_INVARIANT; const size_type pos_n = p - this->cbegin(); for(; first != last; ++first){ @@ -1543,6 +1561,7 @@ class stable_vector >::type insert(const_iterator p, FwdIt first, FwdIt last) { + BOOST_ASSERT(this->priv_in_range_or_end(p)); const size_type num_new = static_cast(boost::container::iterator_distance(first, last)); const size_type idx = static_cast(p - this->cbegin()); if(num_new){ @@ -1556,12 +1575,12 @@ class stable_vector //Prepare rollback insert_rollback rollback(*this, it_past_newly_constructed, it_past_new); while(first != last){ - const node_ptr p = this->priv_get_from_pool(); - BOOST_ASSERT(!!p); + const node_ptr n = this->priv_get_from_pool(); + BOOST_ASSERT(!!n); //Put it in the index so rollback can return it in pool if construct_in_place throws - *it_past_newly_constructed = p; + *it_past_newly_constructed = n; //Constructs and fixes up pointers This can throw - this->priv_build_node_from_it(p, it_past_newly_constructed, first); + this->priv_build_node_from_it(n, it_past_newly_constructed, first); ++first; ++it_past_newly_constructed; } @@ -1581,7 +1600,10 @@ class stable_vector //! //! Complexity: Constant time. void pop_back() BOOST_NOEXCEPT_OR_NOTHROW - { this->erase(--this->cend()); } + { + BOOST_ASSERT(!this->empty()); + this->erase(--this->cend()); + } //! Effects: Erases the element at p. //! @@ -1591,6 +1613,7 @@ class stable_vector //! last element. Constant if p is the last element. iterator erase(const_iterator p) BOOST_NOEXCEPT_OR_NOTHROW { + BOOST_ASSERT(this->priv_in_range(p)); STABLE_VECTOR_CHECK_INVARIANT; const size_type d = p - this->cbegin(); index_iterator it = this->index.begin() + d; @@ -1608,6 +1631,8 @@ class stable_vector //! plus linear to the elements between p and the last element. iterator erase(const_iterator first, const_iterator last) BOOST_NOEXCEPT_OR_NOTHROW { + BOOST_ASSERT(first == last || + (first < last && this->priv_in_range(first) && this->priv_in_range_or_end(last))); STABLE_VECTOR_CHECK_INVARIANT; const const_iterator cbeg(this->cbegin()); const size_type d1 = static_cast(first - cbeg), @@ -1641,6 +1666,9 @@ class stable_vector BOOST_NOEXCEPT_IF( allocator_traits_type::propagate_on_container_swap::value || allocator_traits_type::is_always_equal::value) { + BOOST_ASSERT(allocator_traits_type::propagate_on_container_swap::value || + allocator_traits_type::is_always_equal::value || + this->get_stored_allocator() == x.get_stored_allocator()); STABLE_VECTOR_CHECK_INVARIANT; container_detail::bool_ flag; container_detail::swap_alloc(this->priv_node_alloc(), x.priv_node_alloc(), flag); @@ -1702,6 +1730,16 @@ class stable_vector #ifndef BOOST_CONTAINER_DOXYGEN_INVOKED private: + bool priv_in_range(const_iterator pos) const + { + return (this->begin() <= pos) && (pos < this->end()); + } + + bool priv_in_range_or_end(const_iterator pos) const + { + return (this->begin() <= pos) && (pos <= this->end()); + } + size_type priv_index_of(node_ptr p) const { //Check range @@ -1807,12 +1845,14 @@ class stable_vector iterator priv_insert(const_iterator p, const value_type &t) { + BOOST_ASSERT(this->priv_in_range_or_end(p)); typedef constant_iterator cvalue_iterator; return this->insert(p, cvalue_iterator(t, 1), cvalue_iterator()); } iterator priv_insert(const_iterator p, BOOST_RV_REF(T) x) { + BOOST_ASSERT(this->priv_in_range_or_end(p)); typedef repeat_iterator repeat_it; typedef boost::move_iterator repeat_move_it; //Just call more general insert(p, size, value) and return iterator diff --git a/boost/container/static_vector.hpp b/boost/container/static_vector.hpp index c36832dfa3..69540dcc7b 100644 --- a/boost/container/static_vector.hpp +++ b/boost/container/static_vector.hpp @@ -48,7 +48,7 @@ class static_storage_allocator {} static_storage_allocator & operator=(const static_storage_allocator &) BOOST_NOEXCEPT_OR_NOTHROW - {} + { return *this; } T* internal_storage() const BOOST_NOEXCEPT_OR_NOTHROW { return const_cast(static_cast(static_cast(&storage))); } @@ -645,7 +645,7 @@ public: //! //! @brief Assigns a range [il.begin(), il.end()) of Values to this container. //! - //! @param first std::initializer_list with values used to construct new content of this container. + //! @param il std::initializer_list with values used to construct new content of this container. //! //! @par Throws //! If Value's copy constructor or copy assignment throws, @@ -809,7 +809,7 @@ public: //! //! @brief Returns the index of the element pointed by p. //! - //! @param i The element's index. + //! @param p An iterator to the element. //! //! @return The index of the element pointed by p. //! @@ -824,7 +824,7 @@ public: //! //! @brief Returns the index of the element pointed by p. //! - //! @param i The index of the element pointed by p. + //! @param p A const_iterator to the element. //! //! @return a const_iterator to the i-th element. //! diff --git a/boost/container/string.hpp b/boost/container/string.hpp index 7399223904..33f5f66176 100644 --- a/boost/container/string.hpp +++ b/boost/container/string.hpp @@ -1,6 +1,6 @@ ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2005-2013. Distributed under the Boost +// (C) Copyright Ion Gaztanaga 2005-2015. 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) // @@ -93,11 +93,11 @@ class basic_string_base : members_() { init(); } - basic_string_base(const allocator_type& a) + explicit basic_string_base(const allocator_type& a) : members_(a) { init(); } - basic_string_base(BOOST_RV_REF(allocator_type) a) + explicit basic_string_base(BOOST_RV_REF(allocator_type) a) : members_(boost::move(a)) { this->init(); } @@ -108,6 +108,13 @@ class basic_string_base this->allocate_initial_block(n); } + explicit basic_string_base(size_type n) + : members_() + { + this->init(); + this->allocate_initial_block(n); + } + ~basic_string_base() { if(!this->is_short()){ @@ -647,10 +654,22 @@ class basic_string } } + //! Effects: Constructs a basic_string with a default-constructed allocator, + //! and is initialized by a specific number of characters of the s string. + basic_string(const basic_string& s, size_type pos, size_type n = npos) + : base_t() + { + this->priv_terminate_string(); + if (pos > s.size()) + throw_out_of_range("basic_string::basic_string out of range position"); + else + this->assign + (s.begin() + pos, s.begin() + pos + container_detail::min_value(n, s.size() - pos)); + } + //! Effects: Constructs a basic_string taking the allocator as parameter, //! and is initialized by a specific number of characters of the s string. - basic_string(const basic_string& s, size_type pos, size_type n = npos, - const allocator_type& a = allocator_type()) + basic_string(const basic_string& s, size_type pos, size_type n, const allocator_type& a) : base_t(a) { this->priv_terminate_string(); @@ -661,46 +680,93 @@ class basic_string (s.begin() + pos, s.begin() + pos + container_detail::min_value(n, s.size() - pos)); } + //! Effects: Constructs a basic_string taking a default-constructed allocator, + //! and is initialized by a specific number of characters of the s c-string. + basic_string(const CharT* s, size_type n) + : base_t() + { + this->priv_terminate_string(); + this->assign(s, s + n); + } + //! Effects: Constructs a basic_string taking the allocator as parameter, //! and is initialized by a specific number of characters of the s c-string. - basic_string(const CharT* s, size_type n, const allocator_type& a = allocator_type()) + basic_string(const CharT* s, size_type n, const allocator_type& a) : base_t(a) { this->priv_terminate_string(); this->assign(s, s + n); } + //! Effects: Constructs a basic_string with a default-constructed allocator, + //! and is initialized by the null-terminated s c-string. + basic_string(const CharT* s) + : base_t() + { + this->priv_terminate_string(); + this->assign(s, s + Traits::length(s)); + } + //! Effects: Constructs a basic_string taking the allocator as parameter, //! and is initialized by the null-terminated s c-string. - basic_string(const CharT* s, const allocator_type& a = allocator_type()) + basic_string(const CharT* s, const allocator_type& a) : base_t(a) { this->priv_terminate_string(); this->assign(s, s + Traits::length(s)); } + + //! Effects: Constructs a basic_string with a default-constructed allocator, + //! and is initialized by n copies of c. + basic_string(size_type n, CharT c) + : base_t() + { + this->priv_terminate_string(); + this->assign(n, c); + } + //! Effects: Constructs a basic_string taking the allocator as parameter, //! and is initialized by n copies of c. - basic_string(size_type n, CharT c, const allocator_type& a = allocator_type()) + basic_string(size_type n, CharT c, const allocator_type& a) : base_t(a) { this->priv_terminate_string(); this->assign(n, c); } + //! Effects: Constructs a basic_string with a default-constructed allocator, + //! and is initialized by n default-initialized characters. + basic_string(size_type n, default_init_t) + : base_t(n + 1) + { + this->priv_size(n); + this->priv_terminate_string(); + } + //! Effects: Constructs a basic_string taking the allocator as parameter, //! and is initialized by n default-initialized characters. - basic_string(size_type n, default_init_t, const allocator_type& a = allocator_type()) + basic_string(size_type n, default_init_t, const allocator_type& a) : base_t(a, n + 1) { this->priv_size(n); this->priv_terminate_string(); } + //! Effects: Constructs a basic_string with a default-constructed allocator, + //! and a range of iterators. + template + basic_string(InputIterator f, InputIterator l) + : base_t() + { + this->priv_terminate_string(); + this->assign(f, l); + } + //! Effects: Constructs a basic_string taking the allocator as parameter, //! and a range of iterators. template - basic_string(InputIterator f, InputIterator l, const allocator_type& a = allocator_type()) + basic_string(InputIterator f, InputIterator l, const allocator_type& a) : base_t(a) { this->priv_terminate_string(); @@ -1058,6 +1124,62 @@ class basic_string // ////////////////////////////////////////////// + //! Requires: !empty() + //! + //! Effects: Returns a reference to the first + //! element of the container. + //! + //! Throws: Nothing. + //! + //! Complexity: Constant. + reference front() BOOST_NOEXCEPT_OR_NOTHROW + { + BOOST_ASSERT(!this->empty()); + return *this->priv_addr(); + } + + //! Requires: !empty() + //! + //! Effects: Returns a const reference to the first + //! element of the container. + //! + //! Throws: Nothing. + //! + //! Complexity: Constant. + const_reference front() const BOOST_NOEXCEPT_OR_NOTHROW + { + BOOST_ASSERT(!this->empty()); + return *this->priv_addr(); + } + + //! Requires: !empty() + //! + //! Effects: Returns a reference to the last + //! element of the container. + //! + //! Throws: Nothing. + //! + //! Complexity: Constant. + reference back() BOOST_NOEXCEPT_OR_NOTHROW + { + BOOST_ASSERT(!this->empty()); + return *(this->priv_addr() + (this->size() - 1u) ); + } + + //! Requires: !empty() + //! + //! Effects: Returns a const reference to the last + //! element of the container. + //! + //! Throws: Nothing. + //! + //! Complexity: Constant. + const_reference back() const BOOST_NOEXCEPT_OR_NOTHROW + { + BOOST_ASSERT(!this->empty()); + return *(this->priv_addr() + (this->size() - 1u) ); + } + //! Requires: size() > n. //! //! Effects: Returns a reference to the nth element @@ -1067,7 +1189,10 @@ class basic_string //! //! Complexity: Constant. reference operator[](size_type n) BOOST_NOEXCEPT_OR_NOTHROW - { return *(this->priv_addr() + n); } + { + BOOST_ASSERT(this->size() > n); + return *(this->priv_addr() + n); + } //! Requires: size() > n. //! @@ -1078,7 +1203,10 @@ class basic_string //! //! Complexity: Constant. const_reference operator[](size_type n) const BOOST_NOEXCEPT_OR_NOTHROW - { return *(this->priv_addr() + n); } + { + BOOST_ASSERT(this->size() > n); + return *(this->priv_addr() + n); + } //! Requires: size() > n. //! @@ -1560,6 +1688,18 @@ class basic_string } #endif + //! Effects: Removes the last element from the container. + //! + //! Throws: Nothing. + //! + //! Complexity: Constant time. + void pop_back() BOOST_NOEXCEPT_OR_NOTHROW + { + BOOST_ASSERT(!this->empty()); + iterator p = this->end(); + this->erase(--p); + } + //! Requires: pos <= size() //! //! Effects: Determines the effective length xlen of the string to be removed as the smaller of n and size() - pos. @@ -1621,18 +1761,6 @@ class basic_string return iterator(f); } - //! Requires: !empty() - //! - //! Throws: Nothing - //! - //! Effects: Equivalent to erase(size() - 1, 1). - void pop_back() BOOST_NOEXCEPT_OR_NOTHROW - { - const size_type old_size = this->priv_size(); - Traits::assign(this->priv_addr()[old_size-1], CharT(0)); - this->priv_size(old_size-1);; - } - //! Effects: Erases all the elements of the vector. //! //! Throws: Nothing. diff --git a/boost/container/uses_allocator.hpp b/boost/container/uses_allocator.hpp new file mode 100644 index 0000000000..2bcc465890 --- /dev/null +++ b/boost/container/uses_allocator.hpp @@ -0,0 +1,169 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2011-2013. Distributed under the Boost +// Software License, Version 1.0. (See accompanying file +// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) +// +// See http://www.boost.org/libs/container for documentation. +// +////////////////////////////////////////////////////////////////////////////// + +#ifndef BOOST_CONTAINER_USES_ALLOCATOR_HPP +#define BOOST_CONTAINER_USES_ALLOCATOR_HPP + +#include +#include + +namespace boost { +namespace container { + +//! Remark: if a specialization constructible_with_allocator_suffix::value is true, indicates that T may be constructed +//! with an allocator as its last constructor argument. Ideally, all constructors of T (including the +//! copy and move constructors) should have a variant that accepts a final argument of +//! allocator_type. +//! +//! Requires: if a specialization constructible_with_allocator_suffix::value is true, T must have a nested type, +//! allocator_type and at least one constructor for which allocator_type is the last +//! parameter. If not all constructors of T can be called with a final allocator_type argument, +//! and if T is used in a context where a container must call such a constructor, then the program is +//! ill-formed. +//! +//! +//! template > +//! class Z { +//! public: +//! typedef Allocator allocator_type; +//! +//! // Default constructor with optional allocator suffix +//! Z(const allocator_type& a = allocator_type()); +//! +//! // Copy constructor and allocator-extended copy constructor +//! Z(const Z& zz); +//! Z(const Z& zz, const allocator_type& a); +//! }; +//! +//! // Specialize trait for class template Z +//! template > +//! struct constructible_with_allocator_suffix > +//! { static const bool value = true; }; +//! +//! +//! Note: This trait is a workaround inspired by "N2554: The Scoped A Model (Rev 2)" +//! (Pablo Halpern, 2008-02-29) to backport the scoped allocator model to C++03, as +//! in C++03 there is no mechanism to detect if a type can be constructed from arbitrary arguments. +//! Applications aiming portability with several compilers should always define this trait. +//! +//! In conforming C++11 compilers or compilers supporting SFINAE expressions +//! (when BOOST_NO_SFINAE_EXPR is NOT defined), this trait is ignored and C++11 rules will be used +//! to detect if a type should be constructed with suffix or prefix allocator arguments. +template +struct constructible_with_allocator_suffix +{ static const bool value = false; }; + +//! Remark: if a specialization constructible_with_allocator_prefix::value is true, indicates that T may be constructed +//! with allocator_arg and T::allocator_type as its first two constructor arguments. +//! Ideally, all constructors of T (including the copy and move constructors) should have a variant +//! that accepts these two initial arguments. +//! +//! Requires: specialization constructible_with_allocator_prefix::value is true, T must have a nested type, +//! allocator_type and at least one constructor for which allocator_arg_t is the first +//! parameter and allocator_type is the second parameter. If not all constructors of T can be +//! called with these initial arguments, and if T is used in a context where a container must call such +//! a constructor, then the program is ill-formed. +//! +//! +//! template > +//! class Y { +//! public: +//! typedef Allocator allocator_type; +//! +//! // Default constructor with and allocator-extended default constructor +//! Y(); +//! Y(allocator_arg_t, const allocator_type& a); +//! +//! // Copy constructor and allocator-extended copy constructor +//! Y(const Y& yy); +//! Y(allocator_arg_t, const allocator_type& a, const Y& yy); +//! +//! // Variadic constructor and allocator-extended variadic constructor +//! template Y(Args&& args...); +//! template +//! Y(allocator_arg_t, const allocator_type& a, BOOST_FWD_REF(Args)... args); +//! }; +//! +//! // Specialize trait for class template Y +//! template > +//! struct constructible_with_allocator_prefix > +//! { static const bool value = true; }; +//! +//! +//! +//! Note: This trait is a workaround inspired by "N2554: The Scoped Allocator Model (Rev 2)" +//! (Pablo Halpern, 2008-02-29) to backport the scoped allocator model to C++03, as +//! in C++03 there is no mechanism to detect if a type can be constructed from arbitrary arguments. +//! Applications aiming portability with several compilers should always define this trait. +//! +//! In conforming C++11 compilers or compilers supporting SFINAE expressions +//! (when BOOST_NO_SFINAE_EXPR is NOT defined), this trait is ignored and C++11 rules will be used +//! to detect if a type should be constructed with suffix or prefix allocator arguments. +template +struct constructible_with_allocator_prefix +{ static const bool value = false; }; + +#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED + +namespace container_detail { + +template +struct uses_allocator_imp +{ + // Use SFINAE (Substitution Failure Is Not An Error) to detect the + // presence of an 'allocator_type' nested type convertilble from Allocator. + private: + typedef char yes_type; + struct no_type{ char dummy[2]; }; + + // Match this function if T::allocator_type exists and is + // implicitly convertible from Allocator + template + static yes_type test(typename U::allocator_type); + + // Match this function if T::allocator_type exists and it's type is `erased_type`. + template + static typename container_detail::enable_if + < container_detail::is_same + , yes_type + >::type test(const V&); + + // Match this function if TypeT::allocator_type does not exist or is + // not convertible from Allocator. + template + static no_type test(...); + static Allocator alloc; // Declared but not defined + + public: + static const bool value = sizeof(test(alloc)) == sizeof(yes_type); +}; + +} //namespace container_detail { + +#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED + +//! Remark: Automatically detects whether T has a nested allocator_type that is convertible from +//! Allocator. Meets the BinaryTypeTrait requirements ([meta.rqmts] 20.4.1). A program may +//! specialize this type to define uses_allocator::value as true for a T of user-defined type if T does not +//! have a nested allocator_type but is nonetheless constructible using the specified Allocator where either: +//! the first argument of a constructor has type allocator_arg_t and the second argument has type Alloc or +//! the last argument of a constructor has type Alloc. +//! +//! Result: uses_allocator::value== true if a type T::allocator_type +//! exists and either is_convertible::value != false or T::allocator_type +//! is an alias `erased_type`. False otherwise. +template +struct uses_allocator + : container_detail::uses_allocator_imp +{}; + +}} //namespace boost::container + +#endif //BOOST_CONTAINER_USES_ALLOCATOR_HPP diff --git a/boost/container/uses_allocator_fwd.hpp b/boost/container/uses_allocator_fwd.hpp new file mode 100644 index 0000000000..d8fe67fbfe --- /dev/null +++ b/boost/container/uses_allocator_fwd.hpp @@ -0,0 +1,73 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2015-2015. 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_USES_ALLOCATOR_FWD_HPP +#define BOOST_CONTAINER_USES_ALLOCATOR_FWD_HPP + +#include +#include + +//! \file +//! This header forward declares boost::container::constructible_with_allocator_prefix, +//! boost::container::constructible_with_allocator_suffix and +//! boost::container::uses_allocator. Also defines the following types: + +namespace boost { +namespace container { + +#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED + + template + struct std_allocator_arg_holder + { + static ::std::allocator_arg_t *dummy; + }; + + template + ::std::allocator_arg_t *std_allocator_arg_holder::dummy; + +typedef const std::allocator_arg_t & allocator_arg_t; + +#else + +//! The allocator_arg_t struct is an empty structure type used as a unique type to +//! disambiguate constructor and function overloading. Specifically, several types +//! have constructors with allocator_arg_t as the first argument, immediately followed +//! by an argument of a type that satisfies Allocator requirements +typedef unspecified allocator_arg_t; + +#endif //#ifndef BOOST_CONTAINER_DOXYGEN_INVOKED + +//! The `erased_type` struct is an empty struct that serves as a placeholder for a type +//! T in situations where the actual type T is determined at runtime. For example, +//! the nested type, `allocator_type`, is an alias for `erased_type` in classes that +//! use type-erased allocators. +struct erased_type {}; + +//! A instance of type +//! allocator_arg_t +static allocator_arg_t allocator_arg = BOOST_CONTAINER_DOC1ST(unspecified, *std_allocator_arg_holder<>::dummy); + +// @cond + +template +struct constructible_with_allocator_suffix; + +template +struct constructible_with_allocator_prefix; + +template +struct uses_allocator; + +// @endcond + +}} // namespace boost { namespace container { + +#endif //BOOST_CONTAINER_USES_ALLOCATOR_HPP diff --git a/boost/container/vector.hpp b/boost/container/vector.hpp index 1cf44c8e27..e3bc1068aa 100644 --- a/boost/container/vector.hpp +++ b/boost/container/vector.hpp @@ -1,6 +1,6 @@ ////////////////////////////////////////////////////////////////////////////// // -// (C) Copyright Ion Gaztanaga 2005-2014. Distributed under the Boost +// (C) Copyright Ion Gaztanaga 2005-2015. 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) // @@ -216,7 +216,7 @@ struct vector_merge_cursor typedef SizeType size_type; typedef typename iterator_traits::reference reference; - vector_merge_cursor(T *pbeg, T *plast, BiDirValueIt valueit, Comp cmp) + vector_merge_cursor(T *pbeg, T *plast, BiDirValueIt valueit, Comp &cmp) : m_pbeg(pbeg), m_pcur(--plast), m_valueit(valueit), m_cmp(cmp) {} @@ -241,7 +241,7 @@ struct vector_merge_cursor T *const m_pbeg; T *m_pcur; BiDirValueIt m_valueit; - Comp m_cmp; + Comp &m_cmp; }; } //namespace container_detail { @@ -346,18 +346,17 @@ struct vector_alloc_holder static bool is_propagable_from(const allocator_type &from_alloc, pointer p, const allocator_type &to_alloc, bool const propagate_allocator) { (void)propagate_allocator; (void)p; (void)to_alloc; (void)from_alloc; - return (!allocator_traits_type::is_partially_propagable::value || - !allocator_traits_type::storage_is_unpropagable(from_alloc, p)) && - (propagate_allocator || allocator_traits_type::equal(from_alloc, to_alloc)); + const bool all_storage_propagable = !allocator_traits_type::is_partially_propagable::value || + !allocator_traits_type::storage_is_unpropagable(from_alloc, p); + return all_storage_propagable && (propagate_allocator || allocator_traits_type::equal(from_alloc, to_alloc)); } static bool are_swap_propagable(const allocator_type &l_a, pointer l_p, const allocator_type &r_a, pointer r_p, bool const propagate_allocator) { (void)propagate_allocator; (void)l_p; (void)r_p; (void)l_a; (void)r_a; - return (!allocator_traits_type::is_partially_propagable::value || - (!allocator_traits_type::storage_is_unpropagable(r_a, r_p) && - !allocator_traits_type::storage_is_unpropagable(l_a, l_p)) - ) && (propagate_allocator || allocator_traits_type::equal(l_a, r_a)); + const bool all_storage_propagable = !allocator_traits_type::is_partially_propagable::value || + !(allocator_traits_type::storage_is_unpropagable(l_a, l_p) || allocator_traits_type::storage_is_unpropagable(r_a, r_p)); + return all_storage_propagable && (propagate_allocator || allocator_traits_type::equal(l_a, r_a)); } //Constructor, does not throw @@ -646,7 +645,7 @@ struct vector_alloc_holder this->priv_deep_swap(x); } - void swap_resources(vector_alloc_holder &x) BOOST_NOEXCEPT_OR_NOTHROW + void swap_resources(vector_alloc_holder &) BOOST_NOEXCEPT_OR_NOTHROW { //Containers with version 0 allocators can't be moved without moving elements one by one throw_bad_alloc(); } @@ -819,7 +818,7 @@ class vector this->num_alloc += n != 0; #endif boost::container::uninitialized_value_init_alloc_n - (this->m_holder.alloc(), n, container_detail::to_raw_pointer(this->m_holder.start())); + (this->m_holder.alloc(), n, this->priv_raw_begin()); } //! Effects: Constructs a vector that will use a copy of allocator a @@ -838,7 +837,7 @@ class vector this->num_alloc += n != 0; #endif boost::container::uninitialized_default_init_alloc_n - (this->m_holder.alloc(), n, container_detail::to_raw_pointer(this->m_holder.start())); + (this->m_holder.alloc(), n, this->priv_raw_begin()); } //! Effects: Constructs a vector that will use a copy of allocator a @@ -855,7 +854,7 @@ class vector this->num_alloc += n != 0; #endif boost::container::uninitialized_value_init_alloc_n - (this->m_holder.alloc(), n, container_detail::to_raw_pointer(this->m_holder.start())); + (this->m_holder.alloc(), n, this->priv_raw_begin()); } //! Effects: Constructs a vector that will use a copy of allocator a @@ -874,7 +873,7 @@ class vector this->num_alloc += n != 0; #endif boost::container::uninitialized_default_init_alloc_n - (this->m_holder.alloc(), n, container_detail::to_raw_pointer(this->m_holder.start())); + (this->m_holder.alloc(), n, this->priv_raw_begin()); } //! Effects: Constructs a vector @@ -891,7 +890,7 @@ class vector this->num_alloc += n != 0; #endif boost::container::uninitialized_fill_alloc_n - (this->m_holder.alloc(), value, n, container_detail::to_raw_pointer(this->m_holder.start())); + (this->m_holder.alloc(), value, n, this->priv_raw_begin()); } //! Effects: Constructs a vector that will use a copy of allocator a @@ -908,7 +907,7 @@ class vector this->num_alloc += n != 0; #endif boost::container::uninitialized_fill_alloc_n - (this->m_holder.alloc(), value, n, container_detail::to_raw_pointer(this->m_holder.start())); + (this->m_holder.alloc(), value, n, this->priv_raw_begin()); } //! Effects: Constructs a vector @@ -952,8 +951,8 @@ class vector this->num_alloc += x.size() != 0; #endif ::boost::container::uninitialized_copy_alloc_n - ( this->m_holder.alloc(), container_detail::to_raw_pointer(x.m_holder.start()) - , x.size(), container_detail::to_raw_pointer(this->m_holder.start())); + ( this->m_holder.alloc(), x.priv_raw_begin() + , x.size(), this->priv_raw_begin()); } //! Effects: Move constructor. Moves x's resources to *this. @@ -1013,8 +1012,8 @@ class vector this->num_alloc += x.size() != 0; #endif ::boost::container::uninitialized_copy_alloc_n_source - ( this->m_holder.alloc(), container_detail::to_raw_pointer(x.m_holder.start()) - , x.size(), container_detail::to_raw_pointer(this->m_holder.start())); + ( this->m_holder.alloc(), x.priv_raw_begin() + , x.size(), this->priv_raw_begin()); } //! Effects: Move constructor using the specified allocator. @@ -1038,8 +1037,8 @@ class vector this->num_alloc += n != 0; #endif ::boost::container::uninitialized_move_alloc_n_source - ( this->m_holder.alloc(), container_detail::to_raw_pointer(x.m_holder.start()) - , n, container_detail::to_raw_pointer(this->m_holder.start())); + ( this->m_holder.alloc(), x.priv_raw_begin() + , n, this->priv_raw_begin()); } } @@ -1052,7 +1051,7 @@ class vector ~vector() BOOST_NOEXCEPT_OR_NOTHROW { boost::container::destroy_alloc_n - (this->get_stored_allocator(), container_detail::to_raw_pointer(this->m_holder.start()), this->m_holder.m_size); + (this->get_stored_allocator(), this->priv_raw_begin(), this->m_holder.m_size); //vector_alloc_holder deallocates the data } @@ -1098,6 +1097,7 @@ class vector BOOST_NOEXCEPT_IF(allocator_traits_type::propagate_on_container_move_assignment::value || allocator_traits_type::is_always_equal::value) { + BOOST_ASSERT(&x != this); this->priv_move_assign(boost::move(x)); return *this; } @@ -1177,7 +1177,7 @@ class vector if (first == last){ //There are no more elements in the sequence, erase remaining - T* const end_pos = this->back_raw(); + T* const end_pos = this->priv_raw_end(); const size_type n = static_cast(end_pos - container_detail::iterator_to_raw_pointer(cur)); this->priv_destroy_last_n(n); } @@ -1513,7 +1513,10 @@ class vector //! //! Complexity: Constant. reference front() BOOST_NOEXCEPT_OR_NOTHROW - { return *this->m_holder.start(); } + { + BOOST_ASSERT(!this->empty()); + return *this->m_holder.start(); + } //! Requires: !empty() //! @@ -1524,7 +1527,10 @@ class vector //! //! Complexity: Constant. const_reference front() const BOOST_NOEXCEPT_OR_NOTHROW - { return *this->m_holder.start(); } + { + BOOST_ASSERT(!this->empty()); + return *this->m_holder.start(); + } //! Requires: !empty() //! @@ -1536,7 +1542,7 @@ class vector //! Complexity: Constant. reference back() BOOST_NOEXCEPT_OR_NOTHROW { - BOOST_ASSERT(this->m_holder.m_size > 0); + BOOST_ASSERT(!this->empty()); return this->m_holder.start()[this->m_holder.m_size - 1]; } @@ -1550,7 +1556,7 @@ class vector //! Complexity: Constant. const_reference back() const BOOST_NOEXCEPT_OR_NOTHROW { - BOOST_ASSERT(this->m_holder.m_size > 0); + BOOST_ASSERT(!this->empty()); return this->m_holder.start()[this->m_holder.m_size - 1]; } @@ -1578,7 +1584,8 @@ class vector //! Complexity: Constant. const_reference operator[](size_type n) const BOOST_NOEXCEPT_OR_NOTHROW { - return this->m_holder.start()[n]; + BOOST_ASSERT(this->m_holder.m_size > n); + return this->m_holder.start()[n]; } //! Requires: size() >= n. @@ -1627,7 +1634,10 @@ class vector //! //! Note: Non-standard extension size_type index_of(iterator p) BOOST_NOEXCEPT_OR_NOTHROW - { return this->priv_index_of(vector_iterator_get_ptr(p)); } + { + //Range check assert done in priv_index_of + return this->priv_index_of(vector_iterator_get_ptr(p)); + } //! Requires: begin() <= p <= end(). //! @@ -1640,7 +1650,10 @@ class vector //! //! Note: Non-standard extension size_type index_of(const_iterator p) const BOOST_NOEXCEPT_OR_NOTHROW - { return this->priv_index_of(vector_iterator_get_ptr(p)); } + { + //Range check assert done in priv_index_of + return this->priv_index_of(vector_iterator_get_ptr(p)); + } //! Requires: size() > n. //! @@ -1651,7 +1664,10 @@ class vector //! //! Complexity: Constant. reference at(size_type n) - { this->priv_check_range(n); return this->m_holder.start()[n]; } + { + this->priv_throw_if_out_of_range(n); + return this->m_holder.start()[n]; + } //! Requires: size() > n. //! @@ -1662,7 +1678,10 @@ class vector //! //! Complexity: Constant. const_reference at(size_type n) const - { this->priv_check_range(n); return this->m_holder.start()[n]; } + { + this->priv_throw_if_out_of_range(n); + return this->m_holder.start()[n]; + } ////////////////////////////////////////////// // @@ -1677,7 +1696,7 @@ class vector //! //! Complexity: Constant. T* data() BOOST_NOEXCEPT_OR_NOTHROW - { return container_detail::to_raw_pointer(this->m_holder.start()); } + { return this->priv_raw_begin(); } //! Returns: A pointer such that [data(),data() + size()) is a valid range. //! For a non-empty vector, data() == &front(). @@ -1686,7 +1705,7 @@ class vector //! //! Complexity: Constant. const T * data() const BOOST_NOEXCEPT_OR_NOTHROW - { return container_detail::to_raw_pointer(this->m_holder.start()); } + { return this->priv_raw_begin(); } ////////////////////////////////////////////// // @@ -1707,7 +1726,7 @@ class vector { if (BOOST_LIKELY(this->room_enough())){ //There is more memory, just construct a new object at the end - allocator_traits_type::construct(this->m_holder.alloc(), this->back_raw(), ::boost::forward(args)...); + allocator_traits_type::construct(this->m_holder.alloc(), this->priv_raw_end(), ::boost::forward(args)...); ++this->m_holder.m_size; } else{ @@ -1731,7 +1750,7 @@ class vector const bool is_room_enough = this->room_enough() || (alloc_version::value == 2 && this->m_holder.try_expand_fwd(1u)); if (BOOST_LIKELY(is_room_enough)){ //There is more memory, just construct a new object at the end - allocator_traits_type::construct(this->m_holder.alloc(), this->back_raw(), ::boost::forward(args)...); + allocator_traits_type::construct(this->m_holder.alloc(), this->priv_raw_end(), ::boost::forward(args)...); ++this->m_holder.m_size; } return is_room_enough; @@ -1750,6 +1769,7 @@ class vector template iterator emplace(const_iterator position, BOOST_FWD_REF(Args) ...args) { + BOOST_ASSERT(this->priv_in_range_or_end(position)); //Just call more general insert(pos, size, value) and return iterator typedef container_detail::insert_emplace_proxy type; return this->priv_forward_range_insert( vector_iterator_get_ptr(position), 1 @@ -1764,7 +1784,7 @@ class vector {\ if (BOOST_LIKELY(this->room_enough())){\ allocator_traits_type::construct (this->m_holder.alloc()\ - , this->back_raw() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ + , this->priv_raw_end() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ ++this->m_holder.m_size;\ }\ else{\ @@ -1780,7 +1800,7 @@ class vector const bool is_room_enough = this->room_enough() || (alloc_version::value == 2 && this->m_holder.try_expand_fwd(1u));\ if (BOOST_LIKELY(is_room_enough)){\ allocator_traits_type::construct (this->m_holder.alloc()\ - , this->back_raw() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ + , this->priv_raw_end() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ ++this->m_holder.m_size;\ }\ return is_room_enough;\ @@ -1789,6 +1809,7 @@ class vector BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ iterator emplace(const_iterator pos BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\ {\ + BOOST_ASSERT(this->priv_in_range_or_end(pos));\ typedef container_detail::insert_emplace_proxy_arg##N type;\ return this->priv_forward_range_insert(vector_iterator_get_ptr(pos), 1, type(BOOST_MOVE_FWD##N));\ }\ @@ -1854,6 +1875,7 @@ class vector //! Complexity: Linear to n. iterator insert(const_iterator p, size_type n, const T& x) { + BOOST_ASSERT(this->priv_in_range_or_end(p)); container_detail::insert_n_copies_proxy proxy(x); return this->priv_forward_range_insert(vector_iterator_get_ptr(p), n, proxy); } @@ -1879,6 +1901,7 @@ class vector #endif ) { + BOOST_ASSERT(this->priv_in_range_or_end(pos)); const size_type n_pos = pos - this->cbegin(); iterator it(vector_iterator_get_ptr(pos)); for(;first != last; ++first){ @@ -1898,6 +1921,7 @@ class vector >::type * = 0 ) { + BOOST_ASSERT(this->priv_in_range_or_end(pos)); container_detail::insert_range_proxy proxy(first); return this->priv_forward_range_insert(vector_iterator_get_ptr(pos), boost::container::iterator_distance(first, last), proxy); } @@ -1922,6 +1946,7 @@ class vector template iterator insert(const_iterator pos, size_type num, InIt first, InIt last) { + BOOST_ASSERT(this->priv_in_range_or_end(pos)); BOOST_ASSERT(container_detail::is_input_iterator::value || num == static_cast(boost::container::iterator_distance(first, last))); (void)last; @@ -1940,17 +1965,19 @@ class vector //! Complexity: Linear to the range [il.begin(), il.end()). iterator insert(const_iterator position, std::initializer_list il) { + //Assertion done in insert() return this->insert(position, il.begin(), il.end()); } #endif - //! Effects: Removes the last element from the vector. + //! Effects: Removes the last element from the container. //! //! Throws: Nothing. //! //! Complexity: Constant time. void pop_back() BOOST_NOEXCEPT_OR_NOTHROW { + BOOST_ASSERT(!this->empty()); //Destroy last element this->priv_destroy_last(); } @@ -1963,9 +1990,10 @@ class vector //! last element. Constant if pos is the last element. iterator erase(const_iterator position) { + BOOST_ASSERT(this->priv_in_range(position)); const pointer p = vector_iterator_get_ptr(position); T *const pos_ptr = container_detail::to_raw_pointer(p); - T *const beg_ptr = container_detail::to_raw_pointer(this->m_holder.start()); + T *const beg_ptr = this->priv_raw_begin(); T *const new_end_ptr = ::boost::container::move(pos_ptr + 1, beg_ptr + this->m_holder.m_size, pos_ptr); //Move elements forward and destroy last this->priv_destroy_last(pos_ptr == new_end_ptr); @@ -1980,8 +2008,10 @@ class vector //! plus linear to the elements between pos and the last element. iterator erase(const_iterator first, const_iterator last) { + BOOST_ASSERT(first == last || + (first < last && this->priv_in_range(first) && this->priv_in_range_or_end(last))); if (first != last){ - T* const old_end_ptr = this->back_raw(); + T* const old_end_ptr = this->priv_raw_end(); T* const first_ptr = container_detail::to_raw_pointer(vector_iterator_get_ptr(first)); T* const last_ptr = container_detail::to_raw_pointer(vector_iterator_get_ptr(last)); T* const ptr = container_detail::to_raw_pointer(boost::container::move(last_ptr, old_end_ptr, first_ptr)); @@ -2128,7 +2158,7 @@ class vector { const size_type old_size_pos = this->size(); this->reserve(old_size_pos + element_count); - T* const begin_ptr = container_detail::to_raw_pointer(this->m_holder.start()); + T* const begin_ptr = this->priv_raw_begin(); size_type insertions_left = element_count; size_type prev_pos = old_size_pos; size_type old_hole_size = element_count; @@ -2184,48 +2214,55 @@ class vector void priv_merge(UniqueBool, BidirIt first, BidirIt last, Compare comp) { size_type const n = static_cast(boost::container::iterator_distance(first, last)); - if(BOOST_LIKELY(n)){ - size_type const s = this->size(); - if(BOOST_LIKELY(s)){ - size_type const c = this->capacity(); - size_type const free_c = (c - s); - //Use a new buffer if current one is too small for new elements, - //or there is no room for position indexes - bool new_buffer = false; - if(free_c < n){ - new_buffer = true; - } - else if(!UniqueBool::value && free_c >= n){ - typedef container_detail::vector_merge_cursor inserter_t; - T* const pbeg = container_detail::to_raw_pointer(m_holder.start()); - return this->priv_insert_ordered_at(n, inserter_t(pbeg, pbeg + s, last, comp)); - } - else if(UniqueBool::value){ //Query for room to store n + 1 indexes (+1 to guarantee potential alignment overhead). - //No need to destroy them as they are integral types, which simplifies things a lot. - std::size_t const sz_vlt = sizeof(value_type); - std::size_t const sz_szt = sizeof(size_type); - new_buffer = (c-s-n)*sz_vlt/sz_szt < (n+1); - } - - if(new_buffer){ - size_type const new_size = s + n; - size_type new_cap = new_size; - pointer p = pointer(); - p = this->m_holder.allocation_command(allocate_new, new_size, new_cap, p); - this->priv_merge_in_new_buffer(UniqueBool(), first, n, comp, p, new_cap); - } - else{ - //Use trailing memory to store position offsets + size_type const s = this->size(); + if(BOOST_LIKELY(s)){ + size_type const c = this->capacity(); + size_type const free_c = (c - s); + //Use a new buffer if current one is too small for new elements, + //or there is no room for position indexes + if(free_c < n){ + size_type const new_size = s + n; + size_type new_cap = new_size; + pointer p = pointer(); + p = this->m_holder.allocation_command(allocate_new, new_size, new_cap, p); + this->priv_merge_in_new_buffer(UniqueBool(), first, n, comp, p, new_cap); + } + else if(!UniqueBool::value && free_c >= n){ + typedef container_detail::vector_merge_cursor inserter_t; + T* const pbeg = this->priv_raw_begin(); + return this->priv_insert_ordered_at(n, inserter_t(pbeg, pbeg + s, last, comp)); + } + else{ //UniqueBool::value == true and free_c >= n + std::size_t remaining = n; + static const std::size_t PosCount = 64u; + size_type positions[PosCount]; + size_type *indexes = 0; + while(remaining){ + //Query for room to store indexes in the remaining buffer uintptr_t const szt_align_mask = container_detail::alignment_of::value - 1; - boost::uintptr_t const addr = boost::uintptr_t(container_detail::to_raw_pointer(m_holder.start()) + s + n); - //Align memory before casting to address - size_type *const paddr = reinterpret_cast((addr + szt_align_mask) & ~szt_align_mask); - this->priv_insert_ordered_range(UniqueBool(), n, first, last, paddr, comp); + boost::uintptr_t const addr = boost::uintptr_t(this->priv_raw_begin() + s + n); + boost::uintptr_t const capaddr = boost::uintptr_t(this->priv_raw_begin() + c); + boost::uintptr_t const aligned_addr = (addr + szt_align_mask) & ~szt_align_mask; + indexes = reinterpret_cast(aligned_addr); + std::size_t index_capacity = (aligned_addr >= capaddr) ? 0u : (capaddr - addr)/sizeof(size_type); + + //Capacity is constant, we're not going to change it + if(index_capacity < PosCount){ + indexes = positions; + index_capacity = PosCount; + } + if(index_capacity > remaining) + index_capacity = remaining; + BidirIt limit = first; + boost::container::iterator_advance(limit, index_capacity); + this->priv_insert_ordered_range(UniqueBool(), index_capacity, first, limit, indexes, comp); + first = limit; + remaining -= index_capacity; } } - else{ - this->insert(this->cend(), n, first, last); - } + } + else{ + this->insert(this->cend(), n, first, last); } } @@ -2245,7 +2282,7 @@ class vector //bool const linear = !s || !n || (s <= n) || ((s+n)/n/2 < logN); size_type const s = this->size(); size_type remaining = n; - T* const pbeg = container_detail::to_raw_pointer(m_holder.start()); + T* const pbeg = this->priv_raw_begin(); T* const pend = pbeg + s; T* pcur = pbeg; size_type *position = positions; @@ -2284,7 +2321,7 @@ class vector allocator_type &a = this->m_holder.alloc(); typename value_traits::ArrayDeallocator new_buffer_deallocator(new_storage, a, new_cap); typename value_traits::ArrayDestructor new_values_destroyer(new_storage, a, 0u); - T* pbeg = container_detail::to_raw_pointer(m_holder.start()); + T* pbeg = this->priv_raw_begin(); size_type const old_size = this->size(); T* const pend = pbeg + old_size; T* d_first = container_detail::to_raw_pointer(new_storage); @@ -2338,9 +2375,6 @@ class vector pointer back_ptr() const { return this->m_holder.start() + this->m_holder.m_size; } - T* back_raw() const - { return container_detail::to_raw_pointer(this->m_holder.start()) + this->m_holder.m_size; } - size_type priv_index_of(pointer p) const { BOOST_ASSERT(this->m_holder.start() <= p); @@ -2357,8 +2391,8 @@ class vector this->capacity() < x.size()){ throw_bad_alloc(); } - T* const this_start = container_detail::to_raw_pointer(m_holder.start()); - T* const other_start = container_detail::to_raw_pointer(x.m_holder.start()); + T* const this_start = this->priv_raw_begin(); + T* const other_start = x.priv_raw_begin(); const size_type this_sz = m_holder.m_size; const size_type other_sz = static_cast(x.m_holder.m_size); boost::container::move_assign_range_alloc_n(this->m_holder.alloc(), other_start, other_sz, this_start, this_sz); @@ -2373,7 +2407,7 @@ class vector , container_detail::is_different >::type * = 0) { - //for move constructor, no aliasing (&x != this) is assummed. + //for move assignment, no aliasing (&x != this) is assummed. BOOST_ASSERT(this != &x); allocator_type &this_alloc = this->m_holder.alloc(); allocator_type &x_alloc = x.m_holder.alloc(); @@ -2414,8 +2448,8 @@ class vector this->capacity() < x.size()){ throw_bad_alloc(); } - T* const this_start = container_detail::to_raw_pointer(m_holder.start()); - T* const other_start = container_detail::to_raw_pointer(x.m_holder.start()); + T* const this_start = this->priv_raw_begin(); + T* const other_start = x.priv_raw_begin(); const size_type this_sz = m_holder.m_size; const size_type other_sz = static_cast(x.m_holder.m_size); boost::container::copy_assign_range_alloc_n(this->m_holder.alloc(), other_start, other_sz, this_start, this_sz); @@ -2439,8 +2473,7 @@ class vector this->shrink_to_fit(); } container_detail::assign_alloc(this_alloc, x_alloc, flag); - this->assign( container_detail::to_raw_pointer(x.m_holder.start()) - , container_detail::to_raw_pointer(x.m_holder.start() + x.m_holder.m_size)); + this->assign( x.priv_raw_begin(), x.priv_raw_end() ); } template //Template it to avoid it in explicit instantiations @@ -2452,7 +2485,7 @@ class vector { const bool propagate_alloc = allocator_traits_type::propagate_on_container_swap::value; if(are_swap_propagable( this->get_stored_allocator(), this->m_holder.start() - , x.get_stored_allocator(), this->m_holder.start(), propagate_alloc)){ + , x.get_stored_allocator(), x.m_holder.start(), propagate_alloc)){ //Just swap internals this->m_holder.swap_resources(x.m_holder); } @@ -2471,6 +2504,8 @@ class vector , boost::make_move_iterator(container_detail::iterator_to_raw_pointer(big.nth(common_elements))) , boost::make_move_iterator(container_detail::iterator_to_raw_pointer(big.end())) ); + //Destroy remaining elements + big.erase(big.nth(common_elements), big.cend()); } //And now swap the allocator container_detail::swap_alloc(this->m_holder.alloc(), x.m_holder.alloc(), container_detail::bool_()); @@ -2492,7 +2527,7 @@ class vector pointer const p = allocator_traits_type::allocate(this->m_holder.alloc(), new_cap, this->m_holder.m_start); //We will reuse insert code, so create a dummy input iterator this->priv_forward_range_insert_new_allocation - ( container_detail::to_raw_pointer(p), new_cap, this->back_raw(), 0, this->priv_dummy_empty_proxy()); + ( container_detail::to_raw_pointer(p), new_cap, this->priv_raw_end(), 0, this->priv_dummy_empty_proxy()); } void priv_reserve_no_capacity(size_type new_cap, version_2) @@ -2514,7 +2549,7 @@ class vector } else{ //If there is no forward expansion, move objects, we will reuse insertion code T * const new_mem = container_detail::to_raw_pointer(ret); - T * const ins_pos = this->back_raw(); + T * const ins_pos = this->priv_raw_end(); if(reuse){ //Backwards (and possibly forward) expansion #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS ++this->num_expand_bwd; @@ -2536,7 +2571,7 @@ class vector { (void)moved; if(!(value_traits::trivial_dctr || (value_traits::trivial_dctr_after_move && moved))){ - value_type* const p = this->back_raw() - 1; + value_type* const p = this->priv_raw_end() - 1; allocator_traits_type::destroy(this->get_stored_allocator(), p); } --this->m_holder.m_size; @@ -2546,7 +2581,7 @@ class vector { BOOST_ASSERT(n <= this->m_holder.m_size); if(!value_traits::trivial_dctr){ - T* const destroy_pos = container_detail::to_raw_pointer(this->m_holder.start()) + (this->m_holder.m_size-n); + T* const destroy_pos = this->priv_raw_begin() + (this->m_holder.m_size-n); boost::container::destroy_alloc_n(this->get_stored_allocator(), destroy_pos, n); } this->m_holder.m_size -= n; @@ -2555,7 +2590,7 @@ class vector template void priv_uninitialized_construct_at_end(InpIt first, InpIt last) { - T* const old_end_pos = this->back_raw(); + T* const old_end_pos = this->priv_raw_end(); T* const new_end_pos = boost::container::uninitialized_copy_alloc(this->m_holder.alloc(), first, last, old_end_pos); this->m_holder.m_size += new_end_pos - old_end_pos; } @@ -2563,13 +2598,14 @@ class vector void priv_destroy_all() BOOST_NOEXCEPT_OR_NOTHROW { boost::container::destroy_alloc_n - (this->get_stored_allocator(), container_detail::to_raw_pointer(this->m_holder.start()), this->m_holder.m_size); + (this->get_stored_allocator(), this->priv_raw_begin(), this->m_holder.m_size); this->m_holder.m_size = 0; } template iterator priv_insert(const const_iterator &p, BOOST_FWD_REF(U) x) { + BOOST_ASSERT(this->priv_in_range_or_end(p)); return this->priv_forward_range_insert ( vector_iterator_get_ptr(p), 1, container_detail::get_insert_value_proxy(::boost::forward(x))); } @@ -2586,9 +2622,7 @@ class vector if (BOOST_LIKELY(this->room_enough())){ //There is more memory, just construct a new object at the end allocator_traits_type::construct - ( this->m_holder.alloc() - , container_detail::to_raw_pointer(this->m_holder.start() + this->m_holder.m_size) - , ::boost::forward(u) ); + ( this->m_holder.alloc(), this->priv_raw_end(), ::boost::forward(u) ); ++this->m_holder.m_size; } else{ @@ -2645,8 +2679,7 @@ class vector #endif this->priv_forward_range_insert_new_allocation ( container_detail::to_raw_pointer(p), sz - , container_detail::to_raw_pointer(this->m_holder.start()) - , 0, this->priv_dummy_empty_proxy()); + , this->priv_raw_begin(), 0, this->priv_dummy_empty_proxy()); } } } @@ -2693,7 +2726,8 @@ class vector const size_type new_cap = this->m_holder.next_capacity(n); //Pass the hint so that allocators can take advantage of this. - T * const new_buf = container_detail::to_raw_pointer(allocator_traits_type::allocate(this->m_holder.alloc(), new_cap, this->m_holder.m_start)); + T * const new_buf = container_detail::to_raw_pointer + (allocator_traits_type::allocate(this->m_holder.alloc(), new_cap, this->m_holder.m_start)); #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS ++this->num_alloc; #endif @@ -2708,7 +2742,7 @@ class vector { //Check if we have enough memory or try to expand current memory T *const raw_pos = container_detail::to_raw_pointer(pos); - const size_type n_pos = raw_pos - container_detail::to_raw_pointer(this->m_holder.start()); + const size_type n_pos = raw_pos - this->priv_raw_begin(); //There is not enough memory, allocate a new //buffer or expand the old one. @@ -2764,7 +2798,7 @@ class vector else{ //Expand forward T *const raw_pos = container_detail::to_raw_pointer(pos); - const size_type n_pos = raw_pos - container_detail::to_raw_pointer(this->m_holder.start()); + const size_type n_pos = raw_pos - this->priv_raw_begin(); this->priv_forward_range_insert_expand_forward(raw_pos, n, insert_range_proxy); return iterator(this->m_holder.start() + n_pos); } @@ -2849,7 +2883,7 @@ class vector BOOST_ASSERT(first_pos <= last_pos); BOOST_ASSERT(last_pos <= limit_pos); // - T* const begin_ptr = container_detail::to_raw_pointer(this->m_holder.start()); + T* const begin_ptr = this->priv_raw_begin(); T* const first_ptr = begin_ptr + first_pos; T* const last_ptr = begin_ptr + last_pos; @@ -2879,10 +2913,16 @@ class vector } private: + T *priv_raw_begin() const + { return container_detail::to_raw_pointer(m_holder.start()); } + + T* priv_raw_end() const + { return this->priv_raw_begin() + this->m_holder.m_size; } + template void priv_forward_range_insert_at_end_expand_forward(const size_type n, InsertionProxy insert_range_proxy) { - T* const old_finish = this->back_raw(); + T* const old_finish = this->priv_raw_end(); insert_range_proxy.uninitialized_copy_n_and_update(this->m_holder.alloc(), old_finish, n); this->m_holder.m_size += n; } @@ -2893,7 +2933,7 @@ class vector //n can't be 0, because there is nothing to do in that case if(BOOST_UNLIKELY(!n)) return; //There is enough memory - T* const old_finish = this->back_raw(); + T* const old_finish = this->priv_raw_end(); const size_type elems_after = old_finish - pos; if (!elems_after){ @@ -2944,10 +2984,10 @@ class vector //Initialize with [begin(), pos) old buffer //the start of the new buffer - T * const old_buffer = container_detail::to_raw_pointer(this->m_holder.start()); + T * const old_buffer = this->priv_raw_begin(); if(old_buffer){ new_finish = ::boost::container::uninitialized_move_alloc - (this->m_holder.alloc(), container_detail::to_raw_pointer(this->m_holder.start()), pos, old_finish = new_finish); + (this->m_holder.alloc(), this->priv_raw_begin(), pos, old_finish = new_finish); new_values_destroyer.increment_size(new_finish - old_finish); } //Initialize new objects, starting from previous point @@ -2981,7 +3021,7 @@ class vector { //n can be zero to just expand capacity //Backup old data - T* const old_start = container_detail::to_raw_pointer(this->m_holder.start()); + T* const old_start = this->priv_raw_begin(); const size_type old_size = this->m_holder.m_size; T* const old_finish = old_start + old_size; @@ -3291,7 +3331,7 @@ class vector } } - void priv_check_range(size_type n) const + void priv_throw_if_out_of_range(size_type n) const { //If n is out of range, throw an out_of_range exception if (n >= this->size()){ @@ -3299,6 +3339,16 @@ class vector } } + bool priv_in_range(const_iterator pos) const + { + return (this->begin() <= pos) && (pos < this->end()); + } + + bool priv_in_range_or_end(const_iterator pos) const + { + return (this->begin() <= pos) && (pos <= this->end()); + } + #ifdef BOOST_CONTAINER_VECTOR_ALLOC_STATS public: unsigned int num_expand_fwd; -- cgit v1.2.3