v16-0010-Template-out-node-insert-functions.patch

From 48892a7f66892aeb3346622fd7b26e20811154d8 Mon Sep 17 00:00:00 2001
From: John Naylor <john.naylor@postgresql.org>
Date: Fri, 23 Dec 2022 14:33:49 +0700
Subject: [PATCH v16 10/12] Template out node insert functions

---
 src/backend/lib/radixtree.c             | 369 +-----------------------
 src/include/lib/radixtree_insert_impl.h | 257 +++++++++++++++++
 2 files changed, 263 insertions(+), 363 deletions(-)
 create mode 100644 src/include/lib/radixtree_insert_impl.h

diff --git a/src/backend/lib/radixtree.c b/src/backend/lib/radixtree.c
index 7899e844fb..79d12b27d2 100644
--- a/src/backend/lib/radixtree.c
+++ b/src/backend/lib/radixtree.c
@@ -1290,185 +1290,9 @@ static bool
 rt_node_insert_inner(radix_tree *tree, rt_node *parent, rt_node *node, uint64 key,
 					 rt_node *child)
 {
-	uint8		chunk = RT_GET_KEY_CHUNK(key, node->shift);
-	bool		chunk_exists = false;
-	rt_node		*newnode = NULL;
-
-	Assert(!NODE_IS_LEAF(node));
-
-	switch (node->kind)
-	{
-		case RT_NODE_KIND_4:
-			{
-				rt_node_inner_4 *n4 = (rt_node_inner_4 *) node;
-				int			idx;
-
-				idx = node_4_search_eq(&n4->base, chunk);
-				if (idx != -1)
-				{
-					/* found the existing chunk */
-					chunk_exists = true;
-					n4->children[idx] = child;
-					break;
-				}
-
-				if (unlikely(!VAR_NODE_HAS_FREE_SLOT(n4)))
-				{
-					rt_node_inner_32 *new32;
-
-					/* grow node from 4 to 32 */
-					newnode = rt_grow_node_kind(tree, node, RT_NODE_KIND_32);
-					new32 = (rt_node_inner_32 *) newnode;
-					chunk_children_array_copy(n4->base.chunks, n4->children,
-											  new32->base.chunks, new32->children);
-
-					Assert(parent != NULL);
-					rt_replace_node(tree, parent, node, newnode, key);
-					node = newnode;
-				}
-				else
-				{
-					int			insertpos = node_4_get_insertpos(&n4->base, chunk);
-					uint16		count = n4->base.n.count;
-
-					/* shift chunks and children */
-					if (count != 0 && insertpos < count)
-						chunk_children_array_shift(n4->base.chunks, n4->children,
-												   count, insertpos);
-
-					n4->base.chunks[insertpos] = chunk;
-					n4->children[insertpos] = child;
-					break;
-				}
-			}
-			/* FALLTHROUGH */
-		case RT_NODE_KIND_32:
-			{
-				const rt_size_class_elem minclass = rt_size_class_info[RT_CLASS_32_PARTIAL];
-				const rt_size_class_elem maxclass = rt_size_class_info[RT_CLASS_32_FULL];
-				rt_node_inner_32 *n32 = (rt_node_inner_32 *) node;
-				int			idx;
-
-				idx = node_32_search_eq(&n32->base, chunk);
-				if (idx != -1)
-				{
-					/* found the existing chunk */
-					chunk_exists = true;
-					n32->children[idx] = child;
-					break;
-				}
-
-				if (unlikely(!VAR_NODE_HAS_FREE_SLOT(n32)) &&
-					n32->base.n.count == minclass.fanout)
-				{
-					/* grow to the next size class of this kind */
-					newnode = rt_alloc_node(tree, RT_CLASS_32_FULL, true);
-					memcpy(newnode, node, minclass.inner_size);
-					newnode->fanout = maxclass.fanout;
-
-					Assert(parent != NULL);
-					rt_replace_node(tree, parent, node, newnode, key);
-					node = newnode;
-
-					/* also update pointer for this kind */
-					n32 = (rt_node_inner_32 *) newnode;
-				}
-
-				if (unlikely(!VAR_NODE_HAS_FREE_SLOT(n32)))
-				{
-					rt_node_inner_125 *new125;
-
-					/* grow node from 32 to 125 */
-					newnode = rt_grow_node_kind(tree, node, RT_NODE_KIND_125);
-					new125 = (rt_node_inner_125 *) newnode;
-					for (int i = 0; i < n32->base.n.count; i++)
-						node_inner_125_insert(new125, n32->base.chunks[i], n32->children[i]);
-
-					Assert(parent != NULL);
-					rt_replace_node(tree, parent, node, newnode, key);
-					node = newnode;
-				}
-				else
-				{
-					int	insertpos = node_32_get_insertpos(&n32->base, chunk);
-					int16 count = n32->base.n.count;
-
-					if (insertpos < count)
-					{
-						Assert(count > 0);
-						chunk_children_array_shift(n32->base.chunks, n32->children,
-												   count, insertpos);
-					}
-
-					n32->base.chunks[insertpos] = chunk;
-					n32->children[insertpos] = child;
-					break;
-				}
-			}
-			/* FALLTHROUGH */
-		case RT_NODE_KIND_125:
-			{
-				rt_node_inner_125 *n125 = (rt_node_inner_125 *) node;
-				int			cnt = 0;
-
-				if (node_125_is_chunk_used(&n125->base, chunk))
-				{
-					/* found the existing chunk */
-					chunk_exists = true;
-					node_inner_125_update(n125, chunk, child);
-					break;
-				}
-
-				if (unlikely(!VAR_NODE_HAS_FREE_SLOT(n125)))
-				{
-					rt_node_inner_256 *new256;
-					Assert(parent != NULL);
-
-					/* grow node from 125 to 256 */
-					newnode = rt_grow_node_kind(tree, node, RT_NODE_KIND_256);
-					new256 = (rt_node_inner_256 *) newnode;
-					for (int i = 0; i < RT_NODE_MAX_SLOTS && cnt < n125->base.n.count; i++)
-					{
-						if (!node_125_is_chunk_used(&n125->base, i))
-							continue;
-
-						node_inner_256_set(new256, i, node_inner_125_get_child(n125, i));
-						cnt++;
-					}
-
-					rt_replace_node(tree, parent, node, newnode, key);
-					node = newnode;
-				}
-				else
-				{
-					node_inner_125_insert(n125, chunk, child);
-					break;
-				}
-			}
-			/* FALLTHROUGH */
-		case RT_NODE_KIND_256:
-			{
-				rt_node_inner_256 *n256 = (rt_node_inner_256 *) node;
-
-				chunk_exists = node_inner_256_is_chunk_used(n256, chunk);
-				Assert(chunk_exists || FIXED_NODE_HAS_FREE_SLOT(n256, RT_CLASS_256));
-
-				node_inner_256_set(n256, chunk, child);
-				break;
-			}
-	}
-
-	/* Update statistics */
-	if (!chunk_exists)
-		node->count++;
-
-	/*
-	 * Done. Finally, verify the chunk and value is inserted or replaced
-	 * properly in the node.
-	 */
-	rt_verify_node(node);
-
-	return chunk_exists;
+#define RT_NODE_LEVEL_INNER
+#include "lib/radixtree_insert_impl.h"
+#undef RT_NODE_LEVEL_INNER
 }
 
 /* Insert the value to the leaf node */
