Hi,
I am writing a tutorial about red-black trees, in which I present an recursive formula that I deduced for left leaning red-black trees . I implemented it in java. In emacs the red-black trees are already used in this moment for keeping the memory segments of lisp symbols.
An application of red-black trees in emacs, which would drastically improve the redisplay system, would be to keep the text of each line as a rbt.
I give a rough explanation of the basic operations, without having studied recently the details of buffer implementation.
In emacs the buffers text contents is kept in memory linearly at the address buffer_text->beg.
One could keep as well the text from each line of the buffer into a red-black tree.
Each node will contain
* a buffer with a part of the text (for gap an empty text)
* a pointer to the next node, such that the search operation to be done in constant time
* the number of characters of text are on the nodes at left of the current node
The speed of the basic operations will be so:
1. search for text (remain the same)
-- it will remain linear as it is now.
2. seach for a given offset into a line (almost no change)
-- this will be logarithmic , logarithm of the length of the line
-- in this moment I think it's constant time, so no visible change
3. insert a new gap (major improvement)
-- this will be logarithmic in time, and no need to move memory segments. To insert a new gap at offset X of a line, we start at the root, if X > number of characters at the left of root we go to right, ifnot, we either move to left or insert a new node and move the current node to the left of the new node.
4. insert a new text into the buffer. (the same)
-- This will insert into the gap from the point, and when the gap is filled, a new gap is created.
5. remove text.
-- this supposes a lot of things, like re-checking the values of all values of properties at the left and right, so many changes, but it will remain as fast as in this moment.
6. merging 2 lines means to combine the text from 2 red-black trees, and this is done in constant time, with no need to move memory segments.
The text properties, overlays, markers, etc will remain almost the same as now. Or they can be moved on the node of a corresponding text. In this moment these are kept into lists, but one can move the given properties into the node that keeps the corresponding text.
The whole buffer would be encoded as a list of lines, and each line is encoded as a red-black tree, as I described.
This will make fast operations involving the gap, the red-black trees are quite easy to implement, but I cannot see now the bad side effects involved by such a change. The major improvement would be the redisplay.