Revision c62bc49139f1d18e922fc98e35bb08b1aadbcafc authored by Junio C Hamano on 02 August 2019, 20:12:02 UTC, committed by Junio C Hamano on 02 August 2019, 20:12:02 UTC
Support building Git with Visual Studio The bits about .git/branches/* have been dropped from the series. We may want to drop the support for it, but until that happens, the tests should rely on the existence of the support to pass. * js/visual-studio: (23 commits) git: avoid calling aliased builtins via their dashed form bin-wrappers: append `.exe` to target paths if necessary .gitignore: ignore Visual Studio's temporary/generated files .gitignore: touch up the entries regarding Visual Studio vcxproj: also link-or-copy builtins msvc: add a Makefile target to pre-generate the Visual Studio solution contrib/buildsystems: add a backend for modern Visual Studio versions contrib/buildsystems: handle options starting with a slash contrib/buildsystems: also handle -lexpat contrib/buildsystems: handle libiconv, too contrib/buildsystems: handle the curl library option contrib/buildsystems: error out on unknown option contrib/buildsystems: optionally capture the dry-run in a file contrib/buildsystems: redirect errors of the dry run into a log file contrib/buildsystems: ignore gettext stuff contrib/buildsystems: handle quoted spaces in filenames contrib/buildsystems: fix misleading error message contrib/buildsystems: ignore irrelevant files in Generators/ contrib/buildsystems: ignore invalidcontinue.obj Vcproj.pm: urlencode '<' and '>' when generating VC projects ...
levenshtein.c
#include "cache.h"
#include "levenshtein.h"
/*
* This function implements the Damerau-Levenshtein algorithm to
* calculate a distance between strings.
*
* Basically, it says how many letters need to be swapped, substituted,
* deleted from, or added to string1, at least, to get string2.
*
* The idea is to build a distance matrix for the substrings of both
* strings. To avoid a large space complexity, only the last three rows
* are kept in memory (if swaps had the same or higher cost as one deletion
* plus one insertion, only two rows would be needed).
*
* At any stage, "i + 1" denotes the length of the current substring of
* string1 that the distance is calculated for.
*
* row2 holds the current row, row1 the previous row (i.e. for the substring
* of string1 of length "i"), and row0 the row before that.
*
* In other words, at the start of the big loop, row2[j + 1] contains the
* Damerau-Levenshtein distance between the substring of string1 of length
* "i" and the substring of string2 of length "j + 1".
*
* All the big loop does is determine the partial minimum-cost paths.
*
* It does so by calculating the costs of the path ending in characters
* i (in string1) and j (in string2), respectively, given that the last
* operation is a substitution, a swap, a deletion, or an insertion.
*
* This implementation allows the costs to be weighted:
*
* - w (as in "sWap")
* - s (as in "Substitution")
* - a (for insertion, AKA "Add")
* - d (as in "Deletion")
*
* Note that this algorithm calculates a distance _iff_ d == a.
*/
int levenshtein(const char *string1, const char *string2,
int w, int s, int a, int d)
{
int len1 = strlen(string1), len2 = strlen(string2);
int *row0, *row1, *row2;
int i, j;
ALLOC_ARRAY(row0, len2 + 1);
ALLOC_ARRAY(row1, len2 + 1);
ALLOC_ARRAY(row2, len2 + 1);
for (j = 0; j <= len2; j++)
row1[j] = j * a;
for (i = 0; i < len1; i++) {
int *dummy;
row2[0] = (i + 1) * d;
for (j = 0; j < len2; j++) {
/* substitution */
row2[j + 1] = row1[j] + s * (string1[i] != string2[j]);
/* swap */
if (i > 0 && j > 0 && string1[i - 1] == string2[j] &&
string1[i] == string2[j - 1] &&
row2[j + 1] > row0[j - 1] + w)
row2[j + 1] = row0[j - 1] + w;
/* deletion */
if (row2[j + 1] > row1[j + 1] + d)
row2[j + 1] = row1[j + 1] + d;
/* insertion */
if (row2[j + 1] > row2[j] + a)
row2[j + 1] = row2[j] + a;
}
dummy = row0;
row0 = row1;
row1 = row2;
row2 = dummy;
}
i = row1[len2];
free(row0);
free(row1);
free(row2);
return i;
}
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...