root/src/itree.c

DEFINITIONS

1. itree_stack_create
2. itree_stack_destroy
3. itree_stack_ensure_space
4. itree_stack_push
5. itree_stack_pop
6. itree_max_height
7. check_subtree
8. check_tree
9. null_safe_is_red
10. null_safe_is_black
11. itree_newlimit
12. itree_update_limit
13. itree_inherit_offset
14. itree_propagate_limit
15. itree_validate
16. itree_node_init
17. itree_node_begin
18. itree_node_end
19. itree_create
20. itree_clear
21. itree_init
22. itree_destroy
23. itree_size
24. itree_rotate_left
25. itree_rotate_right
26. itree_insert_fix
27. itree_insert_node
28. itree_insert
29. itree_node_set_region
30. itree_contains
31. itree_limit_is_stable
32. itree_subtree_min
33. itree_remove_fix
34. itree_total_offset
35. itree_replace_child
36. itree_transplant
37. itree_remove
38. itree_insert_gap
39. itree_delete_gap
40. itree_node_intersects
41. itree_iter_next_in_subtree
42. itree_iterator_first_node
43. itree_iterator_start
44. itree_iterator_next
45. itree_iterator_narrow

     1 /* This file implements an efficient interval data-structure.
     2 
     3 Copyright (C) 2017-2023 Free Software Foundation, Inc.
     4 
     5 This file is part of GNU Emacs.
     6 
     7 GNU Emacs is free software: you can redistribute it and/or modify
     8 it under the terms of the GNU General Public License as published by
     9 the Free Software Foundation, either version 3 of the License, or (at
    10 your option) any later version.
    11 
    12 GNU Emacs is distributed in the hope that it will be useful,
    13 but WITHOUT ANY WARRANTY; without even the implied warranty of
    14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    15 GNU General Public License for more details.
    16 
    17 You should have received a copy of the GNU General Public License
    18 along with GNU Emacs.  If not, see <https://www.gnu.org/licenses/>.  */
    19 
    20 #include <config.h>
    21 #include <math.h>
    22 
    23 #include "itree.h"
    24 
    25 /*
    26    Intervals of the form [BEGIN, END), are stored as nodes inside a RB
    27    tree, ordered by BEGIN.  The core operation of this tree (besides
    28    insert, remove, etc.) is finding all intervals intersecting with
    29    some given interval.  In order to perform this operation
    30    efficiently, every node stores a third value called LIMIT. (See
    31    https://en.wikipedia.org/wiki/Interval_tree#Augmented_tree and its
    32    source Introduction to Algorithms, Cormen et al. .)
    33 
    34    ==== Finding intervals ====
    35 
    36    If we search for all intervals intersecting with (X, Y], we look at
    37    some node and test whether
    38 
    39    NODE.BEGIN > Y
    40 
    41    Due to the invariant of the search tree, we know, that we may
    42    safely prune NODE's right subtree if this test succeeds, since all
    43    intervals begin strictly after Y.
    44 
    45    But we can not make such an assumptions about the left tree, since
    46    all we know is that the intervals in this subtree must start before
    47    or at NODE.BEGIN.  So we can't tell, whether they end before X or
    48    not.  To solve this problem we add another attribute to each node,
    49    called LIMIT.
    50 
    51    The LIMIT of a node is the largest END value occurring in the nodes
    52    subtree (including the node itself).  Thus, we may look at the left
    53    child of some NODE and test whether
    54 
    55    NODE.left.LIMIT < X
    56 
    57    and this tells us, if all intervals in the left subtree of NODE end
    58    before X and if they can be pruned.
    59 
    60    Conversely, if this inequality is false, the left subtree must
    61    contain at least one intersecting interval, giving a resulting time
    62    complexity of O(K*log(N)) for this operation, where K is the size
    63    of the result set and N the size of the tree.
    64 
    65    ==== FIXME: bug#58342 some important operations remain slow ===
    66 
    67    The amortized costs of Emacs' previous-overlay-change and
    68    next-overlay-change functions are O(N) with this data structure.
    69    The root problem is that we only have an order for the BEG field,
    70    but not the END.  The previous/next overlay change operations need
    71    to find the nearest point where there is *either* an interval BEG
    72    or END point, but there is no efficient way to narrow the search
    73    space over END positions.
    74 
    75    Consider the case where next-overlay-change is called at POS, all
    76    interval BEG positions are less than pos POS and all interval END
    77    posistions are after.  These END positions have no order, and so
    78    *every* interval must be examined.  This is at least O(N).  The
    79    previous-overlay-change case is similar.  The root issue is that
    80    the iterative "narrowing" approach is not guaranteed to reduce the
    81    search space in logarithmic time, since END is not ordered in the
    82    tree.
    83 
    84    One might argue that the LIMIT value will do this narrowing, but
    85    this narrowing is O(K*log(N)) where K is the size of the result
    86    set.  If we are interested in finding the node in a range with the
    87    smallest END, we might have to examine all K nodes in that range.
    88    In the case of the *-overlay-change functions, K may well be equal
    89    to N.
    90 
    91    Ideally, a tree based data structure for overlays would have
    92    O(log(N)) performance for previous-overlay-change and
    93    next-overlay-change, as these are called in performance sensitive
    94    situations such as redisplay.  The only way I can think of
    95    achieving this is by keeping one ordering by BEG and a separate
    96    ordering by END, and then performing logic quite similar to the
    97    current Emacs overlays-before and overlays-after lists.
    98 
    99    ==== Adjusting intervals ====
   100 
   101    Since this data-structure will be used for overlays in an Emacs
   102    buffer, a second core operation is the ability to insert and delete
   103    gaps in the tree.  This models the insertion and deletion of text
   104    in a buffer and the effects it may have on the positions of
   105    overlays.
   106 
   107    Consider this: Something gets inserted at position P into a buffer
   108    and assume that all overlays occur strictly after P.  Ordinarily,
   109    we would have to iterate all overlays and increment their BEGIN and
   110    END values accordingly (the insertion of text pushes them back).
   111    In order to avoid this, we introduce yet another node attribute,
   112    called OFFSET.
   113 
   114    The OFFSET of some subtree, represented by its root, is the
   115    amount of shift that needs to be applied to its BEGIN, END and
   116    LIMIT values, in order to get to the actual buffer positions.
   117    Coming back to the example, all we would need to do in this case,
   118    is to increment the OFFSET of the tree's root, without any
   119    traversal of the tree itself.
   120 
   121    As a consequence, the real values of BEGIN, END and LIMIT of some
   122    NODE need to be computed by incrementing them by the sum of NODE's
   123    OFFSET and all of its ancestors offsets.  Therefore, we store a
   124    counter (otick) inside every node and also the tree, by which we
   125    remember the fact, that a node's path to the root has no offsets
   126    applied (i.e. its values are up to date).  This is the case if some
   127    node's value differs from the tree's one, the later of which is
   128    incremented whenever some node's offset has changed.  */
   129 
   130 /* +=======================================================================+
   131  * | Stack
   132  * +=======================================================================+ */
   133 
   134 /* Simple dynamic array. */
   135 struct itree_stack
   136 {
   137   struct itree_node **nodes;
   138   size_t size;
   139   size_t length;
   140 };
   141 
   142 /* This is just a simple dynamic array with stack semantics. */
   143 
   144 static struct itree_stack*
   145 itree_stack_create (intmax_t initial_size)
   146 {
   147   struct itree_stack *stack = xmalloc (sizeof (struct itree_stack));
   148   stack->size = max (0, initial_size);
   149   stack->nodes = xmalloc (stack->size * sizeof (struct itree_node*));
   150   stack->length = 0;
   151   return stack;
   152 }
   153 
   154 static void
   155 itree_stack_destroy (struct itree_stack *stack)
   156 {
   157   if (! stack)
   158     return;
   159   if (stack->nodes)
   160     xfree (stack->nodes);
   161   xfree (stack);
   162 }
   163 
   164 static inline void
   165 itree_stack_ensure_space (struct itree_stack *stack, uintmax_t nelements)
   166 {
   167   if (nelements > stack->size)
   168     {
   169       stack->size = (nelements + 1) * 2;
   170       stack->nodes = xrealloc (stack->nodes,
   171                                stack->size * sizeof (*stack->nodes));
   172     }
   173 }
   174 
   175 /* Push NODE on the STACK, while settings its visited flag to FLAG. */
   176 
   177 static inline void
   178 itree_stack_push (struct itree_stack *stack, struct itree_node *node)
   179 {
   180   eassert (node);
   181   itree_stack_ensure_space (stack, stack->length + 1);
   182 
   183   stack->nodes[stack->length] = node;
   184   stack->length++;
   185 }
   186 
   187 static inline struct itree_node *
   188 itree_stack_pop (struct itree_stack *stack)
   189 {
   190   if (stack->length == 0)
   191     return NULL;
   192   return stack->nodes[--stack->length];
   193 }
   194 
   195 
   196 /* +-----------------------------------------------------------------------+ */
   197 
   198 static int
   199 itree_max_height (const struct itree_tree *tree)
   200 {
   201   return 2 * log (tree->size + 1) / log (2) + 0.5;
   202 }
   203 
   204 struct check_subtree_result
   205 {
   206   /* Node count of the tree.  */
   207   int size;
   208 
   209   /* Limit of the tree (max END).  */
   210   ptrdiff_t limit;
   211 
   212   /* Black height of the tree.  */
   213   int black_height;
   214 };
   215 
   216 static struct check_subtree_result
   217 check_subtree (struct itree_node *node,
   218                bool check_red_black_invariants, uintmax_t tree_otick,
   219                ptrdiff_t offset, ptrdiff_t min_begin,
   220                ptrdiff_t max_begin)
   221 {
   222   struct check_subtree_result result = { .size = 0,
   223                                          .limit = PTRDIFF_MIN,
   224                                          .black_height = 0 };
   225   if (node == NULL)
   226     return result;
   227 
   228   /* Validate structure.  */
   229   eassert (node->left == NULL || node->left->parent == node);
   230   eassert (node->right == NULL || node->right->parent == node);
   231 
   232   /* Validate otick.  A node's otick must be <= to the tree's otick
   233      and <= to its parent's otick.
   234 
   235      Note: we cannot assert that (NODE.otick == NODE.parent.otick)
   236      implies (NODE.offset == 0) because itree_inherit_offset()
   237      doesn't always update otick.  It could, but it is not clear there
   238      is a need.  */
   239   eassert (node->otick <= tree_otick);
   240   eassert (node->parent == NULL || node->otick <= node->parent->otick);
   241   eassert (node->otick != tree_otick || node->offset == 0);
   242 
   243   offset += node->offset;
   244   ptrdiff_t begin = node->begin + offset;
   245   ptrdiff_t end = node->end + offset;
   246   ptrdiff_t limit = node->limit + offset;
   247 
   248   eassert (min_begin <= max_begin);
   249   eassert (min_begin <= begin);
   250   eassert (begin <= max_begin);
   251   eassert (end <= limit);
   252 
   253   struct check_subtree_result left_result
   254     = check_subtree (node->left, check_red_black_invariants,
   255                      tree_otick, offset, min_begin, begin);
   256   struct check_subtree_result right_result
   257     = check_subtree (node->right, check_red_black_invariants,
   258                      tree_otick, offset, begin, max_begin);
   259 
   260   eassert (left_result.limit <= limit);
   261   eassert (right_result.limit <= limit);
   262   eassert (limit == max (end, max (left_result.limit, right_result.limit)));
   263 
   264   if (check_red_black_invariants)
   265     {
   266       eassert (left_result.black_height == right_result.black_height);
   267       eassert (node->parent == NULL || !node->red || !node->parent->red);
   268     }
   269 
   270   result.size = 1 + left_result.size + right_result.size;
   271   result.limit = limit;
   272   result.black_height = (node->red ? 0 : 1) + left_result.black_height;
   273   return result;
   274 }
   275 
   276 /* Validate invariants for TREE.  If CHECK_RED_BLACK_INVARIANTS, red
   277    nodes with red children are considered invalid.
   278 
   279    This runs in constant time when ENABLE_OVERLAY_CHECKING is 0
   280    (i.e. Emacs is not configured with
   281    "--enable_checking=yes,overlays").  In this mode it can't check all
   282    the invariants.  When ENABLE_OVERLAY_CHECKING is 1 it checks the
   283    entire tree and validates all invariants.
   284 */
   285 static bool
   286 check_tree (struct itree_tree *tree,
   287             bool check_red_black_invariants)
   288 {
   289   eassert (tree != NULL);
   290   eassert (tree->size >= 0);
   291   eassert ((tree->size == 0) == (tree->root == NULL));
   292   if (tree->root == NULL)
   293     return true;
   294   eassert (tree->root->parent == NULL);
   295   eassert (!check_red_black_invariants || !tree->root->red);
   296 
   297   struct itree_node *node = tree->root;
   298   struct check_subtree_result result
   299     = check_subtree (node, check_red_black_invariants, tree->otick,
   300                      node->offset, PTRDIFF_MIN,
   301                      PTRDIFF_MAX);
   302   eassert (result.size == tree->size);
   303 
   304   /* The only way this function fails is eassert().  */
   305   return true;
   306 }
   307 
   308 /* +=======================================================================+
   309  * | Internal Functions
   310  * +=======================================================================+ */
   311 
   312 static bool
   313 null_safe_is_red (struct itree_node *node)
   314 {
   315   return node != NULL && node->red;
   316 }
   317 
   318 static bool
   319 null_safe_is_black (struct itree_node *node)
   320 {
   321   return node == NULL || !node->red; /* NULL nodes are black */
   322 }
   323 
   324 static inline ptrdiff_t
   325 itree_newlimit (struct itree_node *node)
   326 {
   327   eassert (node != NULL);
   328   return max (node->end,
   329               max (node->left == NULL
   330                      ? PTRDIFF_MIN
   331                      : node->left->limit + node->left->offset,
   332                    node->right == NULL
   333                      ? PTRDIFF_MIN
   334                      : node->right->limit + node->right->offset));
   335 }
   336 
   337 /* Update NODE's limit attribute according to its children. */
   338 
   339 static void
   340 itree_update_limit (struct itree_node *node)
   341 {
   342   if (node == NULL)
   343     return;
   344 
   345   node->limit = itree_newlimit (node);
   346 }
   347 
   348 /* Apply NODE's offset to its begin, end and limit values and
   349    propagate it to its children.
   350 
   351    Does nothing, if NODE is clean, i.e. NODE.otick = tree.otick .
   352 */
   353 
   354 static void
   355 itree_inherit_offset (uintmax_t otick, struct itree_node *node)
   356 {
   357   eassert (node->parent == NULL || node->parent->otick >= node->otick);
   358   if (node->otick == otick)
   359     {
   360       eassert (node->offset == 0);
   361       return;
   362     }
   363 
   364   /* Offsets can be inherited from dirty nodes (with out of date
   365      otick) during removal, since we do not travel down from the root
   366      in that case.  In this case rotations are performed on
   367      potentially "dirty" nodes, where we only need to make sure the
   368      *local* offsets are zero.  */
   369 
   370   if (node->offset)
   371     {
   372       node->begin += node->offset;
   373       node->end   += node->offset;
   374       node->limit += node->offset;
   375       if (node->left != NULL)
   376         node->left->offset += node->offset;
   377       if (node->right != NULL)
   378         node->right->offset += node->offset;
   379       node->offset = 0;
   380     }
   381   /* The only thing that matters about `otick` is whether it's equal to
   382      that of the tree.  We could also "blindly" inherit from parent->otick,
   383      but we need to tree's `otick` anyway for when there's no parent.  */
   384   if (node->parent == NULL || node->parent->otick == otick)
   385     node->otick = otick;
   386 }
   387 
   388 /* Update limit of NODE and its ancestors.  Stop when it becomes
   389    stable, i.e. new_limit = old_limit.  */
   390 
   391 static void
   392 itree_propagate_limit (struct itree_node *node)
   393 {
   394   ptrdiff_t newlimit;
   395 
   396   if (node == NULL)
   397     return;
   398 
   399   while (1)
   400     {
   401       newlimit = itree_newlimit (node);
   402 
   403       if (newlimit == node->limit)
   404         break;
   405       node->limit = newlimit;
   406       if (node->parent == NULL)
   407         break;
   408       node = node->parent;
   409     }
   410 }
   411 
   412 static struct itree_node*
   413 itree_validate (struct itree_tree *tree, struct itree_node *node)
   414 {
   415 
   416   if (tree->otick == node->otick || node == NULL)
   417     return node;
   418   if (node != tree->root)
   419     itree_validate (tree, node->parent);
   420 
   421   itree_inherit_offset (tree->otick, node);
   422   return node;
   423 }
   424 
   425 /* +=======================================================================+
   426  * | Tree operations
   427  * +=======================================================================+ */
   428 
   429 /* Initialize an allocated node. */
   430 
   431 void
   432 itree_node_init (struct itree_node *node,
   433                  bool front_advance, bool rear_advance,
   434                  Lisp_Object data)
   435 {
   436   node->parent = NULL;
   437   node->left = NULL;
   438   node->right = NULL;
   439   node->begin = -1;
   440   node->end = -1;
   441   node->front_advance = front_advance;
   442   node->rear_advance = rear_advance;
   443   node->data = data;
   444 }
   445 
   446 /* Return NODE's begin value, computing it if necessary. */
   447 
   448 ptrdiff_t
   449 itree_node_begin (struct itree_tree *tree,
   450                   struct itree_node *node)
   451 {
   452   itree_validate (tree, node);
   453   return node->begin;
   454 }
   455 
   456 /* Return NODE's end value, computing it if necessary. */
   457 
   458 ptrdiff_t
   459 itree_node_end (struct itree_tree *tree,
   460                 struct itree_node *node)
   461 {
   462   itree_validate (tree, node);
   463   return node->end;
   464 }
   465 
   466 /* Allocate an itree_tree.  Free with itree_destroy.  */
   467 
   468 struct itree_tree *
   469 itree_create (void)
   470 {
   471   struct itree_tree *tree = xmalloc (sizeof (*tree));
   472   itree_clear (tree);
   473   return tree;
   474 }
   475 
   476 /* Reset the tree TREE to its empty state.  */
   477 
   478 void
   479 itree_clear (struct itree_tree *tree)
   480 {
   481   tree->root = NULL;
   482   tree->otick = 1;
   483   tree->size = 0;
   484 }
   485 
   486 #ifdef ITREE_TESTING
   487 /* Initialize a pre-allocated tree (presumably on the stack).  */
   488 
   489 static void
   490 itree_init (struct itree_tree *tree)
   491 {
   492   itree_clear (tree);
   493 }
   494 #endif
   495 
   496 /* Release a tree, freeing its allocated memory.  */
   497 void
   498 itree_destroy (struct itree_tree *tree)
   499 {
   500   eassert (tree->root == NULL);
   501   xfree (tree);
   502 }
   503 
   504 /* Return the number of nodes in TREE.  */
   505 
   506 intmax_t
   507 itree_size (struct itree_tree *tree)
   508 {
   509   return tree->size;
   510 }
   511 
   512 /* Perform the familiar left-rotation on node NODE.  */
   513 
   514 static void
   515 itree_rotate_left (struct itree_tree *tree,
   516                            struct itree_node *node)
   517 {
   518   eassert (node->right != NULL);
   519 
   520   struct itree_node *right = node->right;
   521 
   522   itree_inherit_offset (tree->otick, node);
   523   itree_inherit_offset (tree->otick, right);
   524 
   525   /* Turn right's left subtree into node's right subtree.  */
   526   node->right = right->left;
   527   if (right->left != NULL)
   528     right->left->parent = node;
   529 
   530   /* right's parent was node's parent.  */
   531   if (right != NULL)
   532     right->parent = node->parent;
   533 
   534   /* Get the parent to point to right instead of node.  */
   535   if (node != tree->root)
   536     {
   537       if (node == node->parent->left)
   538         node->parent->left = right;
   539       else
   540         node->parent->right = right;
   541     }
   542   else
   543     tree->root = right;
   544 
   545   /* Put node on right's left.  */
   546   right->left = node;
   547   if (node != NULL)
   548     node->parent = right;
   549 
   550   /* Order matters here.  */
   551   itree_update_limit (node);
   552   itree_update_limit (right);
   553 }
   554 
   555 /* Perform the familiar right-rotation on node NODE.  */
   556 
   557 static void
   558 itree_rotate_right (struct itree_tree *tree,
   559                             struct itree_node *node)
   560 {
   561   eassert (tree && node && node->left != NULL);
   562 
   563   struct itree_node *left = node->left;
   564 
   565   itree_inherit_offset (tree->otick, node);
   566   itree_inherit_offset (tree->otick, left);
   567 
   568   node->left = left->right;
   569   if (left->right != NULL)
   570     left->right->parent = node;
   571 
   572   if (left != NULL)
   573     left->parent = node->parent;
   574   if (node != tree->root)
   575     {
   576       if (node == node->parent->right)
   577         node->parent->right = left;
   578       else
   579         node->parent->left = left;
   580     }
   581   else
   582     tree->root = left;
   583 
   584   left->right = node;
   585   if (node != NULL)
   586     node->parent = left;
   587 
   588   itree_update_limit (left);
   589   itree_update_limit (node);
   590 }
   591 
   592 /* Repair the tree after an insertion.
   593    The new NODE was added as red, so we may have 2 reds in a row.
   594    Rebalance the parents as needed to re-establish the RB invariants.  */
   595 
   596 static void
   597 itree_insert_fix (struct itree_tree *tree,
   598                           struct itree_node *node)
   599 {
   600   eassert (tree->root->red == false);
   601 
   602   while (null_safe_is_red (node->parent))
   603     {
   604       /* NODE is red and its parent is red.  This is a violation of
   605          red-black tree property #3.  */
   606       eassert (node->red);
   607 
   608       if (node->parent == node->parent->parent->left)
   609         {
   610           /* We're on the left side of our grandparent, and OTHER is
   611              our "uncle".  */
   612           struct itree_node *uncle = node->parent->parent->right;
   613 
   614           if (null_safe_is_red (uncle)) /* case 1.a */
   615             {
   616               /* Uncle and parent are red but should be black because
   617                  NODE is red.  Change the colors accordingly and
   618                  proceed with the grandparent.  */
   619               node->parent->red = false;
   620               uncle->red = false;
   621               node->parent->parent->red = true;
   622               node = node->parent->parent;
   623             }
   624           else
   625             {
   626               /* Parent and uncle have different colors; parent is
   627                  red, uncle is black.  */
   628               if (node == node->parent->right) /* case 2.a */
   629                 {
   630                   node = node->parent;
   631                   itree_rotate_left (tree, node);
   632                 }
   633               /* case 3.a */
   634               node->parent->red = false;
   635               node->parent->parent->red = true;
   636               itree_rotate_right (tree, node->parent->parent);
   637             }
   638         }
   639       else
   640         {
   641           /* This is the symmetrical case of above.  */
   642           struct itree_node *uncle = node->parent->parent->left;
   643 
   644           if (null_safe_is_red (uncle)) /* case 1.b */
   645             {
   646               node->parent->red = false;
   647               uncle->red = false;
   648               node->parent->parent->red = true;
   649               node = node->parent->parent;
   650             }
   651           else
   652             {
   653               if (node == node->parent->left) /* case 2.b */
   654                 {
   655                   node = node->parent;
   656                   itree_rotate_right (tree, node);
   657                 }
   658               /* case 3.b */
   659               node->parent->red = false;
   660               node->parent->parent->red = true;
   661               itree_rotate_left (tree, node->parent->parent);
   662             }
   663         }
   664     }
   665 
   666   /* The root may have been changed to red due to the algorithm.
   667      Set it to black so that property #5 is satisfied.  */
   668   tree->root->red = false;
   669   eassert (check_tree (tree, true)); /* FIXME: Too expensive.  */
   670 }
   671 
   672 /* Insert a NODE into the TREE.
   673    Note, that inserting a node twice results in undefined behavior.  */
   674 
   675 static void
   676 itree_insert_node (struct itree_tree *tree, struct itree_node *node)
   677 {
   678   eassert (node && node->begin <= node->end);
   679   eassert (node->left == NULL && node->right == NULL
   680            && node->parent == NULL);
   681   eassert (check_tree (tree, true)); /* FIXME: Too expensive.  */
   682 
   683   struct itree_node *parent = NULL;
   684   struct itree_node *child = tree->root;
   685   uintmax_t otick = tree->otick;
   686   /* It's the responsibility of the caller to set `otick` on the node,
   687      to "confirm" that the begin/end fields are up to date.  */
   688   eassert (node->otick == otick);
   689 
   690   /* Find the insertion point, accumulate node's offset and update
   691      ancestors limit values.  */
   692   while (child != NULL)
   693     {
   694       itree_inherit_offset (otick, child);
   695       parent = child;
   696       eassert (child->offset == 0);
   697       child->limit = max (child->limit, node->end);
   698       /* This suggests that nodes in the right subtree are strictly
   699          greater.  But this is not true due to later rotations.  */
   700       child = node->begin <= child->begin ? child->left : child->right;
   701     }
   702 
   703   /* Insert the node */
   704   if (parent == NULL)
   705     tree->root = node;
   706   else if (node->begin <= parent->begin)
   707     parent->left = node;
   708   else
   709     parent->right = node;
   710 
   711   /* Init the node */
   712   node->parent = parent;
   713   node->left = NULL;
   714   node->right = NULL;
   715   node->offset = 0;
   716   node->limit = node->end;
   717   eassert (node->parent == NULL || node->parent->otick >= node->otick);
   718 
   719   /* Fix/update the tree */
   720   ++tree->size;
   721   if (node == tree->root)
   722     node->red = false;
   723   else
   724     {
   725       node->red = true;
   726       eassert (check_tree (tree, false)); /* FIXME: Too expensive.  */
   727       itree_insert_fix (tree, node);
   728     }
   729 }
   730 
   731 void
   732 itree_insert (struct itree_tree *tree, struct itree_node *node,
   733               ptrdiff_t begin, ptrdiff_t end)
   734 {
   735   node->begin = begin;
   736   node->end = end;
   737   node->otick = tree->otick;
   738   itree_insert_node (tree, node);
   739 }
   740 
   741 /* Safely modify a node's interval. */
   742 
   743 void
   744 itree_node_set_region (struct itree_tree *tree,
   745                        struct itree_node *node,
   746                        ptrdiff_t begin, ptrdiff_t end)
   747 {
   748   itree_validate (tree, node);
   749   if (begin != node->begin)
   750     {
   751       itree_remove (tree, node);
   752       node->begin = min (begin, PTRDIFF_MAX - 1);
   753       node->end = max (node->begin, end);
   754       itree_insert_node (tree, node);
   755     }
   756   else if (end != node->end)
   757     {
   758       node->end = max (node->begin, end);
   759       eassert (node != NULL);
   760       itree_propagate_limit (node);
   761     }
   762 }
   763 
   764 /* Return true, if NODE is a member of TREE. */
   765 
   766 static bool
   767 itree_contains (struct itree_tree *tree, struct itree_node *node)
   768 {
   769   eassert (node);
   770   struct itree_node *other;
   771   ITREE_FOREACH (other, tree, node->begin, PTRDIFF_MAX, ASCENDING)
   772     if (other == node)
   773       return true;
   774 
   775   return false;
   776 }
   777 
   778 static bool
   779 itree_limit_is_stable (struct itree_node *node)
   780 {
   781   if (node == NULL)
   782     return true;
   783   ptrdiff_t newlimit = itree_newlimit (node);
   784   return (newlimit == node->limit);
   785 }
   786 
   787 static struct itree_node*
   788 itree_subtree_min (uintmax_t otick, struct itree_node *node)
   789 {
   790   if (node == NULL)
   791     return node;
   792   while ((itree_inherit_offset (otick, node),
   793           node->left != NULL))
   794     node = node->left;
   795   return node;
   796 }
   797 
   798 /* Repair the tree after a deletion.
   799    The black-depth of NODE is one less than that of its sibling,
   800    so re-balance the parents to re-establish the RB invariants.  */
   801 
   802 static void
   803 itree_remove_fix (struct itree_tree *tree,
   804                           struct itree_node *node,
   805                           struct itree_node *parent)
   806 {
   807   if (parent == NULL)
   808     eassert (node == tree->root);
   809   else
   810     eassert (node == NULL || node->parent == parent);
   811 
   812   while (parent != NULL && null_safe_is_black (node))
   813     {
   814       eassert (node == parent->left || node == parent->right);
   815 
   816       if (node == parent->left)
   817         {
   818           struct itree_node *other = parent->right;
   819 
   820           if (null_safe_is_red (other)) /* case 1.a */
   821             {
   822               other->red = false;
   823               parent->red = true;
   824               itree_rotate_left (tree, parent);
   825               other = parent->right;
   826             }
   827           eassume (other != NULL);
   828 
   829           if (null_safe_is_black (other->left) /* 2.a */
   830               && null_safe_is_black (other->right))
   831             {
   832               other->red = true;
   833               node = parent;
   834               eassert (node != NULL);
   835               parent = node->parent;
   836             }
   837           else
   838             {
   839               if (null_safe_is_black (other->right)) /* 3.a */
   840                 {
   841                   other->left->red = false;
   842                   other->red = true;
   843                   itree_rotate_right (tree, other);
   844                   other = parent->right;
   845                 }
   846               other->red = parent->red; /* 4.a */
   847               parent->red = false;
   848               other->right->red = false;
   849               itree_rotate_left (tree, parent);
   850               node = tree->root;
   851               parent = NULL;
   852             }
   853         }
   854       else
   855         {
   856           struct itree_node *other = parent->left;
   857 
   858           if (null_safe_is_red (other)) /* 1.b */
   859             {
   860               other->red = false;
   861               parent->red = true;
   862               itree_rotate_right (tree, parent);
   863               other = parent->left;
   864             }
   865           eassume (other != NULL);
   866 
   867           if (null_safe_is_black (other->right) /* 2.b */
   868               && null_safe_is_black (other->left))
   869             {
   870               other->red = true;
   871               node = parent;
   872               eassert (node != NULL);
   873               parent = node->parent;
   874             }
   875           else
   876             {
   877               if (null_safe_is_black (other->left)) /* 3.b */
   878                 {
   879                   other->right->red = false;
   880                   other->red = true;
   881                   itree_rotate_left (tree, other);
   882                   other = parent->left;
   883                 }
   884 
   885               other->red = parent->red; /* 4.b */
   886               parent->red = false;
   887               other->left->red = false;
   888               itree_rotate_right (tree, parent);
   889               node = tree->root;
   890               parent = NULL;
   891             }
   892         }
   893     }
   894 
   895   if (node != NULL)
   896     node->red = false;
   897 }
   898 
   899 /* Return accumulated offsets of NODE's parents.  */
   900 static ptrdiff_t
   901 itree_total_offset (struct itree_node *node)
   902 {
   903   eassert (node != NULL);
   904   ptrdiff_t offset = 0;
   905   while (node->parent != NULL)
   906     {
   907       node = node->parent;
   908       offset += node->offset;
   909     }
   910   return offset;
   911 }
   912 
   913 /* Replace DEST with SOURCE as a child of DEST's parent.  Adjusts
   914    *only* the parent linkage of SOURCE and either the parent's child
   915    link the tree root.
   916 
   917    Warning: DEST is left unmodified.  SOURCE's child links are
   918    unchanged.  Caller is responsible for recalculation of `limit`.
   919    Requires both nodes to be using the same effective `offset`.  */
   920 static void
   921 itree_replace_child (struct itree_tree *tree,
   922                              struct itree_node *source,
   923                              struct itree_node *dest)
   924 {
   925   eassert (tree && dest != NULL);
   926   eassert (source == NULL
   927            || itree_total_offset (source) == itree_total_offset (dest));
   928 
   929   if (dest == tree->root)
   930     tree->root = source;
   931   else if (dest == dest->parent->left)
   932     dest->parent->left = source;
   933   else
   934     dest->parent->right = source;
   935 
   936   if (source != NULL)
   937     source->parent = dest->parent;
   938 }
   939 /* Replace DEST with SOURCE in the tree.  Copies the following fields
   940    from DEST to SOURCE: red, parent, left, right.  Also updates
   941    parent, left and right in surrounding nodes to point to SOURCE.
   942 
   943    Warning: DEST is left unmodified.  Caller is responsible for
   944    recalculation of `limit`.  Requires both nodes to be using the same
   945    effective `offset`. */
   946 static void
   947 itree_transplant (struct itree_tree *tree,
   948                           struct itree_node *source,
   949                           struct itree_node *dest)
   950 {
   951   itree_replace_child (tree, source, dest);
   952   source->left = dest->left;
   953   if (source->left != NULL)
   954     source->left->parent = source;
   955   source->right = dest->right;
   956   if (source->right != NULL)
   957     source->right->parent = source;
   958   source->red = dest->red;
   959 }
   960 
   961 /* Remove NODE from TREE and return it.  NODE must exist in TREE.  */
   962 
   963 struct itree_node*
   964 itree_remove (struct itree_tree *tree, struct itree_node *node)
   965 {
   966   eassert (itree_contains (tree, node));
   967   eassert (check_tree (tree, true)); /* FIXME: Too expensive.  */
   968 
   969   /* Find `splice`, the leaf node to splice out of the tree.  When
   970      `node` has at most one child this is `node` itself.  Otherwise,
   971      it is the in order successor of `node`.  */
   972   itree_inherit_offset (tree->otick, node);
   973   struct itree_node *splice
   974     = (node->left == NULL || node->right == NULL)
   975         ? node
   976         : itree_subtree_min (tree->otick, node->right);
   977 
   978   /* Find `subtree`, the only child of `splice` (may be NULL).  Note:
   979      `subtree` will not be modified other than changing its parent to
   980      `splice`.  */
   981   eassert (splice->left == NULL || splice->right == NULL);
   982   struct itree_node *subtree
   983     = (splice->left != NULL) ? splice->left : splice->right;
   984 
   985   /* Save a pointer to the parent of where `subtree` will eventually
   986      be in `subtree_parent`.  */
   987   struct itree_node *subtree_parent
   988     = (splice->parent != node) ? splice->parent : splice;
   989 
   990   /* If `splice` is black removing it may violate Red-Black
   991      invariants, so note this for later.  */
   992 
   993   /* Replace `splice` with `subtree` under subtree's parent.  If
   994      `splice` is black, this creates a red-red violation, so remember
   995      this now as the field can be overwritten when splice is
   996      transplanted below.  */
   997   itree_replace_child (tree, subtree, splice);
   998   bool removed_black = !splice->red;
   999 
  1000   /* Replace `node` with `splice` in the tree and propagate limit
  1001      upwards, if necessary.  Note: Limit propagation can stabilize at
  1002      any point, so we must call from bottom to top for every node that
  1003      has a new child.  */
  1004   if (splice != node)
  1005     {
  1006       itree_transplant (tree, splice, node);
  1007       itree_propagate_limit (subtree_parent);
  1008       if (splice != subtree_parent)
  1009         itree_update_limit (splice);
  1010     }
  1011   itree_propagate_limit (splice->parent);
  1012 
  1013   --tree->size;
  1014 
  1015   /* Fix any black height violation caused by removing a black node.  */
  1016   if (removed_black)
  1017     itree_remove_fix (tree, subtree, subtree_parent);
  1018 
  1019   eassert ((tree->size == 0) == (tree->root == NULL));
  1020   eassert (check_tree (tree, true)); /* FIXME: Too expensive.  */
  1021 
  1022   /* Clear fields related to the tree for sanity while debugging.  */
  1023   node->red = false;
  1024   node->right = node->left = node->parent = NULL;
  1025   node->limit = 0;
  1026 
  1027   /* Must be clean (all offsets applied).  Also, some callers rely on
  1028      node's otick being the tree's otick.  */
  1029   eassert (node->otick == tree->otick);
  1030   eassert (node->offset == 0);
  1031 
  1032   return node;
  1033 }
  1034 
  1035 
  1036 /* +=======================================================================+
  1037  * | Insert/Delete Gaps
  1038  * +=======================================================================+ */
  1039 
  1040 /* Insert a gap at POS of length LENGTH expanding all intervals
  1041    intersecting it, while respecting their rear_advance and
  1042    front_advance setting.
  1043 
  1044    If BEFORE_MARKERS is non-zero, all overlays beginning/ending at POS
  1045    are treated as if their front_advance/rear_advance was true. */
  1046 
  1047 void
  1048 itree_insert_gap (struct itree_tree *tree,
  1049                   ptrdiff_t pos, ptrdiff_t length, bool before_markers)
  1050 {
  1051   if (!tree || length <= 0 || tree->root == NULL)
  1052     return;
  1053   uintmax_t ootick = tree->otick;
  1054 
  1055   /* FIXME: Don't allocate iterator/stack anew every time. */
  1056 
  1057   /* Nodes with front_advance starting at pos may mess up the tree
  1058      order, so we need to remove them first.  This doesn't apply for
  1059      `before_markers` since in that case, all positions move identically
  1060      regardless of `front_advance` or `rear_advance`.  */
  1061   struct itree_stack *saved = itree_stack_create (0);
  1062   struct itree_node *node = NULL;
  1063   if (!before_markers)
  1064     {
  1065       /* Actually any order would do.  */
  1066       ITREE_FOREACH (node, tree, pos, pos + 1, PRE_ORDER)
  1067         {
  1068           if (node->begin == pos && node->front_advance
  1069               /* If we have front_advance and !rear_advance and
  1070                  the overlay is empty, make sure we don't move
  1071                  begin past end by pretending it's !front_advance.  */
  1072               && (node->begin != node->end || node->rear_advance))
  1073             itree_stack_push (saved, node);
  1074         }
  1075     }
  1076   for (size_t i = 0; i < saved->length; ++i)
  1077     itree_remove (tree, saved->nodes[i]);
  1078 
  1079   /* We can't use an iterator here, because we can't effectively
  1080      narrow AND shift some subtree at the same time.  */
  1081   if (tree->root != NULL)
  1082     {
  1083       const int size = itree_max_height (tree) + 1;
  1084       struct itree_stack *stack = itree_stack_create (size);
  1085       itree_stack_push (stack, tree->root);
  1086       while ((node = itree_stack_pop (stack)))
  1087         {
  1088           /* Process in pre-order. */
  1089           itree_inherit_offset (tree->otick, node);
  1090           if (pos > node->limit)
  1091             continue;
  1092           if (node->right != NULL)
  1093             {
  1094               if (node->begin > pos)
  1095                 {
  1096                   /* All nodes in this subtree are shifted by length.  */
  1097                   node->right->offset += length;
  1098                   ++tree->otick;
  1099                 }
  1100               else
  1101                 itree_stack_push (stack, node->right);
  1102             }
  1103           if (node->left != NULL)
  1104             itree_stack_push (stack, node->left);
  1105 
  1106           if (before_markers
  1107               ? node->begin >= pos
  1108               : node->begin > pos) /* node->begin == pos => !front-advance  */
  1109             node->begin += length;
  1110           if (node->end > pos
  1111               || (node->end == pos && (before_markers || node->rear_advance)))
  1112             {
  1113               node->end += length;
  1114               eassert (node != NULL);
  1115               itree_propagate_limit (node);
  1116             }
  1117         }
  1118       itree_stack_destroy (stack);
  1119     }
  1120 
  1121   /* Reinsert nodes starting at POS having front-advance.  */
  1122   uintmax_t notick = tree->otick;
  1123   while ((node = itree_stack_pop (saved)))
  1124     {
  1125       eassert (node->otick == ootick);
  1126       eassert (node->begin == pos);
  1127       eassert (node->end > pos || node->rear_advance);
  1128       node->begin += length;
  1129       node->end += length;
  1130       node->otick = notick;
  1131       itree_insert_node (tree, node);
  1132     }
  1133 
  1134   itree_stack_destroy (saved);
  1135 }
  1136 
  1137 /* Delete a gap at POS of length LENGTH, contracting all intervals
  1138    intersecting it.  */
  1139 
  1140 void
  1141 itree_delete_gap (struct itree_tree *tree,
  1142                   ptrdiff_t pos, ptrdiff_t length)
  1143 {
  1144   if (!tree || length <= 0 || tree->root == NULL)
  1145     return;
  1146 
  1147   /* FIXME: Don't allocate stack anew every time.  */
  1148 
  1149   /* Can't use the iterator here, because by decrementing begin, we
  1150      might unintentionally bring shifted nodes back into our search space.  */
  1151   const int size = itree_max_height (tree) + 1;
  1152   struct itree_stack *stack = itree_stack_create (size);
  1153   struct itree_node *node;
  1154 
  1155   itree_stack_push (stack, tree->root);
  1156   while ((node = itree_stack_pop (stack)))
  1157     {
  1158       itree_inherit_offset (tree->otick, node);
  1159       if (pos > node->limit)
  1160         continue;
  1161       if (node->right != NULL)
  1162         {
  1163           if (node->begin > pos + length)
  1164             {
  1165               /* Shift right subtree to the left. */
  1166               node->right->offset -= length;
  1167               ++tree->otick;
  1168             }
  1169           else
  1170             itree_stack_push (stack, node->right);
  1171         }
  1172       if (node->left != NULL)
  1173         itree_stack_push (stack, node->left);
  1174 
  1175       if (pos < node->begin)
  1176         node->begin = max (pos, node->begin - length);
  1177       if (node->end > pos)
  1178         {
  1179           node->end = max (pos , node->end - length);
  1180           eassert (node != NULL);
  1181           itree_propagate_limit (node);
  1182         }
  1183     }
  1184   itree_stack_destroy (stack);
  1185 }
  1186 
  1187 
  1188 
  1189 /* +=======================================================================+
  1190  * | Iterator
  1191  * +=======================================================================+ */
  1192 
  1193 /* Return true, if NODE's interval intersects with [BEGIN, END).
  1194    Note: We always include empty nodes at BEGIN (and not at END),
  1195    but if BEGIN==END, then we don't include non-empty nodes starting
  1196    at BEGIN or ending at END.  This seems to match the behavior of the
  1197    old overlays code but it's not clear if it's The Right Thing
  1198    (e.g. it breaks the expectation that if NODE1 is included, then
  1199    a NODE2 strictly bigger than NODE1 should also be included).  */
  1200 
  1201 static inline bool
  1202 itree_node_intersects (const struct itree_node *node,
  1203                        ptrdiff_t begin, ptrdiff_t end)
  1204 {
  1205   return (begin < node->end && node->begin < end)
  1206     || (node->begin == node->end && begin == node->begin);
  1207 }
  1208 
  1209 /* Return the "next" node in the current traversal order.
  1210 
  1211    Note that this should return all the nodes that we need to traverse
  1212    in order to traverse the nodes selected by the current narrowing (i.e.
  1213    `ITER->begin..ITER->end`) so it will also return some nodes which aren't in
  1214    that narrowing simply because they may have children which are.
  1215 
  1216    The code itself is very unsatifactory because the code of each one
  1217    of the supported traversals seems completely different from the others.
  1218    If someone knows how to make it more uniform and "obviously correct",
  1219    please make yourself heard.  */
  1220 
  1221 static struct itree_node *
  1222 itree_iter_next_in_subtree (struct itree_node *node,
  1223                             struct itree_iterator *iter)
  1224 {
  1225   /* FIXME: Like in the previous version of the iterator, we
  1226      prune based on `limit` only when moving to a left child,
  1227      but `limit` can also get smaller when moving to a right child
  1228      It's actually fairly common, so maybe it would be worthwhile
  1229      to prune a bit more aggressively here.  */
  1230   struct itree_node *next;
  1231   switch (iter->order)
  1232     {
  1233     case ITREE_ASCENDING:
  1234       next = node->right;
  1235       if (!next)
  1236         {
  1237           while ((next = node->parent)
  1238                  && next->right == node)
  1239             node = next;
  1240           if (!next)
  1241             return NULL;   /* No more nodes to visit. */
  1242           node = next;
  1243         }
  1244       else
  1245         {
  1246           node = next;
  1247           itree_inherit_offset (iter->otick, node);
  1248           while ((next = node->left)
  1249                  && (itree_inherit_offset (iter->otick, next),
  1250                      iter->begin <= next->limit))
  1251             node = next;
  1252         }
  1253       if (node->begin > iter->end)
  1254         return NULL;  /* No more nodes within begin..end.  */
  1255       return node;
  1256 
  1257     case ITREE_DESCENDING:
  1258       next = node->left;
  1259       if (!next
  1260           || (itree_inherit_offset (iter->otick, next),
  1261               next->limit < iter->begin))
  1262         {
  1263           while ((next = node->parent)
  1264                  && next->left == node)
  1265             node = next;
  1266           if (!next)
  1267             return NULL;   /* No more nodes to visit. */
  1268           node = next;
  1269         }
  1270       else
  1271         {
  1272           node = next;
  1273           while (node->begin <= iter->end
  1274                  && (next = node->right))
  1275             {
  1276               itree_inherit_offset (iter->otick, next),
  1277               node = next;
  1278             }
  1279         }
  1280       return node;
  1281 
  1282     case ITREE_PRE_ORDER:
  1283       next = node->left;
  1284       if (next
  1285           && (itree_inherit_offset (iter->otick, next),
  1286               !(next->limit < iter->begin)))
  1287         return next;
  1288       next = node->right;
  1289       if (node->begin <= iter->end && next)
  1290         {
  1291           itree_inherit_offset (iter->otick, next);
  1292           return next;
  1293         }
  1294       while ((next = node->parent))
  1295         {
  1296           if (next->right == node)
  1297             node = next;
  1298           else
  1299             {
  1300               eassert (next->left == node);
  1301               node = next;
  1302               next = node->right;
  1303               if (node->begin <= iter->end && next)
  1304                 {
  1305                   itree_inherit_offset (iter->otick, next);
  1306                   return next;
  1307                 }
  1308             }
  1309           }
  1310       return NULL;
  1311 
  1312     case ITREE_POST_ORDER:
  1313       next = node->parent;
  1314       if (!next || next->right == node)
  1315         return next;
  1316       eassert (next->left == node);
  1317       node = next;
  1318       next = node->right;
  1319       if (!(node->begin <= iter->end && next))
  1320         return node;
  1321       node = next;
  1322       itree_inherit_offset (iter->otick, node);
  1323       while (((next = node->left)
  1324               && (itree_inherit_offset (iter->otick, next),
  1325                   iter->begin <= next->limit))
  1326              || (node->begin <= iter->end
  1327                  && (next = node->right)
  1328                  && (itree_inherit_offset (iter->otick, next), true)))
  1329         node = next;
  1330       return node;
  1331 
  1332     default:
  1333     emacs_abort ();
  1334     }
  1335 }
  1336 
  1337 static struct itree_node *
  1338 itree_iterator_first_node (struct itree_tree *tree,
  1339                            struct itree_iterator *iter)
  1340 {
  1341   struct itree_node *node = tree->root;
  1342   if (node)
  1343     {
  1344       struct itree_node dummy;
  1345       dummy.left = NULL;
  1346       dummy.parent = NULL;
  1347       dummy.right = NULL;
  1348       itree_inherit_offset (iter->otick, node);
  1349       switch (iter->order)
  1350         {
  1351         case ITREE_ASCENDING:
  1352           dummy.right = node;
  1353           dummy.begin = PTRDIFF_MIN;
  1354           node = itree_iter_next_in_subtree (&dummy, iter);
  1355           break;
  1356 
  1357         case ITREE_DESCENDING:
  1358           dummy.left = node;
  1359           node = itree_iter_next_in_subtree (&dummy, iter);
  1360           break;
  1361 
  1362         case ITREE_PRE_ORDER:
  1363           break;
  1364 
  1365         case ITREE_POST_ORDER:
  1366           dummy.parent = &dummy;
  1367           dummy.left = &dummy;
  1368           dummy.right = node;
  1369           dummy.begin = PTRDIFF_MIN;
  1370           node = itree_iter_next_in_subtree (&dummy, iter);
  1371           break;
  1372         default:
  1373           emacs_abort ();
  1374         }
  1375     }
  1376   return node;
  1377 }
  1378 
  1379 /* Start a iterator enumerating all intervals in [BEGIN,END) in the
  1380    given ORDER.  */
  1381 
  1382 struct itree_iterator *
  1383 itree_iterator_start (struct itree_iterator *iter,
  1384                       struct itree_tree *tree,
  1385                       ptrdiff_t begin, ptrdiff_t end, enum itree_order order)
  1386 {
  1387   eassert (iter);
  1388   iter->begin = begin;
  1389   iter->end = end;
  1390   iter->otick = tree->otick;
  1391   iter->order = order;
  1392   /* Beware: the `node` field always holds "the next" node to consider.
  1393      so it's always "one node ahead" of what the iterator loop sees.
  1394      In most respects this makes no difference, but we depend on this
  1395      detail in `delete_all_overlays` where this allows us to modify
  1396      the current node knowing that the iterator will not need it to
  1397      find the next.  */
  1398   iter->node = itree_iterator_first_node (tree, iter);
  1399   return iter;
  1400 }
  1401 
  1402 struct itree_node *
  1403 itree_iterator_next (struct itree_iterator *iter)
  1404 {
  1405   struct itree_node *node = iter->node;
  1406   while (node
  1407          && !itree_node_intersects (node, iter->begin, iter->end))
  1408     {
  1409       node = itree_iter_next_in_subtree (node, iter);
  1410       eassert (itree_limit_is_stable (node));
  1411     }
  1412   iter->node = node ? itree_iter_next_in_subtree (node, iter) : NULL;
  1413   return node;
  1414 }
  1415 
  1416 /* Limit G to the new interval [BEGIN, END), which must be a subset of
  1417    the current one.  I.E. it can't grow on either side. */
  1418 
  1419 void
  1420 itree_iterator_narrow (struct itree_iterator *g,
  1421                        ptrdiff_t begin, ptrdiff_t end)
  1422 {
  1423   eassert (g);
  1424   eassert (begin >= g->begin);
  1425   eassert (end <= g->end);
  1426   g->begin = max (begin, g->begin);
  1427   g->end = min (end, g->end);
  1428 }