boost/interprocess/mem_algo/detail/mem_algo_common.hpp
////////////////////////////////////////////////////////////////////////////// // // (C) Copyright Ion Gaztanaga 2005-2008. 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/interprocess for documentation. // ////////////////////////////////////////////////////////////////////////////// #ifndef BOOST_INTERPROCESS_DETAIL_MEM_ALGO_COMMON_HPP #define BOOST_INTERPROCESS_DETAIL_MEM_ALGO_COMMON_HPP #if (defined _MSC_VER) && (_MSC_VER >= 1200) # pragma once #endif #include <boost/interprocess/detail/config_begin.hpp> #include <boost/interprocess/detail/workaround.hpp> #include <boost/interprocess/interprocess_fwd.hpp> #include <boost/interprocess/containers/allocation_type.hpp> #include <boost/interprocess/detail/utilities.hpp> #include <boost/interprocess/detail/type_traits.hpp> #include <boost/interprocess/detail/math_functions.hpp> #include <boost/interprocess/detail/utilities.hpp> #include <boost/interprocess/detail/move.hpp> #include <boost/assert.hpp> #include <boost/static_assert.hpp> #include <algorithm> #include <utility> #include <iterator> //!\file //!Implements common operations for memory algorithms. namespace boost { namespace interprocess { namespace detail { template<class VoidPointer> class basic_multiallocation_slist { public: typedef VoidPointer void_pointer; private: static VoidPointer &priv_get_ref(const VoidPointer &p) { return *static_cast<void_pointer*>(detail::get_pointer(p)); } basic_multiallocation_slist(basic_multiallocation_slist &); basic_multiallocation_slist &operator=(basic_multiallocation_slist &); public: BOOST_INTERPROCESS_ENABLE_MOVE_EMULATION(basic_multiallocation_slist) //!This iterator is returned by "allocate_many" functions so that //!the user can access the multiple buffers allocated in a single call class iterator : public std::iterator<std::input_iterator_tag, char> { friend class basic_multiallocation_slist<void_pointer>; void unspecified_bool_type_func() const {} typedef void (iterator::*unspecified_bool_type)() const; iterator(void_pointer node_range) : next_node_(node_range) {} public: typedef char value_type; typedef value_type & reference; typedef value_type * pointer; iterator() : next_node_(0) {} iterator &operator=(const iterator &other) { next_node_ = other.next_node_; return *this; } public: iterator& operator++() { next_node_ = *static_cast<void_pointer*>(detail::get_pointer(next_node_)); return *this; } iterator operator++(int) { iterator result(*this); ++*this; return result; } bool operator== (const iterator& other) const { return next_node_ == other.next_node_; } bool operator!= (const iterator& other) const { return !operator== (other); } reference operator*() const { return *static_cast<char*>(detail::get_pointer(next_node_)); } operator unspecified_bool_type() const { return next_node_? &iterator::unspecified_bool_type_func : 0; } pointer operator->() const { return &(*(*this)); } private: void_pointer next_node_; }; private: iterator it_; public: basic_multiallocation_slist() : it_(iterator()) {} basic_multiallocation_slist(void_pointer p) : it_(p ? iterator_to(p) : iterator()) {} basic_multiallocation_slist(BOOST_INTERPROCESS_RV_REF(basic_multiallocation_slist) other) : it_(iterator()) { this->swap(other); } basic_multiallocation_slist& operator=(BOOST_INTERPROCESS_RV_REF(basic_multiallocation_slist) other) { basic_multiallocation_slist tmp(boost::interprocess::move(other)); this->swap(tmp); return *this; } bool empty() const { return !it_; } iterator before_begin() const { return iterator(void_pointer(const_cast<void*>(static_cast<const void*>(&it_.next_node_)))); } iterator begin() const { return it_; } iterator end() const { return iterator(); } void clear() { this->it_.next_node_ = void_pointer(0); } iterator insert_after(iterator it, void_pointer m) { priv_get_ref(m) = priv_get_ref(it.next_node_); priv_get_ref(it.next_node_) = m; return iterator(m); } void push_front(void_pointer m) { priv_get_ref(m) = this->it_.next_node_; this->it_.next_node_ = m; } void pop_front() { ++it_; } void *front() const { return detail::get_pointer(it_.next_node_); } void splice_after(iterator after_this, iterator before_begin, iterator before_end) { if (after_this != before_begin && after_this != before_end && before_begin != before_end) { void_pointer next_b = priv_get_ref(before_begin.next_node_); void_pointer next_e = priv_get_ref(before_end.next_node_); void_pointer next_p = priv_get_ref(after_this.next_node_); priv_get_ref(before_begin.next_node_) = next_e; priv_get_ref(before_end.next_node_) = next_p; priv_get_ref(after_this.next_node_) = next_b; } } void swap(basic_multiallocation_slist &other_chain) { std::swap(this->it_, other_chain.it_); } static iterator iterator_to(void_pointer p) { return iterator(p); } void_pointer extract_data() { void_pointer ret = empty() ? void_pointer(0) : void_pointer(&*it_); it_ = iterator(); return ret; } }; template<class VoidPointer> class basic_multiallocation_cached_slist { private: basic_multiallocation_slist<VoidPointer> slist_; typename basic_multiallocation_slist<VoidPointer>::iterator last_; basic_multiallocation_cached_slist(basic_multiallocation_cached_slist &); basic_multiallocation_cached_slist &operator=(basic_multiallocation_cached_slist &); public: BOOST_INTERPROCESS_ENABLE_MOVE_EMULATION(basic_multiallocation_cached_slist) typedef typename basic_multiallocation_slist<VoidPointer>::void_pointer void_pointer; typedef typename basic_multiallocation_slist<VoidPointer>::iterator iterator; basic_multiallocation_cached_slist() : slist_(), last_(slist_.before_begin()) {} /* basic_multiallocation_cached_slist(iterator first_node) : slist_(first_node), last_(slist_.before_begin()) { iterator end; while(first_node != end){ ++last_; } }*/ basic_multiallocation_cached_slist(void_pointer p1, void_pointer p2) : slist_(p1), last_(p2 ? iterator_to(p2) : slist_.before_begin()) {} basic_multiallocation_cached_slist(BOOST_INTERPROCESS_RV_REF(basic_multiallocation_cached_slist) other) : slist_(), last_(slist_.before_begin()) { this->swap(other); } basic_multiallocation_cached_slist& operator=(BOOST_INTERPROCESS_RV_REF(basic_multiallocation_cached_slist) other) { basic_multiallocation_cached_slist tmp(boost::interprocess::move(other)); this->swap(tmp); return *this; } bool empty() const { return slist_.empty(); } iterator before_begin() const { return slist_.before_begin(); } iterator begin() const { return slist_.begin(); } iterator end() const { return slist_.end(); } iterator last() const { return last_; } void clear() { slist_.clear(); last_ = slist_.before_begin(); } iterator insert_after(iterator it, void_pointer m) { slist_.insert_after(it, m); if(it == last_){ last_ = slist_.iterator_to(m); } return iterator_to(m); } void push_front(void_pointer m) { this->insert_after(this->before_begin(), m); } void push_back(void_pointer m) { this->insert_after(last_, m); } void pop_front() { if(last_ == slist_.begin()){ last_ = slist_.before_begin(); } slist_.pop_front(); } void *front() const { return slist_.front(); } void splice_after(iterator after_this, iterator before_begin, iterator before_end) { if(before_begin == before_end) return; if(after_this == last_){ last_ = before_end; } slist_.splice_after(after_this, before_begin, before_end); } void swap(basic_multiallocation_cached_slist &x) { slist_.swap(x.slist_); using std::swap; swap(last_, x.last_); if(last_ == x.before_begin()){ last_ = this->before_begin(); } if(x.last_ == this->before_begin()){ x.last_ = x.before_begin(); } } static iterator iterator_to(void_pointer p) { return basic_multiallocation_slist<VoidPointer>::iterator_to(p); } std::pair<void_pointer, void_pointer> extract_data() { if(this->empty()){ return std::pair<void_pointer, void_pointer>(void_pointer(0), void_pointer(0)); } else{ void_pointer p1 = slist_.extract_data(); void_pointer p2 = void_pointer(&*last_); last_ = iterator(); return std::pair<void_pointer, void_pointer>(p1, p2); } } }; template<class MultiallocatorCachedSlist> class basic_multiallocation_cached_counted_slist { private: MultiallocatorCachedSlist cached_slist_; std::size_t size_; basic_multiallocation_cached_counted_slist(basic_multiallocation_cached_counted_slist &); basic_multiallocation_cached_counted_slist &operator=(basic_multiallocation_cached_counted_slist &); public: BOOST_INTERPROCESS_ENABLE_MOVE_EMULATION(basic_multiallocation_cached_counted_slist) typedef typename MultiallocatorCachedSlist::void_pointer void_pointer; typedef typename MultiallocatorCachedSlist::iterator iterator; basic_multiallocation_cached_counted_slist() : cached_slist_(), size_(0) {} basic_multiallocation_cached_counted_slist(void_pointer p1, void_pointer p2, std::size_t n) : cached_slist_(p1, p2), size_(n) {} basic_multiallocation_cached_counted_slist(BOOST_INTERPROCESS_RV_REF(basic_multiallocation_cached_counted_slist) other) : cached_slist_(), size_(0) { this->swap(other); } basic_multiallocation_cached_counted_slist& operator=(BOOST_INTERPROCESS_RV_REF(basic_multiallocation_cached_counted_slist) other) { basic_multiallocation_cached_counted_slist tmp(boost::interprocess::move(other)); this->swap(tmp); return *this; } basic_multiallocation_cached_counted_slist (MultiallocatorCachedSlist mem, std::size_t n) : cached_slist_(boost::interprocess::move(mem)), size_(n) {} bool empty() const { return cached_slist_.empty(); } std::size_t size() const { return size_; } iterator before_begin() const { return cached_slist_.before_begin(); } iterator begin() const { return cached_slist_.begin(); } iterator end() const { return cached_slist_.end(); } iterator last() const { return cached_slist_.last(); } void clear() { cached_slist_.clear(); size_ = 0; } iterator insert_after(iterator it, void_pointer m) { iterator ret = cached_slist_.insert_after(it, m); ++size_; return ret; } void push_front(void_pointer m) { this->insert_after(this->before_begin(), m); } void push_back(void_pointer m) { this->insert_after(this->before_begin(), m); } void pop_front() { cached_slist_.pop_front(); --size_; } void *front() const { return cached_slist_.front(); } void splice_after(iterator after_this, basic_multiallocation_cached_counted_slist &x, iterator before_begin, iterator before_end) { std::size_t n = static_cast<std::size_t>(std::distance(before_begin, before_end)); this->splice_after(after_this, x, before_begin, before_end, n); } void splice_after(iterator after_this, basic_multiallocation_cached_counted_slist &x, iterator before_begin, iterator before_end, std::size_t n) { cached_slist_.splice_after(after_this, before_begin, before_end); size_ += n; x.size_ -= n; } void splice_after(iterator after_this, basic_multiallocation_cached_counted_slist &x) { cached_slist_.splice_after(after_this, x.before_begin(), x.last()); size_ += x.size_; x.size_ = 0; } void swap(basic_multiallocation_cached_counted_slist &x) { cached_slist_.swap(x.cached_slist_); using std::swap; swap(size_, x.size_); } static iterator iterator_to(void_pointer p) { return MultiallocatorCachedSlist::iterator_to(p); } std::pair<void_pointer, void_pointer> extract_data() { size_ = 0; return cached_slist_.extract_data(); } }; template<class T> struct cast_functor { typedef typename detail::add_reference<T>::type result_type; result_type operator()(char &ptr) const { return *static_cast<T*>(static_cast<void*>(&ptr)); } }; template<class MultiallocationChain, class T> class transform_multiallocation_chain { private: MultiallocationChain holder_; typedef typename MultiallocationChain::void_pointer void_pointer; typedef typename boost::pointer_to_other <void_pointer, T>::type pointer; transform_multiallocation_chain(transform_multiallocation_chain &); transform_multiallocation_chain &operator=(transform_multiallocation_chain &); static pointer cast(void_pointer p) { return pointer(static_cast<T*>(detail::get_pointer(p))); } public: BOOST_INTERPROCESS_ENABLE_MOVE_EMULATION(transform_multiallocation_chain) typedef transform_iterator < typename MultiallocationChain::iterator , detail::cast_functor <T> > iterator; transform_multiallocation_chain(void_pointer p1, void_pointer p2, std::size_t n) : holder_(p1, p2, n) {} transform_multiallocation_chain() : holder_() {} transform_multiallocation_chain(BOOST_INTERPROCESS_RV_REF(transform_multiallocation_chain) other) : holder_() { this->swap(other); } transform_multiallocation_chain(BOOST_INTERPROCESS_RV_REF(MultiallocationChain) other) : holder_(boost::interprocess::move(other)) {} transform_multiallocation_chain& operator=(BOOST_INTERPROCESS_RV_REF(transform_multiallocation_chain) other) { transform_multiallocation_chain tmp(boost::interprocess::move(other)); this->swap(tmp); return *this; } void push_front(pointer mem) { holder_.push_front(mem); } void swap(transform_multiallocation_chain &other_chain) { holder_.swap(other_chain.holder_); } /* void splice_after(iterator after_this, iterator before_begin, iterator before_end) { holder_.splice_after(after_this.base(), before_begin.base(), before_end.base()); } */ void splice_after(iterator after_this, transform_multiallocation_chain &x, iterator before_begin, iterator before_end, std::size_t n) { holder_.splice_after(after_this.base(), x.holder_, before_begin.base(), before_end.base(), n); } void pop_front() { holder_.pop_front(); } pointer front() const { return cast(holder_.front()); } bool empty() const { return holder_.empty(); } iterator before_begin() const { return iterator(holder_.before_begin()); } iterator begin() const { return iterator(holder_.begin()); } iterator end() const { return iterator(holder_.end()); } iterator last() const { return iterator(holder_.last()); } std::size_t size() const { return holder_.size(); } void clear() { holder_.clear(); } iterator insert_after(iterator it, pointer m) { return iterator(holder_.insert_after(it.base(), m)); } static iterator iterator_to(pointer p) { return iterator(MultiallocationChain::iterator_to(p)); } std::pair<void_pointer, void_pointer> extract_data() { return holder_.extract_data(); } MultiallocationChain extract_multiallocation_chain() { return MultiallocationChain(boost::interprocess::move(holder_)); } }; //!This class implements several allocation functions shared by different algorithms //!(aligned allocation, multiple allocation...). template<class MemoryAlgorithm> class memory_algorithm_common { public: typedef typename MemoryAlgorithm::void_pointer void_pointer; typedef typename MemoryAlgorithm::block_ctrl block_ctrl; typedef typename MemoryAlgorithm::multiallocation_chain multiallocation_chain; typedef memory_algorithm_common<MemoryAlgorithm> this_type; static const std::size_t Alignment = MemoryAlgorithm::Alignment; static const std::size_t MinBlockUnits = MemoryAlgorithm::MinBlockUnits; static const std::size_t AllocatedCtrlBytes = MemoryAlgorithm::AllocatedCtrlBytes; static const std::size_t AllocatedCtrlUnits = MemoryAlgorithm::AllocatedCtrlUnits; static const std::size_t BlockCtrlBytes = MemoryAlgorithm::BlockCtrlBytes; static const std::size_t BlockCtrlUnits = MemoryAlgorithm::BlockCtrlUnits; static const std::size_t UsableByPreviousChunk = MemoryAlgorithm::UsableByPreviousChunk; static void assert_alignment(const void *ptr) { assert_alignment((std::size_t)ptr); } static void assert_alignment(std::size_t uint_ptr) { (void)uint_ptr; BOOST_ASSERT(uint_ptr % Alignment == 0); } static bool check_alignment(const void *ptr) { return (((std::size_t)ptr) % Alignment == 0); } static std::size_t ceil_units(std::size_t size) { return detail::get_rounded_size(size, Alignment)/Alignment; } static std::size_t floor_units(std::size_t size) { return size/Alignment; } static std::size_t multiple_of_units(std::size_t size) { return detail::get_rounded_size(size, Alignment); } static multiallocation_chain allocate_many (MemoryAlgorithm *memory_algo, std::size_t elem_bytes, std::size_t n_elements) { return this_type::priv_allocate_many(memory_algo, &elem_bytes, n_elements, 0); } static void deallocate_many(MemoryAlgorithm *memory_algo, multiallocation_chain chain) { return this_type::priv_deallocate_many(memory_algo, boost::interprocess::move(chain)); } static bool calculate_lcm_and_needs_backwards_lcmed (std::size_t backwards_multiple, std::size_t received_size, std::size_t size_to_achieve, std::size_t &lcm_out, std::size_t &needs_backwards_lcmed_out) { // Now calculate lcm std::size_t max = backwards_multiple; std::size_t min = Alignment; std::size_t needs_backwards; std::size_t needs_backwards_lcmed; std::size_t lcm; std::size_t current_forward; //Swap if necessary if(max < min){ std::size_t tmp = min; min = max; max = tmp; } //Check if it's power of two if((backwards_multiple & (backwards_multiple-1)) == 0){ if(0 != (size_to_achieve & ((backwards_multiple-1)))){ return false; } lcm = max; //If we want to use minbytes data to get a buffer between maxbytes //and minbytes if maxbytes can't be achieved, calculate the //biggest of all possibilities current_forward = detail::get_truncated_size_po2(received_size, backwards_multiple); needs_backwards = size_to_achieve - current_forward; assert((needs_backwards % backwards_multiple) == 0); needs_backwards_lcmed = detail::get_rounded_size_po2(needs_backwards, lcm); lcm_out = lcm; needs_backwards_lcmed_out = needs_backwards_lcmed; return true; } //Check if it's multiple of alignment else if((backwards_multiple & (Alignment - 1u)) == 0){ lcm = backwards_multiple; current_forward = detail::get_truncated_size(received_size, backwards_multiple); //No need to round needs_backwards because backwards_multiple == lcm needs_backwards_lcmed = needs_backwards = size_to_achieve - current_forward; assert((needs_backwards_lcmed & (Alignment - 1u)) == 0); lcm_out = lcm; needs_backwards_lcmed_out = needs_backwards_lcmed; return true; } //Check if it's multiple of the half of the alignmment else if((backwards_multiple & ((Alignment/2u) - 1u)) == 0){ lcm = backwards_multiple*2u; current_forward = detail::get_truncated_size(received_size, backwards_multiple); needs_backwards_lcmed = needs_backwards = size_to_achieve - current_forward; if(0 != (needs_backwards_lcmed & (Alignment-1))) //while(0 != (needs_backwards_lcmed & (Alignment-1))) needs_backwards_lcmed += backwards_multiple; assert((needs_backwards_lcmed % lcm) == 0); lcm_out = lcm; needs_backwards_lcmed_out = needs_backwards_lcmed; return true; } //Check if it's multiple of the half of the alignmment else if((backwards_multiple & ((Alignment/4u) - 1u)) == 0){ std::size_t remainder; lcm = backwards_multiple*4u; current_forward = detail::get_truncated_size(received_size, backwards_multiple); needs_backwards_lcmed = needs_backwards = size_to_achieve - current_forward; //while(0 != (needs_backwards_lcmed & (Alignment-1))) //needs_backwards_lcmed += backwards_multiple; if(0 != (remainder = ((needs_backwards_lcmed & (Alignment-1))>>(Alignment/8u)))){ if(backwards_multiple & Alignment/2u){ needs_backwards_lcmed += (remainder)*backwards_multiple; } else{ needs_backwards_lcmed += (4-remainder)*backwards_multiple; } } assert((needs_backwards_lcmed % lcm) == 0); lcm_out = lcm; needs_backwards_lcmed_out = needs_backwards_lcmed; return true; } else{ lcm = detail::lcm(max, min); } //If we want to use minbytes data to get a buffer between maxbytes //and minbytes if maxbytes can't be achieved, calculate the //biggest of all possibilities current_forward = detail::get_truncated_size(received_size, backwards_multiple); needs_backwards = size_to_achieve - current_forward; assert((needs_backwards % backwards_multiple) == 0); needs_backwards_lcmed = detail::get_rounded_size(needs_backwards, lcm); lcm_out = lcm; needs_backwards_lcmed_out = needs_backwards_lcmed; return true; } static multiallocation_chain allocate_many ( MemoryAlgorithm *memory_algo , const std::size_t *elem_sizes , std::size_t n_elements , std::size_t sizeof_element) { return this_type::priv_allocate_many(memory_algo, elem_sizes, n_elements, sizeof_element); } static void* allocate_aligned (MemoryAlgorithm *memory_algo, std::size_t nbytes, std::size_t alignment) { //Ensure power of 2 if ((alignment & (alignment - std::size_t(1u))) != 0){ //Alignment is not power of two BOOST_ASSERT((alignment & (alignment - std::size_t(1u))) == 0); return 0; } std::size_t real_size; if(alignment <= Alignment){ return memory_algo->priv_allocate (boost::interprocess::allocate_new, nbytes, nbytes, real_size).first; } if(nbytes > UsableByPreviousChunk) nbytes -= UsableByPreviousChunk; //We can find a aligned portion if we allocate a block that has alignment //nbytes + alignment bytes or more. std::size_t minimum_allocation = max_value (nbytes + alignment, std::size_t(MinBlockUnits*Alignment)); //Since we will split that block, we must request a bit more memory //if the alignment is near the beginning of the buffer, because otherwise, //there is no space for a new block before the alignment. // // ____ Aligned here // | // ----------------------------------------------------- // | MBU | // ----------------------------------------------------- std::size_t request = minimum_allocation + (2*MinBlockUnits*Alignment - AllocatedCtrlBytes //prevsize - UsableByPreviousChunk ); //Now allocate the buffer void *buffer = memory_algo->priv_allocate (boost::interprocess::allocate_new, request, request, real_size).first; if(!buffer){ return 0; } else if ((((std::size_t)(buffer)) % alignment) == 0){ //If we are lucky and the buffer is aligned, just split it and //return the high part block_ctrl *first = memory_algo->priv_get_block(buffer); std::size_t old_size = first->m_size; const std::size_t first_min_units = max_value(ceil_units(nbytes) + AllocatedCtrlUnits, std::size_t(MinBlockUnits)); //We can create a new block in the end of the segment if(old_size >= (first_min_units + MinBlockUnits)){ block_ctrl *second = reinterpret_cast<block_ctrl *> (reinterpret_cast<char*>(first) + Alignment*first_min_units); first->m_size = first_min_units; second->m_size = old_size - first->m_size; BOOST_ASSERT(second->m_size >= MinBlockUnits); memory_algo->priv_mark_new_allocated_block(first); //memory_algo->priv_tail_size(first, first->m_size); memory_algo->priv_mark_new_allocated_block(second); memory_algo->priv_deallocate(memory_algo->priv_get_user_buffer(second)); } return buffer; } //Buffer not aligned, find the aligned part. // // ____ Aligned here // | // ----------------------------------------------------- // | MBU +more | ACB | // ----------------------------------------------------- char *pos = reinterpret_cast<char*> (reinterpret_cast<std::size_t>(static_cast<char*>(buffer) + //This is the minimum size of (2) (MinBlockUnits*Alignment - AllocatedCtrlBytes) + //This is the next MBU for the aligned memory AllocatedCtrlBytes + //This is the alignment trick alignment - 1) & -alignment); //Now obtain the address of the blocks block_ctrl *first = memory_algo->priv_get_block(buffer); block_ctrl *second = memory_algo->priv_get_block(pos); assert(pos <= (reinterpret_cast<char*>(first) + first->m_size*Alignment)); assert(first->m_size >= 2*MinBlockUnits); assert((pos + MinBlockUnits*Alignment - AllocatedCtrlBytes + nbytes*Alignment/Alignment) <= (reinterpret_cast<char*>(first) + first->m_size*Alignment)); //Set the new size of the first block std::size_t old_size = first->m_size; first->m_size = (reinterpret_cast<char*>(second) - reinterpret_cast<char*>(first))/Alignment; memory_algo->priv_mark_new_allocated_block(first); //Now check if we can create a new buffer in the end // // __"second" block // | __Aligned here // | | __"third" block // -----------|-----|-----|------------------------------ // | MBU +more | ACB | (3) | BCU | // ----------------------------------------------------- //This size will be the minimum size to be able to create a //new block in the end. const std::size_t second_min_units = max_value(std::size_t(MinBlockUnits), ceil_units(nbytes) + AllocatedCtrlUnits ); //Check if we can create a new block (of size MinBlockUnits) in the end of the segment if((old_size - first->m_size) >= (second_min_units + MinBlockUnits)){ //Now obtain the address of the end block block_ctrl *third = new (reinterpret_cast<char*>(second) + Alignment*second_min_units)block_ctrl; second->m_size = second_min_units; third->m_size = old_size - first->m_size - second->m_size; BOOST_ASSERT(third->m_size >= MinBlockUnits); memory_algo->priv_mark_new_allocated_block(second); memory_algo->priv_mark_new_allocated_block(third); memory_algo->priv_deallocate(memory_algo->priv_get_user_buffer(third)); } else{ second->m_size = old_size - first->m_size; assert(second->m_size >= MinBlockUnits); memory_algo->priv_mark_new_allocated_block(second); } memory_algo->priv_deallocate(memory_algo->priv_get_user_buffer(first)); return memory_algo->priv_get_user_buffer(second); } static bool try_shrink (MemoryAlgorithm *memory_algo, void *ptr ,const std::size_t max_size, const std::size_t preferred_size ,std::size_t &received_size) { (void)memory_algo; //Obtain the real block block_ctrl *block = memory_algo->priv_get_block(ptr); std::size_t old_block_units = block->m_size; //The block must be marked as allocated BOOST_ASSERT(memory_algo->priv_is_allocated_block(block)); //Check if alignment and block size are right assert_alignment(ptr); //Put this to a safe value received_size = (old_block_units - AllocatedCtrlUnits)*Alignment + UsableByPreviousChunk; //Now translate it to Alignment units const std::size_t max_user_units = floor_units(max_size - UsableByPreviousChunk); const std::size_t preferred_user_units = ceil_units(preferred_size - UsableByPreviousChunk); //Check if rounded max and preferred are possible correct if(max_user_units < preferred_user_units) return false; //Check if the block is smaller than the requested minimum std::size_t old_user_units = old_block_units - AllocatedCtrlUnits; if(old_user_units < preferred_user_units) return false; //If the block is smaller than the requested minimum if(old_user_units == preferred_user_units) return true; std::size_t shrunk_user_units = ((BlockCtrlUnits - AllocatedCtrlUnits) > preferred_user_units) ? (BlockCtrlUnits - AllocatedCtrlUnits) : preferred_user_units; //Some parameter checks if(max_user_units < shrunk_user_units) return false; //We must be able to create at least a new empty block if((old_user_units - shrunk_user_units) < BlockCtrlUnits ){ return false; } //Update new size received_size = shrunk_user_units*Alignment + UsableByPreviousChunk; return true; } static bool shrink (MemoryAlgorithm *memory_algo, void *ptr ,const std::size_t max_size, const std::size_t preferred_size ,std::size_t &received_size) { //Obtain the real block block_ctrl *block = memory_algo->priv_get_block(ptr); std::size_t old_block_units = block->m_size; if(!try_shrink (memory_algo, ptr, max_size, preferred_size, received_size)){ return false; } //Check if the old size was just the shrunk size (no splitting) if((old_block_units - AllocatedCtrlUnits) == ceil_units(preferred_size - UsableByPreviousChunk)) return true; //Now we can just rewrite the size of the old buffer block->m_size = (received_size-UsableByPreviousChunk)/Alignment + AllocatedCtrlUnits; BOOST_ASSERT(block->m_size >= BlockCtrlUnits); //We create the new block block_ctrl *new_block = reinterpret_cast<block_ctrl*> (reinterpret_cast<char*>(block) + block->m_size*Alignment); //Write control data to simulate this new block was previously allocated //and deallocate it new_block->m_size = old_block_units - block->m_size; BOOST_ASSERT(new_block->m_size >= BlockCtrlUnits); memory_algo->priv_mark_new_allocated_block(block); memory_algo->priv_mark_new_allocated_block(new_block); memory_algo->priv_deallocate(memory_algo->priv_get_user_buffer(new_block)); return true; } private: static multiallocation_chain priv_allocate_many ( MemoryAlgorithm *memory_algo , const std::size_t *elem_sizes , std::size_t n_elements , std::size_t sizeof_element) { //Note: sizeof_element == 0 indicates that we want to //allocate n_elements of the same size "*elem_sizes" //Calculate the total size of all requests std::size_t total_request_units = 0; std::size_t elem_units = 0; const std::size_t ptr_size_units = memory_algo->priv_get_total_units(sizeof(void_pointer)); if(!sizeof_element){ elem_units = memory_algo->priv_get_total_units(*elem_sizes); elem_units = ptr_size_units > elem_units ? ptr_size_units : elem_units; total_request_units = n_elements*elem_units; } else{ for(std::size_t i = 0; i < n_elements; ++i){ elem_units = memory_algo->priv_get_total_units(elem_sizes[i]*sizeof_element); elem_units = ptr_size_units > elem_units ? ptr_size_units : elem_units; total_request_units += elem_units; } } multiallocation_chain chain; std::size_t low_idx = 0; while(low_idx < n_elements){ std::size_t total_bytes = total_request_units*Alignment - AllocatedCtrlBytes + UsableByPreviousChunk; std::size_t min_allocation = (!sizeof_element) ? elem_units : memory_algo->priv_get_total_units(elem_sizes[low_idx]*sizeof_element); min_allocation = min_allocation*Alignment - AllocatedCtrlBytes + UsableByPreviousChunk; std::size_t received_size; std::pair<void *, bool> ret = memory_algo->priv_allocate (boost::interprocess::allocate_new, min_allocation, total_bytes, received_size, 0); if(!ret.first){ break; } block_ctrl *block = memory_algo->priv_get_block(ret.first); std::size_t received_units = block->m_size; char *block_address = reinterpret_cast<char*>(block); std::size_t total_used_units = 0; // block_ctrl *prev_block = 0; while(total_used_units < received_units){ if(sizeof_element){ elem_units = memory_algo->priv_get_total_units(elem_sizes[low_idx]*sizeof_element); elem_units = ptr_size_units > elem_units ? ptr_size_units : elem_units; } if(total_used_units + elem_units > received_units) break; total_request_units -= elem_units; //This is the position where the new block must be created block_ctrl *new_block = reinterpret_cast<block_ctrl *>(block_address); assert_alignment(new_block); //The last block should take all the remaining space if((low_idx + 1) == n_elements || (total_used_units + elem_units + ((!sizeof_element) ? elem_units : memory_algo->priv_get_total_units(elem_sizes[low_idx+1]*sizeof_element)) ) > received_units){ //By default, the new block will use the rest of the buffer new_block->m_size = received_units - total_used_units; memory_algo->priv_mark_new_allocated_block(new_block); //If the remaining units are bigger than needed and we can //split it obtaining a new free memory block do it. if((received_units - total_used_units) >= (elem_units + MemoryAlgorithm::BlockCtrlUnits)){ std::size_t shrunk_received; std::size_t shrunk_request = elem_units*Alignment - AllocatedCtrlBytes + UsableByPreviousChunk; bool shrink_ok = shrink (memory_algo ,memory_algo->priv_get_user_buffer(new_block) ,shrunk_request ,shrunk_request ,shrunk_received); (void)shrink_ok; //Shrink must always succeed with passed parameters BOOST_ASSERT(shrink_ok); //Some sanity checks BOOST_ASSERT(shrunk_request == shrunk_received); BOOST_ASSERT(elem_units == ((shrunk_request-UsableByPreviousChunk)/Alignment + AllocatedCtrlUnits)); //"new_block->m_size" must have been reduced to elem_units by "shrink" BOOST_ASSERT(new_block->m_size == elem_units); //Now update the total received units with the reduction received_units = elem_units + total_used_units; } } else{ new_block->m_size = elem_units; memory_algo->priv_mark_new_allocated_block(new_block); } block_address += new_block->m_size*Alignment; total_used_units += new_block->m_size; //Check we have enough room to overwrite the intrusive pointer assert((new_block->m_size*Alignment - AllocatedCtrlUnits) >= sizeof(void_pointer)); void_pointer p = new(memory_algo->priv_get_user_buffer(new_block))void_pointer(0); chain.push_back(p); ++low_idx; //prev_block = new_block; } //Sanity check BOOST_ASSERT(total_used_units == received_units); } if(low_idx != n_elements){ priv_deallocate_many(memory_algo, boost::interprocess::move(chain)); } return boost::interprocess::move(chain); } static void priv_deallocate_many(MemoryAlgorithm *memory_algo, multiallocation_chain chain) { while(!chain.empty()){ void *addr = detail::get_pointer(chain.front()); chain.pop_front(); memory_algo->priv_deallocate(addr); } } }; } //namespace detail { } //namespace interprocess { } //namespace boost { #include <boost/interprocess/detail/config_end.hpp> #endif //#ifndef BOOST_INTERPROCESS_DETAIL_MEM_ALGO_COMMON_HPP