1 files changed, 16 insertions, 183 deletions

diff --git a/src/itree.c b/src/itree.c
index 9e60071980d..e4d5fb304b7 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -131,33 +131,10 @@ along with GNU Emacs.  If not, see <http://www.gnu.org/licenses/>.  */
  * | Stack
  * +=======================================================================+ */
 
-typedef uintptr_t nodeptr_and_flag;
-
-static inline nodeptr_and_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.  */
-  eassert (!(v & 1));
-  return v | !!flag;
-}
-
-static inline struct itree_node *
-nav_nodeptr (nodeptr_and_flag nav)
-{
-  return (struct itree_node *) (nav & (~(uintptr_t)1));
-}
-
-static inline bool
-nav_flag (nodeptr_and_flag nav)
-{
-  return (bool) (nav & 1);
-}
-
 /* Simple dynamic array. */
 struct itree_stack
 {
-  nodeptr_and_flag *nodes;
+  struct itree_node **nodes;
   size_t size;
   size_t length;
 };
@@ -184,12 +161,6 @@ itree_stack_destroy (struct itree_stack *stack)
   xfree (stack);
 }
 
-static void
-itree_stack_clear (struct itree_stack *stack)
-{
-  stack->length = 0;
-}
-
 static inline void
 itree_stack_ensure_space (struct itree_stack *stack, uintmax_t nelements)
 {
@@ -204,34 +175,20 @@ itree_stack_ensure_space (struct itree_stack *stack, uintmax_t nelements)
 /* Push NODE on the STACK, while settings its visited flag to FLAG. */
 
 static inline void
-itree_stack_push_flagged (struct itree_stack *stack,
-                             struct itree_node *node, bool flag)
+itree_stack_push (struct itree_stack *stack, struct itree_node *node)
 {
   eassert (node);
-
-  /* FIXME: While the stack used in the iterator is bounded by the tree
-     depth and could be easily pre-allocated to a large enough size to avoid
-     this "ensure" check, `itree_stack_push` is also used elsewhere to
-     simply collect some subset of the overlays, where it's only bounded by
-     the total number of overlays in the buffer (which can be large and thus
-     preferably not pre-allocated needlessly).  */
   itree_stack_ensure_space (stack, stack->length + 1);
 
-  stack->nodes[stack->length] = make_nav (node, flag);
+  stack->nodes[stack->length] = node;
   stack->length++;
 }
 
-static inline void
-itree_stack_push (struct itree_stack *stack, struct itree_node *node)
-{
-  itree_stack_push_flagged (stack, node, false);
-}
-
-static inline nodeptr_and_flag
+static inline struct itree_node *
 itree_stack_pop (struct itree_stack *stack)
 {
   if (stack->length == 0)
-    return make_nav (NULL, false);
+    return NULL;
   return stack->nodes[--stack->length];
 }
 
@@ -815,10 +772,7 @@ itree_contains (struct itree_tree *tree, struct itree_node *node)
   struct itree_node *other;
   ITREE_FOREACH (other, tree, node->begin, PTRDIFF_MAX, ASCENDING)
     if (other == node)
-      {
-        ITREE_FOREACH_ABORT ();
-        return true;
-      }
+      return true;
 
   return false;
 }
@@ -1122,7 +1076,7 @@ itree_insert_gap (struct itree_tree *tree,
         }
     }
   for (size_t i = 0; i < saved->length; ++i)
-    itree_remove (tree, nav_nodeptr (saved->nodes[i]));
+    itree_remove (tree, saved->nodes[i]);
 
   /* We can't use an iterator here, because we can't effectively
      narrow AND shift some subtree at the same time.  */
