v21-0009-Remove-hard-coded-128.patch

From 5b4fff91055335d5dcc22ae6eee26168cf889486 Mon Sep 17 00:00:00 2001
From: John Naylor <john.naylor@postgresql.org>
Date: Fri, 20 Jan 2023 15:51:21 +0700
Subject: [PATCH v21 09/22] Remove hard-coded 128

Also comment that 64 could be a valid number of bits
in the bitmap for this node type.

TODO: Consider whether we should in fact limit this
node to ~64.

In passing, remove "125" from invalid-slot-index macro.
---
 src/include/lib/radixtree.h             | 19 +++++++++++++------
 src/include/lib/radixtree_delete_impl.h |  4 ++--
 src/include/lib/radixtree_insert_impl.h |  4 ++--
 src/include/lib/radixtree_search_impl.h |  4 ++--
 4 files changed, 19 insertions(+), 12 deletions(-)

diff --git a/src/include/lib/radixtree.h b/src/include/lib/radixtree.h
index 172d62c6b0..d15ea8f0fe 100644
--- a/src/include/lib/radixtree.h
+++ b/src/include/lib/radixtree.h
@@ -270,8 +270,15 @@ RT_SCOPE void RT_STATS(RT_RADIX_TREE *tree);
 /* Tree level the radix tree uses */
 #define RT_MAX_LEVEL	((sizeof(uint64) * BITS_PER_BYTE) / RT_NODE_SPAN)
 
+/*
+ * Number of bits necessary for isset array in the slot-index node.
+ * Since bitmapword can be 64 bits, the only values that make sense
+ * here are 64 and 128.
+ */
+#define RT_SLOT_IDX_LIMIT (RT_NODE_MAX_SLOTS / 2)
+
 /* Invalid index used in node-125 */
-#define RT_NODE_125_INVALID_IDX	0xFF
+#define RT_INVALID_SLOT_IDX	0xFF
 
 /* Get a chunk from the key */
 #define RT_GET_KEY_CHUNK(key, shift) ((uint8) (((key) >> (shift)) & RT_CHUNK_MASK))
@@ -409,7 +416,7 @@ typedef struct RT_NODE_BASE_125
 	uint8		slot_idxs[RT_NODE_MAX_SLOTS];
 
 	/* isset is a bitmap to track which slot is in use */
-	bitmapword		isset[BM_IDX(128)];
+	bitmapword		isset[BM_IDX(RT_SLOT_IDX_LIMIT)];
 } RT_NODE_BASE_125;
 
 typedef struct RT_NODE_BASE_256
