v21-0004-Clean-up-some-nomenclature-around-node-insertion.patch

From d9f4b6280f73076df05c1fd03ca6860df3b90c74 Mon Sep 17 00:00:00 2001
From: John Naylor <john.naylor@postgresql.org>
Date: Thu, 19 Jan 2023 16:33:51 +0700
Subject: [PATCH v21 04/22] Clean up some nomenclature around node insertion

Replace node/nodep with hopefully more informative names.

In passing, remove some outdated asserts and move some
variable declarations to the scope where they're used.
---
 src/include/lib/radixtree.h             | 64 ++++++++++++++-----------
 src/include/lib/radixtree_insert_impl.h | 22 +++++----
 2 files changed, 47 insertions(+), 39 deletions(-)

diff --git a/src/include/lib/radixtree.h b/src/include/lib/radixtree.h
index 97cccdc9ca..a1458bc25f 100644
--- a/src/include/lib/radixtree.h
+++ b/src/include/lib/radixtree.h
@@ -645,9 +645,9 @@ typedef struct RT_ITER
 } RT_ITER;
 
 
-static bool RT_NODE_INSERT_INNER(RT_RADIX_TREE *tree, RT_PTR_LOCAL parent, RT_PTR_ALLOC nodep, RT_PTR_LOCAL node,
+static bool 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 nodep, RT_PTR_LOCAL node,
+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, uint64 value);
 
 /* verification (available only with assertion) */
@@ -1153,18 +1153,18 @@ RT_NODE_UPDATE_INNER(RT_PTR_LOCAL node, uint64 key, RT_PTR_ALLOC new_child)
  * Replace old_child with new_child, and free the old one.
  */
 static void
