Am Samstag, 8. Dezember 2007 schrieb Julian Seward:
> > I don't get the assertion until some more stuff has been added to
> > the tree - the reason is that although the tree is out of order that
> > node is at the root and is therefore found without having to decide
> > which way to go.
>
> But the tree isn't out of order, is it? I thought what you established
> on the way to the station is that the ordering is signed word ordering,
> not unsigned, yes?
In my opinion the problem is, that you have lost transitivity. Assume Word is
only 8 bits wide.
The range is -128 ... 127
Now there are three numbers:
a = -100
b = 0
c = 100
a - b = -100 < 0 ==> b > a
b - c = -100 < 0 ==> c > b
c - a = 200 == -56 < 0 ==> a > c
If you put a, b, c in this order in an AVL-Tree you get:
a
/ \
c b
Because b > a and c < a. Now we add e = -1 and f = 1 into the tree and
get:
a
/ \
c b
/ \
e f
One additional node: g = -2 results in this tree:
a
/ \
c b
/ \
e f
/
g
Now we violate the AVL conditions at node a and we have to rotate. The result
will be:
e
/ \
a b
/ \ \
c g f
Now searching for c will not succeed because c > e.
I have changed the createSecVBitTable function to show this error:
static OSet* createSecVBitTable(void)
{
SecVBitNode * n;
Addr aAligned;
OSet * set = VG_(OSetGen_Create)( offsetof(SecVBitNode, a),
NULL, // use fast comparisons
VG_(malloc), VG_(free) );
n = VG_(OSetGen_AllocNode)(set, sizeof(SecVBitNode));
n->a = 0x81000000;
VG_(OSetGen_Insert)(set, n);
n = VG_(OSetGen_AllocNode)(set, sizeof(SecVBitNode));
n->a = 0x0;
VG_(OSetGen_Insert)(set, n);
n = VG_(OSetGen_AllocNode)(set, sizeof(SecVBitNode));
n->a = 0x7F000000;
VG_(OSetGen_Insert)(set, n);
n = VG_(OSetGen_AllocNode)(set, sizeof(SecVBitNode));
n->a = 1;
VG_(OSetGen_Insert)(set, n);
n = VG_(OSetGen_AllocNode)(set, sizeof(SecVBitNode));
n->a = -1;
VG_(OSetGen_Insert)(set, n);
n = VG_(OSetGen_AllocNode)(set, sizeof(SecVBitNode));
n->a = -2;
VG_(OSetGen_Insert)(set, n);
aAligned = 0x0;
tl_assert2(VG_(OSetGen_Lookup)(set, &aAligned),
"Not found: %lu\n", aAligned);
aAligned = 0x7F000000;
tl_assert2(VG_(OSetGen_Lookup)(set, &aAligned),
"Not found: %lu\n", aAligned);
aAligned = 0x81000000;
tl_assert2(VG_(OSetGen_Lookup)(set, &aAligned),
"Not found: %lu\n", aAligned);
return set;
}
Greetings
Christoph
-------------------------------------------------------------------------
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
[email protected]
https://lists.sourceforge.net/lists/listinfo/valgrind-developers
