Lines Matching +full:bottom +full:- +full:speed
21 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
25 Algorithmica Vol. 1 No. 2, 1986, pp. 251-266;
27 Unless the --minimal option is specified, this code uses the TOO_EXPENSIVE
34 Information and Control Vol. 64, 1985, pp. 100-118. */
39 #include <file-type.h>
67 doing a breadth-first search through the space of edit-sequence.
75 Set PART->(xmid,ymid) to the midpoint (XMID,YMID). The diagonal number
76 XMID - YMID equals the number of inserted lines minus the number
79 Set PART->lo_minimal to true iff the minimal edit script for the
80 left half of the partition is known; similarly for PART->hi_minimal.
99 lin const dmin = xoff - ylim; /* Minimum valid diagonal. */ in diag()
100 lin const dmax = xlim - yoff; /* Maximum valid diagonal. */ in diag()
101 lin const fmid = xoff - yoff; /* Center diagonal of top-down search. */ in diag()
102 lin const bmid = xlim - ylim; /* Center diagonal of bottom-up search. */ in diag()
103 lin fmin = fmid, fmax = fmid; /* Limits of top-down search. */ in diag()
104 lin bmin = bmid, bmax = bmid; /* Limits of bottom-up search. */ in diag()
106 bool odd = (fmid - bmid) & 1; /* True if southeast corner is on an odd in diag()
117 /* Extend the top-down search by an edit step in each diagonal. */ in diag()
118 fmin > dmin ? fd[--fmin - 1] = -1 : ++fmin; in diag()
119 fmax < dmax ? fd[++fmax + 1] = -1 : --fmax; in diag()
120 for (d = fmax; d >= fmin; d -= 2) in diag()
122 lin x, y, oldx, tlo = fd[d - 1], thi = fd[d + 1]; in diag()
129 y = x - d; in diag()
132 if (x - oldx > SNAKE_LIMIT) in diag()
137 part->xmid = x; in diag()
138 part->ymid = y; in diag()
139 part->lo_minimal = part->hi_minimal = true; in diag()
144 /* Similarly extend the bottom-up search. */ in diag()
145 bmin > dmin ? bd[--bmin - 1] = LIN_MAX : ++bmin; in diag()
146 bmax < dmax ? bd[++bmax + 1] = LIN_MAX : --bmax; in diag()
147 for (d = bmax; d >= bmin; d -= 2) in diag()
149 lin x, y, oldx, tlo = bd[d - 1], thi = bd[d + 1]; in diag()
154 x = thi - 1; in diag()
156 y = x - d; in diag()
157 while (x > xoff && y > yoff && xv[x - 1] == yv[y - 1]) in diag()
158 --x, --y; in diag()
159 if (oldx - x > SNAKE_LIMIT) in diag()
164 part->xmid = x; in diag()
165 part->ymid = y; in diag()
166 part->lo_minimal = part->hi_minimal = true; in diag()
186 for (d = fmax; d >= fmin; d -= 2) in diag()
188 lin dd = d - fmid; in diag()
190 lin y = x - d; in diag()
191 lin v = (x - xoff) * 2 - dd; in diag()
192 if (v > 12 * (c + (dd < 0 ? -dd : dd))) in diag()
202 for (k = 1; xv[x - k] == yv[y - k]; k++) in diag()
206 part->xmid = x; in diag()
207 part->ymid = y; in diag()
215 part->lo_minimal = true; in diag()
216 part->hi_minimal = false; in diag()
221 for (d = bmax; d >= bmin; d -= 2) in diag()
223 lin dd = d - bmid; in diag()
225 lin y = x - d; in diag()
226 lin v = (xlim - x) * 2 + dd; in diag()
227 if (v > 12 * (c + (dd < 0 ? -dd : dd))) in diag()
230 && xoff < x && x <= xlim - SNAKE_LIMIT in diag()
231 && yoff < y && y <= ylim - SNAKE_LIMIT) in diag()
238 if (k == SNAKE_LIMIT - 1) in diag()
241 part->xmid = x; in diag()
242 part->ymid = y; in diag()
250 part->lo_minimal = false; in diag()
251 part->hi_minimal = true; in diag()
263 fxbest = bxbest = 0; /* Pacify `gcc -Wall'. */ in diag()
266 fxybest = -1; in diag()
267 for (d = fmax; d >= fmin; d -= 2) in diag()
270 lin y = x - d; in diag()
282 for (d = bmax; d >= bmin; d -= 2) in diag()
285 lin y = x - d; in diag()
296 if ((xlim + ylim) - bxybest < fxybest - (xoff + yoff)) in diag()
298 part->xmid = fxbest; in diag()
299 part->ymid = fxybest - fxbest; in diag()
300 part->lo_minimal = true; in diag()
301 part->hi_minimal = false; in diag()
305 part->xmid = bxbest; in diag()
306 part->ymid = bxybest - bxbest; in diag()
307 part->lo_minimal = false; in diag()
308 part->hi_minimal = true; in diag()
324 All line numbers are origin-0 and discarded lines are not counted.
335 /* Slide down the bottom initial diagonal. */ in compareseq()
339 while (xlim > xoff && ylim > yoff && xv[xlim - 1] == yv[ylim - 1]) in compareseq()
340 --xlim, --ylim; in compareseq()
417 lin *counts = equiv_count[1 - f]; in discard_confusing_lines()
472 while (j > i && discards[j - 1] == 2) in discard_confusing_lines()
473 discards[--j] = 0, --provisional; in discard_confusing_lines()
477 length = j - i; in discard_confusing_lines()
484 if (discards[--j] == 2) in discard_confusing_lines()
508 j -= consec; in discard_confusing_lines()
531 i += length - 1; in discard_confusing_lines()
536 if (j >= 8 && discards[i - j] == 1) in discard_confusing_lines()
538 if (discards[i - j] == 2) in discard_confusing_lines()
539 consec = 0, discards[i - j] = 0; in discard_confusing_lines()
540 else if (discards[i - j] == 0) in discard_confusing_lines()
591 char *other_changed = filevec[1 - f].changed; in shift_boundaries()
627 runlength = i - start; in shift_boundaries()
633 while (start && equivs[start - 1] == equivs[i - 1]) in shift_boundaries()
635 changed[--start] = 1; in shift_boundaries()
636 changed[--i] = 0; in shift_boundaries()
637 while (changed[start - 1]) in shift_boundaries()
638 start--; in shift_boundaries()
639 while (other_changed[--j]) in shift_boundaries()
646 corresponding = other_changed[j - 1] ? i : i_end; in shift_boundaries()
664 while (runlength != i - start); in shift_boundaries()
666 /* If possible, move the fully-merged run of changes in shift_boundaries()
671 changed[--start] = 1; in shift_boundaries()
672 changed[--i] = 0; in shift_boundaries()
673 while (other_changed[--j]) in shift_boundaries()
694 new->line0 = line0; in add_change()
695 new->line1 = line1; in add_change()
696 new->inserted = inserted; in add_change()
697 new->deleted = deleted; in add_change()
698 new->link = old; in add_change()
729 script = add_change (line0, line1, i0 - line0, i1 - line1, script); in build_reverse_script()
750 /* Note that changedN[-1] does exist, and is 0. */ in build_script()
754 if (changed0[i0 - 1] | changed1[i1 - 1]) in build_script()
759 while (changed0[i0 - 1]) --i0; in build_script()
760 while (changed1[i1 - 1]) --i1; in build_script()
763 script = add_change (i0, i1, line0 - i0, line1 - i1, script); in build_script()
767 i0--, i1--; in build_script()
804 Also, --brief without any --ignore-* options means in diff_2_files()
805 we can speed things up by treating the files as binary. */ in diff_2_files()
807 if (read_files (cmp->file, files_can_be_treated_as_binary)) in diff_2_files()
810 if (cmp->file[0].stat.st_size != cmp->file[1].stat.st_size in diff_2_files()
811 && (cmp->file[0].desc < 0 || S_ISREG (cmp->file[0].stat.st_mode)) in diff_2_files()
812 && (cmp->file[1].desc < 0 || S_ISREG (cmp->file[1].stat.st_mode))) in diff_2_files()
816 else if (cmp->file[0].desc == cmp->file[1].desc) in diff_2_files()
822 /* Allocate same-sized buffers for both files. */ in diff_2_files()
823 size_t lcm_max = PTRDIFF_MAX - 1; in diff_2_files()
826 buffer_lcm (STAT_BLOCKSIZE (cmp->file[0].stat), in diff_2_files()
827 STAT_BLOCKSIZE (cmp->file[1].stat), in diff_2_files()
831 cmp->file[f].buffer = xrealloc (cmp->file[f].buffer, buffer_size); in diff_2_files()
833 for (;; cmp->file[0].buffered = cmp->file[1].buffered = 0) in diff_2_files()
837 if (0 <= cmp->file[f].desc) in diff_2_files()
838 file_block_read (&cmp->file[f], in diff_2_files()
839 buffer_size - cmp->file[f].buffered); in diff_2_files()
842 if (cmp->file[0].buffered != cmp->file[1].buffered in diff_2_files()
843 || memcmp (cmp->file[0].buffer, in diff_2_files()
844 cmp->file[1].buffer, in diff_2_files()
845 cmp->file[0].buffered)) in diff_2_files()
852 if (cmp->file[0].buffered != buffer_size) in diff_2_files()
860 changes = briefly_report (changes, cmp->file); in diff_2_files()
869 size_t s = cmp->file[0].buffered_lines + cmp->file[1].buffered_lines + 4; in diff_2_files()
871 cmp->file[0].changed = flag_space + 1; in diff_2_files()
872 cmp->file[1].changed = flag_space + cmp->file[0].buffered_lines + 3; in diff_2_files()
878 discard_confusing_lines (cmp->file); in diff_2_files()
883 xvec = cmp->file[0].undiscarded; in diff_2_files()
884 yvec = cmp->file[1].undiscarded; in diff_2_files()
885 diags = (cmp->file[0].nondiscarded_lines in diff_2_files()
886 + cmp->file[1].nondiscarded_lines + 3); in diff_2_files()
889 fdiag += cmp->file[1].nondiscarded_lines + 1; in diff_2_files()
890 bdiag += cmp->file[1].nondiscarded_lines + 1; in diff_2_files()
899 files[0] = cmp->file[0]; in diff_2_files()
900 files[1] = cmp->file[1]; in diff_2_files()
902 compareseq (0, cmp->file[0].nondiscarded_lines, in diff_2_files()
903 0, cmp->file[1].nondiscarded_lines, minimal); in diff_2_files()
905 free (fdiag - (cmp->file[1].nondiscarded_lines + 1)); in diff_2_files()
910 shift_boundaries (cmp->file); in diff_2_files()
913 of `struct change's -- an edit script. */ in diff_2_files()
916 script = build_reverse_script (cmp->file); in diff_2_files()
918 script = build_script (cmp->file); in diff_2_files()
938 next = end->link; in diff_2_files()
939 end->link = 0; in diff_2_files()
946 end->link = next; in diff_2_files()
953 changes = briefly_report (changes, cmp->file); in diff_2_files()
960 setup_output (file_label[0] ? file_label[0] : cmp->file[0].name, in diff_2_files()
961 file_label[1] ? file_label[1] : cmp->file[1].name, in diff_2_files()
962 cmp->parent != 0); in diff_2_files()
1006 free (cmp->file[0].undiscarded); in diff_2_files()
1012 free (cmp->file[f].equivs); in diff_2_files()
1013 free (cmp->file[f].linbuf + cmp->file[f].linbuf_base); in diff_2_files()
1018 p = e->link; in diff_2_files()
1024 if (cmp->file[f].missing_newline) in diff_2_files()
1027 file_label[f] ? file_label[f] : cmp->file[f].name, in diff_2_files()
1033 if (cmp->file[0].buffer != cmp->file[1].buffer) in diff_2_files()
1034 free (cmp->file[0].buffer); in diff_2_files()
1035 free (cmp->file[1].buffer); in diff_2_files()