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.

1 files changed, 4 insertions, 2 deletions

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);
   }