Markers/intervals/overlays + trees

[Dmitry Antipov]

On 08/09/2012 12:44 AM, Eli Zaretskii wrote:
> > From: Stefan Monnier <address@hidden>
> > Date: Wed, 08 Aug 2012 15:47:58 -0400
> > Cc: address@hidden, address@hidden
> >
> > > 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