master 35221a7bd5: (itree_insert_gap, itree_delete_gap): Minor optimization

[Stefan Monnier]

branch: master
commit 35221a7bd55e18244604376497097f4259c7351b
Author: Stefan Monnier <monnier@iro.umontreal.ca>
Commit: Stefan Monnier <monnier@iro.umontreal.ca>

    (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 d73fbffd2b..989173db4e 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)