diff options
| author | Tucker Evans <tucker@tuckerevans.com> | 2021-01-03 23:20:16 -0500 | 
|---|---|---|
| committer | Tucker Evans <tucker@tuckerevans.com> | 2021-01-03 23:20:16 -0500 | 
| commit | fe1647fbb45f2124baa34c1308c94cd845c78d48 (patch) | |
| tree | 24df9ca28fc9b9e61416e230b1331b612952cbba /structures | |
| parent | 54877babe8700bc39c7e2f8528e5146ed2fe6831 (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>
Diffstat (limited to 'structures')
| -rw-r--r-- | structures/rope/rope.c | 33 | 
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;  } | 
