From 009249e0c6d3bb6c4a3714a279ae91807d133c77 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Gerd=20M=C3=B6llmann?= Date: Fri, 30 Sep 2022 13:25:15 +0200 Subject: [PATCH] Remove the per-tree null node "make check" shows 0 unexpcted. * src/itree.h (itree_null): Declare extern. (ITREE_NULL): New macro (struct interval_tree): Remove null member. * src/alloc.c (mark_overlays): Use ITREE_NULL. * src/itree.c: Use ITREE_NULL insteads of a tree's null. * src/pdumper.c (dump_buffer): Use ITREE_NULL. --- src/alloc.c | 2 +- src/itree.c | 81 ++++++++++++++++++++++++++++++--------------------- src/itree.h | 5 +++- src/pdumper.c | 3 +- 4 files changed, 54 insertions(+), 37 deletions(-) diff --git a/src/alloc.c b/src/alloc.c index 8dc45659b50..db8f39a60e0 100644 --- a/src/alloc.c +++ b/src/alloc.c @@ -6519,7 +6519,7 @@ mark_overlays (struct interval_tree *it, struct interval_node *in) they use the `null` node instead when the overlay is not deleted (i.e. is within an overlay tree). */ eassert (in); - if (in == &it->null) + if (in == ITREE_NULL) return; mark_object (in->data); diff --git a/src/itree.c b/src/itree.c index 3b354b56403..6d97dd2a715 100644 --- a/src/itree.c +++ b/src/itree.c @@ -119,6 +119,14 @@ static inline struct interval_node* interval_generator_next (struct interval_generator *g); static inline void interval_tree_iter_ensure_space (struct interval_tree *); +/* The sentinel node, the null node. */ +struct interval_node itree_null; + +static void +init_itree_null (void) +{ + itree_null.parent = itree_null.left = itree_null.right = ITREE_NULL; +} /* +------------------------------------------------------------------------------------+ */ @@ -302,6 +310,11 @@ interval_node_set_region (struct interval_tree *tree, struct interval_tree* interval_tree_create (void) { + /* FIXME? Maybe avoid the initialization of itree_null in the same + way that is used to call mem_init in alloc.c? It's not really + important though. */ + init_itree_null (); + struct interval_tree *tree = xmalloc (sizeof (*tree)); interval_tree_clear (tree); tree->iter = interval_generator_create (tree); @@ -313,13 +326,15 @@ interval_tree_create (void) void interval_tree_clear (struct interval_tree *tree) { - struct interval_node *null = &tree->null; + /* FIXME: Why is this done? */ + struct interval_node *null = ITREE_NULL; null->left = null->right = null->parent = null; null->offset = null->otick = 0; null->begin = PTRDIFF_MIN; null->end = PTRDIFF_MIN; null->limit = PTRDIFF_MIN; /* => max(x, null.limit) = x */ null->red = false; + tree->root = null; tree->otick = 1; tree->size = 0; @@ -364,15 +379,15 @@ interval_tree_size (struct interval_tree *tree) void interval_tree_insert (struct interval_tree *tree, struct interval_node *node) { - eassert (node && node->begin <= node->end && node != &tree->null); + eassert (node && node->begin <= node->end && node != ITREE_NULL); - struct interval_node *parent = &tree->null; + struct interval_node *parent = ITREE_NULL; struct interval_node *child = tree->root; ptrdiff_t offset = 0; /* Find the insertion point, accumulate node's offset and update ancestors limit values. */ - while (child != &tree->null) + while (child != ITREE_NULL) { parent = child; offset += child->offset; @@ -383,7 +398,7 @@ interval_tree_insert (struct interval_tree *tree, struct interval_node *node) } /* Insert the node */ - if (parent == &tree->null) + if (parent == ITREE_NULL) tree->root = node; else if (node->begin <= parent->begin) parent->left = node; @@ -392,8 +407,8 @@ interval_tree_insert (struct interval_tree *tree, struct interval_node *node) /* Init the node */ node->parent = parent; - node->left = &tree->null; - node->right = &tree->null; + node->left = ITREE_NULL; + node->right = ITREE_NULL; node->red = true; node->offset = 0; node->begin -= offset; @@ -433,10 +448,10 @@ interval_tree_remove (struct interval_tree *tree, struct interval_node *node) struct interval_node *broken = NULL; interval_tree_inherit_offset (tree, node); - if (node->left == &tree->null || node->right == &tree->null) + if (node->left == ITREE_NULL || node->right == ITREE_NULL) { - struct interval_node *subst = - (node->right == &tree->null) ? node->left : node->right; + struct interval_node *subst + = node->right == ITREE_NULL ? node->left : node->right; if (!node->red) broken = subst; interval_tree_transplant (tree, subst, node); @@ -472,7 +487,7 @@ interval_tree_remove (struct interval_tree *tree, struct interval_node *node) node->right = node->left = node->parent = NULL; --tree->size; - eassert (tree->size == 0 || (tree->size > 0 && tree->root != &tree->null)); + eassert (tree->size == 0 || (tree->size > 0 && tree->root != ITREE_NULL)); return node; } @@ -481,7 +496,7 @@ static struct interval_node* interval_tree_validate (struct interval_tree *tree, struct interval_node *node) { - if (tree->otick == node->otick || node == &tree->null) + if (tree->otick == node->otick || node == ITREE_NULL) return node; if (node != tree->root) interval_tree_validate (tree, node->parent); @@ -625,7 +640,7 @@ interval_tree_insert_gap (struct interval_tree *tree, ptrdiff_t pos, ptrdiff_t l { /* Process in pre-order. */ interval_tree_inherit_offset (tree, node); - if (node->right != &tree->null) + if (node->right != ITREE_NULL) { if (node->begin > pos) { @@ -636,7 +651,7 @@ interval_tree_insert_gap (struct interval_tree *tree, ptrdiff_t pos, ptrdiff_t l else interval_stack_push (stack, node->right); } - if (node->left != &tree->null + if (node->left != ITREE_NULL && pos <= node->left->limit + node->left->offset) interval_stack_push (stack, node->left); @@ -688,7 +703,7 @@ interval_tree_delete_gap (struct interval_tree *tree, ptrdiff_t pos, ptrdiff_t l { node = nav_nodeptr (nav); interval_tree_inherit_offset (tree, node); - if (node->right != &tree->null) + if (node->right != ITREE_NULL) { if (node->begin > pos + length) { @@ -699,7 +714,7 @@ interval_tree_delete_gap (struct interval_tree *tree, ptrdiff_t pos, ptrdiff_t l else interval_stack_push (stack, node->right); } - if (node->left != &tree->null + if (node->left != ITREE_NULL && pos <= node->left->limit + node->left->offset) interval_stack_push (stack, node->left); @@ -783,7 +798,7 @@ interval_generator_next (struct interval_generator *g) { if (! g) return NULL; - struct interval_node * const null = &g->tree->null; + struct interval_node * const null = ITREE_NULL; struct interval_node *node; /* The `visited` flag stored in each node is used here (and only here): @@ -879,7 +894,7 @@ static void interval_tree_update_limit (const struct interval_tree *tree, struct interval_node *node) { - if (node == &tree->null) + if (node == ITREE_NULL) return; node->limit = max (node->end, max (node->left->limit + node->left->offset, @@ -903,9 +918,9 @@ interval_tree_inherit_offset (const struct interval_tree *tree, node->begin += node->offset; node->end += node->offset; node->limit += node->offset; - if (node->left != &tree->null) + if (node->left != ITREE_NULL) node->left->offset += node->offset; - if (node->right != &tree->null) + if (node->right != ITREE_NULL) node->right->offset += node->offset; node->offset = 0; if (node == tree->root || node->parent->otick == tree->otick) @@ -923,9 +938,9 @@ static void interval_tree_propagate_limit (const struct interval_tree *tree, struct interval_node *node) { - if (node == &tree->null) + if (node == ITREE_NULL) node = node->parent; - if (node == &tree->null) + if (node == ITREE_NULL) return; while (1) { @@ -945,7 +960,7 @@ interval_tree_propagate_limit (const struct interval_tree *tree, static void interval_tree_rotate_left (struct interval_tree *tree, struct interval_node *node) { - eassert (node->right != &tree->null); + eassert (node->right != ITREE_NULL); struct interval_node *right = node->right; @@ -954,11 +969,11 @@ interval_tree_rotate_left (struct interval_tree *tree, struct interval_node *nod /* Turn right's left subtree into node's right subtree. */ node->right = right->left; - if (right->left != &tree->null) + if (right->left != ITREE_NULL) right->left->parent = node; /* right's parent was node's parent. */ - if (right != &tree->null) + if (right != ITREE_NULL) right->parent = node->parent; /* Get the parent to point to right instead of node. */ @@ -974,7 +989,7 @@ interval_tree_rotate_left (struct interval_tree *tree, struct interval_node *nod /* Put node on right's left. */ right->left = node; - if (node != &tree->null) + if (node != ITREE_NULL) node->parent = right; /* Order matters here. */ @@ -987,7 +1002,7 @@ interval_tree_rotate_left (struct interval_tree *tree, struct interval_node *nod static void interval_tree_rotate_right (struct interval_tree *tree, struct interval_node *node) { - eassert (tree && node && node->left != &tree->null); + eassert (tree && node && node->left != ITREE_NULL); struct interval_node *left = node->left; @@ -995,10 +1010,10 @@ interval_tree_rotate_right (struct interval_tree *tree, struct interval_node *no interval_tree_inherit_offset (tree, left); node->left = left->right; - if (left->right != &tree->null) + if (left->right != ITREE_NULL) left->right->parent = node; - if (left != &tree->null) + if (left != ITREE_NULL) left->parent = node->parent; if (node != tree->root) { @@ -1011,7 +1026,7 @@ interval_tree_rotate_right (struct interval_tree *tree, struct interval_node *no tree->root = left; left->right = node; - if (node != &tree->null) + if (node != ITREE_NULL) node->parent = left; interval_tree_update_limit (tree, left); @@ -1180,7 +1195,7 @@ static void interval_tree_transplant (struct interval_tree *tree, struct interval_node *source, struct interval_node *dest) { - eassert (tree && source && dest && dest != &tree->null); + eassert (tree && source && dest && dest != ITREE_NULL); if (dest == tree->root) tree->root = source; @@ -1196,9 +1211,9 @@ interval_tree_transplant (struct interval_tree *tree, struct interval_node *sour static struct interval_node* interval_tree_subtree_min (const struct interval_tree *tree, struct interval_node *node) { - if (node == &tree->null) + if (node == ITREE_NULL) return node; - while (node->left != &tree->null) + while (node->left != ITREE_NULL) node = node->left; return node; } diff --git a/src/itree.h b/src/itree.h index f24b12fcf61..f1ef7f99463 100644 --- a/src/itree.h +++ b/src/itree.h @@ -50,10 +50,13 @@ struct interval_node bool_bf front_advance : 1; /* Same as for marker and overlays. */ }; +/* The sentinel node, the null node. */ +extern struct interval_node itree_null; +#define ITREE_NULL (&itree_null) + struct interval_tree { struct interval_node *root; - struct interval_node null; /* The tree's version of NULL. */ uintmax_t otick; /* offset tick, compared with node's otick. */ intmax_t size; /* Number of nodes in the tree. */ struct interval_generator *iter; diff --git a/src/pdumper.c b/src/pdumper.c index 4c057117b4a..e39f5f1109f 100644 --- a/src/pdumper.c +++ b/src/pdumper.c @@ -2863,8 +2863,7 @@ dump_buffer (struct dump_context *ctx, const struct buffer *in_buffer) DUMP_FIELD_COPY (out, buffer, inhibit_buffer_hooks); DUMP_FIELD_COPY (out, buffer, long_line_optimizations_p); - if (buffer->overlays - && (buffer->overlays->root != &buffer->overlays->null)) + if (buffer->overlays && buffer->overlays->root != ITREE_NULL) /* We haven't implemented the code to dump overlays. */ emacs_abort (); else -- 2.39.2