From 35221a7bd55e18244604376497097f4259c7351b Mon Sep 17 00:00:00 2001 From: Stefan Monnier Date: Mon, 7 Nov 2022 00:38:43 -0500 Subject: [PATCH] (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. --- src/itree.c | 10 ++++++---- 1 file 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) -- 2.39.2