Subject: [Boost-commit] svn:boost r53810 - in sandbox/monotonic: . boost boost/monotonic libs libs/monotonic libs/monotonic/doc libs/monotonic/example libs/monotonic/src libs/monotonic/test
From: christian.schladetsch_at_[hidden]
Date: 2009-06-12 04:01:25
Author: cschladetsch
Date: 2009-06-12 04:01:23 EDT (Fri, 12 Jun 2009)
New Revision: 53810
URL: http://svn.boost.org/trac/boost/changeset/53810
Log:
initial commit of monotonic allocator proposal.
Added:
sandbox/monotonic/
sandbox/monotonic/boost/
sandbox/monotonic/boost/monotonic/
sandbox/monotonic/boost/monotonic/allocator.h (contents, props changed)
sandbox/monotonic/boost/monotonic/inline_clone_allocator.h (contents, props changed)
sandbox/monotonic/boost/monotonic/inline_storage.h (contents, props changed)
sandbox/monotonic/boost/monotonic/list.h (contents, props changed)
sandbox/monotonic/boost/monotonic/map.h (contents, props changed)
sandbox/monotonic/boost/monotonic/ptr_list.h (contents, props changed)
sandbox/monotonic/boost/monotonic/set.h (contents, props changed)
sandbox/monotonic/boost/monotonic/storage.h (contents, props changed)
sandbox/monotonic/boost/monotonic/storage_base.h (contents, props changed)
sandbox/monotonic/boost/monotonic/vector.h (contents, props changed)
sandbox/monotonic/libs/
sandbox/monotonic/libs/monotonic/
sandbox/monotonic/libs/monotonic/doc/
sandbox/monotonic/libs/monotonic/doc/index.html (contents, props changed)
sandbox/monotonic/libs/monotonic/example/
sandbox/monotonic/libs/monotonic/src/
sandbox/monotonic/libs/monotonic/test/
sandbox/monotonic/libs/monotonic/test/main.cpp (contents, props changed)
sandbox/monotonic/libs/monotonic/test/monotonic.sln (contents, props changed)
sandbox/monotonic/libs/monotonic/test/monotonic.vcproj (contents, props changed)
Added: sandbox/monotonic/boost/monotonic/allocator.h
==============================================================================
--- (empty file)
+++ sandbox/monotonic/boost/monotonic/allocator.h 2009-06-12 04:01:23 EDT (Fri, 12 Jun 2009)
@@ -0,0 +1,140 @@
+// Copyright (C) 2009 Christian Schladetsch
+//
+// 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)
+
+#pragma once
+
+#include <boost/monotonic/storage.h>
+#include <boost/monotonic/storage_base.h>
+#include <boost/monotonic/inline_storage.h>
+
+namespace boost
+{
+ namespace monotonic
+ {
+ /// forward declaration
+ template <class T>
+ class allocator;
+
+ /// specialization for void
+ template <>
+ class allocator<void>
+ {
+ public:
+ typedef void* pointer;
+ typedef const void* const_pointer;
+
+ typedef void value_type;
+ template <class U>
+ struct rebind
+ {
+ typedef allocator<U> other;
+ };
+ };
+
+ /// a monotonic allocator always increases in size
+ template <class T>
+ class allocator
+ {
+ public:
+ typedef size_t size_type;
+ typedef ptrdiff_t difference_type;
+ typedef T *pointer;
+ typedef const T *const_pointer;
+ typedef T &reference;
+ typedef const T &const_reference;
+ typedef T value_type;
+
+ /// rebind storage to a another type
+ template <class U>
+ struct rebind
+ {
+ typedef allocator<U> other;
+ };
+
+ /// the storage used by the allocator
+ storage_interface *storage;
+
+ public:
+ allocator() throw()
+ : storage(0)
+ {
+ }
+
+ allocator(storage_interface &P) throw()
+ : storage(&P)
+ {
+ }
+
+ allocator(const allocator& Q) throw()
+ : storage(Q.storage)
+ {
+ }
+
+ template <class U>
+ allocator(const allocator<U> &Q) throw()
+ {
+ typedef typename allocator<T>::template rebind<U> Other;
+ typedef typename Other::other OtherStorage;
+ storage = OtherStorage(*Q.storage).storage;
+ }
+
+ ~allocator() throw()
+ {
+ }
+
+ pointer address(reference x) const
+ {
+ return &x;
+ }
+
+ const_pointer address(const_reference x) const
+ {
+ return &x;
+ }
+
+ pointer allocate(size_type num, allocator<void>::const_pointer hint = 0)
+ {
+ assert(num > 0);
+ return static_cast<T *>(storage->allocate(num*sizeof(T), hint));
+ }
+
+ void deallocate(pointer p, size_type n)
+ {
+ // do nothing
+ }
+
+ size_type max_size() const throw()
+ {
+ return storage->max_size();
+ }
+
+ void construct(pointer p)
+ {
+ new (p) T();
+ }
+ void construct(pointer p, const T& val)
+ {
+ new (p) T(val);
+ }
+
+ void destroy(pointer p)
+ {
+ if (!p)
+ return;
+ p->T::~T();
+ }
+
+ void swap(allocator<T> &other)
+ {
+ std::swap(storage, other.storage);
+ }
+
+ friend bool operator==(allocator<T> const &A, allocator<T> const &B) { return A.storage == B.storage; }
+ friend bool operator!=(allocator<T> const &A, allocator<T> const &B) { return A.storage != B.storage; }
+ };
+ }
+}
+
+//EOF
Added: sandbox/monotonic/boost/monotonic/inline_clone_allocator.h
==============================================================================
--- (empty file)
+++ sandbox/monotonic/boost/monotonic/inline_clone_allocator.h 2009-06-12 04:01:23 EDT (Fri, 12 Jun 2009)
@@ -0,0 +1,35 @@
+// Copyright (C) 2009 Christian Schladetsch
+//
+// 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)
+
+#pragma once
+
+namespace boost
+{
+ namespace monotonic
+ {
+ /// custom clone allocator for ptr-containers using a monotonic allocator.
+ /// see http://www.boost.org/doc/libs/1_38_0/libs/ptr_container/doc/reference.html for details.
+ struct inline_clone_allocator
+ {
+ template< class U >
+ static U* allocate_clone( const U& r )
+ {
+ // can't allocate clone without access to the monotonic allocator.
+ // this is a design fault in boost::ptr_container.
+ return 0;
+ }
+
+ template< class U >
+ static void deallocate_clone( const U* clone )
+ {
+ if (clone)
+ clone->U::~U();
+ }
+ };
+
+ }
+}
+
+//EOF
Added: sandbox/monotonic/boost/monotonic/inline_storage.h
==============================================================================
--- (empty file)
+++ sandbox/monotonic/boost/monotonic/inline_storage.h 2009-06-12 04:01:23 EDT (Fri, 12 Jun 2009)
@@ -0,0 +1,77 @@
+// Copyright (C) 2009 Christian Schladetsch
+//
+// 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)
+
+#pragma once
+
+#include <cassert>
+#include <boost/array.hpp>
+
+namespace boost
+{
+ namespace monotonic
+ {
+ /// storage for an allocator that is on the stack or heap
+ template <size_t N>
+ struct inline_storage : storage_base
+ {
+ // how to determine alignment requirements?
+ BOOST_STATIC_CONSTANT(size_t, Alignment = 16);
+
+ private:
+ boost::array<char, N> buffer; ///< the storage
+ size_t cursor; ///< pointer to current index within storage for next allocation
+
+ public:
+ inline_storage() : cursor(0)
+ {
+ }
+
+ void reset()
+ {
+ cursor = 0;
+ }
+
+ size_t get_cursor() const
+ {
+ return cursor;
+ }
+
+ void set_cursor(size_t c)
+ {
+ cursor = c;
+ }
+
+ /// allocate storage. ignore hint.
+ void *allocate(size_t num_bytes, void const * = 0)
+ {
+ // ensure we return a point on an aligned boundary
+ //size_t extra = num_bytes % Alignment;
+ size_t extra = 0;//num_bytes & 15;
+ size_t required = num_bytes + extra;
+ char *ptr = &buffer[cursor];
+ cursor += required;
+ return ptr + extra;
+ }
+
+ /// no work is done to deallocate storage
+ void deallocate(void * /*p*/, size_t /*n*/)
+ {
+ }
+
+ /// the maximum size is determined at compile-time
+ size_t max_size() const
+ {
+ return N;
+ }
+
+ size_t remaining() const
+ {
+ return N - cursor;
+ }
+ };
+ }
+}
+
+//EOF
Added: sandbox/monotonic/boost/monotonic/list.h
==============================================================================
--- (empty file)
+++ sandbox/monotonic/boost/monotonic/list.h 2009-06-12 04:01:23 EDT (Fri, 12 Jun 2009)
@@ -0,0 +1,37 @@
+// Copyright (C) 2009 Christian Schladetsch
+//
+// 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)
+
+#pragma once
+
+#include <list>
+#include <boost/monotonic/allocator.h>
+
+namespace boost
+{
+ namespace monotonic
+ {
+ /// A std::list<T> that uses a monotonic allocator
+ template <class T>
+ struct list : std::list<T, allocator<T> >
+ {
+ typedef allocator<T> Allocator;
+ typedef std::list<T, Allocator> List;
+
+ list() { }
+ list(storage_base &storage)
+ : List(Allocator(storage)) { }
+ list(Allocator const &A)
+ : List(A) { }
+ template <class II>
+ list(II F, II L, storage_base &S)
+ : List(F,L,Allocator(S)) { }
+ template <class II>
+ list(II F, II L, Allocator const &A)
+ : List(F,L,A) { }
+ };
+ }
+}
+
+//EOF
Added: sandbox/monotonic/boost/monotonic/map.h
==============================================================================
--- (empty file)
+++ sandbox/monotonic/boost/monotonic/map.h 2009-06-12 04:01:23 EDT (Fri, 12 Jun 2009)
@@ -0,0 +1,46 @@
+// Copyright (C) 2009 Christian Schladetsch
+//
+// 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)
+
+#pragma once
+
+#include <map>
+#include <boost/monotonic/allocator.h>
+
+namespace boost
+{
+ namespace monotonic
+ {
+ /// A std::map<K,T,P> that uses a monotonic allocator
+ template <class K, class T, class P = std::less<K> >
+ struct map : std::map<K,T,P, allocator<K> >
+ {
+ typedef allocator<K> Allocator;
+ typedef std::map<K,T,P,Allocator > Map;
+ typedef P Predicate;
+
+ map() { }
+ map(storage_base &S)
+ : Map(Predicate(), Allocator(S)) { }
+ map(Allocator const &A)
+ : Map(Predicate(), A) { }
+ map(Predicate Pr, Allocator const &A)
+ : Map(Pr, A) { }
+ template <class II>
+ map(II F, II L, storage_base &S)
+ : Map(F,L,Predicate(),Allocator(S)) { }
+ template <class II>
+ map(II F, II L, Allocator const &A)
+ : Map(F,L,A) { }
+ template <class II>
+ map(II F, II L, Predicate const &Pr, storage_base &S)
+ : Map(F,L,Pr,Allocator(S)) { }
+ template <class II>
+ map(II F, II L, Predicate const &Pr, Allocator const &A)
+ : Map(F,L,Pr,A) { }
+ };
+ }
+}
+
+//EOF
Added: sandbox/monotonic/boost/monotonic/ptr_list.h
==============================================================================
--- (empty file)
+++ sandbox/monotonic/boost/monotonic/ptr_list.h 2009-06-12 04:01:23 EDT (Fri, 12 Jun 2009)
@@ -0,0 +1,44 @@
+// Copyright (C) 2009 Christian Schladetsch
+//
+// 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)
+
+#pragma once
+
+#include <boost/ptr_container/ptr_list.hpp>
+#include <boost/monotonic/allocator.h>
+#include <boost/monotonic/inline_clone_allocator.h>
+
+namespace boost
+{
+ namespace monotonic
+ {
+ /// A boost::ptr_list<T> that uses a monotonic allocator, and a custom clone allocator
+ template <class T>
+ struct ptr_list : boost::ptr_list<T, inline_clone_allocator, allocator<T> >
+ {
+ typedef allocator<T> Allocator;
+ typedef boost::ptr_list<T, inline_clone_allocator, Allocator> List;
+
+ ptr_list()
+ {
+ }
+ ptr_list(storage_base &storage) // Copyright (C) 2009 Christian Schladetsch
+ //
+ // 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)
+
+
+ : List(Allocator(storage))
+ {
+ }
+ ptr_list(Allocator const &A)
+ : List(A)
+ {
+ }
+ };
+
+ }
+}
+
+//EOF
Added: sandbox/monotonic/boost/monotonic/set.h
==============================================================================
--- (empty file)
+++ sandbox/monotonic/boost/monotonic/set.h 2009-06-12 04:01:23 EDT (Fri, 12 Jun 2009)
@@ -0,0 +1,46 @@
+// Copyright (C) 2009 Christian Schladetsch
+//
+// 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)
+
+#pragma once
+
+#include <set>
+#include <boost/monotonic/allocator.h>
+
+namespace boost
+{
+ namespace monotonic
+ {
+ /// A std::set<T,P> that uses a monotonic allocator
+ template <class T, class P = std::less<T> >
+ struct set : std::set<T,P, allocator<T> >
+ {
+ typedef allocator<T> Allocator;
+ typedef P Predicate;
+ typedef std::set<T,P,allocator<T> > Set;
+
+ set() { }
+ set(storage_base &S)
+ : Set(Predicate(), Allocator(S)) { }
+ set(Allocator const &A)
+ : Set(Predicate(), A) { }
+ set(Predicate Pr, Allocator const &A)
+ : Set(Pr, A) { }
+ template <class II>
+ set(II F, II L, storage_base &S)
+ : Set(F,L,Predicate(),Allocator(S)) { }
+ template <class II>
+ set(II F, II L, Allocator const &A)
+ : Set(F,L,A) { }
+ template <class II>
+ set(II F, II L, Predicate const &Pr, storage_base &S)
+ : Set(F,L,Pr,Allocator(S)) { }
+ template <class II>
+ set(II F, II L, Predicate const &Pr, Allocator const &A)
+ : Set(F,L,Pr,A) { }
+ };
+ }
+}
+
+//EOF
Added: sandbox/monotonic/boost/monotonic/storage.h
==============================================================================
--- (empty file)
+++ sandbox/monotonic/boost/monotonic/storage.h 2009-06-12 04:01:23 EDT (Fri, 12 Jun 2009)
@@ -0,0 +1,23 @@
+// Copyright (C) 2009 Christian Schladetsch
+//
+// 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)
+
+#pragma once
+
+namespace boost
+{
+ namespace monotonic
+ {
+ /// interface common to all storage heaps
+ struct storage_interface
+ {
+ virtual void *allocate(size_t num_bytes, void const *hint = 0) = 0;
+ virtual void deallocate(void *base, size_t num_bytes) = 0;
+ virtual size_t max_size() const = 0;
+ virtual size_t remaining() const = 0;
+ };
+ }
+}
+
+//EOF
Added: sandbox/monotonic/boost/monotonic/storage_base.h
==============================================================================
--- (empty file)
+++ sandbox/monotonic/boost/monotonic/storage_base.h 2009-06-12 04:01:23 EDT (Fri, 12 Jun 2009)
@@ -0,0 +1,38 @@
+// Copyright (C) 2009 Christian Schladetsch
+//
+// 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)
+
+#pragma once
+
+#include <boost/cstdint.hpp>
+#include <boost/monotonic/storage.h>
+
+namespace boost
+{
+ namespace monotonic
+ {
+ /// base structure for all allocators.
+ ///
+ /// implements storage_interface using malloc and free
+ struct storage_base : storage_interface
+ {
+ void *allocate(size_t num_bytes, void const * = 0)
+ {
+ return malloc(num_bytes);
+ }
+
+ void deallocate(void *p, size_t /*n*/)
+ {
+ free(p);
+ }
+
+ size_t max_size() const
+ {
+ return INT_MAX;
+ }
+ };
+ }
+}
+
+//EOF
Added: sandbox/monotonic/boost/monotonic/vector.h
==============================================================================
--- (empty file)
+++ sandbox/monotonic/boost/monotonic/vector.h 2009-06-12 04:01:23 EDT (Fri, 12 Jun 2009)
@@ -0,0 +1,48 @@
+// Copyright (C) 2009 Christian Schladetsch
+//
+// 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)
+
+#pragma once
+
+#include <vector>
+#include <boost/monotonic/allocator.h>
+#include <boost/monotonic/storage_base.h>
+
+namespace boost
+{
+ namespace monotonic
+ {
+ /// a std::vector<T> that uses a monotonic allocator
+ template <class T>
+ struct vector : std::vector<T, allocator<T> >
+ {
+ typedef allocator<T> Allocator;
+ typedef std::vector<T,Allocator> Vector;
+
+ vector() { }
+ vector(storage_base &storage)
+ : Vector(Allocator(storage)) { }
+ vector(Allocator const &A)
+ : Vector(A) { }
+ vector(size_t N, T const &X, storage_base &S)
+ : Vector(N,X,Allocator(S)) { }
+ vector(size_t N, T const &X, Allocator const &A)
+ : Vector(N,X,A) { }
+ template <class II>
+ vector(II F, II L, storage_base &S)
+ : Vector(F,L,Allocator(S)) { }
+ template <class II>
+ vector(II F, II L, Allocator const &A)
+ : Vector(F,L,A) { }
+
+ void set_storage(storage_base &store)
+ {
+ this->allocator()
+ this->get_allocator().storage = &store;//(store);
+ }
+ };
+ }
+}
+
+//EOF
Added: sandbox/monotonic/libs/monotonic/doc/index.html
Added: sandbox/monotonic/libs/monotonic/test/main.cpp
Added: sandbox/monotonic/libs/monotonic/test/monotonic.sln
Added: sandbox/monotonic/libs/monotonic/test/monotonic.vcproj
==============================================================================
--- (empty file)
+++ sandbox/monotonic/libs/monotonic/doc/index.html 2009-06-12 04:01:23 EDT (Fri, 12 Jun 2009)
@@ -0,0 +1,282 @@
+<HTML>
+<HEAD>
+<META NAME="GENERATOR" Content="Microsoft Visual Studio 10.0">
+<TITLE></TITLE>
+</HEAD>
+<BODY>
+
+
+
+ <div class="document">
+ <table class="docinfo" frame="void" rules="none">
+ <colgroup>
+ <col class="docinfo-name" />
+ <col class="docinfo-content" />
+ </colgroup>
+ <tbody valign="top">
+ <tr>
+ <th class="docinfo-name">
+ Authors:</th>
+ <td>
+ Christian Schladetsch (christian.schladetsch_at_[hidden])</td>
+ </tr>
+ <tr>
+ <th class="docinfo-name">
+ Version:</th>
+ <td>
+ Unversioned, still just in vault</td>
+ </tr>
+ <tr class="field">
+ <th class="docinfo-name">
+ License:</th>
+ <td class="field-body">
+ None.</td>
+ </tr>
+ </tbody>
+ </table>
+ <div id="boost-bloom-filter" class="section">
+ <h1>
+ Boost.Monotonic</h1>
+ <p>
+ Boost.Monotonic is an implementation of container allocators that use a given,
+ fixed-size storage buffer.
+ This buffer can be on the heap, or the stack.</p>
+ <h2 id="Motivation">
+ Motivation
+ </h2>
+ <p>
+ We would like to use STL containers which take their storage from the stack. In
+ this way, for example a std::map<K,T> can use storage from the stack rather than
+ fragmenting the heap. </p>
+ <p>
+ There are many uses for such a system, including per-frame containers and
+ efficient containers for use in recursion. </p>
+ <p>
+ It is the fastest allocation system theoretically possible, with the downside
+ that the resident set size can only grow in size. Hence the proposed name of a
+ "monotonic" allocator.
+ </p>
+ <h2 id="Proposal">
+ Proposal
+ </h2>
+ <p>
+ The source code resides at <a href="http://www.boostpro.com/vault/index.php?action=downloadfile&filename=MonotonicAllocator.zip&directory=&"
+ target="_blank">http://www.boostpro.com/vault/
+ <p>
+ This is a constant-time, stack-based STL-compliant allocator with the following
+ properties: </p>
+ <ul>
+ <li>Space for objects is pre-allocated. This can be on the heap <strong>or</strong>
+ on the stack. </li>
+ <li>Objects are initialised only as required. </li>
+ <li>De-allocating an object calls its destructor. </li>
+ <li>Object storage is not reclaimed until the underlying storage goes out of scope.
+ </li>
+ </ul>
+ <p>
+ The benefits of using a monotonic::allocator over other allocators are:
+ </p>
+ <ul>
+ <li>All storage is pre-allocated, similar to a pool </li>
+ <li>Storage can be on the stack: <ul>
+ <li>Heap is not even used, let alone fragmented </li>
+ <li>Cache coherency is high </li>
+ </ul>
+ </li>
+ <li>Allocation is lightening-fast as it only involves advancing a pointer </li>
+ <li>Deallocation is even faster as it does absolutely nothing </li>
+ <li>Different containers can share the same storage </li>
+ </ul>
+ <p>
+ There are also limitations: </p>
+ <ul>
+ <li>Containers must be constructed with either an allocator or storage. There are no
+ default allocators, and hence no default container constructors. </li>
+ <li>Storage grows monotonically: removing objects from a container does not
+ de-allocate memory </li>
+ <li>Stackspace is limited and putting large containers on the stack may exhaust
+ stack space
+ <ul>
+ <li>This can be addressed on a per-compiler basis </li>
+ <li>The system can be used with the storage on the heap </li>
+ </ul>
+ </li>
+ </ul>
+ <p>
+ TODO:
+ </p>
+ <ul>
+ <li>provide details on default stack-sizes on each target platform </li>
+ <li>provide details as details on how to increase this. </li>
+ <li>provide guidance on 'good' sizes for containers that are stored on the stack
+ </li>
+ </ul>
+ <h3 id="Containers">
+ Containers
+ </h3>
+ <p>
+ The following containers are part of this proposal: </p>
+ <ul>
+ <li>boost::monotonic::list<T> </li>
+ <li>boost::monotonic::vector<T> </li>
+ <li>boost::monotonic::map<K,T> </li>
+ <li>boost::monotonic::multi_map<K,T> </li>
+ <li>boost::monotonic::set<T> </li>
+ <li>boost::monotonic::multi_set<T> </li>
+ <li>boost::monotonic::ptr_list<T> </li>
+ <li>boost::monotonic::ptr_vector<T> </li>
+ <li>boost::monotonic::ptr_map<K,T> </li>
+ <li>boost::monotonic::ptr_set<T> </li>
+ </ul>
+ <p>
+ boost::unordered can have a similar treatment.</p>
+ <h2 id="Architecture">
+ Architecture
+ </h2>
+ <p>
+ The architecture is quite simple. There are three main components: the storage,
+ the allocator and the container. The storage is based on boost::array<char,N>
+ and is on the stack or the heap. The allocator is stored in the
+ container, which is initialised with either an allocator or storage, as shown
+ for example with monotonic::map:
+ </p>
+ <div class="code">
+ <pre>/// A std::map<K,T,P> that uses a monotonic allocator
+template <class K, class T, class P = std::less<K> >
+struct map : std::map<K,T,P, allocator<K> >
+{
+ typedef allocator<K> Allocator;
+ typedef std::map<K,T,P,Allocator > Map;
+ typedef P Predicate;
+ map() { }
+ map(storage_base &S) : Map(Predicate(), Allocator(S)) { }
+ map(Allocator const &A) : Map(Predicate(), A) { }
+ map(Predicate P, Allocator const &A) : Map(P, A) { } </pre>
+ <pre>}; </pre>
+ </div>
+ <h2 id="ExampleUsage">
+ Example Usage
+ </h2>
+ <p>
+ Quite often, we need to create a temporary collection of objects which will
+ exist only for the duration of a code block. A common pattern for this is to
+ collect a set of objects from a container to do some work on: </p>
+ <div class="code">
+ <pre><b><span class="code-type">void</span></b> <b><span class="code-func">MainLoop</span></b>()
+{
+ boost::monotonic::inline_storage<100*<span class="code-lang"><b>sizeof</b>(Object)> storage; <i><span
+ class="code-comment">// create local storage on the stack
+</span></i> boost::monotonic::vector<Object> deathrow(storage); <i><span
+ class="code-comment">// create a std::vector that uses this storage</span></i></span></pre>
+ <pre><span class="code-lang"><span
+ class="code-comment"> foreach (object in world)
+ {
+ <b><span class="code-lang">if</span></b> (IsDead(object))
+ deathrow.push_back(object); <i><span class="code-comment">// allocation is just advancing a pointer
+</span></i> }
+ foreach (object in deathrow)
+ {
+ world.Remove(object);
+ object.Delete();
+ }
+ <span class="code-comment"><i>// storage is removed from stack; the heap is not touched
+</i></span>}
+</pre>
+ </div>
+ <p>
+ The same system can be used to store very large containers on the heap but still
+ using a monotonic allocator:
+ </p>
+ <div class="code">
+ <pre><b><span class="code-type">void</span></b> <b><span class="code-func">InlineHeapStorage</span></b>()
+{
+ <i><span class="code-comment">// create inline storage on the heap
+</span></i> <b><span class="code-keyword">std</span></b>::auto_ptr<boost::monotonic::storage<1000*1000*1000> > storage = <b><span
+ class="code-lang">new </b>boost::monotonic::storage<1000*1000*1000>();
+
+ <i><span class="code-comment">// create a hash-table-based mapping of ints to ints using a monotonic allocator
+</span></i> boost::monotonic::unsorted_map<<b><span class="code-type">int</b>, <b><span
+ class="code-type">int</span></b>> table(*storage);
+
+ <i><span class="code-comment">// populate the container; no new heap allocations are performed
+</span></i> <b><span class="code-lang">for</span></b> (<b><span class="code-type">int</span></b> n = 0; n < 1000*1000; ++n)
+ {
+ <i><span class="code-comment">// storage created for the hash-table (including the lists) is pre-allocated
+</span></i> <i><span class="code-comment">// and each allocation requires only a pointer advance
+</span></i> table[rand()] = n;
+ }
+}
+</pre>
+ </div>
+ <p>
+ Also, the stack-based allocation model can be used for per-frame allocation for
+ temporary storage. By passing the storage down the call-stack (either explicitly
+ as a parameter, or by storing within a visible member field), per-frame
+ containers and other storage can be used without resorting to the heap. At the
+ end of the frame, the storage is automatically released.
+ </p>
+ <div class="code">
+ <pre><b><span class="code-type">void</span></b> <b><span class="code-func">DoSomething</span></b>(boost::monotonic::storage_base &storage)
+{
+ boost::monotonic::vector<Object> vector(storage);
+ <span class="code-comment"><i>// populate and use vector</i>
+ DoSomethingElse(storage);
+}
+
+<b><span class="code-type">void</span></b> <b><span class="code-func">DoSDoSomethingElse</span></b>(boost::monotonic::storage_base &storage)
+{
+ boost::monotonic::map<<span class="code-type"><b>int</b>, Object> map(storage);
+ <i><span class="code-comment">// populate and use map
+</span></i>}
+
+<b><span class="code-type">void</span></b> <b><span class="code-func">MainLoop</span></b>()
+{
+ <b><span class="code-lang">while</span></b> (!Finished())
+ {
+ boost::monotonic::inline_storage<10*1000> storage;
+ DoSomething(storage);
+ <span class="code-comment"><i>// storage is released, ready for next loop</i>
+ </span>}
+}
+</pre>
+ </div>
+ <p>
+ Recursion also benefits from using the stack to store containers. For example,
+ assuming a cyclic graph of objects, we can avoid infinite recursion by using a
+ stack-based set:
+ </p>
+ <div class="code">
+ <pre><b><span class="code-type">void</span></b> <b><span class="code-func">Object::Recurse</span></b>()
+{
+ boost::monotonic::inline_storage<5000> storage; <i><span class="code-comment">// create storage on the stack for a set
+</span></i> Recurse(boost::monotonic::set<<b><span class="code-type">int</b>>(storage)); <i><span
+ class="code-comment">// recurse, passing the set
+</span></i>}
+
+<b><span class="code-type">void</span></b> <b><span class="code-func">Object::Recurse</span></b>(boost::monotonic::set<<b><span
+ class="code-type">int</b>> &set)
+{
+ <b><span class="code-lang">if</span></b> (set.find(handle) != set.end()) <b><span
+ class="code-lang">return</span></b>; <i><span class="code-comment">// avoid infinite recursion
+</span></i> set.insert(handle); <i><span class="code-comment">// add handle to set for testing later
+</span></i> DoSomething(); <i><span class="code-comment">// do something to this object
+</span></i> foreach (child object in <b><span class="code-lang">this</span></b>) <i><span
+ class="code-comment">// visit all child objects
+</span></i> Recurse(set);
+}
+</pre>
+ </div>
+ <div id="reference" class="section">
+ <h2>
+ References</h2>
+ <ul class="simple">
+ <li><none></li>
+ </ul>
+ </div>
+ </div>
+ </div>
+
+
+
+</BODY>
+</HTML>
==============================================================================
--- (empty file)
+++ sandbox/monotonic/libs/monotonic/test/main.cpp 2009-06-12 04:01:23 EDT (Fri, 12 Jun 2009)
@@ -0,0 +1,237 @@
+// 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)
+
+#include <boost/monotonic/vector.h>
+#include <boost/monotonic/list.h>
+#include <boost/monotonic/map.h>
+#include <boost/monotonic/set.h>
+
+#include <boost/timer.hpp>
+#include <iostream>
+
+using namespace std;
+using namespace boost;
+
+void test_copy()
+{
+ monotonic::inline_storage<1000*sizeof(int)> storage;
+ monotonic::vector<int> v1(storage);
+
+ for (int n = 0; n < 100; ++n)
+ v1.push_back(n);
+
+ size_t rem1 = storage.remaining();
+ monotonic::vector<int> v2(v1);
+ size_t rem2 = storage.remaining();
+
+ assert(v2 == v1);
+ assert(rem1 - rem2 == 100*sizeof(int));
+}
+
+void test_ctors()
+{
+ monotonic::inline_storage<1000*sizeof(int)> storage;
+ string foo = "foo";
+ monotonic::vector<char> v1(foo.begin(), foo.end(), storage);
+ assert(v1.size() == 3);
+ assert(equal(v1.begin(), v1.end(), "foo"));
+
+ monotonic::vector<char> v2(6, 'x', storage);
+ assert(v2.size() == 6);
+ assert(equal(v2.begin(), v2.end(), "xxxxxx"));
+
+ monotonic::set<char> s2(foo.begin(), foo.end(), storage);
+ assert(s2.size() == 2);
+ assert(s2.find('f') != s2.end());
+ assert(s2.find('o') != s2.end());
+
+ vector<pair<int, string> > v;
+ v.push_back(make_pair(42,"foo"));
+ v.push_back(make_pair(123,"bar"));
+ monotonic::map<int, string> m1(v.begin(), v.end(), storage);
+ assert(m1.find(42) != m1.end());
+ assert(m1.find(123) != m1.end());
+
+ monotonic::list<int> l1(foo.begin(), foo.end(), storage);
+ assert(equal(l1.begin(), l1.end(), "foo"));
+}
+
+void test_speed()
+{
+ typedef monotonic::map<int, monotonic::list<int> > map_with_list;
+ monotonic::inline_storage<1000000> storage;
+ map_with_list m(storage);
+ size_t count = 10000;
+ boost::timer timer;
+ for (size_t i = 0; i < count; ++i)
+ {
+ int random = rand() % 100;
+ map_with_list::iterator iter = m.find(random);
+ if (iter == m.end())
+ m.insert(make_pair(random, monotonic::list<int>(storage)));
+ else
+ iter->second.push_back(i);
+ }
+ double elapsed = timer.elapsed();
+ cout << "monotonic: " << elapsed << endl;
+
+ // do the same thing, with std::containers
+ {
+ typedef std::map<int, std::list<int> > map_with_list;
+ map_with_list m;
+ boost::timer timer;
+ for (size_t i = 0; i < count; ++i)
+ {
+ int random = rand() % 100;
+ map_with_list::iterator iter = m.find(random);
+ if (iter == m.end())
+ m[random] = std::list<int>();
+ else
+ iter->second.push_back(i);
+ }
+ double elapsed = timer.elapsed();
+ cout << "std: " << elapsed << endl;
+ }
+}
+
+void test_speed_heap()
+{
+ size_t num_iterations = 100000;
+
+ typedef monotonic::map<int, monotonic::list<int> > map_with_list;
+ monotonic::inline_storage<10000000> *storage = new monotonic::inline_storage<10000000>;
+
+ // do the test with monotonic containers and heap-based storage
+ {
+ map_with_list m(*storage);
+ boost::timer timer;
+ for (size_t i = 0; i < num_iterations; ++i)
+ {
+ int random = rand() % 100;
+ map_with_list::iterator iter = m.find(random);
+ if (iter == m.end())
+ m.insert(make_pair(random, monotonic::list<int>(*storage)));
+ else
+ iter->second.push_back(i);
+ }
+ double elapsed = timer.elapsed();
+ cout << "monotonic: " << elapsed << endl;
+ }
+ delete storage;
+
+ // do the same thing, with std::containers
+ {
+ typedef std::map<int, std::list<int> > map_with_list;
+ map_with_list m;
+ boost::timer timer;
+ for (size_t i = 0; i < num_iterations; ++i)
+ {
+ int random = rand() % 100;
+ map_with_list::iterator iter = m.find(random);
+ if (iter == m.end())
+ m[random] = std::list<int>();
+ else
+ iter->second.push_back(i);
+ }
+ double elapsed = timer.elapsed();
+ cout << "std: " << elapsed << endl;
+ }
+}
+
+namespace
+{
+
+ template<typename C>
+ struct Foo
+ {
+ long ord;
+ C c;
+ };
+
+ const int LOOP_COUNT = 100000000;
+ const int ELEM_COUNT = 1000;
+
+ template<typename C>
+ void test_loop_monotonic()
+ {
+ boost::monotonic::inline_storage<100000> storage;
+ boost::monotonic::vector<Foo<C> > vec(storage);
+ Foo<C> orig = { 'A', 65 };
+ vec.assign(ELEM_COUNT, orig);
+ boost::timer timer;
+ for (int i = 0; i < LOOP_COUNT; ++i)
+ ++vec[1 + i % (ELEM_COUNT - 2)].ord;
+ double elapsed = timer.elapsed();
+ std::cout << "Incrementing ord = " << 1000000000*elapsed/LOOP_COUNT << " ps per iteration" << std::endl;
+ }
+
+ template <class C>
+ void test_loop_std()
+ {
+ Foo<C> orig = { 'A', 65 };
+ std::vector<Foo<C> > vec;
+ vec.assign(ELEM_COUNT, orig);
+ boost::timer timer;
+ for (int i = 0; i < LOOP_COUNT; ++i)
+ ++vec[1 + i % (ELEM_COUNT - 2)].ord;
+ double elapsed = timer.elapsed();
+ std::cout << "STD: Incrementing ord = " << 1000000000*elapsed/LOOP_COUNT << " ps per iteration" << std::endl;
+ }
+
+} // namespace
+
+void test_alignment()
+{
+ test_loop_monotonic<char>();
+ test_loop_monotonic<long>();
+
+ test_loop_std<char>();
+ test_loop_std<short>();
+}
+
+int main()
+{
+ test_alignment();
+
+ test_copy();
+ test_ctors();
+ test_speed();
+ test_speed_heap();
+
+ monotonic::inline_storage<1000*sizeof(int)> storage1; // create local storage on the stack
+ monotonic::vector<int> v1(storage1); // create a vector that uses this storage
+
+ for(int i = 0; i < 100; ++i)
+ v1.push_back(i);
+
+ size_t len = storage1.remaining();
+ monotonic::vector<int> copy(v1);
+ size_t len2 = storage1.remaining();
+
+ assert(copy == v1);
+ assert(len - len2 == 100*sizeof(int));
+
+
+ // create the storage that will be used for the various monotonic containers.
+ // while it is on the stack here, it could be on the heap as well.
+ monotonic::inline_storage<1000> storage;
+
+ // create a list that uses inline, monotonically-increasing storage
+ monotonic::list<int> list(storage);
+ list.push_back(100);
+ list.push_back(400);
+ list.erase(list.begin());
+
+ // a map from the same storage
+ monotonic::map<int, float> map(storage);
+ map[42] = 3.14f;
+ assert(map[42] == 3.14f);
+
+ // a set...
+ monotonic::set<float> set(storage);
+ set.insert(3.14f);
+ set.insert(-123.f);
+
+}
+
+//EOF
==============================================================================
--- (empty file)
+++ sandbox/monotonic/libs/monotonic/test/monotonic.sln 2009-06-12 04:01:23 EDT (Fri, 12 Jun 2009)
@@ -0,0 +1,20 @@
+
+Microsoft Visual Studio Solution File, Format Version 10.00
+# Visual Studio 2008
+Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "monotonic", "monotonic.vcproj", "{5688980A-015B-4C7D-8D8D-F5894205FACE}"
+EndProject
+Global
+ GlobalSection(SolutionConfigurationPlatforms) = preSolution
+ Debug|Win32 = Debug|Win32
+ Release|Win32 = Release|Win32
+ EndGlobalSection
+ GlobalSection(ProjectConfigurationPlatforms) = postSolution
+ {5688980A-015B-4C7D-8D8D-F5894205FACE}.Debug|Win32.ActiveCfg = Debug|Win32
+ {5688980A-015B-4C7D-8D8D-F5894205FACE}.Debug|Win32.Build.0 = Debug|Win32
+ {5688980A-015B-4C7D-8D8D-F5894205FACE}.Release|Win32.ActiveCfg = Release|Win32
+ {5688980A-015B-4C7D-8D8D-F5894205FACE}.Release|Win32.Build.0 = Release|Win32
+ EndGlobalSection
+ GlobalSection(SolutionProperties) = preSolution
+ HideSolutionNode = FALSE
+ EndGlobalSection
+EndGlobal
==============================================================================
--- (empty file)
+++ sandbox/monotonic/libs/monotonic/test/monotonic.vcproj 2009-06-12 04:01:23 EDT (Fri, 12 Jun 2009)
@@ -0,0 +1,225 @@
+<?xml version="1.0" encoding="Windows-1252"?>
+<VisualStudioProject
+ ProjectType="Visual C++"
+ Version="9.00"
+ Name="monotonic"
+ ProjectGUID="{5688980A-015B-4C7D-8D8D-F5894205FACE}"
+ RootNamespace="monotonic"
+ Keyword="Win32Proj"
+ TargetFrameworkVersion="196613"
+ >
+ <Platforms>
+ <Platform
+ Name="Win32"
+ />
+ </Platforms>
+ <ToolFiles>
+ </ToolFiles>
+ <Configurations>
+ <Configuration
+ Name="Debug|Win32"
+ OutputDirectory="$(SolutionDir)$(ConfigurationName)"
+ IntermediateDirectory="$(ConfigurationName)"
+ ConfigurationType="1"
+ CharacterSet="1"
+ >
+ <Tool
+ Name="VCPreBuildEventTool"
+ />
+ <Tool
+ Name="VCCustomBuildTool"
+ />
+ <Tool
+ Name="VCXMLDataGeneratorTool"
+ />
+ <Tool
+ Name="VCWebServiceProxyGeneratorTool"
+ />
+ <Tool
+ Name="VCMIDLTool"
+ />
+ <Tool
+ Name="VCCLCompilerTool"
+ Optimization="0"
+ AdditionalIncludeDirectories="$(ProjectDir)/../../.."
+ PreprocessorDefinitions="WIN32;_DEBUG;_CONSOLE"
+ MinimalRebuild="true"
+ BasicRuntimeChecks="3"
+ RuntimeLibrary="3"
+ UsePrecompiledHeader="0"
+ WarningLevel="3"
+ DebugInformationFormat="4"
+ />
+ <Tool
+ Name="VCManagedResourceCompilerTool"
+ />
+ <Tool
+ Name="VCResourceCompilerTool"
+ />
+ <Tool
+ Name="VCPreLinkEventTool"
+ />
+ <Tool
+ Name="VCLinkerTool"
+ LinkIncremental="2"
+ GenerateDebugInformation="true"
+ SubSystem="1"
+ TargetMachine="1"
+ />
+ <Tool
+ Name="VCALinkTool"
+ />
+ <Tool
+ Name="VCManifestTool"
+ />
+ <Tool
+ Name="VCXDCMakeTool"
+ />
+ <Tool
+ Name="VCBscMakeTool"
+ />
+ <Tool
+ Name="VCFxCopTool"
+ />
+ <Tool
+ Name="VCAppVerifierTool"
+ />
+ <Tool
+ Name="VCPostBuildEventTool"
+ />
+ </Configuration>
+ <Configuration
+ Name="Release|Win32"
+ OutputDirectory="$(SolutionDir)$(ConfigurationName)"
+ IntermediateDirectory="$(ConfigurationName)"
+ ConfigurationType="1"
+ CharacterSet="1"
+ WholeProgramOptimization="1"
+ >
+ <Tool
+ Name="VCPreBuildEventTool"
+ />
+ <Tool
+ Name="VCCustomBuildTool"
+ />
+ <Tool
+ Name="VCXMLDataGeneratorTool"
+ />
+ <Tool
+ Name="VCWebServiceProxyGeneratorTool"
+ />
+ <Tool
+ Name="VCMIDLTool"
+ />
+ <Tool
+ Name="VCCLCompilerTool"
+ Optimization="2"
+ EnableIntrinsicFunctions="true"
+ AdditionalIncludeDirectories="$(ProjectDir)/../../.."
+ PreprocessorDefinitions="WIN32;NDEBUG;_CONSOLE"
+ RuntimeLibrary="2"
+ EnableFunctionLevelLinking="true"
+ UsePrecompiledHeader="0"
+ WarningLevel="3"
+ DebugInformationFormat="3"
+ />
+ <Tool
+ Name="VCManagedResourceCompilerTool"
+ />
+ <Tool
+ Name="VCResourceCompilerTool"
+ />
+ <Tool
+ Name="VCPreLinkEventTool"
+ />
+ <Tool
+ Name="VCLinkerTool"
+ LinkIncremental="1"
+ GenerateDebugInformation="true"
+ SubSystem="1"
+ OptimizeReferences="2"
+ EnableCOMDATFolding="2"
+ TargetMachine="1"
+ />
+ <Tool
+ Name="VCALinkTool"
+ />
+ <Tool
+ Name="VCManifestTool"
+ />
+ <Tool
+ Name="VCXDCMakeTool"
+ />
+ <Tool
+ Name="VCBscMakeTool"
+ />
+ <Tool
+ Name="VCFxCopTool"
+ />
+ <Tool
+ Name="VCAppVerifierTool"
+ />
+ <Tool
+ Name="VCPostBuildEventTool"
+ />
+ </Configuration>
+ </Configurations>
+ <References>
+ </References>
+ <Files>
+ <Filter
+ Name="boost"
+ >
+ <Filter
+ Name="monotonic"
+ >
+ <File
+ RelativePath="..\..\..\boost\monotonic\allocator.h"
+ >
+ </File>
+ <File
+ RelativePath="..\..\..\boost\monotonic\inline_clone_allocator.h"
+ >
+ </File>
+ <File
+ RelativePath="..\..\..\boost\monotonic\inline_storage.h"
+ >
+ </File>
+ <File
+ RelativePath="..\..\..\boost\monotonic\list.h"
+ >
+ </File>
+ <File
+ RelativePath="..\..\..\boost\monotonic\map.h"
+ >
+ </File>
+ <File
+ RelativePath="..\..\..\boost\monotonic\ptr_list.h"
+ >
+ </File>
+ <File
+ RelativePath="..\..\..\boost\monotonic\set.h"
+ >
+ </File>
+ <File
+ RelativePath="..\..\..\boost\monotonic\storage.h"
+ >
+ </File>
+ <File
+ RelativePath="..\..\..\boost\monotonic\storage_base.h"
+ >
+ </File>
+ <File
+ RelativePath="..\..\..\boost\monotonic\vector.h"
+ >
+ </File>
+ </Filter>
+ </Filter>
+ <File
+ RelativePath=".\main.cpp"
+ >
+ </File>
+ </Files>
+ <Globals>
+ </Globals>
+</VisualStudioProject>