#include "levenshtein.h"
#include <errno.h>
#include <stdlib.h>
#include <string.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 substition, 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 = malloc(sizeof(int) * (len2 + 1));
	int *row1 = malloc(sizeof(int) * (len2 + 1));
	int *row2 = malloc(sizeof(int) * (len2 + 1));
	int i, j;

	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;
}
value='search'/>
</form>
</td></tr></table>
<div class='path'>path: <a href='/cgit.cgi/linux/net-next.git/commit/?id=f2557779e1a9cfbf69c99b74da26cc1b2b10e752'>root</a>/<a href='/cgit.cgi/linux/net-next.git/commit/drivers?id=f2557779e1a9cfbf69c99b74da26cc1b2b10e752'>drivers</a>/<a href='/cgit.cgi/linux/net-next.git/commit/drivers/usb?id=f2557779e1a9cfbf69c99b74da26cc1b2b10e752'>usb</a>/<a href='/cgit.cgi/linux/net-next.git/commit/drivers/usb/misc?id=f2557779e1a9cfbf69c99b74da26cc1b2b10e752'>misc</a>/<a href='/cgit.cgi/linux/net-next.git/commit/drivers/usb/misc/ucsi.h?id=f2557779e1a9cfbf69c99b74da26cc1b2b10e752'>ucsi.h</a></div><div class='content'><div class='cgit-panel'><b>diff options</b><form method='get'><input type='hidden' name='id' value='f2557779e1a9cfbf69c99b74da26cc1b2b10e752'/><table><tr><td colspan='2'/></tr><tr><td class='label'>context:</td><td class='ctrl'><select name='context' onchange='this.form.submit();'><option value='1'>1</option><option value='2'>2</option><option value='3' selected='selected'>3</option><option value='4'>4</option><option value='5'>5</option><option value='6'>6</option><option value='7'>7</option><option value='8'>8</option><option value='9'>9</option><option value='10'>10</option><option value='15'>15</option><option value='20'>20</option><option value='25'>25</option><option value='30'>30</option><option value='35'>35</option><option value='40'>40</option></select></td></tr><tr><td class='label'>space:</td><td class='ctrl'><select name='ignorews' onchange='this.form.submit();'><option value='0' selected='selected'>include</option><option value='1'>ignore</option></select></td></tr><tr><td class='label'>mode:</td><td class='ctrl'><select name='dt' onchange='this.form.submit();'><option value='0' selected='selected'>unified</option><option value='1'>ssdiff</option><option value='2'>stat only</option></select></td></tr><tr><td/><td class='ctrl'><noscript><input type='submit' value='reload'/></noscript></td></tr></table></form></div><table summary='commit info' class='commit-info'>
<tr><th>author</th><td>Linus Torvalds &lt;torvalds@linux-foundation.org&gt;</td><td class='right'>2017-02-02 12:34:27 -0800</td></tr>
<tr><th>committer</th><td>Linus Torvalds &lt;torvalds@linux-foundation.org&gt;</td><td class='right'>2017-02-02 12:34:27 -0800</td></tr>
<tr><th>commit</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/commit/drivers/usb/misc/ucsi.h?id=f2557779e1a9cfbf69c99b74da26cc1b2b10e752'>f2557779e1a9cfbf69c99b74da26cc1b2b10e752</a> (<a href='/cgit.cgi/linux/net-next.git/patch/drivers/usb/misc/ucsi.h?id=f2557779e1a9cfbf69c99b74da26cc1b2b10e752'>patch</a>)</td></tr>
<tr><th>tree</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/tree/?id=f2557779e1a9cfbf69c99b74da26cc1b2b10e752'>8ddca65c897199add553948c429072b8bd463692</a> /<a href='/cgit.cgi/linux/net-next.git/tree/drivers/usb/misc/ucsi.h?id=f2557779e1a9cfbf69c99b74da26cc1b2b10e752'>drivers/usb/misc/ucsi.h</a></td></tr>
<tr><th>parent</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/commit/drivers/usb/misc/ucsi.h?id=6d04dfc8966019b8b0977b2cb942351f13d2b178'>6d04dfc8966019b8b0977b2cb942351f13d2b178</a> (<a href='/cgit.cgi/linux/net-next.git/diff/drivers/usb/misc/ucsi.h?id=f2557779e1a9cfbf69c99b74da26cc1b2b10e752&amp;id2=6d04dfc8966019b8b0977b2cb942351f13d2b178'>diff</a>)</td></tr><tr><th>parent</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/commit/drivers/usb/misc/ucsi.h?id=030305d69fc6963c16003f50d7e8d74b02d0a143'>030305d69fc6963c16003f50d7e8d74b02d0a143</a> (<a href='/cgit.cgi/linux/net-next.git/diff/drivers/usb/misc/ucsi.h?id=f2557779e1a9cfbf69c99b74da26cc1b2b10e752&amp;id2=030305d69fc6963c16003f50d7e8d74b02d0a143'>diff</a>)</td></tr></table>
<div class='commit-subject'>Merge tag 'pci-v4.10-fixes-2' of git://git.kernel.org/pub/scm/linux/kernel/git/helgaas/pci</div><div class='commit-msg'>Pull PCI fix from Bjorn Helgaas:
 "Configure ASPM on the link from a PCI-to-PCIe bridge (avoids a NULL
  pointer dereference on topologies including these bridges)"

* tag 'pci-v4.10-fixes-2' of git://git.kernel.org/pub/scm/linux/kernel/git/helgaas/pci:
  PCI/ASPM: Handle PCI-to-PCIe bridges as roots of PCIe hierarchies
</div><div class='diffstat-header'><a href='/cgit.cgi/linux/net-next.git/diff/?id=f2557779e1a9cfbf69c99b74da26cc1b2b10e752'>Diffstat</a> (limited to 'drivers/usb/misc/ucsi.h')</div><table summary='diffstat' class='diffstat'>