Re: line buffer as Red Black Trees instead of linear

[Alin Soare <as1789@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 2272 bytes --]

2014-05-21 18:17 GMT+03:00 Eli Zaretskii <eliz@gnu.org>:

> > Date: Wed, 21 May 2014 11:34:10 +0300
> > From: Alin Soare <as1789@gmail.com>
> > Cc: Stefan Monnier <monnier@iro.umontreal.ca>, emacs-devel@gnu.org
> >
> > Ideally, at each node all the text should have the same properties
> (marks,
> > fonts, etc), and chaging 1 such property can be implemented by splitting
> > the node or removing a few nodes, and their text be preserved in 1 node
> > (only the field owner must be changed when a few nodes are joined in only
> > 1).
>
> That would mean we will need to rearrange the tree each time text
> properties or overlays change, something we avoid today.
>

Yes, each time ! But however, a simple mental computation is still much
faster than now, because the computation is made only 1 for each change,
and there will be lots of simple pre-computations that never repeat. Not
all the attributes will be pre-computed at the creation of the node. Some
attributes, like # of newlines on the text at the left of the node and on
the self will be precomputed at the creation. The Node->marks will be
perhaps precomputed when some mark is added in the text within the node.
Display props are pre-computed when the redisplay-internal requires it, so
kind of lazy.


> Also please note that 'display' properties can specify that Emacs
> displays something entirely different from buffer text, so the display
> engine will still need to consult Lisp strings, in addition to the
> text.  (Yes, it's lots of fun.)
>


What is displayed will be all the time pre-computed for each node, and this
will never be re-computed for that node before modifications. The attribute
NODE->what-to-display-data perhaps will be evaluated at the 1st display,
not at the node creation.

Note also that I will do such that each node keeps not a block of text, but
a linked list of blocks of text, such that to be fast to manipulate
operations like join and split.

Apart from search in buffer and reading the text at a given offset(point),
that will be a little slower because the problem of page cache, all the
other functions will be faster (at a first sight).

We will see. When i start working, I will send you private message to ask
you to read what I did. Try since October on to do it.

[-- Attachment #2: Type: text/html, Size: 3169 bytes --]