From fe1647fbb45f2124baa34c1308c94cd845c78d48 Mon Sep 17 00:00:00 2001 From: Tucker Evans Date: Sun, 3 Jan 2021 23:20:16 -0500 Subject: Fix rope_relen to free unneeded nodes During recalculating of length for rope nodes any that do not branch will be removed, e.g. node B: A / \ (B) / results in: A / \ --- structures/rope/rope.c | 33 ++++++++++++++++++++++++++------- 1 file 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; } -- cgit v1.1