Re: Markers/intervals/overlays + trees

[Stefan Monnier <monnier@iro.umontreal.ca>]

> 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),

Definitely 0.

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

As mentioned elsewhere, we could/should move overlays to the tree
currently used for text-properties (using the "augmented tree" approach
described in http://en.wikipedia.org/wiki/Interval_tree, and using the
"interval tree" of text-properties as the simple underlying balanced
binary tree).

This wouldn't quite merge text-properties and overlays (the two concepts
are subtly different), but it would bring the implementation of the two
closer and should make overlays a lot more scalable/efficient.

I suspect that once this is done, markers wouldn't matter much any more
(because overlays wouldn't use them internally), so we could keep the
current implementation or turn them into "degenerate overlays".

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

Not sure it's worth the trouble:
- doubly-linked lists wouldn't speed up chaining.
- while unchaining would be faster, this is normally not a common
  operation (hopefully most markers should be unchained lazily in batch
  by the GC, which can do it efficiently).
  Of course, this is only true of real markers, not of overlay's markers
  since these aren't implicitly reclaimed by the GC.
- sorting would slow down insertion and would only speed up other
  operations by a factor 2 (you only need to traverse half the list on
  average).  When the list is long enough to be a problem, a factor 2 is
  not sufficient, we need algorithmic improvement.

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

If we have to provide our own implementation in some cases, then we may
as well use it everywhere.  OTOH we could maybe use Glib's trees.
It would probably be fairly easy to do for alloc.c's redblack trees, but
changing text-properties's intervals trees to some "standard" balanced
tree library would probably take more work.

Also it would be less efficient since every node would be split into the
"tree node" and the "value node".


        Stefan