Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r67673 - sandbox/guild/pool/libs/pool/test
From: chankwanting_at_[hidden]
Date: 2011-01-05 02:51:33


Author: ktchan
Date: 2011-01-05 02:51:32 EST (Wed, 05 Jan 2011)
New Revision: 67673
URL: http://svn.boost.org/trac/boost/changeset/67673

Log:
Add test for simple_segregated_storage.
Added:
   sandbox/guild/pool/libs/pool/test/test_simple_seg_storage.cpp (contents, props changed)
   sandbox/guild/pool/libs/pool/test/test_simple_seg_storage.hpp (contents, props changed)
   sandbox/guild/pool/libs/pool/test/track_allocator.hpp (contents, props changed)
Text files modified:
   sandbox/guild/pool/libs/pool/test/Jamfile.v2 | 1 +
   1 files changed, 1 insertions(+), 0 deletions(-)

Modified: sandbox/guild/pool/libs/pool/test/Jamfile.v2
==============================================================================
--- sandbox/guild/pool/libs/pool/test/Jamfile.v2 (original)
+++ sandbox/guild/pool/libs/pool/test/Jamfile.v2 2011-01-05 02:51:32 EST (Wed, 05 Jan 2011)
@@ -14,6 +14,7 @@
 
 test-suite pool :
     [ run test_gcd_lcm.cpp ]
+ [ run test_simple_seg_storage.cpp ]
     [ run test_pool_alloc.cpp ]
     [ run pool_msvc_compiler_bug_test.cpp ]
     [ run test_msvc_mem_leak_detect.cpp ]

