From a7ad0f806c1ed82f4d0710111aa92417e04a1110 Mon Sep 17 00:00:00 2001 From: Stefan Monnier Date: Thu, 29 Sep 2022 17:12:21 -0400 Subject: [PATCH] itree: Remove the `visited` flag from the tree nodes These bits really belong in the "workstack" used within `interval_generator_next`, so move them there. * src/itree.c (nodeptr_and_flag): New type; (struct interval_stack): Use it. (make_nav, nav_nodeptr, nav_flag): New functions. (interval_tree_insert_gap, interval_tree_delete_gap): Adjust accordingly. (interval_generator_next): Stash the `visited` bit in the work stack rather than inside the tree nodes. (interval_stack_create, interval_stack_destroy, interval_stack_clear) (interval_stack_ensure_space, interval_stack_push_flagged) (interval_stack_push, interval_stack_pop): Move before first use. * src/itree.h (struct interval_node): Remove `visited` field. * src/pdumper.c (dump_interval_node): Adjust accordingly. --- src/itree.c | 202 +++++++++++++++++++++++++++----------------------- src/itree.h | 1 - src/pdumper.c | 1 - 3 files changed, 109 insertions(+), 95 deletions(-) diff --git a/src/itree.c b/src/itree.c index 7c2602683c4..3b354b56403 100644 --- a/src/itree.c +++ b/src/itree.c @@ -98,13 +98,6 @@ static struct interval_node *interval_tree_validate (struct interval_tree *, str static void interval_generator_ensure_space (struct interval_generator *); static bool interval_node_intersects (const struct interval_node *, ptrdiff_t, ptrdiff_t); static int interval_tree_max_height (const struct interval_tree *); -static struct interval_stack *interval_stack_create (intmax_t); -static void interval_stack_destroy (struct interval_stack *); -static void interval_stack_clear (struct interval_stack *); -static void interval_stack_ensure_space (struct interval_stack *, intmax_t); -static void interval_stack_push (struct interval_stack *, struct interval_node *); -static void interval_stack_push_flagged (struct interval_stack *, struct interval_node *, bool); -static struct interval_node *interval_stack_pop (struct interval_stack *); static void interval_tree_update_limit (const struct interval_tree *, struct interval_node *); static void interval_tree_inherit_offset (const struct interval_tree *, struct interval_node *); static void interval_tree_propagate_limit (const struct interval_tree *, struct interval_node *); @@ -130,10 +123,12 @@ static inline void interval_tree_iter_ensure_space (struct interval_tree *); /* +------------------------------------------------------------------------------------+ */ +typedef uintptr_t nodeptr_and_flag; + /* Simple dynamic array. */ struct interval_stack { - struct interval_node **nodes; + nodeptr_and_flag *nodes; size_t size; size_t length; }; @@ -148,6 +143,97 @@ struct interval_generator enum interval_tree_order order; }; + +/* +===================================================================================+ + * | Stack + * +===================================================================================+ */ + +static inline nodeptr_and_flag +make_nav (struct interval_node *ptr, bool flag) +{ + uintptr_t v = (uintptr_t) ptr; + /* We assume alignment imposes the LSB is clear for us to use it. */ + eassert (!(v & 1)); + return v | !!flag; +} + +static inline struct interval_node * +nav_nodeptr (nodeptr_and_flag nav) +{ + return (struct interval_node *) (nav & (~(uintptr_t)1)); +} + +static inline bool +nav_flag (nodeptr_and_flag nav) +{ + return (bool) (nav & 1); +} + +/* This is just a simple dynamic array with stack semantics. */ + +static struct interval_stack* +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->length = 0; + return stack; +} + +static void +interval_stack_destroy (struct interval_stack *stack) +{ + if (! stack) + return; + if (stack->nodes) + xfree (stack->nodes); + xfree (stack); +} + +static void +interval_stack_clear (struct interval_stack *stack) +{ + stack->length = 0; +} + +static inline void +interval_stack_ensure_space (struct interval_stack *stack, intmax_t nelements) +{ + if (nelements > stack->size) + { + stack->size = (nelements + 1) * 2; + stack->nodes = xrealloc (stack->nodes, stack->size * sizeof (*stack->nodes)); + } +} + +/* Push NODE on the STACK, while settings its visited flag to FLAG. */ + +static inline void +interval_stack_push_flagged (struct interval_stack *stack, + struct interval_node *node, bool flag) +{ + /* FIXME: Isn't this redundant with the calls that are passed + `interval_tree_max_height` before the iteration? */ + interval_stack_ensure_space (stack, stack->length + 1); + + stack->nodes[stack->length] = make_nav (node, flag); + stack->length++; +} + +static inline void +interval_stack_push (struct interval_stack *stack, struct interval_node *node) +{ + interval_stack_push_flagged (stack, node, false); +} + +static inline nodeptr_and_flag +interval_stack_pop (struct interval_stack *stack) +{ + if (stack->length == 0) + return make_nav (NULL, false); + return stack->nodes[--stack->length]; +} /* +===================================================================================+ @@ -525,7 +611,7 @@ interval_tree_insert_gap (struct interval_tree *tree, ptrdiff_t pos, ptrdiff_t l } interval_tree_iter_finish (tree); for (int i = 0; i < saved->length; ++i) - interval_tree_remove (tree, saved->nodes[i]); + interval_tree_remove (tree, nav_nodeptr (saved->nodes[i])); /* We can't use a generator here, because we can't effectively @@ -533,7 +619,9 @@ interval_tree_insert_gap (struct interval_tree *tree, ptrdiff_t pos, ptrdiff_t l const int size = interval_tree_max_height (tree) + 1; struct interval_stack *stack = interval_stack_create (size); interval_stack_push (stack, tree->root); - while ((node = interval_stack_pop (stack))) + nodeptr_and_flag nav; + while ((nav = interval_stack_pop (stack), + node = nav_nodeptr (nav))) { /* Process in pre-order. */ interval_tree_inherit_offset (tree, node); @@ -564,7 +652,8 @@ interval_tree_insert_gap (struct interval_tree *tree, ptrdiff_t pos, ptrdiff_t l interval_stack_destroy (stack); /* Reinsert nodes starting at POS having front-advance. */ - while ((node = interval_stack_pop (saved))) + while ((nav = interval_stack_pop (saved), + node = nav_nodeptr (nav))) { node->begin += length; if (node->end != pos || node->rear_advance) @@ -594,8 +683,10 @@ interval_tree_delete_gap (struct interval_tree *tree, ptrdiff_t pos, ptrdiff_t l struct interval_node *node; interval_stack_push (stack, tree->root); - while ((node = interval_stack_pop (stack))) + nodeptr_and_flag nav; + while ((nav = interval_stack_pop (stack))) { + node = nav_nodeptr (nav); interval_tree_inherit_offset (tree, node); if (node->right != &tree->null) { @@ -705,19 +796,13 @@ interval_generator_next (struct interval_generator *g) needs to be considered but we haven't yet decided whether it's included in the generator's output. */ - /* FIXME: We should move the `visited` flag to the stack: each entry - there should simply consist of a node and a bool (the `visited` status) - so this internal implementation detail doesn't leak into the - `interval_node` structure. - [ In theory it would also allow multiple iterations to be active - at the same time, tho that does not seem particularly useful at - this time and would require further changes anyway. ] - To save space on the stack, we could hijack the LSB bit of the `node*` - word to hold the `visited` bit. */ - do { - while ((node = interval_stack_pop (g->stack)) - && ! node->visited) + nodeptr_and_flag nav; + bool visited; + while ((nav = interval_stack_pop (g->stack), + node = nav_nodeptr (nav), + visited = nav_flag (nav), + node && !visited)) { struct interval_node * const left = node->left; struct interval_node * const right = node->right; @@ -783,75 +868,6 @@ interval_generator_destroy (struct interval_generator *g) xfree (g); } - -/* +===================================================================================+ - * | Stack - * +===================================================================================+ */ - -/* This is just a simple dynamic array with stack semantics. */ - -static struct interval_stack* -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->length = 0; - return stack; -} - -static void -interval_stack_destroy (struct interval_stack *stack) -{ - if (! stack) - return; - if (stack->nodes) - xfree (stack->nodes); - xfree (stack); -} - -static void -interval_stack_clear (struct interval_stack *stack) -{ - stack->length = 0; -} - -static inline void -interval_stack_ensure_space (struct interval_stack *stack, intmax_t nelements) -{ - if (nelements > stack->size) - { - stack->size = (nelements + 1) * 2; - stack->nodes = xrealloc (stack->nodes, stack->size * sizeof (*stack->nodes)); - } -} - -static inline void -interval_stack_push (struct interval_stack *stack, struct interval_node *node) -{ - interval_stack_ensure_space (stack, stack->length + 1); - stack->nodes[stack->length] = node; - stack->length++; -} - -/* Push NODE on the STACK, while settings its visited flag to FLAG. */ - -static inline void -interval_stack_push_flagged (struct interval_stack *stack, - struct interval_node *node, bool flag) -{ - interval_stack_push (stack, node); - node->visited = flag; -} - -static inline struct interval_node* -interval_stack_pop (struct interval_stack *stack) -{ - if (stack->length == 0) - return NULL; - return stack->nodes[--stack->length]; -} - /* +===================================================================================+ * | Internal Functions diff --git a/src/itree.h b/src/itree.h index 8f0454dc7a4..f24b12fcf61 100644 --- a/src/itree.h +++ b/src/itree.h @@ -46,7 +46,6 @@ struct interval_node uintmax_t otick; /* offset modified tick */ Lisp_Object data; /* Exclusively used by the client. */ bool_bf red : 1; - bool_bf visited : 1; /* Internal to `interval_generator_next`. */ bool_bf rear_advance : 1; /* Same as for marker and overlays. */ bool_bf front_advance : 1; /* Same as for marker and overlays. */ }; diff --git a/src/pdumper.c b/src/pdumper.c index 44486015f05..4c057117b4a 100644 --- a/src/pdumper.c +++ b/src/pdumper.c @@ -2155,7 +2155,6 @@ dump_interval_node (struct dump_context *ctx, struct interval_node *node, DUMP_FIELD_COPY (&out, node, otick); dump_field_lv (ctx, &out, node, &node->data, WEIGHT_STRONG); DUMP_FIELD_COPY (&out, node, red); - DUMP_FIELD_COPY (&out, node, visited); DUMP_FIELD_COPY (&out, node, rear_advance); DUMP_FIELD_COPY (&out, node, front_advance); dump_off offset = dump_object_finish (ctx, &out, sizeof (out)); -- 2.39.2