From: Mark Wooding <mdw@distorted.org.uk>
Date: Tue, 20 Aug 2024 19:17:40 +0000 (+0100)
Subject: avltree.c (avltree_splitroot): Set right tree height correctly.
X-Git-Tag: 0.99.0~112
X-Git-Url: https://www.chiark.greenend.org.uk/ucgi/~mdw/git/xyla/commitdiff_plain/8a8a2ffb2d41c0d92e5dd40728a18c1d3e3eeb3a

avltree.c (avltree_splitroot): Set right tree height correctly.

Obvious editing blunder.
---

diff --git a/Makefile b/Makefile
index 9b2dc95..dd94204 100644
--- a/Makefile
+++ b/Makefile
@@ -60,7 +60,7 @@ COMMON_TESTS		 = test-simple
 TREES			+= avl
 avl_LIBSRCS		 = avltree.c
 avl_DEFINES		 = -DTREE=AVL
-avl_TESTS		 = avltest
+avl_TESTS		 = avltest avlregress
 
 TREES			+= rb
 rb_LIBSRCS		 = rbtree.c
diff --git a/avl-avlregress.ref b/avl-avlregress.ref
new file mode 100644
index 0000000..2790424
--- /dev/null
+++ b/avl-avlregress.ref
@@ -0,0 +1,90 @@
+
+;; Bungled heights in `avltree_splitroot'.
+tree dump, ht = 6
+	#0x00000000 (n =   1)	            (=) 1
+	#0x00000003 (n =   4)	        (+) 7
+	#0x00000002 (n =   2)	            (+) 9
+	#0x00000001 (n =   1)	                (=) 10
+	#0x0000000c (n =  13)	    (+) 15
+	#0x00000004 (n =   1)	                (=) 16
+	#0x00000007 (n =   4)	            (+) 20
+	#0x00000006 (n =   2)	                (+) 21
+	#0x00000005 (n =   1)	                    (=) 22
+	#0x0000000b (n =   8)	        (-) 23
+	#0x00000008 (n =   1)	                (=) 25
+	#0x0000000a (n =   3)	            (=) 26
+	#0x00000009 (n =   1)	                (=) 27
+	#0x0000001d (n =  30)	(=) 28
+	#0x0000000d (n =   1)	            (=) 29
+	#0x00000011 (n =   5)	        (+) 32
+	#0x0000000e (n =   1)	                (=) 37
+	#0x00000010 (n =   3)	            (=) 41
+	#0x0000000f (n =   1)	                (=) 42
+	#0x0000001c (n =  16)	    (+) 44
+	#0x00000012 (n =   1)	                (=) 45
+	#0x00000015 (n =   4)	            (+) 46
+	#0x00000014 (n =   2)	                (+) 51
+	#0x00000013 (n =   1)	                    (=) 52
+	#0x0000001b (n =  10)	        (=) 55
+	#0x00000016 (n =   1)	                    (=) 56
+	#0x00000017 (n =   2)	                (-) 57
+	#0x0000001a (n =   5)	            (=) 58
+	#0x00000018 (n =   1)	                    (=) 59
+	#0x00000019 (n =   2)	                (-) 61
+tree dump, ht = 4
+	#0x0000001f (n =   2)	        (+) 3
+	#0x0000001e (n =   1)	            (=) 4
+	#0x00000023 (n =   6)	    (=) 6
+	#0x00000020 (n =   1)	            (=) 9
+	#0x00000022 (n =   3)	        (=) 10
+	#0x00000021 (n =   1)	            (=) 12
+	#0x00000029 (n =  12)	(=) 15
+	#0x00000025 (n =   2)	        (+) 16
+	#0x00000024 (n =   1)	            (=) 17
+	#0x00000028 (n =   5)	    (=) 19
+	#0x00000026 (n =   1)	            (=) 20
+	#0x00000027 (n =   2)	        (-) 25
+tree dump, ht = 6
+	#0x00000000 (n =   1)	                    (=) 1
+	#0x0000001f (n =   2)	                (-) 3
+	#0x0000001e (n =   4)	            (-) 4
+	#0x00000023 (n =   1)	                (=) 6
+	#0x00000003 (n =   8)	        (-) 7
+	#0x00000002 (n =   1)	                (=) 9
+	#0x00000001 (n =   3)	            (=) 10
+	#0x00000021 (n =   1)	                (=) 12
+	#0x0000000c (n =  19)	    (=) 15
+	#0x00000004 (n =   1)	                    (=) 16
+	#0x00000024 (n =   3)	                (=) 17
+	#0x00000028 (n =   1)	                    (=) 19
+	#0x00000007 (n =   6)	            (=) 20
+	#0x00000006 (n =   2)	                (+) 21
+	#0x00000005 (n =   1)	                    (=) 22
+	#0x0000000b (n =  10)	        (-) 23
+	#0x00000008 (n =   1)	                (=) 25
+	#0x0000000a (n =   3)	            (=) 26
+	#0x00000009 (n =   1)	                (=) 27
+	#0x0000001d (n =  36)	(=) 28
+	#0x0000000d (n =   1)	            (=) 29
+	#0x00000011 (n =   5)	        (+) 32
+	#0x0000000e (n =   1)	                (=) 37
+	#0x00000010 (n =   3)	            (=) 41
+	#0x0000000f (n =   1)	                (=) 42
+	#0x0000001c (n =  16)	    (+) 44
+	#0x00000012 (n =   1)	                (=) 45
+	#0x00000015 (n =   4)	            (+) 46
+	#0x00000014 (n =   2)	                (+) 51
+	#0x00000013 (n =   1)	                    (=) 52
+	#0x0000001b (n =  10)	        (=) 55
+	#0x00000016 (n =   1)	                    (=) 56
+	#0x00000017 (n =   2)	                (-) 57
+	#0x0000001a (n =   5)	            (=) 58
+	#0x00000018 (n =   1)	                    (=) 59
+	#0x00000019 (n =   2)	                (-) 61
+tree dump, ht = 3
+	#0x00000020 (n =   2)	    (+) 9
+	#0x00000022 (n =   1)	        (=) 10
+	#0x00000029 (n =   6)	(=) 15
+	#0x00000025 (n =   1)	        (=) 16
+	#0x00000026 (n =   3)	    (=) 20
+	#0x00000027 (n =   1)	        (=) 25
diff --git a/avlregress.in b/avlregress.in
new file mode 100644
index 0000000..2a5c22a
--- /dev/null
+++ b/avlregress.in
@@ -0,0 +1,53 @@
+;;; Regression testing for AVL trees.
+
+:
+:;; Bungled heights in `avltree_splitroot'.
+=					((((_ 1 _)
+				7
+					(_ 9
+						(_ 10 _)))
+			15
+						(((_ 16 _)
+					20
+						(_ 21
+							(_ 22 _)))
+				23
+						((_ 25 _)
+					26
+						(_ 27 _))))
+	28
+					(((_ 29 _)
+				32
+						((_ 37 _)
+					41
+						(_ 42 _)))
+			44
+						(((_ 45 _)
+					46
+						(_ 51
+							(_ 52 _)))
+				55
+							(((_ 56 _)
+						57 _)
+					58
+							((_ 59 _)
+						61 _)))))
+
+D!
+
+(
+=			(((_ 3
+				(_ 4 _))
+		6
+				((_ 9 _)
+			10
+				(_ 12 _)))
+	15
+			((_ 16
+				(_ 17 _))
+		19
+				((_ 20 _)
+			25 _)))
+D!
+
+| D! ) D!
diff --git a/avltree.c b/avltree.c
index 28aa433..44bb519 100644
--- a/avltree.c
+++ b/avltree.c
@@ -1406,7 +1406,7 @@ void *avltree_splitroot(struct bstnode **left_out, int *lht_out,
 	default: assert(0);
       }
       if (lht_out) *lht_out = lht;
-      if (rht_out) *rht_out = lht;
+      if (rht_out) *rht_out = rht;
     }
     node->f &= ~AVLF_BALMASK;
     *left_out = left ? &left->_bst : 0;