From: Christoph B. <bar...@or...> - 2007-12-08 11:10:32
|
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 |