Martin Sebor wrote:
I think we should rewrite the test and hardcode the initial and
partitioned sequences. I don't think we can sufficiently exercise the
interesting/corner cases by generating the sequence. Also, I think we
should be able to eliminate one of the two predicates. It's sufficient
to exercise the algorithm with just one so long as we exhaustively
verify all the requirements. Let me know if this makes sense to you
and/or if you have any questions.
The attached file 25.partitions.cpp contains the updated test version.
I hardcoded test sequences and eliminated one predicate.
Martin Sebor wrote:
It's certainly possible that there is a bug in the algorithm, but I
would be more inclined to suspect the test before the algorithm just
because you just made making non-trivial changes to it.
[...]
A simple test case would be helpful.
The old test version didn't exercise all possible cases. I updated the
test according to your notes and got the same results. So I still
suspect the bug in the algorithm.
The attached file stable_partition_test.cpp illustrates the problem:
the algorithm fails when the predicate returns true for any element.
I debug the algorithm and found the following code in algorithm.cc, line
760:
...
_Dist __fill = 0;
const _BidirIter __res =
__stable_partition_adaptive (__first, __last, __pred, __dist,
__pair.first, __pair.second,
__fill, (_TypeT*)0);
for (_TypeT *__ptr = __pair.first + __fill; !(__pair.first ==
--__ptr); )
(*__ptr).~_TypeT ();
...
If the __fill remains equal to 0 after the __stable_partition_adaptive
call the "for" will never end and will try to call destructors of
non-existing elements moving from the left bound of the given sequence
to left. Also if __fill is equal to 1 no destructors will be called, but
one should be, shouldn't it?
May be, something like this
...
for (_TypeT *__ptr = __pair.first + __fill; !(__pair.first ==
__ptr--); )
(*__ptr).~_TypeT ();
...
will fix the issue?
And I have another question: what will happen with the temporary buffer
in stable_partition if the X copy ctor throws an exception? It looks
like the buffer will leak.
With best wishes,
Anton Pevtsov
-----Original Message-----
From: Martin Sebor [mailto:[EMAIL PROTECTED]
Sent: Friday, January 27, 2006 03:43
To: stdcxx-dev@incubator.apache.org
Subject: Re: test for lib.alg.partitions
Anton Pevtsov wrote:
The attached file contains my attempt to update lib.alg.partiton and
lib.alg.stable_partiton tests and port them to new test driver.
I think we should rewrite the test and hardcode the initial and
partitioned sequences. I don't think we can sufficiently exercise the
interesting/corner cases by generating the sequence. Also, I think we
should be able to eliminate one of the two predicates. It's sufficient
to exercise the algorithm with just one so long as we exhaustively
verify all the requirements. Let me know if this makes sense to you
and/or if you have any questions.
I suspect a bug in the stable_partiton algorithm implementation.
Suppose that for all elements of an array the predicate is true. The
stable_partition should return "last" in this case. But call of the
stable_partiton on this array fails with the following
assertion:
stdlib\tests\src\alg_test.cpp:135: __thiscall X::~X(void):
Assertion 'id_ && id_ <= id_gen_' failed. In the debugger you can see
that the id_ of the deleting X object is equal to 0 (I suppose that
this X is invalid), but the "this" looks good.
Yes, the id_ member is reset in the dtor to indicate that the object has
already been destroyed (no valid id_ is ever 0).
What do you think about this issue?
It's certainly possible that there is a bug in the algorithm, but I
would be more inclined to suspect the test before the algorithm just
because you just made making non-trivial changes to it.
I plan investigate this more deeply.
A simple test case would be helpful.
Current test version includes the tests on which stable_partiton fails
and these tests are marked using comments.
Also, there is another intresting thing with the stable_partition
algorithm. Suppose that an array contains only one element. According
to the standard the complexity in this case should be equal to 0
swaps. Actually there are 0 swaps, but there is 1 assignment. I guess
this is not a bug (the standard talks nothing about the assignments),
but may be there are unnecessary assignment operations in the
stable_partitions implementation.
What do you think about it?
There is no reason to do anything if there's only one element in the
range, but if the standard allows it we don't need to go to heroic
measures eliminating it. That said, if it's an easy change we should
definitely do it.
A few more comments below...
With best wishes,
Anton Pevtsov
----------------------------------------------------------------------
--
[...]
template <class T>
struct LessThanPredicate : ComparePredicateBase
{
LessThanPredicate (const int value) : ComparePredicateBase (value)
{}
// return a type other than bool but one that is implicitly
// convertible to bool to detect incorrect assumptions
ConvertibleToBool operator() (const T &arg) {
Let's replace the type with the canned conv_to_bool type defined in
alg_test.h.
[...]
// exercises std::partition() and std::stable_partition() template
<class T, class Iterator, class Predicate> void test_partitions (const
std::size_t line, const std::size_t N,
line should be int to match the type of the __LINE__ macro.
const Iterator& it, const Predicate& pr,
const T* , int val, bool stable)
{
_RWSTD_UNUSED(pr);
const char* const itname = type_name (it, (T*)0);
const char* const fname =
stable ? "stable_partition" : "partition";
const char* const funname = Predicate::name();
rw_info (0, 0, 0,
"%s %s (%1$s, %1$s, %s)",
itname, fname, funname);
// create an array of T
T::gen_ = gen_seq;
T *buf = new T[N];
for (std::size_t i = 0; i < N; ++i) {
const Iterator first = make_iter (buf, buf, buf + i + 1, it);
The end pointer above should be (buf + i), not (buf + i + 1). (This is
true in general for all these tests. I corrected this in the others but
forgot to mention it.)
Martin
#include <algorithm>
#include <stdio.h>
static int ids;
struct TestX
{
TestX () {
id_ = ++ids;
val_ = id_;
printf ("ctor created TestX with id == %d, this == %p\n",
id_, (void*) this);
}
TestX (const TestX& y) {
id_ = ++ids;
this->val_ = y.val_;
printf ("copy ctor created TestX with id == %d, this == %p\n",
id_, (void*) this);
}
~TestX () {
printf ("deleting TestX with id == %d, this == %p\n",
id_, (void*) this);
id_ = 0;
}
int val_;
private:
int id_;
};
bool true_predicate (TestX& ) {
return true;
}
int main()
{
TestX* px = new TestX[3];
printf ("begin stable_partition\n");
std::stable_partition (px, px + 2, true_predicate);
printf ("end stable_partition\n");
delete[] px;
return 0;
}
/***************************************************************************
*
* partitions.cpp - test exercising 25.2.12 [lib.alg.partitions]
*
* $Id: //stdlib/dev/tests/stdlib/algorithm/partitions.cpp#18 $
*
***************************************************************************
*
* Copyright (c) 1994-2005 Quovadx, Inc., acting through its Rogue Wave
* Software division. Licensed under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance with the
* License. You may obtain a copy of the License at
* http://www.apache.org/licenses/LICENSE-2.0. Unless required by
* applicable law or agreed to in writing, software distributed under
* the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR
* CONDITIONS OF ANY KIND, either express or implied. See the License
* for the specific language governing permissions and limitations under
* the License.
*
**************************************************************************/
#include <algorithm> // for partition, stable_partition
#include <cstring> // for strlen, size_t
#include <alg_test.h>
#include <driver.h> // for rw_test()
/**************************************************************************/
_RWSTD_NAMESPACE (std) {
// disable explicit instantiation for compilers (like MSVC)
// that can't handle it
#ifndef _RWSTD_NO_EXPLICIT_INSTANTIATION
template
BidirIter<assign<base<cpy_ctor> > >
partition (BidirIter<assign<base<cpy_ctor> > >,
BidirIter<assign<base<cpy_ctor> > >,
predicate<assign<base<cpy_ctor> > >);
template
BidirIter<assign<base<cpy_ctor> > >
stable_partition (BidirIter<assign<base<cpy_ctor> > >,
BidirIter<assign<base<cpy_ctor> > >,
predicate<assign<base<cpy_ctor> > >);
#endif // _RWSTD_NO_EXPLICIT_INSTANTIATION
} // namespace std
/**************************************************************************/
template <class T>
struct GreaterThanPredicate
{
static std::size_t funcalls_;
GreaterThanPredicate (const int value) : value_(value) {
funcalls_ = 0;
}
// return a type other than bool but one that is implicitly
// convertible to bool to detect incorrect assumptions
conv_to_bool operator() (const T &arg) {
++funcalls_;
return conv_to_bool::make (arg.val_ > value_);
}
static const char* name () { return "GreaterThanPredicate"; }
private:
const int value_;
void operator= (GreaterThanPredicate&);
};
template<class T> std::size_t GreaterThanPredicate<T>::funcalls_;
/**************************************************************************/
// exercises std::partition() and std::stable_partition()
template <class T, class Iterator, class Predicate>
void test_partitions (int line,
const char *src,
const char *dst,
const int value,
const std::size_t offset,
const Iterator &it,
const Predicate *ppred,
const T* ,
bool stable)
{
_RWSTD_UNUSED(ppred);
const char* const itname = type_name (it, (T*)0);
const char* const fname =
stable ? "stable_partition" : "partition";
const char* const funname = Predicate::name();
const std::size_t nsrc = std::strlen (src);
const std::size_t ndst = std::strlen (dst);
T* const xsrc = T::from_char (src, nsrc);
T* const xdst = T::from_char (dst, ndst);
T* const xsrc_end = xsrc + nsrc;
const Iterator first = make_iter (xsrc, xsrc, xsrc_end, it);
const Iterator last = make_iter (xsrc_end, xsrc, xsrc_end, it);
const std::size_t last_n_op_assign = T::n_total_op_assign_;
const Predicate pred(value);
const Iterator res =
stable ? std::stable_partition (first, last, pred)
: std::partition (first, last, pred);
// check that the returned iterator points to the expected element
bool success = res.cur_ == first.cur_ + offset;
rw_assert (success, 0, line,
"line %d: std::%s <%s, %s>(\"%s\", ...) ==> \"%{X=*.*}\", "
"returned iterator it = first + %td, expected first + %zu",
__LINE__, fname, itname, funname, src, int (nsrc),
-1, xsrc, res.cur_ - first.cur_, offset);
// check 25.2.12, p2 & p5
// "left" part of the array there the predicate should be true
std::size_t i = 0;
for ( ; i < offset; i++) {
success = xsrc[i].val_ > value;
if (!success)
break;
}
rw_assert (success, 0, line,
"line %d: std::%s <%s, %s>(\"%s\", ...) "
"==> \"%{X=*.*}\", at %zu got: %#c !> %#c",
__LINE__, fname, itname, funname, src, int (nsrc),
-1, xsrc, i + 1, xsrc[i].val_, value);
// "right" part of the array there the predicate should be false
for ( ; i < nsrc; i++) {
success = xsrc[i].val_ <= value;
if (!success)
break;
}
rw_assert (success, 0, line,
"line %d: std::%s <%s, %s>(\"%s\", ...) "
"==> \"%{X=*.*}\", at %zu got: %#c !<= %#c",
__LINE__, fname, itname, funname, src, int (nsrc),
-1, xsrc, i + 1, xsrc[i].val_, value);
// check the complexity, 25.2.12 p3 & p6
// first check number of swaps, 2 assignments per swap
// add 1 in case of stable_partition to avoid the assertion failing
// when i == 0 (only one element presents in the sequence)
// is this one extra assignment an algorithm bug??
// the standard talks about swaps only, not about assignments
// and there are 0 swaps (1 swap equals 2 assignments) in this case...
std::size_t exp_assigns = stable ? 2 * nsrc * ::ilog2 (nsrc) + 1 : nsrc;
std::size_t op_assigns = T::n_total_op_assign_ - last_n_op_assign;
success = op_assigns <= exp_assigns;
rw_assert (success, 0, line,
"line %d: std::%s <%s, %s>(\"%s\", ...): complexity: "
"got %zu assignments, expected no more than %zu",
__LINE__, fname, itname, funname, src,
op_assigns, exp_assigns);
// second check the number of the predicate calls
success = Predicate::funcalls_ == nsrc;
rw_assert (success, 0, line,
"line %d: std::%s <%s, %s>(\"%s\", ...): complexity: "
"got %zu applications of the predicate, "
"expected no more than %zu",
__LINE__, fname, itname, funname, src,
Predicate::funcalls_, nsrc);
if (!stable) {
delete[] xsrc;
delete[] xdst;
return;
}
// check the stable_partition is really stable 25.2.12, p5
for (i = 0; i < nsrc; i++) {
success = xsrc[i].val_ == xdst[i].val_;
if (!success)
break;
}
rw_assert (success, 0, line,
"line %d: std::%s <%s, %s>(\"%s\", ...) ==> \"%{X=*.*}\", "
"expected \"%{X=*.*}\", realtive order broken at %zu, "
"%#c != %#c",
__LINE__, fname, itname, funname, src,
int (nsrc), int (i), xsrc, int (ndst), int (i), xdst,
i, xsrc[i].val_, xdst[i].val_);
delete[] xsrc;
delete[] xdst;
}
template <class T, class Iterator>
void test_partitions (const Iterator &it,
const T* ,
bool stable)
{
const char* const itname = type_name (it, (T*)0);
const char* const fname =
stable ? "stable_partition" : "partition";
const char* const funname = GreaterThanPredicate<T>::name();
rw_info (0, 0, 0,
"%s %s (%1$s, %1$s, %s)",
itname, fname, funname);
#define TEST(src, dest, mid, offet) \
test_partitions (__LINE__, src, dest, mid, offet, it, \
(GreaterThanPredicate<T>*)0, (T*)0, stable)
// stable_partition fails this test
TEST ("abcdefghij", "abcdefghij", 0, 10);
TEST ("abcdefghij", "bcdefghija", 'a', 9);
TEST ("abcdefghij", "cdefghijab", 'b', 8);
TEST ("abcdefghij", "defghijabc", 'c', 7);
TEST ("abcdefghij", "efghijabcd", 'd', 6);
TEST ("abcdefghij", "fghijabcde", 'e', 5);
TEST ("abcdefghij", "ghijabcdef", 'f', 4);
TEST ("abcdefghij", "hijabcdefg", 'g', 3);
TEST ("abcdefghij", "ijabcdefgh", 'h', 2);
TEST ("abcdefghij", "jabcdefghi", 'i', 1);
TEST ("abcdefghij", "abcdefghij", 'j', 0);
// stable_partition fails this test
TEST ("jihgfedcba", "jihgfedcba", 0, 10);
TEST ("jihgfedcba", "jihgfedcba", 'a', 9);
TEST ("jihgfedcba", "jihgfedcba", 'b', 8);
TEST ("jihgfedcba", "jihgfedcba", 'c', 7);
TEST ("jihgfedcba", "jihgfedcba", 'd', 6);
TEST ("jihgfedcba", "jihgfedcba", 'e', 5);
TEST ("jihgfedcba", "jihgfedcba", 'f', 4);
TEST ("jihgfedcba", "jihgfedcba", 'g', 3);
TEST ("jihgfedcba", "jihgfedcba", 'h', 2);
TEST ("jihgfedcba", "jihgfedcba", 'i', 1);
TEST ("jihgfedcba", "jihgfedcba", 'j', 0);
// stable_partition fails this test
TEST ("a", "a", 0, 1);
TEST ("a", "a", 'a', 0);
}
/**************************************************************************/
/* extern */ int rw_opt_no_partition; // --no-partition
/* extern */ int rw_opt_no_stable_partition; // --no-stable_partition
/* extern */ int rw_opt_no_bidir_iter; // --no-BidirectionalIterator
/* extern */ int rw_opt_no_rnd_iter; // --no-RandomAccessIterator
template <class T>
void test_partitions (const T* ,
bool stable)
{
rw_info (0, 0, 0,
"template <class %s, class %s> %1$s %s (%1$s, %1$s, %2$s)",
"BidirectionalIterator", "Predicate",
stable ? "stable_partition" : "partition");
if (rw_opt_no_bidir_iter) {
rw_note (0, __FILE__, __LINE__, "BidirectionalIterator test disabled");
}
else {
test_partitions (BidirIter<T>(), (T*)0, stable);
}
if (rw_opt_no_rnd_iter) {
rw_note (0, __FILE__, __LINE__, "RandomAccessIterator test disabled");
}
else {
test_partitions (RandomAccessIter<T>(), (T*)0, stable);
}
}
static int run_test (int, char*[])
{
if (rw_opt_no_partition) {
rw_note (0, __FILE__, __LINE__, "std::partition test disabled");
}
else {
test_partitions ((X*)0, false);
}
if (rw_opt_no_stable_partition) {
rw_note (0, __FILE__, __LINE__,
"std::stable_partition test disabled");
}
else {
test_partitions ((X*)0, true);
}
return 0;
}
/**************************************************************************/
int main (int argc, char *argv[])
{
return rw_test (argc, argv, __FILE__,
"lib.alg.partitions",
0 /* no comment */, run_test,
"|-no-partition# "
"|-no-stable_partition# "
"|-no-BidirectionalIterator# "
"|-no-RandomAccessIterator",
&rw_opt_no_partition,
&rw_opt_no_stable_partition,
&rw_opt_no_bidir_iter,
&rw_opt_no_rnd_iter);
}
