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

Obvious editing blunder.

diff --git a/Makefile b/Makefile
index 9b2dc95fb6c1b81fd98609ecda537590454e0981..dd942041c60984ccb60ab9de86331dd509dabf40 100644 (file)
--- 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 (file)
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 (file)
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 28aa433d4bcc28cb8948054ac6abe69e01a144a3..44bb5190532ab316aa01b05be6c089961887aacb 100644 (file)
--- 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;