From 1226982cc3c3ac779953de4afb6e85f31be11a28 Mon Sep 17 00:00:00 2001 From: John Naylor Date: Fri, 20 Jan 2023 18:05:15 +0700 Subject: [PATCH v21 10/22] Reduce node4 to node3 Now that we don't store "chunk", the base node type is only 5 bytes in size. With 3 key chunks, There is no alignment padding between the chunks array and the child/value array. This reduces the smallest inner node to 32 bytes on 64-bit platforms. --- src/include/lib/radixtree.h | 124 ++++++++++++------------ src/include/lib/radixtree_delete_impl.h | 20 ++-- src/include/lib/radixtree_insert_impl.h | 38 ++++---- src/include/lib/radixtree_iter_impl.h | 18 ++-- src/include/lib/radixtree_search_impl.h | 18 ++-- 5 files changed, 109 insertions(+), 109 deletions(-) diff --git a/src/include/lib/radixtree.h b/src/include/lib/radixtree.h index d15ea8f0fe..6cc8442c89 100644 --- a/src/include/lib/radixtree.h +++ b/src/include/lib/radixtree.h @@ -136,9 +136,9 @@ #define RT_REPLACE_NODE RT_MAKE_NAME(replace_node) #define RT_PTR_GET_LOCAL RT_MAKE_NAME(ptr_get_local) #define RT_PTR_ALLOC_IS_VALID RT_MAKE_NAME(ptr_stored_is_valid) -#define RT_NODE_4_SEARCH_EQ RT_MAKE_NAME(node_4_search_eq) +#define RT_NODE_3_SEARCH_EQ RT_MAKE_NAME(node_3_search_eq) #define RT_NODE_32_SEARCH_EQ RT_MAKE_NAME(node_32_search_eq) -#define RT_NODE_4_GET_INSERTPOS RT_MAKE_NAME(node_4_get_insertpos) +#define RT_NODE_3_GET_INSERTPOS RT_MAKE_NAME(node_3_get_insertpos) #define RT_NODE_32_GET_INSERTPOS RT_MAKE_NAME(node_32_get_insertpos) #define RT_CHUNK_CHILDREN_ARRAY_SHIFT RT_MAKE_NAME(chunk_children_array_shift) #define RT_CHUNK_VALUES_ARRAY_SHIFT RT_MAKE_NAME(chunk_values_array_shift) @@ -181,22 +181,22 @@ #endif #define RT_NODE RT_MAKE_NAME(node) #define RT_NODE_ITER RT_MAKE_NAME(node_iter) -#define RT_NODE_BASE_4 RT_MAKE_NAME(node_base_4) +#define RT_NODE_BASE_3 RT_MAKE_NAME(node_base_3) #define RT_NODE_BASE_32 RT_MAKE_NAME(node_base_32) #define RT_NODE_BASE_125 RT_MAKE_NAME(node_base_125) #define RT_NODE_BASE_256 RT_MAKE_NAME(node_base_256) -#define RT_NODE_INNER_4 RT_MAKE_NAME(node_inner_4) +#define RT_NODE_INNER_3 RT_MAKE_NAME(node_inner_3) #define RT_NODE_INNER_32 RT_MAKE_NAME(node_inner_32) #define RT_NODE_INNER_125 RT_MAKE_NAME(node_inner_125) #define RT_NODE_INNER_256 RT_MAKE_NAME(node_inner_256) -#define RT_NODE_LEAF_4 RT_MAKE_NAME(node_leaf_4) +#define RT_NODE_LEAF_3 RT_MAKE_NAME(node_leaf_3) #define RT_NODE_LEAF_32 RT_MAKE_NAME(node_leaf_32) #define RT_NODE_LEAF_125 RT_MAKE_NAME(node_leaf_125) #define RT_NODE_LEAF_256 RT_MAKE_NAME(node_leaf_256) #define RT_SIZE_CLASS RT_MAKE_NAME(size_class) #define RT_SIZE_CLASS_ELEM RT_MAKE_NAME(size_class_elem) #define RT_SIZE_CLASS_INFO RT_MAKE_NAME(size_class_info) -#define RT_CLASS_4_FULL RT_MAKE_NAME(class_4_full) +#define RT_CLASS_3_FULL RT_MAKE_NAME(class_3_full) #define RT_CLASS_32_PARTIAL RT_MAKE_NAME(class_32_partial) #define RT_CLASS_32_FULL RT_MAKE_NAME(class_32_full) #define RT_CLASS_125_FULL RT_MAKE_NAME(class_125_full) @@ -305,7 +305,7 @@ RT_SCOPE void RT_STATS(RT_RADIX_TREE *tree); * allocator padding in both the inner and leaf nodes on DSA. * node */ -#define RT_NODE_KIND_4 0x00 +#define RT_NODE_KIND_3 0x00 #define RT_NODE_KIND_32 0x01 #define RT_NODE_KIND_125 0x02 #define RT_NODE_KIND_256 0x03 @@ -323,7 +323,7 @@ RT_SCOPE void RT_STATS(RT_RADIX_TREE *tree); typedef enum RT_SIZE_CLASS { - RT_CLASS_4_FULL = 0, + RT_CLASS_3_FULL = 0, RT_CLASS_32_PARTIAL, RT_CLASS_32_FULL, RT_CLASS_125_FULL, @@ -387,13 +387,13 @@ typedef struct RT_NODE /* Base type of each node kinds for leaf and inner nodes */ /* The base types must be a be able to accommodate the largest size class for variable-sized node kinds*/ -typedef struct RT_NODE_BASE_4 +typedef struct RT_NODE_BASE_3 { RT_NODE n; - /* 4 children, for key chunks */ - uint8 chunks[4]; -} RT_NODE_BASE_4; + /* 3 children, for key chunks */ + uint8 chunks[3]; +} RT_NODE_BASE_3; typedef struct RT_NODE_BASE_32 { @@ -437,21 +437,21 @@ typedef struct RT_NODE_BASE_256 * good. It might be better to just indicate non-existing entries the same way * in inner nodes. */ -typedef struct RT_NODE_INNER_4 +typedef struct RT_NODE_INNER_3 { - RT_NODE_BASE_4 base; + RT_NODE_BASE_3 base; /* number of children depends on size class */ RT_PTR_ALLOC children[FLEXIBLE_ARRAY_MEMBER]; -} RT_NODE_INNER_4; +} RT_NODE_INNER_3; -typedef struct RT_NODE_LEAF_4 +typedef struct RT_NODE_LEAF_3 { - RT_NODE_BASE_4 base; + RT_NODE_BASE_3 base; /* number of values depends on size class */ RT_VALUE_TYPE values[FLEXIBLE_ARRAY_MEMBER]; -} RT_NODE_LEAF_4; +} RT_NODE_LEAF_3; typedef struct RT_NODE_INNER_32 { @@ -520,11 +520,11 @@ typedef struct RT_SIZE_CLASS_ELEM } RT_SIZE_CLASS_ELEM; static const RT_SIZE_CLASS_ELEM RT_SIZE_CLASS_INFO[] = { - [RT_CLASS_4_FULL] = { - .name = "radix tree node 4", - .fanout = 4, - .inner_size = sizeof(RT_NODE_INNER_4) + 4 * sizeof(RT_PTR_ALLOC), - .leaf_size = sizeof(RT_NODE_LEAF_4) + 4 * sizeof(RT_VALUE_TYPE), + [RT_CLASS_3_FULL] = { + .name = "radix tree node 3", + .fanout = 3, + .inner_size = sizeof(RT_NODE_INNER_3) + 3 * sizeof(RT_PTR_ALLOC), + .leaf_size = sizeof(RT_NODE_LEAF_3) + 3 * sizeof(RT_VALUE_TYPE), }, [RT_CLASS_32_PARTIAL] = { .name = "radix tree node 15", @@ -556,7 +556,7 @@ static const RT_SIZE_CLASS_ELEM RT_SIZE_CLASS_INFO[] = { /* Map from the node kind to its minimum size class */ static const RT_SIZE_CLASS RT_KIND_MIN_SIZE_CLASS[RT_NODE_KIND_COUNT] = { - [RT_NODE_KIND_4] = RT_CLASS_4_FULL, + [RT_NODE_KIND_3] = RT_CLASS_3_FULL, [RT_NODE_KIND_32] = RT_CLASS_32_PARTIAL, [RT_NODE_KIND_125] = RT_CLASS_125_FULL, [RT_NODE_KIND_256] = RT_CLASS_256, @@ -673,7 +673,7 @@ RT_PTR_ALLOC_IS_VALID(RT_PTR_ALLOC ptr) * if there is no such element. */ static inline int -RT_NODE_4_SEARCH_EQ(RT_NODE_BASE_4 *node, uint8 chunk) +RT_NODE_3_SEARCH_EQ(RT_NODE_BASE_3 *node, uint8 chunk) { int idx = -1; @@ -693,7 +693,7 @@ RT_NODE_4_SEARCH_EQ(RT_NODE_BASE_4 *node, uint8 chunk) * Return index of the chunk to insert into chunks in the given node. */ static inline int -RT_NODE_4_GET_INSERTPOS(RT_NODE_BASE_4 *node, uint8 chunk) +RT_NODE_3_GET_INSERTPOS(RT_NODE_BASE_3 *node, uint8 chunk) { int idx; @@ -810,7 +810,7 @@ RT_NODE_32_GET_INSERTPOS(RT_NODE_BASE_32 *node, uint8 chunk) /* * Functions to manipulate both chunks array and children/values array. - * These are used for node-4 and node-32. + * These are used for node-3 and node-32. */ /* Shift the elements right at 'idx' by one */ @@ -848,7 +848,7 @@ static inline void RT_CHUNK_CHILDREN_ARRAY_COPY(uint8 *src_chunks, RT_PTR_ALLOC *src_children, uint8 *dst_chunks, RT_PTR_ALLOC *dst_children) { - const int fanout = RT_SIZE_CLASS_INFO[RT_CLASS_4_FULL].fanout; + const int fanout = RT_SIZE_CLASS_INFO[RT_CLASS_3_FULL].fanout; const Size chunk_size = sizeof(uint8) * fanout; const Size children_size = sizeof(RT_PTR_ALLOC) * fanout; @@ -860,7 +860,7 @@ static inline void RT_CHUNK_VALUES_ARRAY_COPY(uint8 *src_chunks, RT_VALUE_TYPE *src_values, uint8 *dst_chunks, RT_VALUE_TYPE *dst_values) { - const int fanout = RT_SIZE_CLASS_INFO[RT_CLASS_4_FULL].fanout; + const int fanout = RT_SIZE_CLASS_INFO[RT_CLASS_3_FULL].fanout; const Size chunk_size = sizeof(uint8) * fanout; const Size values_size = sizeof(RT_VALUE_TYPE) * fanout; @@ -1060,9 +1060,9 @@ RT_NEW_ROOT(RT_RADIX_TREE *tree, uint64 key) RT_PTR_ALLOC allocnode; RT_PTR_LOCAL newnode; - allocnode = RT_ALLOC_NODE(tree, RT_CLASS_4_FULL, inner); + allocnode = RT_ALLOC_NODE(tree, RT_CLASS_3_FULL, inner); newnode = RT_PTR_GET_LOCAL(tree, allocnode); - RT_INIT_NODE(newnode, RT_NODE_KIND_4, RT_CLASS_4_FULL, inner); + RT_INIT_NODE(newnode, RT_NODE_KIND_3, RT_CLASS_3_FULL, inner); newnode->shift = shift; tree->ctl->max_val = RT_SHIFT_GET_MAX_VAL(shift); tree->ctl->root = allocnode; @@ -1183,17 +1183,17 @@ RT_EXTEND(RT_RADIX_TREE *tree, uint64 key) { RT_PTR_ALLOC allocnode; RT_PTR_LOCAL node; - RT_NODE_INNER_4 *n4; + RT_NODE_INNER_3 *n3; - allocnode = RT_ALLOC_NODE(tree, RT_CLASS_4_FULL, true); + allocnode = RT_ALLOC_NODE(tree, RT_CLASS_3_FULL, true); node = RT_PTR_GET_LOCAL(tree, allocnode); - RT_INIT_NODE(node, RT_NODE_KIND_4, RT_CLASS_4_FULL, true); + RT_INIT_NODE(node, RT_NODE_KIND_3, RT_CLASS_3_FULL, true); node->shift = shift; node->count = 1; - n4 = (RT_NODE_INNER_4 *) node; - n4->base.chunks[0] = 0; - n4->children[0] = tree->ctl->root; + n3 = (RT_NODE_INNER_3 *) node; + n3->base.chunks[0] = 0; + n3->children[0] = tree->ctl->root; /* Update the root */ tree->ctl->root = allocnode; @@ -1223,9 +1223,9 @@ RT_SET_EXTEND(RT_RADIX_TREE *tree, uint64 key, RT_VALUE_TYPE value, RT_PTR_LOCAL int newshift = shift - RT_NODE_SPAN; bool inner = newshift > 0; - allocchild = RT_ALLOC_NODE(tree, RT_CLASS_4_FULL, inner); + allocchild = RT_ALLOC_NODE(tree, RT_CLASS_3_FULL, inner); newchild = RT_PTR_GET_LOCAL(tree, allocchild); - RT_INIT_NODE(newchild, RT_NODE_KIND_4, RT_CLASS_4_FULL, inner); + RT_INIT_NODE(newchild, RT_NODE_KIND_3, RT_CLASS_3_FULL, inner); newchild->shift = newshift; RT_NODE_INSERT_INNER(tree, parent, stored_node, node, key, allocchild); @@ -1430,12 +1430,12 @@ RT_FREE_RECURSE(RT_RADIX_TREE *tree, RT_PTR_ALLOC ptr) switch (node->kind) { - case RT_NODE_KIND_4: + case RT_NODE_KIND_3: { - RT_NODE_INNER_4 *n4 = (RT_NODE_INNER_4 *) node; + RT_NODE_INNER_3 *n3 = (RT_NODE_INNER_3 *) node; - for (int i = 0; i < n4->base.n.count; i++) - RT_FREE_RECURSE(tree, n4->children[i]); + for (int i = 0; i < n3->base.n.count; i++) + RT_FREE_RECURSE(tree, n3->children[i]); break; } @@ -1892,12 +1892,12 @@ RT_VERIFY_NODE(RT_PTR_LOCAL node) switch (node->kind) { - case RT_NODE_KIND_4: + case RT_NODE_KIND_3: { - RT_NODE_BASE_4 *n4 = (RT_NODE_BASE_4 *) node; + RT_NODE_BASE_3 *n3 = (RT_NODE_BASE_3 *) node; - for (int i = 1; i < n4->n.count; i++) - Assert(n4->chunks[i - 1] < n4->chunks[i]); + for (int i = 1; i < n3->n.count; i++) + Assert(n3->chunks[i - 1] < n3->chunks[i]); break; } @@ -1959,10 +1959,10 @@ RT_VERIFY_NODE(RT_PTR_LOCAL node) RT_SCOPE void RT_STATS(RT_RADIX_TREE *tree) { - ereport(NOTICE, (errmsg("num_keys = " UINT64_FORMAT ", height = %d, n4 = %u, n15 = %u, n32 = %u, n125 = %u, n256 = %u", + ereport(NOTICE, (errmsg("num_keys = " UINT64_FORMAT ", height = %d, n3 = %u, n15 = %u, n32 = %u, n125 = %u, n256 = %u", tree->ctl->num_keys, tree->ctl->root->shift / RT_NODE_SPAN, - tree->ctl->cnt[RT_CLASS_4_FULL], + tree->ctl->cnt[RT_CLASS_3_FULL], tree->ctl->cnt[RT_CLASS_32_PARTIAL], tree->ctl->cnt[RT_CLASS_32_FULL], tree->ctl->cnt[RT_CLASS_125_FULL], @@ -1977,7 +1977,7 @@ RT_DUMP_NODE(RT_PTR_LOCAL node, int level, bool recurse) fprintf(stderr, "[%s] kind %d, fanout %d, count %u, shift %u:\n", NODE_IS_LEAF(node) ? "LEAF" : "INNR", - (node->kind == RT_NODE_KIND_4) ? 4 : + (node->kind == RT_NODE_KIND_3) ? 3 : (node->kind == RT_NODE_KIND_32) ? 32 : (node->kind == RT_NODE_KIND_125) ? 125 : 256, node->fanout == 0 ? 256 : node->fanout, @@ -1988,26 +1988,26 @@ RT_DUMP_NODE(RT_PTR_LOCAL node, int level, bool recurse) switch (node->kind) { - case RT_NODE_KIND_4: + case RT_NODE_KIND_3: { for (int i = 0; i < node->count; i++) { if (NODE_IS_LEAF(node)) { - RT_NODE_LEAF_4 *n4 = (RT_NODE_LEAF_4 *) node; + RT_NODE_LEAF_3 *n3 = (RT_NODE_LEAF_3 *) node; fprintf(stderr, "%schunk 0x%X value 0x" UINT64_FORMAT_HEX "\n", - space, n4->base.chunks[i], (uint64) n4->values[i]); + space, n3->base.chunks[i], (uint64) n3->values[i]); } else { - RT_NODE_INNER_4 *n4 = (RT_NODE_INNER_4 *) node; + RT_NODE_INNER_3 *n3 = (RT_NODE_INNER_3 *) node; fprintf(stderr, "%schunk 0x%X ->", - space, n4->base.chunks[i]); + space, n3->base.chunks[i]); if (recurse) - RT_DUMP_NODE(n4->children[i], level + 1, recurse); + RT_DUMP_NODE(n3->children[i], level + 1, recurse); else fprintf(stderr, "\n"); } @@ -2229,22 +2229,22 @@ RT_DUMP(RT_RADIX_TREE *tree) #undef RT_ITER #undef RT_NODE #undef RT_NODE_ITER -#undef RT_NODE_BASE_4 +#undef RT_NODE_BASE_3 #undef RT_NODE_BASE_32 #undef RT_NODE_BASE_125 #undef RT_NODE_BASE_256 -#undef RT_NODE_INNER_4 +#undef RT_NODE_INNER_3 #undef RT_NODE_INNER_32 #undef RT_NODE_INNER_125 #undef RT_NODE_INNER_256 -#undef RT_NODE_LEAF_4 +#undef RT_NODE_LEAF_3 #undef RT_NODE_LEAF_32 #undef RT_NODE_LEAF_125 #undef RT_NODE_LEAF_256 #undef RT_SIZE_CLASS #undef RT_SIZE_CLASS_ELEM #undef RT_SIZE_CLASS_INFO -#undef RT_CLASS_4_FULL +#undef RT_CLASS_3_FULL #undef RT_CLASS_32_PARTIAL #undef RT_CLASS_32_FULL #undef RT_CLASS_125_FULL @@ -2282,9 +2282,9 @@ RT_DUMP(RT_RADIX_TREE *tree) #undef RT_REPLACE_NODE #undef RT_PTR_GET_LOCAL #undef RT_PTR_ALLOC_IS_VALID -#undef RT_NODE_4_SEARCH_EQ +#undef RT_NODE_3_SEARCH_EQ #undef RT_NODE_32_SEARCH_EQ -#undef RT_NODE_4_GET_INSERTPOS +#undef RT_NODE_3_GET_INSERTPOS #undef RT_NODE_32_GET_INSERTPOS #undef RT_CHUNK_CHILDREN_ARRAY_SHIFT #undef RT_CHUNK_VALUES_ARRAY_SHIFT diff --git a/src/include/lib/radixtree_delete_impl.h b/src/include/lib/radixtree_delete_impl.h index 2f1c172672..b9f07f4eb5 100644 --- a/src/include/lib/radixtree_delete_impl.h +++ b/src/include/lib/radixtree_delete_impl.h @@ -1,12 +1,12 @@ /* TODO: shrink nodes */ #if defined(RT_NODE_LEVEL_INNER) -#define RT_NODE4_TYPE RT_NODE_INNER_4 +#define RT_NODE3_TYPE RT_NODE_INNER_3 #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_NODE3_TYPE RT_NODE_LEAF_3 #define RT_NODE32_TYPE RT_NODE_LEAF_32 #define RT_NODE125_TYPE RT_NODE_LEAF_125 #define RT_NODE256_TYPE RT_NODE_LEAF_256 @@ -24,20 +24,20 @@ switch (node->kind) { - case RT_NODE_KIND_4: + case RT_NODE_KIND_3: { - RT_NODE4_TYPE *n4 = (RT_NODE4_TYPE *) node; - int idx = RT_NODE_4_SEARCH_EQ((RT_NODE_BASE_4 *) n4, chunk); + RT_NODE3_TYPE *n3 = (RT_NODE3_TYPE *) node; + int idx = RT_NODE_3_SEARCH_EQ((RT_NODE_BASE_3 *) n3, chunk); if (idx < 0) return false; #ifdef RT_NODE_LEVEL_LEAF - RT_CHUNK_VALUES_ARRAY_DELETE(n4->base.chunks, n4->values, - n4->base.n.count, idx); + RT_CHUNK_VALUES_ARRAY_DELETE(n3->base.chunks, n3->values, + n3->base.n.count, idx); #else - RT_CHUNK_CHILDREN_ARRAY_DELETE(n4->base.chunks, n4->children, - n4->base.n.count, idx); + RT_CHUNK_CHILDREN_ARRAY_DELETE(n3->base.chunks, n3->children, + n3->base.n.count, idx); #endif break; } @@ -100,7 +100,7 @@ return true; -#undef RT_NODE4_TYPE +#undef RT_NODE3_TYPE #undef RT_NODE32_TYPE #undef RT_NODE125_TYPE #undef RT_NODE256_TYPE diff --git a/src/include/lib/radixtree_insert_impl.h b/src/include/lib/radixtree_insert_impl.h index 90fe5f539e..16461bdb03 100644 --- a/src/include/lib/radixtree_insert_impl.h +++ b/src/include/lib/radixtree_insert_impl.h @@ -1,10 +1,10 @@ #if defined(RT_NODE_LEVEL_INNER) -#define RT_NODE4_TYPE RT_NODE_INNER_4 +#define RT_NODE3_TYPE RT_NODE_INNER_3 #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_NODE3_TYPE RT_NODE_LEAF_3 #define RT_NODE32_TYPE RT_NODE_LEAF_32 #define RT_NODE125_TYPE RT_NODE_LEAF_125 #define RT_NODE256_TYPE RT_NODE_LEAF_256 @@ -25,25 +25,25 @@ switch (node->kind) { - case RT_NODE_KIND_4: + case RT_NODE_KIND_3: { - RT_NODE4_TYPE *n4 = (RT_NODE4_TYPE *) node; + RT_NODE3_TYPE *n3 = (RT_NODE3_TYPE *) node; int idx; - idx = RT_NODE_4_SEARCH_EQ(&n4->base, chunk); + idx = RT_NODE_3_SEARCH_EQ(&n3->base, chunk); if (idx != -1) { /* found the existing chunk */ chunk_exists = true; #ifdef RT_NODE_LEVEL_LEAF - n4->values[idx] = value; + n3->values[idx] = value; #else - n4->children[idx] = child; + n3->children[idx] = child; #endif break; } - if (unlikely(!VAR_NODE_HAS_FREE_SLOT(n4))) + if (unlikely(!VAR_NODE_HAS_FREE_SLOT(n3))) { RT_PTR_ALLOC allocnode; RT_PTR_LOCAL newnode; @@ -51,16 +51,16 @@ const uint8 new_kind = RT_NODE_KIND_32; const RT_SIZE_CLASS new_class = RT_KIND_MIN_SIZE_CLASS[new_kind]; - /* grow node from 4 to 32 */ + /* grow node from 3 to 32 */ allocnode = RT_ALLOC_NODE(tree, new_class, inner); newnode = RT_SWITCH_NODE_KIND(tree, allocnode, node, new_kind, new_class, inner); new32 = (RT_NODE32_TYPE *) newnode; #ifdef RT_NODE_LEVEL_LEAF - RT_CHUNK_VALUES_ARRAY_COPY(n4->base.chunks, n4->values, + RT_CHUNK_VALUES_ARRAY_COPY(n3->base.chunks, n3->values, new32->base.chunks, new32->values); #else - RT_CHUNK_CHILDREN_ARRAY_COPY(n4->base.chunks, n4->children, + RT_CHUNK_CHILDREN_ARRAY_COPY(n3->base.chunks, n3->children, new32->base.chunks, new32->children); #endif RT_REPLACE_NODE(tree, parent, stored_node, node, allocnode, key); @@ -68,27 +68,27 @@ } else { - int insertpos = RT_NODE_4_GET_INSERTPOS(&n4->base, chunk); - int count = n4->base.n.count; + int insertpos = RT_NODE_3_GET_INSERTPOS(&n3->base, chunk); + int count = n3->base.n.count; /* shift chunks and children */ if (insertpos < count) { Assert(count > 0); #ifdef RT_NODE_LEVEL_LEAF - RT_CHUNK_VALUES_ARRAY_SHIFT(n4->base.chunks, n4->values, + RT_CHUNK_VALUES_ARRAY_SHIFT(n3->base.chunks, n3->values, count, insertpos); #else - RT_CHUNK_CHILDREN_ARRAY_SHIFT(n4->base.chunks, n4->children, + RT_CHUNK_CHILDREN_ARRAY_SHIFT(n3->base.chunks, n3->children, count, insertpos); #endif } - n4->base.chunks[insertpos] = chunk; + n3->base.chunks[insertpos] = chunk; #ifdef RT_NODE_LEVEL_LEAF - n4->values[insertpos] = value; + n3->values[insertpos] = value; #else - n4->children[insertpos] = child; + n3->children[insertpos] = child; #endif break; } @@ -304,7 +304,7 @@ return chunk_exists; -#undef RT_NODE4_TYPE +#undef RT_NODE3_TYPE #undef RT_NODE32_TYPE #undef RT_NODE125_TYPE #undef RT_NODE256_TYPE diff --git a/src/include/lib/radixtree_iter_impl.h b/src/include/lib/radixtree_iter_impl.h index 5c06f8b414..c428531438 100644 --- a/src/include/lib/radixtree_iter_impl.h +++ b/src/include/lib/radixtree_iter_impl.h @@ -1,10 +1,10 @@ #if defined(RT_NODE_LEVEL_INNER) -#define RT_NODE4_TYPE RT_NODE_INNER_4 +#define RT_NODE3_TYPE RT_NODE_INNER_3 #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_NODE3_TYPE RT_NODE_LEAF_3 #define RT_NODE32_TYPE RT_NODE_LEAF_32 #define RT_NODE125_TYPE RT_NODE_LEAF_125 #define RT_NODE256_TYPE RT_NODE_LEAF_256 @@ -31,19 +31,19 @@ switch (node_iter->node->kind) { - case RT_NODE_KIND_4: + case RT_NODE_KIND_3: { - RT_NODE4_TYPE *n4 = (RT_NODE4_TYPE *) node_iter->node; + RT_NODE3_TYPE *n3 = (RT_NODE3_TYPE *) node_iter->node; node_iter->current_idx++; - if (node_iter->current_idx >= n4->base.n.count) + if (node_iter->current_idx >= n3->base.n.count) break; #ifdef RT_NODE_LEVEL_LEAF - value = n4->values[node_iter->current_idx]; + value = n3->values[node_iter->current_idx]; #else - child = RT_PTR_GET_LOCAL(iter->tree, n4->children[node_iter->current_idx]); + child = RT_PTR_GET_LOCAL(iter->tree, n3->children[node_iter->current_idx]); #endif - key_chunk = n4->base.chunks[node_iter->current_idx]; + key_chunk = n3->base.chunks[node_iter->current_idx]; found = true; break; } @@ -132,7 +132,7 @@ return child; #endif -#undef RT_NODE4_TYPE +#undef RT_NODE3_TYPE #undef RT_NODE32_TYPE #undef RT_NODE125_TYPE #undef RT_NODE256_TYPE diff --git a/src/include/lib/radixtree_search_impl.h b/src/include/lib/radixtree_search_impl.h index d2bbdd2450..31138b6a72 100644 --- a/src/include/lib/radixtree_search_impl.h +++ b/src/include/lib/radixtree_search_impl.h @@ -1,10 +1,10 @@ #if defined(RT_NODE_LEVEL_INNER) -#define RT_NODE4_TYPE RT_NODE_INNER_4 +#define RT_NODE3_TYPE RT_NODE_INNER_3 #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_NODE3_TYPE RT_NODE_LEAF_3 #define RT_NODE32_TYPE RT_NODE_LEAF_32 #define RT_NODE125_TYPE RT_NODE_LEAF_125 #define RT_NODE256_TYPE RT_NODE_LEAF_256 @@ -27,22 +27,22 @@ switch (node->kind) { - case RT_NODE_KIND_4: + case RT_NODE_KIND_3: { - RT_NODE4_TYPE *n4 = (RT_NODE4_TYPE *) node; - int idx = RT_NODE_4_SEARCH_EQ((RT_NODE_BASE_4 *) n4, chunk); + RT_NODE3_TYPE *n3 = (RT_NODE3_TYPE *) node; + int idx = RT_NODE_3_SEARCH_EQ((RT_NODE_BASE_3 *) n3, chunk); #ifdef RT_ACTION_UPDATE Assert(idx >= 0); - n4->children[idx] = new_child; + n3->children[idx] = new_child; #else if (idx < 0) return false; #ifdef RT_NODE_LEVEL_LEAF - value = n4->values[idx]; + value = n3->values[idx]; #else - child = n4->children[idx]; + child = n3->children[idx]; #endif #endif /* RT_ACTION_UPDATE */ break; @@ -125,7 +125,7 @@ return true; #endif /* RT_ACTION_UPDATE */ -#undef RT_NODE4_TYPE +#undef RT_NODE3_TYPE #undef RT_NODE32_TYPE #undef RT_NODE125_TYPE #undef RT_NODE256_TYPE -- 2.39.0