[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: noverlay branch
|
From: |
Matt Armstrong |
|
Subject: |
Re: noverlay branch |
|
Date: |
Mon, 10 Oct 2022 20:46:43 -0700 |
Stefan, I read only Eli's reply this morning. Got to yours just now.
Stefan Monnier <monnier@iro.umontreal.ca> writes:
>> I had a different idea of tightening the otree invariant to this:
>>
>> 1) A node's otick must be greater than or equal to its children's.
>
> That's already checked in the current code, right?
Not yet...until...just now. See patches below.
>> 3) All downward tree traversal propagates offsets and otick.
>
> I think we already do that, but if there are places we missed, then yes,
> of course.
Yes, I think we do. The wrinkle is that we don't always start
inheriting at the root, but otick is not updated in that case.
> Regarding `otick`, I can see 2 more options:
> - Get rid of it completely: its sole purpose is to try and keep
> `overlay-start/end` O(1) in the usual case instead of O(log N), but
> I'm not convinced it's worth the cost of propagating `otick` everywhere
> all the time.
> - A halfway point is to keep `otick` but update it more lazily,
> i.e. only update it when we do `overlay-start/end` (e.g. in
> `interval_tree_validate`).
These ideas are simpler but similar in direction to my idea to use a
btree instead. Then some of the "augmentation" could live in btree
arrays, which are a lot faster to traverse and modify in bulk. (pie in
sky idea, maybe for Emacs 30 but more likely 40!).
>> Subject: [PATCH 2/2] Add ./configure --enable-checking=overlays
>
> I think this is going overboard. I'd rather focus on providing good
> "everyday checks" (i.e. cheap checks which help document our invariants,
> controlled by the normal ENABLE_CHECKING) and leave the rest of the
> debugging code under "manual" control rather than expose it as an
> `--enable-checking=` option.
Yes, Eli said the same. I've removed it.
> My assumption here is that once debugged, this overlay code will stay
> untouched for the next many years (based on the past history of our
> overlay code).
Yep, a great reason to have good ENABLE_CHECKING code.
>> +static struct check_subtree_result
>> +check_subtree (struct interval_node *node, uintmax_t tree_otick,
>> + int max_depth, ptrdiff_t offset, ptrdiff_t min_begin,
>> + ptrdiff_t max_begin)
>
> This max_depth also sounds to me like over-engineering.
I'd like to keep max_depth.
My reason for adding it is informed by experience on similar projects.
It is easier to understand an assertion that the tree is too deep than
it is to debug, say, stack overflow when there is a cycle in the link
structure of the tree. It is easier to limit the height of checking if,
indeed, on some night I am diagnosing an unrelated bug but the perf cost
here is too much. With max_depth in place I can easily manually hack up
a functon to verify checks only in a small subset of the tree
(e.g. around a rotation operation, etc.). I've done and benefited from
this sort of thing in the past.
There is a small concrete benefit to it right now. MAX_DEPTH is now
initialized from interval_tree_max_height(), which currently could wildy
under estimate the height and we wouldn't notice (because generator
stacks auto-grow). Since we call that fucntion to make "big enough to
not need growing" stacks, it is nice to have test coverage for it.
I don't like over-engeneering, but I wouldn't call this engineering at
all. It is just an arg and a bit of related code, with some utility,
and a tiny maintenance cost. :-)
>> - /* We don't check the RB invariants here (neither the absence of
>> - red+red nor the equal-black-depth), so that we can use this check
>> - even while the tree is temporarily breaking some of those invarints.
>> */
>> - /* Red nodes cannot have red parents. */
>> - /* eassert (node->parent == ITREE_NULL
>> - || !(node->red && node->parent->red)); */
>> + /* We don't normally check the RB invariants here (neither the
>> + absence of red+red nor the equal-black-depth), so that we can use
>> + this check even while the tree is temporarily breaking some of
>> + those invarints. You can enable them if you want. */
>> + if (false)
>> + {
>> + /* If a node is red then both of its children are black. Red
>> + nodes cannot have red parents. */
>> + if (node->red)
>> + {
>> + eassert (node->left == ITREE_NULL
>> + || node->left->red == false);
>> + eassert (node->right == ITREE_NULL
>> + || node->right->red == false);
>> + eassert (node->parent == ITREE_NULL || !node->parent->red);
>> + }
>> + }
>
> Since we'll be recursing into the children, the first two easserts seem
> redundant with the third (IOW the new code just does the same as the old
> code, only more verbosely and less efficiently :-( ).
> What am I missing?
Good point, I reworked this for simplicity.
>> + result.complete = left_result.complete && right_result.complete;
>> + if (result.complete)
>
> I think all calls to `check_tree` should be complete traversals.
>
> Most of the invariants checked in it are already checked incrementally
> via sprinkled assertions elsewhere, so it's only really useful when
> debugging a concrete known issue where the "local" checks aren't good
> enough.
All `check_tree` calls are complete traversals. If they aren't there is
a bug and an `eassert` will fire.
> We could also include a few "cheap" calls to `check_tree` via `eassert`
> (i.e. calls which we know shouldn't be algorithmically too expensive
> because we're already traversing the whole tree for some other reason,
> e.g. when killing a buffer (e.g. to verify that, at the end of the day,
> we still preversed the RB invariants :-) or maybe during GC).
...I'm not understanding something here. All `check_tree` calls are in
`eassert` already.
>> + {
>> + /* Every path from a node to a descendent leaf contains the same
>> + number of black nodes. Often said this way: all nodes have
>> + the same "black height". */
>> + eassert (left_result.black_height == right_result.black_height);
>
> IIUC this assertion should be conditionalized in the same way as the
> red+red check, since this invariant can be temporarily false.
Done, and now we have `check_tree_no_rb` for the one call site.
At https://git.sr.ht/~matta/emacs/log/feature/noverlay or below.
>From 67b9e89a5aa0052b1abdcd8971a0fa83f52e13a5 Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Mon, 10 Oct 2022 08:48:41 -0700
Subject: [PATCH 1/4] Improve check_subtree
* src/itree.c (struct check_subtree_result): new struct returned by
check_subtree.
(check_subtree): new function, renamed from recurse_check_tree. Add
new black height assertions.
(check_tree): assert that the tree has non-negative size, assert that
limiting to interval_tree_max_height(tree) levels is enough to
traverses the complete tree.
---
src/itree.c | 156 ++++++++++++++++++++++++++++++++++++++++++----------
1 file changed, 126 insertions(+), 30 deletions(-)
diff --git a/src/itree.c b/src/itree.c
index bbab70dac7..aa8a5f7f3b 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -205,14 +205,44 @@ itree_init (void)
iter = interval_generator_create (NULL);
}
-static ptrdiff_t
-recurse_check_tree (struct interval_node *node, uintmax_t tree_otick,
- ptrdiff_t offset, ptrdiff_t min_begin,
- ptrdiff_t max_begin, intmax_t *size)
+struct check_subtree_result
+{
+ /* Were all nodes visited? */
+ bool complete;
+
+ /* Computed node count of the tree. */
+ int size;
+
+ /* Computed limit of the tree (max END). */
+ ptrdiff_t limit;
+
+ /* Computed black height of the tree (count of black nodes from the
+ bottom up to the root). */
+ int black_height;
+};
+
+static struct check_subtree_result
+check_subtree (struct interval_node *node, uintmax_t tree_otick,
+ int max_depth, ptrdiff_t offset, ptrdiff_t min_begin,
+ ptrdiff_t max_begin)
{
+ struct check_subtree_result result = { .complete = false,
+ .size = 0,
+ .limit = PTRDIFF_MIN,
+ .black_height = 0 };
if (node == ITREE_NULL)
- return PTRDIFF_MIN;
- ++*size;
+ {
+ /* Every nil node of a Red-Black tree is black */
+ result.black_height = 1;
+ result.complete = true;
+ return result;
+ };
+
+ if (max_depth == 0)
+ {
+ result.complete = false;
+ return result;
+ }
/* Validate structure. */
eassert (
@@ -221,14 +251,35 @@ recurse_check_tree (struct interval_node *node, uintmax_t
tree_otick,
eassert (node->left == ITREE_NULL || node->left->parent == node);
eassert (node->right == ITREE_NULL || node->right->parent == node);
- /* We don't check the RB invariants here (neither the absence of
- red+red nor the equal-black-depth), so that we can use this check
- even while the tree is temporarily breaking some of those invarints. */
- /* Red nodes cannot have red parents. */
- /* eassert (node->parent == ITREE_NULL
- || !(node->red && node->parent->red)); */
+ /* We don't normally check the RB invariants here (neither the
+ absence of red+red nor the equal-black-depth), so that we can use
+ this check even while the tree is temporarily breaking some of
+ those invarints. You can enable them if you want. */
+ if (false)
+ {
+ /* If a node is red then both of its children are black. Red
+ nodes cannot have red parents. */
+ if (node->red)
+ {
+ eassert (node->left == ITREE_NULL
+ || node->left->red == false);
+ eassert (node->right == ITREE_NULL
+ || node->right->red == false);
+ eassert (node->parent == ITREE_NULL || !node->parent->red);
+ }
+ }
- eassert (node->offset == 0 || node->otick < tree_otick);
+ /* Validate otick. A node's otick must be <= to the tree's otick
+ and <= to its parent's otick.
+
+ Note: we cannot assert that (NODE.otick == NODE.parent.otick)
+ implies (NODE.offset == 0) because interval_tree_inherit_offset()
+ doesn't always update otick. It could, but it is not clear there
+ is a need. */
+ eassert (node->otick <= tree_otick);
+ eassert (node->parent == ITREE_NULL
+ || node->otick <= node->parent->otick);
+ eassert (node->otick != tree_otick || node->offset == 0);
offset += node->offset;
ptrdiff_t begin = node->begin + offset;
@@ -240,29 +291,74 @@ recurse_check_tree (struct interval_node *node, uintmax_t
tree_otick,
eassert (begin <= max_begin);
eassert (end <= limit);
- ptrdiff_t left_limit
- = recurse_check_tree (node->left, tree_otick, offset, min_begin,
- begin, size);
- ptrdiff_t right_limit
- = recurse_check_tree (node->right, tree_otick, offset, begin,
- max_begin, size);
- eassert (left_limit <= limit);
- eassert (right_limit <= limit);
- eassert (limit == max (end, max (left_limit, right_limit)));
- return limit;
+ struct check_subtree_result left_result
+ = check_subtree (node->left, tree_otick, max_depth - 1, offset,
+ min_begin, begin);
+ struct check_subtree_result right_result
+ = check_subtree (node->right, tree_otick, max_depth - 1, offset,
+ begin, max_begin);
+
+ eassert (left_result.limit <= limit);
+ eassert (right_result.limit <= limit);
+
+ result.complete = left_result.complete && right_result.complete;
+ if (result.complete)
+ {
+ /* Every path from a node to a descendent leaf contains the same
+ number of black nodes. Often said this way: all nodes have
+ the same "black height". */
+ eassert (left_result.black_height == right_result.black_height);
+ result.black_height
+ = (node->red ? 0 : 1) + left_result.black_height;
+
+ result.size = 1 + left_result.size + right_result.size;
+ result.limit
+ = max (end, max (left_result.limit, right_result.limit));
+
+ eassert (limit == result.limit);
+ }
+
+ return result;
}
+/* Validate invariants for TREE.
+
+ This runs in constant time when ENABLE_OVERLAY_CHECKING is 0
+ (i.e. Emacs is not configured with
+ "--enable_checking=yes,overlays"). In this mode it can't check all
+ the invariants. When ENABLE_OVERLAY_CHECKING is 1 it checks the
+ entire tree and validates all invariants.
+*/
static bool
check_tree (struct interval_tree *tree)
{
eassert (tree != NULL);
+ eassert (tree->size >= 0);
eassert ((tree->size == 0) == (tree->root == ITREE_NULL));
if (tree->root == ITREE_NULL)
return true;
- intmax_t size = 0;
- recurse_check_tree (tree->root, tree->otick, 0,
- PTRDIFF_MIN, PTRDIFF_MAX, &size);
+ /* Limit the traversal depth to what 'interval_tree_max_height'
+ returns. Later, verify that this is enough height to traverse
+ the complete tree. */
+ const int max_height = interval_tree_max_height (tree);
+ eassert (max_height >= 0);
+ eassert (max_height <= 120);
+
+ /* NOTE: if this check is too expensive an easy fix is to reduce
+ max_height to for large trees, then relax the assertion on
+ result.complete. Assertions in check_subtree will still be made
+ at the bottom of the tree (where they are probably most
+ interesting), but some will be skipped closer to the root. */
+
+ struct interval_node *node = tree->root;
+ struct check_subtree_result result
+ = check_subtree (node, tree->otick, max_height, node->offset,
+ PTRDIFF_MIN, PTRDIFF_MAX);
+ eassert (result.complete);
+ eassert (result.size == tree->size);
+
+ /* The only way this function fails is eassert(). */
return true;
}
@@ -1145,10 +1241,10 @@ interval_tree_inherit_offset (uintmax_t otick, struct
interval_node *node)
}
/* Offsets can be inherited from dirty nodes (with out of date
- otick) during insert and remove. Offsets aren't inherited
- downward from the root for these operations so rotations are
- performed on potentially "dirty" nodes, where we only make sure
- the *local* offsets are all zero. */
+ otick) during removal, since we do not travel down from the root
+ in that case. In this case rotations are performed on
+ potentially "dirty" nodes, where we only need to make sure the
+ *local* offsets are zero. */
if (node->offset)
{
--
2.35.1
>From 51a8e375ebea2e6e05eed623bddfb323b8e408f0 Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Mon, 10 Oct 2022 09:07:42 -0700
Subject: [PATCH 2/4] Check red-black invariants in most places
Stefan recently disabled this but I happened to want it back soon
after.
* src/itree.c (check_subtree): new arg: allow_red_red
(check_tree_common): renamed from check_tree, pass allow_red_red
through.
(check_tree): new function, pass allow_red_red=false
(interval_tree_insert): check_tree -> check_tree_common with
allow_red_red=true.
---
src/itree.c | 80 ++++++++++++++++++++++++++++++-----------------------
1 file changed, 46 insertions(+), 34 deletions(-)
diff --git a/src/itree.c b/src/itree.c
index aa8a5f7f3b..7ac400398b 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -222,7 +222,8 @@ itree_init (void)
};
static struct check_subtree_result
-check_subtree (struct interval_node *node, uintmax_t tree_otick,
+check_subtree (struct interval_node *node,
+ bool check_red_black_invariants, uintmax_t tree_otick,
int max_depth, ptrdiff_t offset, ptrdiff_t min_begin,
ptrdiff_t max_begin)
{
@@ -251,23 +252,9 @@ check_subtree (struct interval_node *node, uintmax_t
tree_otick,
eassert (node->left == ITREE_NULL || node->left->parent == node);
eassert (node->right == ITREE_NULL || node->right->parent == node);
- /* We don't normally check the RB invariants here (neither the
- absence of red+red nor the equal-black-depth), so that we can use
- this check even while the tree is temporarily breaking some of
- those invarints. You can enable them if you want. */
- if (false)
- {
- /* If a node is red then both of its children are black. Red
- nodes cannot have red parents. */
- if (node->red)
- {
- eassert (node->left == ITREE_NULL
- || node->left->red == false);
- eassert (node->right == ITREE_NULL
- || node->right->red == false);
- eassert (node->parent == ITREE_NULL || !node->parent->red);
- }
- }
+ /* No red nodes have red parents. */
+ if (check_red_black_invariants && node->parent != ITREE_NULL)
+ eassert (!node->red || !node->parent->red);
/* Validate otick. A node's otick must be <= to the tree's otick
and <= to its parent's otick.
@@ -292,11 +279,13 @@ check_subtree (struct interval_node *node, uintmax_t
tree_otick,
eassert (end <= limit);
struct check_subtree_result left_result
- = check_subtree (node->left, tree_otick, max_depth - 1, offset,
- min_begin, begin);
+ = check_subtree (node->left, check_red_black_invariants,
+ tree_otick, max_depth - 1, offset, min_begin,
+ begin);
struct check_subtree_result right_result
- = check_subtree (node->right, tree_otick, max_depth - 1, offset,
- begin, max_begin);
+ = check_subtree (node->right, check_red_black_invariants,
+ tree_otick, max_depth - 1, offset, begin,
+ max_begin);
eassert (left_result.limit <= limit);
eassert (right_result.limit <= limit);
@@ -304,24 +293,29 @@ check_subtree (struct interval_node *node, uintmax_t
tree_otick,
result.complete = left_result.complete && right_result.complete;
if (result.complete)
{
- /* Every path from a node to a descendent leaf contains the same
- number of black nodes. Often said this way: all nodes have
- the same "black height". */
- eassert (left_result.black_height == right_result.black_height);
- result.black_height
- = (node->red ? 0 : 1) + left_result.black_height;
-
result.size = 1 + left_result.size + right_result.size;
result.limit
= max (end, max (left_result.limit, right_result.limit));
eassert (limit == result.limit);
+
+ if (check_red_black_invariants)
+ {
+ /* Every path from a node to a descendent leaf contains the
+ same number of black nodes. Often said this way: all
+ nodes have the same "black height". */
+ eassert (left_result.black_height
+ == right_result.black_height);
+ result.black_height
+ = (node->red ? 0 : 1) + left_result.black_height;
+ }
}
return result;
}
-/* Validate invariants for TREE.
+/* Validate invariants for TREE. If CHECK_RED_BLACK_INVARIANTS, red
+ nodes with red children are considered invalid.
This runs in constant time when ENABLE_OVERLAY_CHECKING is 0
(i.e. Emacs is not configured with
@@ -330,7 +324,8 @@ check_subtree (struct interval_node *node, uintmax_t
tree_otick,
entire tree and validates all invariants.
*/
static bool
-check_tree (struct interval_tree *tree)
+check_tree_common (struct interval_tree *tree,
+ bool check_red_black_invariants)
{
eassert (tree != NULL);
eassert (tree->size >= 0);
@@ -353,8 +348,9 @@ check_tree (struct interval_tree *tree)
struct interval_node *node = tree->root;
struct check_subtree_result result
- = check_subtree (node, tree->otick, max_height, node->offset,
- PTRDIFF_MIN, PTRDIFF_MAX);
+ = check_subtree (node, check_red_black_invariants, tree->otick,
+ max_height, node->offset, PTRDIFF_MIN,
+ PTRDIFF_MAX);
eassert (result.complete);
eassert (result.size == tree->size);
@@ -362,6 +358,22 @@ check_tree (struct interval_tree *tree)
return true;
}
+/* Check the tree with all invariant checks enabled. */
+static bool
+check_tree (struct interval_tree *tree)
+{
+ return check_tree_common (tree, true);
+}
+
+/* Check the tree with all invariant checks enabled, except for the
+ red-black tree invariants. Useful for asserting the other
+ invariants while inserting or removing. */
+static bool
+check_tree_no_rb (struct interval_tree *tree)
+{
+ return check_tree_common (tree, false);
+}
+
/*
+===================================================================================+
* | Stack
*
+===================================================================================+
*/
@@ -626,7 +638,7 @@ interval_tree_insert (struct interval_tree *tree, struct
interval_node *node)
/* Fix/update the tree */
++tree->size;
- eassert (check_tree (tree));
+ eassert (check_tree_no_rb (tree));
interval_tree_insert_fix (tree, node);
}
--
2.35.1
>From a154259bfacf7f1406794a952e80a8197b9a83fb Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Mon, 10 Oct 2022 08:32:56 -0700
Subject: [PATCH 3/4] Simplify itree_null initialization
* src/itree.c (null_is_sane): call eassert directly, check
REAR_ADVANCE, FRONT_ADVANCE. Add FIXME that PARENT is still
read/write.
(itree_null): initialize statically
(itree_init): remove initialization code, call eassert(null_is_sane())
(check_tree_common): call eassert (null_is_sane())
---
src/itree.c | 52 ++++++++++++++++++++++++++++++++++++----------------
1 file changed, 36 insertions(+), 16 deletions(-)
diff --git a/src/itree.c b/src/itree.c
index 7ac400398b..d9f9ec8cd6 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -145,19 +145,42 @@ Copyright (C) 2017-2022 Free Software Foundation, Inc.
static void interval_tree_insert (struct interval_tree *, struct interval_node
*);
/* The sentinel node, the null node. */
-struct interval_node itree_null;
+struct interval_node itree_null = {
+ .parent = &itree_null,
+ .left = &itree_null,
+ .right = &itree_null,
+ .begin = PTRDIFF_MIN,
+ .end = PTRDIFF_MIN,
+ .limit = PTRDIFF_MIN, /* => max(x, null.limit) = x */
+ .offset = 0,
+ .otick = 0,
+ .red = false,
+ .rear_advance = false,
+ .front_advance = false,
+};
static bool
null_is_sane (void)
{
- /* The sentinel node has most of its fields read-only, except for `parent`,
- `left`, `right` which are write only. */
- return itree_null.red == false
- && itree_null.otick == 0
- && itree_null.offset == 0
- && itree_null.begin == PTRDIFF_MIN
- && itree_null.end == PTRDIFF_MIN
- && itree_null.limit == PTRDIFF_MIN;
+ /* The sentinel node has most of its fields read-only.
+
+ FIXME: PARENT is still read/write. It is written to
+ ininterval_tree_transplant, and later read. --matt
+ */
+ /* eassert (itree_null.parent == &itree_null); */
+ eassert (itree_null.left == &itree_null);
+ eassert (itree_null.right == &itree_null);
+ eassert (itree_null.begin == PTRDIFF_MIN);
+ eassert (itree_null.end == PTRDIFF_MIN);
+ eassert (itree_null.limit == PTRDIFF_MIN);
+ eassert (itree_null.offset == 0);
+ eassert (itree_null.otick == 0);
+ eassert (itree_null.red == false);
+ eassert (itree_null.rear_advance == false);
+ eassert (itree_null.front_advance == false);
+
+ /* if we get this far things must be good */
+ return true;
}
/*
+------------------------------------------------------------------------------------+
*/
@@ -195,13 +218,8 @@ null_is_sane (void)
static void
itree_init (void)
{
- 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;
+ eassert (null_is_sane ());
+
iter = interval_generator_create (NULL);
}
@@ -327,6 +345,8 @@ check_subtree (struct interval_node *node,
check_tree_common (struct interval_tree *tree,
bool check_red_black_invariants)
{
+ eassert (null_is_sane ());
+
eassert (tree != NULL);
eassert (tree->size >= 0);
eassert ((tree->size == 0) == (tree->root == ITREE_NULL));
--
2.35.1
>From da0387f0fe79f577fae6d5453c758f600e1ae495 Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Mon, 10 Oct 2022 10:45:05 -0700
Subject: [PATCH 4/4] Stop reading and writing the itree_null.parent field
entirely.
With this change all fields in the itree_null sentinel are read only.
This makes accessing itree_null thread safe in an obvious way.
Because it took two commits from two peole to get this right, I think
we can call this design fragile and difficult to reason about.
Another benefit of this commit is as preparation for removing sentinel
node completely, and just using NULL.
* src/itree.c (itree_null): Statically initialize itree_null.parent to
NULL. It is never accessed.
(null_is_sane): Assert parent == NULL.
(interval_tree_remove_fix): Remove unecessary assignments to parent
from node->parent. These were the last places itree_null.parent were
read.
(interval_tree_remove): Avoid an assignment to itree_null.parent
through min->right->parent.
(interval_tree_transplant): Avoid an assignment to itree_null.parent
through source->parent.
---
src/itree.c | 20 +++++++-------------
1 file changed, 7 insertions(+), 13 deletions(-)
diff --git a/src/itree.c b/src/itree.c
index d9f9ec8cd6..9c5d8ce142 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -146,7 +146,7 @@ Copyright (C) 2017-2022 Free Software Foundation, Inc.
/* The sentinel node, the null node. */
struct interval_node itree_null = {
- .parent = &itree_null,
+ .parent = NULL, /* never accessed */
.left = &itree_null,
.right = &itree_null,
.begin = PTRDIFF_MIN,
@@ -162,12 +162,8 @@ Copyright (C) 2017-2022 Free Software Foundation, Inc.
static bool
null_is_sane (void)
{
- /* The sentinel node has most of its fields read-only.
-
- FIXME: PARENT is still read/write. It is written to
- ininterval_tree_transplant, and later read. --matt
- */
- /* eassert (itree_null.parent == &itree_null); */
+ /* All sentinel node fields are read-only. */
+ eassert (itree_null.parent == NULL);
eassert (itree_null.left == &itree_null);
eassert (itree_null.right == &itree_null);
eassert (itree_null.begin == PTRDIFF_MIN);
@@ -742,7 +738,6 @@ interval_tree_remove_fix (struct interval_tree *tree,
other->red = false;
parent->red = true;
interval_tree_rotate_left (tree, parent);
- parent = node->parent;
other = parent->right;
}
@@ -761,7 +756,6 @@ interval_tree_remove_fix (struct interval_tree *tree,
other->left->red = false;
other->red = true;
interval_tree_rotate_right (tree, other);
- parent = node->parent;
other = parent->right;
}
other->red = parent->red; /* 4.a */
@@ -781,7 +775,6 @@ interval_tree_remove_fix (struct interval_tree *tree,
other->red = false;
parent->red = true;
interval_tree_rotate_right (tree, parent);
- parent = node->parent;
other = parent->left;
}
@@ -800,7 +793,6 @@ interval_tree_remove_fix (struct interval_tree *tree,
other->right->red = false;
other->red = true;
interval_tree_rotate_left (tree, other);
- parent = node->parent;
other = parent->left;
}
@@ -881,7 +873,8 @@ interval_tree_remove (struct interval_tree *tree, struct
interval_node *node)
interval_tree_transplant (tree, min, node);
/* We set min->right->parent after `interval_tree_transplant` so
that calls to `itree_total_offset` don't get stuck in an inf-loop. */
- min->right->parent = min;
+ if (min->right != ITREE_NULL)
+ min->right->parent = min;
interval_tree_update_limit (min);
/* This call "belongs" with the first `interval_tree_transplant`
(of `min_right`, done earlier in the `if`) but we prefer to do it
@@ -1508,7 +1501,8 @@ interval_tree_transplant (struct interval_tree *tree,
struct interval_node *sour
else
dest->parent->right = source;
- source->parent = dest->parent;
+ if (source != ITREE_NULL)
+ source->parent = dest->parent;
}
--
2.35.1
- Re: noverlay branch, (continued)
- Re: noverlay branch, Matt Armstrong, 2022/10/07
- Re: noverlay branch, Stefan Monnier, 2022/10/07
- Re: noverlay branch, Matt Armstrong, 2022/10/08
- Re: noverlay branch, Matt Armstrong, 2022/10/08
- Re: noverlay branch, Stefan Monnier, 2022/10/09
- Re: noverlay branch, Stefan Monnier, 2022/10/09
- Re: noverlay branch, Matt Armstrong, 2022/10/09
- Re: noverlay branch, Eli Zaretskii, 2022/10/10
- Re: noverlay branch, Matt Armstrong, 2022/10/10
- Re: noverlay branch, Stefan Monnier, 2022/10/10
- Re: noverlay branch,
Matt Armstrong <=
- Re: noverlay branch, Stefan Monnier, 2022/10/11
- Re: noverlay branch, Matt Armstrong, 2022/10/11
- Re: noverlay branch, Stefan Monnier, 2022/10/11
- Re: noverlay branch, Matt Armstrong, 2022/10/12
- Re: noverlay branch, Stefan Monnier, 2022/10/12
- Re: noverlay branch, Matt Armstrong, 2022/10/12
- Re: noverlay branch, Stefan Monnier, 2022/10/13
- Re: noverlay branch, Stefan Monnier, 2022/10/09
- Re: noverlay branch, Emanuel Berg, 2022/10/10
- Re: noverlay branch, Matt Armstrong, 2022/10/10