diff options
| author | Stefan Monnier <monnier@iro.umontreal.ca> | 2022-11-07 00:38:43 -0500 |
|---|---|---|
| committer | Stefan Monnier <monnier@iro.umontreal.ca> | 2022-11-07 00:38:43 -0500 |
| commit | 35221a7bd55e18244604376497097f4259c7351b (patch) | |
| tree | b471f73adcd5c6ddc26127014fee554e78e61873 | |
| parent | 61d55ce3bb4dc1f7deac552439c61bbe0909dcdb (diff) | |
| download | emacs-35221a7bd55e18244604376497097f4259c7351b.tar.gz | |
(itree_insert_gap, itree_delete_gap): Minor optimization
`limit` can get smaller in either of the two children of a node.
It can also happen that the root node itself has a low enough limit
that the loop can be interrupted right away.
The previous code only checked `limit` when going down to a left
child, which is not wrong, but tests suggest that it is also very
common to reach this limit when going to a right child, so move the
test accordingly.
* src/itree.c (itree_insert_gap, itree_delete_gap): Check `limit` for
all nodes, rather than only when following a `left` pointer.
| -rw-r--r-- | src/itree.c | 10 |
1 files changed, 6 insertions, 4 deletions
diff --git a/src/itree.c b/src/itree.c index d73fbffd2b6..989173db4e5 100644 --- a/src/itree.c +++ b/src/itree.c @@ -1240,6 +1240,8 @@ itree_insert_gap (struct itree_tree *tree, { /* Process in pre-order. */ interval_tree_inherit_offset (tree->otick, node); + if (pos > node->limit) + continue; if (node->right != NULL) { if (node->begin > pos) @@ -1251,8 +1253,7 @@ itree_insert_gap (struct itree_tree *tree, else interval_stack_push (stack, node->right); } - if (node->left != NULL - && pos <= node->left->limit + node->left->offset) + if (node->left != NULL) interval_stack_push (stack, node->left); if (before_markers @@ -1312,6 +1313,8 @@ itree_delete_gap (struct itree_tree *tree, { node = nav_nodeptr (nav); interval_tree_inherit_offset (tree->otick, node); + if (pos > node->limit) + continue; if (node->right != NULL) { if (node->begin > pos + length) @@ -1323,8 +1326,7 @@ itree_delete_gap (struct itree_tree *tree, else interval_stack_push (stack, node->right); } - if (node->left != NULL - && pos <= node->left->limit + node->left->offset) + if (node->left != NULL) interval_stack_push (stack, node->left); if (pos < node->begin) |