From: Mark Wooding <mdw@distorted.org.uk>
Date: Tue, 20 Aug 2024 19:15:20 +0000 (+0100)
Subject: rbtree.c (rbtree_splitroot): Count output black-heights correctly.
X-Git-Tag: 0.99.0~113
X-Git-Url: https://www.chiark.greenend.org.uk/ucgi/~mdw/git/xyla/commitdiff_plain/a93c3ff7828cbc443d9c92a4fb9107c818a8302e

rbtree.c (rbtree_splitroot): Count output black-heights correctly.

The root is black, so the default would be that the subtrees have
black-height one less.  But if their roots (exist and) are red, then
we'll blacken them, which increases the black-height by one again.
---

diff --git a/rb-rbregress.ref b/rb-rbregress.ref
index ca80d60..d2a77b0 100644
--- a/rb-rbregress.ref
+++ b/rb-rbregress.ref
@@ -156,3 +156,111 @@ tree dump, ht = 3
 	#0x0000001f (n =   1)	                    ( ) 55
 	#0x00000022 (n =   5)	        (*) 57
 	#0x00000021 (n =   1)	                (*) 59
+
+;; `rbtree_splitroot' just could not track subtree heights correctly.
+tree dump, ht = 4
+	#0x00000044 (n =   2)	                        (*) 4
+	#0x00000043 (n =   1)	                            ( ) 6
+	#0x00000046 (n =   4)	                (*) 10
+	#0x00000045 (n =   1)	                        (*) 11
+	#0x0000004b (n =   9)	            ( ) 13
+	#0x00000047 (n =   1)	                        (*) 17
+	#0x0000004a (n =   4)	                (*) 18
+	#0x00000048 (n =   1)	                            ( ) 19
+	#0x00000049 (n =   2)	                        (*) 20
+	#0x00000050 (n =  14)	        (*) 22
+	#0x0000004c (n =   1)	                        (*) 23
+	#0x0000004f (n =   4)	                (*) 25
+	#0x0000004d (n =   1)	                            ( ) 26
+	#0x0000004e (n =   2)	                        (*) 27
+	#0x00000061 (n =  31)	(*) 30
+	#0x00000051 (n =   1)	                            ( ) 32
+	#0x00000052 (n =   2)	                        (*) 33
+	#0x00000057 (n =   7)	                (*) 34
+	#0x00000054 (n =   2)	                        (*) 36
+	#0x00000053 (n =   1)	                            ( ) 38
+	#0x00000056 (n =   4)	                    ( ) 40
+	#0x00000055 (n =   1)	                        (*) 41
+	#0x00000060 (n =  16)	        (*) 43
+	#0x00000058 (n =   1)	                            ( ) 45
+	#0x00000059 (n =   2)	                        (*) 46
+	#0x0000005f (n =   8)	                (*) 48
+	#0x0000005a (n =   1)	                            ( ) 49
+	#0x0000005b (n =   2)	                        (*) 51
+	#0x0000005e (n =   5)	                    ( ) 53
+	#0x0000005d (n =   2)	                        (*) 61
+	#0x0000005c (n =   1)	                            ( ) 62
+tree dump, ht = 3
+	#0x00000062 (n =   1)	                (*) 6
+	#0x00000064 (n =   3)	            ( ) 15
+	#0x00000063 (n =   1)	                (*) 16
+	#0x00000066 (n =   5)	        (*) 23
+	#0x00000065 (n =   1)	                (*) 24
+	#0x00000070 (n =  15)	    ( ) 33
+	#0x00000067 (n =   1)	                (*) 35
+	#0x0000006a (n =   4)	            ( ) 36
+	#0x00000069 (n =   2)	                (*) 37
+	#0x00000068 (n =   1)	                    ( ) 39
+	#0x0000006f (n =   9)	        (*) 40
+	#0x0000006b (n =   1)	                (*) 43
+	#0x0000006e (n =   4)	            ( ) 47
+	#0x0000006d (n =   2)	                (*) 48
+	#0x0000006c (n =   1)	                    ( ) 49
+	#0x00000075 (n =  20)	(*) 50
+	#0x00000071 (n =   1)	                (*) 57
+	#0x00000074 (n =   4)	        (*) 59
+	#0x00000072 (n =   1)	                    ( ) 61
+	#0x00000073 (n =   2)	                (*) 62
+tree dump, ht = 4
+	#0x00000044 (n =   1)	                            ( ) 4
+	#0x00000043 (n =   2)	                        (*) 6
+	#0x00000046 (n =   4)	                (*) 10
+	#0x00000045 (n =   1)	                        (*) 11
+	#0x0000004b (n =  17)	        (*) 13
+	#0x00000064 (n =   1)	                            ( ) 15
+	#0x00000063 (n =   3)	                        (*) 16
+	#0x00000047 (n =   1)	                            ( ) 17
+	#0x0000004a (n =   6)	                (*) 18
+	#0x00000048 (n =   1)	                            ( ) 19
+	#0x00000049 (n =   2)	                        (*) 20
+	#0x00000050 (n =  12)	            ( ) 22
+	#0x0000004c (n =   1)	                            ( ) 23
+	#0x00000065 (n =   2)	                        (*) 24
+	#0x0000004f (n =   5)	                (*) 25
+	#0x0000004d (n =   1)	                            ( ) 26
+	#0x0000004e (n =   2)	                        (*) 27
+	#0x00000061 (n =  28)	    ( ) 30
+	#0x00000051 (n =   2)	                        (*) 32
+	#0x00000052 (n =   1)	                            ( ) 33
+	#0x00000057 (n =   4)	                    ( ) 34
+	#0x00000067 (n =   1)	                        (*) 35
+	#0x00000054 (n =   6)	                (*) 36
+	#0x00000069 (n =   1)	                        (*) 37
+	#0x00000053 (n =  10)	        (*) 38
+	#0x00000068 (n =   1)	                        (*) 39
+	#0x00000056 (n =   3)	                (*) 40
+	#0x00000055 (n =   1)	                        (*) 41
+	#0x00000060 (n =  41)	(*) 43
+	#0x00000058 (n =   1)	                        (*) 45
+	#0x00000059 (n =   3)	                (*) 46
+	#0x0000006e (n =   1)	                        (*) 47
+	#0x0000005f (n =  12)	        (*) 48
+	#0x0000005a (n =   1)	                            ( ) 49
+	#0x00000075 (n =   3)	                        (*) 50
+	#0x0000005b (n =   1)	                            ( ) 51
+	#0x0000005e (n =   6)	                    ( ) 53
+	#0x00000071 (n =   2)	                        (*) 57
+	#0x00000074 (n =   1)	                            ( ) 59
+	#0x0000005d (n =   8)	                (*) 61
+	#0x0000005c (n =   1)	                        (*) 62
+tree dump, ht = 2
+	#0x00000062 (n =   2)	        (*) 6
+	#0x00000066 (n =   1)	            ( ) 23
+	#0x00000070 (n =   5)	    ( ) 33
+	#0x0000006a (n =   2)	        (*) 36
+	#0x0000006f (n =   1)	            ( ) 40
+	#0x0000006b (n =  10)	(*) 43
+	#0x0000006d (n =   1)	            ( ) 48
+	#0x0000006c (n =   2)	        (*) 49
+	#0x00000072 (n =   4)	    ( ) 61
+	#0x00000073 (n =   1)	        (*) 62
diff --git a/rbregress.in b/rbregress.in
index 38dc171..8a7c75e 100644
--- a/rbregress.in
+++ b/rbregress.in
@@ -88,3 +88,64 @@ D!
 D!
 
 \ D! ) D! ) D!
+
+:
+:;; `rbtree_splitroot' just could not track subtree heights correctly.
+
+=						(((((_ *4
+							(_ 6 _))
+				*10
+						(_ *11 _))
+			13
+						((_ *17 _)
+				*18
+							((_ 19 _)
+						*20 _)))
+		*22
+						((_ *23 _)
+				*25
+							((_ 26 _)
+						*27 _)))
+	*30
+							((((_ 32 _)
+						*33 _)
+				*34
+						((_ *36
+							(_ 38 _))
+					40
+						(_ *41 _)))
+		*43
+							(((_ 45 _)
+						*46 _)
+				*48
+							(((_ 49 _)
+						*51 _)
+					53
+						(_ *61
+							(_ 62 _))))))
+D!
+
+(
+=					(((((_ *6 _)
+				15
+					(_ *16 _))
+			*23
+					(_ *24 _))
+		33
+					(((_ *35 _)
+				36
+					(_ *37
+						(_ 39 _)))
+			*40
+					((_ *43 _)
+				47
+					(_ *48
+						(_ 49 _)))))
+	*50
+					((_ *57 _)
+			*59
+						((_ 61 _)
+					*62 _)))
+D!
+
+| D! ) D!
diff --git a/rbtree.c b/rbtree.c
index 8cb7cde..e4dbeba 100644
--- a/rbtree.c
+++ b/rbtree.c
@@ -1285,7 +1285,7 @@ void *rbtree_splitroot(struct bstnode **left_out, int *lht_out,
       if (right->f&RBF_RED) { right->f &= ~RBF_RED; }
     } else {
       if (blkht < 0) blkht = rbtree_height(node);
-      lht = rht = blkht;
+      lht = rht = blkht - 1;
       if (left && left->f&RBF_RED) { lht++; left->f &= ~RBF_RED; }
       if (right && right->f&RBF_RED) { rht++; right->f &= ~RBF_RED; }
       if (lht_out) *lht_out = lht;