Prefix all itree.h type names with itree_

Rename interval_node -> itree_node, interval_tree -> itree_tree,
interval_tree_order -> itree_order.

* src/alloc.c: Renames.
* src/buffer.c: ditto.
* src/itree.c: ditto.
* src/itree.h: ditto.
* src/lisp.h: ditto.
* src/pdumper.h: ditto.
* src/textprop.h: ditto.
* src/xdisp.h: ditto.

9 files changed, 135 insertions, 136 deletions

diff --git a/src/alloc.c b/src/alloc.c
index d7e0a99ffe7..a08249b1b11 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -3711,7 +3711,7 @@ build_overlay (bool front_advance, bool rear_advance,
   struct Lisp_Overlay *p = ALLOCATE_PSEUDOVECTOR (struct Lisp_Overlay, plist,
                                                   PVEC_OVERLAY);
   Lisp_Object overlay = make_lisp_ptr (p, Lisp_Vectorlike);
-  struct interval_node *node = xmalloc (sizeof (*node));
+  struct itree_node *node = xmalloc (sizeof (*node));
   interval_node_init (node, front_advance, rear_advance, overlay);
   p->interval = node;
   p->buffer = NULL;
@@ -6518,7 +6518,7 @@ mark_overlay (struct Lisp_Overlay *ov)
 /* Mark the overlay subtree rooted at NODE.  */
 
 static void
-mark_overlays (struct interval_node *node)
+mark_overlays (struct itree_node *node)
 {
   if (node == NULL)
     return;
diff --git a/src/buffer.c b/src/buffer.c
index 74c6705cbd3..228c6e60560 100644
--- a/src/buffer.c
+++ b/src/buffer.c
@@ -655,7 +655,7 @@ static void
 copy_overlays (struct buffer *from, struct buffer *to)
 {
   eassert (to && ! to->overlays);
-  struct interval_node *node;
+  struct itree_node *node;
 
   ITREE_FOREACH (node, from->overlays, PTRDIFF_MIN, PTRDIFF_MAX, ASCENDING)
     {
@@ -932,13 +932,13 @@ drop_overlay (struct Lisp_Overlay *ov)
 void
 delete_all_overlays (struct buffer *b)
 {
-  struct interval_node *node;
+  struct itree_node *node;
 
   if (! b->overlays)
     return;
 
   /* FIXME: This loop sets the overlays' `buffer` field to NULL but
-     doesn't set the interval_nodes' `parent`, `left` and `right`
+     doesn't set the itree_nodes' `parent`, `left` and `right`
      fields accordingly.  I believe it's harmless, but a bit untidy since
      other parts of the code are careful to set those fields to NULL when
      the overlay is deleted.
@@ -978,8 +978,8 @@ set_overlays_multibyte (bool multibyte)
   if (! current_buffer->overlays || Z == Z_BYTE)
     return;
 
-  struct interval_node **nodes = NULL;
-  struct interval_tree *tree = current_buffer->overlays;
+  struct itree_node **nodes = NULL;
+  struct itree_tree *tree = current_buffer->overlays;
   const intmax_t size = interval_tree_size (tree);
 
   /* We can't use `interval_node_set_region` at the same time
@@ -988,14 +988,14 @@ set_overlays_multibyte (bool multibyte)
   USE_SAFE_ALLOCA;
   SAFE_NALLOCA (nodes, 1, size);
   {
-    struct interval_node *node, **cursor = nodes;
+    struct itree_node *node, **cursor = nodes;
     ITREE_FOREACH (node, tree, PTRDIFF_MIN, PTRDIFF_MAX, ASCENDING)
       *(cursor++) = node;
   }
 
   for (int i = 0; i < size; ++i, ++nodes)
     {
-      struct interval_node * const node = *nodes;
+      struct itree_node * const node = *nodes;
 
       if (multibyte)
         {
@@ -2436,7 +2436,7 @@ advance_to_char_boundary (ptrdiff_t byte_pos)
 static void
 swap_buffer_overlays (struct buffer *buffer, struct buffer *other)
 {
-  struct interval_node *node;
+  struct itree_node *node;
 
   ITREE_FOREACH (node, buffer->overlays, PTRDIFF_MIN, PTRDIFF_MAX, ASCENDING)
     XOVERLAY (node->data)->buffer = other;
@@ -2965,7 +2965,7 @@ overlays_in (ptrdiff_t beg, ptrdiff_t end, bool extend,
   ptrdiff_t len = *len_ptr;
   ptrdiff_t next = ZV;
   Lisp_Object *vec = *vec_ptr;
-  struct interval_node *node;
+  struct itree_node *node;
 
   ITREE_FOREACH (node, current_buffer->overlays, beg,
                  /* Find empty OV at Z ? */
@@ -3026,7 +3026,7 @@ ptrdiff_t
 next_overlay_change (ptrdiff_t pos)
 {
   ptrdiff_t next = ZV;
-  struct interval_node *node;
+  struct itree_node *node;
 
   ITREE_FOREACH (node, current_buffer->overlays, pos, next, ASCENDING)
     {
@@ -3052,7 +3052,7 @@ next_overlay_change (ptrdiff_t pos)
 ptrdiff_t
 previous_overlay_change (ptrdiff_t pos)
 {
-  struct interval_node *node;
+  struct itree_node *node;
   ptrdiff_t prev = BEGV;
 
   ITREE_FOREACH (node, current_buffer->overlays, prev, pos, DESCENDING)
@@ -3135,7 +3135,7 @@ disable_line_numbers_overlay_at_eob (void)
 bool
 overlay_touches_p (ptrdiff_t pos)
 {
-  struct interval_node *node;
+  struct itree_node *node;
 
   /* We need to find overlays ending in pos, as well as empty ones at
      pos. */
@@ -3347,7 +3347,7 @@ ptrdiff_t
 overlay_strings (ptrdiff_t pos, struct window *w, unsigned char **pstr)
 {
   bool multibyte = ! NILP (BVAR (current_buffer, enable_multibyte_characters));
-  struct interval_node *node;
+  struct itree_node *node;
 
   overlay_heads.used = overlay_heads.bytes = 0;
   overlay_tails.used = overlay_tails.bytes = 0;
@@ -3848,7 +3848,7 @@ However, the overlays you get are the real objects that the buffer uses. */)
   (void)
 {
   Lisp_Object overlays = Qnil;
-  struct interval_node *node;
+  struct itree_node *node;
 
   ITREE_FOREACH (node, current_buffer->overlays, BEG, Z, DESCENDING)
     overlays = Fcons (node->data, overlays);
@@ -3980,7 +3980,7 @@ report_overlay_modification (Lisp_Object start, Lisp_Object end, bool after,
 
   if (!after)
     {
-      struct interval_node *node;
+      struct itree_node *node;
       EMACS_INT begin_arg = XFIXNUM (start);
       EMACS_INT end_arg = XFIXNUM (end);
       /* We are being called before a change.
@@ -4072,7 +4072,7 @@ void
 evaporate_overlays (ptrdiff_t pos)
 {
   Lisp_Object hit_list = Qnil;
-  struct interval_node *node;
+  struct itree_node *node;
 
   ITREE_FOREACH (node, current_buffer->overlays, pos, pos, ASCENDING)
     {
@@ -4913,7 +4913,7 @@ defvar_per_buffer (struct Lisp_Buffer_Objfwd *bo_fwd, const char *namestring,
 
 #ifdef ITREE_DEBUG
 static Lisp_Object
-make_lispy_interval_node (const struct interval_node *node)
+make_lispy_itree_node (const struct itree_node *node)
 {
   return listn (12,
                 intern (":begin"),
@@ -4931,12 +4931,12 @@ make_lispy_interval_node (const struct interval_node *node)
 }
 
 static Lisp_Object
-overlay_tree (const struct interval_tree *tree,
-              const struct interval_node *node)
+overlay_tree (const struct itree_tree *tree,
+              const struct itree_node *node)
 {
   if (node == ITREE_NULL)
     return Qnil;
-  return list3 (make_lispy_interval_node (node),
+  return list3 (make_lispy_itree_node (node),
                 overlay_tree (tree, node->left),
                 overlay_tree (tree, node->right));
 }
diff --git a/src/buffer.h b/src/buffer.h
index afcdfcd9a02..ee0c8dd8361 100644
--- a/src/buffer.h
+++ b/src/buffer.h
@@ -698,7 +698,7 @@ struct buffer
   bool_bf long_line_optimizations_p : 1;
 
   /* The inveral tree containing this buffer's overlays. */
-  struct interval_tree *overlays;
+  struct itree_tree *overlays;
 
   /* Changes in the buffer are recorded here for undo, and t means
      don't record anything.  This information belongs to the base
diff --git a/src/itree.c b/src/itree.c
index f7597ef86ad..6d54a36c3bb 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -135,7 +135,7 @@ along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.  */
 typedef uintptr_t nodeptr_and_flag;
 
 static inline nodeptr_and_flag
-make_nav (struct interval_node *ptr, bool flag)
+make_nav (struct itree_node *ptr, bool flag)
 {
   uintptr_t v = (uintptr_t) ptr;
   /* We assume alignment imposes the LSB is clear for us to use it.  */
@@ -143,10 +143,10 @@ make_nav (struct interval_node *ptr, bool flag)
   return v | !!flag;
 }
 
-static inline struct interval_node *
+static inline struct itree_node *
 nav_nodeptr (nodeptr_and_flag nav)
 {
-  return (struct interval_node *) (nav & (~(uintptr_t)1));
+  return (struct itree_node *) (nav & (~(uintptr_t)1));
 }
 
 static inline bool
@@ -170,7 +170,7 @@ interval_stack_create (intmax_t initial_size)
 {
   struct interval_stack *stack = xmalloc (sizeof (struct interval_stack));
   stack->size = max (0, initial_size);
-  stack->nodes = xmalloc (stack->size * sizeof (struct interval_node*));
+  stack->nodes = xmalloc (stack->size * sizeof (struct itree_node*));
   stack->length = 0;
   return stack;
 }
@@ -206,7 +206,7 @@ interval_stack_ensure_space (struct interval_stack *stack, intmax_t nelements)
 
 static inline void
 interval_stack_push_flagged (struct interval_stack *stack,
-                             struct interval_node *node, bool flag)
+                             struct itree_node *node, bool flag)
 {
   eassert (node && node != NULL);
 
@@ -223,7 +223,7 @@ interval_stack_push_flagged (struct interval_stack *stack,
 }
 
 static inline void
-interval_stack_push (struct interval_stack *stack, struct interval_node *node)
+interval_stack_push (struct interval_stack *stack, struct itree_node *node)
 {
   interval_stack_push_flagged (stack, node, false);
 }
@@ -246,7 +246,7 @@ struct itree_iterator
   ptrdiff_t begin;
   ptrdiff_t end;
   uintmax_t otick;              /* A copy of the tree's `otick`.  */
-  enum interval_tree_order order;
+  enum itree_order order;
   bool running;
   const char* file;
   int line;
@@ -260,7 +260,7 @@ struct itree_iterator
 static struct itree_iterator *iter;
 
 static int
-interval_tree_max_height (const struct interval_tree *tree)
+interval_tree_max_height (const struct itree_tree *tree)
 {
   return 2 * log (tree->size + 1) / log (2) + 0.5;
 }
@@ -268,7 +268,7 @@ interval_tree_max_height (const struct interval_tree *tree)
 /* Allocate a new iterator for TREE. */
 
 static struct itree_iterator *
-itree_iterator_create (struct interval_tree *tree)
+itree_iterator_create (struct itree_tree *tree)
 {
   struct itree_iterator *g = xmalloc (sizeof *g);
   /* 19 here just avoids starting with a silly-small stack.
@@ -300,7 +300,7 @@ struct check_subtree_result
 };
 
 static struct check_subtree_result
-check_subtree (struct interval_node *node,
+check_subtree (struct itree_node *node,
                bool check_red_black_invariants, uintmax_t tree_otick,
                ptrdiff_t offset, ptrdiff_t min_begin,
                ptrdiff_t max_begin)
@@ -369,7 +369,7 @@ check_subtree (struct interval_node *node,
    entire tree and validates all invariants.
 */
 static bool
-check_tree (struct interval_tree *tree,
+check_tree (struct itree_tree *tree,
             bool check_red_black_invariants)
 {
   eassert (tree != NULL);
@@ -380,7 +380,7 @@ check_tree (struct interval_tree *tree,
   eassert (tree->root->parent == NULL);
   eassert (!check_red_black_invariants || !tree->root->red);
 
-  struct interval_node *node = tree->root;
+  struct itree_node *node = tree->root;
   struct check_subtree_result result
     = check_subtree (node, check_red_black_invariants, tree->otick,
                      node->offset, PTRDIFF_MIN,
@@ -396,19 +396,19 @@ check_tree (struct interval_tree *tree,
  * +=======================================================================+ */
 
 static bool
-null_safe_is_red (struct interval_node *node)
+null_safe_is_red (struct itree_node *node)
 {
   return node != NULL && node->red;
 }
 
 static bool
-null_safe_is_black (struct interval_node *node)
+null_safe_is_black (struct itree_node *node)
 {
   return node == NULL || !node->red; /* NULL nodes are black */
 }
 
 static inline ptrdiff_t
-itree_newlimit (struct interval_node *node)
+itree_newlimit (struct itree_node *node)
 {
   eassert (node != NULL);
   return max (node->end,
@@ -423,7 +423,7 @@ itree_newlimit (struct interval_node *node)
 /* Update NODE's limit attribute according to its children. */
 
 static void
-interval_tree_update_limit (struct interval_node *node)
+interval_tree_update_limit (struct itree_node *node)
 {
   if (node == NULL)
     return;
@@ -438,7 +438,7 @@ interval_tree_update_limit (struct interval_node *node)
 */
 
 static void
-interval_tree_inherit_offset (uintmax_t otick, struct interval_node *node)
+interval_tree_inherit_offset (uintmax_t otick, struct itree_node *node)
 {
   eassert (node->parent == NULL || node->parent->otick >= node->otick);
   if (node->otick == otick)
@@ -475,7 +475,7 @@ interval_tree_inherit_offset (uintmax_t otick, struct interval_node *node)
    stable, i.e. new_limit = old_limit.  */
 
 static void
-interval_tree_propagate_limit (struct interval_node *node)
+interval_tree_propagate_limit (struct itree_node *node)
 {
   if (node == NULL)
     return;
@@ -491,8 +491,8 @@ interval_tree_propagate_limit (struct interval_node *node)
   }
 }
 
-static struct interval_node*
-interval_tree_validate (struct interval_tree *tree, struct interval_node *node)
+static struct itree_node*
+interval_tree_validate (struct itree_tree *tree, struct itree_node *node)
 {
 
   if (tree->otick == node->otick || node == NULL)
@@ -511,7 +511,7 @@ interval_tree_validate (struct interval_tree *tree, struct interval_node *node)
 /* Initialize an allocated node. */
 
 void
-interval_node_init (struct interval_node *node,
+interval_node_init (struct itree_node *node,
                     bool front_advance, bool rear_advance,
                     Lisp_Object data)
 {
@@ -528,8 +528,8 @@ interval_node_init (struct interval_node *node,
 /* Return NODE's begin value, computing it if necessary. */
 
 ptrdiff_t
-interval_node_begin (struct interval_tree *tree,
-                     struct interval_node *node)
+interval_node_begin (struct itree_tree *tree,
+                     struct itree_node *node)
 {
   interval_tree_validate (tree, node);
   return node->begin;
@@ -538,8 +538,8 @@ interval_node_begin (struct interval_tree *tree,
 /* Return NODE's end value, computing it if necessary. */
 
 ptrdiff_t
-interval_node_end (struct interval_tree *tree,
-                   struct interval_node *node)
+interval_node_end (struct itree_tree *tree,
+                   struct itree_node *node)
 {
   interval_tree_validate (tree, node);
   return node->end;
@@ -547,7 +547,7 @@ interval_node_end (struct interval_tree *tree,
 
 /* Allocate an interval_tree. Free with interval_tree_destroy. */
 
-struct interval_tree*
+struct itree_tree*
 interval_tree_create (void)
 {
   /* FIXME?  Maybe avoid the initialization of itree_null in the same
@@ -555,7 +555,7 @@ interval_tree_create (void)
      important though.  */
   itree_init ();
 
-  struct interval_tree *tree = xmalloc (sizeof (*tree));
+  struct itree_tree *tree = xmalloc (sizeof (*tree));
   interval_tree_clear (tree);
   return tree;
 }
@@ -563,7 +563,7 @@ interval_tree_create (void)
 /* Reset the tree TREE to its empty state.  */
 
 void
-interval_tree_clear (struct interval_tree *tree)
+interval_tree_clear (struct itree_tree *tree)
 {
   tree->root = NULL;
   tree->otick = 1;
@@ -583,7 +583,7 @@ interval_tree_init (struct interval_tree *tree)
 
 /* Release a tree, freeing its allocated memory.  */
 void
-interval_tree_destroy (struct interval_tree *tree)
+interval_tree_destroy (struct itree_tree *tree)
 {
   eassert (tree->root == NULL);
   /* if (tree->iter)
@@ -594,7 +594,7 @@ interval_tree_destroy (struct interval_tree *tree)
 /* Return the number of nodes in TREE.  */
 
 intmax_t
-interval_tree_size (struct interval_tree *tree)
+interval_tree_size (struct itree_tree *tree)
 {
   return tree->size;
 }
@@ -602,12 +602,12 @@ interval_tree_size (struct interval_tree *tree)
 /* Perform the familiar left-rotation on node NODE.  */
 
 static void
-interval_tree_rotate_left (struct interval_tree *tree,
-                           struct interval_node *node)
+interval_tree_rotate_left (struct itree_tree *tree,
+                           struct itree_node *node)
 {
   eassert (node->right != NULL);
 
-  struct interval_node *right = node->right;
+  struct itree_node *right = node->right;
 
   interval_tree_inherit_offset (tree->otick, node);
   interval_tree_inherit_offset (tree->otick, right);
@@ -645,12 +645,12 @@ interval_tree_rotate_left (struct interval_tree *tree,
 /* Perform the familiar right-rotation on node NODE.  */
 
 static void
-interval_tree_rotate_right (struct interval_tree *tree,
-                            struct interval_node *node)
+interval_tree_rotate_right (struct itree_tree *tree,
+                            struct itree_node *node)
 {
   eassert (tree && node && node->left != NULL);
 
-  struct interval_node *left = node->left;
+  struct itree_node *left = node->left;
 
   interval_tree_inherit_offset (tree->otick, node);
   interval_tree_inherit_offset (tree->otick, left);
@@ -684,8 +684,8 @@ interval_tree_rotate_right (struct interval_tree *tree,
    Rebalance the parents as needed to re-establish the RB invariants.  */
 
 static void
-interval_tree_insert_fix (struct interval_tree *tree,
-                          struct interval_node *node)
+interval_tree_insert_fix (struct itree_tree *tree,
+                          struct itree_node *node)
 {
   eassert (tree->root->red == false);
 
@@ -699,7 +699,7 @@ interval_tree_insert_fix (struct interval_tree *tree,
         {
           /* We're on the left side of our grandparent, and OTHER is
              our "uncle".  */
-          struct interval_node *uncle = node->parent->parent->right;
+          struct itree_node *uncle = node->parent->parent->right;
 
           if (null_safe_is_red (uncle)) /* case 1.a */
             {
@@ -729,7 +729,7 @@ interval_tree_insert_fix (struct interval_tree *tree,
       else
         {
           /* This is the symmetrical case of above.  */
-          struct interval_node *uncle = node->parent->parent->left;
+          struct itree_node *uncle = node->parent->parent->left;
 
           if (null_safe_is_red (uncle)) /* case 1.b */
             {
@@ -763,7 +763,7 @@ interval_tree_insert_fix (struct interval_tree *tree,
    Note, that inserting a node twice results in undefined behaviour.  */
 
 static void
-interval_tree_insert (struct interval_tree *tree, struct interval_node *node)
+interval_tree_insert (struct itree_tree *tree, struct itree_node *node)
 {
   eassert (node->begin <= node->end && node != NULL);
   /* FIXME: The assertion below fails because `delete_all_overlays`
@@ -772,8 +772,8 @@ interval_tree_insert (struct interval_tree *tree, struct interval_node *node)
              && node->parent == NULL) */;
   eassert (check_tree (tree, true)); /* FIXME: Too expensive.  */
 
-  struct interval_node *parent = NULL;
-  struct interval_node *child = tree->root;
+  struct itree_node *parent = NULL;
+  struct itree_node *child = tree->root;
   uintmax_t otick = tree->otick;
   /* It's the responsability of the caller to set `otick` on the node,
      to "confirm" that the begin/end fields are up to date.  */
@@ -821,7 +821,7 @@ interval_tree_insert (struct interval_tree *tree, struct interval_node *node)
 }
 
 void
-itree_insert_node (struct interval_tree *tree, struct interval_node *node,
+itree_insert_node (struct itree_tree *tree, struct itree_node *node,
                    ptrdiff_t begin, ptrdiff_t end)
 {
   node->begin = begin;
@@ -833,8 +833,8 @@ itree_insert_node (struct interval_tree *tree, struct interval_node *node,
 /* Safely modify a node's interval. */
 
 void
-interval_node_set_region (struct interval_tree *tree,
-                          struct interval_node *node,
+interval_node_set_region (struct itree_tree *tree,
+                          struct itree_node *node,
                           ptrdiff_t begin, ptrdiff_t end)
 {
   interval_tree_validate (tree, node);
@@ -856,10 +856,10 @@ interval_node_set_region (struct interval_tree *tree,
 /* Return true, if NODE is a member of TREE. */
 
 static bool
-interval_tree_contains (struct interval_tree *tree, struct interval_node *node)
+interval_tree_contains (struct itree_tree *tree, struct itree_node *node)
 {
   eassert (node);
-  struct interval_node *other;
+  struct itree_node *other;
   ITREE_FOREACH (other, tree, node->begin, PTRDIFF_MAX, ASCENDING)
     if (other == node)
       {
@@ -871,7 +871,7 @@ interval_tree_contains (struct interval_tree *tree, struct interval_node *node)
 }
 
 static bool
-itree_limit_is_stable (struct interval_node *node)
+itree_limit_is_stable (struct itree_node *node)
 {
   if (node == NULL)
     return true;
@@ -879,8 +879,8 @@ itree_limit_is_stable (struct interval_node *node)
   return (newlimit == node->limit);
 }
 
-static struct interval_node*
-interval_tree_subtree_min (uintmax_t otick, struct interval_node *node)
+static struct itree_node*
+interval_tree_subtree_min (uintmax_t otick, struct itree_node *node)
 {
   if (node == NULL)
     return node;
@@ -895,9 +895,9 @@ interval_tree_subtree_min (uintmax_t otick, struct interval_node *node)
    so re-balance the parents to re-establish the RB invariants.  */
 
 static void
-interval_tree_remove_fix (struct interval_tree *tree,
-                          struct interval_node *node,
-                          struct interval_node *parent)
+interval_tree_remove_fix (struct itree_tree *tree,
+                          struct itree_node *node,
+                          struct itree_node *parent)
 {
   if (parent == NULL)
     eassert (node == tree->root);
@@ -910,7 +910,7 @@ interval_tree_remove_fix (struct interval_tree *tree,
 
       if (node == parent->left)
         {
-          struct interval_node *other = parent->right;
+          struct itree_node *other = parent->right;
 
           if (null_safe_is_red (other)) /* case 1.a */
             {
@@ -947,7 +947,7 @@ interval_tree_remove_fix (struct interval_tree *tree,
         }
       else
         {
-          struct interval_node *other = parent->left;
+          struct itree_node *other = parent->left;
 
           if (null_safe_is_red (other)) /* 1.b */
             {
@@ -991,7 +991,7 @@ interval_tree_remove_fix (struct interval_tree *tree,
 
 /* Return accumulated offsets of NODE's parents.  */
 static ptrdiff_t
-itree_total_offset (struct interval_node *node)
+itree_total_offset (struct itree_node *node)
 {
   eassert (node != NULL);
   ptrdiff_t offset = 0;
@@ -1011,9 +1011,9 @@ itree_total_offset (struct interval_node *node)
    unchanged.  Caller is responsible for recalculation of `limit`.
    Requires both nodes to be using the same effective `offset`.  */
 static void
-interval_tree_replace_child (struct interval_tree *tree,
-                             struct interval_node *source,
-                             struct interval_node *dest)
+interval_tree_replace_child (struct itree_tree *tree,
+                             struct itree_node *source,
+                             struct itree_node *dest)
 {
   eassert (tree && dest != NULL);
   eassert (source == NULL
@@ -1037,9 +1037,9 @@ interval_tree_replace_child (struct interval_tree *tree,
    recalculation of `limit`.  Requires both nodes to be using the same
    effective `offset`. */
 static void
-interval_tree_transplant (struct interval_tree *tree,
-                          struct interval_node *source,
-                          struct interval_node *dest)
+interval_tree_transplant (struct itree_tree *tree,
+                          struct itree_node *source,
+                          struct itree_node *dest)
 {
   interval_tree_replace_child (tree, source, dest);
   source->left = dest->left;
@@ -1053,8 +1053,8 @@ interval_tree_transplant (struct interval_tree *tree,
 
 /* Remove NODE from TREE and return it.  NODE must exist in TREE.  */
 
-struct interval_node*
-interval_tree_remove (struct interval_tree *tree, struct interval_node *node)
+struct itree_node*
+interval_tree_remove (struct itree_tree *tree, struct itree_node *node)
 {
   eassert (interval_tree_contains (tree, node));
   eassert (check_tree (tree, true)); /* FIXME: Too expensive.  */
@@ -1063,7 +1063,7 @@ interval_tree_remove (struct interval_tree *tree, struct interval_node *node)
      `node` has at most one child this is `node` itself.  Otherwise,
      it is the in order successor of `node`.  */
   interval_tree_inherit_offset (tree->otick, node);
-  struct interval_node *splice
+  struct itree_node *splice
     = (node->left == NULL || node->right == NULL)
         ? node
         : interval_tree_subtree_min (tree->otick, node->right);
@@ -1072,12 +1072,12 @@ interval_tree_remove (struct interval_tree *tree, struct interval_node *node)
      `subtree` will not be modified other than changing its parent to
      `splice`.  */
   eassert (splice->left == NULL || splice->right == NULL);
-  struct interval_node *subtree
+  struct itree_node *subtree
     = (splice->left != NULL) ? splice->left : splice->right;
 
   /* Save a pointer to the parent of where `subtree` will eventually
      be in `subtree_parent`.  */
-  struct interval_node *subtree_parent
+  struct itree_node *subtree_parent
     = (splice->parent != node) ? splice->parent : splice;
 
   /* If `splice` is black removing it may violate Red-Black
@@ -1135,8 +1135,8 @@ itree_iterator_busy_p (void)
    given ORDER.  Only one iterator per tree can be running at any time.  */
 
 struct itree_iterator *
-itree_iterator_start (struct interval_tree *tree, ptrdiff_t begin,
-                      ptrdiff_t end, enum interval_tree_order order,
+itree_iterator_start (struct itree_tree *tree, ptrdiff_t begin,
+                      ptrdiff_t end, enum itree_order order,
                       const char *file, int line)
 {
   /* struct itree_iterator *iter = tree->iter; */
@@ -1181,7 +1181,7 @@ itree_iterator_finish (struct itree_iterator *iter)
    front_advance setting. */
 
 void
-interval_tree_insert_gap (struct interval_tree *tree,
+interval_tree_insert_gap (struct itree_tree *tree,
                           ptrdiff_t pos, ptrdiff_t length)
 {
   if (length <= 0 || tree->root == NULL)
@@ -1193,7 +1193,7 @@ interval_tree_insert_gap (struct interval_tree *tree,
   /* Nodes with front_advance starting at pos may mess up the tree
      order, so we need to remove them first. */
   struct interval_stack *saved = interval_stack_create (0);
-  struct interval_node *node = NULL;
+  struct itree_node *node = NULL;
   ITREE_FOREACH (node, tree, pos, pos + 1, PRE_ORDER)
     {
       if (node->begin == pos && node->front_advance
@@ -1265,7 +1265,7 @@ interval_tree_insert_gap (struct interval_tree *tree,
    intersecting it. */
 
 void
-interval_tree_delete_gap (struct interval_tree *tree,
+interval_tree_delete_gap (struct itree_tree *tree,
                           ptrdiff_t pos, ptrdiff_t length)
 {
   if (length <= 0 || tree->root == NULL)
@@ -1277,7 +1277,7 @@ interval_tree_delete_gap (struct interval_tree *tree,
      might unintentionally bring shifted nodes back into our search space. */
   const int size = interval_tree_max_height (tree) + 1;
   struct interval_stack *stack = interval_stack_create (size);
-  struct interval_node *node;
+  struct itree_node *node;
 
   interval_stack_push (stack, tree->root);
   nodeptr_and_flag nav;
@@ -1327,7 +1327,7 @@ interval_tree_delete_gap (struct interval_tree *tree,
    a NODE2 strictly bigger than NODE1 should also be included).  */
 
 static inline bool
-interval_node_intersects (const struct interval_node *node,
+interval_node_intersects (const struct itree_node *node,
                           ptrdiff_t begin, ptrdiff_t end)
 {
   return (begin < node->end && node->begin < end)
@@ -1337,13 +1337,13 @@ interval_node_intersects (const struct interval_node *node,
 /* Return the next node of the iterator in the order given when it was
    started; or NULL if there are no more nodes. */
 
-struct interval_node *
+struct itree_node *
 itree_iterator_next (struct itree_iterator *g)
 {
   eassert (g->running);
 
-  struct interval_node * const null = NULL;
-  struct interval_node *node;
+  struct itree_node * const null = NULL;
+  struct itree_node *node;
 
   /* The `visited` flag stored in each node is used here (and only here):
      We keep a "workstack" of nodes we need to consider.  This stack
@@ -1363,8 +1363,8 @@ itree_iterator_next (struct itree_iterator *g)
             visited = nav_flag (nav),
             node && !visited))
       {
-        struct interval_node * const left = node->left;
-        struct interval_node * const right = node->right;
+        struct itree_node * const left = node->left;
+        struct itree_node * const right = node->right;
 
         interval_tree_inherit_offset (g->otick, node);
         eassert (itree_limit_is_stable (node));
diff --git a/src/itree.h b/src/itree.h
index b0f7a1d193b..b4116a1fb75 100644
--- a/src/itree.h
+++ b/src/itree.h
@@ -36,15 +36,14 @@ along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.  */
    returns as a side-effect.  See ITREE_FOREACH.
  */
 
-struct interval_node;
-struct interval_node
+struct itree_node
 {
   /* The normal parent, left and right links found in binary trees.
      See also `red`, below, which completes the Red-Black tree
      representation.  */
-  struct interval_node *parent;
-  struct interval_node *left;
-  struct interval_node *right;
+  struct itree_node *parent;
+  struct itree_node *left;
+  struct itree_node *right;
 
   /* The following five fields comprise the interval abstraction.
 
@@ -63,7 +62,7 @@ struct interval_node
 
      OTICK determines whether BEGIN, END, LIMIT and OFFSET are
      considered dirty.  A node is clean when its OTICK is equal to the
-     OTICK of its tree (see struct interval_tree).  Otherwise, it is
+     OTICK of its tree (see struct itree_tree).  Otherwise, it is
      dirty.
 
      In a clean node, BEGIN, END and LIMIT are correct buffer
@@ -95,44 +94,44 @@ struct interval_node
   bool_bf front_advance : 1;    /* Same as for marker and overlays.  */
 };
 
-struct interval_tree
+struct itree_tree
 {
-  struct interval_node *root;
+  struct itree_node *root;
   uintmax_t otick;              /* offset tick, compared with node's otick. */
   intmax_t size;                /* Number of nodes in the tree. */
 };
 
-enum interval_tree_order {
+enum itree_order {
   ITREE_ASCENDING,
   ITREE_DESCENDING,
   ITREE_PRE_ORDER,
 };
 
-void interval_node_init (struct interval_node *, bool, bool, Lisp_Object);
-ptrdiff_t interval_node_begin (struct interval_tree *, struct interval_node *);
-ptrdiff_t interval_node_end (struct interval_tree *, struct interval_node *);
-void interval_node_set_region (struct interval_tree *, struct interval_node *, ptrdiff_t, ptrdiff_t);
-struct interval_tree *interval_tree_create (void);
-void interval_tree_destroy (struct interval_tree *);
-intmax_t interval_tree_size (struct interval_tree *);
-void interval_tree_clear (struct interval_tree *);
-void itree_insert_node (struct interval_tree *tree, struct interval_node *node,
+void interval_node_init (struct itree_node *, bool, bool, Lisp_Object);
+ptrdiff_t interval_node_begin (struct itree_tree *, struct itree_node *);
+ptrdiff_t interval_node_end (struct itree_tree *, struct itree_node *);
+void interval_node_set_region (struct itree_tree *, struct itree_node *, ptrdiff_t, ptrdiff_t);
+struct itree_tree *interval_tree_create (void);
+void interval_tree_destroy (struct itree_tree *);
+intmax_t interval_tree_size (struct itree_tree *);
+void interval_tree_clear (struct itree_tree *);
+void itree_insert_node (struct itree_tree *tree, struct itree_node *node,
                         ptrdiff_t begin, ptrdiff_t end);
-struct interval_node *interval_tree_remove (struct interval_tree *, struct interval_node *);
-void interval_tree_insert_gap (struct interval_tree *, ptrdiff_t, ptrdiff_t);
-void interval_tree_delete_gap (struct interval_tree *, ptrdiff_t, ptrdiff_t);
+struct itree_node *interval_tree_remove (struct itree_tree *, struct itree_node *);
+void interval_tree_insert_gap (struct itree_tree *, ptrdiff_t, ptrdiff_t);
+void interval_tree_delete_gap (struct itree_tree *, ptrdiff_t, ptrdiff_t);
 
 /* Iteration functions.  Almost all code should use ITREE_FOREACH
    instead.  */
 bool itree_iterator_busy_p (void);
 struct itree_iterator *
-itree_iterator_start (struct interval_tree *tree, ptrdiff_t begin,
-                      ptrdiff_t end, enum interval_tree_order order,
+itree_iterator_start (struct itree_tree *tree, ptrdiff_t begin,
+                      ptrdiff_t end, enum itree_order order,
                       const char *file, int line);
 void itree_iterator_narrow (struct itree_iterator *, ptrdiff_t,
                             ptrdiff_t);
 void itree_iterator_finish (struct itree_iterator *);
-struct interval_node *itree_iterator_next (struct itree_iterator *);
+struct itree_node *itree_iterator_next (struct itree_iterator *);
 
 /* Iterate over the intervals between BEG and END in the tree T.
    N will hold successive nodes.  ORDER can be one of : `ASCENDING`,
diff --git a/src/lisp.h b/src/lisp.h
index 7cd78712814..b256d65efcd 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -2604,7 +2604,7 @@ struct Lisp_Overlay
     union vectorlike_header header;
     Lisp_Object plist;
     struct buffer *buffer;        /* eassert (live buffer || NULL). */
-    struct interval_node *interval;
+    struct itree_node *interval;
   } GCALIGNED_STRUCT;
 
 struct Lisp_Misc_Ptr
diff --git a/src/pdumper.c b/src/pdumper.c
index 1a2ecea71e6..1830c6bd18b 100644
--- a/src/pdumper.c
+++ b/src/pdumper.c
@@ -2134,13 +2134,13 @@ dump_marker (struct dump_context *ctx, const struct Lisp_Marker *marker)
 }
 
 static dump_off
-dump_interval_node (struct dump_context *ctx, struct interval_node *node,
+dump_interval_node (struct dump_context *ctx, struct itree_node *node,
                     dump_off parent_offset)
 {
 #if CHECK_STRUCTS && !defined (HASH_interval_node_5765524F7E)
 # error "interval_node changed. See CHECK_STRUCTS comment in config.h."
 #endif
-  struct interval_node out;
+  struct itree_node out;
   dump_object_start (ctx, &out, sizeof (out));
   if (node->parent)
     dump_field_fixup_later (ctx, &out, node, &node->parent);
@@ -2161,17 +2161,17 @@ dump_interval_node (struct dump_context *ctx, struct interval_node *node,
   if (node->parent)
       dump_remember_fixup_ptr_raw
         (ctx,
-         offset + dump_offsetof (struct interval_node, parent),
+         offset + dump_offsetof (struct itree_node, parent),
          dump_interval_node (ctx, node->parent, offset));
   if (node->left)
       dump_remember_fixup_ptr_raw
         (ctx,
-         offset + dump_offsetof (struct interval_node, left),
+         offset + dump_offsetof (struct itree_node, left),
          dump_interval_node (ctx, node->left, offset));
   if (node->right)
       dump_remember_fixup_ptr_raw
         (ctx,
-         offset + dump_offsetof (struct interval_node, right),
+         offset + dump_offsetof (struct itree_node, right),
          dump_interval_node (ctx, node->right, offset));
   return offset;
 }
diff --git a/src/textprop.c b/src/textprop.c
index b34246f5bc7..45ead993a60 100644
--- a/src/textprop.c
+++ b/src/textprop.c
@@ -634,7 +634,7 @@ get_char_property_and_overlay (Lisp_Object position, register Lisp_Object prop,
   if (BUFFERP (object))
     {
       struct buffer *b = XBUFFER (object);
-      struct interval_node *node;
+      struct itree_node *node;
       struct sortvec items[2];
       struct sortvec *result = NULL;
       Lisp_Object result_tem = Qnil;
diff --git a/src/xdisp.c b/src/xdisp.c
index d585d57fd05..ca7e2820f42 100644
--- a/src/xdisp.c
+++ b/src/xdisp.c
@@ -6534,7 +6534,7 @@ load_overlay_strings (struct it *it, ptrdiff_t charpos)
   struct overlay_entry entriesbuf[20];
   ptrdiff_t size = ARRAYELTS (entriesbuf);
   struct overlay_entry *entries = entriesbuf;
-  struct interval_node *node;
+  struct itree_node *node;
 
   USE_SAFE_ALLOCA;
 
@@ -7001,7 +7001,7 @@ back_to_previous_line_start (struct it *it)
 static bool
 strings_with_newlines (ptrdiff_t startpos, ptrdiff_t endpos, struct window *w)
 {
-  struct interval_node *node;
+  struct itree_node *node;
   /* Process overlays.  */
   ITREE_FOREACH (node, current_buffer->overlays, startpos, endpos, DESCENDING)
     {