Markers/intervals/overlays + trees

[Dmitry Antipov <dmantipov@yandex.ru>]

On 08/09/2012 12:44 AM, Eli Zaretskii wrote:
>> From: Stefan Monnier <monnier@IRO.UMontreal.CA>
>> Date: Wed, 08 Aug 2012 15:47:58 -0400
>> Cc: dmantipov@yandex.ru, emacs-devel@gnu.org
>>
>>> FWIW, the display engine uses this division quite a lot.  If we end up
>>> removing it, I suggest to time the code with and without it, e.g. by
>>> timing some modes that are heavy users of overlays.
>>
>> I don't think we need timings.
>
> Not if we aren't getting rid of overlay-recenter, we don't ;-)

The more I do different things around buffers and markers/intervals/overlays,
the more I think that the last three ones represents nearly the same thing,
i.e. "buffer range with properties" (marker is the range of length 0 (or 1,
that's may be the question), and without properties). Is it reasonable/
possible/feasible to generalize them into the only type and use it everywhere?

If not, shouldn't markers and overlays be chained into double-linked lists
instead of single-linked, for the sake of fast unchain/re-chain and in-place sort?

Finally, what about an idea to generalize red-black tree from alloc.c and
use it everywhere when O(log(n)) data structure is needed? I suppose that we
can even avoid our own tree implementation while compiling for GNU/Linux because
glibc trees (tsearch/tfind/etc.) are balanced and good enough in general.

Dmitry