[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: line buffer as Red Black Trees instead of linear

From: Alin Soare
Subject: Re: line buffer as Red Black Trees instead of linear
Date: Fri, 16 May 2014 10:44:44 +0300

> logarithmic in the worse case.

Not in redisplay.  It always moves to the next character, and
remembers the last place it was at, so it mostly only needs to advance
to the next character.

Whatever are the functions that scan the whole line of a buffer, slowing emacs, this can be improved if the values are precomputed and kept at the tree nodes, and when some change is made at a property, like the font, it will affect only some nodes, where it is precomputed.

The solution of this problem is the red-black trees, by inserting at each node all the pre-computed characteristics of the block of text kept at the given node. Any modification will pre-compute a finite number of nodes, and when need to access them , only a logarithmic # of nodes will be taken in consideration for all possible operations.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]