#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;
}
earch'/>
</form>
</td></tr></table>
<div class='path'>path: <a href='/cgit.cgi/linux/net-next.git/commit/?id=1930b60352e7e195f55b27cde15d2a8f43342a8b'>root</a>/<a href='/cgit.cgi/linux/net-next.git/commit/net?id=1930b60352e7e195f55b27cde15d2a8f43342a8b'>net</a>/<a href='/cgit.cgi/linux/net-next.git/commit/net/netrom?id=1930b60352e7e195f55b27cde15d2a8f43342a8b'>netrom</a>/<a href='/cgit.cgi/linux/net-next.git/commit/net/netrom/sysctl_net_netrom.c?id=1930b60352e7e195f55b27cde15d2a8f43342a8b'>sysctl_net_netrom.c</a></div><div class='content'><div class='cgit-panel'><b>diff options</b><form method='get'><input type='hidden' name='id' value='1930b60352e7e195f55b27cde15d2a8f43342a8b'/><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>David S. Miller &lt;davem@davemloft.net&gt;</td><td class='right'>2017-01-30 15:55:48 -0500</td></tr>
<tr><th>committer</th><td>David S. Miller &lt;davem@davemloft.net&gt;</td><td class='right'>2017-01-30 15:56:40 -0500</td></tr>
<tr><th>commit</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/commit/net/netrom/sysctl_net_netrom.c?id=1930b60352e7e195f55b27cde15d2a8f43342a8b'>1930b60352e7e195f55b27cde15d2a8f43342a8b</a> (<a href='/cgit.cgi/linux/net-next.git/patch/net/netrom/sysctl_net_netrom.c?id=1930b60352e7e195f55b27cde15d2a8f43342a8b'>patch</a>)</td></tr>
<tr><th>tree</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/tree/?id=1930b60352e7e195f55b27cde15d2a8f43342a8b'>ec3f66cd8d8110bf7b4f61e0446bdea505915db9</a> /<a href='/cgit.cgi/linux/net-next.git/tree/net/netrom/sysctl_net_netrom.c?id=1930b60352e7e195f55b27cde15d2a8f43342a8b'>net/netrom/sysctl_net_netrom.c</a></td></tr>
<tr><th>parent</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/commit/net/netrom/sysctl_net_netrom.c?id=4be9993493bc7ee3fdf950a83bc050a3e6cf2a45'>4be9993493bc7ee3fdf950a83bc050a3e6cf2a45</a> (<a href='/cgit.cgi/linux/net-next.git/diff/net/netrom/sysctl_net_netrom.c?id=1930b60352e7e195f55b27cde15d2a8f43342a8b&amp;id2=4be9993493bc7ee3fdf950a83bc050a3e6cf2a45'>diff</a>)</td></tr><tr><th>parent</th><td colspan='2' class='oid'><a href='/cgit.cgi/linux/net-next.git/commit/net/netrom/sysctl_net_netrom.c?id=ec960de61503ef349588dccfa3ae02efabcc2762'>ec960de61503ef349588dccfa3ae02efabcc2762</a> (<a href='/cgit.cgi/linux/net-next.git/diff/net/netrom/sysctl_net_netrom.c?id=1930b60352e7e195f55b27cde15d2a8f43342a8b&amp;id2=ec960de61503ef349588dccfa3ae02efabcc2762'>diff</a>)</td></tr></table>
<div class='commit-subject'>Merge branch 'dsa-port-mirroring'</div><div class='commit-msg'>Florian Fainelli says:

====================
net: dsa: Port mirroring support

This patch series adds support for port mirroring in the two
Broadcom switch drivers. The major part of the functional are actually with
the plumbing between tc and the drivers.

Changes in v5:

- Added Jiri's Reviewed-by tag to first patch
- rebase against latest net-next/master after bcm_sf2 CFP series

Changes in v4:

- rebased against latest net-next/master after Vivien's changes

Changes in v3:

- removed multiline comments from added structures
- simplify error handling in dsa_slave_add_cls_matchall

Changes in v2:

- fixed filter removal logic to disable the ingress or egress mirroring
  when there are no longer ports being monitored in ingress or egress

- removed a stray list_head in dsa_port structure that is not used

Tested using the two iproute2 examples:

      tc qdisc  add dev eth1 handle ffff: ingress
      tc filter add dev eth1 parent ffff:           \
               matchall skip_sw                      \
               action mirred egress mirror           \
               dev eth2
      tc qdisc add dev eth1 handle 1: root prio
      tc filter add dev eth1 parent 1:               \
               matchall skip_sw                       \
               action mirred egress mirror            \
               dev eth2
====================

Signed-off-by: David S. Miller &lt;davem@davemloft.net&gt;
</div><div class='diffstat-header'><a href='/cgit.cgi/linux/net-next.git/diff/?id=1930b60352e7e195f55b27cde15d2a8f43342a8b'>Diffstat</a> (limited to 'net/netrom/sysctl_net_netrom.c')</div><table summary='diffstat' class='diffstat'>