[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
feature/noverlay f421b58db5 4/5: Prefix all itree.h type names with itre
|
From: |
Stefan Monnier |
|
Subject: |
feature/noverlay f421b58db5 4/5: Prefix all itree.h type names with itree_ |
|
Date: |
Wed, 19 Oct 2022 21:40:26 -0400 (EDT) |
branch: feature/noverlay
commit f421b58db5d34f45773a73c699b4b1a5a5b9da03
Author: Matt Armstrong <matt@rfc20.org>
Commit: Stefan Monnier <monnier@iro.umontreal.ca>
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.
---
src/alloc.c | 4 +-
src/buffer.c | 40 +++++++--------
src/buffer.h | 2 +-
src/itree.c | 160 ++++++++++++++++++++++++++++-----------------------------
src/itree.h | 47 +++++++++--------
src/lisp.h | 2 +-
src/pdumper.c | 10 ++--
src/textprop.c | 2 +-
src/xdisp.c | 4 +-
9 files changed, 135 insertions(+), 136 deletions(-)
diff --git a/src/alloc.c b/src/alloc.c
index d7e0a99ffe..a08249b1b1 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 74c6705cbd..228c6e6056 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 afcdfcd9a0..ee0c8dd836 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 f7597ef86a..6d54a36c3b 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 b0f7a1d193..b4116a1fb7 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 7cd7871281..b256d65efc 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 1a2ecea71e..1830c6bd18 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 b34246f5bc..45ead993a6 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 d585d57fd0..ca7e2820f4 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)
{