Subject: [Boost-commit] svn:boost r53918 - in sandbox/monotonic: boost/monotonic boost/utility libs/monotonic/test
From: christian.schladetsch_at_[hidden]
Date: 2009-06-15 02:07:42
Author: cschladetsch
Date: 2009-06-15 02:07:40 EDT (Mon, 15 Jun 2009)
New Revision: 53918
URL: http://svn.boost.org/trac/boost/changeset/53918
Log:
added bubble-sort test
Text files modified:
sandbox/monotonic/boost/monotonic/allocator.h | 4
sandbox/monotonic/boost/monotonic/inline_storage.h | 26 ++++++++
sandbox/monotonic/boost/monotonic/rope.h | 87 ++++++++++++++++++++++---------
sandbox/monotonic/boost/utility/iter_range.h | 22 ++++++++
sandbox/monotonic/libs/monotonic/test/main.cpp | 109 +++++++++++++++++++++++++++++++++++++++
sandbox/monotonic/libs/monotonic/test/monotonic.vcproj | 30 ++++++++++
sandbox/monotonic/libs/monotonic/test/rope.cpp | 60 ++++++++++++++++-----
7 files changed, 291 insertions(+), 47 deletions(-)
Modified: sandbox/monotonic/boost/monotonic/allocator.h
==============================================================================
--- sandbox/monotonic/boost/monotonic/allocator.h (original)
+++ sandbox/monotonic/boost/monotonic/allocator.h 2009-06-15 02:07:40 EDT (Mon, 15 Jun 2009)
@@ -78,8 +78,8 @@
template <class U>
allocator(const allocator<U> &Q) throw()
{
- typedef typename allocator<T>::template rebind<U> Other;
- typedef typename Other::other OtherStorage;
+ typedef BOOST_DEDUCED_TYPENAME allocator<T>::template rebind<U> Other;
+ typedef BOOST_DEDUCED_TYPENAME Other::other OtherStorage;
storage = OtherStorage(*Q.storage).storage;
}
Modified: sandbox/monotonic/boost/monotonic/inline_storage.h
==============================================================================
--- sandbox/monotonic/boost/monotonic/inline_storage.h (original)
+++ sandbox/monotonic/boost/monotonic/inline_storage.h 2009-06-15 02:07:40 EDT (Mon, 15 Jun 2009)
@@ -36,9 +36,15 @@
private:
buffer_type buffer; ///< the storage
size_t cursor; ///< pointer to current index within storage for next allocation
-
+#ifndef NDEBUG
+ size_t num_allocations;
+#endif
public:
- inline_storage() : cursor(0)
+ inline_storage()
+ : cursor(0)
+#ifndef NDEBUG
+ , num_allocations(0)
+#endif
{
}
@@ -57,6 +63,9 @@
void reset()
{
cursor = 0;
+#ifndef NDEBUG
+ num_allocations = 0;
+#endif
}
size_t get_cursor() const
@@ -72,6 +81,9 @@
/// allocate storage, given alignment requirement
void *allocate(size_t num_bytes, size_t alignment)
{
+#ifndef NDEBUG
+ ++num_allocations;
+#endif
// ensure we return a point on an aligned boundary
size_t extra = cursor & (alignment - 1);
if (extra > 0)
@@ -101,6 +113,16 @@
{
return N - cursor;
}
+ size_t used() const
+ {
+ return cursor;
+ }
+#ifndef NDEBUG
+ size_t get_num_allocs() const
+ {
+ return num_allocations;
+ }
+#endif
};
}
}
Modified: sandbox/monotonic/boost/monotonic/rope.h
==============================================================================
--- sandbox/monotonic/boost/monotonic/rope.h (original)
+++ sandbox/monotonic/boost/monotonic/rope.h 2009-06-15 02:07:40 EDT (Mon, 15 Jun 2009)
@@ -8,22 +8,31 @@
#include <boost/monotonic/allocator.h>
#include <boost/monotonic/storage_base.h>
#include <boost/utility/iter_range.h>
-#include <boost/unordered_map.hpp>
+#include <boost/iterator.hpp>
+#include <boost/iterator/iterator_categories.hpp>
namespace boost
{
namespace monotonic
{
- /// a set of sequences that are tied together to present a contiguous sequence
+ /// a list of vectors that are tied together to present a contiguous sequence
///
/// this is to provide a sequence type that is 'between' a list and a vector. it
/// has slower access speed than a vector, but faster access speed than a list.
///
- /// unlike a vector, a rope cannot be resize()d
- template <class T, size_t ChunkSize = 32>
- struct rope
+ /// unlike a vector, a chain cannot be resized
+ ///
+ /// this has limited utility outside of the context of a monotonic allocator.
+ /// the reason to use it there is to avoid resizing a vector using a monotonic
+ /// allocator, which is very wasteful. so, the trade-off is slightly slower
+ /// access but ability to extend without resizing. then again, given that the
+ /// main reason to use a monotonic allocator is speed, there may be limited
+ /// application even there.
+ ///
+ template <class T, size_t ChunkSize = 64>
+ struct chain
{
- typedef rope<T,ChunkSize> Rope;
+ typedef chain<T, ChunkSize> Rope;
typedef allocator<T> Allocator;
typedef vector<T> Vector;
typedef list<Vector> Strands;
@@ -32,8 +41,12 @@
typedef const_iter_range<Vector> ConstVectorIterators;
typedef iter_range<Vector> VectorIterators;
+ typedef T value_type;
+ typedef T &reference;
+ typedef const T &const_reference;
+
template <class R, class S, class V, class Derived>
- struct iterator_base //: TODO: add iterator category
+ struct iterator_base : boost::iterator<random_access_traversal_tag, T>
{
typedef R Rope;
typedef S StrandIterators;
@@ -43,7 +56,8 @@
VectorIterators vec;
iterator_base() { }
- iterator_base(Rope &P) : parent(&P) { }
+ iterator_base(Rope &P)
+ : parent(&P) { }
iterator_base(Rope &P, StrandIterators const &S)
: parent(&P), strand(S) { }
iterator_base(Rope &P, StrandIterators const &S, VectorIterators const &V)
@@ -64,6 +78,12 @@
}
return This();
}
+ Derived operator++(int)
+ {
+ Derived tmp = This();
+ ++*this;
+ return tmp;
+ }
bool operator==(iterator_base const &B) const
{
return parent == B.parent && strand == B.strand && vec == B.vec;
@@ -92,13 +112,14 @@
return *Parent::vec;
}
};
+ typedef iterator Iter;
struct const_iterator : iterator_base<Rope const, ConstStrandsIterators, ConstVectorIterators, const_iterator>
{
typedef iterator_base<Rope const, ConstStrandsIterators, ConstVectorIterators, const_iterator> Parent;
const_iterator() { }
const_iterator(Rope const &P)
: Parent(P) { }
- const_iterator(iterator const &X)
+ const_iterator(Iter const &X)
: Parent(*X.parent, X.strand, X.vec)
{ }
const_iterator(Rope const &P, ConstStrandsIterators const &S)
@@ -116,19 +137,31 @@
Allocator alloc;
public:
- rope() { }
- rope(Allocator const &A)
+ chain() { }
+ chain(Allocator const &A)
: alloc(A), strands(A) { }
- rope(size_t N, T const &X, Allocator const &A)
+ chain(size_t len, Allocator const &A)
+ : alloc(A), strands(A)
+ {
+ // TODO
+ }
+ chain(size_t len, T const &X, Allocator const &A)
: alloc(A), strands(A)
{
- //TODO
+ strands.push_back(Vector(alloc));
+ strands.back().resize(len, X);
}
template <class II>
- rope(II F, II L, Allocator const &A)
+ chain(II F, II L, Allocator const &A)
: alloc(A), strands(A)
{
- //TODO
+ strands.push_back(Vector(alloc));
+ Vector &vec = strands.back();
+ size_t len = std::distance(F,L);
+ vec.resize(len);
+ Vector::iterator G = vec.begin();
+ for (size_t N = 0; N < len; ++F, ++G)
+ *G = *F;
}
size_t size() const
@@ -180,45 +213,45 @@
strands.back().push_back(X);
}
- T &at(size_t N)
+ T &at(size_t index)
{
size_t offset = 0;
BOOST_FOREACH(Vector &vec, strands)
{
- size_t local = N - offset;
+ size_t local = index - offset;
if (local < vec.size())
{
return vec.at(local);
}
offset += vec.size();
- if (offset > N)
+ if (offset > index)
break;
}
- throw std::out_of_range("rope");
+ throw std::out_of_range("chain");
}
- T const &at(size_t N) const
+ T const &at(size_t index) const
{
size_t offset = 0;
BOOST_FOREACH(Vector const &vec, strands)
{
- size_t local = N - offset;
+ size_t local = index - offset;
if (local < vec.size())
{
return vec.at(local);
}
offset += vec.size();
- if (offset < N)
+ if (offset < index)
break;
}
- throw std::out_of_range("rope");
+ throw std::out_of_range("chain");
}
- T &operator[](size_t N)
+ T &operator[](size_t index)
{
- return at(N);
+ return at(index);
}
- T const &operator[](size_t N) const
+ T const &operator[](size_t index) const
{
- return at(N);
+ return at(index);
}
};
}
Modified: sandbox/monotonic/boost/utility/iter_range.h
==============================================================================
--- sandbox/monotonic/boost/utility/iter_range.h (original)
+++ sandbox/monotonic/boost/utility/iter_range.h 2009-06-15 02:07:40 EDT (Mon, 15 Jun 2009)
@@ -78,6 +78,17 @@
: Parent(A,A) { }
iter_range(iterator A, iterator B)
: Parent(A,B) { }
+ iter_range& operator++()
+ {
+ Parent::operator++();
+ return *this;
+ }
+ iter_range operator++(int)
+ {
+ iter_range tmp(*this);
+ Parent::operator++(0);
+ return tmp;
+ }
typename Value &operator*() const
{
return *first;
@@ -102,6 +113,17 @@
: Parent(A,A) { }
const_iter_range(const_iterator A, const_iterator B)
: Parent(A,B) { }
+ const_iter_range& operator++()
+ {
+ Parent::operator++();
+ return *this;
+ }
+ const_iter_range operator++(int)
+ {
+ const_iter_range tmp(*this);
+ Parent::operator++(0);
+ return tmp;
+ }
typename const Value &operator*() const
{
return *first;
Modified: sandbox/monotonic/libs/monotonic/test/main.cpp
==============================================================================
--- sandbox/monotonic/libs/monotonic/test/main.cpp (original)
+++ sandbox/monotonic/libs/monotonic/test/main.cpp 2009-06-15 02:07:40 EDT (Mon, 15 Jun 2009)
@@ -10,18 +10,72 @@
#include <boost/monotonic/map.h>
#include <boost/monotonic/set.h>
+#include <boost/iterator/counting_iterator.hpp>
+
+#include <boost/monotonic/rope.h>
+
#include <boost/timer.hpp>
#include <boost/foreach.hpp>
#include <iostream>
+#include <deque>
#include <boost/range.hpp>
#include <boost/iterator/counting_iterator.hpp>
#include <boost/array.hpp>
#include <boost/scoped_ptr.hpp>
+template <class T
+, size_t C = 64
+, class Al = std::allocator<T>
+, class Link = std::vector<T, Al>
+, class Links = std::deque<Link, Al>
+>
+struct chain;
+
+
using namespace std;
using namespace boost;
+void test_deque()
+{
+ monotonic::inline_storage<4000> storage; // create local storage on the stack
+ {
+ {
+ std::list<int, boost::monotonic::allocator<int> > list(storage);
+ fill_n(back_inserter(list), 100, 42);
+ cout << "list: " << storage.used() << endl;
+ }
+ storage.reset();
+ {
+ std::deque<int, boost::monotonic::allocator<int> > deque(storage);
+ fill_n(back_inserter(deque), 100, 42);
+ cout << "deque: " << storage.used() << endl;
+ }
+ storage.reset();
+
+ {
+ std::vector<int, boost::monotonic::allocator<int> > vector(storage);
+ fill_n(back_inserter(vector), 100, 42);
+ cout << "vector: " << storage.used() << endl;
+ }
+ storage.reset();
+
+ {
+ monotonic::chain<int> rope(storage);
+ fill_n(back_inserter(rope), 100, 42);
+ cout << "default chain: " << storage.used() << endl;
+ }
+ storage.reset();
+
+ {
+ monotonic::chain<int, 100> rope(storage);
+ fill_n(back_inserter(rope), 100, 42);
+ cout << "chain<100>: " << storage.used() << endl;
+ }
+ storage.reset();
+ }
+}
+
void test_basic()
{
monotonic::inline_storage<1000*sizeof(int)> storage1; // create local storage on the stack
@@ -430,16 +484,69 @@
}
void test_rope();
+void test_chain();
+
+template <class List>
+void test_bubble_sort_impl(size_t length, List &list)
+{
+ for (size_t n = 0; n < length; ++n)
+ list.push_back(length - n);
+ bool swapped = false;
+ do
+ {
+ swapped = false;
+ List::iterator A = list.begin(), B = --list.end();
+ for (--B; A != B; ++A)
+ {
+ List::iterator C = A;
+ ++C;
+ if (*A > *C)
+ {
+ std::swap(*A, *C);
+ swapped = true;
+ }
+ }
+ }
+ while (swapped);
+}
+
+void test_bubble_sort()
+{
+ monotonic::inline_storage<100000> storage;
+ const size_t count = 50000;
+ const size_t length = 20;
+
+ boost::timer mono_timer;
+ for (size_t n = 0; n < count; ++n)
+ {
+ test_bubble_sort_impl(length, std::list<int, monotonic::allocator<int> >(storage));
+ storage.reset();
+ }
+ double mono_total = mono_timer.elapsed();
+ cout << "mono bubble sort: " << 1000*1000*mono_total/count << "us" << endl;
+
+ boost::timer std_timer;
+ for (size_t n = 0; n < count; ++n)
+ {
+ test_bubble_sort_impl(length, std::list<int>());
+ }
+ double std_total = std_timer.elapsed();
+ cout << "std bubble sort: " << 1000*1000*std_total/count << "us" << endl;
+}
int main()
{
+ test_bubble_sort();
+ //test_map_list_realtime();
+ return 0;
+ //test_chain();
+ test_deque();
//test_rope();
test_shared_allocators();
test_alignment();
test_auto_buffer();
test_speed();
test_speed_heap();
- test_map_list_realtime();
test_basic();
test_copy();
test_ctors();
Modified: sandbox/monotonic/libs/monotonic/test/monotonic.vcproj
==============================================================================
--- sandbox/monotonic/libs/monotonic/test/monotonic.vcproj (original)
+++ sandbox/monotonic/libs/monotonic/test/monotonic.vcproj 2009-06-15 02:07:40 EDT (Mon, 15 Jun 2009)
@@ -218,14 +218,42 @@
Name="utility"
>
<File
+ RelativePath="..\..\..\boost\utility\chain.h"
+ >
+ </File>
+ <File
RelativePath="..\..\..\boost\utility\iter_range.h"
>
</File>
</Filter>
</Filter>
+ <Filter
+ Name="doc"
+ >
+ <File
+ RelativePath="..\doc\index.html"
+ >
+ </File>
+ </Filter>
<File
- RelativePath="..\doc\index.html"
+ RelativePath=".\chain.cpp"
>
+ <FileConfiguration
+ Name="Debug|Win32"
+ ExcludedFromBuild="true"
+ >
+ <Tool
+ Name="VCCLCompilerTool"
+ />
+ </FileConfiguration>
+ <FileConfiguration
+ Name="Release|Win32"
+ ExcludedFromBuild="true"
+ >
+ <Tool
+ Name="VCCLCompilerTool"
+ />
+ </FileConfiguration>
</File>
<File
RelativePath=".\main.cpp"
Modified: sandbox/monotonic/libs/monotonic/test/rope.cpp
==============================================================================
--- sandbox/monotonic/libs/monotonic/test/rope.cpp (original)
+++ sandbox/monotonic/libs/monotonic/test/rope.cpp 2009-06-15 02:07:40 EDT (Mon, 15 Jun 2009)
@@ -18,6 +18,7 @@
#include <boost/iterator/counting_iterator.hpp>
#include <boost/array.hpp>
#include <boost/scoped_ptr.hpp>
+#include <boost/noncopyable.hpp>
#include <boost/monotonic/rope.h>
@@ -28,13 +29,41 @@
{
std::vector<int> v(10);
boost::iter_range<std::vector<int> > r(v);
+ *r = 10;
+ *r++ = 10;
+ //while (r)
+ //{
+ // *r++ = 10;
+ //}
boost::const_iter_range<std::vector<int> > c(r);
}
+
+struct Foo : boost::noncopyable
+{
+ int n;
+ Foo(int N) : n(N) { }
+};
+
void test_rope()
{
+ {
+ monotonic::inline_storage<4000> storage; // create local storage on the stack
+ {
+ monotonic::chain<int, 100> rope(storage);
+ for (int n = 0; n < 200; ++n)
+ {
+ rope.push_back(n);
+ }
+ }
+ }
+
+
monotonic::inline_storage<1000> storage;
{
- typedef monotonic::rope<int, 2> Rope;
+ typedef monotonic::chain<Foo, 2> Rope2;
+ Rope2 foo(4, storage);
+
+ typedef monotonic::chain<int, 2> Rope;
Rope rope(storage);
rope.push_back(0);
rope.push_back(1);
@@ -46,25 +75,28 @@
{
*A *= 2;
}
+ Rope::iterator Q = rope.begin();
+ *Q++ = 13;
+
Rope::const_iterator C = rope.begin(), D = rope.end();
for (; C != D; ++C)
{
cout << *C;
}
- //BOOST_FOREACH(int n, rope)
- //{
- // cout << n << endl;
- //}
-
- //BOOST_FOREACH(int &n, rope)
- //{
- // n *= 2;
- //}
- //BOOST_FOREACH(int n, rope)
- //{
- // cout << n << endl;
- //}
+ BOOST_FOREACH(int n, rope)
+ {
+ cout << n << endl;
+ }
+
+ BOOST_FOREACH(int &n, rope)
+ {
+ n *= 2;
+ }
+ BOOST_FOREACH(int n, rope)
+ {
+ cout << n << endl;
+ }
rope[0] = 0;