@@ -1131,9 +1085,7 @@ itree_insert_gap (struct itree_tree *tree,
       const int size = itree_max_height (tree) + 1;
       struct itree_stack *stack = itree_stack_create (size);
       itree_stack_push (stack, tree->root);
-      nodeptr_and_flag nav;
-      while ((nav = itree_stack_pop (stack),
-              node = nav_nodeptr (nav)))
+      while ((node = itree_stack_pop (stack)))
         {
           /* Process in pre-order. */
           itree_inherit_offset (tree->otick, node);
@@ -1170,9 +1122,7 @@ itree_insert_gap (struct itree_tree *tree,
 
   /* Reinsert nodes starting at POS having front-advance.  */
   uintmax_t notick = tree->otick;
-  nodeptr_and_flag nav;
-  while ((nav = itree_stack_pop (saved),
-          node = nav_nodeptr (nav)))
+  while ((node = itree_stack_pop (saved)))
     {
       eassert (node->otick == ootick);
       eassert (node->begin == pos);
@@ -1205,10 +1155,8 @@ itree_delete_gap (struct itree_tree *tree,
   struct itree_node *node;
 
   itree_stack_push (stack, tree->root);
-  nodeptr_and_flag nav;
-  while ((nav = itree_stack_pop (stack)))
+  while ((node = itree_stack_pop (stack)))
     {
-      node = nav_nodeptr (nav);
       itree_inherit_offset (tree->otick, node);
       if (pos > node->limit)
         continue;
@@ -1244,16 +1192,6 @@ itree_delete_gap (struct itree_tree *tree,
  * | Iterator
  * +=======================================================================+ */
 
-/* Stop using the iterator. */
-
-void
-itree_iterator_finish (struct itree_iterator *iter)
-{
-  eassert (iter && iter->running);
-  itree_stack_destroy (iter->stack);
-  iter->running = false;
-}
-
 /* Return true, if NODE's interval intersects with [BEGIN, END).
    Note: We always include empty nodes at BEGIN (and not at END),
    but if BEGIN==END, then we don't include non-empty nodes starting
@@ -1436,7 +1374,7 @@ itree_iterator_first_node (struct itree_tree *tree,
 }
 
 /* Start a iterator enumerating all intervals in [BEGIN,END) in the
-   given ORDER.  Only one iterator per tree can be running at any time.  */
+   given ORDER.  */
 
 struct itree_iterator *
 itree_iterator_start (struct itree_iterator *iter,
@@ -1444,133 +1382,28 @@ itree_iterator_start (struct itree_iterator *iter,
                       ptrdiff_t begin, ptrdiff_t end, enum itree_order order)
 {
   eassert (iter);
-  /* eassert (!iter->running); */
-  /* 19 here just avoids starting with a silly-small stack.
-     FIXME: Since this stack only needs to be about 2*max_depth
-     in the worst case, we could completely pre-allocate it to something
-     like word-bit-size * 2 and then never worry about growing it.  */
-  const int size = (tree ? itree_max_height (tree) : 19) + 1;
-  iter->stack = itree_stack_create (size);
-  uintmax_t otick= tree->otick;
   iter->begin = begin;
   iter->end = end;
-  iter->otick = otick;
+  iter->otick = tree->otick;
   iter->order = order;
-  itree_stack_clear (iter->stack);
-  if (begin <= end && tree->root != NULL)
-    itree_stack_push_flagged (iter->stack, tree->root, false);
-  iter->running = true;
-  /* itree_stack_ensure_space (iter->stack,
-                               2 * itree_max_height (tree)); */
   iter->node = itree_iterator_first_node (tree, iter);
   return iter;
 }
 
-static struct itree_node *
-itree_iter_next (struct itree_iterator *iter)
+struct itree_node *
+itree_iterator_next (struct itree_iterator *iter)
 {
   struct itree_node *node = iter->node;
   while (node
          && !itree_node_intersects (node, iter->begin, iter->end))
     {
       node = itree_iter_next_in_subtree (node, iter);
+      eassert (itree_limit_is_stable (node));
     }
   iter->node = node ? itree_iter_next_in_subtree (node, iter) : NULL;
   return 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 itree_node *
-itree_iterator_next (struct itree_iterator *g)
-{
-  eassert (g && g->running);
-
-  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
-     consist of nodes of two types: nodes that we have decided
-     should be returned by the iterator, and nodes which we may
-     need to consider (including checking their children).
-     We start an iteration with a stack containing just the root
-     node marked as "not visited" which means that it (and its children)
-     needs to be considered but we haven't yet decided whether it's included
-     in the iterator's output.  */
-
-  do
-    {
-      nodeptr_and_flag nav;
-      bool visited;
-      while ((nav = itree_stack_pop (g->stack),
-              node = nav_nodeptr (nav),
-              visited = nav_flag (nav),
-              node && !visited))
-        {
-          struct itree_node *const left = node->left;
-          struct itree_node *const right = node->right;
-
-          itree_inherit_offset (g->otick, node);
-          eassert (itree_limit_is_stable (node));
-          switch (g->order)
-            {
-            case ITREE_ASCENDING:
-              if (right != null && node->begin <= g->end)
-                itree_stack_push_flagged (g->stack, right, false);
-              if (itree_node_intersects (node, g->begin, g->end))
-                itree_stack_push_flagged (g->stack, node, true);
-              /* Node's children may still be off-set and we need to add it.  */
-              if (left != null && g->begin <= left->limit + left->offset)
-                itree_stack_push_flagged (g->stack, left, false);
-              break;
-            case ITREE_DESCENDING:
-              if (left != null && g->begin <= left->limit + left->offset)
-                itree_stack_push_flagged (g->stack, left, false);
-              if (itree_node_intersects (node, g->begin, g->end))
-                itree_stack_push_flagged (g->stack, node, true);
-              if (right != null && node->begin <= g->end)
-                itree_stack_push_flagged (g->stack, right, false);
-              break;
-            case ITREE_PRE_ORDER:
-              if (right != null && node->begin <= g->end)
-                itree_stack_push_flagged (g->stack, right, false);
-              if (left != null && g->begin <= left->limit + left->offset)
-                itree_stack_push_flagged (g->stack, left, false);
-              if (itree_node_intersects (node, g->begin, g->end))
-                itree_stack_push_flagged (g->stack, node, true);
-              break;
-            case ITREE_POST_ORDER:
-              if (itree_node_intersects (node, g->begin, g->end))
-                itree_stack_push_flagged (g->stack, node, true);
-              if (right != null && node->begin <= g->end)
-                itree_stack_push_flagged (g->stack, right, false);
-              if (left != null && g->begin <= left->limit + left->offset)
-                itree_stack_push_flagged (g->stack, left, false);
-              break;
-            }
-        }
-      /* Node may have been invalidated by itree_iterator_narrow
-         after it was pushed: Check if it still intersects. */
-    } while (node && ! itree_node_intersects (node, g->begin, g->end));
-
-  struct itree_node *old_node = g->node;
-  struct itree_node *other_node = itree_iter_next (g);
-  if (other_node != node)
-    {
-      fprintf (stderr, "WOW!! %ld..%ld vs %ld..%ld\n",
-               other_node ? other_node->begin : -1,
-               other_node ? other_node->end : -1,
-               node ? node->begin : -1,
-               node ? node->end : -1);
-      fprintf (stderr, "ON=%lx N=%lx OlN=%lx\n", other_node, node,
-               old_node);
-      emacs_abort ();
-    }
-  return node;
-}
-
 /* Limit G to the new interval [BEGIN, END), which must be a subset of
    the current one.  I.E. it can't grow on either side. */
 
@@ -1578,7 +1411,7 @@ void
 itree_iterator_narrow (struct itree_iterator *g,
                        ptrdiff_t begin, ptrdiff_t end)
 {
-  eassert (g && g->running);
+  eassert (g);
   eassert (begin >= g->begin);
   eassert (end <= g->end);
   g->begin = max (begin, g->begin);