Re: Overlays as an AA-tree

[Andreas Politz]

I stopped working on this, since it wasn't clear where this will be
going (among other things).  But I'm willing to pick it up again.
Following is a fairly concise status-report.

I'm running this branch for some time now, so I'm confident that there
are no obvious hard bugs, by which I mean bugs which would terminate
Emacs.

Even though, there is at least one of those which I haven't being
able to track down yet.  It occurs in a fairly complex situation
(using customize). Probably due to a combination of narrowing and
modifying the buffer, because this is not very well tested.

The branch contains about 300 Lisp- and about 50 C-level test-cases.

I am frequently merging master into it, while pushing to
https://github.com/politza/emacs-noverlay.

The memory allocation in some functions is dynamic, which could be
made static, I assume.  Also, quitting may be a problem in these
cases.  

I think it would be advantageous to represent overlays with identical
start values as a single node by utilizing a linked list.  This would
improve performance in some degenerate cases (from a tree's
perspective), by combining the best aspects of the (current) list and
tree approaches.

We also talked about using the same data-structure for marker, but
there is no work done in this direction currently.

-ap