feature/noverlay 009249e0c6: Remove the per-tree null node

[Gerd Moellmann]

branch: feature/noverlay
commit 009249e0c6d3bb6c4a3714a279ae91807d133c77
Author: Gerd Möllmann <gerd@gnu.org>
Commit: Gerd Möllmann <gerd@gnu.org>

    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 8dc45659b5..db8f39a60e 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 3b354b5640..6d97dd2a71 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 f24b12fcf6..f1ef7f9946 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 4c057117b4..e39f5f1109 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