Added: sandbox/guild/pool/libs/pool/test/test_simple_seg_storage.cpp
==============================================================================
--- (empty file)
+++ sandbox/guild/pool/libs/pool/test/test_simple_seg_storage.cpp 2011-01-05 02:51:32 EST (Wed, 05 Jan 2011)
@@ -0,0 +1,280 @@
+/* Copyright (C) 2011 Kwan Ting Chan
+ *
+ * Use, modification and distribution is subject to the
+ * Boost Software License, Version 1.0. (See accompanying
+ * file LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+ */
+
+#include "test_simple_seg_storage.hpp"
+#include "track_allocator.hpp"
+
+#include <boost/pool/simple_segregated_storage.hpp>
+#include <boost/assert.hpp>
+#include <boost/math/common_factor_ct.hpp>
+
+#include <boost/detail/lightweight_test.hpp>
+
+#include <algorithm>
+#include <functional>
+#include <set>
+#include <vector>
+
+#include <cstddef>
+#include <cstdlib>
+#include <ctime>
+
+// "A free list is ordered if repeated calls to malloc() will result in a
+// constantly-increasing sequence of values, as determined by std::less<void*>"
+// Return: true if in constantly-increasing order, false otherwise
+bool check_is_order(const std::vector<void*>& vs)
+{
+ if(vs.size() < 2) { return true; }
+
+ void *lower, *higher;
+ std::vector<void*>::const_iterator ci = vs.begin();
+ lower = *(ci++);
+ while(ci != vs.end())
+ {
+ higher = *(ci++);
+ if(!std::less<void*>()(lower, higher)) { return false; }
+ }
+
+ return true;
+}
+
+// Return: number of chunks malloc'd from store
+std::size_t test_is_order(test_simp_seg_store& store)
+{
+ std::vector<void*> vpv;
+ std::size_t nchunk = 0;
+ // Pre: !empty()
+ while(!store.empty())
+ {
+ void* const first = store.get_first();
+ void* const pv = store.malloc();
+ // "Takes the first available chunk from the free list
+ // and returns it"
+ BOOST_TEST(first == pv);
+
+ vpv.push_back(pv);
+ ++nchunk;
+ }
+ BOOST_TEST(check_is_order(vpv));
+
+ return nchunk;
+}
+
+int main()
+{
+ std::srand(static_cast<unsigned>(std::time(0)));
+
+ /* Store::segregate(block, sz, partition_sz, end) */
+ std::size_t partition_sz
+ = boost::math::static_lcm<sizeof(void*), sizeof(int)>::value;
+ std::size_t block_size;
+ while((block_size = std::rand()) < partition_sz) {}
+ // Pre: npartition_sz >= sizeof(void*)
+ // npartition_sz = sizeof(void*) * i, for some integer i
+ // nsz >= npartition_sz
+ // block is properly aligned for an array of object of
+ // size npartition_sz and array of void *
+ BOOST_ASSERT(partition_sz >= sizeof(void*));
+ BOOST_ASSERT(partition_sz % sizeof(void*) == 0);
+ BOOST_ASSERT(block_size >= partition_sz);
+ {
+ char* const pc = track_allocator::malloc(block_size);
+ // (Test) Pre: block of memory is valid
+ BOOST_ASSERT(pc);
+ int endadd = 0;
+ void* const pvret = test_simp_seg_store::segregate(pc, block_size,
+ partition_sz, &endadd);
+
+ // The first chunk "is always equal to block"
+ BOOST_TEST(pvret == pc);
+
+ void* cur = test_simp_seg_store::get_nextof(static_cast<int*>(pvret));
+ void* last = pvret;
+ std::size_t nchunk = 1;
+ while(cur != &endadd)
+ {
+ ++nchunk;
+
+ // Memory of each chunk does not overlap
+ // The free list constructed is actually from the given block
+ // The "interleaved free list is ordered"
+ BOOST_TEST(std::less_equal<void*>()(static_cast<char*>(last)
+ + partition_sz, cur));
+ BOOST_TEST(std::less_equal<void*>()(static_cast<char*>(cur)
+ + partition_sz, pc + block_size));
+
+ last = cur;
+ cur = test_simp_seg_store::get_nextof(static_cast<int*>(cur));
+ }
+ // "The last chunk is set to point to end"
+ // "Partitioning into as many partition_sz-sized chunks as possible"
+ BOOST_TEST(nchunk == block_size/partition_sz);
+ }
+
+ /* t.add_block(block, sz, partition_sz), t.malloc() */
+ {
+ // Default constructor of simple_segregated_storage do nothing
+ test_simp_seg_store tstore;
+ // Post: empty()
+ BOOST_TEST(tstore.empty());
+
+ char* const pc = track_allocator::malloc(block_size);
+ tstore.add_block(pc, block_size, partition_sz);
+
+ // The first chunk "is always equal to block"
+ BOOST_TEST(tstore.get_first() == pc);
+
+ // Empty before add_block() => "is ordered after"
+ std::size_t nchunk = test_is_order(tstore);
+ // "Partitioning into as many partition_sz-sized chunks as possible"
+ BOOST_TEST(nchunk == block_size/partition_sz);
+
+ BOOST_ASSERT(partition_sz <= 23);
+ test_simp_seg_store tstore2;
+ char* const pc2 = track_allocator::malloc(75);
+ tstore2.add_block(pc2, 24, partition_sz);
+ tstore2.add_block(pc2 + 49, 24, partition_sz);
+ tstore2.add_block(pc2 + 25, 24, partition_sz);
+ tstore2.add_block(track_allocator::malloc(23), 23, partition_sz);
+ std::size_t nchunk_ref = (3*(24/partition_sz)) + (23/partition_sz);
+ for(nchunk = 0; !tstore2.empty(); tstore2.malloc(), ++nchunk) {}
+ // add_block() merges new free list to existing
+ BOOST_TEST(nchunk == nchunk_ref);
+ }
+
+ /* t.free(chunk) */
+ {
+ test_simp_seg_store tstore;
+ char* const pc = track_allocator::malloc(partition_sz);
+ tstore.add_block(pc, partition_sz, partition_sz);
+ void* pv = tstore.malloc();
+ BOOST_TEST(tstore.empty());
+ tstore.free(pv);
+ }
+
+ /* t.add_ordered_block(block, sz, partition_sz) */
+ {
+ {
+ char* const pc = track_allocator::malloc(6 * partition_sz);
+ std::vector<void*> vpv;
+ vpv.push_back(pc);
+ vpv.push_back(pc + (2 * partition_sz));
+ vpv.push_back(pc + (4 * partition_sz));
+
+ do
+ {
+ test_simp_seg_store tstore;
+ tstore.add_ordered_block(vpv[0], 2*partition_sz, partition_sz);
+ tstore.add_ordered_block(vpv[1], 2*partition_sz, partition_sz);
+ tstore.add_ordered_block(vpv[2], 2*partition_sz, partition_sz);
+ // "Order-preserving"
+ test_is_order(tstore);
+ } while(std::next_permutation(vpv.begin(), vpv.end()));
+ }
+
+ {
+ test_simp_seg_store tstore;
+ char* const pc = track_allocator::malloc(6 * partition_sz);
+ tstore.add_ordered_block(pc, 2 * partition_sz, partition_sz);
+ tstore.add_ordered_block(pc + (4 * partition_sz),
+ (2 * partition_sz), partition_sz);
+ // "Order-preserving"
+ test_is_order(tstore);
+ }
+
+ {
+ test_simp_seg_store tstore;
+ char* const pc = track_allocator::malloc(6 * partition_sz);
+ tstore.add_ordered_block(pc + (4 * partition_sz),
+ (2 * partition_sz), partition_sz);
+ tstore.add_ordered_block(pc, 2 * partition_sz, partition_sz);
+ // "Order-preserving"
+ test_is_order(tstore);
+ }
+ }
+
+ /* t.ordered_free(chunk) */
+ {
+ char* const pc = track_allocator::malloc(6 * partition_sz);
+
+ test_simp_seg_store tstore;
+ tstore.add_block(pc, 6 * partition_sz, partition_sz);
+
+ std::vector<void*> vpv;
+ for(std::size_t i=0; i < 6; ++i) { vpv.push_back(tstore.malloc()); }
+ BOOST_ASSERT(tstore.empty());
+ std::random_shuffle(vpv.begin(), vpv.end());
+
+ for(std::size_t i=0; i < 6; ++i)
+ {
+ tstore.ordered_free(vpv[i]);
+ }
+ // "Order-preserving"
+ test_is_order(tstore);
+ }
+
+ /* t.malloc_n(n, partition_sz) */
+ {
+ {
+ char* const pc = track_allocator::malloc(12 * partition_sz);
+ test_simp_seg_store tstore;
+ tstore.add_ordered_block(pc, 2 * partition_sz, partition_sz);
+ tstore.add_ordered_block(pc + (3 * partition_sz),
+ 3 * partition_sz, partition_sz);
+ tstore.add_ordered_block(pc + (7 * partition_sz),
+ 5 * partition_sz, partition_sz);
+
+ void* pvret = tstore.malloc_n(6, partition_sz);
+ BOOST_TEST(pvret == 0);
+
+ pvret = tstore.malloc_n(0, partition_sz);
+ // There's no prohibition against asking for zero elements
+ BOOST_TEST(pvret == 0);
+
+ pvret = tstore.malloc_n(3, partition_sz);
+ // Implicit assumption that contiguous sequence found is the first
+ // available while traversing from the start of the free list
+ BOOST_TEST(pvret == pc + (3 * partition_sz));
+
+ pvret = tstore.malloc_n(4, partition_sz);
+ BOOST_TEST(pvret == pc + (7 * partition_sz));
+
+ // There should still be two contiguous
+ // and one non-contiguous chunk left
+ std::size_t nchunks = 0;
+ while(!tstore.empty())
+ {
+ tstore.malloc();
+ ++nchunks;
+ }
+ BOOST_TEST(nchunks == 3);
+ }
+
+ {
+ char* const pc = track_allocator::malloc(12 * partition_sz);
+ test_simp_seg_store tstore;
+ tstore.add_ordered_block(pc, 2 * partition_sz, partition_sz);
+ tstore.add_ordered_block(pc + (3 * partition_sz),
+ 3 * partition_sz, partition_sz);
+ tstore.add_ordered_block(pc + (7 * partition_sz),
+ 5 * partition_sz, partition_sz);
+
+ void* pvret = tstore.malloc_n(3, partition_sz);
+ // "Order-preserving"
+ test_is_order(tstore);
+ }
+ }
+
+ for(std::set<char*>::iterator itr
+ = track_allocator::allocated_blocks.begin();
+ itr != track_allocator::allocated_blocks.end();
+ ++itr)
+ {
+ delete [] *itr;
+ }
+ track_allocator::allocated_blocks.clear();
+}

