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 f148f1724178e464e33963f61aba2a50241c07ae..ca80d60d3ead118b118621b6c377c611334ef51d 100644 (file)
--- 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 6f9668b78819915e2f77b8e4383cd169f35b810d..38dc1718fcffe9bdda4afae0db8a22777a62e1a2 100644 (file)
--- 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 047c47436aed82016fe989b336885315cae42101..8cb7cdeb904c098f393b519fa8cbf4dff24f7634 100644 (file)
--- 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