@@ -1476,190 +1300,9 @@ static bool
 rt_node_insert_leaf(radix_tree *tree, rt_node *parent, rt_node *node,
 					uint64 key, uint64 value)
 {
-	uint8		chunk = RT_GET_KEY_CHUNK(key, node->shift);
-	bool		chunk_exists = false;
-
-	Assert(NODE_IS_LEAF(node));
-
-	switch (node->kind)
-	{
-		case RT_NODE_KIND_4:
-			{
-				rt_node_leaf_4 *n4 = (rt_node_leaf_4 *) node;
-				int			idx;
-
-				idx = node_4_search_eq((rt_node_base_4 *) n4, chunk);
-				if (idx != -1)
-				{
-					/* found the existing chunk */
-					chunk_exists = true;
-					n4->values[idx] = value;
-					break;
-				}
-
-				if (unlikely(!VAR_NODE_HAS_FREE_SLOT(n4)))
-				{
-					rt_node_leaf_32 *new32;
-					Assert(parent != NULL);
-
-					/* grow node from 4 to 32 */
-					new32 = (rt_node_leaf_32 *) rt_grow_node_kind(tree, (rt_node *) n4,
-																  RT_NODE_KIND_32);
-					chunk_values_array_copy(n4->base.chunks, n4->values,
-											new32->base.chunks, new32->values);
-					rt_replace_node(tree, parent, (rt_node *) n4, (rt_node *) new32, key);
-					node = (rt_node *) new32;
-				}
-				else
-				{
-					int			insertpos = node_4_get_insertpos((rt_node_base_4 *) n4, chunk);
-					int			count = n4->base.n.count;
-
-					/* shift chunks and values */
-					if (count != 0 && insertpos < count)
-						chunk_values_array_shift(n4->base.chunks, n4->values,
-												 count, insertpos);
-
-					n4->base.chunks[insertpos] = chunk;
-					n4->values[insertpos] = value;
-					break;
-				}
-			}
-			/* FALLTHROUGH */
-		case RT_NODE_KIND_32:
-			{
-				rt_node_leaf_32 *n32 = (rt_node_leaf_32 *) node;
-				int			idx;
-
-				idx = node_32_search_eq((rt_node_base_32 *) n32, chunk);
-				if (idx != -1)
-				{
-					/* found the existing chunk */
-					chunk_exists = true;
-					n32->values[idx] = value;
-					break;
-				}
-
-				if (unlikely(!VAR_NODE_HAS_FREE_SLOT(n32)))
-				{
-					Assert(parent != NULL);
-
-					if (n32->base.n.count == rt_size_class_info[RT_CLASS_32_PARTIAL].fanout)
-					{
-						/* use the same node kind, but expand to the next size class */
-						const Size size = rt_size_class_info[RT_CLASS_32_PARTIAL].leaf_size;
-						const int fanout = rt_size_class_info[RT_CLASS_32_FULL].fanout;
-						rt_node_leaf_32 *new32;
-
-						new32 = (rt_node_leaf_32 *) rt_alloc_node(tree, RT_CLASS_32_FULL, false);
-						memcpy(new32, n32, size);
-						new32->base.n.fanout = fanout;
-
-						rt_replace_node(tree, parent, (rt_node *) n32, (rt_node *) new32, key);
-
-						/* must update both pointers here */
-						node = (rt_node *) new32;
-						n32 = new32;
-
-						goto retry_insert_leaf_32;
-					}
-					else
-					{
-						rt_node_leaf_125 *new125;
-
-						/* grow node from 32 to 125 */
-						new125 = (rt_node_leaf_125 *) rt_grow_node_kind(tree, (rt_node *) n32,
-																		RT_NODE_KIND_125);
-						for (int i = 0; i < n32->base.n.count; i++)
-							node_leaf_125_insert(new125, n32->base.chunks[i], n32->values[i]);
-
-						rt_replace_node(tree, parent, (rt_node *) n32, (rt_node *) new125,
-										key);
-						node = (rt_node *) new125;
-					}
-				}
-				else
-				{
-				retry_insert_leaf_32:
-					{
-						int	insertpos = node_32_get_insertpos((rt_node_base_32 *) n32, chunk);
-						int	count = n32->base.n.count;
-
-						if (count != 0 && insertpos < count)
-							chunk_values_array_shift(n32->base.chunks, n32->values,
-													 count, insertpos);
-
-						n32->base.chunks[insertpos] = chunk;
-						n32->values[insertpos] = value;
-						break;
-					}
-				}
-			}
-			/* FALLTHROUGH */
-		case RT_NODE_KIND_125:
-			{
-				rt_node_leaf_125 *n125 = (rt_node_leaf_125 *) node;
-				int			cnt = 0;
-
-				if (node_125_is_chunk_used((rt_node_base_125 *) n125, chunk))
-				{
-					/* found the existing chunk */
-					chunk_exists = true;
-					node_leaf_125_update(n125, chunk, value);
-					break;
-				}
-
-				if (unlikely(!VAR_NODE_HAS_FREE_SLOT(n125)))
-				{
-					rt_node_leaf_256 *new256;
-					Assert(parent != NULL);
-
-					/* grow node from 125 to 256 */
-					new256 = (rt_node_leaf_256 *) rt_grow_node_kind(tree, (rt_node *) n125,
-																	RT_NODE_KIND_256);
-					for (int i = 0; i < RT_NODE_MAX_SLOTS && cnt < n125->base.n.count; i++)
-					{
-						if (!node_125_is_chunk_used((rt_node_base_125 *) n125, i))
-							continue;
-
-						node_leaf_256_set(new256, i, node_leaf_125_get_value(n125, i));
-						cnt++;
-					}
-
-					rt_replace_node(tree, parent, (rt_node *) n125, (rt_node *) new256,
-									key);
-					node = (rt_node *) new256;
-				}
-				else
-				{
-					node_leaf_125_insert(n125, chunk, value);
-					break;
-				}
-			}
-			/* FALLTHROUGH */
-		case RT_NODE_KIND_256:
-			{
-				rt_node_leaf_256 *n256 = (rt_node_leaf_256 *) node;
-
-				chunk_exists = node_leaf_256_is_chunk_used(n256, chunk);
-				Assert(chunk_exists || FIXED_NODE_HAS_FREE_SLOT(n256, RT_CLASS_256));
-
-				node_leaf_256_set(n256, chunk, value);
-				break;
-			}
-	}
-
-	/* Update statistics */
-	if (!chunk_exists)
-		node->count++;
-
-	/*
-	 * Done. Finally, verify the chunk and value is inserted or replaced
-	 * properly in the node.
-	 */
-	rt_verify_node(node);
-
-	return chunk_exists;
+#define RT_NODE_LEVEL_LEAF
+#include "lib/radixtree_insert_impl.h"
+#undef RT_NODE_LEVEL_LEAF
 }
 
 /*
diff --git a/src/include/lib/radixtree_insert_impl.h b/src/include/lib/radixtree_insert_impl.h
new file mode 100644
index 0000000000..8e02c83fc7
--- /dev/null
+++ b/src/include/lib/radixtree_insert_impl.h
@@ -0,0 +1,257 @@
+#if defined(RT_NODE_LEVEL_INNER)
+#define RT_NODE4_TYPE rt_node_inner_4
+#define RT_NODE32_TYPE rt_node_inner_32
+#define RT_NODE125_TYPE rt_node_inner_125
+#define RT_NODE256_TYPE rt_node_inner_256
+#elif defined(RT_NODE_LEVEL_LEAF)
+#define RT_NODE4_TYPE rt_node_leaf_4
+#define RT_NODE32_TYPE rt_node_leaf_32
+#define RT_NODE125_TYPE rt_node_leaf_125
+#define RT_NODE256_TYPE rt_node_leaf_256
+#else
+#error node level must be either inner or leaf
+#endif
+
+	uint8		chunk = RT_GET_KEY_CHUNK(key, node->shift);
+	bool		chunk_exists = false;
+	rt_node		*newnode = NULL;
+
+#ifdef RT_NODE_LEVEL_LEAF
+	Assert(NODE_IS_LEAF(node));
+#else
+	Assert(!NODE_IS_LEAF(node));
+#endif
+
+	switch (node->kind)
+	{
+		case RT_NODE_KIND_4:
+			{
+				RT_NODE4_TYPE *n4 = (RT_NODE4_TYPE *) node;
+				int			idx;
+
+				idx = node_4_search_eq(&n4->base, chunk);
+				if (idx != -1)
+				{
+					/* found the existing chunk */
+					chunk_exists = true;
+#ifdef RT_NODE_LEVEL_LEAF
+					n4->values[idx] = value;
+#else
+					n4->children[idx] = child;
+#endif
+					break;
+				}
+
+				if (unlikely(!VAR_NODE_HAS_FREE_SLOT(n4)))
+				{
+					RT_NODE32_TYPE *new32;
+
+					/* grow node from 4 to 32 */
+					newnode = rt_grow_node_kind(tree, node, RT_NODE_KIND_32);
+					new32 = (RT_NODE32_TYPE *) newnode;
+#ifdef RT_NODE_LEVEL_LEAF
+					chunk_values_array_copy(n4->base.chunks, n4->values,
+											  new32->base.chunks, new32->values);
+#else
+					chunk_children_array_copy(n4->base.chunks, n4->children,
+											  new32->base.chunks, new32->children);
+#endif
+					Assert(parent != NULL);
+					rt_replace_node(tree, parent, node, newnode, key);
+					node = newnode;
+				}
+				else
+				{
+					int			insertpos = node_4_get_insertpos(&n4->base, chunk);
+					int			count = n4->base.n.count;
+
+					/* shift chunks and children */
+					if (insertpos < count)
+					{
+						Assert(count > 0);
+#ifdef RT_NODE_LEVEL_LEAF
+						chunk_values_array_shift(n4->base.chunks, n4->values,
+												   count, insertpos);
+#else
+						chunk_children_array_shift(n4->base.chunks, n4->children,
+												   count, insertpos);
+#endif
+					}
+
+					n4->base.chunks[insertpos] = chunk;
+#ifdef RT_NODE_LEVEL_LEAF
+					n4->values[insertpos] = value;
+#else
+					n4->children[insertpos] = child;
+#endif
+					break;
+				}
+			}
+			/* FALLTHROUGH */
+		case RT_NODE_KIND_32:
+			{
+				const rt_size_class_elem minclass = rt_size_class_info[RT_CLASS_32_PARTIAL];
+				const rt_size_class_elem maxclass = rt_size_class_info[RT_CLASS_32_FULL];
+				RT_NODE32_TYPE *n32 = (RT_NODE32_TYPE *) node;
+				int			idx;
+
+				idx = 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;
+#else
+					n32->children[idx] = child;
+#endif
+					break;
+				}
+
+				if (unlikely(!VAR_NODE_HAS_FREE_SLOT(n32)) &&
+					n32->base.n.count == minclass.fanout)
+				{
+					/* grow to the next size class of this kind */
+					newnode = rt_alloc_node(tree, RT_CLASS_32_FULL, true);
+					memcpy(newnode, node, minclass.inner_size);
+					newnode->fanout = maxclass.fanout;
+
+					Assert(parent != NULL);
+					rt_replace_node(tree, parent, node, newnode, key);
+					node = newnode;
+
+					/* also update pointer for this kind */
+					n32 = (RT_NODE32_TYPE *) newnode;
+				}
+
+				if (unlikely(!VAR_NODE_HAS_FREE_SLOT(n32)))
+				{
+					RT_NODE125_TYPE *new125;
+
+					/* grow node from 32 to 125 */
+					newnode = rt_grow_node_kind(tree, node, RT_NODE_KIND_125);
+					new125 = (RT_NODE125_TYPE *) newnode;
+					for (int i = 0; i < n32->base.n.count; i++)
+#ifdef RT_NODE_LEVEL_LEAF
+						node_leaf_125_insert(new125, n32->base.chunks[i], n32->values[i]);
+#else
+						node_inner_125_insert(new125, n32->base.chunks[i], n32->children[i]);
+#endif
+					Assert(parent != NULL);
+					rt_replace_node(tree, parent, node, newnode, key);
+					node = newnode;
+				}
+				else
+				{
+					int	insertpos = node_32_get_insertpos(&n32->base, chunk);
+					int count = n32->base.n.count;
+
+					if (insertpos < count)
+					{
+						Assert(count > 0);
+#ifdef RT_NODE_LEVEL_LEAF
+						chunk_values_array_shift(n32->base.chunks, n32->values,
+												   count, insertpos);
+#else
+						chunk_children_array_shift(n32->base.chunks, n32->children,
+												   count, insertpos);
+#endif
+					}
+
+					n32->base.chunks[insertpos] = chunk;
+#ifdef RT_NODE_LEVEL_LEAF
+					n32->values[insertpos] = value;
+#else
+					n32->children[insertpos] = child;
+#endif
+					break;
+				}
+			}
+			/* FALLTHROUGH */
+		case RT_NODE_KIND_125:
+			{
+				RT_NODE125_TYPE *n125 = (RT_NODE125_TYPE *) node;
+				int			cnt = 0;
+
+				if (node_125_is_chunk_used(&n125->base, chunk))
+				{
+					/* found the existing chunk */
+					chunk_exists = true;
+#ifdef RT_NODE_LEVEL_LEAF
+					node_leaf_125_update(n125, chunk, value);
+#else
+					node_inner_125_update(n125, chunk, child);
+#endif
+					break;
+				}
+
+				if (unlikely(!VAR_NODE_HAS_FREE_SLOT(n125)))
+				{
+					RT_NODE256_TYPE *new256;
+
+					/* grow node from 125 to 256 */
+					newnode = rt_grow_node_kind(tree, node, RT_NODE_KIND_256);
+					new256 = (RT_NODE256_TYPE *) newnode;
+					for (int i = 0; i < RT_NODE_MAX_SLOTS && cnt < n125->base.n.count; i++)
+					{
+						if (!node_125_is_chunk_used(&n125->base, i))
+							continue;
+#ifdef RT_NODE_LEVEL_LEAF
+						node_leaf_256_set(new256, i, node_leaf_125_get_value(n125, i));
+#else
+						node_inner_256_set(new256, i, node_inner_125_get_child(n125, i));
+#endif
+						cnt++;
+					}
+
+					Assert(parent != NULL);
+					rt_replace_node(tree, parent, node, newnode, key);
+					node = newnode;
+				}
+				else
+				{
+#ifdef RT_NODE_LEVEL_LEAF
+					node_leaf_125_insert(n125, chunk, value);
+#else
+					node_inner_125_insert(n125, chunk, child);
+#endif
+					break;
+				}
+			}
+			/* FALLTHROUGH */
+		case RT_NODE_KIND_256:
+			{
+				RT_NODE256_TYPE *n256 = (RT_NODE256_TYPE *) node;
+
+#ifdef RT_NODE_LEVEL_LEAF
+				chunk_exists = node_leaf_256_is_chunk_used(n256, chunk);
+#else
+				chunk_exists = node_inner_256_is_chunk_used(n256, chunk);
+#endif
+				Assert(chunk_exists || FIXED_NODE_HAS_FREE_SLOT(n256, RT_CLASS_256));
+
+#ifdef RT_NODE_LEVEL_LEAF
+				node_leaf_256_set(n256, chunk, value);
+#else
+				node_inner_256_set(n256, chunk, child);
+#endif
+				break;
+			}
+	}
+
+	/* Update statistics */
+	if (!chunk_exists)
+		node->count++;
+
+	/*
+	 * Done. Finally, verify the chunk and value is inserted or replaced
+	 * properly in the node.
+	 */
+	rt_verify_node(node);
+
+	return chunk_exists;
+
+#undef RT_NODE4_TYPE
+#undef RT_NODE32_TYPE
+#undef RT_NODE125_TYPE
+#undef RT_NODE256_TYPE
-- 
2.38.1