Added: sandbox/guild/pool/libs/pool/test/test_simple_seg_storage.hpp
==============================================================================
--- (empty file)
+++ sandbox/guild/pool/libs/pool/test/test_simple_seg_storage.hpp 2011-01-05 02:51:32 EST (Wed, 05 Jan 2011)
@@ -0,0 +1,171 @@
+/* Copyright (C) 2000, 2001 Stephen Cleary
+* Copyright (C) 2011 Kwan Ting Chan
+*
+* Use, modification and distribution is subject to the
+* Boost Software License, Version 1.0. (See accompanying
+* file LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+*/
+
+#ifndef BOOST_POOL_TEST_SIMP_SEG_STORE_HPP
+#define BOOST_POOL_TEST_SIMP_SEG_STORE_HPP
+
+#include <boost/pool/simple_segregated_storage.hpp>
+#include <boost/assert.hpp>
+
+#include <boost/detail/lightweight_test.hpp>
+
+#include <functional>
+#include <set>
+#include <utility>
+#include <vector>
+
+#include <cstddef>
+
+class test_simp_seg_store : public boost::simple_segregated_storage<std::size_t>
+{
+private:
+ // ::first is the address of the start of the added block,
+ // ::second is the size in bytes of the added block
+ std::vector<std::pair<void*, std::size_t> > allocated_blocks;
+ size_type np_sz;
+ std::set<void*> allocated_chunks;
+
+ void set_partition_size(const size_type sz)
+ {
+ if(allocated_blocks.empty())
+ {
+ np_sz = sz;
+ }
+ else
+ {
+ BOOST_ASSERT(np_sz == sz);
+ }
+ }
+
+ // Return: true if chunk is from added blocks, false otherwise
+ bool is_inside_allocated_blocks(void* const chunk) const
+ {
+ typedef std::vector<std::pair<void*, std::size_t> >::const_iterator
+ VPIter;
+ for(VPIter iter = allocated_blocks.begin();
+ iter != allocated_blocks.end();
+ ++iter)
+ {
+ if( std::less_equal<void*>()(iter->first, chunk)
+ && std::less_equal<void*>()(static_cast<char*>(chunk) + np_sz,
+ static_cast<char*>(iter->first) + iter->second) )
+ {
+ return true;
+ }
+ }
+
+ return false;
+ }
+
+ void check_in(void* const chunk)
+ {
+ // Check that the newly allocated chunk has not already previously
+ // been allocated, and that the memory does not overlap with
+ // previously allocated chunks
+ for(std::set<void*>::const_iterator iter = allocated_chunks.begin();
+ iter != allocated_chunks.end();
+ ++iter)
+ {
+ BOOST_TEST( std::less_equal<void*>()(static_cast<char*>(chunk)
+ + np_sz, *iter)
+ || std::less_equal<void*>()(static_cast<char*>(*iter)
+ + np_sz, chunk) );
+ }
+
+ allocated_chunks.insert(chunk);
+ }
+
+ void check_out(void* const chunk)
+ {
+ BOOST_TEST(allocated_chunks.erase(chunk) == 1);
+ }
+
+public:
+ test_simp_seg_store()
+ : np_sz(0) {}
+
+ void* get_first() { return first; }
+ static void*& get_nextof(void* const ptr) { return nextof(ptr); }
+
+ // (Test) Pre: npartition_sz of all added block is the same
+ // different blocks of memory does not overlap
+ void add_block(void* const block,
+ const size_type nsz, const size_type npartition_sz)
+ {
+ set_partition_size(npartition_sz);
+ allocated_blocks.push_back(
+ std::make_pair<void*, std::size_t>(block, nsz) );
+ simple_segregated_storage<std::size_t>::add_block(
+ block, nsz, npartition_sz );
+ // Post: !empty()
+ BOOST_TEST(!empty());
+ }
+
+ // (Test) Pre: npartition_sz of all added block is the same
+ // different blocks of memory does not overlap
+ void add_ordered_block(void* const block,
+ const size_type nsz, const size_type npartition_sz)
+ {
+ set_partition_size(npartition_sz);
+ allocated_blocks.push_back(
+ std::make_pair<void*, std::size_t>(block, nsz) );
+ simple_segregated_storage<std::size_t>::add_ordered_block(
+ block, nsz, npartition_sz );
+ // Post: !empty()
+ BOOST_TEST(!empty());
+ }
+
+ void* malloc()
+ {
+ void* const ret = simple_segregated_storage<std::size_t>::malloc();
+ // Chunk returned should actually be from added blocks
+ BOOST_TEST(is_inside_allocated_blocks(ret));
+ check_in(ret);
+ return ret;
+ }
+
+ void free(void* const chunk)
+ {
+ BOOST_ASSERT(chunk);
+ check_out(chunk);
+ simple_segregated_storage<std::size_t>::free(chunk);
+ // Post: !empty()
+ BOOST_TEST(!empty());
+ }
+
+ void ordered_free(void* const chunk)
+ {
+ BOOST_ASSERT(chunk);
+ check_out(chunk);
+ simple_segregated_storage<std::size_t>::ordered_free(chunk);
+ // Post: !empty()
+ BOOST_TEST(!empty());
+ }
+
+ void* malloc_n(size_type n, size_type partition_size)
+ {
+ void* const ret = simple_segregated_storage<std::size_t>::malloc_n(n,
+ partition_size);
+
+ if(ret)
+ {
+ for(std::size_t i=0; i < n; ++i)
+ {
+ void* const chunk = static_cast<char*>(ret)
+ + (i * partition_size);
+ // Memory returned should actually be from added blocks
+ BOOST_TEST(is_inside_allocated_blocks(chunk));
+ check_in(chunk);
+ }
+ }
+
+ return ret;
+ }
+};
+
+#endif // BOOST_POOL_TEST_SIMP_SEG_STORE_HPP