@@ -867,7 +874,7 @@ RT_CHUNK_VALUES_ARRAY_COPY(uint8 *src_chunks, RT_VALUE_TYPE *src_values,
 static inline bool
 RT_NODE_125_IS_CHUNK_USED(RT_NODE_BASE_125 *node, uint8 chunk)
 {
-	return node->slot_idxs[chunk] != RT_NODE_125_INVALID_IDX;
+	return node->slot_idxs[chunk] != RT_INVALID_SLOT_IDX;
 }
 
 static inline RT_PTR_ALLOC
@@ -881,7 +888,7 @@ static inline RT_VALUE_TYPE
 RT_NODE_LEAF_125_GET_VALUE(RT_NODE_LEAF_125 *node, uint8 chunk)
 {
 	Assert(NODE_IS_LEAF(node));
-	Assert(((RT_NODE_BASE_125 *) node)->slot_idxs[chunk] != RT_NODE_125_INVALID_IDX);
+	Assert(((RT_NODE_BASE_125 *) node)->slot_idxs[chunk] != RT_INVALID_SLOT_IDX);
 	return node->values[node->base.slot_idxs[chunk]];
 }
 
@@ -1037,7 +1044,7 @@ RT_INIT_NODE(RT_PTR_LOCAL node, uint8 kind, RT_SIZE_CLASS size_class, bool inner
 	{
 		RT_NODE_BASE_125 *n125 = (RT_NODE_BASE_125 *) node;
 
-		memset(n125->slot_idxs, RT_NODE_125_INVALID_IDX, sizeof(n125->slot_idxs));
+		memset(n125->slot_idxs, RT_INVALID_SLOT_IDX, sizeof(n125->slot_idxs));
 	}
 }
 
@@ -2052,7 +2059,7 @@ RT_DUMP_NODE(RT_PTR_LOCAL node, int level, bool recurse)
 					RT_NODE_LEAF_125 *n = (RT_NODE_LEAF_125 *) node;
 
 					fprintf(stderr, ", isset-bitmap:");
-					for (int i = 0; i < BM_IDX(128); i++)
+					for (int i = 0; i < BM_IDX(RT_SLOT_IDX_LIMIT); i++)
 					{
 						fprintf(stderr, UINT64_FORMAT_HEX " ", (uint64) n->base.isset[i]);
 					}
diff --git a/src/include/lib/radixtree_delete_impl.h b/src/include/lib/radixtree_delete_impl.h
index 2612730481..2f1c172672 100644
--- a/src/include/lib/radixtree_delete_impl.h
+++ b/src/include/lib/radixtree_delete_impl.h
@@ -65,13 +65,13 @@
 				int			idx;
 				int			bitnum;
 
-				if (slotpos == RT_NODE_125_INVALID_IDX)
+				if (slotpos == RT_INVALID_SLOT_IDX)
 					return false;
 
 				idx = BM_IDX(slotpos);
 				bitnum = BM_BIT(slotpos);
 				n125->base.isset[idx] &= ~((bitmapword) 1 << bitnum);
-				n125->base.slot_idxs[chunk] = RT_NODE_125_INVALID_IDX;
+				n125->base.slot_idxs[chunk] = RT_INVALID_SLOT_IDX;
 
 				break;
 			}
diff --git a/src/include/lib/radixtree_insert_impl.h b/src/include/lib/radixtree_insert_impl.h
index e3e44669ea..90fe5f539e 100644
--- a/src/include/lib/radixtree_insert_impl.h
+++ b/src/include/lib/radixtree_insert_impl.h
@@ -201,7 +201,7 @@
 				int			slotpos = n125->base.slot_idxs[chunk];
 				int			cnt = 0;
 
-				if (slotpos != RT_NODE_125_INVALID_IDX)
+				if (slotpos != RT_INVALID_SLOT_IDX)
 				{
 					/* found the existing chunk */
 					chunk_exists = true;
@@ -247,7 +247,7 @@
 					bitmapword	inverse;
 
 					/* get the first word with at least one bit not set */
-					for (idx = 0; idx < BM_IDX(128); idx++)
+					for (idx = 0; idx < BM_IDX(RT_SLOT_IDX_LIMIT); idx++)
 					{
 						if (n125->base.isset[idx] < ~((bitmapword) 0))
 							break;
diff --git a/src/include/lib/radixtree_search_impl.h b/src/include/lib/radixtree_search_impl.h
index 365abaa46d..d2bbdd2450 100644
--- a/src/include/lib/radixtree_search_impl.h
+++ b/src/include/lib/radixtree_search_impl.h
@@ -73,10 +73,10 @@
 				int			slotpos = n125->base.slot_idxs[chunk];
 
 #ifdef RT_ACTION_UPDATE
-				Assert(slotpos != RT_NODE_125_INVALID_IDX);
+				Assert(slotpos != RT_INVALID_SLOT_IDX);
 				n125->children[slotpos] = new_child;
 #else
-				if (slotpos == RT_NODE_125_INVALID_IDX)
+				if (slotpos == RT_INVALID_SLOT_IDX)
 					return false;
 
 #ifdef RT_NODE_LEVEL_LEAF
-- 
2.39.0