|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r83508 - in sandbox/pool2/boost/pool: . details
From: svart.riddare_at_[hidden]
Date: 2013-03-20 17:01:45
Author: edupuis
Date: 2013-03-20 17:01:44 EDT (Wed, 20 Mar 2013)
New Revision: 83508
URL: http://svn.boost.org/trac/boost/changeset/83508
Log:
Implemented hybrid array/vector to represent chunks in order to prevent useless memory allocation when using pools that perform almost no reallocations.
Added:
sandbox/pool2/boost/pool/details/chunks.hpp
- copied, changed from r83094, /sandbox/pool2/boost/pool/details/pool.hpp
sandbox/pool2/boost/pool/details/iterators.hpp (contents, props changed)
Text files modified:
sandbox/pool2/boost/pool/details/chunks.hpp | 381 +++++++++++++++++++++++++++------------
sandbox/pool2/boost/pool/details/pool.hpp | 53 -----
sandbox/pool2/boost/pool/pool.hpp | 27 +-
3 files changed, 277 insertions(+), 184 deletions(-)
Copied: sandbox/pool2/boost/pool/details/chunks.hpp (from r83094, /sandbox/pool2/boost/pool/details/pool.hpp)
==============================================================================
--- /sandbox/pool2/boost/pool/details/pool.hpp (original)
+++ sandbox/pool2/boost/pool/details/chunks.hpp 2013-03-20 17:01:44 EDT (Wed, 20 Mar 2013)
@@ -1,161 +1,133 @@
-#ifndef __BOOST_POOL_DETAILS
-#define __BOOST_POOL_DETAILS
+#ifndef __BOOST_POOL_DETAILS_CHUNKS
+#define __BOOST_POOL_DETAILS_CHUNKS
-/* -------------------------------------------------------------------------- */
-/* -- boost::pool::list_t -- */
-/* -------------------------------------------------------------------------- */
-
-template<typename T>
-class list_t
-{
- public :
- list_t() { _node.buffer = NULL; }
- list_t(T *buffer, list_t list = list_t()) { _node.buffer = buffer; if (_node.next) *_node.next = list; }
-
- public :
- inline void push(T *buffer)
- { *this = list_t(buffer, *this); }
- inline T *pop()
- { T *buffer = front(); *this = next(); return buffer; }
-
- inline T *front() const
- { return _node.buffer; }
- inline bool empty() const
- { return !_node.buffer; }
-
- inline list_t next() const
- { return _node.next ? *_node.next : *this; }
- inline void next(list_t list)
- { if (_node.next) *_node.next = list; }
-
- inline bool operator<(const list_t& list) const
- { return front() < list.front(); }
-
- public :
- bool contains(T *buffer) const
- {
- for (list_t list = *this; !list.empty(); list = list.next())
- if (list.front() == buffer)
- return true;
-
- return false;
- }
-
- void sort()
- {
- *this = sort(*this);
- }
-
- static list_t sort(list_t list)
- {
- if (list.empty() || list.next().empty())
- return list;
-
- list_t listA, listB;
- split(list, &listA, &listB);
-
- return merge(sort(listA), sort(listB));
- }
-
- static list_t merge(list_t listA, list_t listB)
- {
- if (listA.empty()) return listB;
- if (listB.empty()) return listA;
-
- if (listB < listA)
- std::swap(listA, listB);
-
- list_t list = listA; listA = listA.next();
- list_t last = list;
-
- while (!listA.empty())
- {
- if (listB < listA)
- std::swap(listA, listB);
-
- last.next(listA);
- last = last.next();
- listA = listA.next();
- }
-
- last.next(listB);
- return list;
- }
-
- static void split(list_t list, list_t *listA, list_t *listB)
- {
- list_t half = list;
- list_t full = list.next();
-
- while (!full.empty())
- {
- full = full.next();
- if (!full.empty())
- {
- half = half.next();
- full = full.next();
- }
- }
-
- *listA = list;
- *listB = half.next();
-
- half.next(list_t());
- }
-
- private :
- union
- {
- T *buffer; // Buffer pointer.
- list_t *next; // Linked list pointer.
-
- } _node; // Linked list node
-};
+#include "iterators.hpp"
/* -------------------------------------------------------------------------- */
-/* -- boost::pool::chunk_t -- */
+/* -- boost::pool::_chunk_t -- */
/* -------------------------------------------------------------------------- */
+/** ----------------------------------------------------------------------------
+ * A chunk describes a pointer to a memory space large enough to hold 'count'
+ * buffers of 'size' bytes.
+ *
+ * It provides helper functions to get a pointer to the nth buffer and to check
+ * whether an arbitrary pointer is a valid buffer pointer.
+ *
+ * \tparam T
+ * Buffer object type, provided for convenience, i.e. for casting
+ * pointers given or returned by this object.
+ * -------------------------------------------------------------------------- */
+
template<typename T>
-class chunk_t
+class _chunk_t
{
public :
- chunk_t() {}
- chunk_t(char *pointer, size_t size, size_t count) : _pointer(pointer), _size(size), _count(count) {}
-
+ /** ------------------------------------------------------------------------
+ * Default constructor. All members are left uninitialized.
+ * ---------------------------------------------------------------------- */
+ _chunk_t() {}
+
+ /** ------------------------------------------------------------------------
+ * Constructor.
+ * \param pointer
+ * Memory chunk pointer. It is expected that it's size is equal to
+ * \p size times \p count and that the alignment constraints of
+ * type T are satisfied.
+ * \param size
+ * Individual buffer size, in bytes. It is assumed that this value
+ * is a multiple of the alignment constraints of type T.
+ * \param count
+ * Number of buffers in memory chunk.
+ * ---------------------------------------------------------------------- */
+ _chunk_t(char *pointer, size_t size, size_t count) : _pointer(pointer), _size(size), _count(count) {}
+
+ /** ------------------------------------------------------------------------
+ * Returns the memory chunk pointer given to the constructor.
+ * ---------------------------------------------------------------------- */
inline char *pointer() const
{ return _pointer; }
+
+ /** ------------------------------------------------------------------------
+ * Returns the size of buffer in bytes, as given to the constructor.
+ * ---------------------------------------------------------------------- */
inline size_t size() const
{ return _size; }
+
+ /** ------------------------------------------------------------------------
+ * Returns the number of buffers in the chunk, as given to the constructor.
+ * ---------------------------------------------------------------------- */
inline size_t count() const
{ return _count; }
- inline bool operator<(const chunk_t& chunk) const
+ /** ------------------------------------------------------------------------
+ * Defines a linear order between chunks. Chunks are ordered according to
+ * their memory addresses.
+ * ---------------------------------------------------------------------- */
+ inline bool operator<(const _chunk_t& chunk) const
{ return _pointer < chunk._pointer; }
public :
+ /** ------------------------------------------------------------------------
+ * Returns a pointer to the nth buffer contained in this chunk.
+ * \param n
+ * Buffer index. This value shall be smaller than the number of
+ * buffers returned by count().
+ * ---------------------------------------------------------------------- */
+ inline T *operator[](size_t n) const
+ { assert(n < _count); return reinterpret_cast<T *>(_pointer + _size * n); }
+
+ /** ------------------------------------------------------------------------
+ * Returns a pointer to the first buffer contained in this chunk. This
+ * function, along with last() and next(), may be used to iterate over the
+ * buffers of the chunk.
+ * ---------------------------------------------------------------------- */
inline T *first() const
{ return reinterpret_cast<T *>(_pointer); }
+
+ /** ------------------------------------------------------------------------
+ * Returns a pointer to the first buffer past the end of the chunk. This
+ * function, along with first() and next(), may be used to iterator over the
+ * buffer of the chunk.
+ * ---------------------------------------------------------------------- */
inline T *last() const
{ return reinterpret_cast<T *>(_pointer + _size * _count); }
+
+ /** ------------------------------------------------------------------------
+ * Returns the next chunk buffer, given one. This function, along with
+ * first() and last(), can be used to iterate over all buffers of a chunk.
+ * \param buffer
+ * Valid chunk buffer, as asserted with contains(). This pointer
+ * could have been obtained with first() or a previous call to
+ * next().
+ * ---------------------------------------------------------------------- */
inline T *next(T *buffer) const
- { return reinterpret_cast<T *>(reinterpret_cast<char *>(buffer) + _size); }
+ { assert(contains(buffer)); return reinterpret_cast<T *>(reinterpret_cast<char *>(buffer) + _size); }
public :
+ /** ------------------------------------------------------------------------
+ * Returns true if the given buffer is part of the chunk.
+ * ---------------------------------------------------------------------- */
bool contains(const T *buffer) const
{
const char *pointer = reinterpret_cast<const char *>(buffer);
+ /* -- Check if buffer is contained in memory chunk -- */
+
if (pointer < _pointer)
return false;
- size_t index = (pointer - _pointer) / _size;
+ size_t index = _size ? (pointer - _pointer) / _size : 0;
if (index >= _count)
return false;
+ /* -- Check if pointer is correctly aligned on a buffer boundary -- */
+
if (_pointer + _size * index != pointer)
return false;
+ /* -- Everything's fine -- */
+
return true;
}
@@ -166,5 +138,174 @@
};
/* -------------------------------------------------------------------------- */
+/* -- boost::pool::chunks_t -- */
+/* -------------------------------------------------------------------------- */
+
+/** ----------------------------------------------------------------------------
+ * Chunks describes a list of _chunk_t chunks. It is a hybrid class between
+ * std::array and std::vector. The first N chunks are stored in a statically
+ * allocated array while the remainders are stored in a dynamically allocated
+ * one.
+ *
+ * Functions provided are a small subset of the standard std::vector<chunk_t>.
+ *
+ * \tparam T
+ * Chunk buffer object type. Chunks will be of type _chunk_t<T>.
+ * \tparam N
+ * Maximum number of chunks that can be handled before resorting to
+ * dynamic memory allocation. Defaults to one.
+ * \tparam Allocator
+ * Allocator for chunks, if required. Defaults to the standard
+ * allocator for type _chunk_t<T>.
+ * -------------------------------------------------------------------------- */
+
+template<typename T, size_t N = 1, class Allocator = std::allocator<_chunk_t<T>>>
+class _chunks_t
+{
+ public :
+ /** ------------------------------------------------------------------------
+ * Chunk type.
+ * ---------------------------------------------------------------------- */
+ typedef _chunk_t<T> chunk_t;
+
+ /** ------------------------------------------------------------------------
+ * Iterator over chunks.
+ * ---------------------------------------------------------------------- */
+ typedef obvious_iterator<_chunks_t, chunk_t> iterator;
+
+ /** ------------------------------------------------------------------------
+ * Constant iterator over chunks.
+ * ---------------------------------------------------------------------- */
+ typedef obvious_iterator<const _chunks_t, const chunk_t> const_iterator;
+
+ public :
+ /** ------------------------------------------------------------------------
+ * Constructor. Constructs an empty list of chunks.
+ * ---------------------------------------------------------------------- */
+ _chunks_t(Allocator allocator = Allocator()) : _allocator(allocator), _pchunks(NULL), _maxChunks(N), _numChunks(0), _sorted(true) {}
+
+ /** ------------------------------------------------------------------------
+ * Returns the number of chunks in list.
+ * ---------------------------------------------------------------------- */
+ inline size_t chunks() const
+ { return _numChunks; }
+
+ public :
+ /** ------------------------------------------------------------------------
+ * Returns the nth chunk.
+ * ---------------------------------------------------------------------- */
+ inline chunk_t& operator[](size_t chunk)
+ { assert(chunk < _numChunks); return (chunk < N) ? _achunks[chunk] : _pchunks[chunk - N]; }
+
+ /** ------------------------------------------------------------------------
+ * Returns the nth chunk.
+ * ---------------------------------------------------------------------- */
+ inline const chunk_t& operator[](size_t chunk) const
+ { assert(chunk < _numChunks); return (chunk < N) ? _achunks[chunk] : _pchunks[chunk - N]; }
+
+ /** ------------------------------------------------------------------------
+ * Returns an iterator to the chunk list start.
+ * ---------------------------------------------------------------------- */
+ inline iterator begin()
+ { return iterator(*this); }
+
+ /** ------------------------------------------------------------------------
+ * Returns a constant iterator to the chunk list start.
+ * ---------------------------------------------------------------------- */
+ inline const_iterator cbegin() const
+ { return const_iterator(*this); }
+
+ /** ------------------------------------------------------------------------
+ * Returns an iterator to the chunk list end.
+ * ---------------------------------------------------------------------- */
+ inline iterator end()
+ { return iterator(*this, _numChunks); }
+
+ /** ------------------------------------------------------------------------
+ * Returns a constant iterator to the chunk list end.
+ * ---------------------------------------------------------------------- */
+ inline const_iterator cend() const
+ { return const_iterator(*this, _numChunks); }
+
+ public :
+ /** ------------------------------------------------------------------------
+ * Adds a chunk to the chunk list.
+ *
+ * This function may allocate memory if the chunk list is full, in which
+ * case the list size will be doubled. It is expected that the pool growth
+ * policy is defined as to keep this list small.
+ *
+ * Returns false in case of memory allocation failure.
+ * ---------------------------------------------------------------------- */
+ bool push(const chunk_t& chunk)
+ {
+ /* -- Grow list of chunks if it is full, doubling it's capacity -- */
+
+ if (_numChunks >= _maxChunks)
+ {
+ size_t maxChunks = 2 * _numChunks;
+ chunk_t *pchunks = _allocator.allocate(maxChunks - N);
+ if (!pchunks)
+ return false;
+
+ std::copy(_pchunks, _pchunks + _numChunks - N, pchunks);
+ _allocator.deallocate(_pchunks, _maxChunks - N);
+
+ _pchunks = pchunks;
+ _maxChunks = maxChunks;
+ }
+
+ /* -- Insert new chunk -- */
+
+ (*this)[++_numChunks] = chunk;
+
+ /* -- Update sorted state -- */
+
+ if (_sorted && (_numChunks > 1))
+ if ((*this)[_numChunks - 1] < (*this)[_numChunks - 2])
+ _sorted = false;
+
+ /* -- Done -- */
+
+ return true;
+ }
+
+ /** ------------------------------------------------------------------------
+ * Sorts the chunk lists, by increasing order of memory addresses.
+ * ---------------------------------------------------------------------- */
+ void sort()
+ {
+ if (!_sorted)
+ std::sort(begin(), end());
+
+ _sorted = true;
+ }
+
+ /** ------------------------------------------------------------------------
+ * Returns true if the given buffer is a valid buffer from one of the
+ * chunks in chunk list, using _chunk_t::contains().
+ * ---------------------------------------------------------------------- */
+ bool contains(const T *buffer) const
+ {
+ for (size_t chunk = 0; chunk < _numChunks; chunk++)
+ if ((*this)[chunk].contains(buffer))
+ return true;
+
+ return false;
+ }
+
+ private :
+ Allocator _allocator; // Allocator.
+
+ chunk_t _achunks[N]; // Chunks, static array.
+ chunk_t *_pchunks; // Chunks, dynamic array.
+
+ size_t _maxChunks; // Maximum number of chunks that may be holded.
+ size_t _numChunks; // Number of chunks holded.
+
+ mutable bool _sorted; // True if chunk list is sorted.
+};
+
+/* -------------------------------------------------------------------------- */
#endif
\ No newline at end of file
Added: sandbox/pool2/boost/pool/details/iterators.hpp
==============================================================================
--- (empty file)
+++ sandbox/pool2/boost/pool/details/iterators.hpp 2013-03-20 17:01:44 EDT (Wed, 20 Mar 2013)
@@ -0,0 +1,55 @@
+#ifndef BOOST_POOL_DETAILS_ITERATORS
+#define BOOST_POOL_DETAILS_ITERATORS
+
+/* -------------------------------------------------------------------------- */
+/* -- boost::pool::obvious_iterator -- */
+/* -------------------------------------------------------------------------- */
+
+/** ----------------------------------------------------------------------------
+ * An "obvious iterator" is an iterator derived from an object which implements
+ * the [] operator to access it's elements.
+ *
+ * The implementation uses boost::iterator_facade for convenience.
+ *
+ * \tparam Collection
+ * Container class which implements the [] operators to access it's
+ * elements.
+ * \tparam Element
+ * Type of the element contained by the Collection class.
+ * -------------------------------------------------------------------------- */
+
+template<typename Collection, typename Element>
+class obvious_iterator : public boost::iterator_facade<obvious_iterator<Collection, Element>, Element, boost::random_access_traversal_tag>
+{
+ public :
+ obvious_iterator() {}
+ obvious_iterator(Collection& collection, size_t index = 0) : _collection(&collection), _index(index) {}
+
+ protected :
+ friend class boost::iterator_core_access;
+ typedef boost::iterator_facade<obvious_iterator<Collection, Element>, Element, boost::random_access_traversal_tag> Base;
+
+ inline void increment()
+ { advance(1); }
+ inline void decrement()
+ { advance(-1); }
+ inline void advance(typename Base::difference_type n)
+ { _index += n; }
+
+ inline typename Base::reference dereference() const
+ { return (*_collection)[_index]; }
+
+ inline bool equal(const obvious_iterator& i) const
+ { assert(_collection == i._collection); return _index == i._index; }
+
+ inline typename Base::difference_type distance_to(const obvious_iterator& i) const
+ { return i._index - _index; }
+
+ private :
+ Collection *_collection;
+ size_t _index;
+};
+
+/* -------------------------------------------------------------------------- */
+
+#endif
\ No newline at end of file
Modified: sandbox/pool2/boost/pool/details/pool.hpp
==============================================================================
--- sandbox/pool2/boost/pool/details/pool.hpp (original)
+++ sandbox/pool2/boost/pool/details/pool.hpp 2013-03-20 17:01:44 EDT (Wed, 20 Mar 2013)
@@ -113,58 +113,5 @@
};
/* -------------------------------------------------------------------------- */
-/* -- boost::pool::chunk_t -- */
-/* -------------------------------------------------------------------------- */
-
-template<typename T>
-class chunk_t
-{
- public :
- chunk_t() {}
- chunk_t(char *pointer, size_t size, size_t count) : _pointer(pointer), _size(size), _count(count) {}
-
- inline char *pointer() const
- { return _pointer; }
- inline size_t size() const
- { return _size; }
- inline size_t count() const
- { return _count; }
-
- inline bool operator<(const chunk_t& chunk) const
- { return _pointer < chunk._pointer; }
-
- public :
- inline T *first() const
- { return reinterpret_cast<T *>(_pointer); }
- inline T *last() const
- { return reinterpret_cast<T *>(_pointer + _size * _count); }
- inline T *next(T *buffer) const
- { return reinterpret_cast<T *>(reinterpret_cast<char *>(buffer) + _size); }
-
- public :
- bool contains(const T *buffer) const
- {
- const char *pointer = reinterpret_cast<const char *>(buffer);
-
- if (pointer < _pointer)
- return false;
-
- size_t index = (pointer - _pointer) / _size;
- if (index >= _count)
- return false;
-
- if (_pointer + _size * index != pointer)
- return false;
-
- return true;
- }
-
- private :
- char *_pointer; // Memory chunk pointer.
- size_t _size; // Size of a buffer, in bytes.
- size_t _count; // Number of buffers in chunk.
-};
-
-/* -------------------------------------------------------------------------- */
#endif
\ No newline at end of file
Modified: sandbox/pool2/boost/pool/pool.hpp
==============================================================================
--- sandbox/pool2/boost/pool/pool.hpp (original)
+++ sandbox/pool2/boost/pool/pool.hpp 2013-03-20 17:01:44 EDT (Wed, 20 Mar 2013)
@@ -3,15 +3,17 @@
#include <boost/config.hpp>
#include <boost/static_assert.hpp>
-#include <boost/bind.hpp>
+#include <boost/iterator/iterator_facade.hpp>
-#include <algorithm> // std::sort, std::find_if
+#ifdef BOOST_MSVC
+ #pragma warning(disable: 4996) // Function call with parameters that may be unsafe
+#endif
+
+#include <algorithm> // std::copy, std::sort
#include <cassert> // assert
#include <cstddef> // size_t
-#include <functional> // std::mem_fun
#include <limits> // std:numeric_limits
#include <memory> // std::allocator
-#include <vector> // std::vector
#include <boost/tr1/type_traits.hpp>
@@ -104,6 +106,7 @@
{
private :
#include "details/pool.hpp"
+ #include "details/chunks.hpp"
public :
/** ------------------------------------------------------------------------
@@ -251,7 +254,9 @@
Allocator _allocator; // Custom allocator. Set by the constructor.
pools::policy _policy; // Pool growth policy. Set by the constructor.
- typedef std::vector<chunk_t<T>> chunks_t;
+ typedef _chunks_t<T> chunks_t;
+ typedef _chunk_t<T> chunk_t;
+
chunks_t _chunks; // Allocated memory chunks.
list_t<T> _list; // List of free pool buffers.
@@ -280,7 +285,7 @@
/* -- Release all pool memory -- */
- for (chunks_t::iterator chunk = _chunks.begin(); chunk != _chunks.end(); chunk++)
+ for (chunks_t::const_iterator chunk = _chunks.cbegin(); chunk != _chunks.cend(); chunk++)
_allocator.deallocate(chunk->pointer(), chunk->size());
}
@@ -301,14 +306,14 @@
/* -- Sort allocated chunks and list of free buffers -- */
- std::sort(_chunks.begin(), _chunks.end());
+ _chunks.sort();
_list.sort();
/* -- Release missing elements -- */
list_t<T> list = _list;
- for (chunks_t::iterator chunk = _chunks.begin(); chunk != _chunks.end(); chunk++)
+ for (chunks_t::const_iterator chunk = _chunks.cbegin(); chunk != _chunks.cend(); chunk++)
for (T *buffer = chunk->first(); buffer != chunk->last(); buffer = chunk->next(buffer))
if (list.front() != buffer)
release(buffer);
@@ -343,13 +348,13 @@
/* -- Perform allocation -- */
- chunk_t<T> chunk(_allocator.allocate(size * count), size, count);
+ chunk_t chunk(_allocator.allocate(size * count), size, count);
if (!chunk.pointer())
return false;
/* -- Keep allocated pointer for purge function -- */
- _chunks.push_back(chunk);
+ _chunks.push(chunk);
_allocated += count;
/* -- Push newly allocated buffers in list of free buffers -- */
@@ -467,7 +472,7 @@
assert(_requested > 0);
assert(!_list.contains(buffer));
- assert(std::find_if(_chunks.begin(), _chunks.end(), boost::bind(&chunk_t<T>::contains, _1, buffer)) != _chunks.end()); // TODO : Remove boost::bind
+ assert(_chunks.contains(buffer));
/* -- Destroy buffer content -- */
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk