You are looking at historical revision 26319 of this page. It may differ significantly from its current revision.
Gap buffer implementation.
A gap buffer is a structure that models a string but allows relatively efficient insertion of text somewhere in the middle. The insertion location is called `point' with minimum value 1, and a maximum value of the length of the string (which is not fixed).
Specifically, we allocate a continuous buffer of characters that is composed of the BEFORE, the GAP and the AFTER (reading L->R), like so:
+--- POINT v +--------------------+--------------------+--------------------+ | BEFORE | GAP | AFTER | +--------------------+--------------------+--------------------+
<----- bef-sz ----->|<----- gap-sz ----->|<----- aft-sz ----->
<-------------------| usr-sz |------------------->
<-------------------------- all-sz -------------------------->
This diagram also shows how the different sizes are computed, and the location of POINT. Note that the user-visible buffer size `usr-sz' does NOT include the GAP, while the allocation `all-sz' DOES.
The consequence of this arrangement is that "moving point" is simply a matter of kicking characters across the GAP, while insertion can be viewed as filling up the gap, increasing `bef-sz' and decreasing `gap-sz'. When `gap-sz' falls below some threshold, we reallocate with a larger `all-sz'.
In the implementation, we actually keep track of the AFTER start offset `aft-ofs' since it is used more often than `gap-sz'. In fact, most of the variables in the diagram are for conceptualization only.
(The term and concept of "gap buffer" are borrowed from Emacs. We
will gladly return them when libemacs.so is available. ;-)
Library Procedures[procedure] gb? :: OBJECT -> BOOL
Returns #t if the given object is a gap buffer object, #f otherwise.[procedure] make-gap-buffer :: [INIT] -> GAP-BUFFER
Returns a new gap buffer. Optional argument INIT is either a port to read from; a string, used to initialize the buffer contents; or an integer specifying the memory allocation (in bytes) requested. Point is left at the maximum position.
Querying[procedure] gb-point :: GAP-BUFFER -> INTEGER
Returns the position of point in the given gap buffer. This is an integer starting with 1.[procedure] gb-point-min :: GAP-BUFFER -> INTEGER
Return the minimum position possible for point in the gap buffer. In the current implementation, this value is always 1 (one).[procedure] gb-point-max :: GAP-BUFFER -> INTEGER
Returns the maximum position possible for point in the given gap buffer. This value can be changed by inserting text into the buffer.
Munging[procedure] gb-insert-string! :: GAP-BUFFER * STRING -> VOID
Inserts the given string into the given gap buffer, moving point forward as well as increasing the value that would be returned by gb-point-max.[procedure] gb-insert-char! :: GAP-BUFFER * CHAR -> VOID
Inserts the given character into, moving point forward as well as increasing the value that would be returned by gb-point-max.[procedure] gb-delete-char! :: GAP-BUFFER * INTEGER -> VOID
Deletes the given number of characters from point, forward if the integer argument is positive, backward if it is negative. (If zero, do nothing.) Deleting backwards moves point backwards. Deleting forwards or backwards decreases the value that would be returned by gb-point-max.[procedure] gb-erase! :: GAP-BUFFER -> VOID
Completely erases the gap buffer. Point is left at the minimum position possible.
Moving[procedure] gb-goto-char :: GAP-BUFFER * INTEGER -> INTEGER
Moves point to the given point and returns it. If the new point is outside the minimum and maximum positions possible, it is adjusted to the the nearest boundary (however, the return value is unchanged).
Transforming[procedure] gb->string :: GAP-BUFFER -> STRING
Return a new string representing the text of the gap buffer. Point does not move.[procedure] gb-filter! :: GAP-BUFFER * PROCEDURE -> VOID
Passes the string representing the contents of the gap buffer to the given procedure, and uses its return value to replace the contents of the gap buffer. Point is set to the maximum position.[procedure] gb->lines :: GAP-BUFFER -> LIST
Returns a list of strings representing the lines of text of the gap buffer. Newlines are automatically removed. A buffer with N newlines results in a list of length N+1. Point does not move.
- 1.0 Initial Release
The gap-buffer library was written by Thien-Thi Nguyen for Guile Scheme.
gap-buffer was ported to Chicken Scheme by Ivan Raikov.
Copyright (C) 2002, 2003, 2006 Free Software Foundation, Inc. This program is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. A full copy of the Lesser GPL license can be found at <http://www.gnu.org/licenses/>.