all messages for Emacs-related lists mirrored at yhetil.org
 help / color / mirror / code / Atom feed
* line buffer as Red Black Trees instead of linear
@ 2014-05-15 14:33 Alin Soare
  2014-05-15 17:15 ` Alin Soare
  2014-05-15 19:17 ` Stefan Monnier
  0 siblings, 2 replies; 22+ messages in thread
From: Alin Soare @ 2014-05-15 14:33 UTC (permalink / raw)
  To: emacs-devel

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

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.

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

^ permalink raw reply	[flat|nested] 22+ messages in thread

end of thread, other threads:[~2014-05-22  9:33 UTC | newest]

Thread overview: 22+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2014-05-15 14:33 line buffer as Red Black Trees instead of linear Alin Soare
2014-05-15 17:15 ` Alin Soare
2014-05-15 19:17 ` Stefan Monnier
2014-05-15 19:47   ` Alin Soare
2014-05-15 20:06     ` Eli Zaretskii
2014-05-15 20:38       ` Slow redisplay with long lines Stefan Monnier
2014-05-15 20:57         ` Stephan Mueller
2014-05-16  5:40           ` Eli Zaretskii
2014-05-16 18:08             ` Stephan Mueller
2014-05-16 20:36               ` Eli Zaretskii
2014-05-16  5:39         ` Eli Zaretskii
2014-05-15 23:40       ` line buffer as Red Black Trees instead of linear Alin Soare
2014-05-16  5:41         ` Eli Zaretskii
2014-05-16  7:44           ` Alin Soare
2014-05-16  8:28             ` Eli Zaretskii
2014-05-16  8:53               ` Alin Soare
2014-05-16  9:24                 ` Thien-Thi Nguyen
2014-05-21  8:34                 ` Alin Soare
2014-05-21 15:17                   ` Eli Zaretskii
2014-05-21 16:00                     ` Alin Soare
2014-05-21 17:03                       ` Eli Zaretskii
2014-05-22  9:33                         ` Alin Soare

Code repositories for project(s) associated with this external index

	https://git.savannah.gnu.org/cgit/emacs.git
	https://git.savannah.gnu.org/cgit/emacs/org-mode.git

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.