v32-0010-radix-tree-fix-radix-tree-test-code.patch

From 591bede6738ca9e5c7264db7ff1d3dd9ba29247f Mon Sep 17 00:00:00 2001
From: Masahiko Sawada <sawada.mshk@gmail.com>
Date: Mon, 17 Apr 2023 17:35:14 +0900
Subject: [PATCH v32 10/18] radix tree: fix radix tree test code

fix tests for key insertion in ascending or descending order.

Also, we missed tests for MIN and MAX size classes.
---
 .../expected/test_radixtree.out               |   6 +-
 .../modules/test_radixtree/test_radixtree.c   | 103 ++++++++++++------
 2 files changed, 71 insertions(+), 38 deletions(-)

diff --git a/src/test/modules/test_radixtree/expected/test_radixtree.out b/src/test/modules/test_radixtree/expected/test_radixtree.out
index ce645cb8b5..7ad1ce3605 100644
--- a/src/test/modules/test_radixtree/expected/test_radixtree.out
+++ b/src/test/modules/test_radixtree/expected/test_radixtree.out
@@ -4,8 +4,10 @@ CREATE EXTENSION test_radixtree;
 -- an error if something fails.
 --
 SELECT test_radixtree();
-NOTICE:  testing basic operations with leaf node 4
-NOTICE:  testing basic operations with inner node 4
+NOTICE:  testing basic operations with leaf node 3
+NOTICE:  testing basic operations with inner node 3
+NOTICE:  testing basic operations with leaf node 15
+NOTICE:  testing basic operations with inner node 15
 NOTICE:  testing basic operations with leaf node 32
 NOTICE:  testing basic operations with inner node 32
 NOTICE:  testing basic operations with leaf node 125
diff --git a/src/test/modules/test_radixtree/test_radixtree.c b/src/test/modules/test_radixtree/test_radixtree.c
index afe53382f3..5a169854d9 100644
--- a/src/test/modules/test_radixtree/test_radixtree.c
+++ b/src/test/modules/test_radixtree/test_radixtree.c
@@ -43,12 +43,15 @@ typedef uint64 TestValueType;
  */
 static const bool rt_test_stats = false;
 
