1 files changed, 284 insertions, 0 deletions
diff --git a/tests/contrib/test_qp-trie.c b/tests/contrib/test_qp-trie.c
new file mode 100644
index 0000000..a50661f
--- /dev/null
+++ b/tests/contrib/test_qp-trie.c
@@ -0,0 +1,284 @@
+/*  Copyright (C) 2019 CZ.NIC, z.s.p.o. <knot-dns@labs.nic.cz>
+
+    This program is free software: you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation, either version 3 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License
+    along with this program.  If not, see <https://www.gnu.org/licenses/>.
+ */
+
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+#include <tap/basic.h>
+
+#include "contrib/qp-trie/trie.h"
+#include "contrib/macros.h"
+#include "contrib/string.h"
+#include "libknot/dname.h"
+#include "libknot/errcode.h"
+
+/* UCW array sorting defines. */
+#define ASORT_PREFIX(X) str_key_##X
+#define ASORT_KEY_TYPE char*
+#define ASORT_LT(x, y) (strcmp((x), (y)) < 0)
+#include "contrib/ucw/array-sort.h"
+
+/* Constants. */
+#define KEY_MAXLEN 64
+
+/* Generate random key. */
+static const char *alphabet = "abcdefghijklmn0123456789";
+static char *str_key_rand(size_t len)
+{
+	char *s = malloc(len);
+	memset(s, 0, len);
+	for (unsigned i = 0; i < len - 1; ++i) {
+		s[i] = alphabet[rand() % strlen(alphabet)];
+	}
+	return s;
+}
+
+/* Check lesser or equal result. */
+static bool str_key_get_leq(trie_t *trie, char **keys, size_t i, size_t size)
+{
+	static char key_buf[KEY_MAXLEN];
+
+	int ret = 0;
+	trie_val_t *val = NULL;
+	const char *key = keys[i];
+	size_t key_len = strlen(key) + 1;
+	memcpy(key_buf, key, key_len);
+
+	/* Count equal first keys. */
+	size_t first_key_count = 1;
+	for (size_t k = 1; k < size; ++k) {
+		if (strcmp(keys[0], keys[k]) == 0) {
+			first_key_count += 1;
+		} else {
+			break;
+		}
+	}
+
+	/* Before current key. */
+	key_buf[key_len - 2] -= 1;
+	if (i < first_key_count) {
+		ret = trie_get_leq(trie, (uint8_t *)key_buf, key_len, &val);
+		if (ret != KNOT_ENOENT) {
+			diag("%s: leq for key BEFORE %zu/'%s' ret = %d", __func__, i, keys[i], ret);
+			return false; /* No key before first. */
+		}
+	} else {
+		ret = trie_get_leq(trie, (uint8_t *)key_buf, key_len, &val);
+		if (ret < KNOT_EOK || strcmp(*val, key_buf) > 0) {
+			diag("%s: '%s' is not before the key %zu/'%s'", __func__, (char*)*val, i, keys[i]);
+			return false; /* Found key must be LEQ than searched. */
+		}
+	}
+
+	/* Current key. */
+	key_buf[key_len - 2] += 1;
+	ret = trie_get_leq(trie, (uint8_t *)key_buf, key_len, &val);
+	if (! (ret == KNOT_EOK && val && strcmp(*val, key_buf) == 0)) {
+		diag("%s: leq for key %zu/'%s' ret = %d", __func__, i, keys[i], ret);
+		return false; /* Must find equal match. */
+	}
+
+	/* After the current key. */
+	key_buf[key_len - 2] += 1;
+	ret = trie_get_leq(trie, (uint8_t *)key_buf, key_len, &val);
+	if (! (ret >= KNOT_EOK && strcmp(*val, key_buf) <= 0)) {
+		diag("%s: leq for key AFTER %zu/'%s' ret = %d %s", __func__, i, keys[i], ret, (char*)*val);
+		return false; /* Every key must have its LEQ match. */
+	}
+
+	return true;
+
+}
+
+static void test_wildcards(void)
+{
+	/* Test zone. */
+	const char *names[] = {
+		"*",
+		"example.cz",
+		"*.example.cz",
+		"+.example.cz",
+
+		"*.exampld.cz",
+		"www.exampld.cz",
+	};
+	/* Query-answer pairs for wildcard search. */
+	const char *qa_pairs[][2] = {
+		{ ".", NULL },
+		{ "*", "*" },
+		{ "bar", "*" },
+		{ "foo.test.", "*" },
+		{ "example.cz", "example.cz" },
+		{ "*.example.cz", "*.example.cz" },
+		{ "a.example.cz", "*.example.cz" },
+		{ "ab.cd.example.cz", "*.example.cz" },
+		{ "a+.example.cz", "*.example.cz" },
+		{ "+.example.cz", "+.example.cz" },
+		{ "exampld.cz", NULL },
+		{ ":.exampld.cz", "*.exampld.cz" },
+		{ "ww.exampld.cz", "*.exampld.cz" },
+	};
+
+	trie_t *trie = trie_create(NULL);
+	if (!trie) ok(false, "trie: create");
+
+	/* Insert the whole zone. */
+	for (int i = 0; i < sizeof(names) / sizeof(names[0]); ++i) {
+		knot_dname_storage_t dname_st, lf_st;
+		const knot_dname_t
+			*dname = knot_dname_from_str(dname_st, names[i], sizeof(dname_st)),
+			*lf = knot_dname_lf(dname, lf_st);
+		if (!dname || !lf) {
+			ok(false, "trie: converting '%s'", names[i]);
+			return;
+		}
+
+		trie_val_t *val = trie_get_ins(trie, lf + 1 , lf[0]);
+		if (!val || *val != NULL) {
+			ok(false, "trie: inserting '%s' (as dname_lf)", names[i]);
+			return;
+		}
+		*val = (void *)names[i];
+	}
+
+	/* Perform each test query. */
+	for (int i = 0; i < sizeof(qa_pairs) / sizeof(qa_pairs[0]); ++i) {
+		knot_dname_storage_t q_dname_st, q_lf_st;
+		const knot_dname_t *q_dname =
+			knot_dname_from_str(q_dname_st, qa_pairs[i][0], sizeof(q_dname_st));
+		const knot_dname_t *q_lf = knot_dname_lf(q_dname, q_lf_st);
+		if (!q_dname || !q_lf) {
+			ok(false, "trie: converting '%s'", qa_pairs[i][0]);
+			return;
+		}
+
+		const char **ans = (const char **)trie_get_try_wildcard(trie, q_lf + 1, q_lf[0]);
+		bool is_ok = !!ans == !!qa_pairs[i][1] && (!ans || !strcmp(*ans, qa_pairs[i][1]));
+		if (!is_ok) {
+			ok(false, "trie: wildcard test for '%s' -> '%s'",
+				qa_pairs[i][0], ans ? *ans : "<null>");
+			return;
+		}
+	}
+
+	trie_free(trie);
+	ok(true, "trie: wildcard searches");
+}
+
+int main(int argc, char *argv[])
+{
+	plan_lazy();
+
+	/* Random keys. */
+	srand(time(NULL));
+	unsigned key_count = 100000;
+	char **keys = malloc(sizeof(char*) * key_count);
+	/* key must have at least one char and a nul terminator
+	   so that the before/after checks have a char to modify */
+	for (unsigned i = 0; i < key_count; ++i) {
+		keys[i] = str_key_rand(rand() % (KEY_MAXLEN - 2) + 2);
+	}
+
+	/* Sort random keys. */
+	str_key_sort(keys, key_count);
+
+	/* Create trie */
+	trie_val_t *val = NULL;
+	trie_t *trie = trie_create(NULL);
+	ok(trie != NULL, "trie: create");
+
+	/* Insert keys */
+	bool passed = true;
+	size_t inserted = 0;
+	for (unsigned i = 0; i < key_count; ++i) {
+		val = trie_get_ins(trie, (uint8_t *)keys[i], strlen(keys[i]) + 1);
+		if (!val) {
+			passed = false;
+			break;
+		}
+		if (*val == NULL) {
+			*val = keys[i];
+			++inserted;
+		}
+	}
+	ok(passed, "trie: insert");
+
+	/* Check total insertions against trie weight. */
+	is_int(trie_weight(trie), inserted, "trie: trie weight matches insertions");
+
+	/* Lookup all keys */
+	passed = true;
+	for (unsigned i = 0; i < key_count; ++i) {
+		val = trie_get_try(trie, (uint8_t *)keys[i], strlen(keys[i]) + 1);
+		if (val && (*val == keys[i] || strcmp(*val, keys[i]) == 0)) {
+			continue;
+		} else {
+			diag("trie: mismatch on element '%u'", i);
+			passed = false;
+			break;
+		}
+	}
+	ok(passed, "trie: lookup all keys");
+
+	/* Lesser or equal lookup. */
+	passed = true;
+	for (unsigned i = 0; i < key_count; ++i) {
+		if (!str_key_get_leq(trie, keys, i, key_count)) {
+			passed = false;
+			for (int off = -10; off < 10; ++off) {
+				int k = (int)i + off;
+				if (k < 0 || k >= key_count) {
+					continue;
+				}
+				diag("[%u/%d]: %s%s", i, off, off == 0?">":"",keys[k]);
+			}
+			break;
+		}
+	}
+	ok(passed, "trie: find lesser or equal for all keys");
+
+	/* Sorted iteration. */
+	char key_buf[KEY_MAXLEN] = {'\0'};
+	size_t iterated = 0;
+	trie_it_t *it = trie_it_begin(trie);
+	while (!trie_it_finished(it)) {
+		size_t cur_key_len = 0;
+		const char *cur_key = (const char *)trie_it_key(it, &cur_key_len);
+		if (iterated > 0) { /* Only if previous exists. */
+			if (strcmp(key_buf, cur_key) > 0) {
+				diag("'%s' <= '%s' FAIL\n", key_buf, cur_key);
+				break;
+			}
+		}
+		++iterated;
+		memcpy(key_buf, cur_key, cur_key_len);
+		trie_it_next(it);
+	}
+	is_int(inserted, iterated, "trie: sorted iteration");
+	trie_it_free(it);
+
+	/* Cleanup */
+	for (unsigned i = 0; i < key_count; ++i) {
+		free(keys[i]);
+	}
+	free(keys);
+	trie_free(trie);
+
+	/* Test trie_get_try_wildcard(). */
+	test_wildcards();
+
+	return 0;
+}