v31-0013-Add-min-and-max-classes-for-node3-and-node125.patch

From 1b43002d25137699d0e13158d821a8550e757348 Mon Sep 17 00:00:00 2001
From: Masahiko Sawada <sawada.mshk@gmail.com>
Date: Thu, 9 Mar 2023 11:42:17 +0900
Subject: [PATCH v31 13/14] Add min and max classes for node3 and node125.

---
 src/include/lib/radixtree.h                   | 70 +++++++++++++------
 src/include/lib/radixtree_insert_impl.h       | 56 ++++++++++++++-
 .../expected/test_radixtree.out               |  4 ++
 .../modules/test_radixtree/test_radixtree.c   |  6 +-
 4 files changed, 110 insertions(+), 26 deletions(-)

diff --git a/src/include/lib/radixtree.h b/src/include/lib/radixtree.h
index f7812eb12a..1759c909b6 100644
--- a/src/include/lib/radixtree.h
+++ b/src/include/lib/radixtree.h
@@ -225,10 +225,12 @@
 #define RT_SIZE_CLASS RT_MAKE_NAME(size_class)
 #define RT_SIZE_CLASS_ELEM RT_MAKE_NAME(size_class_elem)
 #define RT_SIZE_CLASS_INFO RT_MAKE_NAME(size_class_info)
-#define RT_CLASS_3 RT_MAKE_NAME(class_3)
+#define RT_CLASS_3_MIN RT_MAKE_NAME(class_3_min)
+#define RT_CLASS_3_MAX RT_MAKE_NAME(class_3_max)
 #define RT_CLASS_32_MIN RT_MAKE_NAME(class_32_min)
 #define RT_CLASS_32_MAX RT_MAKE_NAME(class_32_max)
-#define RT_CLASS_125 RT_MAKE_NAME(class_125)
+#define RT_CLASS_125_MIN RT_MAKE_NAME(class_125_min)
+#define RT_CLASS_125_MAX RT_MAKE_NAME(class_125_max)
 #define RT_CLASS_256 RT_MAKE_NAME(class_256)
 
 /* generate forward declarations necessary to use the radix tree */
@@ -561,10 +563,12 @@ typedef struct RT_NODE_LEAF_256
  */
 typedef enum RT_SIZE_CLASS
 {
-	RT_CLASS_3 = 0,
+	RT_CLASS_3_MIN = 0,
+	RT_CLASS_3_MAX,
 	RT_CLASS_32_MIN,
 	RT_CLASS_32_MAX,
-	RT_CLASS_125,
+	RT_CLASS_125_MIN,
+	RT_CLASS_125_MAX,
 	RT_CLASS_256
 } RT_SIZE_CLASS;
 