Added: sandbox/guild/pool/libs/pool/test/track_allocator.hpp
==============================================================================
--- (empty file)
+++ sandbox/guild/pool/libs/pool/test/track_allocator.hpp 2011-01-05 02:51:32 EST (Wed, 05 Jan 2011)
@@ -0,0 +1,104 @@
+/* Copyright (C) 2000, 2001 Stephen Cleary
+* Copyright (C) 2011 Kwan Ting Chan
+*
+* Use, modification and distribution is subject to the
+* Boost Software License, Version 1.0. (See accompanying
+* file LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+*/
+
+#ifndef BOOST_POOL_TRACK_ALLOCATOR_HPP
+#define BOOST_POOL_TRACK_ALLOCATOR_HPP
+
+#include <boost/detail/lightweight_test.hpp>
+
+#include <new>
+#include <set>
+#include <stdexcept>
+
+#include <cstddef>
+
+// Each "tester" object below checks into and out of the "cdtor_checker",
+// which will check for any problems related to the construction/destruction of
+// "tester" objects.
+class cdtor_checker
+{
+private:
+ // Each constructed object registers its "this" pointer into "objs"
+ std::set<void*> objs;
+
+public:
+ // True iff all objects that have checked in have checked out
+ bool ok() const { return objs.empty(); }
+
+ ~cdtor_checker()
+ {
+ BOOST_TEST(ok());
+ }
+
+ void check_in(void * const This)
+ {
+ BOOST_TEST(objs.find(This) == objs.end());
+ objs.insert(This);
+ }
+
+ void check_out(void * const This)
+ {
+ BOOST_TEST(objs.find(This) != objs.end());
+ objs.erase(This);
+ }
+};
+static cdtor_checker mem;
+
+struct tester
+{
+ tester(bool throw_except = false)
+ {
+ if(throw_except)
+ {
+ throw std::logic_error("Deliberate constructor exception");
+ }
+
+ mem.check_in(this);
+ }
+
+ tester(const tester &)
+ {
+ mem.check_in(this);
+ }
+
+ ~tester()
+ {
+ mem.check_out(this);
+ }
+};
+
+// Allocator that registers alloc/dealloc to/from the system memory
+struct track_allocator
+{
+ typedef std::size_t size_type;
+ typedef std::ptrdiff_t difference_type;
+
+ static std::set<char*> allocated_blocks;
+
+ static char* malloc(const size_type bytes)
+ {
+ char* const ret = new (std::nothrow) char[bytes];
+ allocated_blocks.insert(ret);
+ return ret;
+ }
+
+ static char* free(char* const block)
+ {
+ BOOST_TEST(allocated_blocks.find(block) != allocated_blocks.end());
+ allocated_blocks.erase(block);
+ delete [] block;
+ }
+
+ static bool ok()
+ {
+ return allocated_blocks.empty();
+ }
+};
+std::set<char*> track_allocator::allocated_blocks;
+
+#endif // BOOST_POOL_TRACK_ALLOCATOR_HPP


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