aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorTucker Evans <tucker@tuckerevans.com>2021-01-03 23:20:16 -0500
committerTucker Evans <tucker@tuckerevans.com>2021-01-03 23:20:16 -0500
commitfe1647fbb45f2124baa34c1308c94cd845c78d48 (patch)
tree24df9ca28fc9b9e61416e230b1331b612952cbba
parent54877babe8700bc39c7e2f8528e5146ed2fe6831 (diff)
Fix rope_relen to free unneeded nodesrope
During recalculating of length for rope nodes any that do not branch will be removed, e.g. node B: A / \ (B) <subtree 1> / <subtree 2> results in: A / \ <subtree 2> <subtree 1>
-rw-r--r--structures/rope/rope.c33
1 files changed, 26 insertions, 7 deletions
diff --git a/structures/rope/rope.c b/structures/rope/rope.c
index 4719b18..295a78c 100644
--- a/structures/rope/rope.c
+++ b/structures/rope/rope.c
@@ -103,15 +103,34 @@ rope *root;
}
size_t rope_relen(root)
-rope *root;
+rope **root;
{
- if (!root)
+ rope *tmp;
+
+ if (!*root)
return 0;
- if (root->str)
- return root->len;
+ tmp = *root;
+
+ if (tmp->str) {
+ return tmp->len;
+ } else {
+ if (tmp->left && !tmp->right) {
+ tmp->left->parent = tmp->left;
+ *root = tmp->left;
+
+ tmp->left = NULL;
+ rope_free(tmp);
+ } else if (tmp->right && !tmp->left) {
+ tmp->right->parent = tmp->right;
+ *root = tmp->right;
+
+ tmp->right = NULL;
+ rope_free(tmp);
+ }
+ }
- return root->len = rope_relen(root->left) + rope_len(root->right);
+ return (*root)->len = rope_relen(&(*root)->left) + rope_relen(&(*root)->right);
}
rope* str_to_rope(str)
@@ -206,8 +225,8 @@ size_t i;
*root = cur;
/*TODO should be rebalancing rather than just recalulating lengths*/
- rope_relen(split);
- rope_relen(*root);
+ rope_relen(&split);
+ rope_relen(root);
return split;
}