Re: Markers/intervals/overlays + trees

[Eli Zaretskii]

> Date: Thu, 09 Aug 2012 07:53:48 +0400
> From: Dmitry Antipov <address@hidden>
> CC: Eli Zaretskii <address@hidden>, 
>  Stefan Monnier <address@hidden>
> 
> 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).

They are not necessarily as similar as you make them sound.  I don't
know if the dissimilarities contradict your idea, but they should be
kept in mind:

 . Intervals are basis for text properties, and text properties cannot
   overlap, in the sense that 2 text properties with same property but
   different values cannot span overlapping regions of text.  By
   contrast, overlays with the same property but different values
   _can_ overlap.

 . Text properties can be attached to strings, not just buffers.  The
   other two kinds cannot.

> Is it reasonable/ possible/feasible to generalize them into the only
> type and use it everywhere?

What would be the gains from such a generalization?

> 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?

My gut feeling is that the most important operation is to find an
overlay covering the some buffer position, or the next/previous
overlay from a given position.  Optimization efforts should be
directed to these operations first and foremost.

> 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?

Aren't insertion and deletion more expensive in red-black trees than
in "regular" binary trees?  If they are, this will hurt text
properties performance.  Buffers with an enormous amount of text
properties are quite frequent.

As another data point, the XEmacs "extents", which are (AFAIK) a kind
of text properties and overlays in the same feature, are not
implemented on top of trees.  I dare to assume that this is not
because the designers didn't know about trees.

IOW, I think  little more analysis and initial design is needed before
we can assess the alternatives.