home *** CD-ROM | disk | FTP | other *** search
/ vim.ftp.fu-berlin.de / 2015-02-03.vim.ftp.fu-berlin.de.tar / vim.ftp.fu-berlin.de / amiga / vim46src.lha / vim-4.6 / src / undo.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-02-06  |  26.7 KB  |  1,055 lines
  1. /* vi:set ts=4 sw=4:
  2.  *
  3.  * VIM - Vi IMproved        by Bram Moolenaar
  4.  *
  5.  * Do ":help uganda"  in Vim to read copying and usage conditions.
  6.  * Do ":help credits" in Vim to see a list of people who contributed.
  7.  */
  8.  
  9. /*
  10.  * undo.c: multi level undo facility
  11.  *
  12.  * The saved lines are stored in a list of lists (one for each buffer):
  13.  *
  14.  * b_u_oldhead------------------------------------------------+
  15.  *                                                            |
  16.  *                                                            V
  17.  *                +--------------+    +--------------+    +--------------+
  18.  * b_u_newhead--->| u_header     |    | u_header     |    | u_header     |
  19.  *                |     uh_next------>|     uh_next------>|     uh_next---->NULL
  20.  *         NULL<--------uh_prev  |<---------uh_prev  |<---------uh_prev  |
  21.  *                |     uh_entry |    |     uh_entry |    |     uh_entry |
  22.  *                +--------|-----+    +--------|-----+    +--------|-----+
  23.  *                         |                   |                   |
  24.  *                         V                   V                   V
  25.  *                +--------------+    +--------------+    +--------------+
  26.  *                | u_entry      |    | u_entry      |    | u_entry      |
  27.  *                |     ue_next  |    |     ue_next  |    |     ue_next  |
  28.  *                +--------|-----+    +--------|-----+    +--------|-----+
  29.  *                         |                   |                   |
  30.  *                         V                   V                   V
  31.  *                +--------------+            NULL                NULL
  32.  *                | u_entry      |
  33.  *                |     ue_next  |
  34.  *                +--------|-----+
  35.  *                         |
  36.  *                         V
  37.  *                        etc.
  38.  *
  39.  * Each u_entry list contains the information for one undo or redo.
  40.  * curbuf->b_u_curhead points to the header of the last undo (the next redo),
  41.  * or is NULL if nothing has been undone.
  42.  *
  43.  * All data is allocated with u_alloc_line(), thus it will be freed as soon as
  44.  * we switch files!
  45.  */
  46.  
  47. #include "vim.h"
  48. #include "globals.h"
  49. #include "proto.h"
  50. #include "option.h"
  51.  
  52. static void u_getbot __ARGS((void));
  53. static int u_savecommon __ARGS((linenr_t, linenr_t, linenr_t));
  54. static void u_undoredo __ARGS((void));
  55. static void u_undo_end __ARGS((void));
  56. static void u_freelist __ARGS((struct u_header *));
  57. static void u_freeentry __ARGS((struct u_entry *, long));
  58.  
  59. static char_u *u_blockalloc __ARGS((long_u));
  60. static void u_free_line __ARGS((char_u *));
  61. static char_u *u_alloc_line __ARGS((unsigned));
  62. static char_u *u_save_line __ARGS((linenr_t));
  63.  
  64. static long        u_newcount, u_oldcount;
  65.  
  66. /*
  67.  * save the current line for both the "u" and "U" command
  68.  */
  69.     int
  70. u_save_cursor()
  71. {
  72.     return (u_save((linenr_t)(curwin->w_cursor.lnum - 1), (linenr_t)(curwin->w_cursor.lnum + 1)));
  73. }
  74.  
  75. /*
  76.  * Save the lines between "top" and "bot" for both the "u" and "U" command.
  77.  * "top" may be 0 and bot may be curbuf->b_ml.ml_line_count + 1.
  78.  * Returns FAIL when lines could not be saved, OK otherwise.
  79.  */
  80.     int
  81. u_save(top, bot)
  82.     linenr_t top, bot;
  83. {
  84.     if (undo_off)
  85.         return OK;
  86.  
  87.     if (top > curbuf->b_ml.ml_line_count ||
  88.                             top >= bot || bot > curbuf->b_ml.ml_line_count + 1)
  89.         return FALSE;    /* rely on caller to do error messages */
  90.  
  91.     if (top + 2 == bot)
  92.         u_saveline((linenr_t)(top + 1));
  93.  
  94.     return (u_savecommon(top, bot, (linenr_t)0));
  95. }
  96.  
  97. /*
  98.  * save the line "lnum" (used by :s command)
  99.  * The line is replaced, so the new bottom line is lnum + 1.
  100.  */
  101.     int
  102. u_savesub(lnum)
  103.     linenr_t    lnum;
  104. {
  105.     if (undo_off)
  106.         return OK;
  107.  
  108.     return (u_savecommon(lnum - 1, lnum + 1, lnum + 1));
  109. }
  110.  
  111. /*
  112.  * a new line is inserted before line "lnum" (used by :s command)
  113.  * The line is inserted, so the new bottom line is lnum + 1.
  114.  */
  115.      int
  116. u_inssub(lnum)
  117.     linenr_t    lnum;
  118. {
  119.     if (undo_off)
  120.         return OK;
  121.  
  122.     return (u_savecommon(lnum - 1, lnum, lnum + 1));
  123. }
  124.  
  125. /*
  126.  * save the lines "lnum" - "lnum" + nlines (used by delete command)
  127.  * The lines are deleted, so the new bottom line is lnum, unless the buffer
  128.  * becomes empty.
  129.  */
  130.     int
  131. u_savedel(lnum, nlines)
  132.     linenr_t    lnum;
  133.     long        nlines;
  134. {
  135.     if (undo_off)
  136.         return OK;
  137.  
  138.     return (u_savecommon(lnum - 1, lnum + nlines,
  139.                         nlines == curbuf->b_ml.ml_line_count ? 2 : lnum));
  140. }
  141.  
  142.     static int 
  143. u_savecommon(top, bot, newbot)
  144.     linenr_t top, bot;
  145.     linenr_t newbot;
  146. {
  147.     linenr_t        lnum;
  148.     long            i;
  149.     struct u_header *uhp;
  150.     struct u_entry    *uep;
  151.     long            size;
  152.  
  153.     /*
  154.      * if curbuf->b_u_synced == TRUE make a new header
  155.      */
  156.     if (curbuf->b_u_synced)
  157.     {
  158.         /*
  159.          * if we undid more than we redid, free the entry lists before and
  160.          * including curbuf->b_u_curhead
  161.          */
  162.         while (curbuf->b_u_curhead != NULL)
  163.             u_freelist(curbuf->b_u_newhead);
  164.  
  165.         /*
  166.          * free headers to keep the size right
  167.          */
  168.         while (curbuf->b_u_numhead > p_ul && curbuf->b_u_oldhead != NULL)
  169.             u_freelist(curbuf->b_u_oldhead);
  170.  
  171.         if (p_ul < 0)            /* no undo at all */
  172.             return OK;
  173.  
  174.         /*
  175.          * make a new header entry
  176.          */
  177.         uhp = (struct u_header *)u_alloc_line((unsigned)sizeof(struct u_header));
  178.         if (uhp == NULL)
  179.             goto nomem;
  180.         uhp->uh_prev = NULL;
  181.         uhp->uh_next = curbuf->b_u_newhead;
  182.         if (curbuf->b_u_newhead != NULL)
  183.             curbuf->b_u_newhead->uh_prev = uhp;
  184.         uhp->uh_entry = NULL;
  185.         uhp->uh_cursor = curwin->w_cursor;        /* save cursor pos. for undo */
  186.  
  187.         /* save changed and buffer empty flag for undo */
  188.         uhp->uh_flags = (curbuf->b_changed ? UH_CHANGED : 0) +
  189.                        ((curbuf->b_ml.ml_flags & ML_EMPTY) ? UH_EMPTYBUF : 0);
  190.  
  191.         /* save named marks for undo */
  192.         vim_memmove(uhp->uh_namedm, curbuf->b_namedm, sizeof(FPOS) * NMARKS); 
  193.         curbuf->b_u_newhead = uhp;
  194.         if (curbuf->b_u_oldhead == NULL)
  195.             curbuf->b_u_oldhead = uhp;
  196.         ++curbuf->b_u_numhead;
  197.     }
  198.     else    /* find line number for ue_bot for previous u_save() */
  199.         u_getbot();
  200.  
  201.     size = bot - top - 1;
  202. #if !defined(UNIX) && !defined(DJGPP) && !defined(WIN32) && !defined(__EMX__)
  203.         /*
  204.          * With Amiga and MSDOS we can't handle big undo's, because then
  205.          * u_alloc_line would have to allocate a block larger than 32K
  206.          */
  207.     if (size >= 8000)
  208.         goto nomem;
  209. #endif
  210.  
  211.     /*
  212.      * add lines in front of entry list
  213.      */
  214.     uep = (struct u_entry *)u_alloc_line((unsigned)sizeof(struct u_entry));
  215.     if (uep == NULL)
  216.         goto nomem;
  217.  
  218.     uep->ue_size = size;
  219.     uep->ue_top = top;
  220.     uep->ue_lcount = 0;
  221.     if (newbot)
  222.         uep->ue_bot = newbot;
  223.         /*
  224.          * Use 0 for ue_bot if bot is below last line.
  225.          * Otherwise we have to compute ue_bot later.
  226.          */
  227.     else if (bot > curbuf->b_ml.ml_line_count)
  228.         uep->ue_bot = 0;
  229.     else
  230.         uep->ue_lcount = curbuf->b_ml.ml_line_count;
  231.  
  232.     if (size)
  233.     {
  234.         if ((uep->ue_array = (char_u **)u_alloc_line((unsigned)(sizeof(char_u *) * size))) == NULL)
  235.         {
  236.             u_freeentry(uep, 0L);
  237.             goto nomem;
  238.         }
  239.         for (i = 0, lnum = top + 1; i < size; ++i)
  240.         {
  241.             if ((uep->ue_array[i] = u_save_line(lnum++)) == NULL)
  242.             {
  243.                 u_freeentry(uep, i);
  244.                 goto nomem;
  245.             }
  246.         }
  247.     }
  248.     uep->ue_next = curbuf->b_u_newhead->uh_entry;
  249.     curbuf->b_u_newhead->uh_entry = uep;
  250.     curbuf->b_u_synced = FALSE;
  251.     return OK;
  252.  
  253. nomem:
  254.     if (ask_yesno((char_u *)"No undo possible; continue anyway", TRUE) == 'y')
  255.     {
  256.         undo_off = TRUE;            /* will be reset when character typed */
  257.         return OK;
  258.     }
  259.     do_outofmem_msg();
  260.     return FAIL;
  261. }
  262.  
  263.     void
  264. u_undo(count)
  265.     int count;
  266. {
  267.     /*
  268.      * If we get an undo command while executing a macro, we behave like the 
  269.      * original vi. If this happens twice in one macro the result will not
  270.      * be compatible.
  271.      */
  272.     if (curbuf->b_u_synced == FALSE)
  273.     {
  274.         u_sync();
  275.         count = 1;
  276.     }
  277.  
  278.     u_newcount = 0;
  279.     u_oldcount = 0;
  280.     while (count--)
  281.     {
  282.         if (curbuf->b_u_curhead == NULL)            /* first undo */
  283.             curbuf->b_u_curhead = curbuf->b_u_newhead;
  284.         else if (p_ul > 0)                            /* multi level undo */
  285.                                                     /* get next undo */
  286.             curbuf->b_u_curhead = curbuf->b_u_curhead->uh_next;
  287.                                                     /* nothing to undo */
  288.         if (curbuf->b_u_numhead == 0 || curbuf->b_u_curhead == NULL)
  289.         {
  290.                                     /* stick curbuf->b_u_curhead at end */
  291.             curbuf->b_u_curhead = curbuf->b_u_oldhead;
  292.             beep_flush();
  293.             break;
  294.         }
  295.  
  296.         u_undoredo();
  297.     }
  298.     u_undo_end();
  299. }
  300.  
  301.     void
  302. u_redo(count)
  303.     int count;
  304. {
  305.     u_newcount = 0;
  306.     u_oldcount = 0;
  307.     while (count--)
  308.     {
  309.         if (curbuf->b_u_curhead == NULL || p_ul <= 0)    /* nothing to redo */
  310.         {
  311.             beep_flush();
  312.             break;
  313.         }
  314.  
  315.         u_undoredo();
  316.                                                     /* advance for next redo */
  317.         curbuf->b_u_curhead = curbuf->b_u_curhead->uh_prev;
  318.     }
  319.     u_undo_end();
  320. }
  321.  
  322. /*
  323.  * u_undoredo: common code for undo and redo
  324.  *
  325.  * The lines in the file are replaced by the lines in the entry list at
  326.  * curbuf->b_u_curhead. The replaced lines in the file are saved in the entry
  327.  * list for the next undo/redo.
  328.  */
  329.     static void
  330. u_undoredo()
  331. {
  332.     char_u        **newarray = NULL;
  333.     linenr_t    oldsize;
  334.     linenr_t    newsize;
  335.     linenr_t    top, bot;
  336.     linenr_t    lnum;
  337.     linenr_t    newlnum = MAXLNUM;
  338.     long        i;
  339.     struct u_entry *uep, *nuep;
  340.     struct u_entry *newlist = NULL;
  341.     int            old_flags;
  342.     int            new_flags;
  343.     FPOS        namedm[NMARKS];
  344.     int            empty_buffer;                /* buffer became empty */
  345.  
  346.     old_flags = curbuf->b_u_curhead->uh_flags;
  347.     new_flags = (curbuf->b_changed ? UH_CHANGED : 0) +
  348.                ((curbuf->b_ml.ml_flags & ML_EMPTY) ? UH_EMPTYBUF : 0);
  349.     if (old_flags & UH_CHANGED)
  350.         CHANGED;
  351.     else
  352.         UNCHANGED(curbuf);
  353.     setpcmark();
  354.  
  355.     /*
  356.      * save marks before undo/redo
  357.      */
  358.     vim_memmove(namedm, curbuf->b_namedm, sizeof(FPOS) * NMARKS); 
  359.     curbuf->b_op_start.lnum = curbuf->b_ml.ml_line_count;
  360.     curbuf->b_op_start.col = 0;
  361.     curbuf->b_op_end.lnum = 0;
  362.     curbuf->b_op_end.col = 0;
  363.  
  364.     for (uep = curbuf->b_u_curhead->uh_entry; uep != NULL; uep = nuep)
  365.     {
  366.         top = uep->ue_top;
  367.         bot = uep->ue_bot;
  368.         if (bot == 0)
  369.             bot = curbuf->b_ml.ml_line_count + 1;
  370.         if (top > curbuf->b_ml.ml_line_count || top >= bot || bot > curbuf->b_ml.ml_line_count + 1)
  371.         {
  372.             EMSG("u_undo: line numbers wrong");
  373.             CHANGED;        /* don't want UNCHANGED now */
  374.             return;
  375.         }
  376.  
  377.         if (top < newlnum)
  378.         {
  379.             newlnum = top;
  380.             curwin->w_cursor.lnum = top + 1;
  381.         }
  382.         oldsize = bot - top - 1;    /* number of lines before undo */
  383.         newsize = uep->ue_size;        /* number of lines after undo */
  384.  
  385.         empty_buffer = FALSE;
  386.  
  387.         /* delete the lines between top and bot and save them in newarray */
  388.         if (oldsize)
  389.         {
  390.             if ((newarray = (char_u **)u_alloc_line((unsigned)(sizeof(char_u *) * oldsize))) == NULL)
  391.             {
  392.                 do_outofmem_msg();
  393.                 /*
  394.                  * We have messed up the entry list, repair is impossible.
  395.                  * we have to free the rest of the list.
  396.                  */
  397.                 while (uep != NULL)
  398.                 {
  399.                     nuep = uep->ue_next;
  400.                     u_freeentry(uep, uep->ue_size);
  401.                     uep = nuep;
  402.                 }
  403.                 break;
  404.             }
  405.             /* delete backwards, it goes faster in most cases */
  406.             for (lnum = bot - 1, i = oldsize; --i >= 0; --lnum)
  407.             {
  408.                     /* what can we do when we run out of memory? */
  409.                 if ((newarray[i] = u_save_line(lnum)) == NULL)
  410.                     do_outofmem_msg();
  411.                     /* remember we deleted the last line in the buffer, and a
  412.                      * dummy empty line will be inserted */
  413.                 if (curbuf->b_ml.ml_line_count == 1)
  414.                     empty_buffer = TRUE;
  415.                 ml_delete(lnum, FALSE);
  416.             }
  417.         }
  418.  
  419.         /* insert the lines in u_array between top and bot */
  420.         if (newsize)
  421.         {
  422.             for (lnum = top, i = 0; i < newsize; ++i, ++lnum)
  423.             {
  424.                 /*
  425.                  * If the file is empty, there is an empty line 1 that we
  426.                  * should get rid of, by replacing it with the new line
  427.                  */
  428.                 if (empty_buffer && lnum == 0)
  429.                     ml_replace((linenr_t)1, uep->ue_array[i], TRUE);
  430.                 else
  431.                     ml_append(lnum, uep->ue_array[i], (colnr_t)0, FALSE);
  432.                 u_free_line(uep->ue_array[i]);
  433.             }
  434.             u_free_line((char_u *)uep->ue_array);
  435.         }
  436.  
  437.         /* adjust marks */
  438.         if (oldsize != newsize)
  439.         {
  440.             mark_adjust(top + 1, top + oldsize, MAXLNUM,
  441.                                                (long)newsize - (long)oldsize);
  442.             if (curbuf->b_op_start.lnum > top + oldsize)
  443.                 curbuf->b_op_start.lnum += newsize - oldsize;
  444.             if (curbuf->b_op_end.lnum > top + oldsize)
  445.                 curbuf->b_op_end.lnum += newsize - oldsize;
  446.         }
  447.         /* set '[ and '] mark */
  448.         if (top + 1 < curbuf->b_op_start.lnum)
  449.             curbuf->b_op_start.lnum = top + 1;
  450.         if (newsize == 0 && top + 1 > curbuf->b_op_end.lnum)
  451.             curbuf->b_op_end.lnum = top + 1;
  452.         else if (top + newsize > curbuf->b_op_end.lnum)
  453.             curbuf->b_op_end.lnum = top + newsize;
  454.  
  455.         u_newcount += newsize;
  456.         u_oldcount += oldsize;
  457.         uep->ue_size = oldsize;
  458.         uep->ue_array = newarray;
  459.         uep->ue_bot = top + newsize + 1;
  460.  
  461.         /*
  462.          * insert this entry in front of the new entry list
  463.          */
  464.         nuep = uep->ue_next;
  465.         uep->ue_next = newlist;
  466.         newlist = uep;
  467.     }
  468.  
  469.     curbuf->b_u_curhead->uh_entry = newlist;
  470.     curbuf->b_u_curhead->uh_flags = new_flags;
  471.     if ((old_flags & UH_EMPTYBUF) && bufempty())
  472.         curbuf->b_ml.ml_flags |= ML_EMPTY;
  473.  
  474.     /*
  475.      * restore marks from before undo/redo
  476.      */
  477.     for (i = 0; i < NMARKS; ++i)
  478.         if (curbuf->b_u_curhead->uh_namedm[i].lnum)
  479.         {
  480.             curbuf->b_namedm[i] = curbuf->b_u_curhead->uh_namedm[i];
  481.             curbuf->b_u_curhead->uh_namedm[i] = namedm[i];
  482.         }
  483.  
  484.     /*
  485.      * If the cursor is only off by one line, put it at the same position as
  486.      * before starting the change (for the "o" command).
  487.      * Otherwise the cursor should go to the first undone line.
  488.      */
  489.     if (curbuf->b_u_curhead->uh_cursor.lnum + 1 == curwin->w_cursor.lnum &&
  490.                                                     curwin->w_cursor.lnum > 1)
  491.         --curwin->w_cursor.lnum;
  492.     if (curbuf->b_u_curhead->uh_cursor.lnum == curwin->w_cursor.lnum)
  493.         curwin->w_cursor.col = curbuf->b_u_curhead->uh_cursor.col;
  494.     else if (curwin->w_cursor.lnum <= curbuf->b_ml.ml_line_count)
  495.         beginline(MAYBE);
  496.     /* We still seem to need the case below because sometimes we get here with
  497.      * the current cursor line being one past the end (eg after adding lines
  498.      * at the end of the file, and then undoing it).  Is it fair enough that
  499.      * this happens? -- webb
  500.      */
  501.     else
  502.         curwin->w_cursor.col = 0;
  503. }
  504.  
  505. /*
  506.  * If we deleted or added lines, report the number of less/more lines.
  507.  * Otherwise, report the number of changes (this may be incorrect
  508.  * in some cases, but it's better than nothing).
  509.  */
  510.     static void
  511. u_undo_end()
  512. {
  513.     if ((u_oldcount -= u_newcount) != 0)
  514.         msgmore(-u_oldcount);
  515.     else if (u_newcount > p_report)
  516.         smsg((char_u *)"%ld change%s", u_newcount, plural(u_newcount));
  517.  
  518.     update_curbuf(CURSUPD);        /* need to update all windows in this buffer */
  519. }
  520.  
  521. /*
  522.  * u_sync: stop adding to the current entry list
  523.  */
  524.     void
  525. u_sync()
  526. {
  527.     if (curbuf->b_u_synced)
  528.         return;                /* already synced */
  529.     u_getbot();                /* compute ue_bot of previous u_save */
  530.     curbuf->b_u_curhead = NULL;
  531. }
  532.  
  533. /*
  534.  * Called after writing the file and setting b_changed to FALSE.
  535.  * Now an undo means that the buffer is modified.
  536.  */
  537.     void
  538. u_unchanged(buf)
  539.     BUF        *buf;
  540. {
  541.     register struct u_header *uh;
  542.  
  543.     for (uh = buf->b_u_newhead; uh; uh = uh->uh_next)
  544.         uh->uh_flags |= UH_CHANGED;
  545.     buf->b_did_warn = FALSE;
  546. }
  547.  
  548. /*
  549.  * u_getbot(): compute the line number of the previous u_save
  550.  *                 It is called only when b_u_synced is FALSE.
  551.  */
  552.     static void
  553. u_getbot()
  554. {
  555.     register struct u_entry *uep;
  556.  
  557.     if (curbuf->b_u_newhead == NULL ||
  558.                                 (uep = curbuf->b_u_newhead->uh_entry) == NULL)
  559.     {
  560.         EMSG("undo list corrupt");
  561.         return;
  562.     }
  563.  
  564.     if (uep->ue_lcount != 0)
  565.     {
  566.         /*
  567.          * the new ue_bot is computed from the number of lines that has been
  568.          * inserted (0 - deleted) since calling u_save. This is equal to the old
  569.          * line count subtracted from the current line count.
  570.          */
  571.         uep->ue_bot = uep->ue_top + uep->ue_size + 1 +
  572.                                 (curbuf->b_ml.ml_line_count - uep->ue_lcount);
  573.         if (uep->ue_bot < 1 || uep->ue_bot > curbuf->b_ml.ml_line_count)
  574.         {
  575.             EMSG("undo line missing");
  576.             uep->ue_bot = uep->ue_top + 1;    /* assume all lines deleted, will
  577.                                              * get all the old lines back
  578.                                              * without deleting the current
  579.                                              * ones */
  580.         }
  581.         uep->ue_lcount = 0;
  582.     }
  583.  
  584.     curbuf->b_u_synced = TRUE;
  585. }
  586.  
  587. /*
  588.  * u_freelist: free one entry list and adjust the pointers
  589.  */
  590.     static void
  591. u_freelist(uhp)
  592.     struct u_header *uhp;
  593. {
  594.     register struct u_entry *uep, *nuep;
  595.  
  596.     for (uep = uhp->uh_entry; uep != NULL; uep = nuep)
  597.     {
  598.         nuep = uep->ue_next;
  599.         u_freeentry(uep, uep->ue_size);
  600.     }
  601.  
  602.     if (curbuf->b_u_curhead == uhp)
  603.         curbuf->b_u_curhead = NULL;
  604.  
  605.     if (uhp->uh_next == NULL)
  606.         curbuf->b_u_oldhead = uhp->uh_prev;
  607.     else
  608.         uhp->uh_next->uh_prev = uhp->uh_prev;
  609.  
  610.     if (uhp->uh_prev == NULL)
  611.         curbuf->b_u_newhead = uhp->uh_next;
  612.     else
  613.         uhp->uh_prev->uh_next = uhp->uh_next;
  614.  
  615.     u_free_line((char_u *)uhp);
  616.     --curbuf->b_u_numhead;
  617. }
  618.  
  619. /*
  620.  * free entry 'uep' and 'n' lines in uep->ue_array[]
  621.  */
  622.     static void
  623. u_freeentry(uep, n)
  624.     struct u_entry *uep;
  625.     register long n;
  626. {
  627.     while (n)
  628.         u_free_line(uep->ue_array[--n]);
  629.     u_free_line((char_u *)uep);
  630. }
  631.  
  632. /*
  633.  * invalidate the undo buffer; called when storage has already been released
  634.  */
  635.     void
  636. u_clearall(buf)
  637.     BUF        *buf;
  638. {
  639.     buf->b_u_newhead = buf->b_u_oldhead = buf->b_u_curhead = NULL;
  640.     buf->b_u_synced = TRUE;
  641.     buf->b_u_numhead = 0;
  642.     buf->b_u_line_ptr = NULL;
  643.     buf->b_u_line_lnum = 0;
  644. }
  645.  
  646. /*
  647.  * save the line "lnum" for the "U" command
  648.  */
  649.     void
  650. u_saveline(lnum)
  651.     linenr_t lnum;
  652. {
  653.     if (lnum == curbuf->b_u_line_lnum)        /* line is already saved */
  654.         return;
  655.     if (lnum < 1 || lnum > curbuf->b_ml.ml_line_count)    /* should never happen */
  656.         return;
  657.     u_clearline();
  658.     curbuf->b_u_line_lnum = lnum;
  659.     if (curwin->w_cursor.lnum == lnum)
  660.         curbuf->b_u_line_colnr = curwin->w_cursor.col;
  661.     else
  662.         curbuf->b_u_line_colnr = 0;
  663.     if ((curbuf->b_u_line_ptr = u_save_line(lnum)) == NULL)
  664.         do_outofmem_msg();
  665. }
  666.  
  667. /*
  668.  * clear the line saved for the "U" command
  669.  * (this is used externally for crossing a line while in insert mode)
  670.  */
  671.     void
  672. u_clearline()
  673. {
  674.     if (curbuf->b_u_line_ptr != NULL)
  675.     {
  676.         u_free_line(curbuf->b_u_line_ptr);
  677.         curbuf->b_u_line_ptr = NULL;
  678.         curbuf->b_u_line_lnum = 0;
  679.     }
  680. }
  681.  
  682. /*
  683.  * Implementation of the "U" command.
  684.  * Differentiation from vi: "U" can be undone with the next "U".
  685.  * We also allow the cursor to be in another line.
  686.  */
  687.     void
  688. u_undoline()
  689. {
  690.     colnr_t t;
  691.     char_u    *oldp;
  692.  
  693.     if (undo_off)
  694.         return;
  695.  
  696.     if (curbuf->b_u_line_ptr == NULL ||
  697.                         curbuf->b_u_line_lnum > curbuf->b_ml.ml_line_count)
  698.     {
  699.         beep_flush();
  700.         return;
  701.     }
  702.         /* first save the line for the 'u' command */
  703.     if (u_savecommon(curbuf->b_u_line_lnum - 1,
  704.                                 curbuf->b_u_line_lnum + 1, (linenr_t)0) == FAIL)
  705.         return;
  706.     oldp = u_save_line(curbuf->b_u_line_lnum);
  707.     if (oldp == NULL)
  708.     {
  709.         do_outofmem_msg();
  710.         return;
  711.     }
  712.     ml_replace(curbuf->b_u_line_lnum, curbuf->b_u_line_ptr, TRUE);
  713.     u_free_line(curbuf->b_u_line_ptr);
  714.     curbuf->b_u_line_ptr = oldp;
  715.  
  716.     t = curbuf->b_u_line_colnr;
  717.     if (curwin->w_cursor.lnum == curbuf->b_u_line_lnum)
  718.         curbuf->b_u_line_colnr = curwin->w_cursor.col;
  719.     curwin->w_cursor.col = t;
  720.     curwin->w_cursor.lnum = curbuf->b_u_line_lnum;
  721.     cursupdate();
  722.     updateScreen(VALID_TO_CURSCHAR);
  723. }
  724.  
  725. /*
  726.  * storage allocation for the undo lines and blocks of the current file
  727.  */
  728.  
  729. /*
  730.  * Memory is allocated in relatively large blocks. These blocks are linked
  731.  * in the allocated block list, headed by curbuf->b_block_head. They are all freed
  732.  * when abandoning a file, so we don't have to free every single line. The
  733.  * list is kept sorted on memory address.
  734.  * block_alloc() allocates a block.
  735.  * m_blockfree() frees all blocks.
  736.  *
  737.  * The available chunks of memory are kept in free chunk lists. There is
  738.  * one free list for each block of allocated memory. The list is kept sorted
  739.  * on memory address.
  740.  * u_alloc_line() gets a chunk from the free lists.
  741.  * u_free_line() returns a chunk to the free lists.
  742.  * curbuf->b_m_search points to the chunk before the chunk that was
  743.  * freed/allocated the last time.
  744.  * curbuf->b_mb_current points to the b_head where curbuf->b_m_search
  745.  * points into the free list.
  746.  *
  747.  *
  748.  *  b_block_head     /---> block #1     /---> block #2
  749.  *       mb_next ---/       mb_next ---/       mb_next ---> NULL
  750.  *       mb_info            mb_info            mb_info
  751.  *          |                  |                  |
  752.  *          V                  V                  V
  753.  *        NULL          free chunk #1.1      free chunk #2.1
  754.  *                             |                  |
  755.  *                             V                  V
  756.  *                      free chunk #1.2          NULL
  757.  *                             |
  758.  *                             V
  759.  *                            NULL
  760.  *
  761.  * When a single free chunk list would have been used, it could take a lot
  762.  * of time in u_free_line() to find the correct place to insert a chunk in the
  763.  * free list. The single free list would become very long when many lines are
  764.  * changed (e.g. with :%s/^M$//).
  765.  */
  766.  
  767.     /*
  768.      * this blocksize is used when allocating new lines
  769.      */
  770. #define MEMBLOCKSIZE 2044
  771.  
  772. /*
  773.  * The size field contains the size of the chunk, including the size field itself.
  774.  *
  775.  * When the chunk is not in-use it is preceded with the m_info structure.
  776.  * The m_next field links it in one of the free chunk lists.
  777.  *
  778.  * On most unix systems structures have to be longword (32 or 64 bit) aligned.
  779.  * On most other systems they are short (16 bit) aligned.
  780.  */
  781.  
  782. /* the structure definitions are now in structs.h */
  783.  
  784. #ifdef ALIGN_LONG
  785.     /* size of m_size */
  786. # define M_OFFSET (sizeof(long_u))
  787. #else
  788.     /* size of m_size */
  789. # define M_OFFSET (sizeof(short_u))
  790. #endif
  791.  
  792. /*
  793.  * Allocate a block of memory and link it in the allocated block list.
  794.  */
  795.     static char_u *
  796. u_blockalloc(size)
  797.     long_u    size;
  798. {
  799.     struct m_block *p;
  800.     struct m_block *mp, *next;
  801.  
  802.     p = (struct m_block *)lalloc(size + sizeof(struct m_block), FALSE);
  803.     if (p != NULL)
  804.     {
  805.          /* Insert the block into the allocated block list, keeping it
  806.                      sorted on address. */
  807.         for (mp = &curbuf->b_block_head; (next = mp->mb_next) != NULL && next < p; mp = next)
  808.             ;
  809.         p->mb_next = next;                /* link in block list */
  810.         mp->mb_next = p;
  811.         p->mb_info.m_next = NULL;        /* clear free list */
  812.         p->mb_info.m_size = 0;
  813.         curbuf->b_mb_current = p;        /* remember current block */
  814.         curbuf->b_m_search = NULL;
  815.         p++;                            /* return usable memory */
  816.     }
  817.     return (char_u *)p;
  818. }
  819.  
  820. /*
  821.  * free all allocated memory blocks for the buffer 'buf'
  822.  */
  823.     void
  824. u_blockfree(buf)
  825.     BUF        *buf;
  826. {
  827.     struct m_block    *p, *np;
  828.  
  829.     for (p = buf->b_block_head.mb_next; p != NULL; p = np)
  830.     {
  831.         np = p->mb_next;
  832.         vim_free(p);
  833.     }
  834.     buf->b_block_head.mb_next = NULL;
  835.     buf->b_m_search = NULL;
  836.     buf->b_mb_current = NULL;
  837. }
  838.  
  839. /*
  840.  * Free a chunk of memory.
  841.  * Insert the chunk into the correct free list, keeping it sorted on address.
  842.  */
  843.     static void
  844. u_free_line(ptr)
  845.     char_u *ptr;
  846. {
  847.     register info_t        *next;
  848.     register info_t        *prev, *curr;
  849.     register info_t        *mp;
  850.     struct m_block        *nextb;
  851.  
  852.     if (ptr == NULL || ptr == IObuff)
  853.         return;    /* illegal address can happen in out-of-memory situations */
  854.  
  855.     mp = (info_t *)(ptr - M_OFFSET);
  856.  
  857.         /* find block where chunk could be a part off */
  858.         /* if we change curbuf->b_mb_current, curbuf->b_m_search is set to NULL */
  859.     if (curbuf->b_mb_current == NULL || mp < (info_t *)curbuf->b_mb_current)
  860.     {
  861.         curbuf->b_mb_current = curbuf->b_block_head.mb_next;
  862.         curbuf->b_m_search = NULL;
  863.     }
  864.     if ((nextb = curbuf->b_mb_current->mb_next) != NULL && (info_t *)nextb < mp)
  865.     {
  866.         curbuf->b_mb_current = nextb;
  867.         curbuf->b_m_search = NULL;
  868.     }
  869.     while ((nextb = curbuf->b_mb_current->mb_next) != NULL && (info_t *)nextb < mp)
  870.         curbuf->b_mb_current = nextb;
  871.  
  872.     curr = NULL;
  873.     /*
  874.      * If mp is smaller than curbuf->b_m_search->m_next go to the start of
  875.      * the free list
  876.      */
  877.     if (curbuf->b_m_search == NULL || mp < (curbuf->b_m_search->m_next))
  878.         next = &(curbuf->b_mb_current->mb_info);
  879.     else
  880.         next = curbuf->b_m_search;
  881.     /*
  882.      * The following loop is executed very often.
  883.      * Therefore it has been optimized at the cost of readability.
  884.      * Keep it fast!
  885.      */
  886. #ifdef SLOW_BUT_EASY_TO_READ
  887.     do
  888.     {
  889.         prev = curr;
  890.         curr = next;
  891.         next = next->m_next;
  892.     }
  893.     while (mp > next && next != NULL);
  894. #else
  895.     do                                        /* first, middle, last */
  896.     {
  897.         prev = next->m_next;                /* curr, next, prev */
  898.         if (prev == NULL || mp <= prev)
  899.         {
  900.             prev = curr;
  901.             curr = next;
  902.             next = next->m_next;
  903.             break;
  904.         }
  905.         curr = prev->m_next;                /* next, prev, curr */
  906.         if (curr == NULL || mp <= curr)
  907.         {
  908.             prev = next;
  909.             curr = prev->m_next;
  910.             next = curr->m_next;
  911.             break;
  912.         }
  913.         next = curr->m_next;                /* prev, curr, next */
  914.     }
  915.     while (mp > next && next != NULL);
  916. #endif
  917.  
  918. /* if *mp and *next are concatenated, join them into one chunk */
  919.     if ((char_u *)mp + mp->m_size == (char_u *)next)
  920.     {
  921.         mp->m_size += next->m_size;
  922.         mp->m_next = next->m_next;
  923.     }
  924.     else
  925.         mp->m_next = next;
  926.  
  927. /* if *curr and *mp are concatenated, join them */
  928.     if (prev != NULL && (char_u *)curr + curr->m_size == (char_u *)mp)
  929.     {
  930.         curr->m_size += mp->m_size;
  931.         curr->m_next = mp->m_next;
  932.         curbuf->b_m_search = prev;
  933.     }
  934.     else
  935.     {
  936.         curr->m_next = mp;
  937.         curbuf->b_m_search = curr;    /* put curbuf->b_m_search before freed chunk */
  938.     }
  939. }
  940.  
  941. /*
  942.  * Allocate and initialize a new line structure with room for at least
  943.  * 'size' characters plus a terminating NUL.
  944.  */
  945.     static char_u *
  946. u_alloc_line(size)
  947.     register unsigned size;
  948. {
  949.     register info_t *mp, *mprev, *mp2;
  950.     struct m_block    *mbp;
  951.     int                 size_align;
  952.  
  953. /*
  954.  * Add room for size field and trailing NUL byte.
  955.  * Adjust for minimal size (must be able to store info_t
  956.  * plus a trailing NUL, so the chunk can be released again)
  957.  */
  958.     size += M_OFFSET + 1;
  959.     if (size < sizeof(info_t) + 1)
  960.       size = sizeof(info_t) + 1;
  961.  
  962. /*
  963.  * round size up for alignment
  964.  */
  965.     size_align = (size + ALIGN_MASK) & ~ALIGN_MASK;
  966.  
  967. /*
  968.  * If curbuf->b_m_search is NULL (uninitialized free list) start at
  969.  * curbuf->b_block_head
  970.  */
  971.     if (curbuf->b_mb_current == NULL || curbuf->b_m_search == NULL)
  972.     {
  973.         curbuf->b_mb_current = &curbuf->b_block_head;
  974.         curbuf->b_m_search = &(curbuf->b_block_head.mb_info);
  975.     }
  976.  
  977. /* search for space in free list */
  978.     mprev = curbuf->b_m_search;
  979.     mbp = curbuf->b_mb_current;
  980.     mp = curbuf->b_m_search->m_next;
  981.     if (mp == NULL)
  982.     {
  983.         if (mbp->mb_next)
  984.             mbp = mbp->mb_next;
  985.         else
  986.             mbp = &curbuf->b_block_head;
  987.         mp = curbuf->b_m_search = &(mbp->mb_info);
  988.     }
  989.     while (mp->m_size < size)
  990.     {
  991.         if (mp == curbuf->b_m_search)        /* back where we started in free chunk list */
  992.         {
  993.             if (mbp->mb_next)
  994.                 mbp = mbp->mb_next;
  995.             else
  996.                 mbp = &curbuf->b_block_head;
  997.             mp = curbuf->b_m_search = &(mbp->mb_info);
  998.             if (mbp == curbuf->b_mb_current)    /* back where we started in block list */
  999.             {
  1000.                 int        n = (size_align > (MEMBLOCKSIZE / 4) ? size_align : MEMBLOCKSIZE);
  1001.  
  1002.                 mp = (info_t *)u_blockalloc((long_u)n);
  1003.                 if (mp == NULL)
  1004.                     return (NULL);
  1005.                 mp->m_size = n;
  1006.                 u_free_line((char_u *)mp + M_OFFSET);
  1007.                 mp = curbuf->b_m_search;
  1008.                 mbp = curbuf->b_mb_current;
  1009.             }
  1010.         }
  1011.         mprev = mp;
  1012.         if ((mp = mp->m_next) == NULL)        /* at end of the list */
  1013.             mp = &(mbp->mb_info);            /* wrap around to begin */
  1014.     }
  1015.  
  1016. /* if the chunk we found is large enough, split it up in two */
  1017.     if ((long)mp->m_size - size_align >= (long)(sizeof(info_t) + 1))
  1018.     {
  1019.         mp2 = (info_t *)((char_u *)mp + size_align);
  1020.         mp2->m_size = mp->m_size - size_align;
  1021.         mp2->m_next = mp->m_next;
  1022.         mprev->m_next = mp2;
  1023.         mp->m_size = size_align;
  1024.     }
  1025.     else                    /* remove *mp from the free list */
  1026.     {
  1027.         mprev->m_next = mp->m_next;
  1028.     }
  1029.     curbuf->b_m_search = mprev;
  1030.     curbuf->b_mb_current = mbp;
  1031.  
  1032.     mp = (info_t *)((char_u *)mp + M_OFFSET);
  1033.     *(char_u *)mp = NUL;                    /* set the first byte to NUL */
  1034.  
  1035.     return ((char_u *)mp);
  1036. }
  1037.  
  1038. /*
  1039.  * u_save_line(): allocate memory with u_alloc_line() and copy line 'lnum' into it.
  1040.  */
  1041.     static char_u *
  1042. u_save_line(lnum)
  1043.     linenr_t    lnum;
  1044. {
  1045.     register char_u *src;
  1046.     register char_u *dst;
  1047.     register unsigned len;
  1048.  
  1049.     src = ml_get(lnum);
  1050.     len = STRLEN(src);
  1051.     if ((dst = u_alloc_line(len)) != NULL)
  1052.         vim_memmove(dst, src, (size_t)(len + 1));
  1053.     return (dst);
  1054. }
  1055.