@@ -580,7 +584,13 @@ typedef struct RT_SIZE_CLASS_ELEM
 } RT_SIZE_CLASS_ELEM;
 
 static const RT_SIZE_CLASS_ELEM RT_SIZE_CLASS_INFO[] = {
-	[RT_CLASS_3] = {
+	[RT_CLASS_3_MIN] = {
+		.name = "radix tree node 1",
+		.fanout = 1,
+		.inner_size = sizeof(RT_NODE_INNER_3) + 1 * sizeof(RT_PTR_ALLOC),
+		.leaf_size = sizeof(RT_NODE_LEAF_3) + 1 * sizeof(RT_VALUE_TYPE),
+	},
+	[RT_CLASS_3_MAX] = {
 		.name = "radix tree node 3",
 		.fanout = 3,
 		.inner_size = sizeof(RT_NODE_INNER_3) + 3 * sizeof(RT_PTR_ALLOC),
@@ -598,7 +608,13 @@ static const RT_SIZE_CLASS_ELEM RT_SIZE_CLASS_INFO[] = {
 		.inner_size = sizeof(RT_NODE_INNER_32) + 32 * sizeof(RT_PTR_ALLOC),
 		.leaf_size = sizeof(RT_NODE_LEAF_32) + 32 * sizeof(RT_VALUE_TYPE),
 	},
-	[RT_CLASS_125] = {
+	[RT_CLASS_125_MIN] = {
+		.name = "radix tree node 125",
+		.fanout = 61,
+		.inner_size = sizeof(RT_NODE_INNER_125) + 61 * sizeof(RT_PTR_ALLOC),
+		.leaf_size = sizeof(RT_NODE_LEAF_125) + 61 * sizeof(RT_VALUE_TYPE),
+	},
+	[RT_CLASS_125_MAX] = {
 		.name = "radix tree node 125",
 		.fanout = 125,
 		.inner_size = sizeof(RT_NODE_INNER_125) + 125 * sizeof(RT_PTR_ALLOC),
@@ -934,7 +950,7 @@ static inline void
 RT_CHUNK_CHILDREN_ARRAY_COPY(uint8 *src_chunks, RT_PTR_ALLOC *src_children,
 						  uint8 *dst_chunks, RT_PTR_ALLOC *dst_children)
 {
-	const int fanout = RT_SIZE_CLASS_INFO[RT_CLASS_3].fanout;
+	const int fanout = RT_SIZE_CLASS_INFO[RT_CLASS_3_MAX].fanout;
 	const Size chunk_size = sizeof(uint8) * fanout;
 	const Size children_size = sizeof(RT_PTR_ALLOC) * fanout;
 
@@ -946,7 +962,7 @@ static inline void
 RT_CHUNK_VALUES_ARRAY_COPY(uint8 *src_chunks, RT_VALUE_TYPE *src_values,
 						uint8 *dst_chunks, RT_VALUE_TYPE *dst_values)
 {
-	const int fanout = RT_SIZE_CLASS_INFO[RT_CLASS_3].fanout;
+	const int fanout = RT_SIZE_CLASS_INFO[RT_CLASS_3_MAX].fanout;
 	const Size chunk_size = sizeof(uint8) * fanout;
 	const Size values_size = sizeof(RT_VALUE_TYPE) * fanout;
 
@@ -1152,9 +1168,9 @@ RT_NEW_ROOT(RT_RADIX_TREE *tree, uint64 key)
 	RT_PTR_ALLOC allocnode;
 	RT_PTR_LOCAL newnode;
 
-	allocnode = RT_ALLOC_NODE(tree, RT_CLASS_3, is_leaf);
+	allocnode = RT_ALLOC_NODE(tree, RT_CLASS_3_MIN, is_leaf);
 	newnode = RT_PTR_GET_LOCAL(tree, allocnode);
-	RT_INIT_NODE(newnode, RT_NODE_KIND_3, RT_CLASS_3, is_leaf);
+	RT_INIT_NODE(newnode, RT_NODE_KIND_3, RT_CLASS_3_MIN, is_leaf);
 	newnode->shift = shift;
 	tree->ctl->max_val = RT_SHIFT_GET_MAX_VAL(shift);
 	tree->ctl->root = allocnode;
@@ -1188,17 +1204,21 @@ static inline Size
 RT_FANOUT_GET_NODE_SIZE(int fanout, bool is_leaf)
 {
 	const Size fanout_inner_node_size[] = {
-		[3] = RT_SIZE_CLASS_INFO[RT_CLASS_3].inner_size,
+		[1] = RT_SIZE_CLASS_INFO[RT_CLASS_3_MIN].inner_size,
+		[3] = RT_SIZE_CLASS_INFO[RT_CLASS_3_MAX].inner_size,
 		[15] = RT_SIZE_CLASS_INFO[RT_CLASS_32_MIN].inner_size,
 		[32] = RT_SIZE_CLASS_INFO[RT_CLASS_32_MAX].inner_size,
-		[125] = RT_SIZE_CLASS_INFO[RT_CLASS_125].inner_size,
+		[61] = RT_SIZE_CLASS_INFO[RT_CLASS_125_MIN].inner_size,
+		[125] = RT_SIZE_CLASS_INFO[RT_CLASS_125_MAX].inner_size,
 		[256] = RT_SIZE_CLASS_INFO[RT_CLASS_256].inner_size,
 	};
 	const Size fanout_leaf_node_size[] = {
-		[3] = RT_SIZE_CLASS_INFO[RT_CLASS_3].leaf_size,
+		[1] = RT_SIZE_CLASS_INFO[RT_CLASS_3_MIN].leaf_size,
+		[3] = RT_SIZE_CLASS_INFO[RT_CLASS_3_MAX].leaf_size,
 		[15] = RT_SIZE_CLASS_INFO[RT_CLASS_32_MIN].leaf_size,
 		[32] = RT_SIZE_CLASS_INFO[RT_CLASS_32_MAX].leaf_size,
-		[125] = RT_SIZE_CLASS_INFO[RT_CLASS_125].leaf_size,
+		[61] = RT_SIZE_CLASS_INFO[RT_CLASS_125_MIN].leaf_size,
+		[125] = RT_SIZE_CLASS_INFO[RT_CLASS_125_MAX].leaf_size,
 		[256] = RT_SIZE_CLASS_INFO[RT_CLASS_256].leaf_size,
 	};
 	Size node_size;
@@ -1337,9 +1357,9 @@ RT_EXTEND_UP(RT_RADIX_TREE *tree, uint64 key)
 		RT_PTR_LOCAL	node;
 		RT_NODE_INNER_3 *n3;
 
-		allocnode = RT_ALLOC_NODE(tree, RT_CLASS_3, true);
+		allocnode = RT_ALLOC_NODE(tree, RT_CLASS_3_MIN, true);
 		node = RT_PTR_GET_LOCAL(tree, allocnode);
-		RT_INIT_NODE(node, RT_NODE_KIND_3, RT_CLASS_3, true);
+		RT_INIT_NODE(node, RT_NODE_KIND_3, RT_CLASS_3_MIN, true);
 		node->shift = shift;
 		node->count = 1;
 
@@ -1375,9 +1395,9 @@ RT_EXTEND_DOWN(RT_RADIX_TREE *tree, uint64 key, RT_VALUE_TYPE *value_p, RT_PTR_L
 		int			newshift = shift - RT_NODE_SPAN;
 		bool		is_leaf = newshift == 0;
 
-		allocchild = RT_ALLOC_NODE(tree, RT_CLASS_3, is_leaf);
+		allocchild = RT_ALLOC_NODE(tree, RT_CLASS_3_MIN, is_leaf);
 		newchild = RT_PTR_GET_LOCAL(tree, allocchild);
-		RT_INIT_NODE(newchild, RT_NODE_KIND_3, RT_CLASS_3, is_leaf);
+		RT_INIT_NODE(newchild, RT_NODE_KIND_3, RT_CLASS_3_MIN, is_leaf);
 		newchild->shift = newshift;
 		RT_NODE_INSERT_INNER(tree, parent, stored_node, node, key, allocchild);
 
@@ -2177,12 +2197,14 @@ RT_STATS(RT_RADIX_TREE *tree)
 	{
 		RT_PTR_LOCAL root = RT_PTR_GET_LOCAL(tree, tree->ctl->root);
 
-		fprintf(stderr, "height = %d, n3 = %u, n15 = %u, n32 = %u, n125 = %u, n256 = %u\n",
+		fprintf(stderr, "height = %d, n1 = %u, n3 = %u, n15 = %u, n32 = %u, n61 = %u, n125 = %u, n256 = %u\n",
 				root->shift / RT_NODE_SPAN,
-				tree->ctl->cnt[RT_CLASS_3],
+				tree->ctl->cnt[RT_CLASS_3_MIN],
+				tree->ctl->cnt[RT_CLASS_3_MAX],
 				tree->ctl->cnt[RT_CLASS_32_MIN],
 				tree->ctl->cnt[RT_CLASS_32_MAX],
-				tree->ctl->cnt[RT_CLASS_125],
+				tree->ctl->cnt[RT_CLASS_125_MIN],
+				tree->ctl->cnt[RT_CLASS_125_MAX],
 				tree->ctl->cnt[RT_CLASS_256]);
 	}
 
@@ -2519,10 +2541,12 @@ RT_DUMP(RT_RADIX_TREE *tree)
 #undef RT_SIZE_CLASS
 #undef RT_SIZE_CLASS_ELEM
 #undef RT_SIZE_CLASS_INFO
-#undef RT_CLASS_3
+#undef RT_CLASS_3_MIN
+#undef RT_CLASS_3_MAX
 #undef RT_CLASS_32_MIN
 #undef RT_CLASS_32_MAX
-#undef RT_CLASS_125
+#undef RT_CLASS_125_MIN
+#undef RT_CLASS_125_MAX
 #undef RT_CLASS_256
 
 /* function declarations */
diff --git a/src/include/lib/radixtree_insert_impl.h b/src/include/lib/radixtree_insert_impl.h
index d56e58dcac..d10093dfba 100644
--- a/src/include/lib/radixtree_insert_impl.h
+++ b/src/include/lib/radixtree_insert_impl.h
@@ -42,6 +42,7 @@
 	{
 		case RT_NODE_KIND_3:
 			{
+				const RT_SIZE_CLASS_ELEM class3_max = RT_SIZE_CLASS_INFO[RT_CLASS_3_MAX];
 				RT_NODE3_TYPE *n3 = (RT_NODE3_TYPE *) node;
 
 #ifdef RT_NODE_LEVEL_LEAF
@@ -55,6 +56,32 @@
 					break;
 				}
 #endif
+				if (unlikely(RT_NODE_MUST_GROW(n3)) &&
+					n3->base.n.fanout < class3_max.fanout)
+				{
+					RT_PTR_ALLOC allocnode;
+					RT_PTR_LOCAL newnode;
+					const RT_SIZE_CLASS_ELEM class3_min = RT_SIZE_CLASS_INFO[RT_CLASS_3_MIN];
+					const RT_SIZE_CLASS new_class = RT_CLASS_3_MAX;
+
+					Assert(n3->base.n.fanout == class3_min.fanout);
+
+					/* grow to the next size class of this kind */
+					allocnode = RT_ALLOC_NODE(tree, new_class, is_leaf);
+					newnode = RT_PTR_GET_LOCAL(tree, allocnode);
+					n3 = (RT_NODE3_TYPE *) newnode;
+
+#ifdef RT_NODE_LEVEL_LEAF
+					memcpy(newnode, node, class3_min.leaf_size);
+#else
+					memcpy(newnode, node, class3_min.inner_size);
+#endif
+					newnode->fanout = class3_max.fanout;
+
+					RT_REPLACE_NODE(tree, parent, stored_node, node, allocnode, key);
+					node = newnode;
+				}
+
 				if (unlikely(RT_NODE_MUST_GROW(n3)))
 				{
 					RT_PTR_ALLOC allocnode;
@@ -154,7 +181,7 @@
 					RT_PTR_LOCAL newnode;
 					RT_NODE125_TYPE *new125;
 					const uint8 new_kind = RT_NODE_KIND_125;
-					const RT_SIZE_CLASS new_class = RT_CLASS_125;
+					const RT_SIZE_CLASS new_class = RT_CLASS_125_MIN;
 
 					Assert(n32->base.n.fanout == class32_max.fanout);
 
@@ -213,6 +240,7 @@
 			/* FALLTHROUGH */
 		case RT_NODE_KIND_125:
 			{
+				const RT_SIZE_CLASS_ELEM class125_max = RT_SIZE_CLASS_INFO[RT_CLASS_125_MAX];
 				RT_NODE125_TYPE *n125 = (RT_NODE125_TYPE *) node;
 				int			slotpos;
 				int			cnt = 0;
@@ -227,6 +255,32 @@
 					break;
 				}
 #endif
+				if (unlikely(RT_NODE_MUST_GROW(n125)) &&
+					n125->base.n.fanout < class125_max.fanout)
+				{
+					RT_PTR_ALLOC allocnode;
+					RT_PTR_LOCAL newnode;
+					const RT_SIZE_CLASS_ELEM class125_min = RT_SIZE_CLASS_INFO[RT_CLASS_125_MIN];
+					const RT_SIZE_CLASS new_class = RT_CLASS_125_MAX;
+
+					Assert(n125->base.n.fanout == class125_min.fanout);
+
+					/* grow to the next size class of this kind */
+					allocnode = RT_ALLOC_NODE(tree, new_class, is_leaf);
+					newnode = RT_PTR_GET_LOCAL(tree, allocnode);
+					n125 = (RT_NODE125_TYPE *) newnode;
+
+#ifdef RT_NODE_LEVEL_LEAF
+					memcpy(newnode, node, class125_min.leaf_size);
+#else
+					memcpy(newnode, node, class125_min.inner_size);
+#endif
+					newnode->fanout = class125_max.fanout;
+
+					RT_REPLACE_NODE(tree, parent, stored_node, node, allocnode, key);
+					node = newnode;
+				}
+
 				if (unlikely(RT_NODE_MUST_GROW(n125)))
 				{
 					RT_PTR_ALLOC allocnode;
diff --git a/src/test/modules/test_radixtree/expected/test_radixtree.out b/src/test/modules/test_radixtree/expected/test_radixtree.out
index 7ad1ce3605..f2b1d7e4f8 100644
--- a/src/test/modules/test_radixtree/expected/test_radixtree.out
+++ b/src/test/modules/test_radixtree/expected/test_radixtree.out
@@ -4,12 +4,16 @@ CREATE EXTENSION test_radixtree;
 -- an error if something fails.
 --
 SELECT test_radixtree();
+NOTICE:  testing basic operations with leaf node 1
+NOTICE:  testing basic operations with inner node 1
 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 61
+NOTICE:  testing basic operations with inner node 61
 NOTICE:  testing basic operations with leaf node 125
 NOTICE:  testing basic operations with inner node 125
 NOTICE:  testing basic operations with leaf node 256
diff --git a/src/test/modules/test_radixtree/test_radixtree.c b/src/test/modules/test_radixtree/test_radixtree.c
index 19d286d84b..4f38b6e3de 100644
--- a/src/test/modules/test_radixtree/test_radixtree.c
+++ b/src/test/modules/test_radixtree/test_radixtree.c
@@ -47,10 +47,12 @@ static const bool rt_test_stats = false;
  * XXX: should we expose and use RT_SIZE_CLASS and RT_SIZE_CLASS_INFO?
  */
 static int	rt_node_class_fanouts[] = {
-	3,		/* RT_CLASS_3 */
+	1,		/* RT_CLASS_3_MIN */
+	3,		/* RT_CLASS_3_MAX */
 	15,		/* RT_CLASS_32_MIN */
 	32, 	/* RT_CLASS_32_MAX */
-	125,	/* RT_CLASS_125 */
+	61,		/* RT_CLASS_125_MIN */
+	125,	/* RT_CLASS_125_MAX */
 	256		/* RT_CLASS_256 */
 };
 /*
-- 
2.31.1