next up previous
Next: Fixed size buffers Up: Recursive Sequence Data Previous: Determination of span

The line span method (one span per line)

Since most text editors do many operations on lines it seems reasonable to use a data structure that is line oriented so line operations can be handled efficiently. The line span method uses a descriptor for each line. Often one large buffer is used to hold all the line spans. New lines are appended to the end of the used part of the buffer. See Figure 5.

Figure 5: The line spans method  

Line deletes are handled by deleting the line descriptor. Deleting characters within a line involves moving the rest of the characters in the line up to fill the gap. Since any one line is probably not that long this is reasonably efficient.

Line inserts are handled by adding a line descriptor. Inserting characters in a line involves copying the initial part (before the insert) of the line buffer to new space allocated for the line, adding the characters to be inserted, copying the rest of the line and pointing the descriptor at the new line. Multiple line inserts and deletes are combinations of these operations. Caching can make this all fairly efficient.

Usually new space is allocated at the end of the buffer and the space occupied by deleted or changed lines is not reused since the effort of dynamic memory allocation is not worth the trouble. A disk file the continues to grow at the end can be handled quite efficiently by most file systems.

This method uses as many descriptors as there are lines in the file, that is, a variable number of descriptors hence there is a recursive problem of keeping these descriptors in a sequence. Typically one of the basic methods described in section 5 is used to maintain the sequence of line descriptors. The linked list method can be used (as in Ved [6]) or the array method (as in Godot [11], Gina [1] and ed [3]).

NOTE: reference to SW Tools and SW Tools Sampler here. For linked lists of lines.

These simpler methods are acceptable since the number of line descriptors is much smaller than the number of characters in the file being edited. The linked list method allows efficient insertions and deletions but requires the management of list nodes.

This method is acceptable for a line oriented text editor but is not as common these days since strict line orientation is seen as too restrictive. It does require preprocessing of the entire buffer before you can begin editing since the line descriptors have to be set up.

next up previous
Next: Fixed size buffers Up: Recursive Sequence Data Previous: Determination of span

Charlie Crowley
Thu Jun 27 15:36:10 MDT 1996