From 095232d6c245d2669eacb7056a8d94293ba8a501 Mon Sep 17 00:00:00 2001
From: Kaz Kylheku <kaz@kylheku.com>
Date: Sat, 18 Dec 2021 13:22:11 -0800
Subject: tree: bugfix wrong tree-count.

When duplicate keys are inserted in the default way with
replacement, the tree size must not be incremented.

* tree.c (tr_insert): Increment the tr->size and maintain
tr->max_size here. In the case of replacing an existing node,
do not touch the count.

* tests/010/tree.tl: Add test cases covering duplicate
insertion and tree-count.
(tree_insert_node): Remove unconditional size increment.
---
 tests/010/tree.tl | 10 ++++++++++
 tree.c            |  6 ++++--
 2 files changed, 14 insertions(+), 2 deletions(-)

diff --git a/tests/010/tree.tl b/tests/010/tree.tl
index 898fd91d..79bab793 100644
--- a/tests/010/tree.tl
+++ b/tests/010/tree.tl
@@ -216,3 +216,13 @@
 (let* ((items (make-items))
        (tr (tree items : : : t)))
   (vtest (vec-list [mapcar .label tr]) [mapcar .label items]))
+
+(let ((tr (tree)))
+  (mtest
+    (tree-insert tr 1) #N(1 nil nil)
+    (tree-insert tr 1) #N(1 nil nil)
+    (tree-insert tr 1) #N(1 nil nil))
+  (tree-insert tr 2)
+  (test (tree-count tr) 2)
+  (tree-insert tr 1 t)
+  (test (tree-count tr) 3))
diff --git a/tree.c b/tree.c
index c3ddd756..8af798ad 100644
--- a/tree.c
+++ b/tree.c
@@ -379,6 +379,8 @@ static void tr_insert(val tree, struct tree *tr, struct tree_iter *ti,
     } else {
       int dep = ti->depth + 1;
       set(mkloc(subtree->tn.left, subtree), node);
+      if (++tr->size > tr->max_size)
+        tr->max_size = tr->size;
       if (subtree->tn.right == nil && (((ucnum) 1) << dep) > tr->size) {
         set(mkloc(ti->path[ti->depth++], ti->self), subtree);
         tr_find_rebuild_scapegoat(tree, tr, ti, node, 1);
@@ -408,6 +410,8 @@ static void tr_insert(val tree, struct tree *tr, struct tree_iter *ti,
     } else {
       int dep = ti->depth + 1;
       set(mkloc(subtree->tn.right, subtree), node);
+      if (++tr->size > tr->max_size)
+        tr->max_size = tr->size;
       if (subtree->tn.left == nil && (((ucnum) 1) << dep) > tr->size) {
         set(mkloc(ti->path[ti->depth++], ti->self), subtree);
         tr_find_rebuild_scapegoat(tree, tr, ti, node, 1);
@@ -608,8 +612,6 @@ val tree_insert_node(val tree, val node, val dup_in)
     set(mkloc(tr->root, tree), node);
   } else {
     struct tree_iter ti = tree_iter_init(0);
-    if (++tr->size > tr->max_size)
-      tr->max_size = tr->size;
     tr_insert(tree, tr, &ti, tr->root, node, dup);
   }
 
-- 
cgit v1.2.3