From: Mark Wooding Date: Tue, 20 Aug 2024 19:03:38 +0000 (+0100) Subject: rbtree.c (rbtree_split): Ensure initial subtree root is black. X-Git-Tag: 0.99.0~114 X-Git-Url: https://www.chiark.greenend.org.uk/ucgi/~mdw/git/xyla/commitdiff_plain/9e97e8c9f94477cd4ad04f8a5314bebef0e3d54f rbtree.c (rbtree_split): Ensure initial subtree root is black. In `rbtree_split', if the path is empty, then we start with an empty tree on one side, and an initial subtree -- up to the first ancestor link in the opposite direction to the null link. Forcibly blacken the root of this subtree and set its black-height correctly. --- diff --git a/rb-rbregress.ref b/rb-rbregress.ref index f148f17..ca80d60 100644 --- a/rb-rbregress.ref +++ b/rb-rbregress.ref @@ -9,3 +9,150 @@ tree dump, ht = 1 #0x00000001 (n = 1) ( ) 0 #0x00000000 (n = 3) (*) 3 #0x00000002 (n = 1) ( ) 6 + +;; In `rbtree_split' with an empty path, the root of the initial tree +;; wasn't forcibly blackened. Make sure this is done and that the +;; black heights are correctly tracked. This causes all manner of +;; trouble otherwise, including leaking nodes because `rbtree_join' +;; assumes that a tree with zero black-height must be empty -- which +;; is true. +tree dump, ht = 3 + #0x00000003 (n = 1) (*) 12 + #0x00000005 (n = 3) (*) 13 + #0x00000004 (n = 1) (*) 14 + #0x0000000a (n = 8) ( ) 16 + #0x00000006 (n = 1) (*) 17 + #0x00000009 (n = 4) (*) 18 + #0x00000008 (n = 2) (*) 19 + #0x00000007 (n = 1) ( ) 23 + #0x00000011 (n = 15) (*) 24 + #0x0000000b (n = 1) (*) 28 + #0x0000000d (n = 3) ( ) 32 + #0x0000000c (n = 1) (*) 35 + #0x00000010 (n = 6) (*) 36 + #0x0000000f (n = 2) (*) 37 + #0x0000000e (n = 1) ( ) 39 +tree dump, ht = 2 + #0x00000007 (n = 1) (*) 23 + #0x00000011 (n = 3) ( ) 24 + #0x0000000b (n = 1) (*) 28 + #0x0000000d (n = 8) (*) 32 + #0x0000000c (n = 1) (*) 35 + #0x00000010 (n = 4) ( ) 36 + #0x0000000f (n = 2) (*) 37 + #0x0000000e (n = 1) ( ) 39 +tree dump, ht = 0 + (tree empty) +tree dump, ht = 3 + #0x00000003 (n = 1) (*) 12 + #0x00000005 (n = 3) (*) 13 + #0x00000004 (n = 1) (*) 14 + #0x0000000a (n = 7) (*) 16 + #0x00000006 (n = 1) (*) 17 + #0x00000009 (n = 3) (*) 18 + #0x00000008 (n = 1) (*) 19 + +;; The hairy test case which found both of these bugs. +tree dump, ht = 3 + #0x00000012 (n = 1) ( ) 0 + #0x00000013 (n = 2) (*) 3 + #0x00000015 (n = 4) (*) 6 + #0x00000014 (n = 1) (*) 9 + #0x0000001d (n = 12) ( ) 11 + #0x00000016 (n = 1) ( ) 12 + #0x00000017 (n = 2) (*) 21 + #0x0000001c (n = 7) (*) 22 + #0x00000019 (n = 2) (*) 27 + #0x00000018 (n = 1) ( ) 28 + #0x0000001b (n = 4) ( ) 31 + #0x0000001a (n = 1) (*) 35 + #0x00000023 (n = 18) (*) 41 + #0x0000001e (n = 1) ( ) 49 + #0x00000020 (n = 3) (*) 50 + #0x0000001f (n = 1) ( ) 55 + #0x00000022 (n = 5) (*) 57 + #0x00000021 (n = 1) (*) 59 +tree dump, ht = 4 + #0x00000025 (n = 2) (*) 0 + #0x00000024 (n = 1) ( ) 1 + #0x00000027 (n = 4) (*) 3 + #0x00000026 (n = 1) (*) 4 + #0x0000002c (n = 9) ( ) 6 + #0x00000028 (n = 1) ( ) 11 + #0x00000029 (n = 2) (*) 12 + #0x0000002b (n = 4) (*) 13 + #0x0000002a (n = 1) (*) 14 + #0x00000037 (n = 20) (*) 16 + #0x0000002d (n = 1) (*) 17 + #0x00000030 (n = 4) (*) 18 + #0x0000002f (n = 2) (*) 19 + #0x0000002e (n = 1) ( ) 23 + #0x00000036 (n = 10) ( ) 24 + #0x00000031 (n = 1) (*) 28 + #0x00000033 (n = 3) ( ) 32 + #0x00000032 (n = 1) (*) 35 + #0x00000035 (n = 5) (*) 36 + #0x00000034 (n = 1) (*) 37 + #0x00000042 (n = 31) (*) 39 + #0x00000038 (n = 1) (*) 41 + #0x0000003b (n = 4) (*) 43 + #0x0000003a (n = 2) (*) 44 + #0x00000039 (n = 1) ( ) 45 + #0x00000041 (n = 10) (*) 52 + #0x0000003c (n = 1) (*) 53 + #0x0000003e (n = 3) ( ) 56 + #0x0000003d (n = 1) (*) 58 + #0x00000040 (n = 5) (*) 60 + #0x0000003f (n = 1) (*) 61 +tree dump, ht = 3 + #0x00000024 (n = 2) (*) 1 + #0x00000026 (n = 1) ( ) 4 + #0x0000002b (n = 4) ( ) 13 + #0x0000002a (n = 1) (*) 14 + #0x00000037 (n = 8) (*) 16 + #0x0000002d (n = 1) (*) 17 + #0x00000030 (n = 3) ( ) 18 + #0x0000002f (n = 1) (*) 19 + #0x0000002e (n = 23) (*) 23 + #0x00000036 (n = 1) (*) 24 + #0x00000033 (n = 3) ( ) 32 + #0x00000035 (n = 1) (*) 36 + #0x00000034 (n = 5) (*) 37 + #0x00000042 (n = 1) (*) 39 + #0x0000003b (n = 14) ( ) 43 + #0x0000003a (n = 2) (*) 44 + #0x00000039 (n = 1) ( ) 45 + #0x00000041 (n = 8) (*) 52 + #0x0000003c (n = 2) (*) 53 + #0x0000003e (n = 1) ( ) 56 + #0x0000003d (n = 5) ( ) 58 + #0x00000040 (n = 2) (*) 60 + #0x0000003f (n = 1) ( ) 61 +tree dump, ht = 2 + #0x00000025 (n = 1) ( ) 0 + #0x00000027 (n = 3) (*) 3 + #0x0000002c (n = 1) ( ) 6 + #0x00000028 (n = 5) ( ) 11 + #0x00000029 (n = 1) (*) 12 + #0x00000031 (n = 8) (*) 28 + #0x00000032 (n = 2) (*) 35 + #0x00000038 (n = 1) ( ) 41 +tree dump, ht = 3 + #0x00000012 (n = 1) ( ) 0 + #0x00000013 (n = 2) (*) 3 + #0x00000015 (n = 4) (*) 6 + #0x00000014 (n = 1) (*) 9 + #0x0000001d (n = 12) ( ) 11 + #0x00000016 (n = 1) ( ) 12 + #0x00000017 (n = 2) (*) 21 + #0x0000001c (n = 7) (*) 22 + #0x00000019 (n = 2) (*) 27 + #0x00000018 (n = 1) ( ) 28 + #0x0000001b (n = 4) ( ) 31 + #0x0000001a (n = 1) (*) 35 + #0x00000023 (n = 18) (*) 41 + #0x0000001e (n = 1) ( ) 49 + #0x00000020 (n = 3) (*) 50 + #0x0000001f (n = 1) ( ) 55 + #0x00000022 (n = 5) (*) 57 + #0x00000021 (n = 1) (*) 59 diff --git a/rbregress.in b/rbregress.in index 6f9668b..38dc171 100644 --- a/rbregress.in +++ b/rbregress.in @@ -6,3 +6,85 @@ = (_ *0 (_ 3 _)) D! ( 6k ~ D! + +: +:;; In `rbtree_split' with an empty path, the root of the initial tree +:;; wasn't forcibly blackened. Make sure this is done and that the +:;; black heights are correctly tracked. This causes all manner of +:;; trouble otherwise, including leaking nodes because `rbtree_join' +:;; assumes that a tree with zero black-height must be empty -- which +:;; is true. += ((((_ *12 _) + *13 + (_ *14 _)) + 16 + ((_ *17 _) + *18 + (_ *19 + (_ 23 _)))) + *24 + (((_ *28 _) + 32 + (_ *35 _)) + *36 + (_ *37 + (_ 39 _)))) +D! 22@ / D! ) D! ) D! + +: +:;; The hairy test case which found both of these bugs. += (((((_ 0 _) + *3 _) + *6 + (_ *9_)) + 11 + (((_ 12 _) + *21 _) + *22 + ((_ *27 + (_ 28 _)) + 31 + (_ *35 _)))) + *41 + (((_ 49 _) + *50 + (_ 55 _)) + *57 + (_ *59 _))) +D! + +( += (((((_ *0 + (_ 1 _)) + *3 + (_ *4 _)) + 6 + (((_ 11 _) + *12 _) + *13 + (_ *14 _))) + *16 + (((_ *17 _) + *18 + (_ *19 + (_ 23 _))) + 24 + (((_ *28 _) + 32 + (_ *35 _)) + *36 + (_ *37 _)))) + *39 + (((_ *41 _) + *43 + (_ *44 + (_ 45 _))) + *52 + (((_ *53 _) + 56 + (_ *58 _)) + *60 + (_ *61 _)))) +D! + +\ D! ) D! ) D! diff --git a/rbtree.c b/rbtree.c index 047c474..8cb7cde 100644 --- a/rbtree.c +++ b/rbtree.c @@ -1121,8 +1121,12 @@ void *rbtree_split(struct bstree_nodecls *cls, node = parent; link = next; \ } \ \ + /* Establish the left and right trees. */ \ left = 0; lht = 0; \ right = &node->_bst; rht = blkht; \ + \ + /* Make sure the root of the right tree is painted black. */ \ + if (node->f&RBF_RED) { rht++; node->f &= ~RBF_RED; } \ } while (0) INIT_SPLIT_EMPTY(left, lht, right, rht); else