|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r54293 - in sandbox/monotonic: boost/monotonic boost/monotonic/container boost/monotonic/detail libs/monotonic/test/Tests
From: christian.schladetsch_at_[hidden]
Date: 2009-06-23 19:15:06
Author: cschladetsch
Date: 2009-06-23 19:15:06 EDT (Tue, 23 Jun 2009)
New Revision: 54293
URL: http://svn.boost.org/trac/boost/changeset/54293
Log:
added monotonic::list::sort with test
Text files modified:
sandbox/monotonic/boost/monotonic/container/list.hpp | 92 +++++++++++++++++++++++++++++++++++++++
sandbox/monotonic/boost/monotonic/detail/pool.hpp | 2
sandbox/monotonic/boost/monotonic/storage.hpp | 4
sandbox/monotonic/libs/monotonic/test/Tests/Tests.vcproj | 2
sandbox/monotonic/libs/monotonic/test/Tests/tests.cpp | 38 ++++++++++++++++
5 files changed, 133 insertions(+), 5 deletions(-)
Modified: sandbox/monotonic/boost/monotonic/container/list.hpp
==============================================================================
--- sandbox/monotonic/boost/monotonic/container/list.hpp (original)
+++ sandbox/monotonic/boost/monotonic/container/list.hpp 2009-06-23 19:15:06 EDT (Tue, 23 Jun 2009)
@@ -2,6 +2,27 @@
//
// 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)
+/*
+* This file is derived from software bearing the following
+* restrictions:
+*
+* Copyright (c) 1994
+* Hewlett-Packard Company
+*
+* Permission to use, copy, modify, distribute and sell this
+* software and its documentation for any purpose is hereby
+* granted without fee, provided that the above copyright notice
+* appear in all copies and that both that copyright notice and
+* this permission notice appear in supporting documentation.
+* Hewlett-Packard Company makes no representations about the
+* suitability of this software for any purpose. It is provided
+* "as is" without express or implied warranty.
+*/
+
+/*
+* Copyright (c) 1992-2007 by P.J. Plauger. ALL RIGHTS RESERVED.
+* Consult your license regarding permissions and restrictions.
+V5.03:0009 */
#ifndef BOOST_MONOTONIC_LIST_HPP
#define BOOST_MONOTONIC_LIST_HPP
@@ -28,7 +49,7 @@
typedef typename List::value_type value_type;
typedef typename List::reference reference;
typedef typename List::const_reference const_reference;
- typedef list<T> This;
+ typedef list<T,Region,Access> This;
private:
Implementation impl;
@@ -107,6 +128,75 @@
{
impl.erase(A);
}
+
+ template <class Pred2>
+ void sort(Pred2 pred)
+ {
+ if (size() < 2)
+ return;
+
+ const size_t MAXBINS = 25;
+ This temp(get_allocator());
+ typename Allocator::template rebind<This>::other alloc_this(get_allocator());
+ This *bin_list = alloc_this.allocate(MAXBINS + 1);
+ for (This *bin = bin_list; bin < bin_list + MAXBINS; ++bin)
+ {
+ alloc_this.construct(bin);
+ }
+ size_t max_bin = 0;
+
+ while (!empty())
+ {
+ // sort another element, using bins
+ temp.impl._Splice(temp.begin(), impl, begin(), ++begin(), 1, true); // don't invalidate iterators
+
+ size_t bin;
+ for (bin = 0; bin < max_bin && !bin_list[bin].empty(); ++bin)
+ { // merge into ever larger bins
+ bin_list[bin].merge(temp, pred);
+ bin_list[bin].swap(temp);
+ }
+
+ if (bin == MAXBINS)
+ {
+ bin_list[bin - 1].merge(temp, pred);
+ }
+ else
+ {
+ // spill to new bin, while they last
+ bin_list[bin].swap(temp);
+ if (bin == max_bin)
+ ++max_bin;
+ }
+ }
+
+ for (size_t bin = 1; bin < max_bin; ++bin)
+ {
+ bin_list[bin].merge(bin_list[bin - 1], pred); // merge up
+ }
+ splice(begin(), bin_list[max_bin - 1]); // result in last bin
+ }
+
+ void sort()
+ {
+ sort(std::less<T>());
+ }
+
+ template <class Pred3>
+ void merge(This& other, Pred3 pred)
+ {
+ impl.merge(other.impl, pred);
+ }
+
+ void splice(const_iterator where, This& other)
+ {
+ impl.splice(where, other.impl);
+ }
+
+ void swap(This &other)
+ {
+ impl.swap(other.impl);
+ }
};
template <class Ty,class R,class Acc,class Ty2,class R2,class Acc2>
Modified: sandbox/monotonic/boost/monotonic/detail/pool.hpp
==============================================================================
--- sandbox/monotonic/boost/monotonic/detail/pool.hpp (original)
+++ sandbox/monotonic/boost/monotonic/detail/pool.hpp 2009-06-23 19:15:06 EDT (Tue, 23 Jun 2009)
@@ -35,7 +35,7 @@
template <class Storage>
bool expand(Storage &storage)
{
- size_t capacity = std::max(DefaultSizes::MinPoolSize*bucket_size, (last - first)*bucket_size*2);
+ size_t capacity = (std::max)(DefaultSizes::MinPoolSize*bucket_size, (last - first)*bucket_size*2);
void *ptr = storage.from_fixed(capacity, 16);
if (ptr == 0)
{
Modified: sandbox/monotonic/boost/monotonic/storage.hpp
==============================================================================
--- sandbox/monotonic/boost/monotonic/storage.hpp (original)
+++ sandbox/monotonic/boost/monotonic/storage.hpp 2009-06-23 19:15:06 EDT (Tue, 23 Jun 2009)
@@ -126,7 +126,7 @@
return ptr;
}
}
- AddLink(std::max(MinHeapIncrement, num_bytes*2));
+ AddLink((std::max)(MinHeapIncrement, num_bytes*2));
void *ptr = chain.front().allocate(num_bytes, alignment);
if (ptr == 0)
throw std::bad_alloc();
@@ -135,7 +135,7 @@
size_t max_size() const
{
- return std::numeric_limits<size_t>::max();
+ return (std::numeric_limits<size_t>::max)();
}
size_t fixed_remaining() const
Modified: sandbox/monotonic/libs/monotonic/test/Tests/Tests.vcproj
==============================================================================
--- sandbox/monotonic/libs/monotonic/test/Tests/Tests.vcproj (original)
+++ sandbox/monotonic/libs/monotonic/test/Tests/Tests.vcproj 2009-06-23 19:15:06 EDT (Tue, 23 Jun 2009)
@@ -87,6 +87,8 @@
/>
<Tool
Name="VCPostBuildEventTool"
+ Description="Running tests"
+ CommandLine="$(OutDir)\$(ProjectName).exe"
/>
</Configuration>
<Configuration
Modified: sandbox/monotonic/libs/monotonic/test/Tests/tests.cpp
==============================================================================
--- sandbox/monotonic/libs/monotonic/test/Tests/tests.cpp (original)
+++ sandbox/monotonic/libs/monotonic/test/Tests/tests.cpp 2009-06-23 19:15:06 EDT (Tue, 23 Jun 2009)
@@ -57,8 +57,11 @@
monotonic::storage<> storage;
{
monotonic::map<int, monotonic::list<int> > local_map(storage);
+ BOOST_ASSERT(local_map.get_allocator().get_storage() == &storage);
+
local_map[1].push_back(42);
- BOOST_ASSERT(local_map.get_allocator().get_storage() == local_map[1].get_allocator().get_storage());
+
+ BOOST_ASSERT(local_map.get_allocator() == local_map[1].get_allocator());
}
}
@@ -87,6 +90,24 @@
monotonic::static_storage<region1>::reset();
}
+template <class II>
+bool is_sorted(II F, II L)
+{
+ II G = F;
+ for (++G; G != L; ++F, ++G)
+ {
+ if (*G < *F)
+ return false;
+ }
+ return true;
+}
+
+template <class Cont>
+bool is_sorted(Cont const &cont)
+{
+ return is_sorted(boost::begin(cont), boost::end(cont));
+}
+
BOOST_AUTO_TEST_CASE(test_list)
{
monotonic::list<int> cont;
@@ -105,6 +126,21 @@
monotonic::static_storage<>::reset();
monotonic::static_storage<region1>::reset();
+
+ monotonic::storage<> storage;
+ {
+ monotonic::list<monotonic::list<int> > list(storage);
+ BOOST_ASSERT(list.get_allocator().get_storage() == &storage);
+ list.push_back(monotonic::list<int>());
+ BOOST_ASSERT(list.get_allocator().get_storage() == list.front().get_allocator().get_storage());
+ generate_n(back_inserter(list.front()), 100, rand);
+ BOOST_ASSERT(!is_sorted(list.front()));
+ size_t used_before = storage.used();
+ list.front().sort();
+ size_t used_after = storage.used();
+ BOOST_ASSERT(used_after > used_before);
+ BOOST_ASSERT(is_sorted(list.front()));
+ }
}
BOOST_AUTO_TEST_CASE(test_deque)
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