Text editor buffer?

[xlar54]

Hi all,

In writing something like a text editor, Im confused as to how the
buffer is constructed. Youd think a simple malloc of RAM would do it,
but this actually seems to create an immediate problem. For instance,
if you insert a new line in a document, everything after the new line
must be moved. This could be a slow process depending on the
machine. Id like to hear your thoughts on the best way to achieve
this kind of function. How do these things really work?

 

[Jerry Freedman]

Hi all,

In writing something like a text editor, Im confused as to how the
buffer is constructed.  Youd think a simple malloc of RAM would do it,
but this actually seems to create an immediate problem. For instance,
if you insert a new line in a document, everything after the new line
must be moved.  This could be a slow process depending on the
machine.  Id like to hear your thoughts on the best way to achieve
this kind of function.  How do these things really work?

Check the source for Emacs--I think there is a book about text editing
too but the name escapes me. Emacs uses a 'buffer gap" which is
explained in the Wikipedia entry for gap buffer. If Emacs uses it, its
got to be good.

BTW I remember reading in the text editor book I referred to that
Stallman intended to go to a linked list implementation but never got
around to it

 

[Gene]

Hi all,

In writing something like a text editor, Im confused as to how the
buffer is constructed.  Youd think a simple malloc of RAM would do it,
but this actually seems to create an immediate problem. For instance,
if you insert a new line in a document, everything after the new line
must be moved.  This could be a slow process depending on the
machine.  Id like to hear your thoughts on the best way to achieve
this kind of function.  How do these things really work?

Google "text editor data structure"

 

[Jerry Freedman]

Check the source for Emacs--I think there is a book about text editing
too but the name escapes me. Emacs uses a 'buffer gap" which is
explained in the Wikipedia entry for gap buffer. If Emacs uses it, its
got to be good.

BTW I remember reading in the text editor book I referred to that
Stallman intended to go to a linked list implementation but never got
around to it

I just remembered. The author of the text editing book is Craig
Finseth if anyone is interested

 

[Nobody]

In writing something like a text editor, Im confused as to how the
buffer is constructed. Youd think a simple malloc of RAM would do it,
but this actually seems to create an immediate problem. For instance,
if you insert a new line in a document, everything after the new line
must be moved. This could be a slow process depending on the
machine. Id like to hear your thoughts on the best way to achieve
this kind of function. How do these things really work?

However you want. The simplest approach (a contiguous block) is clearly
unreasonable, but the next simplest approach is quite usable.

Specifically, rather than keeping the text contiguous, with any left-over
space at the end of the buffer, you keep the left-over space in the
middle, where you're inserting or deleting text.

E.g. you create a new document and enter "hello world":

>hello world[...........................]<

where the [...] is unused memory.

You decide you want a comma between the words, so you first move
everything after the insertion point to the end of the buffer:

>hello[...........................] world<

then insert the comma:

>hello,[..........................] world<

IOW, whenever you want to insert or delete text, you first check that the
editing position is coincident with the gap. If it isn't, you make it so,
by moving the text between the editing position and the gap to the
appropriate end of the gap. Then, you add or remove the text.

This way, you only have to do a memmove() whenever you start making
changes at a new position, and not e.g. for every character which is added
or removed.

The main complication is that you can't assume contiguous data, so
e.g. searching for a word isn't as simple as calling strstr().

From there, there's no limit to how complicated you can make it,
particularly once you start factoring in memory management, multi-byte
encodings, efficiency, markers, extents, etc.

 

[bartc]

However you want. The simplest approach (a contiguous block) is clearly
unreasonable, but the next simplest approach is quite usable.

I've used this approach in an editor, and the performance is acceptable even
up to 10M characters of text, on a basic desktop pc.

(However, my editors are line-oriented, and when editing a specific line,
that happens in a line-buffer separate from the main text.)

A more recent editor uses an array of individually allocated strings.

 

[jacob navia]

xlar54 a écrit :

Hi all,

In writing something like a text editor, Im confused as to how the
buffer is constructed. Youd think a simple malloc of RAM would do it,
but this actually seems to create an immediate problem. For instance,
if you insert a new line in a document, everything after the new line
must be moved. This could be a slow process depending on the
machine. Id like to hear your thoughts on the best way to achieve
this kind of function. How do these things really work?

In the IDE of lcc-win the editor uses a double linked list of lines.
When allocating a line, more space is allocated than strictly needed
(a few characters), and then you reallocate as needed.

This structure is the most ancient part of the IDE, developed under
windows 16 (windows 3.1, around 1992 if I remember well)

It survived the 16-32 bit port, and now the 32-64 bit port. The
text is a circular list, and there is a marker line when the end of
the text joins the start.

The lines are copied into the display from the list. The display
is an array that varies depending the size of the window where
the text will be displayed.

The display is colored (keyword analyzing, etc) and shown in the
window without wrap-around.

Searching is done with an strstr in each line. This has the drawback
that patterns spanning several lines aren't supported. For an
editor of C programs this is no big deal, but it could be
in another applications.