summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorKaz Kylheku <kaz@kylheku.com>2019-10-01 06:39:48 -0700
committerKaz Kylheku <kaz@kylheku.com>2019-10-01 06:39:48 -0700
commitf58f6224e6276f729a4d29732543530d561e2020 (patch)
treea45c1716d4ae22e8ebb2bb97dd485c249458077b
parent415bf7e8ee1a89e6a7f8c0ffc3e941f5ba232658 (diff)
downloadtxr-f58f6224e6276f729a4d29732543530d561e2020.tar.gz
txr-f58f6224e6276f729a4d29732543530d561e2020.tar.bz2
txr-f58f6224e6276f729a4d29732543530d561e2020.zip
tree: bug in key handling in insertion.
* tree.c (tr_insert): We must apply the key_fn to the key of the node which we are inserting, not only to the tree node being searched. This is different from delete, where the key argument is just the key value to be searched for, not a key object from which the key function extracts the key value. Variable naming is hereby adjusted: let's use tr_key for the key from the tree, and tn_key for the key extracted from the argument node. (tn_lookup, tr_delete): Rename the tn_key local variable to tr_key, for consistency with the naming inside tr_insert.
-rw-r--r--tree.c33
1 files changed, 17 insertions, 16 deletions
diff --git a/tree.c b/tree.c
index b7e528eb..14d3b585 100644
--- a/tree.c
+++ b/tree.c
@@ -128,18 +128,18 @@ static ucnum tn_size_one_child(val node, val child, ucnum size)
static val tn_lookup(struct tree *tr, val node, val key)
{
- val tn_key = if3(tr->key_fn,
+ val tr_key = if3(tr->key_fn,
funcall1(tr->key_fn, node->tn.key),
node->tn.key);
if (if3(tr->less_fn,
- funcall2(tr->less_fn, key, tn_key),
- less(key, tn_key)))
+ funcall2(tr->less_fn, key, tr_key),
+ less(key, tr_key)))
{
return if2(node->tn.left, tn_lookup(tr, node->tn.left, key));
} else if (if3(tr->equal_fn == nil,
- equal(key, tn_key),
- funcall2(tr->equal_fn, key, tn_key))) {
+ equal(key, tr_key),
+ funcall2(tr->equal_fn, key, tr_key))) {
return node;
} else {
return if2(node->tn.left, tn_lookup(tr, node->tn.left, key));
@@ -239,14 +239,16 @@ static void tr_find_rebuild_scapegoat(struct tree *tr, struct tree_iter *ti,
static void tr_insert(struct tree *tr, struct tree_iter *ti,
val subtree, val node)
{
- val key = node->tn.key;
val tn_key = if3(tr->key_fn,
+ funcall1(tr->key_fn, node->tn.key),
+ node->tn.key);
+ val tr_key = if3(tr->key_fn,
funcall1(tr->key_fn, subtree->tn.key),
subtree->tn.key);
if (if3(tr->less_fn,
- funcall2(tr->less_fn, key, tn_key),
- less(key, tn_key)))
+ funcall2(tr->less_fn, tn_key, tr_key),
+ less(tn_key, tr_key)))
{
if (subtree->tn.left) {
ti->path[ti->depth++] = subtree;
@@ -260,9 +262,8 @@ static void tr_insert(struct tree *tr, struct tree_iter *ti,
}
}
} else if (if3(tr->equal_fn == nil,
- equal(key, tn_key),
- funcall2(tr->equal_fn, key, tn_key))) {
- val parent = ti->path[ti->depth - 1];
+ equal(tn_key, tr_key),
+ funcall2(tr->equal_fn, tn_key, tr_key))) {
node->tn.left = subtree->tn.left;
node->tn.right = subtree->tn.right;
if (ti->depth > 0) {
@@ -297,20 +298,20 @@ static val tr_lookup(struct tree *tree, val key)
static val tr_do_delete(struct tree *tr, val subtree, val parent, val key)
{
- val tn_key = if3(tr->key_fn,
+ val tr_key = if3(tr->key_fn,
funcall1(tr->key_fn, subtree->tn.key),
subtree->tn.key);
if (if3(tr->less_fn,
- funcall2(tr->less_fn, key, tn_key),
- less(key, tn_key)))
+ funcall2(tr->less_fn, key, tr_key),
+ less(key, tr_key)))
{
if (subtree->tn.left)
return tr_do_delete(tr, subtree->tn.left, subtree, key);
return nil;
} else if (if3(tr->equal_fn == nil,
- equal(key, tn_key),
- funcall2(tr->equal_fn, key, tn_key))) {
+ equal(key, tr_key),
+ funcall2(tr->equal_fn, key, tr_key))) {
val le = subtree->tn.left;
val ri = subtree->tn.right;