Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!ukma!usenet.ins.cwru.edu!shasta!trier
From: trier@shasta.scl.cwru.edu (Stephen Trier)
Newsgroups: comp.editors
Subject: Editors 102: Updating the screen in a buffer-gap editor
Summary: Here's how I did it
Message-ID: <1990May27.045148.23808@usenet.ins.cwru.edu>
Date: 27 May 90 04:51:48 GMT
Sender: news@usenet.ins.cwru.edu
Reply-To: trier@SCL.CWRU.Edu (Stephen Trier)
Organization: Smith Undergrad Lab, CWRU, Cleve. OH
Lines: 101
X-Post-Machine: shasta.scl.cwru.edu


   A few weeks ago, I posted a request for help with an editor I was writing.
After several attempts to write doubly-linked-list-of-lines editors
(hereafter called linked-list editors), I decided to try writing one based
on a buffer-gap data structure.

   I found the basic operations of the editor to be much easier to write
with the buffer-gap structure than with the linked-list structure.  Insertion
and deletion were a breeze, and I didn't have to write any special code to
handle new lines!  On the other hand, managing the screen display became much
more complicated.

   In the linked-list structure, the data is already broken into lines,
simplifying screen updates.  With a pointer to the top line of the screen,
it is trivial to output the next 24 nodes of the list to the screen.  In my
buffer-gap editor, I decided that I must scan through the buffer to find the
line breaks.  For efficiency, I did this while outputing the characters I
passed to the screen.

   The first implementation I tried used two nested loops to scan across the
x and y directions of the window.  Several boolean variables were used to
signal when the next character in the file should be output, when a tab was
being expanded to spaces, or when the end of the line had been encountered,
making it necessary to fill to the end with spaces.  This code was complicated
and was slowed by the many comparisons I was making in order to allow for
special cases such as the end of the buffer and skipping over the buffer gap.

   I then re-implemented the editor from a different viewpoint, this time
using nulls to flag the top of the gap and the end of the buffer.  (I still
had pointers to the top and bottom of the gap and the top and bottom of the
buffer.)  The screen-refresh code was much easier to write this time, and
turned out to be substantially faster.  C-like pseudocode for the second
implementation follows:

	hit_gap = FALSE;
	x = 0; y = 0;
	p = screen;			/* screen points to the top of the
					 *  screen in the buffer.
					 */
	while (y < bottom_line)
	    switch (p++)  {
	        case '\t':
	            /* output spaces and increment x until (x % 8) == 0 */
	            break;
	        case '\n':
	            /* clear to the end of the line */
	            /* increment y */
                    break;
	        case '\0':
	            if (!hit_gap)  {
	                p = bottom_of_gap_pointer;
	                hit_gap = TRUE;
	                /* Mark this location as the current cursor point */
	                }
	            else  {
	                /* Clear to the bottom of the screen */
	                /* Drop out of the while loop */
	                }
	            break;
	       default:
	            /* Output the character to the screen and increment x */
	            break;
	       }

    This implementation turned out to be much faster than the original.  By
scanning the data and making the screen match, rather than the other way
around, the refresh logic became much simpler.  In addition, tab handling
became neat and clean, and the cursor can be positioned to reflect the actual
position of the gap.

    My actual code also has code for horizontal scrolling, clipping to fit
inside a window, and support of larger-than-memory files.  I originally
thought the linked-list structure supported virtual memory well, but that
support came at the cost of a comparison on every line access, to see if
it need to be pulled off of the disk.  It also necessitated some on-disk
garbage collection, which *definitely* was something to avoid.  With the
buffer-gap structure, virtual memory is easy.  If the gap comes too close
to the top of the file, a page from the bottom of the buffer is written
to a temporary file and a page is read into the top of the buffer from a
second file.  If the gap gets too close to the bottom, the opposite
transfers take place.  If the buffer becomes too full, a page is pushed
out to the disk, and if it becomes too empty (more than two pages of free
space), a new page is read in.

    The code I wrote does not have any provision for cursor optimization
during screen refresh.  This is because it's for MS-DOS machines with
memory-mapped video.  In the time it would take to update a memory array
showing what I would like on the screen, I can write the update directly
to the video card.  At some point, I would like to port the code to curses,
in which case I will let curses do the hard work!  :-)

    The replies I received about my original message consisted of two
references to a magazine article and a book and three requests for
information on how I solved the problem.  I'm posting this now because
of those requests.  Perhaps it can be considered the natural successor
to the "Editor 101" articles of a few months back...  :-)

            <=> Stephen Trier    sct%seldon@skybridge.SCL.CWRU.Edu
                                 {sun,att,decvax}!cwjcc!skybridge!seldon!sct
                                 sct@po.CWRU.Edu