[RFC PATCH 4/4] Add test for trie

[Ákos Uzonyi]

---
 tests/.gitignore  |  1 +
 tests/Makefile.am |  3 +++
 tests/trie.c      | 57 +++++++++++++++++++++++++++++++++++++++++++++++
 tests/trie.test   | 12 ++++++++++
 trie.c            |  4 +---
 5 files changed, 74 insertions(+), 3 deletions(-)
 create mode 100644 tests/trie.c
 create mode 100755 tests/trie.test

diff --git a/tests/.gitignore b/tests/.gitignore
index fc512ad2..34268a05 100644
--- a/tests/.gitignore
+++ b/tests/.gitignore
@@ -772,6 +772,7 @@ times
 times-fail
 tkill
 tracer_ppid_pgid_sid
+trie
 truncate
 truncate64
 ugetrlimit
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 8aaa0cae..d1f1a98d 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -29,6 +29,7 @@ AM_CPPFLAGS = $(ARCH_MFLAGS) \
 AM_LDFLAGS = $(ARCH_MFLAGS)
 
 libtests_a_SOURCES = \
+	../trie.c ../trie.h \
 	create_nl_socket.c \
 	create_tmpfile.c \
 	errno2name.c \
@@ -246,6 +247,7 @@ check_PROGRAMS = $(PURE_EXECUTABLES) \
 	threads-execve-qq \
 	threads-execve-qqq \
 	tracer_ppid_pgid_sid \
+	trie \
 	unblock_reset_raise \
 	unix-pair-send-recv \
 	unix-pair-sendto-recvfrom \
@@ -467,6 +469,7 @@ MISC_TESTS = \
 	strace-tt.test \
 	strace-ttt.test \
 	termsig.test \
+	trie.test \
 	threads-execve.test \
 	umovestr_cached.test \
 	# end of MISC_TESTS
diff --git a/tests/trie.c b/tests/trie.c
new file mode 100644
index 00000000..26118c14
--- /dev/null
+++ b/tests/trie.c
@@ -0,0 +1,57 @@
+/*
+ * Copyright (c) 2017-2019 The strace developers.
+ * All rights reserved.
+ *
+ * SPDX-License-Identifier: GPL-2.0-or-later
+ */
+
+#include "tests.h"
+#include "trie.h"
+
+#include <stdio.h>
+
+static void
+assert_equals(const char *msg, uint64_t expected, uint64_t actual) {
+	if (actual != expected)
+		error_msg_and_fail("%s: expected: %ld, actual: %ld", msg, expected, actual);
+}
+
+int
+main(void)
+{
+	static const struct {
+		uint8_t key_size;
+		uint8_t item_size_lg;
+		uint8_t node_key_bits;
+		uint8_t data_block_key_bits;
+		uint64_t empty_value;
+
+		struct {
+			uint64_t key, value, expected_value;
+		} key_value_pairs[3];
+	} params[] = {
+		{64, 6, 10, 10, 0, {{2, 42, 42}, {0, 1, 1}, {2, 43, 43}}},
+	};
+
+	for (size_t i = 0; i < ARRAY_SIZE(params); i++) {
+		struct trie *t = trie_create(params[i].key_size,
+		                             params[i].item_size_lg,
+					     params[i].node_key_bits,
+					     params[i].data_block_key_bits,
+					     params[i].empty_value);
+
+		for (size_t j = 0; j < ARRAY_SIZE(params[i].key_value_pairs); j++) {
+			uint64_t key, value, expected;
+			key = params[i].key_value_pairs[j].key;
+			value = params[i].key_value_pairs[j].value;
+			expected = params[i].key_value_pairs[j].expected_value;
+
+			trie_set(t, key, value);
+			assert_equals("trie_get", expected, trie_get(t, key));
+		}
+
+		trie_free(t);
+	}
+
+	return 0;
+}
diff --git a/tests/trie.test b/tests/trie.test
new file mode 100755
index 00000000..f5a5bf68
--- /dev/null
+++ b/tests/trie.test
@@ -0,0 +1,12 @@
+#!/bin/sh
+#
+# Test trie.
+#
+# Copyright (c) 2020 The strace developers.
+# All rights reserved.
+#
+# SPDX-License-Identifier: LGPL-2.1-or-later
+
+. "${srcdir=.}/init.sh"
+
+run_prog
diff --git a/trie.c b/trie.c
index b2d421cd..e55c5027 100644
--- a/trie.c
+++ b/trie.c
@@ -7,8 +7,6 @@
  * SPDX-License-Identifier: LGPL-2.1-or-later
  */
 
-#include "defs.h"
-
 #include <stdbool.h>
 #include <stdint.h>
 #include <stdlib.h>
@@ -103,7 +101,7 @@ trie_get_node(struct trie *t, uint64_t key, bool auto_create)
 			if (!auto_create)
 				return NULL;
 
-			*cur_node = xcalloc(1 << sz, 1);
+			*cur_node = calloc(1 << sz, 1);
 		}
 
 		if (cur_depth >= t->max_depth)
-- 
2.28.0