Re: [dev] [sandy] [PATCH] VIM key bindings.

From: Charlie Kester <corky1951_AT_comcast.net>
Date: Thu, 10 Jul 2014 09:33:53 -0700

On Thu 10 Jul 2014 at 01:55:24 PDT Marc André Tanner wrote:
>I've recently been reading about Project Oberon whose text subsystem
>is built on piece tables. That is how I became interested and did some
>further investigations. The technique has been used before in a number
>of text editors such as Bravo (from Xerox PARC), Lara and even Word.
>However I'm not aware of a modern, console based, text editor using
>this approach. Pointers welcome.

Another interesting approach is buffer gap. It divides the text into
two contiguous spans, with a gap between them.

Inserted text is added at the beginning of the gap, in effect extending the
first span. Moving the insertion point means copying text across the gap from
the end of the first span to the beginning of the second (or vice versa).

If the gap gets filled beyond some predetermined threshold, the entire second
span is moved "down" so that a gap of the desired size is regained.

There's obviously some overhead involved in maintaining pointers to the
beginning of the gap and the beginning of the second span, and in shuffling
bytes back and forth across the gap. Reestablishing the gap is especially
costly. But with some minor pointer adjustments to address bytes in the
second chunk, the entire text can be treated as a one-dimensional array, so
that the classic search and replace algorithms can be used.

The problem with linked lists of lines and piece tables has always been
achieving good locality of reference. Not a problem with buffer gap,
where locality was the main motivating factor behind the design.

I've read, but haven't confirmed, that buffer gap aka gap buffer, is used in
most emacs-style editors.
Received on Thu Jul 10 2014 - 18:33:53 CEST