-static int	rt_node_kind_fanouts[] = {
-	0,
-	4,							/* RT_NODE_KIND_4 */
-	32,							/* RT_NODE_KIND_32 */
-	125,						/* RT_NODE_KIND_125 */
-	256							/* RT_NODE_KIND_256 */
+/*
+ * XXX: should we expose and use RT_SIZE_CLASS and RT_SIZE_CLASS_INFO?
+ */
+static int	rt_node_class_fanouts[] = {
+	3,		/* RT_CLASS_3 */
+	15,		/* RT_CLASS_32_MIN */
+	32, 	/* RT_CLASS_32_MAX */
+	125,	/* RT_CLASS_125 */
+	256		/* RT_CLASS_256 */
 };
 /*
  * A struct to define a pattern of integers, for use with the test_pattern()
@@ -260,10 +263,9 @@ test_basic(int children, bool test_inner)
  * Check if keys from start to end with the shift exist in the tree.
  */
 static void
-check_search_on_node(rt_radix_tree *radixtree, uint8 shift, int start, int end,
-					 int incr)
+check_search_on_node(rt_radix_tree *radixtree, uint8 shift, int start, int end)
 {
-	for (int i = start; i < end; i++)
+	for (int i = start; i <= end; i++)
 	{
 		uint64		key = ((uint64) i << shift);
 		TestValueType		val;
@@ -277,22 +279,26 @@ check_search_on_node(rt_radix_tree *radixtree, uint8 shift, int start, int end,
 	}
 }
 
+/*
+ * Insert 256 key-value pairs, and check if keys are properly inserted on each
+ * node class.
+ */
+/* Test keys [0, 256) */
+#define NODE_TYPE_TEST_KEY_MIN 0
+#define NODE_TYPE_TEST_KEY_MAX 256
 static void
-test_node_types_insert(rt_radix_tree *radixtree, uint8 shift, bool insert_asc)
+test_node_types_insert_asc(rt_radix_tree *radixtree, uint8 shift)
 {
-	uint64		num_entries;
-	int		ninserted = 0;
-	int		start = insert_asc ? 0 : 256;
-	int 	incr = insert_asc ? 1 : -1;
-	int		end = insert_asc ? 256 : 0;
-	int		node_kind_idx = 1;
+	uint64 num_entries;
+	int node_class_idx = 0;
+	uint64 key_checked = 0;
 
-	for (int i = start; i != end; i += incr)
+	for (int i = NODE_TYPE_TEST_KEY_MIN; i < NODE_TYPE_TEST_KEY_MAX; i++)
 	{
 		uint64		key = ((uint64) i << shift);
 		bool		found;
 
-		found = rt_set(radixtree, key, (TestValueType*) &key);
+		found = rt_set(radixtree, key, (TestValueType *) &key);
 		if (found)
 			elog(ERROR, "newly inserted key 0x" UINT64_HEX_FORMAT " is found", key);
 
@@ -300,24 +306,49 @@ test_node_types_insert(rt_radix_tree *radixtree, uint8 shift, bool insert_asc)
 		 * After filling all slots in each node type, check if the values
 		 * are stored properly.
 		 */
-		if (ninserted == rt_node_kind_fanouts[node_kind_idx] - 1)
+		if ((i + 1) == rt_node_class_fanouts[node_class_idx])
 		{
-			int check_start = insert_asc
-				? rt_node_kind_fanouts[node_kind_idx - 1]
-				: rt_node_kind_fanouts[node_kind_idx];
-			int check_end = insert_asc
-				? rt_node_kind_fanouts[node_kind_idx]
-				: rt_node_kind_fanouts[node_kind_idx - 1];
-
-			check_search_on_node(radixtree, shift, check_start, check_end, incr);
-			node_kind_idx++;
+			check_search_on_node(radixtree, shift, key_checked, i);
+			key_checked = i;
+			node_class_idx++;
 		}
-
-		ninserted++;
 	}
 
 	num_entries = rt_num_entries(radixtree);
+	if (num_entries != 256)
+		elog(ERROR,
+			 "rt_num_entries returned " UINT64_FORMAT ", expected " UINT64_FORMAT,
+			 num_entries, UINT64CONST(256));
+}
+
+/*
+ * Similar to test_node_types_insert_asc(), but inserts keys in descending order.
+ */
+static void
+test_node_types_insert_desc(rt_radix_tree *radixtree, uint8 shift)
+{
+	uint64 num_entries;
+	int node_class_idx = 0;
+	uint64 key_checked = NODE_TYPE_TEST_KEY_MAX - 1;
+
+	for (int i = NODE_TYPE_TEST_KEY_MAX - 1; i >= NODE_TYPE_TEST_KEY_MIN; i--)
+	{
+		uint64		key = ((uint64) i << shift);
+		bool		found;
+
+		found = rt_set(radixtree, key, (TestValueType *) &key);
+		if (found)
+			elog(ERROR, "newly inserted key 0x" UINT64_HEX_FORMAT " is found", key);
 
+		if ((i + 1) == rt_node_class_fanouts[node_class_idx])
+		{
+			check_search_on_node(radixtree, shift, i, key_checked);
+			key_checked = i;
+			node_class_idx++;
+		}
+	}
+
+	num_entries = rt_num_entries(radixtree);
 	if (num_entries != 256)
 		elog(ERROR,
 			 "rt_num_entries returned " UINT64_FORMAT ", expected " UINT64_FORMAT,
@@ -329,7 +360,7 @@ test_node_types_delete(rt_radix_tree *radixtree, uint8 shift)
 {
 	uint64		num_entries;
 
-	for (int i = 0; i < 256; i++)
+	for (int i = NODE_TYPE_TEST_KEY_MIN; i < NODE_TYPE_TEST_KEY_MAX; i++)
 	{
 		uint64		key = ((uint64) i << shift);
 		bool		found;
@@ -379,9 +410,9 @@ test_node_types(uint8 shift)
 	 * then delete all entries to make it empty, and insert and search entries
 	 * again.
 	 */
-	test_node_types_insert(radixtree, shift, true);
+	test_node_types_insert_asc(radixtree, shift);
 	test_node_types_delete(radixtree, shift);
-	test_node_types_insert(radixtree, shift, false);
+	test_node_types_insert_desc(radixtree, shift);
 
 	rt_free(radixtree);
 #ifdef RT_SHMEM
@@ -664,10 +695,10 @@ test_radixtree(PG_FUNCTION_ARGS)
 {
 	test_empty();
 
-	for (int i = 1; i < lengthof(rt_node_kind_fanouts); i++)
+	for (int i = 0; i < lengthof(rt_node_class_fanouts); i++)
 	{
-		test_basic(rt_node_kind_fanouts[i], false);
-		test_basic(rt_node_kind_fanouts[i], true);
+		test_basic(rt_node_class_fanouts[i], false);
+		test_basic(rt_node_class_fanouts[i], true);
 	}
 
 	for (int shift = 0; shift <= (64 - 8); shift += 8)
-- 
2.31.1