home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 5 Edit / 05-Edit.zip / me34src.zip / me3 / doc / Undo.article < prev    next >
Text File  |  1995-01-14  |  28KB  |  677 lines

  1. -*-text-*-
  2.  
  3.  
  4.           Implementing Undo for Text Editors
  5.           ------------ ---- ---    ---- -------
  6.  
  7.                 Craig Durland
  8.                craig@cv.hp.com
  9.                 Copyright 1991
  10.  
  11.  
  12.                 February 1991
  13.                    Updated
  14.                September 1991   
  15.                 February 1992
  16.                 November 1992
  17.  
  18. Probably anyone who has used a text editor has, at one time or another,
  19. made a boo boo and immediately wished they could to go back in time and
  20. not do it all over again.  The Undo command gives that ability by moving
  21. backwards in time, reversing the effects of the most recent changes to
  22. the text.  Some undo commands can go back to the beginning of time,
  23. undoing all changes that have occurred to the text.
  24.  
  25. The undo described in this article is a subset of the idealized undo -
  26. it only reverses changes to text.  It doesn't keep track of cursor
  27. movements, buffer changes or the zillions of other things we do while
  28. editing text.  While this can make undoing changes disconcerting because
  29. it can jump from change to change differently from what you remember, it
  30. also reduces the amount of stuff that the editor needs to remember
  31. (saving memory) and helps keep the editor from bogging down trying to
  32. keep track of whats been going on.  Finally, the material presented is
  33. for text editors.  Editors of other types may find some of the
  34. discussion relevant but that will be a happy accident.
  35.  
  36. Jonathan Payne (author of JOVE) has stated that "Undo/redo is trivial to
  37. implement" (comp.editors, Tue, 2 Jan 1990).  Having just implemented
  38. undo for the editor I am working on, I think that straight forward is a
  39. better term than trivial.  Since it took me a long time to figure out a
  40. workable undo scheme, I thought others might be interested in what I
  41. did.
  42.  
  43.  
  44.  
  45. Caveats:  The algorithms, code and data structures used in this article
  46. are based on working and tested code that has been "sanitized" to remove
  47. obscuring details (like what stack data structures I used).  If you use
  48. the code, make sure you understand it so that you can properly fill in
  49. the missing details.
  50.  
  51. Conditions:  You are free to use the algorithms, code and data
  52. structures contained in this article in anyway you please.  If you use
  53. large chunks, I would appreciate an acknowledgment.  If you distribute
  54. this article, in whole or part, please retain the authorship notice.
  55.  
  56.  
  57.  
  58.             What is Not Discussed
  59.             ---- --    --- ---------
  60.  
  61. Redo is a undo for undo.  Very handy if you undo one time to many and
  62. need to undo that last undo.  I haven't implemented it yet but I think
  63. that it will be easy to modify the algorithms to support it.  I also
  64. think some dragons are there but they are hiding from me.  We'll see
  65. when I actually get around to doing it.
  66.  
  67.  
  68.  
  69.        Editor Implementations and How They Affect Undo
  70.        ------ --------------- --- --- ---- ------ ----
  71.  
  72. Two popular ways text editors store text are "buffer gap" and "linked
  73. list of lines" (described in detail else where - see comp.editors).  As
  74. you might imagine, different implementations for storing text can affect
  75. undo implementations.  Fortunately for this article, the affects are
  76. relatively minor.  As I discuss data structures and algorithms, I will
  77. point out the differences.
  78.  
  79. Note:  I will refer to buffer gap editors as BGE and linked list editors
  80. as LLE.
  81.  
  82.  
  83.            What You Need to Save to Implement Undo
  84.            ---- ---    ---- --    ---- --    --------- ----
  85.  
  86. I use Undo Events to represent text changes.  These events are kept in a
  87. undo stack, most recent event at the top of the stack.  There is one
  88. stack per text object (buffer in Emacs) so undo can only track changes
  89. on a per buffer basis.  This simplifies things quite a bit over tracking
  90. all changes globally in a multibuffer editor.
  91.  
  92. I found that four event types seem to be enough describe all text
  93. changes.  They are:
  94. - BU_INSERT:  This event is used when text is inserted.  The most common
  95.   case is when you type.  When text is inserted, we need to remember how
  96.   much was inserted and where it was inserted.  We don't need to
  97.   remember the what the text was because to undo this type of event, all
  98.   we have to do is delete the inserted text.  Note that in order to
  99.   reduce the number of events saved (and memory used), you need to be
  100.   able to detect text that is inserted sequentially (like when you type
  101.   "123") so that all these events can packed into one event.  This can
  102.   affect more than you would think at first glance and will be discussed
  103.   more fully else where.
  104.  
  105. - BU_DELETE:  This event is used when text is deleted, for example when
  106.   you use the delete (or backspace) key.  Here we need to remember the
  107.   place where the deletion took place and the text to be deleted.  Note
  108.   that we have to save the text before (or while) it is deleted.  This
  109.   is can cause trouble for some editor implementations.  Again, event
  110.   packing can save much of space if users like to lean on the delete
  111.   key.  To undo a delete, we have to insert the deleted text at the
  112.   place where it was deleted.
  113.  
  114. - BU_SP:  A sequence point is a stopping point in the undo stack.  It
  115.   tells the undo routine that this is the last event to undo so the user
  116.   will think that one of his actions has been undone.  Note that this
  117.   implies that one user action may cause one or (many) more undo events
  118.   to be saved.  This is especially true when the editor supports macros
  119.   or an extension language.  I think that it is important that one press
  120.   of the undo key undoes one user action (there are a few exceptions
  121.   (like query replace)).  Probably one of the hardest things to "get
  122.   right" (from the users point of view) is where to place sequence
  123.   points.  Here is my list of rules for sequence points (take these with
  124.   a grain of salt - these are my opinions with nothing to back them up.
  125.   They may change.):
  126.   - Need sequence points so undoing stops at "natural, expected" places.
  127.   - Undo should stop where user explicitly marked the buffer as
  128.     unchanged (like save buffer to disk).  These are usually UNCHANGED
  129.     events.
  130.   - A string of self insert keys should undo as one.  Its pretty
  131.     annoying to have to hit undo 14 times to undo "this is a test".
  132.   - A word wrap or Return should break a character stream.  Thus undo
  133.     only backs up a line at at time, probably better than undoing an
  134.     entire paragraph when only one line needed undoing.
  135.   - Commands, macros, programs written in the extension language, etc
  136.     should undo as a unit.  ie if pressing a key caused a bunch of stuff
  137.     to happen, pressing undo should undo all the stuff the key caused.
  138.   - Since rules can't cover all cases (like query replace), programs
  139.     need to be able to add sequence points.
  140.  
  141.   I also store the buffer modified state here so I know to mark the
  142.   buffer as unchanged if it was before this change happened.
  143.  
  144. - BU_UNCHANGED:  This event marks a time when the text was marked as
  145.   unchanged or saved.  Examples include saving the text to the disk.
  146.   When undoing, this event marks a stopping point:  The user has undoed
  147.   back to a time when the buffer was "safe".  When you make an
  148.   inadvertent change to text that you only wanted to look at, it is
  149.   psychologically reassuring to know the text is back to its original
  150.   state.
  151.  
  152.   Only the most recent unchanged event actually indicates that the
  153.   buffer contents match those out on the disk (and every buffer change
  154.   before and after that event means the buffer is out of sync with the
  155.   disk).  For undo, this means that only the most recent unchanged event
  156.   is valid - when that event is undone, the buffer matches the disk.
  157.   After that one, other unchanged events need to be ignored because the
  158.   buffer at that point can't match the disk.
  159.  
  160.   Note that BU_UNCHANGED events are really just special cases of
  161.   sequence points.  You could easily just combine them into one event.
  162.  
  163. It should be obvious by now that much editing would generate a LOT of
  164. undo events.  Unless your computer has an infinite amount of memory, you
  165. need some rules about when to start throwing away events.  Since
  166. different people will have different ideas about this and the amount of
  167. memory can greatly affect this, you need to let the user control it.
  168. There are three parameters that need to be specified:
  169. - Save or don't save undos.  For Emacs-like editors, there are probably
  170.   many buffers that don't need (or want) undo.  For example, I don't
  171.   care if help buffers have undo.  Not turning on undo for all buffers
  172.   can really save memory and help performance (undo can really slow down
  173.   extension programs).
  174. - The maximum amount of text saved.  When text is deleted, it has to be
  175.   saved somewhere.  The more deleted, the more that needs to saved.  It
  176.   adds up.  We need a point where we discard some of the old saved text
  177.   in order to save some.  Note that a big delete can clean out all the
  178.   existing undos and worst case, the delete is bigger than the max so we
  179.   have to throw away the undos and ignore the delete (because there is
  180.   not enough room to save it).
  181. - The maximum number of events saved.  Each event takes up a bit of
  182.   memory.  Events pile up amazingly fast during editing.  At some point
  183.   we have to start throwing away the old to make room for the new (kinda
  184.   like my garage).  When dumping events, you have to also clean up any
  185.   text the deleted event might have saved.
  186.  
  187. It can be a real guessing game to figure out how to balance the number
  188. of events saved against text saved.  Different editing operations use up
  189. one or the other at different rates.  I'm currently using 600 events and
  190. a 5K save buffer.
  191.  
  192.  
  193.  
  194.  
  195.  
  196.                When an Editor Does Undo
  197.                ---- -- ------ ---- ----
  198.  
  199. Given the undo event types and rules, the editor just has to save undo
  200. events when needed and add sequence points at the "proper" times.  Now
  201. is the time you will be glad you funneled all you buffer changes through
  202. just a couple of insert/delete routines.  Here is where I save events
  203. for my Emacs-like editor:
  204. - Insert a block of text.        save_for_undo(BU_INSERT,n);
  205.   This routine is used when doing things like a kill buffer yank.  It is
  206.   also used to undo a delete so care has to be taken not to get into a
  207.   do/undo tug of war.
  208. - Read a file.                save_for_undo(BU_UNCHANGED,0);
  209.   We mark the buffer as unchanged because it has been cleared and filled
  210.   with new text.  Note that it is up the buffer clear routine to save
  211.   the delete text.  Also note that to do a "real" undo, we should also
  212.   save_for_undo(BU_INSERT,<characters in file>).  I don't because I
  213.   don't think it makes sense and because of the clear buffer problem
  214.   mentioned below.
  215. - Insert a file.            save_for_undo(BU_INSERT,n);
  216.   If you don't know the size of the file that is going to be inserted,
  217.   you can use this trick:  Insert the file (and figure out how much was
  218.   inserted), go back to where the file was inserted (the start of the
  219.   new text) and then save the undo.
  220. - Insert n characters.            save_for_undo(BU_INSERT,n);
  221.   This is used for the self inserting characters.
  222. - Delete n characters.            save_for_undo(BU_DELETE,n);
  223.   Have to be careful here because this routine is also used to undo
  224.   character inserts.  Actually, the undo routine is the one who cares
  225.   and protects against this.
  226. - After a key has been processed.    save_for_undo(BU_SP,0);
  227. - Mark a buffer as unchanged.        save_for_undo(BU_UNCHANGED,0);
  228. - Save a file.  This routine doesn't need to do anything because it
  229.   calls the buffer_is_unchanged() routine.  That routine saves the event.
  230.  
  231. Where I should (but don't) save undo events:
  232. - Clear buffer.  Because it is awkward to do with my type of editor.
  233.   See below for more on this.  Other editors would not have this routine
  234.   and would just use delete.  Instead, I clear all undos.
  235.  
  236. To do undo, the editor just calls the undo routine.
  237.  
  238.  
  239.  
  240.                Data Structures
  241.                ----    ----------
  242.  
  243. Each text object (buffer) has a pointer to a undo header.  This header
  244. contains a undo event stack, number of events in the stack (so I can
  245. easily check to see if the stack has grown too big), a flag that
  246. indicates whether or not the BU_UNCHANGED events are valid and an area
  247. in which to save deleted text.
  248.  
  249. In C, this looks like:
  250.      typedef struct
  251.      {
  252.        Undo *undo_stack;    /* where the undo events are */
  253.        int undo_count;        /* number of undos in the stack */
  254.        int there_is_a_valid_unchanged_event;
  255.        Bag *bag;        /* deleted text saved here */
  256.      } UndoHeader;
  257.  
  258. An undo stack is a linked list of undo events.  I used a linked list
  259. because it was easy and worked well but there are many other ways to
  260. store the data that would probably work as well.  An event contains a
  261. pointer to the next (older) event, the event type (BU_INSERT, etc), a
  262. marker to where the event took place, the number of characters involved
  263. and a pointer to the saved text (if any).  Note that some events may not
  264. use some of these fields.  The clever programmer could probably save
  265. quite a bit of space by having different (sized) structures for each
  266. event type.
  267.  
  268. LLEs (Linked List Editors) can run into problems when asked to save
  269. delete events.  Its quite possible that the we could be asked to save
  270. more text than buffer contains.  For example, in Emacs, the user could
  271. hit control-U a bunch of times and hit the delete key - delete 16384
  272. characters when the buffer only contains 53.  With a BGE (Buffer Gap
  273. Editor), this is very easy to check but is very time consuming with a
  274. LLE.  What I do with LLE is "trust but verify".  I make enough room to
  275. hold that much deleted text, then go ahead and try and save it.  I then
  276. figure out how much I really saved (a side affect of copying the text)
  277. and save that number.  The big drawback with this is that its easy to
  278. clear out most of the undo stack when you didn't need to and looks very
  279. fishy when you can't undo very much.  The other way around this is to
  280. put the "save-deleted-text" stuff in the routine that actually deletes
  281. the text but this would add a lot of noise to a already hard to
  282. understand routine.
  283.  
  284. A problem related to the I-don't-know-how-much-is-going-to-be-deleted
  285. problem is the clear-buffer problem.  With BGE, you know how much you
  286. are going to remove, with LLE, you don't.  So, I just clear the undo
  287. stack when the buffer is cleared because 1) most buffers will probably
  288. be bigger than the undo buffer anyway and cause it to be cleared and 2)
  289. buffer clears don't happen very often - usually for buffer deletes and
  290. file reads.
  291.  
  292. C code:
  293.      typedef struct Undo
  294.      {
  295.        struct Undo *next;    /* pointer to next older event */
  296.        int type;
  297.        UnMark mark;        /* where the event took place */
  298.        int n;            /* number of characters involved */
  299.        char *text;        /* where deleted text is saved */
  300.      } Undo;
  301.  
  302. In my editor, I have the concept of bags.  Bags hold various types of
  303. text objects and I have a lot of builtin support for them.  It was 
  304. natural and very easy to use these to hold deleted text.  Your editor is
  305. probably different so you'll have to use something else (like
  306. malloc()ing some space).  I use one per buffer and holds it all the
  307. deleted text.  The undo delete events point into the bag (actually, I
  308. use offsets but the concept is the same).
  309.  
  310. The undo markers are where in the buffer the event took place.  These
  311. only matter for insert and delete events.  This is one of the areas
  312. where editor implementation really matters.  A BGE (buffer gap editor)
  313. is a real win here.  Since undo events are effectively snapshots of
  314. buffer history, as you undo, the buffer returns to its exact state back
  315. in time.  A BGE mark is just an offset into the buffer.  We can just
  316. store this offset in the event and never mess with it because we know
  317. that it will be correct when we undo to the point where we want to use
  318. it.  We can't do this with a LLE (linked list editor).  A LLE mark is a
  319. pair:  (line pointer, offset in line).  Both editor types have to adjust
  320. marks as text is inserted and deleted but unlike the BGE, LLE marks can
  321. become invalid as time goes on (and lines unlinked).  One example of
  322. this is if you insert text into the middle of a block and then delete
  323. that block.  The delete has unlinked the lines that were inserted so the
  324. marks with insert are invalid.  When you undo the delete, you can't undo
  325. the insert because you no longer know where it took place.  This is not
  326. a problem with BGE because even though the delete made the insert mark
  327. point to the wrong place, when the delete was undoed, the mark became
  328. valid again.
  329.  
  330. To get around this problem a LLE has to either 1) track all cursor
  331. movement or 2) calculate the pair (line number, offset in line).
  332.   1) Pros:  Can undo cursor movements.
  333.      Cons:
  334.        - This would generate bazillions of cursor move events.
  335.        - This could really be a pain in the butt and slow down the
  336.        cursor movement routines.  One of the main reasons for writing a
  337.        LLE is not having to worry about stuff like this.
  338.   2) Pros:
  339.        - Some LLEs might already keep marks like this.
  340.        - You can (sometimes) keep track of this position so that you
  341.        don't have recalculate it all the time.  You would track it when
  342.        you could and mark it as invalid when you couldn't.
  343.        - Its easy to calculate.
  344.        - These marks work just like BGE marks.
  345.        - There are some optimizations that can be made if many events
  346.        are generated (sequentially) for the same line.  Basically, if
  347.        the dot line remains the same, you calculated the line number
  348.        earlier.  Caution - this can be trickier than you think.
  349.      Cons:
  350.        - It takes time to calculate the mark.
  351.        - You have to calculate it a lot.
  352.        - It adds a bunch of piddlie details to try and track the dot
  353.        and greatly increases the chances of screwing up.
  354.  
  355. I chose to do 2) (since my editor is a LLE).  Here is the C code:
  356.      typedef struct
  357.      {
  358.        int line;
  359.        int offset;
  360.      } UnMark;
  361.  
  362. For a BGE, just use the mark type you already have.
  363.  
  364. Some combinations of events occur together frequently and it might be a
  365. win to create an event to take advantage of them.  For example, replace
  366. operations involve a delete and insert at the same place.  If you packed
  367. these two events into one, you could potentially save lots of space in a
  368. big query replace.
  369.  
  370.  
  371.              Alternative Data Structures
  372.              ----------- ---- ----------
  373.  
  374. I've glossed over how I actually store the undo stack.  This is because
  375. there many (good) ways to do it.  I use linked lists because they are
  376. simple.  A more clever and compact method would be to pack the deleted
  377. text into the event structure (using the "clever" technique mentioned
  378. above) and store the event plus text in a fixed size data area.  This
  379. has several advantages:  You don't have to worry the number of events -
  380. when you run out space to store them, start removing the old events.  It
  381. is much easier to garbage collect the undo stack during undo.  Its
  382. also easier to make room for a new event.  The disadvantages are that
  383. you have to worry about structure alignment (and machine architecture)
  384. and the some of the code will get messy (in my opinion).  The old trade
  385. off of fast and small versus big and simple (or, as Julie Brown would
  386. say, "I like 'em big and stupid").
  387.  
  388.  
  389.  
  390.  
  391.                Global Variables
  392.                ------ ---------
  393.  
  394. I use a few global variables to make controlling undo a little easier.
  395.  
  396. Bool do_undo;
  397.   This variable is TRUE if undo is turned on for the current buffer.
  398.   The switch buffer code sets this so people who need to know can do so
  399.   quickly.  The user can change it by toggling a buffer flag.
  400.  
  401. Buffer *current_buffer;
  402.   Pointer to the buffer where changes are taking place.  The current
  403.   undo header hangs off this buffer.
  404.  
  405. int max_undos = 600;
  406.   The maximum number of undo events.
  407.  
  408. int max_undo_saved = 5000;
  409.   The maximum amount of deleted characters that can be saved.
  410.  
  411.  
  412.  
  413.           Algorithm for Saving Undo Events
  414.           --------- ---    ------ ---- ------
  415.  
  416. I save undo events as they occur.  I leave it to the undo routine to
  417. figure out how to undo this type of event because its easy, undo has
  418. more time to do it and this routine should be as fast as possible
  419. because most undo events will never be used and you want the editor to
  420. keep up with you.
  421.  
  422.      save_for_undo(type,n)
  423.        int type;    /* event type:  BU_INSERT, etc */
  424.        int n;        /* number of characters involved (if any) */
  425.      {
  426.        Undo undo;
  427.        UnMark mark;
  428.  
  429.        if (!do_undo) return;    /* don't save undos for this buffer */
  430.  
  431.        switch (type)
  432.        {
  433.      case BU_INSERT:            /* Characters inserted */
  434.        set_unmark(&mark);
  435.        pack_sequential_insert_events();
  436.  
  437.        undo.n = n;
  438.        undo.mark = mark;
  439.  
  440.        break;
  441.      case BU_DELETE:            /* Characters deleted */
  442.      {
  443.        if (n == 0) return;            /* that was easy! */
  444.  
  445.        set_unmark(&mark);
  446.        undo.mark = mark;
  447.        open_bag(n);             /* make sure there is enough space */
  448.        undo.n = save_text(n);    /* returns number of characters saved */
  449.  
  450.        break;
  451.      }
  452.      case BU_SP:                /* Set sequence point */
  453.        if (last_event_was_a_sequence_point()) return;
  454.        break;
  455.      case BU_UNCHANGED:        /* Buffer has been marked safe */
  456.        if (last_event_was_a_save()) return;
  457.        header->there_is_a_valid_unchanged_event = TRUE;
  458.        break;
  459.        }
  460.  
  461.        undo.type = type;
  462.  
  463.        push_undo(&undo);
  464.      }
  465.  
  466.  
  467.  
  468.              Algorithm for Undoing Events
  469.              --------- --- ------- ------
  470.  
  471. This routine performs undo by reversing the effects of undo events from
  472. most recent until it finds a sequence point or runs out of events.
  473.  
  474. Note that undo is turned off so we don't try and re-save undo events as
  475. we march through the stack.
  476.  
  477. If the last event undid was a UNCHANGED, we need to add a new one to the
  478. undo list (to replace the one we popped).  If we don't, when we undo
  479. back to this point in the future, there won't be a UNCHANGED event to
  480. tell us the buffer is unchanged.  Ditto if we empty the undo stack.
  481.  
  482. UNCHANGED events are a no-op if the buffer is not modified.  This makes
  483. <save buffer><undo> work "nicer" and lets the above work (if it wasn't,
  484. undo would stop at the UNCHANGED event and you couldn't undo any more).
  485.  
  486.      undo()
  487.      {
  488.        int undo_flag, num_events, something_happened, push_an_unchanged;
  489.        Undo *ptr;
  490.  
  491.        if (no_undos()) return;
  492.  
  493.        undo_flag = do_undo; do_undo = FALSE;
  494.  
  495.        num_events = 0;
  496.        something_happened = FALSE;
  497.        push_an_unchanged = FALSE;
  498.  
  499.        while (ptr = pop_undo())
  500.        {
  501.      num_events++;
  502.      switch (ptr->type)
  503.      {
  504.        case BU_INSERT:    /* To undo: Delete inserted characters */
  505.          something_happened = TRUE;
  506.          goto_unmark(&ptr->mark);
  507.          delete_text(ptr->n);
  508.          break;
  509.        case BU_DELETE:    /* To undo: Insert deleted characters */
  510.          something_happened = TRUE;
  511.          goto_unmark(&ptr->mark);
  512.          insert_block(ptr->text, ptr->n);
  513.          break;
  514.        case BU_UNCHANGED:    /* At this point, buffer might be unchanged */
  515.          if (header->there_is_a_valid_unchanged_event &&
  516.          buffer_is_modified())
  517.          {
  518.         buffer_modified(FALSE);
  519.         something_happened = TRUE;
  520.         push_an_unchanged = TRUE;
  521.          }
  522.          header->there_is_a_valid_unchanged_event = FALSE;
  523.          /* fall through:  a BU_UNCHANGED acts like a sequence point */
  524.        case BU_SP:        /* Hit a sequence point, stop undoing */
  525.          if (something_happened) goto done;
  526.          break;
  527.      }
  528.        }
  529.  
  530.      done:
  531.  
  532.        gc_undos(num_events);    /* clean up the undo stack needed */
  533.  
  534.        do_undo = undo_flag;
  535.  
  536.        if (push_an_unchanged || (undo_stack_empty() && buffer_not_modified()))
  537.          save_for_undo(BU_UNCHANGED,0);
  538.      }
  539.  
  540.  
  541.  
  542.                Miscellaneous Algorithms
  543.                ------------- ----------
  544.  
  545. Here are some miscellaneous routines to flesh out undo.  Note that there
  546. are a lot missing, for example undo stack management and garbage
  547. collection.  The routines presented here aren't as "clean" as I'd like
  548. because they have to know how the undo stack is implemented.
  549.  
  550. Note:  When I say walk the stack, I mean move towards the older events.
  551. I do this because it is easy and in the case of undo() and thats what you
  552. want.
  553.  
  554.  
  555. The next routine is used to make space available to hold a copy of the
  556. text that will be deleted.  Basically, it figures out which (if any) of
  557. the older events need to be removed from the stack to make room in the
  558. bag.  It does this by looking at delete events (the only event that
  559. saves text) and finding an event such that by deleting that event and all
  560. older events, it will remove the minimum number of events necessary to
  561. free enough space so that the bag can hold space_needed more characters.
  562. The key here is that the number of characters in the bag is the sum of
  563. all delete events (the n in the Undo structure).  Note it would be
  564. faster, in general, to walk the stack backwards (from oldest event to
  565. youngest) and find the first event that met the requirements but that is
  566. not possible the way I implemented the stacks.
  567.  
  568.  
  569.      /* Check to see if space_needed is available in the bag.  If not,
  570.       *   try and pack the bag and stack to make enough room.  If more
  571.       *   space is requested than we allow, clear the stack because if
  572.       *   we can't save this undo, every undo before this one is
  573.       *   invalid.
  574.       * Returns:
  575.       *   TRUE:  Bag (now) has enough room.
  576.       *   FALSE:  You want too much space and can't have it.  Undo stack
  577.       *     cleared.  Try again with a more reasonable request.
  578.       */
  579.      static int open_bag(space_needed) int space_needed;
  580.      {
  581.        int tot, da_total, total_so_far;
  582.        Undo *ptr, *da_winner;
  583.        UndoHeader *header;
  584.  
  585.        header = <the undo header for the current buffer>;
  586.  
  587.        total_so_far = bag_size(header->bag); /* number of characters in bag */
  588.        tot = space_needed -(max_undo_saved -total_so_far);
  589.  
  590.        if (tot <= 0) return TRUE;        /* Plenty of room! */
  591.  
  592.        if (space_needed > max_undo_saved)    /* You want too much! */
  593.        {
  594.      clear_undos();
  595.      return FALSE;
  596.        }
  597.  
  598.        da_winner = NULL;
  599.        for (ptr = <walk undo stack starting at the most recent event>)
  600.        {
  601.      if (ptr->type == BU_DELETE)
  602.      {
  603.        if (total_so_far >= tot)    /* found enough space here */
  604.        {
  605.          da_winner = ptr;
  606.          da_total = total_so_far;
  607.        }
  608.        else break;        /* the last one was the one we wanted */
  609.        total_so_far -= ptr->n;
  610.      }
  611.        }
  612.  
  613.        /* We KNOW (and can prove it) that da_winner != NULL because
  614.         *   bag_size >= tot > max - bag_size
  615.         *   (from
  616.         *   max_undo_saved >= space_needed > max_undo_saved -bag_size
  617.         *   among other things).  Since bag_size is the sum of all the
  618.         *   BU_DELETEs, there must be one or more events that are
  619.         *   winners.
  620.         */
  621.        for (ptr = <walk undo stack starting at da_winner>)
  622.        {
  623.      free_undo(ptr);
  624.        }
  625.        pack_bag(da_total);    /* remove text from bag, fix up pointers */
  626.  
  627.        return TRUE;
  628.      }
  629.  
  630.  
  631.      /* Go though the undo stack and adjust the text indices to reflect
  632.       * n characters being removed from the front of the bag.  Shift n
  633.       * characters off the front of the bag.
  634.       */
  635.      static void pack_bag(n) int n;
  636.      {
  637.        Undo *ptr;
  638.        UndoHeader *header;
  639.  
  640.        header = <the undo header for the current buffer>;
  641.  
  642.        for (ptr = <walk undo stack starting at the most recent event>)
  643.      if (ptr->type == BU_DELETE)
  644.      {
  645.        <adjust ptr->text back by n characters>
  646.      }
  647.  
  648.         /* remove n characters from front of bag */
  649.        slide_bag(header->bag,n);
  650.      }
  651.  
  652.  
  653. Here are a couple of routines that you will need if you have a LLE.
  654. This is how to calculate and use undo marks.
  655.  
  656.      static void goto_unmark(mark) UnMark *mark;
  657.      {
  658.        goto_line(mark->line);
  659.        next_character(mark->offset);
  660.      }
  661.  
  662.      static void set_unmark(mark) UnMark *mark;
  663.      {
  664.        extern Mark *the_dot;    /* the dot in the current buffer */
  665.  
  666.        register Line *lp, *dot_line;
  667.        register int line;
  668.  
  669.        dot_line = the_dot->line;
  670.        for (line = 1, lp = BUFFER_FIRST_LINE(current_buffer);
  671.         lp != dot_line; lp = lp->l_next)
  672.      line++;
  673.  
  674.        mark->line = line;
  675.        mark->offset = the_dot->offset;
  676.      }
  677.