Re: Overlays as an AA-tree

[Stefan Monnier]

>> > Speaking of which, is the byte position stored in a marker of any
>> > significance in an overlay?  Otherwise I could at least get rid of
>> > those.
>> AFAIK, the byte-position of markers is used, but the byte-position of
>> overlays isn't, so you should be able to get rid of them.
> Why bother?

AFAIK there'd be no benefit at all until/unless you add extra code to
try and use those byte-positions somewhere.
I know of two cases where we use such byte-positions, currently:
- in goto-char, but that never receives an overlay as argument.
- when converting charpos <-> bytepos (where we use the table of
  markers as a kind of cache of existing translations)

The second use would probably better be served by a separate table:
- This hack of (ab)using markers can occasionally lead to bad
  performance because it makes the charpos<->bytepos conversion O(N)
  in the worst case where N is the number of markers which can get very
  large).
- It can also lead to bad performance in the other case: lack of
  markers around the "destination" makes the conversion O(N) in the
  worst case where N is the size of the displacement.


        Stefan