next up previous
Next: The piece table Up: Recursive Sequence Data Previous: The line span

Fixed size buffers


In the line spans method the partitioning of the sequence into spans is determined by the contents of the text file, in particular the line structure. Another approach is for the text editor to decide the partitioning of the sequence into spans based on the efficiency of buffer use. Since fixed size blocks are more efficient to deal with the file can be divided into a sequence of fixed size buffers. If the buffers were required to be always full, a great deal of time would be spent rearranging data in the buffers, therefore, each block has a maximum size but will usually contain fewer actual items from the sequence so there is room for inserts and deletes, which will usually affect only one buffer. (See Figure 6.)

Figure 6: Fixed size buffers  

The disk block size (or some multiple of the disk block size) is usually the most efficient choice for the fixed size buffers since then the editor can do its own disk management more easily and not depend on the virtual memory system or the file system for efficient use of the disk.

Usually a lower bound on the number of items in a buffer is set (half the buffer size is a common choice). This requires moving items between buffers and occasionally merging two buffers to prevent the accumulation of large numbers of buffers. There are four problems with letting too many buffers accumulate:

As an example of fixed size buffers, suppose disk blocks are 4K bytes long. Each buffer will be 4K bytes long and will contain a span of length from 2K to 4K bytes. Each buffer is handled using the array method, that is, inserts and deletes are done by moving the items up or down in the buffer. Typically an edit will only affect one buffer but if a buffer fills up it is split into two buffers and if the span in a buffer falls below 2K bytes then items are moved into it from an adjacent buffer or it is coalesced with an adjacent buffer.

Each descriptor points to a buffer and contains the length of the span in the buffer. The fixed size buffer method also requires a recursive sequence for the descriptors. This could be any of the basic methods but most examples from the literature use a linked list of descriptors. The loose packing allows small changes to be made within the buffers and the fact that the buffers are linked makes it easy to add and delete buffers.

This method is used in the text editors Gina [1] and sam [12] and is described by Kyle [9].

next up previous
Next: The piece table Up: Recursive Sequence Data Previous: The line span

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