Re: noverlay branch

[Matt Armstrong]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> Oh, I think you're talking specifically about the complete removal of
> `otick` where a shallower tree would make that less costly.
> Sorry.  I understand quickly, but only after a long explanation.

That and the basic tree operations (find, insert, remove, etc.).

You are right that there is enough essential updating going on in the
tree that perhaps the btree isn't a win.  I haven't thought about it
deeply.


>>> [ FWIW, I'd like to get rid of the `tree->size` field, and thus rely on
>>>   auto-growing more heavily.  ]
>> I rather like the size field.
>
> I agree it has its benefit, which is why I haven't removed it yet:
> I'm not sure.
>
>> I have a different idea about the stacks, though.  Idea: use fixed size
>> stacks, no auto-growing.  120 elements is all that is needed (the max
>> possible depth of a 3-pointer red-black tree on 64 bit architectures).
>> That is 1K memory overhead per traversal, which I think isn't an issue?
>> At least, this is a reasonable choice in other systems I've worked in.
>> Is it reasonable for Emacs?
>
> Maybe you're right.  I think this decision is muddled by the (ab)use of
> stacks as collections of nodes at a few places (where we use
> `interval_stack_push`), where it's not limited to O(log N).

Could most places use a fixed C array (maybe in a simple struct), with
fancy places still using the fancy thing?

Anyway, today 3 tiny patches.  Two improvements, one bug fix.  Also on
https://git.sr.ht/~matta/emacs/log/feature/noverlay.

And now patches...

>From 034d50415858b18b032b116804bfefc1be421bb3 Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Tue, 11 Oct 2022 11:41:47 -0700
Subject: [PATCH 1/3] ; * .clang-format: Add ITREE_FOREACH.

---
 .clang-format | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/.clang-format b/.clang-format
index 44200a3995..ac9f95c88a 100644
--- a/.clang-format
+++ b/.clang-format
@@ -6,7 +6,7 @@ BreakBeforeBinaryOperators: All
 BreakBeforeBraces: GNU
 ColumnLimit: 70
 ContinuationIndentWidth: 2
-ForEachMacros: [FOR_EACH_TAIL, FOR_EACH_TAIL_SAFE]
+ForEachMacros: [FOR_EACH_TAIL, FOR_EACH_TAIL_SAFE, ITREE_FOREACH]
 IncludeCategories:
   - Regex: '^<config\.h>$'
     Priority: -1
-- 
2.35.1

>From fda8723be640593a662d7ff9d4900b7f9e56423e Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Tue, 11 Oct 2022 20:32:08 -0700
Subject: [PATCH 2/3] ; * src/itree.c (check_tree): assert that the tree root
 is black

---
 src/itree.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/src/itree.c b/src/itree.c
index ef623d0850..deef0335cf 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -307,6 +307,7 @@ check_tree (struct interval_tree *tree,
   if (tree->root == ITREE_NULL)
     return true;
   eassert (tree->root->parent == ITREE_NULL);
+  eassert (!check_red_black_invariants || !tree->root->red);
 
   struct interval_node *node = tree->root;
   struct check_subtree_result result
-- 
2.35.1

>From a98497429fcb1369bfe2af9d57820eb94ae380dc Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Tue, 11 Oct 2022 20:19:16 -0700
Subject: [PATCH 3/3] ; * src/itree.c (check_subtree): fix logical error in
 eassert

---
 src/itree.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/src/itree.c b/src/itree.c
index deef0335cf..cd6b0b35f8 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -277,7 +277,8 @@ check_subtree (struct interval_node *node,
   if (check_red_black_invariants)
     {
       eassert (left_result.black_height == right_result.black_height);
-      eassert (node->parent != ITREE_NULL || !node->red || !node->parent->red);
+      eassert (node->parent == ITREE_NULL || !node->red
+               || !node->parent->red);
     }
 
   result.size = 1 + left_result.size + right_result.size;
-- 
2.35.1