-RT_REPLACE_NODE(RT_RADIX_TREE *tree, RT_PTR_LOCAL parent, RT_PTR_ALLOC old_child,
+RT_REPLACE_NODE(RT_RADIX_TREE *tree, RT_PTR_LOCAL parent,
+				RT_PTR_ALLOC stored_old_child, RT_PTR_LOCAL old_child,
 				RT_PTR_ALLOC new_child, uint64 key)
 {
-	RT_PTR_LOCAL old = RT_PTR_GET_LOCAL(tree, old_child);
-
 #ifdef USE_ASSERT_CHECKING
 	RT_PTR_LOCAL new = RT_PTR_GET_LOCAL(tree, new_child);
 
-	Assert(old->shift == new->shift);
+	Assert(old_child->shift == new->shift);
+	Assert(old_child->count == new->count);
 #endif
 
-	if (parent == old)
+	if (parent == old_child)
 	{
 		/* Replace the root node with the new large node */
 		tree->ctl->root = new_child;
@@ -1172,7 +1172,7 @@ RT_REPLACE_NODE(RT_RADIX_TREE *tree, RT_PTR_LOCAL parent, RT_PTR_ALLOC old_child
 	else
 		RT_NODE_UPDATE_INNER(parent, key, new_child);
 
-	RT_FREE_NODE(tree, old_child);
+	RT_FREE_NODE(tree, stored_old_child);
 }
 
 /*
@@ -1220,11 +1220,11 @@ RT_EXTEND(RT_RADIX_TREE *tree, uint64 key)
  */
 static inline void
 RT_SET_EXTEND(RT_RADIX_TREE *tree, uint64 key, uint64 value, RT_PTR_LOCAL parent,
-			  RT_PTR_ALLOC nodep, RT_PTR_LOCAL node)
+			  RT_PTR_ALLOC stored_node, RT_PTR_LOCAL node)
 {
 	int			shift = node->shift;
 
-	Assert(RT_PTR_GET_LOCAL(tree, nodep) == node);
+	Assert(RT_PTR_GET_LOCAL(tree, stored_node) == node);
 
 	while (shift >= RT_NODE_SPAN)
 	{
@@ -1237,15 +1237,15 @@ RT_SET_EXTEND(RT_RADIX_TREE *tree, uint64 key, uint64 value, RT_PTR_LOCAL parent
 		newchild = RT_PTR_GET_LOCAL(tree, allocchild);
 		RT_INIT_NODE(newchild, RT_NODE_KIND_4, RT_CLASS_4_FULL, inner);
 		newchild->shift = newshift;
-		RT_NODE_INSERT_INNER(tree, parent, nodep, node, key, allocchild);
+		RT_NODE_INSERT_INNER(tree, parent, stored_node, node, key, allocchild);
 
 		parent = node;
 		node = newchild;
-		nodep = allocchild;
+		stored_node = allocchild;
 		shift -= RT_NODE_SPAN;
 	}
 
-	RT_NODE_INSERT_LEAF(tree, parent, nodep, node, key, value);
+	RT_NODE_INSERT_LEAF(tree, parent, stored_node, node, key, value);
 	tree->ctl->num_keys++;
 }
 
@@ -1305,9 +1305,15 @@ RT_NODE_DELETE_LEAF(RT_PTR_LOCAL node, uint64 key)
 }
 #endif
 
-/* Insert the child to the inner node */
+/*
+ * Insert "child" into "node".
+ *
+ * "parent" is the parent of "node", so the grandparent of the child.
+ * 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
-RT_NODE_INSERT_INNER(RT_RADIX_TREE *tree, RT_PTR_LOCAL parent, RT_PTR_ALLOC nodep, RT_PTR_LOCAL node,
+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)
 {
 #define RT_NODE_LEVEL_INNER
@@ -1315,9 +1321,9 @@ RT_NODE_INSERT_INNER(RT_RADIX_TREE *tree, RT_PTR_LOCAL parent, RT_PTR_ALLOC node
 #undef RT_NODE_LEVEL_INNER
 }
 
-/* Insert the value to the leaf node */
+/* Like, RT_NODE_INSERT_INNER, but for leaf nodes */
 static bool
-RT_NODE_INSERT_LEAF(RT_RADIX_TREE *tree, RT_PTR_LOCAL parent, RT_PTR_ALLOC nodep, RT_PTR_LOCAL node,
+RT_NODE_INSERT_LEAF(RT_RADIX_TREE *tree, RT_PTR_LOCAL parent, RT_PTR_ALLOC stored_node, RT_PTR_LOCAL node,
 					uint64 key, uint64 value)
 {
 #define RT_NODE_LEVEL_LEAF
@@ -1525,8 +1531,8 @@ RT_SET(RT_RADIX_TREE *tree, uint64 key, uint64 value)
 	int			shift;
 	bool		updated;
 	RT_PTR_LOCAL parent;
-	RT_PTR_ALLOC nodep;
-	RT_PTR_LOCAL  node;
+	RT_PTR_ALLOC stored_child;
+	RT_PTR_LOCAL  child;
 
 #ifdef RT_SHMEM
 	Assert(tree->ctl->magic == RT_RADIX_TREE_MAGIC);
@@ -1540,32 +1546,32 @@ RT_SET(RT_RADIX_TREE *tree, uint64 key, uint64 value)
 	if (key > tree->ctl->max_val)
 		RT_EXTEND(tree, key);
 
-	nodep = tree->ctl->root;
-	parent = RT_PTR_GET_LOCAL(tree, nodep);
+	stored_child = tree->ctl->root;
+	parent = RT_PTR_GET_LOCAL(tree, stored_child);
 	shift = parent->shift;
 
 	/* Descend the tree until a leaf node */
 	while (shift >= 0)
 	{
-		RT_PTR_ALLOC child;
+		RT_PTR_ALLOC new_child;
 
-		node = RT_PTR_GET_LOCAL(tree, nodep);
+		child = RT_PTR_GET_LOCAL(tree, stored_child);
 
-		if (NODE_IS_LEAF(node))
+		if (NODE_IS_LEAF(child))
 			break;
 
-		if (!RT_NODE_SEARCH_INNER(node, key, &child))
+		if (!RT_NODE_SEARCH_INNER(child, key, &new_child))
 		{
-			RT_SET_EXTEND(tree, key, value, parent, nodep, node);
+			RT_SET_EXTEND(tree, key, value, parent, stored_child, child);
 			return false;
 		}
 
-		parent = node;
-		nodep = child;
+		parent = child;
+		stored_child = new_child;
 		shift -= RT_NODE_SPAN;
 	}
 
-	updated = RT_NODE_INSERT_LEAF(tree, parent, nodep, node, key, value);
+	updated = RT_NODE_INSERT_LEAF(tree, parent, stored_child, child, key, value);
 
 	/* Update the statistics */
 	if (!updated)
diff --git a/src/include/lib/radixtree_insert_impl.h b/src/include/lib/radixtree_insert_impl.h
index e4faf54d9d..1d0eb396e2 100644
--- a/src/include/lib/radixtree_insert_impl.h
+++ b/src/include/lib/radixtree_insert_impl.h
@@ -14,8 +14,6 @@
 
 	uint8		chunk = RT_GET_KEY_CHUNK(key, node->shift);
 	bool		chunk_exists = false;
-	RT_PTR_LOCAL newnode = NULL;
-	RT_PTR_ALLOC allocnode;
 
 #ifdef RT_NODE_LEVEL_LEAF
 	const bool inner = false;
@@ -47,6 +45,8 @@
 
 				if (unlikely(!VAR_NODE_HAS_FREE_SLOT(n4)))
 				{
+					RT_PTR_ALLOC allocnode;
+					RT_PTR_LOCAL newnode;
 					RT_NODE32_TYPE *new32;
 					const uint8 new_kind = RT_NODE_KIND_32;
 					const RT_SIZE_CLASS new_class = RT_KIND_MIN_SIZE_CLASS[new_kind];
@@ -65,8 +65,7 @@
 					RT_CHUNK_CHILDREN_ARRAY_COPY(n4->base.chunks, n4->children,
 											  new32->base.chunks, new32->children);
 #endif
-					Assert(parent != NULL);
-					RT_REPLACE_NODE(tree, parent, nodep, allocnode, key);
+					RT_REPLACE_NODE(tree, parent, stored_node, node, allocnode, key);
 					node = newnode;
 				}
 				else
@@ -121,6 +120,8 @@
 					n32->base.n.fanout == class32_min.fanout)
 				{
 					/* grow to the next size class of this kind */
+					RT_PTR_ALLOC allocnode;
+					RT_PTR_LOCAL newnode;
 					const RT_SIZE_CLASS new_class = RT_CLASS_32_FULL;
 
 					allocnode = RT_ALLOC_NODE(tree, new_class, inner);
@@ -132,8 +133,7 @@
 #endif
 					newnode->fanout = class32_max.fanout;
 
-					Assert(parent != NULL);
-					RT_REPLACE_NODE(tree, parent, nodep, allocnode, key);
+					RT_REPLACE_NODE(tree, parent, stored_node, node, allocnode, key);
 					node = newnode;
 
 					/* also update pointer for this kind */
@@ -142,6 +142,8 @@
 
 				if (unlikely(!VAR_NODE_HAS_FREE_SLOT(n32)))
 				{
+					RT_PTR_ALLOC allocnode;
+					RT_PTR_LOCAL newnode;
 					RT_NODE125_TYPE *new125;
 					const uint8 new_kind = RT_NODE_KIND_125;
 					const RT_SIZE_CLASS new_class = RT_KIND_MIN_SIZE_CLASS[new_kind];
@@ -169,8 +171,7 @@
 					Assert(class32_max.fanout <= sizeof(bitmapword) * BITS_PER_BYTE);
 					new125->base.isset[0] = (bitmapword) (((uint64) 1 << class32_max.fanout) - 1);
 
-					Assert(parent != NULL);
-					RT_REPLACE_NODE(tree, parent, nodep, allocnode, key);
+					RT_REPLACE_NODE(tree, parent, stored_node, node, allocnode, key);
 					node = newnode;
 				}
 				else
@@ -220,6 +221,8 @@
 
 				if (unlikely(!VAR_NODE_HAS_FREE_SLOT(n125)))
 				{
+					RT_PTR_ALLOC allocnode;
+					RT_PTR_LOCAL newnode;
 					RT_NODE256_TYPE *new256;
 					const uint8 new_kind = RT_NODE_KIND_256;
 					const RT_SIZE_CLASS new_class = RT_KIND_MIN_SIZE_CLASS[new_kind];
@@ -243,8 +246,7 @@
 						cnt++;
 					}
 
-					Assert(parent != NULL);
-					RT_REPLACE_NODE(tree, parent, nodep, allocnode, key);
+					RT_REPLACE_NODE(tree, parent, stored_node, node, allocnode, key);
 					node = newnode;
 				}
 				else
-- 
2.39.0