summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/Makefile.am1
-rw-r--r--src/misspell.c91
-rw-r--r--src/rule.c25
3 files changed, 114 insertions, 3 deletions
diff --git a/src/Makefile.am b/src/Makefile.am
index 31d076cd..8e1a4d87 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -47,6 +47,7 @@ libnftables_la_SOURCES = \
netlink.c \
netlink_linearize.c \
netlink_delinearize.c \
+ misspell.c \
monitor.c \
segtree.c \
rbtree.c \
diff --git a/src/misspell.c b/src/misspell.c
new file mode 100644
index 00000000..23290819
--- /dev/null
+++ b/src/misspell.c
@@ -0,0 +1,91 @@
+#include <stdlib.h>
+#include <string.h>
+#include <limits.h>
+#include <utils.h>
+#include <misspell.h>
+
+enum string_distance_function {
+ DELETION = 0, /* m1 */
+ INSERTION, /* m2 */
+ TRANSFORMATION, /* m3 */
+};
+#define DISTANCE_MAX (TRANSFORMATION + 1)
+
+static unsigned int min_distance(unsigned int *cost)
+{
+ unsigned int min = UINT_MAX;
+ int k;
+
+ for (k = 0; k < DISTANCE_MAX; k++) {
+ if (cost[k] < min)
+ min = cost[k];
+ }
+
+ return min;
+}
+
+/* A simple implementation of "The string-to-string correction problem (1974)"
+ * by Robert A. Wagner.
+ */
+static unsigned int string_distance(const char *a, const char *b)
+{
+ unsigned int len_a = strlen(a);
+ unsigned int len_b = strlen(b);
+ unsigned int *distance;
+ unsigned int i, j, ret;
+
+ distance = xzalloc((len_a + 1) * (len_b + 1) * sizeof(unsigned int));
+
+#define DISTANCE(__i, __j) distance[(__i) * len_b + (__j)]
+
+ for (i = 0; i <= len_a; i++)
+ DISTANCE(i, 0) = i;
+ for (j = 0; j <= len_b; j++)
+ DISTANCE(0, j) = j;
+
+ for (i = 1; i <= len_a; i++) {
+ for (j = 1; j <= len_b; j++) {
+ unsigned int subcost = (a[i] == b[j]) ? 0 : 1;
+ unsigned int cost[3];
+
+ cost[DELETION] = DISTANCE(i - 1, j) + 1;
+ cost[INSERTION] = DISTANCE(i, j - 1) + 1;
+ cost[TRANSFORMATION] = DISTANCE(i - 1, j - 1) + subcost;
+ DISTANCE(i, j) = min_distance(cost);
+
+ if (i > 1 && j > 1 &&
+ a[i] == b[j - 1] &&
+ a[i - 1] == b[j])
+ DISTANCE(i, j) =
+ min(DISTANCE(i, j),
+ DISTANCE(i - 2, j - 2) + subcost);
+ }
+ }
+
+ ret = DISTANCE(len_a, len_b);
+
+ xfree(distance);
+
+ return ret;
+}
+
+void string_misspell_init(struct string_misspell_state *st)
+{
+ st->obj = NULL;
+ st->min_distance = UINT_MAX;
+}
+
+int string_misspell_update(const char *a, const char *b,
+ void *obj, struct string_misspell_state *st)
+{
+ unsigned int distance;
+
+ distance = string_distance(a, b);
+
+ if (distance < st->min_distance) {
+ st->min_distance = distance;
+ st->obj = obj;
+ return 1;
+ }
+ return 0;
+}
diff --git a/src/rule.c b/src/rule.c
index 1fffa39a..c244d0ba 100644
--- a/src/rule.c
+++ b/src/rule.c
@@ -22,6 +22,7 @@
#include <netdb.h>
#include <netlink.h>
#include <mnl.h>
+#include <misspell.h>
#include <json.h>
#include <libnftnl/common.h>
@@ -354,18 +355,24 @@ struct set *set_lookup_fuzzy(const char *set_name,
const struct nft_cache *cache,
const struct table **t)
{
+ struct string_misspell_state st;
struct table *table;
struct set *set;
+ string_misspell_init(&st);
+
list_for_each_entry(table, &cache->list, list) {
list_for_each_entry(set, &table->sets, list) {
if (!strcmp(set->handle.set.name, set_name)) {
*t = table;
return set;
}
+ if (string_misspell_update(set->handle.set.name,
+ set_name, set, &st))
+ *t = table;
}
}
- return NULL;
+ return st.obj;
}
struct set *set_lookup_global(uint32_t family, const char *table,
@@ -784,18 +791,24 @@ struct chain *chain_lookup_fuzzy(const struct handle *h,
const struct nft_cache *cache,
const struct table **t)
{
+ struct string_misspell_state st;
struct table *table;
struct chain *chain;
+ string_misspell_init(&st);
+
list_for_each_entry(table, &cache->list, list) {
list_for_each_entry(chain, &table->chains, list) {
if (!strcmp(chain->handle.chain.name, h->chain.name)) {
*t = table;
return chain;
}
+ if (string_misspell_update(chain->handle.chain.name,
+ h->chain.name, chain, &st))
+ *t = table;
}
}
- return NULL;
+ return st.obj;
}
const char *family2str(unsigned int family)
@@ -1142,13 +1155,19 @@ struct table *table_lookup(const struct handle *h,
struct table *table_lookup_fuzzy(const struct handle *h,
const struct nft_cache *cache)
{
+ struct string_misspell_state st;
struct table *table;
+ string_misspell_init(&st);
+
list_for_each_entry(table, &cache->list, list) {
if (!strcmp(table->handle.table.name, h->table.name))
return table;
+
+ string_misspell_update(table->handle.table.name,
+ h->table.name, table, &st);
}
- return NULL;
+ return st.obj;
}
const char *table_flags_name[TABLE_FLAGS_MAX] = {