Re: Simple question, err... I think

* "Dr" Jon Harrop:
Alf P. Steinbach wrote:
That is an optimisation, not an error.
Since when was it an optimization to check an always false condition?

That's been an optimisation for quite some time...

Which planet are you from?

It's never been an optimization to introduce non-functional and misleading code.


Doesn't it sound a bit far-fetched even to you?

Not at all.

"I'm optimizing this example of good C++ coding (to be compared to
another language) by adding some statements that I know, but the
compiler doesn't, will never have any effect other than using time."

Removing the unused "if" statements is certainly a good thing. However, the
code was not "wrong".

It was and is.


Second, delete p->l is executed without
reassigning that member, which results in an invalid pointer value in
the structure, which is the second glaring error in this code snippet.
No. The value p->l is no longer used.
Your nodes contain no other indication of which pointers are valid, than
the pointer values themselves.

Thus, the resulting structure causes Undefined Behavior when searched.

The code certainly appears to work and doesn't seem to generate invalid
pointers. Can you walkthough an example of the code generating an invalid
data structure?

I can but won't: I guess that's probably homework you want done.

However, the following program demonstrates some of the errors; all you have to do is check it out manually or using the nearest debugger.

I've instrumented your code by (1) replacing raw Node* pointers with DbgPointer<Node>, (2) replacing 'delete p' with calls to a destroy function (which in turn calls delete and notes the fact), and (3) counting the number of instances of Node existing at any moment. Note that this instrumentation is specific to both your existing code and the test program. More generally much smarter techniques would be required.

<code>
#include <cassert>

// Does not support aliasing and such things, just bare-bones impl.
template< typename T >
struct DbgPointer
{
T* myP;
bool iAmValid;

DbgPointer( T* p = 0 ): myP( p ), iAmValid( true ) {}

T* operator->() { assert( myP != 0 && iAmValid ); return myP; }

DbgPointer& operator=( T* p )
{
assert( p == 0 || myP == 0 );
myP = p;
iAmValid = true;
}

operator void*() const { return myP; }

void destroy()
{
delete myP;
iAmValid = false;
}

bool isValid() const { return iAmValid; }
};

template< typename T >
void destroy( DbgPointer<T>& p ) { p.destroy(); }

void reportCount( unsigned );

struct CountedObject
{
static unsigned theCount;
CountedObject(){ ::reportCount( ++theCount ); }
~CountedObject(){ ::reportCount( --theCount ); }
};

unsigned CountedObject::theCount = 0;

struct Node: CountedObject
{
typedef DbgPointer<Node> Ptr;

int is_red;
Ptr l, r;
int n;
Node( bool is_red_, Ptr l_, int n_, Ptr r_ )
: is_red( is_red_ ), l( l_ ), n( n_ ), r( r_ )
{}
};

typedef Node::Ptr Set;

Set E=0;
Set R(Set l, int n, Set r) { return new Node(true, l, n, r); }
Set B(Set l, int n, Set r) { return new Node(false, l, n, r); }

struct Found { Found() {} };

Set ins(const int x, Set p) {
if (!p) return R(E, x, E);
const int y = p->n;
if (p->is_red) {
if (x < y) {
Set l2=ins(x, p->l);
if (l2 == p->l) throw Found();
::destroy( p->l );
return R(l2, y, p->r);
}
if (x > y) {
Set r2=ins(x, p->r);
if (r2 == p->r) throw Found();
::destroy( p->r );
return R(p->l, y, r2);
}
}
else {
if (x < y) {
Set l2 = ins(x, p->l);
if (l2 == p->l) throw Found();
::destroy( p->l );
if (l2->is_red && l2->l && l2->l->is_red)
return R(B(l2->l->l, l2->l->n, l2->l->r), l2->n, B(l2->r, y, p->r));
if (l2->is_red && l2->r && l2->r->is_red)
return R(B(l2->l, l2->n, l2->r->l), l2->r->n, B(l2->r->r, y, p->r));
return B(l2, y, p->r);
}
if (x > y) {
Set r2 = ins(x, p->r);
if (r2 == p->r) throw Found();
::destroy( p->r );
if (r2->is_red && r2->l && r2->l->is_red)
return R(B(p->l, y, r2->l->l), r2->l->n, B(r2->l->r, r2->n, r2->r));
if (r2->is_red && r2->r && r2->r->is_red)
return R(B(p->l, y, r2->l), r2->n, B(r2->r->l, r2->r->n, r2->r->r));
return B(p->l, y, r2);
}
}
throw Found();
}

#include <stdexcept>
#include <cstddef>
#include <iostream>
#include <ostream>

void reportCount( unsigned c )
{
std::cout << c << std::endl;
}

bool throwX( char const s[] ) { throw std::runtime_error( s ); }

bool lament( char const s[] )
{
std::cout << "Error: " << s << "." << std::endl;
return false;
}

void cppMain()
{
Set r0 = 0;
Set r1 = ins( 100, r0 );
Set r2 = ins( 50, r1 );
Set r3 = ins( 25, r2 );

!(r3->is_red)
|| lament( "red root node" );
!(r3->n == 100 && r3->l->n == 50 && r3->l->l->n == 25 )
|| lament( "degenerate tree" );
!(Node::theCount > 3)
|| lament( "memory leakage" );
!(r2.isValid() && r2->l != 0 && !r2->l.isValid())
|| lament( "invalid pointers" );
}

int main()
{
try
{
cppMain();
return EXIT_SUCCESS;
}
catch( std::exception const& x )
{
std::cerr << "!" << x.what() << std::endl;
return EXIT_FAILURE;
}
catch( ... )
{
std::cerr << "!UNKNOWN EXCEPTION" << std::endl;
return EXIT_FAILURE;
}
}
</code>

which yields the following

<output>
1
2
3
4
5
4
5
Error: red root node.
Error: degenerate tree.
Error: memory leakage.
Error: invalid pointers.
</output>

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
.

Relevant Pages