From d9f4b6280f73076df05c1fd03ca6860df3b90c74 Mon Sep 17 00:00:00 2001 From: John Naylor 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