From 5525bd39322a66cf4133a2593d6349e4d75d8b6a Mon Sep 17 00:00:00 2001 From: Stefan Monnier Date: Fri, 18 Nov 2022 11:11:46 -0500 Subject: [PATCH] itree: Make sure a deleted overlay has NULL pointer fields * src/buffer.c (delete_all_overlays): Use POST_ORDER to set the node's pointers to NULL, as god intended. * src/itree.c (itree_insert_node): Uncomment the assertion accordingly. --- src/buffer.c | 17 +++++++---------- src/itree.c | 17 +++++++++++++---- 2 files changed, 20 insertions(+), 14 deletions(-) diff --git a/src/buffer.c b/src/buffer.c index 4da5b451d0f..d948aaa2662 100644 --- a/src/buffer.c +++ b/src/buffer.c @@ -937,19 +937,16 @@ delete_all_overlays (struct buffer *b) if (! b->overlays) return; - /* FIXME: This loop sets the overlays' `buffer` field to NULL but - 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. - Of course, we can't set them to NULL from within the iteration - because the iterator may need them (tho we could if we added - an ITREE_POST_ORDER iteration order). */ - ITREE_FOREACH (node, b->overlays, PTRDIFF_MIN, PTRDIFF_MAX, ASCENDING) + /* The general rule is that the tree cannot be modified from within + ITREE_FOREACH, but here we bend this rule a little because we know + that the POST_ORDER iterator will not need to look at `node` again. */ + ITREE_FOREACH (node, b->overlays, PTRDIFF_MIN, PTRDIFF_MAX, POST_ORDER) { modify_overlay (b, node->begin, node->end); - /* Where are the nodes freed ? --ap */ XOVERLAY (node->data)->buffer = NULL; + node->parent = NULL; + node->left = NULL; + node->right = NULL; } itree_clear (b->overlays); } diff --git a/src/itree.c b/src/itree.c index 7bf3b9507bf..abd060d6fb8 100644 --- a/src/itree.c +++ b/src/itree.c @@ -676,10 +676,8 @@ static void itree_insert_node (struct itree_tree *tree, struct itree_node *node) { eassert (node && node->begin <= node->end); - /* FIXME: The assertion below fails because `delete_all_overlays` - doesn't set left/right/parent to NULL. */ - /* eassert (node->left == NULL && node->right == NULL - && node->parent == NULL) */; + eassert (node->left == NULL && node->right == NULL + && node->parent == NULL); eassert (check_tree (tree, true)); /* FIXME: Too expensive. */ struct itree_node *parent = NULL; @@ -1224,6 +1222,11 @@ static struct itree_node * itree_iter_next_in_subtree (struct itree_node *node, struct itree_iterator *iter) { + /* FIXME: Like in the previous version of the iterator, we + prune based on `limit` only when moving to a left child, + but `limit` can also get smaller when moving to a right child + It's actually fairly common, so maybe it would be worthwhile + to prune a bit more aggressively here. */ struct itree_node *next; switch (iter->order) { @@ -1386,6 +1389,12 @@ itree_iterator_start (struct itree_iterator *iter, iter->end = end; iter->otick = tree->otick; iter->order = order; + /* Beware: the `node` field alwyas holds "the next" node to consider. + so it's always "one node ahead" of what the iterator loop sees. + In most respects this makes no difference, but we depend on this + detail in `delete_all_overlays` where this allows us to modify + the current node knowing that the iterator will not need it to + find the next. */ iter->node = itree_iterator_first_node (tree, iter); return iter; } -- 2.39.5