v26-0007-Skip-unnecessary-searches-in-RT_NODE_INSERT_INNE.patch

From 6831fe27a2c9c5765113b7903403c426f09f55f6 Mon Sep 17 00:00:00 2001
From: John Naylor <john.naylor@postgresql.org>
Date: Mon, 6 Feb 2023 22:04:50 +0700
Subject: [PATCH v26 7/9] Skip unnecessary searches in RT_NODE_INSERT_INNER

For inner nodes, we know the key chunk doesn't exist already,
otherwise we would have found it while descending the tree.

To reinforce this fact, declare this function to return void.
---
 src/include/lib/radixtree.h             |  4 +--
 src/include/lib/radixtree_insert_impl.h | 48 ++++++++++++-------------
 2 files changed, 24 insertions(+), 28 deletions(-)

diff --git a/src/include/lib/radixtree.h b/src/include/lib/radixtree.h
index 4bd0aaa810..1cdb995e54 100644
--- a/src/include/lib/radixtree.h
+++ b/src/include/lib/radixtree.h
@@ -685,7 +685,7 @@ typedef struct RT_ITER
 } RT_ITER;
 
 
-static bool RT_NODE_INSERT_INNER(RT_RADIX_TREE *tree, RT_PTR_LOCAL parent, RT_PTR_ALLOC stored_node, RT_PTR_LOCAL node,
+static void RT_NODE_INSERT_INNER(RT_RADIX_TREE *tree, RT_PTR_LOCAL parent, RT_PTR_ALLOC stored_node, RT_PTR_LOCAL node,
 								 uint64 key, RT_PTR_ALLOC child);
 static bool RT_NODE_INSERT_LEAF(RT_RADIX_TREE *tree, RT_PTR_LOCAL parent, RT_PTR_ALLOC stored_node, RT_PTR_LOCAL node,
 								uint64 key, RT_VALUE_TYPE *value_p);
@@ -1375,7 +1375,7 @@ RT_NODE_DELETE_LEAF(RT_PTR_LOCAL node, uint64 key)
  * If the node we're inserting into needs to grow, we update the parent's
  * child pointer with the pointer to the new larger node.
  */
-static bool
+static void
 RT_NODE_INSERT_INNER(RT_RADIX_TREE *tree, RT_PTR_LOCAL parent, RT_PTR_ALLOC stored_node, RT_PTR_LOCAL node,
 					uint64 key, RT_PTR_ALLOC child)
 {
diff --git a/src/include/lib/radixtree_insert_impl.h b/src/include/lib/radixtree_insert_impl.h
index c18e26b537..d56e58dcac 100644
--- a/src/include/lib/radixtree_insert_impl.h
+++ b/src/include/lib/radixtree_insert_impl.h
@@ -28,10 +28,10 @@
 #endif
 
 	uint8		chunk = RT_GET_KEY_CHUNK(key, node->shift);
-	bool		chunk_exists = false;
 
 #ifdef RT_NODE_LEVEL_LEAF
 	const bool is_leaf = true;
+	bool		chunk_exists = false;
 	Assert(RT_NODE_IS_LEAF(node));
 #else
 	const bool is_leaf = false;
@@ -43,21 +43,18 @@
 		case RT_NODE_KIND_3:
 			{
 				RT_NODE3_TYPE *n3 = (RT_NODE3_TYPE *) node;
-				int			idx;
 
-				idx = RT_NODE_3_SEARCH_EQ(&n3->base, chunk);
+#ifdef RT_NODE_LEVEL_LEAF
+				int idx = RT_NODE_3_SEARCH_EQ(&n3->base, chunk);
+
 				if (idx != -1)
 				{
 					/* found the existing chunk */
 					chunk_exists = true;
-#ifdef RT_NODE_LEVEL_LEAF
 					n3->values[idx] = *value_p;
-#else
-					n3->children[idx] = child;
-#endif
 					break;
 				}
-
+#endif
 				if (unlikely(RT_NODE_MUST_GROW(n3)))
 				{
 					RT_PTR_ALLOC allocnode;
@@ -113,21 +110,18 @@
 			{
 				const RT_SIZE_CLASS_ELEM class32_max = RT_SIZE_CLASS_INFO[RT_CLASS_32_MAX];
 				RT_NODE32_TYPE *n32 = (RT_NODE32_TYPE *) node;
-				int			idx;
 
-				idx = RT_NODE_32_SEARCH_EQ(&n32->base, chunk);
+#ifdef RT_NODE_LEVEL_LEAF
+				int idx = RT_NODE_32_SEARCH_EQ(&n32->base, chunk);
+
 				if (idx != -1)
 				{
 					/* found the existing chunk */
 					chunk_exists = true;
-#ifdef RT_NODE_LEVEL_LEAF
 					n32->values[idx] = *value_p;
-#else
-					n32->children[idx] = child;
-#endif
 					break;
 				}
-
+#endif
 				if (unlikely(RT_NODE_MUST_GROW(n32)) &&
 					n32->base.n.fanout < class32_max.fanout)
 				{
@@ -220,21 +214,19 @@
 		case RT_NODE_KIND_125:
 			{
 				RT_NODE125_TYPE *n125 = (RT_NODE125_TYPE *) node;
-				int			slotpos = n125->base.slot_idxs[chunk];
+				int			slotpos;
 				int			cnt = 0;
 
+#ifdef RT_NODE_LEVEL_LEAF
+				slotpos = n125->base.slot_idxs[chunk];
 				if (slotpos != RT_INVALID_SLOT_IDX)
 				{
 					/* found the existing chunk */
 					chunk_exists = true;
-#ifdef RT_NODE_LEVEL_LEAF
 					n125->values[slotpos] = *value_p;
-#else
-					n125->children[slotpos] = child;
-#endif
 					break;
 				}
-
+#endif
 				if (unlikely(RT_NODE_MUST_GROW(n125)))
 				{
 					RT_PTR_ALLOC allocnode;
@@ -300,14 +292,10 @@
 
 #ifdef RT_NODE_LEVEL_LEAF
 				chunk_exists = RT_NODE_LEAF_256_IS_CHUNK_USED(n256, chunk);
-#else
-				chunk_exists = RT_NODE_INNER_256_IS_CHUNK_USED(n256, chunk);
-#endif
 				Assert(chunk_exists || node->count < RT_NODE_MAX_SLOTS);
-
-#ifdef RT_NODE_LEVEL_LEAF
 				RT_NODE_LEAF_256_SET(n256, chunk, *value_p);
 #else
+				Assert(node->count < RT_NODE_MAX_SLOTS);
 				RT_NODE_INNER_256_SET(n256, chunk, child);
 #endif
 				break;
@@ -315,8 +303,12 @@
 	}
 
 	/* Update statistics */
+#ifdef RT_NODE_LEVEL_LEAF
 	if (!chunk_exists)
 		node->count++;
+#else
+		node->count++;
+#endif
 
 	/*
 	 * Done. Finally, verify the chunk and value is inserted or replaced
@@ -324,7 +316,11 @@
 	 */
 	RT_VERIFY_NODE(node);
 
+#ifdef RT_NODE_LEVEL_LEAF
 	return chunk_exists;
+#else
+	return;
+#endif
 
 #undef RT_NODE3_TYPE
 #undef RT_NODE32_TYPE
-- 
2.39.1