incubator-stdcxx-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Martin Sebor <>
Subject Re: test for lib.alg.sort
Date Tue, 07 Feb 2006 02:43:17 GMT
Anton Pevtsov wrote:
> The attached file contains tests for the lib.alg.sort,
> lib.alg.stable_sort, lib.alg.partitial_sort and
> lib.alg.partitial_sort_copy algorithms.

It looks to me like the sort and stable_sort tests are completely
independent of the partial sort tests, correct? If that's so, could
you please split the test into two? It will make them easier to
maintain and prevent errors in one from affecting the results of
the other.

> Here I check the algotithms correctness using the hardcoded sequences


> and verify the complexity using the random-generated sequences.
> The upper estimated value for algorithms was left without changes, but
> may be we should open a jira issue about the complexity checks.

I agree, let's do.

> Martin Sebor wrote:
> [...]
>  >Be sure to verify this in the test itself (i.e., the test should issue
>  >an error when it can't force the algorithm to use dynamically allocated
>  >memory.
> [...]
> I am not sure that I understand your completely, but I added the test
> with forced dynamically memory allocation for stable_sort.

What I meant was that after calling get_temporary_buffer() first
in order to force stable sort to use dynamically allocated storage
the test should use the replacement operator to detect whether the
algorithm in fact does use it.

Here's a little program that should demonstrate what I mean. Note
that the replacement operator new and delete don't work across
shared library boundaries on AIX and Windows. It would be nice to
find an equivalent solution that does work there (or at least on
Windows). Some kind of malloc() hook maybe -- any ideas?


#include <cassert>     // for assert()
#include <cstddef>     // for ptrdiff_t, size_t
#include <algorithm>   // for stable_sort()
#include <memory>      // for get_temporary_buffer()
#include <utility>     // for pair
#include <rw_new.h>    // for rwt_free_store, rwt_checkpoint()

int main ()
     // prevent stable_sort from using the temporary buffer
     // and force the algorithm to dynamically allocate storage
     // instead
     const std::pair<int*, std::ptrdiff_t> tmpbuf =

     rwt_free_store state [2];

     // save the initial state of the dynamic store in state[0]
     state [0] = *rwt_get_free_store (0);

     int a[] = { 0, 1, 2 };
     std::stable_sort (a, a + sizeof a / sizeof *a);

     // save the current state of the dynamic store in state[1]
     rwt_get_free_store (state + 1);

     // compute the difference between state[1] and state[0]
     const rwt_free_store* const pdiff =
         rwt_checkpoint (state, state + 1);

     // assert that the two states are different
     assert (0 != pdiff);

     // compute the number of calls to operators new and delete,
     // and the amount of outstanding dynamic storage between
     // the two checkpoints
     const std::size_t new_calls =
         pdiff->new_calls_ [0] + pdiff->new_calls_ [1];
     const std::size_t delete_calls =
         pdiff->delete_calls_ [0] + pdiff->delete_calls_ [1];
     const std::size_t leaked_blocks =
         pdiff->blocks_ [0] + pdiff->blocks_ [1];
     const std::size_t leaked_bytes =
         pdiff->bytes_ [0] + pdiff->bytes_ [1];

     // assert that the algorithm used dynamic storage and that
     // that it made at least as many calls to delete as it did
     // to new (it may have called operator delete (0))
     assert (0 < new_calls);
     assert (new_calls <= delete_calls);

     // assert that the algorithm released all dynamically allocated
     // storage
     assert (0 == leaked_blocks);
     assert (0 == leaked_bytes);

View raw message