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 (other->red) /* case 1.a */
   821             {
   822               other->red = false;
   823               parent->red = true;
   824               itree_rotate_left (tree, parent);
   825               other = parent->right;
   826             }
   827 
   828           if (null_safe_is_black (other->left) /* 2.a */
   829               && null_safe_is_black (other->right))
   830             {
   831               other->red = true;
   832               node = parent;
   833               eassert (node != NULL);
   834               parent = node->parent;
   835             }
   836           else
   837             {
   838               if (null_safe_is_black (other->right)) /* 3.a */
   839                 {
   840                   other->left->red = false;
   841                   other->red = true;
   842                   itree_rotate_right (tree, other);
   843                   other = parent->right;
   844                 }
   845               other->red = parent->red; /* 4.a */
   846               parent->red = false;
   847               other->right->red = false;
   848               itree_rotate_left (tree, parent);
   849               node = tree->root;
   850               parent = NULL;
   851             }
   852         }
   853       else
   854         {
   855           struct itree_node *other = parent->left;
   856 
   857           if (other->red) /* 1.b */
   858             {
   859               other->red = false;
   860               parent->red = true;
   861               itree_rotate_right (tree, parent);
   862               other = parent->left;
   863             }
   864 
   865           if (null_safe_is_black (other->right) /* 2.b */
   866               && null_safe_is_black (other->left))
   867             {
   868               other->red = true;
   869               node = parent;
   870               eassert (node != NULL);
   871               parent = node->parent;
   872             }
   873           else
   874             {
   875               if (null_safe_is_black (other->left)) /* 3.b */
   876                 {
   877                   other->right->red = false;
   878                   other->red = true;
   879                   itree_rotate_left (tree, other);
   880                   other = parent->left;
   881                 }
   882 
   883               other->red = parent->red; /* 4.b */
   884               parent->red = false;
   885               other->left->red = false;
   886               itree_rotate_right (tree, parent);
   887               node = tree->root;
   888               parent = NULL;
   889             }
   890         }
   891     }
   892 
   893   if (node != NULL)
   894     node->red = false;
   895 }
   896 
   897 /* Return accumulated offsets of NODE's parents.  */
   898 static ptrdiff_t
   899 itree_total_offset (struct itree_node *node)
   900 {
   901   eassert (node != NULL);
   902   ptrdiff_t offset = 0;
   903   while (node->parent != NULL)
   904     {
   905       node = node->parent;
   906       offset += node->offset;
   907     }
   908   return offset;
   909 }
   910 
   911 /* Replace DEST with SOURCE as a child of DEST's parent.  Adjusts
   912    *only* the parent linkage of SOURCE and either the parent's child
   913    link the tree root.
   914 
   915    Warning: DEST is left unmodified.  SOURCE's child links are
   916    unchanged.  Caller is responsible for recalculation of `limit`.
   917    Requires both nodes to be using the same effective `offset`.  */
   918 static void
   919 itree_replace_child (struct itree_tree *tree,
   920                              struct itree_node *source,
   921                              struct itree_node *dest)
   922 {
   923   eassert (tree && dest != NULL);
   924   eassert (source == NULL
   925            || itree_total_offset (source) == itree_total_offset (dest));
   926 
   927   if (dest == tree->root)
   928     tree->root = source;
   929   else if (dest == dest->parent->left)
   930     dest->parent->left = source;
   931   else
   932     dest->parent->right = source;
   933 
   934   if (source != NULL)
   935     source->parent = dest->parent;
   936 }
   937 /* Replace DEST with SOURCE in the tree.  Copies the following fields
   938    from DEST to SOURCE: red, parent, left, right.  Also updates
   939    parent, left and right in surrounding nodes to point to SOURCE.
   940 
   941    Warning: DEST is left unmodified.  Caller is responsible for
   942    recalculation of `limit`.  Requires both nodes to be using the same
   943    effective `offset`. */
   944 static void
   945 itree_transplant (struct itree_tree *tree,
   946                           struct itree_node *source,
   947                           struct itree_node *dest)
   948 {
   949   itree_replace_child (tree, source, dest);
   950   source->left = dest->left;
   951   if (source->left != NULL)
   952     source->left->parent = source;
   953   source->right = dest->right;
   954   if (source->right != NULL)
   955     source->right->parent = source;
   956   source->red = dest->red;
   957 }
   958 
   959 /* Remove NODE from TREE and return it.  NODE must exist in TREE.  */
   960 
   961 struct itree_node*
   962 itree_remove (struct itree_tree *tree, struct itree_node *node)
   963 {
   964   eassert (itree_contains (tree, node));
   965   eassert (check_tree (tree, true)); /* FIXME: Too expensive.  */
   966 
   967   /* Find `splice`, the leaf node to splice out of the tree.  When
   968      `node` has at most one child this is `node` itself.  Otherwise,
   969      it is the in order successor of `node`.  */
   970   itree_inherit_offset (tree->otick, node);
   971   struct itree_node *splice
   972     = (node->left == NULL || node->right == NULL)
   973         ? node
   974         : itree_subtree_min (tree->otick, node->right);
   975 
   976   /* Find `subtree`, the only child of `splice` (may be NULL).  Note:
   977      `subtree` will not be modified other than changing its parent to
   978      `splice`.  */
   979   eassert (splice->left == NULL || splice->right == NULL);
   980   struct itree_node *subtree
   981     = (splice->left != NULL) ? splice->left : splice->right;
   982 
   983   /* Save a pointer to the parent of where `subtree` will eventually
   984      be in `subtree_parent`.  */
   985   struct itree_node *subtree_parent
   986     = (splice->parent != node) ? splice->parent : splice;
   987 
   988   /* If `splice` is black removing it may violate Red-Black
   989      invariants, so note this for later.  */
   990 
   991   /* Replace `splice` with `subtree` under subtree's parent.  If
   992      `splice` is black, this creates a red-red violation, so remember
   993      this now as the field can be overwritten when splice is
   994      transplanted below.  */
   995   itree_replace_child (tree, subtree, splice);
   996   bool removed_black = !splice->red;
   997 
   998   /* Replace `node` with `splice` in the tree and propagate limit
   999      upwards, if necessary.  Note: Limit propagation can stabilize at
  1000      any point, so we must call from bottom to top for every node that
  1001      has a new child.  */
  1002   if (splice != node)
  1003     {
  1004       itree_transplant (tree, splice, node);
  1005       itree_propagate_limit (subtree_parent);
  1006       if (splice != subtree_parent)
  1007         itree_update_limit (splice);
  1008     }
  1009   itree_propagate_limit (splice->parent);
  1010 
  1011   --tree->size;
  1012 
  1013   /* Fix any black height violation caused by removing a black node.  */
  1014   if (removed_black)
  1015     itree_remove_fix (tree, subtree, subtree_parent);
  1016 
  1017   eassert ((tree->size == 0) == (tree->root == NULL));
  1018   eassert (check_tree (tree, true)); /* FIXME: Too expensive.  */
  1019 
  1020   /* Clear fields related to the tree for sanity while debugging.  */
  1021   node->red = false;
  1022   node->right = node->left = node->parent = NULL;
  1023   node->limit = 0;
  1024 
  1025   /* Must be clean (all offsets applied).  Also, some callers rely on
  1026      node's otick being the tree's otick.  */
  1027   eassert (node->otick == tree->otick);
  1028   eassert (node->offset == 0);
  1029 
  1030   return node;
  1031 }
  1032 
  1033 
  1034 /* +=======================================================================+
  1035  * | Insert/Delete Gaps
  1036  * +=======================================================================+ */
  1037 
  1038 /* Insert a gap at POS of length LENGTH expanding all intervals
  1039    intersecting it, while respecting their rear_advance and
  1040    front_advance setting.
  1041 
  1042    If BEFORE_MARKERS is non-zero, all overlays beginning/ending at POS
  1043    are treated as if their front_advance/rear_advance was true. */
  1044 
  1045 void
  1046 itree_insert_gap (struct itree_tree *tree,
  1047                   ptrdiff_t pos, ptrdiff_t length, bool before_markers)
  1048 {
  1049   if (!tree || length <= 0 || tree->root == NULL)
  1050     return;
  1051   uintmax_t ootick = tree->otick;
  1052 
  1053   /* FIXME: Don't allocate iterator/stack anew every time. */
  1054 
  1055   /* Nodes with front_advance starting at pos may mess up the tree
  1056      order, so we need to remove them first.  This doesn't apply for
  1057      `before_markers` since in that case, all positions move identically
  1058      regardless of `front_advance` or `rear_advance`.  */
  1059   struct itree_stack *saved = itree_stack_create (0);
  1060   struct itree_node *node = NULL;
  1061   if (!before_markers)
  1062     {
  1063       /* Actually any order would do.  */
  1064       ITREE_FOREACH (node, tree, pos, pos + 1, PRE_ORDER)
  1065         {
  1066           if (node->begin == pos && node->front_advance
  1067               /* If we have front_advance and !rear_advance and
  1068                  the overlay is empty, make sure we don't move
  1069                  begin past end by pretending it's !front_advance.  */
  1070               && (node->begin != node->end || node->rear_advance))
  1071             itree_stack_push (saved, node);
  1072         }
  1073     }
  1074   for (size_t i = 0; i < saved->length; ++i)
  1075     itree_remove (tree, saved->nodes[i]);
  1076 
  1077   /* We can't use an iterator here, because we can't effectively
  1078      narrow AND shift some subtree at the same time.  */
  1079   if (tree->root != NULL)
  1080     {
  1081       const int size = itree_max_height (tree) + 1;
  1082       struct itree_stack *stack = itree_stack_create (size);
  1083       itree_stack_push (stack, tree->root);
  1084       while ((node = itree_stack_pop (stack)))
  1085         {
  1086           /* Process in pre-order. */
  1087           itree_inherit_offset (tree->otick, node);
  1088           if (pos > node->limit)
  1089             continue;
  1090           if (node->right != NULL)
  1091             {
  1092               if (node->begin > pos)
  1093                 {
  1094                   /* All nodes in this subtree are shifted by length.  */
  1095                   node->right->offset += length;
  1096                   ++tree->otick;
  1097                 }
  1098               else
  1099                 itree_stack_push (stack, node->right);
  1100             }
  1101           if (node->left != NULL)
  1102             itree_stack_push (stack, node->left);
  1103 
  1104           if (before_markers
  1105               ? node->begin >= pos
  1106               : node->begin > pos) /* node->begin == pos => !front-advance  */
  1107             node->begin += length;
  1108           if (node->end > pos
  1109               || (node->end == pos && (before_markers || node->rear_advance)))
  1110             {
  1111               node->end += length;
  1112               eassert (node != NULL);
  1113               itree_propagate_limit (node);
  1114             }
  1115         }
  1116       itree_stack_destroy (stack);
  1117     }
  1118 
  1119   /* Reinsert nodes starting at POS having front-advance.  */
  1120   uintmax_t notick = tree->otick;
  1121   while ((node = itree_stack_pop (saved)))
  1122     {
  1123       eassert (node->otick == ootick);
  1124       eassert (node->begin == pos);
  1125       eassert (node->end > pos || node->rear_advance);
  1126       node->begin += length;
  1127       node->end += length;
  1128       node->otick = notick;
  1129       itree_insert_node (tree, node);
  1130     }
  1131 
  1132   itree_stack_destroy (saved);
  1133 }
  1134 
  1135 /* Delete a gap at POS of length LENGTH, contracting all intervals
  1136    intersecting it.  */
  1137 
  1138 void
  1139 itree_delete_gap (struct itree_tree *tree,
  1140                   ptrdiff_t pos, ptrdiff_t length)
  1141 {
  1142   if (!tree || length <= 0 || tree->root == NULL)
  1143     return;
  1144 
  1145   /* FIXME: Don't allocate stack anew every time.  */
  1146 
  1147   /* Can't use the iterator here, because by decrementing begin, we
  1148      might unintentionally bring shifted nodes back into our search space.  */
  1149   const int size = itree_max_height (tree) + 1;
  1150   struct itree_stack *stack = itree_stack_create (size);
  1151   struct itree_node *node;
  1152 
  1153   itree_stack_push (stack, tree->root);
  1154   while ((node = itree_stack_pop (stack)))
  1155     {
  1156       itree_inherit_offset (tree->otick, node);
  1157       if (pos > node->limit)
  1158         continue;
  1159       if (node->right != NULL)
  1160         {
  1161           if (node->begin > pos + length)
  1162             {
  1163               /* Shift right subtree to the left. */
  1164               node->right->offset -= length;
  1165               ++tree->otick;
  1166             }
  1167           else
  1168             itree_stack_push (stack, node->right);
  1169         }
  1170       if (node->left != NULL)
  1171         itree_stack_push (stack, node->left);
  1172 
  1173       if (pos < node->begin)
  1174         node->begin = max (pos, node->begin - length);
  1175       if (node->end > pos)
  1176         {
  1177           node->end = max (pos , node->end - length);
  1178           eassert (node != NULL);
  1179           itree_propagate_limit (node);
  1180         }
  1181     }
  1182   itree_stack_destroy (stack);
  1183 }
  1184 
  1185 
  1186 
  1187 /* +=======================================================================+
  1188  * | Iterator
  1189  * +=======================================================================+ */
  1190 
  1191 /* Return true, if NODE's interval intersects with [BEGIN, END).
  1192    Note: We always include empty nodes at BEGIN (and not at END),
  1193    but if BEGIN==END, then we don't include non-empty nodes starting
  1194    at BEGIN or ending at END.  This seems to match the behavior of the
  1195    old overlays code but it's not clear if it's The Right Thing
  1196    (e.g. it breaks the expectation that if NODE1 is included, then
  1197    a NODE2 strictly bigger than NODE1 should also be included).  */
  1198 
  1199 static inline bool
  1200 itree_node_intersects (const struct itree_node *node,
  1201                        ptrdiff_t begin, ptrdiff_t end)
  1202 {
  1203   return (begin < node->end && node->begin < end)
  1204     || (node->begin == node->end && begin == node->begin);
  1205 }
  1206 
  1207 /* Return the "next" node in the current traversal order.
  1208 
  1209    Note that this should return all the nodes that we need to traverse
  1210    in order to traverse the nodes selected by the current narrowing (i.e.
  1211    `ITER->begin..ITER->end`) so it will also return some nodes which aren't in
  1212    that narrowing simply because they may have children which are.
  1213 
  1214    The code itself is very unsatifactory because the code of each one
  1215    of the supported traversals seems completely different from the others.
  1216    If someone knows how to make it more uniform and "obviously correct",
  1217    please make yourself heard.  */
  1218 
  1219 static struct itree_node *
  1220 itree_iter_next_in_subtree (struct itree_node *node,
  1221                             struct itree_iterator *iter)
  1222 {
  1223   /* FIXME: Like in the previous version of the iterator, we
  1224      prune based on `limit` only when moving to a left child,
  1225      but `limit` can also get smaller when moving to a right child
  1226      It's actually fairly common, so maybe it would be worthwhile
  1227      to prune a bit more aggressively here.  */
  1228   struct itree_node *next;
  1229   switch (iter->order)
  1230     {
  1231     case ITREE_ASCENDING:
  1232       next = node->right;
  1233       if (!next)
  1234         {
  1235           while ((next = node->parent)
  1236                  && next->right == node)
  1237             node = next;
  1238           if (!next)
  1239             return NULL;   /* No more nodes to visit. */
  1240           node = next;
  1241         }
  1242       else
  1243         {
  1244           node = next;
  1245           itree_inherit_offset (iter->otick, node);
  1246           while ((next = node->left)
  1247                  && (itree_inherit_offset (iter->otick, next),
  1248                      iter->begin <= next->limit))
  1249             node = next;
  1250         }
  1251       if (node->begin > iter->end)
  1252         return NULL;  /* No more nodes within begin..end.  */
  1253       return node;
  1254 
  1255     case ITREE_DESCENDING:
  1256       next = node->left;
  1257       if (!next
  1258           || (itree_inherit_offset (iter->otick, next),
  1259               next->limit < iter->begin))
  1260         {
  1261           while ((next = node->parent)
  1262                  && next->left == node)
  1263             node = next;
  1264           if (!next)
  1265             return NULL;   /* No more nodes to visit. */
  1266           node = next;
  1267         }
  1268       else
  1269         {
  1270           node = next;
  1271           while (node->begin <= iter->end
  1272                  && (next = node->right))
  1273             {
  1274               itree_inherit_offset (iter->otick, next),
  1275               node = next;
  1276             }
  1277         }
  1278       return node;
  1279 
  1280     case ITREE_PRE_ORDER:
  1281       next = node->left;
  1282       if (next
  1283           && (itree_inherit_offset (iter->otick, next),
  1284               !(next->limit < iter->begin)))
  1285         return next;
  1286       next = node->right;
  1287       if (node->begin <= iter->end && next)
  1288         {
  1289           itree_inherit_offset (iter->otick, next);
  1290           return next;
  1291         }
  1292       while ((next = node->parent))
  1293         {
  1294           if (next->right == node)
  1295             node = next;
  1296           else
  1297             {
  1298               eassert (next->left == node);
  1299               node = next;
  1300               next = node->right;
  1301               if (node->begin <= iter->end && next)
  1302                 {
  1303                   itree_inherit_offset (iter->otick, next);
  1304                   return next;
  1305                 }
  1306             }
  1307           }
  1308       return NULL;
  1309 
  1310     case ITREE_POST_ORDER:
  1311       next = node->parent;
  1312       if (!next || next->right == node)
  1313         return next;
  1314       eassert (next->left == node);
  1315       node = next;
  1316       next = node->right;
  1317       if (!(node->begin <= iter->end && next))
  1318         return node;
  1319       node = next;
  1320       itree_inherit_offset (iter->otick, node);
  1321       while (((next = node->left)
  1322               && (itree_inherit_offset (iter->otick, next),
  1323                   iter->begin <= next->limit))
  1324              || (node->begin <= iter->end
  1325                  && (next = node->right)
  1326                  && (itree_inherit_offset (iter->otick, next), true)))
  1327         node = next;
  1328       return node;
  1329 
  1330     default:
  1331     emacs_abort ();
  1332     }
  1333 }
  1334 
  1335 static struct itree_node *
  1336 itree_iterator_first_node (struct itree_tree *tree,
  1337                            struct itree_iterator *iter)
  1338 {
  1339   struct itree_node *node = tree->root;
  1340   if (node)
  1341     {
  1342       struct itree_node dummy;
  1343       dummy.left = NULL;
  1344       dummy.parent = NULL;
  1345       dummy.right = NULL;
  1346       itree_inherit_offset (iter->otick, node);
  1347       switch (iter->order)
  1348         {
  1349         case ITREE_ASCENDING:
  1350           dummy.right = node;
  1351           dummy.begin = PTRDIFF_MIN;
  1352           node = itree_iter_next_in_subtree (&dummy, iter);
  1353           break;
  1354 
  1355         case ITREE_DESCENDING:
  1356           dummy.left = node;
  1357           node = itree_iter_next_in_subtree (&dummy, iter);
  1358           break;
  1359 
  1360         case ITREE_PRE_ORDER:
  1361           break;
  1362 
  1363         case ITREE_POST_ORDER:
  1364           dummy.parent = &dummy;
  1365           dummy.left = &dummy;
  1366           dummy.right = node;
  1367           dummy.begin = PTRDIFF_MIN;
  1368           node = itree_iter_next_in_subtree (&dummy, iter);
  1369           break;
  1370         default:
  1371           emacs_abort ();
  1372         }
  1373     }
  1374   return node;
  1375 }
  1376 
  1377 /* Start an iterator enumerating all intervals in [BEGIN,END) in the
  1378    given ORDER.  */
  1379 
  1380 struct itree_iterator *
  1381 itree_iterator_start (struct itree_iterator *iter,
  1382                       struct itree_tree *tree,
  1383                       ptrdiff_t begin, ptrdiff_t end, enum itree_order order)
  1384 {
  1385   eassert (iter);
  1386   iter->begin = begin;
  1387   iter->end = end;
  1388   iter->otick = tree->otick;
  1389   iter->order = order;
  1390   /* Beware: the `node` field always holds "the next" node to consider.
  1391      so it's always "one node ahead" of what the iterator loop sees.
  1392      In most respects this makes no difference, but we depend on this
  1393      detail in `delete_all_overlays` where this allows us to modify
  1394      the current node knowing that the iterator will not need it to
  1395      find the next.  */
  1396   iter->node = itree_iterator_first_node (tree, iter);
  1397   return iter;
  1398 }
  1399 
  1400 struct itree_node *
  1401 itree_iterator_next (struct itree_iterator *iter)
  1402 {
  1403   struct itree_node *node = iter->node;
  1404   while (node
  1405          && !itree_node_intersects (node, iter->begin, iter->end))
  1406     {
  1407       node = itree_iter_next_in_subtree (node, iter);
  1408       eassert (itree_limit_is_stable (node));
  1409     }
  1410   iter->node = node ? itree_iter_next_in_subtree (node, iter) : NULL;
  1411   return node;
  1412 }
  1413 
  1414 /* Limit G to the new interval [BEGIN, END), which must be a subset of
  1415    the current one.  I.E. it can't grow on either side. */
  1416 
  1417 void
  1418 itree_iterator_narrow (struct itree_iterator *g,
  1419                        ptrdiff_t begin, ptrdiff_t end)
  1420 {
  1421   eassert (g);
  1422   eassert (begin >= g->begin);
  1423   eassert (end <= g->end);
  1424   g->begin = max (begin, g->begin);
  1425   g->end = min (end, g->end);
  1426 }