> Yes. The relation established by the comparison function has to be
> transitive. This is not the case here. Therefore the function should not be
> used.
>
> I've shown how this affects the AVL tree in theory and implementation. This
> also fits one fact that Tom gives: There have to be additional additions
> and deletions to the tree till the values are not found.
Below is a test program which compares comparison functions through
exhaustive testing. It shows immediately that the slow (reference)
and fast versions produce different results.
We can fix Memcheck by falling back to the reference version, but I'd
like to see if there is a way to get the correct behaviour without
the extra conditionals.
J
#include <stdio.h>
typedef signed char Char;
typedef unsigned char UChar;
Char cmp_slow_signed ( Char x, Char y ) {
if (x < y) return -1;
if (x > y) return 1;
return 0;
}
Char cmp_fast_signed ( Char x, Char y ) {
Char diff = x - y;
return diff;
}
void run_test_signed ( char* testname,
Char(*cmp1)(Char,Char),
Char(*cmp2)(Char,Char) )
{
unsigned int x, y;
printf("\n%s: start\n", testname);
for (x = 0; x < 256; x++) {
for (y = 0; y < 256; y++) {
Char r1 = cmp1( (Char)x, (Char)y );
Char r2 = cmp2( (Char)x, (Char)y );
if (r1 < 0 && r2 < 0) continue;
if (r1 > 0 && r2 > 0) continue;
if (r1 == 0 && r2 == 0) continue;
printf("%s: difference at %x %x\n\n", testname, x, y);
return;
}
}
printf("%s: success\n\n", testname);
}
int main ( void )
{
run_test_signed( "cmp_fast_signed",
cmp_slow_signed, cmp_fast_signed );
return 0;
}
-------------------------------------------------------------------------
SF.Net email is sponsored by:
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://sourceforge.net/services/buy/index.php
_______________________________________________
Valgrind-developers mailing list
Valgrind-developers@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/valgrind-developers
