Win32: fix detection of empty directories in is_dir_empty
[git/dscho.git] / xdiff / xpatience.c
blob04e1a1ab2a863814df3b9a91d4e854704d47f3f5
1 /*
2 * LibXDiff by Davide Libenzi ( File Differential Library )
3 * Copyright (C) 2003-2009 Davide Libenzi, Johannes E. Schindelin
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
15 * You should have received a copy of the GNU Lesser General Public
16 * License along with this library; if not, write to the Free Software
17 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19 * Davide Libenzi <davidel@xmailserver.org>
22 #include "xinclude.h"
23 #include "xtypes.h"
24 #include "xdiff.h"
27 * The basic idea of patience diff is to find lines that are unique in
28 * both files. These are intuitively the ones that we want to see as
29 * common lines.
31 * The maximal ordered sequence of such line pairs (where ordered means
32 * that the order in the sequence agrees with the order of the lines in
33 * both files) naturally defines an initial set of common lines.
35 * Now, the algorithm tries to extend the set of common lines by growing
36 * the line ranges where the files have identical lines.
38 * Between those common lines, the patience diff algorithm is applied
39 * recursively, until no unique line pairs can be found; these line ranges
40 * are handled by the well-known Myers algorithm.
43 #define NON_UNIQUE ULONG_MAX
46 * This is a hash mapping from line hash to line numbers in the first and
47 * second file.
49 struct hashmap {
50 int nr, alloc;
51 struct entry {
52 unsigned long hash;
54 * 0 = unused entry, 1 = first line, 2 = second, etc.
55 * line2 is NON_UNIQUE if the line is not unique
56 * in either the first or the second file.
58 unsigned long line1, line2;
60 * "next" & "previous" are used for the longest common
61 * sequence;
62 * initially, "next" reflects only the order in file1.
64 struct entry *next, *previous;
65 } *entries, *first, *last;
66 /* were common records found? */
67 unsigned long has_matches;
68 mmfile_t *file1, *file2;
69 xdfenv_t *env;
70 xpparam_t const *xpp;
73 /* The argument "pass" is 1 for the first file, 2 for the second. */
74 static void insert_record(int line, struct hashmap *map, int pass)
76 xrecord_t **records = pass == 1 ?
77 map->env->xdf1.recs : map->env->xdf2.recs;
78 xrecord_t *record = records[line - 1], *other;
80 * After xdl_prepare_env() (or more precisely, due to
81 * xdl_classify_record()), the "ha" member of the records (AKA lines)
82 * is _not_ the hash anymore, but a linearized version of it. In
83 * other words, the "ha" member is guaranteed to start with 0 and
84 * the second record's ha can only be 0 or 1, etc.
86 * So we multiply ha by 2 in the hope that the hashing was
87 * "unique enough".
89 int index = (int)((record->ha << 1) % map->alloc);
91 while (map->entries[index].line1) {
92 other = map->env->xdf1.recs[map->entries[index].line1 - 1];
93 if (map->entries[index].hash != record->ha ||
94 !xdl_recmatch(record->ptr, record->size,
95 other->ptr, other->size,
96 map->xpp->flags)) {
97 if (++index >= map->alloc)
98 index = 0;
99 continue;
101 if (pass == 2)
102 map->has_matches = 1;
103 if (pass == 1 || map->entries[index].line2)
104 map->entries[index].line2 = NON_UNIQUE;
105 else
106 map->entries[index].line2 = line;
107 return;
109 if (pass == 2)
110 return;
111 map->entries[index].line1 = line;
112 map->entries[index].hash = record->ha;
113 if (!map->first)
114 map->first = map->entries + index;
115 if (map->last) {
116 map->last->next = map->entries + index;
117 map->entries[index].previous = map->last;
119 map->last = map->entries + index;
120 map->nr++;
124 * This function has to be called for each recursion into the inter-hunk
125 * parts, as previously non-unique lines can become unique when being
126 * restricted to a smaller part of the files.
128 * It is assumed that env has been prepared using xdl_prepare().
130 static int fill_hashmap(mmfile_t *file1, mmfile_t *file2,
131 xpparam_t const *xpp, xdfenv_t *env,
132 struct hashmap *result,
133 int line1, int count1, int line2, int count2)
135 result->file1 = file1;
136 result->file2 = file2;
137 result->xpp = xpp;
138 result->env = env;
140 /* We know exactly how large we want the hash map */
141 result->alloc = count1 * 2;
142 result->entries = (struct entry *)
143 xdl_malloc(result->alloc * sizeof(struct entry));
144 if (!result->entries)
145 return -1;
146 memset(result->entries, 0, result->alloc * sizeof(struct entry));
148 /* First, fill with entries from the first file */
149 while (count1--)
150 insert_record(line1++, result, 1);
152 /* Then search for matches in the second file */
153 while (count2--)
154 insert_record(line2++, result, 2);
156 return 0;
160 * Find the longest sequence with a smaller last element (meaning a smaller
161 * line2, as we construct the sequence with entries ordered by line1).
163 static int binary_search(struct entry **sequence, int longest,
164 struct entry *entry)
166 int left = -1, right = longest;
168 while (left + 1 < right) {
169 int middle = (left + right) / 2;
170 /* by construction, no two entries can be equal */
171 if (sequence[middle]->line2 > entry->line2)
172 right = middle;
173 else
174 left = middle;
176 /* return the index in "sequence", _not_ the sequence length */
177 return left;
181 * The idea is to start with the list of common unique lines sorted by
182 * the order in file1. For each of these pairs, the longest (partial)
183 * sequence whose last element's line2 is smaller is determined.
185 * For efficiency, the sequences are kept in a list containing exactly one
186 * item per sequence length: the sequence with the smallest last
187 * element (in terms of line2).
189 static struct entry *find_longest_common_sequence(struct hashmap *map)
191 struct entry **sequence = xdl_malloc(map->nr * sizeof(struct entry *));
192 int longest = 0, i;
193 struct entry *entry;
195 for (entry = map->first; entry; entry = entry->next) {
196 if (!entry->line2 || entry->line2 == NON_UNIQUE)
197 continue;
198 i = binary_search(sequence, longest, entry);
199 entry->previous = i < 0 ? NULL : sequence[i];
200 sequence[++i] = entry;
201 if (i == longest)
202 longest++;
205 /* No common unique lines were found */
206 if (!longest) {
207 xdl_free(sequence);
208 return NULL;
211 /* Iterate starting at the last element, adjusting the "next" members */
212 entry = sequence[longest - 1];
213 entry->next = NULL;
214 while (entry->previous) {
215 entry->previous->next = entry;
216 entry = entry->previous;
218 xdl_free(sequence);
219 return entry;
222 static int match(struct hashmap *map, int line1, int line2)
224 xrecord_t *record1 = map->env->xdf1.recs[line1 - 1];
225 xrecord_t *record2 = map->env->xdf2.recs[line2 - 1];
226 return xdl_recmatch(record1->ptr, record1->size,
227 record2->ptr, record2->size, map->xpp->flags);
230 static int patience_diff(mmfile_t *file1, mmfile_t *file2,
231 xpparam_t const *xpp, xdfenv_t *env,
232 int line1, int count1, int line2, int count2);
234 static int walk_common_sequence(struct hashmap *map, struct entry *first,
235 int line1, int count1, int line2, int count2)
237 int end1 = line1 + count1, end2 = line2 + count2;
238 int next1, next2;
240 for (;;) {
241 /* Try to grow the line ranges of common lines */
242 if (first) {
243 next1 = first->line1;
244 next2 = first->line2;
245 while (next1 > line1 && next2 > line2 &&
246 match(map, next1 - 1, next2 - 1)) {
247 next1--;
248 next2--;
250 } else {
251 next1 = end1;
252 next2 = end2;
254 while (line1 < next1 && line2 < next2 &&
255 match(map, line1, line2)) {
256 line1++;
257 line2++;
260 /* Recurse */
261 if (next1 > line1 || next2 > line2) {
262 struct hashmap submap;
264 memset(&submap, 0, sizeof(submap));
265 if (patience_diff(map->file1, map->file2,
266 map->xpp, map->env,
267 line1, next1 - line1,
268 line2, next2 - line2))
269 return -1;
272 if (!first)
273 return 0;
275 while (first->next &&
276 first->next->line1 == first->line1 + 1 &&
277 first->next->line2 == first->line2 + 1)
278 first = first->next;
280 line1 = first->line1 + 1;
281 line2 = first->line2 + 1;
283 first = first->next;
287 static int fall_back_to_classic_diff(struct hashmap *map,
288 int line1, int count1, int line2, int count2)
290 xpparam_t xpp;
291 xpp.flags = map->xpp->flags & ~XDF_DIFF_ALGORITHM_MASK;
293 return xdl_fall_back_diff(map->env, &xpp,
294 line1, count1, line2, count2);
298 * Recursively find the longest common sequence of unique lines,
299 * and if none was found, ask xdl_do_diff() to do the job.
301 * This function assumes that env was prepared with xdl_prepare_env().
303 static int patience_diff(mmfile_t *file1, mmfile_t *file2,
304 xpparam_t const *xpp, xdfenv_t *env,
305 int line1, int count1, int line2, int count2)
307 struct hashmap map;
308 struct entry *first;
309 int result = 0;
311 /* trivial case: one side is empty */
312 if (!count1) {
313 while(count2--)
314 env->xdf2.rchg[line2++ - 1] = 1;
315 return 0;
316 } else if (!count2) {
317 while(count1--)
318 env->xdf1.rchg[line1++ - 1] = 1;
319 return 0;
322 memset(&map, 0, sizeof(map));
323 if (fill_hashmap(file1, file2, xpp, env, &map,
324 line1, count1, line2, count2))
325 return -1;
327 /* are there any matching lines at all? */
328 if (!map.has_matches) {
329 while(count1--)
330 env->xdf1.rchg[line1++ - 1] = 1;
331 while(count2--)
332 env->xdf2.rchg[line2++ - 1] = 1;
333 xdl_free(map.entries);
334 return 0;
337 first = find_longest_common_sequence(&map);
338 if (first)
339 result = walk_common_sequence(&map, first,
340 line1, count1, line2, count2);
341 else
342 result = fall_back_to_classic_diff(&map,
343 line1, count1, line2, count2);
345 xdl_free(map.entries);
346 return result;
349 int xdl_do_patience_diff(mmfile_t *file1, mmfile_t *file2,
350 xpparam_t const *xpp, xdfenv_t *env)
352 if (xdl_prepare_env(file1, file2, xpp, env) < 0)
353 return -1;
355 /* environment is cleaned up in xdl_diff() */
356 return patience_diff(file1, file2, xpp, env,
357 1, env->xdf1.nrec, 1, env->xdf2.nrec);