1 /* vi:set ts=8 sts=4 sw=4:
3 * VIM - Vi IMproved by Bram Moolenaar
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 * See README.txt for an overview of the Vim source code.
11 * undo.c: multi level undo facility
13 * The saved lines are stored in a list of lists (one for each buffer):
15 * b_u_oldhead------------------------------------------------+
18 * +--------------+ +--------------+ +--------------+
19 * b_u_newhead--->| u_header | | u_header | | u_header |
20 * | uh_next------>| uh_next------>| uh_next---->NULL
21 * NULL<--------uh_prev |<---------uh_prev |<---------uh_prev |
22 * | uh_entry | | uh_entry | | uh_entry |
23 * +--------|-----+ +--------|-----+ +--------|-----+
26 * +--------------+ +--------------+ +--------------+
27 * | u_entry | | u_entry | | u_entry |
28 * | ue_next | | ue_next | | ue_next |
29 * +--------|-----+ +--------|-----+ +--------|-----+
32 * +--------------+ NULL NULL
40 * Each u_entry list contains the information for one undo or redo.
41 * curbuf->b_u_curhead points to the header of the last undo (the next redo),
42 * or is NULL if nothing has been undone (end of the branch).
44 * For keeping alternate undo/redo branches the uh_alt field is used. Thus at
45 * each point in the list a branch may appear for an alternate to redo. The
46 * uh_seq field is numbered sequentially to be able to find a newer or older
49 * +---------------+ +---------------+
50 * b_u_oldhead --->| u_header | | u_header |
51 * | uh_alt_next ---->| uh_alt_next ----> NULL
52 * NULL <----- uh_alt_prev |<------ uh_alt_prev |
53 * | uh_prev | | uh_prev |
54 * +-----|---------+ +-----|---------+
57 * +---------------+ +---------------+
58 * | u_header | | u_header |
59 * | uh_alt_next | | uh_alt_next |
60 * b_u_newhead --->| uh_alt_prev | | uh_alt_prev |
61 * | uh_prev | | uh_prev |
62 * +-----|---------+ +-----|---------+
65 * NULL +---------------+ +---------------+
66 * | u_header | | u_header |
67 * | uh_alt_next ---->| uh_alt_next |
68 * | uh_alt_prev |<------ uh_alt_prev |
69 * | uh_prev | | uh_prev |
70 * +-----|---------+ +-----|---------+
75 * All data is allocated with U_ALLOC_LINE(), it will be freed as soon as the
81 /* See below: use malloc()/free() for memory management. */
82 #define U_USE_MALLOC 1
84 static void u_unch_branch
__ARGS((u_header_T
*uhp
));
85 static u_entry_T
*u_get_headentry
__ARGS((void));
86 static void u_getbot
__ARGS((void));
87 static int u_savecommon
__ARGS((linenr_T
, linenr_T
, linenr_T
));
88 static void u_doit
__ARGS((int count
));
89 static void u_undoredo
__ARGS((int undo
));
90 static void u_undo_end
__ARGS((int did_undo
, int absolute
));
91 static void u_add_time
__ARGS((char_u
*buf
, size_t buflen
, time_t tt
));
92 static void u_freeheader
__ARGS((buf_T
*buf
, u_header_T
*uhp
, u_header_T
**uhpp
));
93 static void u_freebranch
__ARGS((buf_T
*buf
, u_header_T
*uhp
, u_header_T
**uhpp
));
94 static void u_freeentries
__ARGS((buf_T
*buf
, u_header_T
*uhp
, u_header_T
**uhpp
));
95 static void u_freeentry
__ARGS((u_entry_T
*, long));
98 # define U_FREE_LINE(ptr) vim_free(ptr)
99 # define U_ALLOC_LINE(size) lalloc((long_u)((size) + 1), FALSE)
101 static void u_free_line
__ARGS((char_u
*ptr
, int keep
));
102 static char_u
*u_alloc_line
__ARGS((unsigned size
));
103 # define U_FREE_LINE(ptr) u_free_line((ptr), FALSE)
104 # define U_ALLOC_LINE(size) u_alloc_line(size)
106 static char_u
*u_save_line
__ARGS((linenr_T
));
108 static long u_newcount
, u_oldcount
;
111 * When 'u' flag included in 'cpoptions', we behave like vi. Need to remember
112 * the action that "u" should do.
114 static int undo_undoes
= FALSE
;
117 * Save the current line for both the "u" and "U" command.
118 * Returns OK or FAIL.
123 return (u_save((linenr_T
)(curwin
->w_cursor
.lnum
- 1),
124 (linenr_T
)(curwin
->w_cursor
.lnum
+ 1)));
128 * Save the lines between "top" and "bot" for both the "u" and "U" command.
129 * "top" may be 0 and bot may be curbuf->b_ml.ml_line_count + 1.
130 * Returns FAIL when lines could not be saved, OK otherwise.
139 if (top
> curbuf
->b_ml
.ml_line_count
||
140 top
>= bot
|| bot
> curbuf
->b_ml
.ml_line_count
+ 1)
141 return FALSE
; /* rely on caller to do error messages */
144 u_saveline((linenr_T
)(top
+ 1));
146 return (u_savecommon(top
, bot
, (linenr_T
)0));
150 * save the line "lnum" (used by ":s" and "~" command)
151 * The line is replaced, so the new bottom line is lnum + 1.
160 return (u_savecommon(lnum
- 1, lnum
+ 1, lnum
+ 1));
164 * a new line is inserted before line "lnum" (used by :s command)
165 * The line is inserted, so the new bottom line is lnum + 1.
174 return (u_savecommon(lnum
- 1, lnum
, lnum
+ 1));
178 * save the lines "lnum" - "lnum" + nlines (used by delete command)
179 * The lines are deleted, so the new bottom line is lnum, unless the buffer
183 u_savedel(lnum
, nlines
)
190 return (u_savecommon(lnum
- 1, lnum
+ nlines
,
191 nlines
== curbuf
->b_ml
.ml_line_count
? 2 : lnum
));
195 * Return TRUE when undo is allowed. Otherwise give an error message and
201 /* Don't allow changes when 'modifiable' is off. */
204 EMSG(_(e_modifiable
));
209 /* In the sandbox it's not allowed to change the text. */
217 /* Don't allow changes in the buffer while editing the cmdline. The
218 * caller of getcmdline() may get confused. */
229 u_savecommon(top
, bot
, newbot
)
236 u_header_T
*old_curhead
;
241 /* When making changes is not allowed return FAIL. It's a crude way to
242 * make all change commands fail. */
246 #ifdef FEAT_NETBEANS_INTG
248 * Netbeans defines areas that cannot be modified. Bail out here when
249 * trying to change text in a guarded area.
253 if (netbeans_is_guarded(top
, bot
))
260 EMSG(_(e_nbreadonly
));
268 * Saving text for undo means we are going to make a change. Give a
269 * warning for a read-only file before making the change, so that the
270 * FileChangedRO event can replace the buffer with a read-write version
271 * (e.g., obtained from a source control system).
276 size
= bot
- top
- 1;
279 * if curbuf->b_u_synced == TRUE make a new header
281 if (curbuf
->b_u_synced
)
284 /* Need to create new entry in b_changelist. */
285 curbuf
->b_new_change
= TRUE
;
291 * Make a new header entry. Do this first so that we don't mess
292 * up the undo info when out of memory.
294 uhp
= (u_header_T
*)U_ALLOC_LINE((unsigned)sizeof(u_header_T
));
302 * If we undid more than we redid, move the entry lists before and
303 * including curbuf->b_u_curhead to an alternate branch.
305 old_curhead
= curbuf
->b_u_curhead
;
306 if (old_curhead
!= NULL
)
308 curbuf
->b_u_newhead
= old_curhead
->uh_next
;
309 curbuf
->b_u_curhead
= NULL
;
313 * free headers to keep the size right
315 while (curbuf
->b_u_numhead
> p_ul
&& curbuf
->b_u_oldhead
!= NULL
)
317 u_header_T
*uhfree
= curbuf
->b_u_oldhead
;
319 /* If there is no branch only free one header. */
320 if (uhfree
->uh_alt_next
== NULL
)
321 u_freeheader(curbuf
, uhfree
, &old_curhead
);
324 /* Free the oldest alternate branch as a whole. */
325 while (uhfree
->uh_alt_next
!= NULL
)
326 uhfree
= uhfree
->uh_alt_next
;
327 u_freebranch(curbuf
, uhfree
, &old_curhead
);
331 if (uhp
== NULL
) /* no undo at all */
333 if (old_curhead
!= NULL
)
334 u_freebranch(curbuf
, old_curhead
, NULL
);
335 curbuf
->b_u_synced
= FALSE
;
340 uhp
->uh_next
= curbuf
->b_u_newhead
;
341 uhp
->uh_alt_next
= old_curhead
;
342 if (old_curhead
!= NULL
)
344 uhp
->uh_alt_prev
= old_curhead
->uh_alt_prev
;
345 if (uhp
->uh_alt_prev
!= NULL
)
346 uhp
->uh_alt_prev
->uh_alt_next
= uhp
;
347 old_curhead
->uh_alt_prev
= uhp
;
348 if (curbuf
->b_u_oldhead
== old_curhead
)
349 curbuf
->b_u_oldhead
= uhp
;
352 uhp
->uh_alt_prev
= NULL
;
353 if (curbuf
->b_u_newhead
!= NULL
)
354 curbuf
->b_u_newhead
->uh_prev
= uhp
;
356 uhp
->uh_seq
= ++curbuf
->b_u_seq_last
;
357 curbuf
->b_u_seq_cur
= uhp
->uh_seq
;
358 uhp
->uh_time
= time(NULL
);
359 curbuf
->b_u_seq_time
= uhp
->uh_time
+ 1;
362 uhp
->uh_entry
= NULL
;
363 uhp
->uh_getbot_entry
= NULL
;
364 uhp
->uh_cursor
= curwin
->w_cursor
; /* save cursor pos. for undo */
365 #ifdef FEAT_VIRTUALEDIT
366 if (virtual_active() && curwin
->w_cursor
.coladd
> 0)
367 uhp
->uh_cursor_vcol
= getviscol();
369 uhp
->uh_cursor_vcol
= -1;
372 /* save changed and buffer empty flag for undo */
373 uhp
->uh_flags
= (curbuf
->b_changed
? UH_CHANGED
: 0) +
374 ((curbuf
->b_ml
.ml_flags
& ML_EMPTY
) ? UH_EMPTYBUF
: 0);
376 /* save named marks and Visual marks for undo */
377 mch_memmove(uhp
->uh_namedm
, curbuf
->b_namedm
, sizeof(pos_T
) * NMARKS
);
379 uhp
->uh_visual
= curbuf
->b_visual
;
382 curbuf
->b_u_newhead
= uhp
;
383 if (curbuf
->b_u_oldhead
== NULL
)
384 curbuf
->b_u_oldhead
= uhp
;
385 ++curbuf
->b_u_numhead
;
389 if (p_ul
< 0) /* no undo at all */
393 * When saving a single line, and it has been saved just before, it
394 * doesn't make sense saving it again. Saves a lot of memory when
395 * making lots of changes inside the same line.
396 * This is only possible if the previous change didn't increase or
397 * decrease the number of lines.
398 * Check the ten last changes. More doesn't make sense and takes too
403 uep
= u_get_headentry();
405 for (i
= 0; i
< 10; ++i
)
410 /* If lines have been inserted/deleted we give up.
411 * Also when the line was included in a multi-line save. */
412 if ((curbuf
->b_u_newhead
->uh_getbot_entry
!= uep
413 ? (uep
->ue_top
+ uep
->ue_size
+ 1
415 ? curbuf
->b_ml
.ml_line_count
+ 1
417 : uep
->ue_lcount
!= curbuf
->b_ml
.ml_line_count
)
419 && top
>= uep
->ue_top
420 && top
+ 2 <= uep
->ue_top
+ uep
->ue_size
+ 1))
423 /* If it's the same line we can skip saving it again. */
424 if (uep
->ue_size
== 1 && uep
->ue_top
== top
)
428 /* It's not the last entry: get ue_bot for the last
429 * entry now. Following deleted/inserted lines go to
430 * the re-used entry. */
432 curbuf
->b_u_synced
= FALSE
;
434 /* Move the found entry to become the last entry. The
435 * order of undo/redo doesn't matter for the entries
436 * we move it over, since they don't change the line
437 * count and don't include this line. It does matter
438 * for the found entry if the line count is changed by
439 * the executed command. */
440 prev_uep
->ue_next
= uep
->ue_next
;
441 uep
->ue_next
= curbuf
->b_u_newhead
->uh_entry
;
442 curbuf
->b_u_newhead
->uh_entry
= uep
;
445 /* The executed command may change the line count. */
447 uep
->ue_bot
= newbot
;
448 else if (bot
> curbuf
->b_ml
.ml_line_count
)
452 uep
->ue_lcount
= curbuf
->b_ml
.ml_line_count
;
453 curbuf
->b_u_newhead
->uh_getbot_entry
= uep
;
462 /* find line number for ue_bot for previous u_save() */
466 #if !defined(UNIX) && !defined(DJGPP) && !defined(WIN32) && !defined(__EMX__)
468 * With Amiga and MSDOS 16 bit we can't handle big undo's, because
469 * then u_alloc_line would have to allocate a block larger than 32K
476 * add lines in front of entry list
478 uep
= (u_entry_T
*)U_ALLOC_LINE((unsigned)sizeof(u_entry_T
));
485 uep
->ue_bot
= newbot
;
487 * Use 0 for ue_bot if bot is below last line.
488 * Otherwise we have to compute ue_bot later.
490 else if (bot
> curbuf
->b_ml
.ml_line_count
)
494 uep
->ue_lcount
= curbuf
->b_ml
.ml_line_count
;
495 curbuf
->b_u_newhead
->uh_getbot_entry
= uep
;
500 if ((uep
->ue_array
= (char_u
**)U_ALLOC_LINE(
501 (unsigned)(sizeof(char_u
*) * size
))) == NULL
)
503 u_freeentry(uep
, 0L);
506 for (i
= 0, lnum
= top
+ 1; i
< size
; ++i
)
514 if ((uep
->ue_array
[i
] = u_save_line(lnum
++)) == NULL
)
522 uep
->ue_array
= NULL
;
523 uep
->ue_next
= curbuf
->b_u_newhead
->uh_entry
;
524 curbuf
->b_u_newhead
->uh_entry
= uep
;
525 curbuf
->b_u_synced
= FALSE
;
531 msg_silent
= 0; /* must display the prompt */
532 if (ask_yesno((char_u
*)_("No undo possible; continue anyway"), TRUE
)
535 undo_off
= TRUE
; /* will be reset when character typed */
538 do_outofmem_msg((long_u
)0);
543 * If 'cpoptions' contains 'u': Undo the previous undo or redo (vi compatible).
544 * If 'cpoptions' does not contain 'u': Always undo.
551 * If we get an undo command while executing a macro, we behave like the
552 * original vi. If this happens twice in one macro the result will not
555 if (curbuf
->b_u_synced
== FALSE
)
561 if (vim_strchr(p_cpo
, CPO_UNDO
) == NULL
)
564 undo_undoes
= !undo_undoes
;
569 * If 'cpoptions' contains 'u': Repeat the previous undo or redo.
570 * If 'cpoptions' does not contain 'u': Always redo.
576 if (vim_strchr(p_cpo
, CPO_UNDO
) == NULL
)
582 * Undo or redo, depending on 'undo_undoes', 'count' times.
588 int count
= startcount
;
595 if (curbuf
->b_ml
.ml_flags
& ML_EMPTY
)
601 if (curbuf
->b_u_curhead
== NULL
) /* first undo */
602 curbuf
->b_u_curhead
= curbuf
->b_u_newhead
;
603 else if (p_ul
> 0) /* multi level undo */
605 curbuf
->b_u_curhead
= curbuf
->b_u_curhead
->uh_next
;
606 /* nothing to undo */
607 if (curbuf
->b_u_numhead
== 0 || curbuf
->b_u_curhead
== NULL
)
609 /* stick curbuf->b_u_curhead at end */
610 curbuf
->b_u_curhead
= curbuf
->b_u_oldhead
;
612 if (count
== startcount
- 1)
614 MSG(_("Already at oldest change"));
624 if (curbuf
->b_u_curhead
== NULL
|| p_ul
<= 0)
626 beep_flush(); /* nothing to redo */
627 if (count
== startcount
- 1)
629 MSG(_("Already at newest change"));
637 /* Advance for next redo. Set "newhead" when at the end of the
638 * redoable changes. */
639 if (curbuf
->b_u_curhead
->uh_prev
== NULL
)
640 curbuf
->b_u_newhead
= curbuf
->b_u_curhead
;
641 curbuf
->b_u_curhead
= curbuf
->b_u_curhead
->uh_prev
;
644 u_undo_end(undo_undoes
, FALSE
);
647 static int lastmark
= 0;
650 * Undo or redo over the timeline.
651 * When "step" is negative go back in time, otherwise goes forward in time.
652 * When "sec" is FALSE make "step" steps, when "sec" is TRUE use "step" as
654 * When "absolute" is TRUE use "step" as the sequence number to jump to.
655 * "sec" must be FALSE then.
658 undo_time(step
, sec
, absolute
)
666 long closest_seq
= 0;
677 /* First make sure the current undoable change is synced. */
678 if (curbuf
->b_u_synced
== FALSE
)
683 if (curbuf
->b_ml
.ml_flags
& ML_EMPTY
)
686 /* "target" is the node below which we want to be.
687 * Init "closest" to a value we can't reach. */
695 /* When doing computations with time_t subtract starttime, because
696 * time_t converted to a long may result in a wrong number. */
698 target
= (long)(curbuf
->b_u_seq_time
- starttime
) + step
;
700 target
= curbuf
->b_u_seq_cur
+ step
;
710 closest
= (long)(time(NULL
) - starttime
+ 1);
712 closest
= curbuf
->b_u_seq_last
+ 2;
713 if (target
>= closest
)
714 target
= closest
- 1;
717 closest_start
= closest
;
718 closest_seq
= curbuf
->b_u_seq_cur
;
722 * 1. Search for "target", update "closest" to the best match found.
723 * 2. If "target" not found search for "closest".
725 * When using the closest time we use the sequence number in the second
726 * round, because there may be several entries with the same time.
728 for (round
= 1; round
<= 2; ++round
)
730 /* Find the path from the current state to where we want to go. The
731 * desired state can be anywhere in the undo tree, need to go all over
732 * it. We put "nomark" in uh_walk where we have been without success,
733 * "mark" where it could possibly be. */
737 if (curbuf
->b_u_curhead
== NULL
) /* at leaf of the tree */
738 uhp
= curbuf
->b_u_newhead
;
740 uhp
= curbuf
->b_u_curhead
;
745 val
= (long)(dosec
? (uhp
->uh_time
- starttime
) : uhp
->uh_seq
);
749 /* Remember the header that is closest to the target.
750 * It must be at least in the right direction (checked with
751 * "b_u_seq_cur"). When the timestamp is equal find the
752 * highest/lowest sequence number. */
753 if ((step
< 0 ? uhp
->uh_seq
<= curbuf
->b_u_seq_cur
754 : uhp
->uh_seq
> curbuf
->b_u_seq_cur
)
755 && ((dosec
&& val
== closest
)
757 ? uhp
->uh_seq
< closest_seq
758 : uhp
->uh_seq
> closest_seq
)
759 : closest
== closest_start
762 ? val
- target
<= closest
- target
763 : val
- target
<= target
- closest
)
765 ? target
- val
<= closest
- target
766 : target
- val
<= target
- closest
))))
769 closest_seq
= uhp
->uh_seq
;
773 /* Quit searching when we found a match. But when searching for a
774 * time we need to continue looking for the best uh_seq. */
775 if (target
== val
&& !dosec
)
778 /* go down in the tree if we haven't been there */
779 if (uhp
->uh_prev
!= NULL
&& uhp
->uh_prev
->uh_walk
!= nomark
780 && uhp
->uh_prev
->uh_walk
!= mark
)
783 /* go to alternate branch if we haven't been there */
784 else if (uhp
->uh_alt_next
!= NULL
785 && uhp
->uh_alt_next
->uh_walk
!= nomark
786 && uhp
->uh_alt_next
->uh_walk
!= mark
)
787 uhp
= uhp
->uh_alt_next
;
789 /* go up in the tree if we haven't been there and we are at the
790 * start of alternate branches */
791 else if (uhp
->uh_next
!= NULL
&& uhp
->uh_alt_prev
== NULL
792 && uhp
->uh_next
->uh_walk
!= nomark
793 && uhp
->uh_next
->uh_walk
!= mark
)
795 /* If still at the start we don't go through this change. */
796 if (uhp
== curbuf
->b_u_curhead
)
797 uhp
->uh_walk
= nomark
;
803 /* need to backtrack; mark this node as useless */
804 uhp
->uh_walk
= nomark
;
805 if (uhp
->uh_alt_prev
!= NULL
)
806 uhp
= uhp
->uh_alt_prev
;
812 if (uhp
!= NULL
) /* found it */
817 EMSGN(_("Undo number %ld not found"), step
);
821 if (closest
== closest_start
)
824 MSG(_("Already at oldest change"));
826 MSG(_("Already at newest change"));
830 target
= closest_seq
;
833 above
= TRUE
; /* stop above the header */
836 /* If we found it: Follow the path to go to where we want to be. */
840 * First go up the tree as much as needed.
844 uhp
= curbuf
->b_u_curhead
;
846 uhp
= curbuf
->b_u_newhead
;
849 if (uhp
== NULL
|| uhp
->uh_walk
!= mark
850 || (uhp
->uh_seq
== target
&& !above
))
852 curbuf
->b_u_curhead
= uhp
;
854 uhp
->uh_walk
= nomark
; /* don't go back down here */
858 * And now go down the tree (redo), branching off where needed.
860 uhp
= curbuf
->b_u_curhead
;
863 /* Go back to the first branch with a mark. */
864 while (uhp
->uh_alt_prev
!= NULL
865 && uhp
->uh_alt_prev
->uh_walk
== mark
)
866 uhp
= uhp
->uh_alt_prev
;
868 /* Find the last branch with a mark, that's the one. */
870 while (last
->uh_alt_next
!= NULL
871 && last
->uh_alt_next
->uh_walk
== mark
)
872 last
= last
->uh_alt_next
;
875 /* Make the used branch the first entry in the list of
876 * alternatives to make "u" and CTRL-R take this branch. */
877 while (uhp
->uh_alt_prev
!= NULL
)
878 uhp
= uhp
->uh_alt_prev
;
879 if (last
->uh_alt_next
!= NULL
)
880 last
->uh_alt_next
->uh_alt_prev
= last
->uh_alt_prev
;
881 last
->uh_alt_prev
->uh_alt_next
= last
->uh_alt_next
;
882 last
->uh_alt_prev
= NULL
;
883 last
->uh_alt_next
= uhp
;
884 uhp
->uh_alt_prev
= last
;
887 if (uhp
->uh_next
!= NULL
)
888 uhp
->uh_next
->uh_prev
= uhp
;
890 curbuf
->b_u_curhead
= uhp
;
892 if (uhp
->uh_walk
!= mark
)
893 break; /* must have reached the target */
895 /* Stop when going backwards in time and didn't find the exact
896 * header we were looking for. */
897 if (uhp
->uh_seq
== target
&& above
)
899 curbuf
->b_u_seq_cur
= target
- 1;
905 /* Advance "curhead" to below the header we last used. If it
906 * becomes NULL then we need to set "newhead" to this leaf. */
907 if (uhp
->uh_prev
== NULL
)
908 curbuf
->b_u_newhead
= uhp
;
909 curbuf
->b_u_curhead
= uhp
->uh_prev
;
912 if (uhp
->uh_seq
== target
) /* found it! */
916 if (uhp
== NULL
|| uhp
->uh_walk
!= mark
)
918 /* Need to redo more but can't find it... */
919 EMSG2(_(e_intern2
), "undo_time()");
924 u_undo_end(did_undo
, absolute
);
928 * u_undoredo: common code for undo and redo
930 * The lines in the file are replaced by the lines in the entry list at
931 * curbuf->b_u_curhead. The replaced lines in the file are saved in the entry
932 * list for the next undo/redo.
934 * When "undo" is TRUE we go up in the tree, when FALSE we go down.
940 char_u
**newarray
= NULL
;
945 linenr_T newlnum
= MAXLNUM
;
947 u_entry_T
*uep
, *nuep
;
948 u_entry_T
*newlist
= NULL
;
951 pos_T namedm
[NMARKS
];
953 visualinfo_T visualinfo
;
955 int empty_buffer
; /* buffer became empty */
956 u_header_T
*curhead
= curbuf
->b_u_curhead
;
958 old_flags
= curhead
->uh_flags
;
959 new_flags
= (curbuf
->b_changed
? UH_CHANGED
: 0) +
960 ((curbuf
->b_ml
.ml_flags
& ML_EMPTY
) ? UH_EMPTYBUF
: 0);
964 * save marks before undo/redo
966 mch_memmove(namedm
, curbuf
->b_namedm
, sizeof(pos_T
) * NMARKS
);
968 visualinfo
= curbuf
->b_visual
;
970 curbuf
->b_op_start
.lnum
= curbuf
->b_ml
.ml_line_count
;
971 curbuf
->b_op_start
.col
= 0;
972 curbuf
->b_op_end
.lnum
= 0;
973 curbuf
->b_op_end
.col
= 0;
975 for (uep
= curhead
->uh_entry
; uep
!= NULL
; uep
= nuep
)
980 bot
= curbuf
->b_ml
.ml_line_count
+ 1;
981 if (top
> curbuf
->b_ml
.ml_line_count
|| top
>= bot
982 || bot
> curbuf
->b_ml
.ml_line_count
+ 1)
984 EMSG(_("E438: u_undo: line numbers wrong"));
985 changed(); /* don't want UNCHANGED now */
989 oldsize
= bot
- top
- 1; /* number of lines before undo */
990 newsize
= uep
->ue_size
; /* number of lines after undo */
994 /* If the saved cursor is somewhere in this undo block, move it to
995 * the remembered position. Makes "gwap" put the cursor back
997 lnum
= curhead
->uh_cursor
.lnum
;
998 if (lnum
>= top
&& lnum
<= top
+ newsize
+ 1)
1000 curwin
->w_cursor
= curhead
->uh_cursor
;
1001 newlnum
= curwin
->w_cursor
.lnum
- 1;
1005 /* Use the first line that actually changed. Avoids that
1006 * undoing auto-formatting puts the cursor in the previous
1008 for (i
= 0; i
< newsize
&& i
< oldsize
; ++i
)
1009 if (STRCMP(uep
->ue_array
[i
], ml_get(top
+ 1 + i
)) != 0)
1011 if (i
== newsize
&& newlnum
== MAXLNUM
&& uep
->ue_next
== NULL
)
1014 curwin
->w_cursor
.lnum
= newlnum
+ 1;
1016 else if (i
< newsize
)
1019 curwin
->w_cursor
.lnum
= newlnum
+ 1;
1024 empty_buffer
= FALSE
;
1026 /* delete the lines between top and bot and save them in newarray */
1029 if ((newarray
= (char_u
**)U_ALLOC_LINE(
1030 (unsigned)(sizeof(char_u
*) * oldsize
))) == NULL
)
1032 do_outofmem_msg((long_u
)(sizeof(char_u
*) * oldsize
));
1034 * We have messed up the entry list, repair is impossible.
1035 * we have to free the rest of the list.
1039 nuep
= uep
->ue_next
;
1040 u_freeentry(uep
, uep
->ue_size
);
1045 /* delete backwards, it goes faster in most cases */
1046 for (lnum
= bot
- 1, i
= oldsize
; --i
>= 0; --lnum
)
1048 /* what can we do when we run out of memory? */
1049 if ((newarray
[i
] = u_save_line(lnum
)) == NULL
)
1050 do_outofmem_msg((long_u
)0);
1051 /* remember we deleted the last line in the buffer, and a
1052 * dummy empty line will be inserted */
1053 if (curbuf
->b_ml
.ml_line_count
== 1)
1054 empty_buffer
= TRUE
;
1055 ml_delete(lnum
, FALSE
);
1061 /* insert the lines in u_array between top and bot */
1064 for (lnum
= top
, i
= 0; i
< newsize
; ++i
, ++lnum
)
1067 * If the file is empty, there is an empty line 1 that we
1068 * should get rid of, by replacing it with the new line
1070 if (empty_buffer
&& lnum
== 0)
1071 ml_replace((linenr_T
)1, uep
->ue_array
[i
], TRUE
);
1073 ml_append(lnum
, uep
->ue_array
[i
], (colnr_T
)0, FALSE
);
1074 U_FREE_LINE(uep
->ue_array
[i
]);
1076 U_FREE_LINE((char_u
*)uep
->ue_array
);
1080 if (oldsize
!= newsize
)
1082 mark_adjust(top
+ 1, top
+ oldsize
, (long)MAXLNUM
,
1083 (long)newsize
- (long)oldsize
);
1084 if (curbuf
->b_op_start
.lnum
> top
+ oldsize
)
1085 curbuf
->b_op_start
.lnum
+= newsize
- oldsize
;
1086 if (curbuf
->b_op_end
.lnum
> top
+ oldsize
)
1087 curbuf
->b_op_end
.lnum
+= newsize
- oldsize
;
1090 changed_lines(top
+ 1, 0, bot
, newsize
- oldsize
);
1092 /* set '[ and '] mark */
1093 if (top
+ 1 < curbuf
->b_op_start
.lnum
)
1094 curbuf
->b_op_start
.lnum
= top
+ 1;
1095 if (newsize
== 0 && top
+ 1 > curbuf
->b_op_end
.lnum
)
1096 curbuf
->b_op_end
.lnum
= top
+ 1;
1097 else if (top
+ newsize
> curbuf
->b_op_end
.lnum
)
1098 curbuf
->b_op_end
.lnum
= top
+ newsize
;
1100 u_newcount
+= newsize
;
1101 u_oldcount
+= oldsize
;
1102 uep
->ue_size
= oldsize
;
1103 uep
->ue_array
= newarray
;
1104 uep
->ue_bot
= top
+ newsize
+ 1;
1107 * insert this entry in front of the new entry list
1109 nuep
= uep
->ue_next
;
1110 uep
->ue_next
= newlist
;
1114 curhead
->uh_entry
= newlist
;
1115 curhead
->uh_flags
= new_flags
;
1116 if ((old_flags
& UH_EMPTYBUF
) && bufempty())
1117 curbuf
->b_ml
.ml_flags
|= ML_EMPTY
;
1118 if (old_flags
& UH_CHANGED
)
1121 #ifdef FEAT_NETBEANS_INTG
1122 /* per netbeans undo rules, keep it as modified */
1123 if (!isNetbeansModified(curbuf
))
1125 unchanged(curbuf
, FALSE
);
1128 * restore marks from before undo/redo
1130 for (i
= 0; i
< NMARKS
; ++i
)
1131 if (curhead
->uh_namedm
[i
].lnum
!= 0)
1133 curbuf
->b_namedm
[i
] = curhead
->uh_namedm
[i
];
1134 curhead
->uh_namedm
[i
] = namedm
[i
];
1137 if (curhead
->uh_visual
.vi_start
.lnum
!= 0)
1139 curbuf
->b_visual
= curhead
->uh_visual
;
1140 curhead
->uh_visual
= visualinfo
;
1145 * If the cursor is only off by one line, put it at the same position as
1146 * before starting the change (for the "o" command).
1147 * Otherwise the cursor should go to the first undone line.
1149 if (curhead
->uh_cursor
.lnum
+ 1 == curwin
->w_cursor
.lnum
1150 && curwin
->w_cursor
.lnum
> 1)
1151 --curwin
->w_cursor
.lnum
;
1152 if (curhead
->uh_cursor
.lnum
== curwin
->w_cursor
.lnum
)
1154 curwin
->w_cursor
.col
= curhead
->uh_cursor
.col
;
1155 #ifdef FEAT_VIRTUALEDIT
1156 if (virtual_active() && curhead
->uh_cursor_vcol
>= 0)
1157 coladvance((colnr_T
)curhead
->uh_cursor_vcol
);
1159 curwin
->w_cursor
.coladd
= 0;
1162 else if (curwin
->w_cursor
.lnum
<= curbuf
->b_ml
.ml_line_count
)
1163 beginline(BL_SOL
| BL_FIX
);
1166 /* We get here with the current cursor line being past the end (eg
1167 * after adding lines at the end of the file, and then undoing it).
1168 * check_cursor() will move the cursor to the last line. Move it to
1169 * the first column here. */
1170 curwin
->w_cursor
.col
= 0;
1171 #ifdef FEAT_VIRTUALEDIT
1172 curwin
->w_cursor
.coladd
= 0;
1176 /* Make sure the cursor is on an existing line and column. */
1179 /* Remember where we are for "g-" and ":earlier 10s". */
1180 curbuf
->b_u_seq_cur
= curhead
->uh_seq
;
1182 /* We are below the previous undo. However, to make ":earlier 1s"
1183 * work we compute this as being just above the just undone change. */
1184 --curbuf
->b_u_seq_cur
;
1186 /* The timestamp can be the same for multiple changes, just use the one of
1187 * the undone/redone change. */
1188 curbuf
->b_u_seq_time
= curhead
->uh_time
;
1192 * If we deleted or added lines, report the number of less/more lines.
1193 * Otherwise, report the number of changes (this may be incorrect
1194 * in some cases, but it's better than nothing).
1197 u_undo_end(did_undo
, absolute
)
1198 int did_undo
; /* just did an undo */
1199 int absolute
; /* used ":undo N" */
1206 if ((fdo_flags
& FDO_UNDO
) && KeyTyped
)
1210 if (global_busy
/* no messages now, wait until global is finished */
1211 || !messaging()) /* 'lazyredraw' set, don't do messages now */
1214 if (curbuf
->b_ml
.ml_flags
& ML_EMPTY
)
1217 u_oldcount
-= u_newcount
;
1218 if (u_oldcount
== -1)
1219 msgstr
= N_("more line");
1220 else if (u_oldcount
< 0)
1221 msgstr
= N_("more lines");
1222 else if (u_oldcount
== 1)
1223 msgstr
= N_("line less");
1224 else if (u_oldcount
> 1)
1225 msgstr
= N_("fewer lines");
1228 u_oldcount
= u_newcount
;
1229 if (u_newcount
== 1)
1230 msgstr
= N_("change");
1232 msgstr
= N_("changes");
1235 if (curbuf
->b_u_curhead
!= NULL
)
1237 /* For ":undo N" we prefer a "after #N" message. */
1238 if (absolute
&& curbuf
->b_u_curhead
->uh_next
!= NULL
)
1240 uhp
= curbuf
->b_u_curhead
->uh_next
;
1244 uhp
= curbuf
->b_u_curhead
;
1246 uhp
= curbuf
->b_u_curhead
->uh_next
;
1249 uhp
= curbuf
->b_u_newhead
;
1254 u_add_time(msgbuf
, sizeof(msgbuf
), uhp
->uh_time
);
1256 smsg((char_u
*)_("%ld %s; %s #%ld %s"),
1257 u_oldcount
< 0 ? -u_oldcount
: u_oldcount
,
1259 did_undo
? _("before") : _("after"),
1260 uhp
== NULL
? 0L : uhp
->uh_seq
,
1265 * u_sync: stop adding to the current entry list
1269 int force
; /* Also sync when no_u_sync is set. */
1271 /* Skip it when already synced or syncing is disabled. */
1272 if (curbuf
->b_u_synced
|| (!force
&& no_u_sync
> 0))
1274 #if defined(FEAT_XIM) && defined(FEAT_GUI_GTK)
1275 if (im_is_preediting())
1276 return; /* XIM is busy, don't break an undo sequence */
1279 curbuf
->b_u_synced
= TRUE
; /* no entries, nothing to do */
1282 u_getbot(); /* compute ue_bot of previous u_save */
1283 curbuf
->b_u_curhead
= NULL
;
1288 * ":undolist": List the leafs of the undo tree
1303 * 1: walk the tree to find all leafs, put the info in "ga".
1305 * 3: display the list
1308 nomark
= ++lastmark
;
1309 ga_init2(&ga
, (int)sizeof(char *), 20);
1311 uhp
= curbuf
->b_u_oldhead
;
1314 if (uhp
->uh_prev
== NULL
&& uhp
->uh_walk
!= nomark
1315 && uhp
->uh_walk
!= mark
)
1317 if (ga_grow(&ga
, 1) == FAIL
)
1319 vim_snprintf((char *)IObuff
, IOSIZE
, "%6ld %7ld ",
1320 uhp
->uh_seq
, changes
);
1321 u_add_time(IObuff
+ STRLEN(IObuff
), IOSIZE
- STRLEN(IObuff
),
1323 ((char_u
**)(ga
.ga_data
))[ga
.ga_len
++] = vim_strsave(IObuff
);
1326 uhp
->uh_walk
= mark
;
1328 /* go down in the tree if we haven't been there */
1329 if (uhp
->uh_prev
!= NULL
&& uhp
->uh_prev
->uh_walk
!= nomark
1330 && uhp
->uh_prev
->uh_walk
!= mark
)
1336 /* go to alternate branch if we haven't been there */
1337 else if (uhp
->uh_alt_next
!= NULL
1338 && uhp
->uh_alt_next
->uh_walk
!= nomark
1339 && uhp
->uh_alt_next
->uh_walk
!= mark
)
1340 uhp
= uhp
->uh_alt_next
;
1342 /* go up in the tree if we haven't been there and we are at the
1343 * start of alternate branches */
1344 else if (uhp
->uh_next
!= NULL
&& uhp
->uh_alt_prev
== NULL
1345 && uhp
->uh_next
->uh_walk
!= nomark
1346 && uhp
->uh_next
->uh_walk
!= mark
)
1354 /* need to backtrack; mark this node as done */
1355 uhp
->uh_walk
= nomark
;
1356 if (uhp
->uh_alt_prev
!= NULL
)
1357 uhp
= uhp
->uh_alt_prev
;
1367 MSG(_("Nothing to undo"));
1370 sort_strings((char_u
**)ga
.ga_data
, ga
.ga_len
);
1373 msg_puts_attr((char_u
*)_("number changes time"), hl_attr(HLF_T
));
1374 for (i
= 0; i
< ga
.ga_len
&& !got_int
; ++i
)
1379 msg_puts(((char_u
**)ga
.ga_data
)[i
]);
1383 ga_clear_strings(&ga
);
1388 * Put the timestamp of an undo header in "buf[buflen]" in a nice format.
1391 u_add_time(buf
, buflen
, tt
)
1396 #ifdef HAVE_STRFTIME
1399 if (time(NULL
) - tt
>= 100)
1401 curtime
= localtime(&tt
);
1402 (void)strftime((char *)buf
, buflen
, "%H:%M:%S", curtime
);
1406 vim_snprintf((char *)buf
, buflen
, _("%ld seconds ago"),
1407 (long)(time(NULL
) - tt
));
1411 * ":undojoin": continue adding to the last entry list
1418 if (curbuf
->b_u_newhead
== NULL
)
1419 return; /* nothing changed before */
1420 if (curbuf
->b_u_curhead
!= NULL
)
1422 EMSG(_("E790: undojoin is not allowed after undo"));
1425 if (!curbuf
->b_u_synced
)
1426 return; /* already unsynced */
1428 return; /* no entries, nothing to do */
1431 /* Go back to the last entry */
1432 curbuf
->b_u_curhead
= curbuf
->b_u_newhead
;
1433 curbuf
->b_u_synced
= FALSE
; /* no entries, nothing to do */
1438 * Called after writing the file and setting b_changed to FALSE.
1439 * Now an undo means that the buffer is modified.
1445 u_unch_branch(buf
->b_u_oldhead
);
1446 buf
->b_did_warn
= FALSE
;
1455 for (uh
= uhp
; uh
!= NULL
; uh
= uh
->uh_prev
)
1457 uh
->uh_flags
|= UH_CHANGED
;
1458 if (uh
->uh_alt_next
!= NULL
)
1459 u_unch_branch(uh
->uh_alt_next
); /* recursive */
1464 * Get pointer to last added entry.
1465 * If it's not valid, give an error message and return NULL.
1470 if (curbuf
->b_u_newhead
== NULL
|| curbuf
->b_u_newhead
->uh_entry
== NULL
)
1472 EMSG(_("E439: undo list corrupt"));
1475 return curbuf
->b_u_newhead
->uh_entry
;
1479 * u_getbot(): compute the line number of the previous u_save
1480 * It is called only when b_u_synced is FALSE.
1488 uep
= u_get_headentry(); /* check for corrupt undo list */
1492 uep
= curbuf
->b_u_newhead
->uh_getbot_entry
;
1496 * the new ue_bot is computed from the number of lines that has been
1497 * inserted (0 - deleted) since calling u_save. This is equal to the
1498 * old line count subtracted from the current line count.
1500 extra
= curbuf
->b_ml
.ml_line_count
- uep
->ue_lcount
;
1501 uep
->ue_bot
= uep
->ue_top
+ uep
->ue_size
+ 1 + extra
;
1502 if (uep
->ue_bot
< 1 || uep
->ue_bot
> curbuf
->b_ml
.ml_line_count
)
1504 EMSG(_("E440: undo line missing"));
1505 uep
->ue_bot
= uep
->ue_top
+ 1; /* assume all lines deleted, will
1506 * get all the old lines back
1507 * without deleting the current
1511 curbuf
->b_u_newhead
->uh_getbot_entry
= NULL
;
1514 curbuf
->b_u_synced
= TRUE
;
1518 * Free one header and its entry list and adjust the pointers.
1521 u_freeheader(buf
, uhp
, uhpp
)
1524 u_header_T
**uhpp
; /* if not NULL reset when freeing this header */
1526 /* When there is an alternate redo list free that branch completely,
1527 * because we can never go there. */
1528 if (uhp
->uh_alt_next
!= NULL
)
1529 u_freebranch(buf
, uhp
->uh_alt_next
, uhpp
);
1531 if (uhp
->uh_alt_prev
!= NULL
)
1532 uhp
->uh_alt_prev
->uh_alt_next
= NULL
;
1534 /* Update the links in the list to remove the header. */
1535 if (uhp
->uh_next
== NULL
)
1536 buf
->b_u_oldhead
= uhp
->uh_prev
;
1538 uhp
->uh_next
->uh_prev
= uhp
->uh_prev
;
1540 if (uhp
->uh_prev
== NULL
)
1541 buf
->b_u_newhead
= uhp
->uh_next
;
1543 uhp
->uh_prev
->uh_next
= uhp
->uh_next
;
1545 u_freeentries(buf
, uhp
, uhpp
);
1549 * Free an alternate branch and any following alternate branches.
1552 u_freebranch(buf
, uhp
, uhpp
)
1555 u_header_T
**uhpp
; /* if not NULL reset when freeing this header */
1557 u_header_T
*tofree
, *next
;
1559 if (uhp
->uh_alt_prev
!= NULL
)
1560 uhp
->uh_alt_prev
->uh_alt_next
= NULL
;
1563 while (next
!= NULL
)
1566 if (tofree
->uh_alt_next
!= NULL
)
1567 u_freebranch(buf
, tofree
->uh_alt_next
, uhpp
); /* recursive */
1568 next
= tofree
->uh_prev
;
1569 u_freeentries(buf
, tofree
, uhpp
);
1574 * Free all the undo entries for one header and the header itself.
1575 * This means that "uhp" is invalid when returning.
1578 u_freeentries(buf
, uhp
, uhpp
)
1581 u_header_T
**uhpp
; /* if not NULL reset when freeing this header */
1583 u_entry_T
*uep
, *nuep
;
1585 /* Check for pointers to the header that become invalid now. */
1586 if (buf
->b_u_curhead
== uhp
)
1587 buf
->b_u_curhead
= NULL
;
1588 if (uhpp
!= NULL
&& uhp
== *uhpp
)
1591 for (uep
= uhp
->uh_entry
; uep
!= NULL
; uep
= nuep
)
1593 nuep
= uep
->ue_next
;
1594 u_freeentry(uep
, uep
->ue_size
);
1597 U_FREE_LINE((char_u
*)uhp
);
1602 * free entry 'uep' and 'n' lines in uep->ue_array[]
1610 U_FREE_LINE(uep
->ue_array
[--n
]);
1611 U_FREE_LINE((char_u
*)uep
->ue_array
);
1612 U_FREE_LINE((char_u
*)uep
);
1616 * invalidate the undo buffer; called when storage has already been released
1622 buf
->b_u_newhead
= buf
->b_u_oldhead
= buf
->b_u_curhead
= NULL
;
1623 buf
->b_u_synced
= TRUE
;
1624 buf
->b_u_numhead
= 0;
1625 buf
->b_u_line_ptr
= NULL
;
1626 buf
->b_u_line_lnum
= 0;
1630 * save the line "lnum" for the "U" command
1636 if (lnum
== curbuf
->b_u_line_lnum
) /* line is already saved */
1638 if (lnum
< 1 || lnum
> curbuf
->b_ml
.ml_line_count
) /* should never happen */
1641 curbuf
->b_u_line_lnum
= lnum
;
1642 if (curwin
->w_cursor
.lnum
== lnum
)
1643 curbuf
->b_u_line_colnr
= curwin
->w_cursor
.col
;
1645 curbuf
->b_u_line_colnr
= 0;
1646 if ((curbuf
->b_u_line_ptr
= u_save_line(lnum
)) == NULL
)
1647 do_outofmem_msg((long_u
)0);
1651 * clear the line saved for the "U" command
1652 * (this is used externally for crossing a line while in insert mode)
1657 if (curbuf
->b_u_line_ptr
!= NULL
)
1659 U_FREE_LINE(curbuf
->b_u_line_ptr
);
1660 curbuf
->b_u_line_ptr
= NULL
;
1661 curbuf
->b_u_line_lnum
= 0;
1666 * Implementation of the "U" command.
1667 * Differentiation from vi: "U" can be undone with the next "U".
1668 * We also allow the cursor to be in another line.
1679 if (curbuf
->b_u_line_ptr
== NULL
||
1680 curbuf
->b_u_line_lnum
> curbuf
->b_ml
.ml_line_count
)
1685 /* first save the line for the 'u' command */
1686 if (u_savecommon(curbuf
->b_u_line_lnum
- 1,
1687 curbuf
->b_u_line_lnum
+ 1, (linenr_T
)0) == FAIL
)
1689 oldp
= u_save_line(curbuf
->b_u_line_lnum
);
1692 do_outofmem_msg((long_u
)0);
1695 ml_replace(curbuf
->b_u_line_lnum
, curbuf
->b_u_line_ptr
, TRUE
);
1696 changed_bytes(curbuf
->b_u_line_lnum
, 0);
1697 U_FREE_LINE(curbuf
->b_u_line_ptr
);
1698 curbuf
->b_u_line_ptr
= oldp
;
1700 t
= curbuf
->b_u_line_colnr
;
1701 if (curwin
->w_cursor
.lnum
== curbuf
->b_u_line_lnum
)
1702 curbuf
->b_u_line_colnr
= curwin
->w_cursor
.col
;
1703 curwin
->w_cursor
.col
= t
;
1704 curwin
->w_cursor
.lnum
= curbuf
->b_u_line_lnum
;
1708 * There are two implementations of the memory management for undo:
1709 * 1. Use the standard malloc()/free() functions.
1710 * This should be fast for allocating memory, but when a buffer is
1711 * abandoned every single allocated chunk must be freed, which may be slow.
1712 * 2. Allocate larger blocks of memory and keep track of chunks ourselves.
1713 * This is fast for abandoning, but the use of linked lists is slow for
1714 * finding a free chunk. Esp. when a lot of lines are changed or deleted.
1715 * A bit of profiling showed that the first method is faster, especially when
1716 * making a large number of changes, under the condition that malloc()/free()
1717 * is implemented efficiently.
1721 * Version of undo memory allocation using malloc()/free()
1723 * U_FREE_LINE() and U_ALLOC_LINE() are macros that invoke vim_free() and
1724 * lalloc() directly.
1728 * Free all allocated memory blocks for the buffer 'buf'.
1734 while (buf
->b_u_oldhead
!= NULL
)
1735 u_freeheader(buf
, buf
->b_u_oldhead
, NULL
);
1736 U_FREE_LINE(buf
->b_u_line_ptr
);
1741 * Storage allocation for the undo lines and blocks of the current file.
1742 * Version where Vim keeps track of the available memory.
1746 * Memory is allocated in relatively large blocks. These blocks are linked
1747 * in the allocated block list, headed by curbuf->b_block_head. They are all
1748 * freed when abandoning a file, so we don't have to free every single line.
1749 * The list is kept sorted on memory address.
1750 * block_alloc() allocates a block.
1751 * m_blockfree() frees all blocks.
1753 * The available chunks of memory are kept in free chunk lists. There is
1754 * one free list for each block of allocated memory. The list is kept sorted
1755 * on memory address.
1756 * u_alloc_line() gets a chunk from the free lists.
1757 * u_free_line() returns a chunk to the free lists.
1758 * curbuf->b_m_search points to the chunk before the chunk that was
1759 * freed/allocated the last time.
1760 * curbuf->b_mb_current points to the b_head where curbuf->b_m_search
1761 * points into the free list.
1764 * b_block_head /---> block #1 /---> block #2
1765 * mb_next ---/ mb_next ---/ mb_next ---> NULL
1766 * mb_info mb_info mb_info
1769 * NULL free chunk #1.1 free chunk #2.1
1772 * free chunk #1.2 NULL
1777 * When a single free chunk list would have been used, it could take a lot
1778 * of time in u_free_line() to find the correct place to insert a chunk in the
1779 * free list. The single free list would become very long when many lines are
1780 * changed (e.g. with :%s/^M$//).
1784 * this blocksize is used when allocating new lines
1786 #define MEMBLOCKSIZE 2044
1789 * The size field contains the size of the chunk, including the size field
1792 * When the chunk is not in-use it is preceded with the m_info structure.
1793 * The m_next field links it in one of the free chunk lists.
1795 * On most unix systems structures have to be longword (32 or 64 bit) aligned.
1796 * On most other systems they are short (16 bit) aligned.
1799 /* the structure definitions are now in structs.h */
1802 /* size of m_size */
1803 # define M_OFFSET (sizeof(long_u))
1805 /* size of m_size */
1806 # define M_OFFSET (sizeof(short_u))
1809 static char_u
*u_blockalloc
__ARGS((long_u
));
1812 * Allocate a block of memory and link it in the allocated block list.
1819 mblock_T
*mp
, *next
;
1821 p
= (mblock_T
*)lalloc(size
+ sizeof(mblock_T
), FALSE
);
1824 /* Insert the block into the allocated block list, keeping it
1825 sorted on address. */
1826 for (mp
= &curbuf
->b_block_head
;
1827 (next
= mp
->mb_next
) != NULL
&& next
< p
;
1830 p
->mb_next
= next
; /* link in block list */
1832 p
->mb_maxsize
= 0; /* nothing free yet */
1834 p
->mb_info
.m_next
= NULL
; /* clear free list */
1835 p
->mb_info
.m_size
= 0;
1836 curbuf
->b_mb_current
= p
; /* remember current block */
1837 curbuf
->b_m_search
= NULL
;
1838 p
++; /* return usable memory */
1844 * free all allocated memory blocks for the buffer 'buf'
1852 for (p
= buf
->b_block_head
.mb_next
; p
!= NULL
; p
= np
)
1857 buf
->b_block_head
.mb_next
= NULL
;
1858 buf
->b_m_search
= NULL
;
1859 buf
->b_mb_current
= NULL
;
1863 * Free a chunk of memory for the current buffer.
1864 * Insert the chunk into the correct free list, keeping it sorted on address.
1867 u_free_line(ptr
, keep
)
1869 int keep
; /* don't free the block when it's empty */
1872 minfo_T
*prev
, *curr
;
1878 if (ptr
== NULL
|| ptr
== IObuff
)
1879 return; /* illegal address can happen in out-of-memory situations */
1881 mp
= (minfo_T
*)(ptr
- M_OFFSET
);
1883 /* find block where chunk could be a part off */
1884 /* if we change curbuf->b_mb_current, curbuf->b_m_search is set to NULL */
1885 if (curbuf
->b_mb_current
== NULL
|| mp
< (minfo_T
*)curbuf
->b_mb_current
)
1887 curbuf
->b_mb_current
= curbuf
->b_block_head
.mb_next
;
1888 curbuf
->b_m_search
= NULL
;
1890 if ((nextb
= curbuf
->b_mb_current
->mb_next
) != NULL
1891 && (minfo_T
*)nextb
< mp
)
1893 curbuf
->b_mb_current
= nextb
;
1894 curbuf
->b_m_search
= NULL
;
1896 while ((nextb
= curbuf
->b_mb_current
->mb_next
) != NULL
1897 && (minfo_T
*)nextb
< mp
)
1898 curbuf
->b_mb_current
= nextb
;
1902 * If mp is smaller than curbuf->b_m_search->m_next go to the start of
1905 if (curbuf
->b_m_search
== NULL
|| mp
< (curbuf
->b_m_search
->m_next
))
1906 next
= &(curbuf
->b_mb_current
->mb_info
);
1908 next
= curbuf
->b_m_search
;
1910 * The following loop is executed very often.
1911 * Therefore it has been optimized at the cost of readability.
1914 #ifdef SLOW_BUT_EASY_TO_READ
1919 next
= next
->m_next
;
1921 while (mp
> next
&& next
!= NULL
);
1923 do /* first, middle, last */
1925 prev
= next
->m_next
; /* curr, next, prev */
1926 if (prev
== NULL
|| mp
<= prev
)
1930 next
= next
->m_next
;
1933 curr
= prev
->m_next
; /* next, prev, curr */
1934 if (curr
== NULL
|| mp
<= curr
)
1937 curr
= prev
->m_next
;
1938 next
= curr
->m_next
;
1941 next
= curr
->m_next
; /* prev, curr, next */
1943 while (mp
> next
&& next
!= NULL
);
1946 /* if *mp and *next are concatenated, join them into one chunk */
1947 if ((char_u
*)mp
+ mp
->m_size
== (char_u
*)next
)
1949 mp
->m_size
+= next
->m_size
;
1950 mp
->m_next
= next
->m_next
;
1954 maxsize
= mp
->m_size
;
1956 /* if *curr and *mp are concatenated, join them */
1957 if (prev
!= NULL
&& (char_u
*)curr
+ curr
->m_size
== (char_u
*)mp
)
1959 curr
->m_size
+= mp
->m_size
;
1960 maxsize
= curr
->m_size
;
1961 curr
->m_next
= mp
->m_next
;
1962 curbuf
->b_m_search
= prev
;
1967 curbuf
->b_m_search
= curr
; /* put curbuf->b_m_search before freed
1972 * If the block only contains free memory now, release it.
1974 if (!keep
&& curbuf
->b_mb_current
->mb_size
1975 == curbuf
->b_mb_current
->mb_info
.m_next
->m_size
)
1977 /* Find the block before the current one to be able to unlink it from
1978 * the list of blocks. */
1979 prevb
= &curbuf
->b_block_head
;
1980 for (nextb
= prevb
->mb_next
; nextb
!= curbuf
->b_mb_current
;
1981 nextb
= nextb
->mb_next
)
1983 prevb
->mb_next
= nextb
->mb_next
;
1985 curbuf
->b_mb_current
= NULL
;
1986 curbuf
->b_m_search
= NULL
;
1988 else if (curbuf
->b_mb_current
->mb_maxsize
< maxsize
)
1989 curbuf
->b_mb_current
->mb_maxsize
= maxsize
;
1993 * Allocate and initialize a new line structure with room for at least
1994 * 'size' characters plus a terminating NUL.
2000 minfo_T
*mp
, *mprev
, *mp2
;
2005 * Add room for size field and trailing NUL byte.
2006 * Adjust for minimal size (must be able to store minfo_T
2007 * plus a trailing NUL, so the chunk can be released again)
2009 size
+= M_OFFSET
+ 1;
2010 if (size
< sizeof(minfo_T
) + 1)
2011 size
= sizeof(minfo_T
) + 1;
2014 * round size up for alignment
2016 size_align
= (size
+ ALIGN_MASK
) & ~ALIGN_MASK
;
2019 * If curbuf->b_m_search is NULL (uninitialized free list) start at
2020 * curbuf->b_block_head
2022 if (curbuf
->b_mb_current
== NULL
|| curbuf
->b_m_search
== NULL
)
2024 curbuf
->b_mb_current
= &curbuf
->b_block_head
;
2025 curbuf
->b_m_search
= &(curbuf
->b_block_head
.mb_info
);
2028 /* Search for a block with enough space. */
2029 mbp
= curbuf
->b_mb_current
;
2030 while (mbp
->mb_maxsize
< size_align
)
2032 if (mbp
->mb_next
!= NULL
)
2035 mbp
= &curbuf
->b_block_head
;
2036 if (mbp
== curbuf
->b_mb_current
)
2038 int n
= (size_align
> (MEMBLOCKSIZE
/ 4)
2039 ? size_align
: MEMBLOCKSIZE
);
2041 /* Back where we started in block list: need to add a new block
2042 * with enough space. */
2043 mp
= (minfo_T
*)u_blockalloc((long_u
)n
);
2047 u_free_line((char_u
*)mp
+ M_OFFSET
, TRUE
);
2048 mbp
= curbuf
->b_mb_current
;
2052 if (mbp
!= curbuf
->b_mb_current
)
2053 curbuf
->b_m_search
= &(mbp
->mb_info
);
2055 /* In this block find a chunk with enough space. */
2056 mprev
= curbuf
->b_m_search
;
2057 mp
= curbuf
->b_m_search
->m_next
;
2060 if (mp
== NULL
) /* at end of the list */
2061 mp
= &(mbp
->mb_info
); /* wrap around to begin */
2062 if (mp
->m_size
>= size
)
2064 if (mp
== curbuf
->b_m_search
)
2066 /* back where we started in free chunk list: "cannot happen" */
2067 EMSG2(_(e_intern2
), "u_alloc_line()");
2074 /* when using the largest chunk adjust mb_maxsize */
2075 if (mp
->m_size
>= mbp
->mb_maxsize
)
2076 mbp
->mb_maxsize
= 0;
2078 /* if the chunk we found is large enough, split it up in two */
2079 if ((long)mp
->m_size
- size_align
>= (long)(sizeof(minfo_T
) + 1))
2081 mp2
= (minfo_T
*)((char_u
*)mp
+ size_align
);
2082 mp2
->m_size
= mp
->m_size
- size_align
;
2083 mp2
->m_next
= mp
->m_next
;
2084 mprev
->m_next
= mp2
;
2085 mp
->m_size
= size_align
;
2087 else /* remove *mp from the free list */
2089 mprev
->m_next
= mp
->m_next
;
2091 curbuf
->b_m_search
= mprev
;
2092 curbuf
->b_mb_current
= mbp
;
2094 /* If using the largest chunk need to find the new largest chunk */
2095 if (mbp
->mb_maxsize
== 0)
2096 for (mp2
= &(mbp
->mb_info
); mp2
!= NULL
; mp2
= mp2
->m_next
)
2097 if (mbp
->mb_maxsize
< mp2
->m_size
)
2098 mbp
->mb_maxsize
= mp2
->m_size
;
2100 mp
= (minfo_T
*)((char_u
*)mp
+ M_OFFSET
);
2101 *(char_u
*)mp
= NUL
; /* set the first byte to NUL */
2103 return ((char_u
*)mp
);
2108 * u_save_line(): allocate memory with u_alloc_line() and copy line 'lnum'
2120 len
= (unsigned)STRLEN(src
);
2121 if ((dst
= U_ALLOC_LINE(len
)) != NULL
)
2122 mch_memmove(dst
, src
, (size_t)(len
+ 1));
2127 * Check if the 'modified' flag is set, or 'ff' has changed (only need to
2128 * check the first character, because it can only be "dos", "unix" or "mac").
2129 * "nofile" and "scratch" type buffers are considered to always be unchanged.
2136 #ifdef FEAT_QUICKFIX
2137 !bt_dontwrite(buf
) &&
2139 (buf
->b_changed
|| file_ff_differs(buf
));
2146 #ifdef FEAT_QUICKFIX
2147 !bt_dontwrite(curbuf
) &&
2149 (curbuf
->b_changed
|| file_ff_differs(curbuf
));