+/* A mapping (correspondence) between entries of FILE1 and of FILE2. */
+struct entries_mapping
+{
+ struct changelog_file *file1;
+ struct changelog_file *file2;
+ /* Mapping from indices in FILE1 to indices in FILE2.
+ A value -1 means that the entry from FILE1 is not found in FILE2.
+ A value -2 means that it has not yet been computed. */
+ ssize_t *index_mapping;
+ /* Mapping from indices in FILE2 to indices in FILE1.
+ A value -1 means that the entry from FILE2 is not found in FILE1.
+ A value -2 means that it has not yet been computed. */
+ ssize_t *index_mapping_reverse;
+};
+
+/* Look up (or lazily compute) the mapping of an entry in FILE1.
+ i is the index in FILE1.
+ Return the index in FILE2, or -1 when the entry is not found in FILE2. */
+static ssize_t
+entries_mapping_get (struct entries_mapping *mapping, ssize_t i)
+{
+ if (mapping->index_mapping[i] < -1)
+ {
+ struct changelog_file *file1 = mapping->file1;
+ struct changelog_file *file2 = mapping->file2;
+ size_t n1 = file1->num_entries;
+ size_t n2 = file2->num_entries;
+ struct entry *entry_i = file1->entries[i];
+ ssize_t j;
+
+ /* Search whether it approximately occurs in file2. */
+ ssize_t best_j = -1;
+ double best_j_similarity = 0.0;
+ for (j = n2 - 1; j >= 0; j--)
+ if (mapping->index_mapping_reverse[j] < 0)
+ {
+ double similarity =
+ entry_fstrcmp (entry_i, file2->entries[j], best_j_similarity);
+ if (similarity > best_j_similarity)
+ {
+ best_j = j;
+ best_j_similarity = similarity;
+ }
+ }
+ if (best_j_similarity >= FSTRCMP_THRESHOLD)
+ {
+ /* Found a similar entry in file2. */
+ struct entry *entry_j = file2->entries[best_j];
+ /* Search whether it approximately occurs in file1 at index i. */
+ ssize_t best_i = -1;
+ double best_i_similarity = 0.0;
+ ssize_t ii;
+ for (ii = n1 - 1; ii >= 0; ii--)
+ if (mapping->index_mapping[ii] < 0)
+ {
+ double similarity =
+ entry_fstrcmp (file1->entries[ii], entry_j,
+ best_i_similarity);
+ if (similarity > best_i_similarity)
+ {
+ best_i = ii;
+ best_i_similarity = similarity;
+ }
+ }
+ if (best_i_similarity >= FSTRCMP_THRESHOLD && best_i == i)
+ {
+ mapping->index_mapping[i] = best_j;
+ mapping->index_mapping_reverse[best_j] = i;
+ }
+ }
+ if (mapping->index_mapping[i] < -1)
+ /* It does not approximately occur in FILE2.
+ Remember it, for next time. */
+ mapping->index_mapping[i] = -1;
+ }
+ return mapping->index_mapping[i];
+}
+
+/* Look up (or lazily compute) the mapping of an entry in FILE2.
+ j is the index in FILE2.
+ Return the index in FILE1, or -1 when the entry is not found in FILE1. */
+static ssize_t
+entries_mapping_reverse_get (struct entries_mapping *mapping, ssize_t j)
+{
+ if (mapping->index_mapping_reverse[j] < -1)
+ {
+ struct changelog_file *file1 = mapping->file1;
+ struct changelog_file *file2 = mapping->file2;
+ size_t n1 = file1->num_entries;
+ size_t n2 = file2->num_entries;
+ struct entry *entry_j = file2->entries[j];
+ ssize_t i;
+
+ /* Search whether it approximately occurs in file1. */
+ ssize_t best_i = -1;
+ double best_i_similarity = 0.0;
+ for (i = n1 - 1; i >= 0; i--)
+ if (mapping->index_mapping[i] < 0)
+ {
+ double similarity =
+ entry_fstrcmp (file1->entries[i], entry_j, best_i_similarity);
+ if (similarity > best_i_similarity)
+ {
+ best_i = i;
+ best_i_similarity = similarity;
+ }
+ }
+ if (best_i_similarity >= FSTRCMP_THRESHOLD)
+ {
+ /* Found a similar entry in file1. */
+ struct entry *entry_i = file1->entries[best_i];
+ /* Search whether it approximately occurs in file2 at index j. */
+ ssize_t best_j = -1;
+ double best_j_similarity = 0.0;
+ ssize_t jj;
+ for (jj = n2 - 1; jj >= 0; jj--)
+ if (mapping->index_mapping_reverse[jj] < 0)
+ {
+ double similarity =
+ entry_fstrcmp (entry_i, file2->entries[jj],
+ best_j_similarity);
+ if (similarity > best_j_similarity)
+ {
+ best_j = jj;
+ best_j_similarity = similarity;
+ }
+ }
+ if (best_j_similarity >= FSTRCMP_THRESHOLD && best_j == j)
+ {
+ mapping->index_mapping_reverse[j] = best_i;
+ mapping->index_mapping[best_i] = j;
+ }
+ }
+ if (mapping->index_mapping_reverse[j] < -1)
+ /* It does not approximately occur in FILE1.
+ Remember it, for next time. */
+ mapping->index_mapping_reverse[j] = -1;
+ }
+ return mapping->index_mapping_reverse[j];
+}
+