stdcxx-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Anton Pevtsov <ant...@moscow.vdiweb.com>
Subject Re: Re: test for lib.alg.sort
Date Tue, 07 Feb 2006 16:20:49 GMT
Martin Sebor wrote:

> <>> It looks to me like the sort and stable_sort tests are completel

> <>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.

Yes, the attached files contains separated tests for sort and
partial_sort algorithms.

Martin Sebor wrote:

> <>[...]

> <>> 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?
>
Hmm, hooks seems to be a tricky and platform-dependent solution.
May be it is possible to add the "logged" (as in the test driver) new
and delete operators into the library itself and switch to them using
some define?

With best wishes,
Anton Pevtsov

> <>
> -----Original Message-----
> From: Martin Sebor [mailto:sebor@roguewave.com]
> Sent: Tuesday, February 07, 2006 05:43
> To: stdcxx-dev@incubator.apache.org
> Subject: Re: test for lib.alg.sort
>
>
> 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
>  
>

Good!


>> 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?

Martin

#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 =
         std::get_temporary_buffer<int>(1000);

     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);
}


Mime
View raw message