Subject: bug#58113: 29.0.50; [noverlay] Segmentation fault while building on macOS

From: Gerd Möllmann <[email-masked]>
Date: Wed, 28 Sep 2022 06:29:33 +0200

Eli Zaretskii <[email-masked]> writes:

>> (lldb) p tree->size
>> (intmax_t) $0 = 26
>> (lldb) p &tree->null
>> (interval_node *) $1 = 0x0000600002c03f08
>> (lldb) p tree->root
>> (interval_node *) $2 = 0x0000600002c03f08
>
> What does tree->null represent?  Does it represent an empty tree?  If
> so, I guess tree->size is not maintained correctly?

I surmise it means the tree is empty.

The tree->null thing reminds me of the MEM_NIL I used in the red-black
tree in alloc.c.  It is sort of a "trick" to make a red-black tree
implementation more "elegant".  Although--one such node per tree looks a
bit odd to me.  But what do I know.

I'll see if I can spot something obvious that goes wrong with the size.
Otherwiese, it would be good if someone who can build an Emacs from the
branch could write some more tests.

[ A more general question is why the existing red-black tree hasn't been
hoisted from alloc.c?  Or even, why not use a ready-made interval tree
like the one in the Linux kernel, which is also an augmented rb-tree?

That would be much more confidence-inducing than this. ]