1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
/* Copyright (c) 1988 Bellcore
** All Rights Reserved
** Permission is granted to copy or use this program, EXCEPT that it
** may not be sold for profit, the copyright notice must be reproduced
** on copies, and credit should be given to Bellcore where it is due.
** BELLCORE MAKES NO WARRANTY AND ACCEPTS NO LIABILITY FOR THIS PROGRAM.
*/
#ifndef lint
static char rcsid[]= "$Header$";
#endif
#include <stdio.h>
#include "misc.h"
#include "token.h"
#include "edit.h"
#include "compare.h"
#define MAXT K_MAXTOKENS
#define ORIGIN (max_obj/2)
#define MILLER_CHATTER 100
/*
** totally opaque miller/myers code
** hacked from a version provided by the author
*/
E_edit
G_do_miller(m,n,max_d,comflags)
int m;
int n;
int max_d;
int comflags;
{
int max_obj = m + n;
int
lower,
upper,
d,
k,
row,
col;
E_edit new;
#ifdef STATIC_MEM
static E_edit script[MAXT+1];
static int last_d[MAXT+1];
#else
E_edit *script;
int *last_d;
/*
** make space for the two big arrays
** these could probably be smaller if I
** understood this algorithm at all
** as is, i just shoe horned it into my program.
** be sure to allocate max_obj + 1 objects as was done
** in original miller/myers code
*/
script = Z_ALLOC(max_obj+1,E_edit);
last_d = Z_ALLOC(max_obj+1,int);
#endif
for (row=0;row < m && row < n && X_com(row,row,comflags) == 0; ++row)
;
last_d[ORIGIN] = row;
script[ORIGIN] = E_NULL;
lower = (row == m) ? ORIGIN+1 : ORIGIN - 1;
upper = (row == n) ? ORIGIN-1 : ORIGIN + 1;
if (lower > upper)
{
/*
** the files are identical
*/
return(E_NULL);
}
for (d = 1; d <= max_d; ++d) {
for (k = lower; k<= upper; k+= 2) {
new = E_edit_alloc();
if (k == ORIGIN-d || (k!= ORIGIN+d && last_d[k+1] >= last_d[k-1])) {
row = last_d[k+1]+1;
E_setnext(new,script[k+1]);
E_setop(new,E_DELETE);
} else {
row = last_d[k-1];
E_setnext(new,script[k-1]);
E_setop(new,E_INSERT);
}
E_setl1(new,row);
col = row + k - ORIGIN;
E_setl2(new,col);
script[k] = new;
while (row < m && col < n && X_com(row,col,comflags) == 0) {
++row;
++col;
}
last_d[k] = row;
if (row == m && col == n) {
return(script[k]);
}
if (row == m)
lower = k+2;
if (col == n)
upper = k-2;
}
--lower;
++upper;
#ifndef NOCHATTER
if ((d > 0) && (0 == (d % MILLER_CHATTER)))
{
(void) sprintf(Z_err_buf,
"found %d differences\n",
d);
Z_chatter(Z_err_buf);
}
#endif
}
Z_exceed(max_d);
/*
** dummy lines to shut up lint
*/
Z_fatal("fell off end of do_miller\n");
return(E_NULL);
}
|
