From 624fd0577546a746f0538b98ab7456adc4ca1bd5 Mon Sep 17 00:00:00 2001 From: Masahiko Sawada Date: Mon, 14 Nov 2022 11:44:17 +0900 Subject: [PATCH v9 4/6] PoC: tag the node kind to rt_pointer. --- src/backend/lib/radixtree.c | 660 ++++++++++++++++++++---------------- 1 file changed, 375 insertions(+), 285 deletions(-) diff --git a/src/backend/lib/radixtree.c b/src/backend/lib/radixtree.c index bd58b2bfad..c25d455d2a 100644 --- a/src/backend/lib/radixtree.c +++ b/src/backend/lib/radixtree.c @@ -126,6 +126,23 @@ typedef enum #define RT_NODE_KIND_128 0x02 #define RT_NODE_KIND_256 0x03 #define RT_NODE_KIND_COUNT 4 +#define RT_POINTER_KIND_MASK 0x03 + +/* + * rt_pointer is a tagged pointer for rt_node. It is encoded from a + * C-pointer (ie, local memory address) and the node kind. The node + * kind uses the lower 2 bits, which are always 0 in local memory address. + * We can encode and decode the pointer using by rt_pointer_decode() + * and rt_pointer_encode() functions, respectively. + * + * The inner nodes of the radix tree need to store rt_pointer rather than + * C-pointer for the above reason. + */ +typedef uintptr_t rt_pointer; +#define InvalidRTPointer ((rt_pointer) 0) +#define RTPointerIsValid(x) (((rt_pointer) (x)) != InvalidRTPointer) +#define RTPointerTagKind(x, k) ((rt_pointer) (x) | ((k) & RT_POINTER_KIND_MASK)) +#define RTPointerUnTagKind(x) ((rt_pointer) (x) & ~RT_POINTER_KIND_MASK) /* Common type for all nodes types */ typedef struct rt_node @@ -144,13 +161,12 @@ typedef struct rt_node uint8 shift; uint8 chunk; - /* Size kind of the node */ - uint8 kind; + /* + * The node kind is tagged into the rt_pointer, see the comments of + * rt_pointer for details. + */ } rt_node; -#define NODE_IS_LEAF(n) (((rt_node *) (n))->shift == 0) -#define NODE_IS_EMPTY(n) (((rt_node *) (n))->count == 0) -#define NODE_HAS_FREE_SLOT(n) \ - (((rt_node *) (n))->count < rt_node_kind_info[((rt_node *) (n))->kind].fanout) +#define RT_NODE_IS_LEAF(n) (((rt_node *) (n))->shift == 0) /* Base type of each node kinds for leaf and inner nodes */ typedef struct rt_node_base_4 @@ -205,7 +221,7 @@ typedef struct rt_node_inner_4 rt_node_base_4 base; /* 4 children, for key chunks */ - rt_node *children[4]; + rt_pointer children[4]; } rt_node_inner_4; typedef struct rt_node_leaf_4 @@ -221,7 +237,7 @@ typedef struct rt_node_inner_32 rt_node_base_32 base; /* 32 children, for key chunks */ - rt_node *children[32]; + rt_pointer children[32]; } rt_node_inner_32; typedef struct rt_node_leaf_32 @@ -237,7 +253,7 @@ typedef struct rt_node_inner_128 rt_node_base_128 base; /* Slots for 128 children */ - rt_node *children[128]; + rt_pointer children[128]; } rt_node_inner_128; typedef struct rt_node_leaf_128 @@ -260,7 +276,7 @@ typedef struct rt_node_inner_256 rt_node_base_256 base; /* Slots for 256 children */ - rt_node *children[RT_NODE_MAX_SLOTS]; + rt_pointer children[RT_NODE_MAX_SLOTS]; } rt_node_inner_256; typedef struct rt_node_leaf_256 @@ -274,6 +290,30 @@ typedef struct rt_node_leaf_256 uint64 values[RT_NODE_MAX_SLOTS]; } rt_node_leaf_256; +/* + * rt_node_ptr is an useful data structure representing a pointer for a rt_node. + */ +typedef struct rt_node_ptr +{ + rt_pointer encoded; + rt_node *decoded; +} rt_node_ptr; +#define InvalidRTNodePtr \ + (rt_node_ptr) {.encoded = InvalidRTPointer, .decoded = NULL } +#define RTNodePtrIsValid(n) \ + (!rt_node_ptr_eq((rt_node_ptr *) &(n), &(InvalidRTNodePtr))) + +/* Macros for rt_node_ptr to access the fields of rt_node */ +#define NODE_RAW(n) (((rt_node_ptr) (n)).decoded) +#define NODE_IS_LEAF(n) (NODE_RAW(n)->shift == 0) +#define NODE_IS_EMPTY(n) (NODE_COUNT(n) == 0) +#define NODE_KIND(n) ((uint8) (((rt_node_ptr) (n)).encoded & RT_POINTER_KIND_MASK)) +#define NODE_COUNT(n) (NODE_RAW(n)->count) +#define NODE_SHIFT(n) (NODE_RAW(n)->shift) +#define NODE_CHUNK(n) (NODE_RAW(n)->chunk) +#define NODE_HAS_FREE_SLOT(n) \ + (NODE_COUNT(n) < rt_node_kind_info[NODE_KIND(n)].fanout) + /* Information of each size kinds */ typedef struct rt_node_kind_info_elem { @@ -347,7 +387,7 @@ static rt_node_kind_info_elem rt_node_kind_info[RT_NODE_KIND_COUNT] = { */ typedef struct rt_node_iter { - rt_node *node; /* current node being iterated */ + rt_node_ptr node; /* current node being iterated */ int current_idx; /* current position. -1 for initial value */ } rt_node_iter; @@ -368,7 +408,7 @@ struct radix_tree { MemoryContext context; - rt_node *root; + rt_pointer root; uint64 max_val; uint64 num_keys; @@ -382,26 +422,56 @@ struct radix_tree }; static void rt_new_root(radix_tree *tree, uint64 key); -static rt_node *rt_alloc_node(radix_tree *tree, int kind, uint8 shift, uint8 chunk, - bool inner); -static void rt_free_node(radix_tree *tree, rt_node *node); +static rt_node_ptr rt_alloc_node(radix_tree *tree, int kind, uint8 shift, uint8 chunk, + bool inner); +static void rt_free_node(radix_tree *tree, rt_node_ptr node); static void rt_extend(radix_tree *tree, uint64 key); -static inline bool rt_node_search_inner(rt_node *node, uint64 key, rt_action action, - rt_node **child_p); -static inline bool rt_node_search_leaf(rt_node *node, uint64 key, rt_action action, +static inline bool rt_node_search_inner(rt_node_ptr node_ptr, uint64 key, rt_action action, + rt_pointer *child_p); +static inline bool rt_node_search_leaf(rt_node_ptr node_ptr, uint64 key, rt_action action, uint64 *value_p); -static bool rt_node_insert_inner(radix_tree *tree, rt_node *parent, rt_node *node, - uint64 key, rt_node *child); -static bool rt_node_insert_leaf(radix_tree *tree, rt_node *parent, rt_node *node, +static bool rt_node_insert_inner(radix_tree *tree, rt_node_ptr parent, rt_node_ptr node, + uint64 key, rt_node_ptr child); +static bool rt_node_insert_leaf(radix_tree *tree, rt_node_ptr parent, rt_node_ptr node, uint64 key, uint64 value); -static inline rt_node *rt_node_inner_iterate_next(rt_iter *iter, rt_node_iter *node_iter); +static inline bool rt_node_inner_iterate_next(rt_iter *iter, rt_node_iter *node_iter, + rt_node_ptr *child_p); static inline bool rt_node_leaf_iterate_next(rt_iter *iter, rt_node_iter *node_iter, uint64 *value_p); -static void rt_update_iter_stack(rt_iter *iter, rt_node *from_node, int from); +static void rt_update_iter_stack(rt_iter *iter, rt_node_ptr from_node, int from); static inline void rt_iter_update_key(rt_iter *iter, uint8 chunk, uint8 shift); /* verification (available only with assertion) */ -static void rt_verify_node(rt_node *node); +static void rt_verify_node(rt_node_ptr node); + +/* Decode and encode function of rt_pointer */ +static inline rt_node * +rt_pointer_decode(rt_pointer encoded) +{ + return (rt_node *) RTPointerUnTagKind(encoded); +} + +static inline rt_pointer +rt_pointer_encode(rt_node *decoded, uint8 kind) +{ + return (rt_pointer) RTPointerTagKind(decoded, kind); +} + +/* Return a rt_pointer created from the given encoded pointer */ +static inline rt_node_ptr +rt_node_ptr_encoded(rt_pointer encoded) +{ + return (rt_node_ptr) { + .encoded = encoded, + .decoded = rt_pointer_decode(encoded) + }; +} + +static inline bool +rt_node_ptr_eq(rt_node_ptr *a, rt_node_ptr *b) +{ + return (a->decoded == b->decoded) && (a->encoded == b->encoded); +} /* * Return index of the first element in 'base' that equals 'key'. Return -1 @@ -550,10 +620,10 @@ node_32_get_insertpos(rt_node_base_32 *node, uint8 chunk) /* Shift the elements right at 'idx' by one */ static inline void -chunk_children_array_shift(uint8 *chunks, rt_node **children, int count, int idx) +chunk_children_array_shift(uint8 *chunks, rt_pointer *children, int count, int idx) { memmove(&(chunks[idx + 1]), &(chunks[idx]), sizeof(uint8) * (count - idx)); - memmove(&(children[idx + 1]), &(children[idx]), sizeof(rt_node *) * (count - idx)); + memmove(&(children[idx + 1]), &(children[idx]), sizeof(rt_pointer) * (count - idx)); } static inline void @@ -565,10 +635,10 @@ chunk_values_array_shift(uint8 *chunks, uint64 *values, int count, int idx) /* Delete the element at 'idx' */ static inline void -chunk_children_array_delete(uint8 *chunks, rt_node **children, int count, int idx) +chunk_children_array_delete(uint8 *chunks, rt_pointer *children, int count, int idx) { memmove(&(chunks[idx]), &(chunks[idx + 1]), sizeof(uint8) * (count - idx - 1)); - memmove(&(children[idx]), &(children[idx + 1]), sizeof(rt_node *) * (count - idx - 1)); + memmove(&(children[idx]), &(children[idx + 1]), sizeof(rt_pointer) * (count - idx - 1)); } static inline void @@ -580,15 +650,15 @@ chunk_values_array_delete(uint8 *chunks, uint64 *values, int count, int idx) /* Copy both chunks and children/values arrays */ static inline void -chunk_children_array_copy(uint8 *src_chunks, rt_node **src_children, - uint8 *dst_chunks, rt_node **dst_children, int count) +chunk_children_array_copy(uint8 *src_chunks, rt_pointer *src_children, + uint8 *dst_chunks, rt_pointer *dst_children, int count) { /* For better code generation */ if (count > rt_node_kind_info[RT_NODE_KIND_4].fanout) pg_unreachable(); memcpy(dst_chunks, src_chunks, sizeof(uint8) * count); - memcpy(dst_children, src_children, sizeof(rt_node *) * count); + memcpy(dst_children, src_children, sizeof(rt_pointer) * count); } static inline void @@ -616,28 +686,28 @@ node_128_is_chunk_used(rt_node_base_128 *node, uint8 chunk) static inline bool node_inner_128_is_slot_used(rt_node_inner_128 *node, uint8 slot) { - Assert(!NODE_IS_LEAF(node)); - return (node->children[slot] != NULL); + Assert(!RT_NODE_IS_LEAF(node)); + return RTPointerIsValid(node->children[slot]); } static inline bool node_leaf_128_is_slot_used(rt_node_leaf_128 *node, uint8 slot) { - Assert(NODE_IS_LEAF(node)); + Assert(RT_NODE_IS_LEAF(node)); return ((node->isset[RT_NODE_BITMAP_BYTE(slot)] & RT_NODE_BITMAP_BIT(slot)) != 0); } -static inline rt_node * +static inline rt_pointer node_inner_128_get_child(rt_node_inner_128 *node, uint8 chunk) { - Assert(!NODE_IS_LEAF(node)); + Assert(!RT_NODE_IS_LEAF(node)); return node->children[node->base.slot_idxs[chunk]]; } static inline uint64 node_leaf_128_get_value(rt_node_leaf_128 *node, uint8 chunk) { - Assert(NODE_IS_LEAF(node)); + Assert(RT_NODE_IS_LEAF(node)); Assert(((rt_node_base_128 *) node)->slot_idxs[chunk] != RT_NODE_128_INVALID_IDX); return node->values[node->base.slot_idxs[chunk]]; } @@ -645,7 +715,7 @@ node_leaf_128_get_value(rt_node_leaf_128 *node, uint8 chunk) static void node_inner_128_delete(rt_node_inner_128 *node, uint8 chunk) { - Assert(!NODE_IS_LEAF(node)); + Assert(!RT_NODE_IS_LEAF(node)); node->base.slot_idxs[chunk] = RT_NODE_128_INVALID_IDX; } @@ -654,7 +724,7 @@ node_leaf_128_delete(rt_node_leaf_128 *node, uint8 chunk) { int slotpos = node->base.slot_idxs[chunk]; - Assert(NODE_IS_LEAF(node)); + Assert(RT_NODE_IS_LEAF(node)); node->isset[RT_NODE_BITMAP_BYTE(slotpos)] &= ~(RT_NODE_BITMAP_BIT(slotpos)); node->base.slot_idxs[chunk] = RT_NODE_128_INVALID_IDX; } @@ -665,7 +735,7 @@ node_inner_128_find_unused_slot(rt_node_inner_128 *node, uint8 chunk) { int slotpos = 0; - Assert(!NODE_IS_LEAF(node)); + Assert(!RT_NODE_IS_LEAF(node)); while (node_inner_128_is_slot_used(node, slotpos)) slotpos++; @@ -677,7 +747,7 @@ node_leaf_128_find_unused_slot(rt_node_leaf_128 *node, uint8 chunk) { int slotpos; - Assert(NODE_IS_LEAF(node)); + Assert(RT_NODE_IS_LEAF(node)); /* We iterate over the isset bitmap per byte then check each bit */ for (slotpos = 0; slotpos < RT_NODE_NSLOTS_BITS(128); slotpos++) @@ -695,11 +765,11 @@ node_leaf_128_find_unused_slot(rt_node_leaf_128 *node, uint8 chunk) } static inline void -node_inner_128_insert(rt_node_inner_128 *node, uint8 chunk, rt_node *child) +node_inner_128_insert(rt_node_inner_128 *node, uint8 chunk, rt_pointer child) { int slotpos; - Assert(!NODE_IS_LEAF(node)); + Assert(!RT_NODE_IS_LEAF(node)); /* find unused slot */ slotpos = node_inner_128_find_unused_slot(node, chunk); @@ -714,7 +784,7 @@ node_leaf_128_insert(rt_node_leaf_128 *node, uint8 chunk, uint64 value) { int slotpos; - Assert(NODE_IS_LEAF(node)); + Assert(RT_NODE_IS_LEAF(node)); /* find unused slot */ slotpos = node_leaf_128_find_unused_slot(node, chunk); @@ -726,16 +796,16 @@ node_leaf_128_insert(rt_node_leaf_128 *node, uint8 chunk, uint64 value) /* Update the child corresponding to 'chunk' to 'child' */ static inline void -node_inner_128_update(rt_node_inner_128 *node, uint8 chunk, rt_node *child) +node_inner_128_update(rt_node_inner_128 *node, uint8 chunk, rt_pointer child) { - Assert(!NODE_IS_LEAF(node)); + Assert(!RT_NODE_IS_LEAF(node)); node->children[node->base.slot_idxs[chunk]] = child; } static inline void node_leaf_128_update(rt_node_leaf_128 *node, uint8 chunk, uint64 value) { - Assert(NODE_IS_LEAF(node)); + Assert(RT_NODE_IS_LEAF(node)); node->values[node->base.slot_idxs[chunk]] = value; } @@ -745,21 +815,21 @@ node_leaf_128_update(rt_node_leaf_128 *node, uint8 chunk, uint64 value) static inline bool node_inner_256_is_chunk_used(rt_node_inner_256 *node, uint8 chunk) { - Assert(!NODE_IS_LEAF(node)); - return (node->children[chunk] != NULL); + Assert(!RT_NODE_IS_LEAF(node)); + return RTPointerIsValid(node->children[chunk]); } static inline bool node_leaf_256_is_chunk_used(rt_node_leaf_256 *node, uint8 chunk) { - Assert(NODE_IS_LEAF(node)); + Assert(RT_NODE_IS_LEAF(node)); return (node->isset[RT_NODE_BITMAP_BYTE(chunk)] & RT_NODE_BITMAP_BIT(chunk)) != 0; } -static inline rt_node * +static inline rt_pointer node_inner_256_get_child(rt_node_inner_256 *node, uint8 chunk) { - Assert(!NODE_IS_LEAF(node)); + Assert(!RT_NODE_IS_LEAF(node)); Assert(node_inner_256_is_chunk_used(node, chunk)); return node->children[chunk]; } @@ -767,16 +837,16 @@ node_inner_256_get_child(rt_node_inner_256 *node, uint8 chunk) static inline uint64 node_leaf_256_get_value(rt_node_leaf_256 *node, uint8 chunk) { - Assert(NODE_IS_LEAF(node)); + Assert(RT_NODE_IS_LEAF(node)); Assert(node_leaf_256_is_chunk_used(node, chunk)); return node->values[chunk]; } /* Set the child in the node-256 */ static inline void -node_inner_256_set(rt_node_inner_256 *node, uint8 chunk, rt_node *child) +node_inner_256_set(rt_node_inner_256 *node, uint8 chunk, rt_pointer child) { - Assert(!NODE_IS_LEAF(node)); + Assert(!RT_NODE_IS_LEAF(node)); node->children[chunk] = child; } @@ -784,7 +854,7 @@ node_inner_256_set(rt_node_inner_256 *node, uint8 chunk, rt_node *child) static inline void node_leaf_256_set(rt_node_leaf_256 *node, uint8 chunk, uint64 value) { - Assert(NODE_IS_LEAF(node)); + Assert(RT_NODE_IS_LEAF(node)); node->isset[RT_NODE_BITMAP_BYTE(chunk)] |= RT_NODE_BITMAP_BIT(chunk); node->values[chunk] = value; } @@ -793,14 +863,14 @@ node_leaf_256_set(rt_node_leaf_256 *node, uint8 chunk, uint64 value) static inline void node_inner_256_delete(rt_node_inner_256 *node, uint8 chunk) { - Assert(!NODE_IS_LEAF(node)); - node->children[chunk] = NULL; + Assert(!RT_NODE_IS_LEAF(node)); + node->children[chunk] = InvalidRTPointer; } static inline void node_leaf_256_delete(rt_node_leaf_256 *node, uint8 chunk) { - Assert(NODE_IS_LEAF(node)); + Assert(RT_NODE_IS_LEAF(node)); node->isset[RT_NODE_BITMAP_BYTE(chunk)] &= ~(RT_NODE_BITMAP_BIT(chunk)); } @@ -835,37 +905,36 @@ static void rt_new_root(radix_tree *tree, uint64 key) { int shift = key_get_shift(key); - rt_node *node; + rt_node_ptr node; - node = (rt_node *) rt_alloc_node(tree, RT_NODE_KIND_4, shift, 0, - shift > 0); + node = rt_alloc_node(tree, RT_NODE_KIND_4, shift, 0, shift > 0); tree->max_val = shift_get_max_val(shift); - tree->root = node; + tree->root = node.encoded; } /* * Allocate a new node with the given node kind. */ -static rt_node * +static rt_node_ptr rt_alloc_node(radix_tree *tree, int kind, uint8 shift, uint8 chunk, bool inner) { - rt_node *newnode; + rt_node_ptr newnode; if (inner) - newnode = (rt_node *) MemoryContextAllocZero(tree->inner_slabs[kind], - rt_node_kind_info[kind].inner_size); + newnode.decoded = (rt_node *) MemoryContextAllocZero(tree->inner_slabs[kind], + rt_node_kind_info[kind].inner_size); else - newnode = (rt_node *) MemoryContextAllocZero(tree->leaf_slabs[kind], - rt_node_kind_info[kind].leaf_size); + newnode.decoded = (rt_node *) MemoryContextAllocZero(tree->leaf_slabs[kind], + rt_node_kind_info[kind].leaf_size); - newnode->kind = kind; - newnode->shift = shift; - newnode->chunk = chunk; + newnode.encoded = rt_pointer_encode(newnode.decoded, kind); + NODE_SHIFT(newnode) = shift; + NODE_CHUNK(newnode) = chunk; /* Initialize slot_idxs to invalid values */ if (kind == RT_NODE_KIND_128) { - rt_node_base_128 *n128 = (rt_node_base_128 *) newnode; + rt_node_base_128 *n128 = (rt_node_base_128 *) newnode.decoded; memset(n128->slot_idxs, RT_NODE_128_INVALID_IDX, sizeof(n128->slot_idxs)); } @@ -882,55 +951,56 @@ rt_alloc_node(radix_tree *tree, int kind, uint8 shift, uint8 chunk, bool inner) * Create a new node with 'new_kind' and the same shift, chunk, and * count of 'node'. */ -static rt_node * -rt_copy_node(radix_tree *tree, rt_node *node, int new_kind) +static rt_node_ptr +rt_copy_node(radix_tree *tree, rt_node_ptr node, int new_kind) { - rt_node *newnode; + rt_node_ptr newnode; + rt_node *n = node.decoded; - newnode = rt_alloc_node(tree, new_kind, node->shift, node->chunk, - node->shift > 0); - newnode->count = node->count; + newnode = rt_alloc_node(tree, new_kind, n->shift, n->chunk, n->shift > 0); + NODE_COUNT(newnode) = NODE_COUNT(node); return newnode; } /* Free the given node */ static void -rt_free_node(radix_tree *tree, rt_node *node) +rt_free_node(radix_tree *tree, rt_node_ptr node) { /* If we're deleting the root node, make the tree empty */ - if (tree->root == node) - tree->root = NULL; + if (tree->root == node.encoded) + tree->root = InvalidRTPointer; #ifdef RT_DEBUG /* update the statistics */ - tree->cnt[node->kind]--; - Assert(tree->cnt[node->kind] >= 0); + tree->cnt[NODE_KIND(node)]--; + Assert(tree->cnt[NODE_KIND(node)] >= 0); #endif - pfree(node); + pfree(node.decoded); } /* * Replace old_child with new_child, and free the old one. */ static void -rt_replace_node(radix_tree *tree, rt_node *parent, rt_node *old_child, - rt_node *new_child, uint64 key) +rt_replace_node(radix_tree *tree, rt_node_ptr parent, rt_node_ptr old_child, + rt_node_ptr new_child, uint64 key) { - Assert(old_child->chunk == new_child->chunk); - Assert(old_child->shift == new_child->shift); + Assert(NODE_CHUNK(old_child) == NODE_CHUNK(new_child)); + Assert(NODE_SHIFT(old_child) == NODE_SHIFT(new_child)); - if (parent == old_child) + if (rt_node_ptr_eq(&parent, &old_child)) { /* Replace the root node with the new large node */ - tree->root = new_child; + tree->root = new_child.encoded; } else { bool replaced PG_USED_FOR_ASSERTS_ONLY; - replaced = rt_node_insert_inner(tree, NULL, parent, key, new_child); + replaced = rt_node_insert_inner(tree, InvalidRTNodePtr, parent, key, + new_child); Assert(replaced); } @@ -945,23 +1015,26 @@ static void rt_extend(radix_tree *tree, uint64 key) { int target_shift; - int shift = tree->root->shift + RT_NODE_SPAN; + rt_node *root = rt_pointer_decode(tree->root); + int shift = root->shift + RT_NODE_SPAN; target_shift = key_get_shift(key); /* Grow tree from 'shift' to 'target_shift' */ while (shift <= target_shift) { - rt_node_inner_4 *node; + rt_node_ptr node; + rt_node_inner_4 *n4; + + node = rt_alloc_node(tree, RT_NODE_KIND_4, shift, 0, true); + n4 = (rt_node_inner_4 *) node.decoded; - node = (rt_node_inner_4 *) rt_alloc_node(tree, RT_NODE_KIND_4, - shift, 0, true); - node->base.n.count = 1; - node->base.chunks[0] = 0; - node->children[0] = tree->root; + n4->base.n.count = 1; + n4->base.chunks[0] = 0; + n4->children[0] = tree->root; - tree->root->chunk = 0; - tree->root = (rt_node *) node; + root->chunk = 0; + tree->root = node.encoded; shift += RT_NODE_SPAN; } @@ -974,18 +1047,18 @@ rt_extend(radix_tree *tree, uint64 key) * Insert inner and leaf nodes from 'node' to bottom. */ static inline void -rt_set_extend(radix_tree *tree, uint64 key, uint64 value, rt_node *parent, - rt_node *node) +rt_set_extend(radix_tree *tree, uint64 key, uint64 value, rt_node_ptr parent, + rt_node_ptr node) { - int shift = node->shift; + int shift = NODE_SHIFT(node); while (shift >= RT_NODE_SPAN) { - rt_node *newchild; + rt_node_ptr newchild; int newshift = shift - RT_NODE_SPAN; newchild = rt_alloc_node(tree, RT_NODE_KIND_4, newshift, - RT_GET_KEY_CHUNK(key, node->shift), + RT_GET_KEY_CHUNK(key, NODE_SHIFT(node)), newshift > 0); rt_node_insert_inner(tree, parent, node, key, newchild); @@ -1006,17 +1079,18 @@ rt_set_extend(radix_tree *tree, uint64 key, uint64 value, rt_node *parent, * pointer is set to child_p. */ static inline bool -rt_node_search_inner(rt_node *node, uint64 key, rt_action action, rt_node **child_p) +rt_node_search_inner(rt_node_ptr node, uint64 key, rt_action action, + rt_pointer *child_p) { - uint8 chunk = RT_GET_KEY_CHUNK(key, node->shift); + uint8 chunk = RT_GET_KEY_CHUNK(key, NODE_SHIFT(node)); bool found = false; - rt_node *child = NULL; + rt_pointer child; - switch (node->kind) + switch (NODE_KIND(node)) { case RT_NODE_KIND_4: { - rt_node_inner_4 *n4 = (rt_node_inner_4 *) node; + rt_node_inner_4 *n4 = (rt_node_inner_4 *) node.decoded; int idx = node_4_search_eq((rt_node_base_4 *) n4, chunk); if (idx < 0) @@ -1034,7 +1108,7 @@ rt_node_search_inner(rt_node *node, uint64 key, rt_action action, rt_node **chil } case RT_NODE_KIND_32: { - rt_node_inner_32 *n32 = (rt_node_inner_32 *) node; + rt_node_inner_32 *n32 = (rt_node_inner_32 *) node.decoded; int idx = node_32_search_eq((rt_node_base_32 *) n32, chunk); if (idx < 0) @@ -1050,7 +1124,7 @@ rt_node_search_inner(rt_node *node, uint64 key, rt_action action, rt_node **chil } case RT_NODE_KIND_128: { - rt_node_inner_128 *n128 = (rt_node_inner_128 *) node; + rt_node_inner_128 *n128 = (rt_node_inner_128 *) node.decoded; if (!node_128_is_chunk_used((rt_node_base_128 *) n128, chunk)) break; @@ -1066,7 +1140,7 @@ rt_node_search_inner(rt_node *node, uint64 key, rt_action action, rt_node **chil } case RT_NODE_KIND_256: { - rt_node_inner_256 *n256 = (rt_node_inner_256 *) node; + rt_node_inner_256 *n256 = (rt_node_inner_256 *) node.decoded; if (!node_inner_256_is_chunk_used(n256, chunk)) break; @@ -1083,7 +1157,7 @@ rt_node_search_inner(rt_node *node, uint64 key, rt_action action, rt_node **chil /* update statistics */ if (action == RT_ACTION_DELETE && found) - node->count--; + NODE_COUNT(node)--; if (found && child_p) *child_p = child; @@ -1099,17 +1173,17 @@ rt_node_search_inner(rt_node *node, uint64 key, rt_action action, rt_node **chil * to the value is set to value_p. */ static inline bool -rt_node_search_leaf(rt_node *node, uint64 key, rt_action action, uint64 *value_p) +rt_node_search_leaf(rt_node_ptr node, uint64 key, rt_action action, uint64 *value_p) { - uint8 chunk = RT_GET_KEY_CHUNK(key, node->shift); + uint8 chunk = RT_GET_KEY_CHUNK(key, NODE_SHIFT(node)); bool found = false; uint64 value = 0; - switch (node->kind) + switch (NODE_KIND(node)) { case RT_NODE_KIND_4: { - rt_node_leaf_4 *n4 = (rt_node_leaf_4 *) node; + rt_node_leaf_4 *n4 = (rt_node_leaf_4 *) node.decoded; int idx = node_4_search_eq((rt_node_base_4 *) n4, chunk); if (idx < 0) @@ -1127,7 +1201,7 @@ rt_node_search_leaf(rt_node *node, uint64 key, rt_action action, uint64 *value_p } case RT_NODE_KIND_32: { - rt_node_leaf_32 *n32 = (rt_node_leaf_32 *) node; + rt_node_leaf_32 *n32 = (rt_node_leaf_32 *) node.decoded; int idx = node_32_search_eq((rt_node_base_32 *) n32, chunk); if (idx < 0) @@ -1143,7 +1217,7 @@ rt_node_search_leaf(rt_node *node, uint64 key, rt_action action, uint64 *value_p } case RT_NODE_KIND_128: { - rt_node_leaf_128 *n128 = (rt_node_leaf_128 *) node; + rt_node_leaf_128 *n128 = (rt_node_leaf_128 *) node.decoded; if (!node_128_is_chunk_used((rt_node_base_128 *) n128, chunk)) break; @@ -1159,7 +1233,7 @@ rt_node_search_leaf(rt_node *node, uint64 key, rt_action action, uint64 *value_p } case RT_NODE_KIND_256: { - rt_node_leaf_256 *n256 = (rt_node_leaf_256 *) node; + rt_node_leaf_256 *n256 = (rt_node_leaf_256 *) node.decoded; if (!node_leaf_256_is_chunk_used(n256, chunk)) break; @@ -1176,7 +1250,7 @@ rt_node_search_leaf(rt_node *node, uint64 key, rt_action action, uint64 *value_p /* update statistics */ if (action == RT_ACTION_DELETE && found) - node->count--; + NODE_COUNT(node)--; if (found && value_p) *value_p = value; @@ -1186,19 +1260,19 @@ rt_node_search_leaf(rt_node *node, uint64 key, rt_action action, uint64 *value_p /* Insert the child to the inner node */ static bool -rt_node_insert_inner(radix_tree *tree, rt_node *parent, rt_node *node, uint64 key, - rt_node *child) +rt_node_insert_inner(radix_tree *tree, rt_node_ptr parent, rt_node_ptr node, + uint64 key, rt_node_ptr child) { - uint8 chunk = RT_GET_KEY_CHUNK(key, node->shift); + uint8 chunk = RT_GET_KEY_CHUNK(key, NODE_SHIFT(node)); bool chunk_exists = false; Assert(!NODE_IS_LEAF(node)); - switch (node->kind) + switch (NODE_KIND(node)) { case RT_NODE_KIND_4: { - rt_node_inner_4 *n4 = (rt_node_inner_4 *) node; + rt_node_inner_4 *n4 = (rt_node_inner_4 *) node.decoded; int idx; idx = node_4_search_eq((rt_node_base_4 *) n4, chunk); @@ -1206,25 +1280,26 @@ rt_node_insert_inner(radix_tree *tree, rt_node *parent, rt_node *node, uint64 ke { /* found the existing chunk */ chunk_exists = true; - n4->children[idx] = child; + n4->children[idx] = child.encoded; break; } - if (unlikely(!NODE_HAS_FREE_SLOT(n4))) + if (unlikely(!NODE_HAS_FREE_SLOT(node))) { + rt_node_ptr new; rt_node_inner_32 *new32; /* grow node from 4 to 32 */ - new32 = (rt_node_inner_32 *) rt_copy_node(tree, (rt_node *) n4, - RT_NODE_KIND_32); + new = rt_copy_node(tree, node, RT_NODE_KIND_32); + new32 = (rt_node_inner_32 *) new.decoded; + chunk_children_array_copy(n4->base.chunks, n4->children, new32->base.chunks, new32->children, n4->base.n.count); - Assert(parent != NULL); - rt_replace_node(tree, parent, (rt_node *) n4, (rt_node *) new32, - key); - node = (rt_node *) new32; + Assert(RTNodePtrIsValid(parent)); + rt_replace_node(tree, parent, node, new, key); + node = new; } else { @@ -1237,14 +1312,14 @@ rt_node_insert_inner(radix_tree *tree, rt_node *parent, rt_node *node, uint64 ke count, insertpos); n4->base.chunks[insertpos] = chunk; - n4->children[insertpos] = child; + n4->children[insertpos] = child.encoded; break; } } /* FALLTHROUGH */ case RT_NODE_KIND_32: { - rt_node_inner_32 *n32 = (rt_node_inner_32 *) node; + rt_node_inner_32 *n32 = (rt_node_inner_32 *) node.decoded; int idx; idx = node_32_search_eq((rt_node_base_32 *) n32, chunk); @@ -1252,24 +1327,25 @@ rt_node_insert_inner(radix_tree *tree, rt_node *parent, rt_node *node, uint64 ke { /* found the existing chunk */ chunk_exists = true; - n32->children[idx] = child; + n32->children[idx] = child.encoded; break; } - if (unlikely(!NODE_HAS_FREE_SLOT(n32))) + if (unlikely(!NODE_HAS_FREE_SLOT(node))) { + rt_node_ptr new; rt_node_inner_128 *new128; /* grow node from 32 to 128 */ - new128 = (rt_node_inner_128 *) rt_copy_node(tree, (rt_node *) n32, - RT_NODE_KIND_128); + new = rt_copy_node(tree, node, RT_NODE_KIND_128); + new128 = (rt_node_inner_128 *) new.decoded; + for (int i = 0; i < n32->base.n.count; i++) node_inner_128_insert(new128, n32->base.chunks[i], n32->children[i]); - Assert(parent != NULL); - rt_replace_node(tree, parent, (rt_node *) n32, (rt_node *) new128, - key); - node = (rt_node *) new128; + Assert(RTNodePtrIsValid(parent)); + rt_replace_node(tree, parent, node, new, key); + node = new; } else { @@ -1281,31 +1357,33 @@ rt_node_insert_inner(radix_tree *tree, rt_node *parent, rt_node *node, uint64 ke count, insertpos); n32->base.chunks[insertpos] = chunk; - n32->children[insertpos] = child; + n32->children[insertpos] = child.encoded; break; } } /* FALLTHROUGH */ case RT_NODE_KIND_128: { - rt_node_inner_128 *n128 = (rt_node_inner_128 *) node; + rt_node_inner_128 *n128 = (rt_node_inner_128 *) node.decoded; int cnt = 0; if (node_128_is_chunk_used((rt_node_base_128 *) n128, chunk)) { /* found the existing chunk */ chunk_exists = true; - node_inner_128_update(n128, chunk, child); + node_inner_128_update(n128, chunk, child.encoded); break; } - if (unlikely(!NODE_HAS_FREE_SLOT(n128))) + if (unlikely(!NODE_HAS_FREE_SLOT(node))) { + rt_node_ptr new; rt_node_inner_256 *new256; /* grow node from 128 to 256 */ - new256 = (rt_node_inner_256 *) rt_copy_node(tree, (rt_node *) n128, - RT_NODE_KIND_256); + new = rt_copy_node(tree, node, RT_NODE_KIND_256); + new256 = (rt_node_inner_256 *) new.decoded; + for (int i = 0; i < RT_NODE_MAX_SLOTS && cnt < n128->base.n.count; i++) { if (!node_128_is_chunk_used((rt_node_base_128 *) n128, i)) @@ -1315,33 +1393,32 @@ rt_node_insert_inner(radix_tree *tree, rt_node *parent, rt_node *node, uint64 ke cnt++; } - Assert(parent != NULL); - rt_replace_node(tree, parent, (rt_node *) n128, (rt_node *) new256, - key); - node = (rt_node *) new256; + Assert(RTNodePtrIsValid(parent)); + rt_replace_node(tree, parent, node, new, key); + node = new; } else { - node_inner_128_insert(n128, chunk, child); + node_inner_128_insert(n128, chunk, child.encoded); break; } } /* FALLTHROUGH */ case RT_NODE_KIND_256: { - rt_node_inner_256 *n256 = (rt_node_inner_256 *) node; + rt_node_inner_256 *n256 = (rt_node_inner_256 *) node.decoded; chunk_exists = node_inner_256_is_chunk_used(n256, chunk); - Assert(chunk_exists || NODE_HAS_FREE_SLOT(n256)); + Assert(chunk_exists || NODE_HAS_FREE_SLOT(node)); - node_inner_256_set(n256, chunk, child); + node_inner_256_set(n256, chunk, child.encoded); break; } } /* Update statistics */ if (!chunk_exists) - node->count++; + NODE_COUNT(node)++; /* * Done. Finally, verify the chunk and value is inserted or replaced @@ -1354,19 +1431,19 @@ rt_node_insert_inner(radix_tree *tree, rt_node *parent, rt_node *node, uint64 ke /* Insert the value to the leaf node */ static bool -rt_node_insert_leaf(radix_tree *tree, rt_node *parent, rt_node *node, +rt_node_insert_leaf(radix_tree *tree, rt_node_ptr parent, rt_node_ptr node, uint64 key, uint64 value) { - uint8 chunk = RT_GET_KEY_CHUNK(key, node->shift); + uint8 chunk = RT_GET_KEY_CHUNK(key, NODE_SHIFT(node)); bool chunk_exists = false; Assert(NODE_IS_LEAF(node)); - switch (node->kind) + switch (NODE_KIND(node)) { case RT_NODE_KIND_4: { - rt_node_leaf_4 *n4 = (rt_node_leaf_4 *) node; + rt_node_leaf_4 *n4 = (rt_node_leaf_4 *) node.decoded; int idx; idx = node_4_search_eq((rt_node_base_4 *) n4, chunk); @@ -1378,21 +1455,22 @@ rt_node_insert_leaf(radix_tree *tree, rt_node *parent, rt_node *node, break; } - if (unlikely(!NODE_HAS_FREE_SLOT(n4))) + if (unlikely(!NODE_HAS_FREE_SLOT(node))) { + rt_node_ptr new; rt_node_leaf_32 *new32; /* grow node from 4 to 32 */ - new32 = (rt_node_leaf_32 *) rt_copy_node(tree, (rt_node *) n4, - RT_NODE_KIND_32); + new = rt_copy_node(tree, node, RT_NODE_KIND_32); + new32 = (rt_node_leaf_32 *) new.decoded; + chunk_values_array_copy(n4->base.chunks, n4->values, new32->base.chunks, new32->values, n4->base.n.count); - Assert(parent != NULL); - rt_replace_node(tree, parent, (rt_node *) n4, (rt_node *) new32, - key); - node = (rt_node *) new32; + Assert(RTNodePtrIsValid(parent)); + rt_replace_node(tree, parent, node, new, key); + node = new; } else { @@ -1412,7 +1490,7 @@ rt_node_insert_leaf(radix_tree *tree, rt_node *parent, rt_node *node, /* FALLTHROUGH */ case RT_NODE_KIND_32: { - rt_node_leaf_32 *n32 = (rt_node_leaf_32 *) node; + rt_node_leaf_32 *n32 = (rt_node_leaf_32 *) node.decoded; int idx; idx = node_32_search_eq((rt_node_base_32 *) n32, chunk); @@ -1424,20 +1502,21 @@ rt_node_insert_leaf(radix_tree *tree, rt_node *parent, rt_node *node, break; } - if (unlikely(!NODE_HAS_FREE_SLOT(n32))) + if (unlikely(!NODE_HAS_FREE_SLOT(node))) { + rt_node_ptr new; rt_node_leaf_128 *new128; /* grow node from 32 to 128 */ - new128 = (rt_node_leaf_128 *) rt_copy_node(tree, (rt_node *) n32, - RT_NODE_KIND_128); + new = rt_copy_node(tree, node, RT_NODE_KIND_128); + new128 = (rt_node_leaf_128 *) new.decoded; + for (int i = 0; i < n32->base.n.count; i++) node_leaf_128_insert(new128, n32->base.chunks[i], n32->values[i]); - Assert(parent != NULL); - rt_replace_node(tree, parent, (rt_node *) n32, (rt_node *) new128, - key); - node = (rt_node *) new128; + Assert(RTNodePtrIsValid(parent)); + rt_replace_node(tree, parent, node, new, key); + node = new; } else { @@ -1456,7 +1535,7 @@ rt_node_insert_leaf(radix_tree *tree, rt_node *parent, rt_node *node, /* FALLTHROUGH */ case RT_NODE_KIND_128: { - rt_node_leaf_128 *n128 = (rt_node_leaf_128 *) node; + rt_node_leaf_128 *n128 = (rt_node_leaf_128 *) node.decoded; int cnt = 0; if (node_128_is_chunk_used((rt_node_base_128 *) n128, chunk)) @@ -1467,13 +1546,15 @@ rt_node_insert_leaf(radix_tree *tree, rt_node *parent, rt_node *node, break; } - if (unlikely(!NODE_HAS_FREE_SLOT(n128))) + if (unlikely(!NODE_HAS_FREE_SLOT(node))) { + rt_node_ptr new; rt_node_leaf_256 *new256; /* grow node from 128 to 256 */ - new256 = (rt_node_leaf_256 *) rt_copy_node(tree, (rt_node *) n128, - RT_NODE_KIND_256); + new = rt_copy_node(tree, node, RT_NODE_KIND_256); + new256 = (rt_node_leaf_256 *) new.decoded; + for (int i = 0; i < RT_NODE_MAX_SLOTS && cnt < n128->base.n.count; i++) { if (!node_128_is_chunk_used((rt_node_base_128 *) n128, i)) @@ -1483,10 +1564,9 @@ rt_node_insert_leaf(radix_tree *tree, rt_node *parent, rt_node *node, cnt++; } - Assert(parent != NULL); - rt_replace_node(tree, parent, (rt_node *) n128, (rt_node *) new256, - key); - node = (rt_node *) new256; + Assert(RTNodePtrIsValid(parent)); + rt_replace_node(tree, parent, node, new, key); + node = new; } else { @@ -1497,10 +1577,10 @@ rt_node_insert_leaf(radix_tree *tree, rt_node *parent, rt_node *node, /* FALLTHROUGH */ case RT_NODE_KIND_256: { - rt_node_leaf_256 *n256 = (rt_node_leaf_256 *) node; + rt_node_leaf_256 *n256 = (rt_node_leaf_256 *) node.decoded; chunk_exists = node_leaf_256_is_chunk_used(n256, chunk); - Assert(chunk_exists || NODE_HAS_FREE_SLOT(n256)); + Assert(chunk_exists || NODE_HAS_FREE_SLOT(node)); node_leaf_256_set(n256, chunk, value); break; @@ -1509,7 +1589,7 @@ rt_node_insert_leaf(radix_tree *tree, rt_node *parent, rt_node *node, /* Update statistics */ if (!chunk_exists) - node->count++; + NODE_COUNT(node)++; /* * Done. Finally, verify the chunk and value is inserted or replaced @@ -1533,7 +1613,7 @@ rt_create(MemoryContext ctx) tree = palloc(sizeof(radix_tree)); tree->context = ctx; - tree->root = NULL; + tree->root = InvalidRTPointer; tree->max_val = 0; tree->num_keys = 0; @@ -1582,26 +1662,24 @@ rt_set(radix_tree *tree, uint64 key, uint64 value) { int shift; bool updated; - rt_node *node; - rt_node *parent = tree->root; + rt_node_ptr node; + rt_node_ptr parent; /* Empty tree, create the root */ - if (!tree->root) + if (!RTPointerIsValid(tree->root)) rt_new_root(tree, key); /* Extend the tree if necessary */ if (key > tree->max_val) rt_extend(tree, key); - Assert(tree->root); - - shift = tree->root->shift; - node = tree->root; - /* Descend the tree until a leaf node */ + parent = rt_node_ptr_encoded(tree->root); + node = rt_node_ptr_encoded(tree->root); + shift = NODE_SHIFT(node); while (shift >= 0) { - rt_node *child; + rt_pointer child; if (NODE_IS_LEAF(node)) break; @@ -1613,7 +1691,7 @@ rt_set(radix_tree *tree, uint64 key, uint64 value) } parent = node; - node = child; + node = rt_node_ptr_encoded(child); shift -= RT_NODE_SPAN; } @@ -1634,21 +1712,21 @@ rt_set(radix_tree *tree, uint64 key, uint64 value) bool rt_search(radix_tree *tree, uint64 key, uint64 *value_p) { - rt_node *node; + rt_node_ptr node; int shift; Assert(value_p != NULL); - if (!tree->root || key > tree->max_val) + if (!RTPointerIsValid(tree->root) || key > tree->max_val) return false; - node = tree->root; - shift = tree->root->shift; + node = rt_node_ptr_encoded(tree->root); + shift = NODE_SHIFT(node); /* Descend the tree until a leaf node */ while (shift >= 0) { - rt_node *child; + rt_pointer child; if (NODE_IS_LEAF(node)) break; @@ -1656,7 +1734,7 @@ rt_search(radix_tree *tree, uint64 key, uint64 *value_p) if (!rt_node_search_inner(node, key, RT_ACTION_FIND, &child)) return false; - node = child; + node = rt_node_ptr_encoded(child); shift -= RT_NODE_SPAN; } @@ -1670,8 +1748,8 @@ rt_search(radix_tree *tree, uint64 key, uint64 *value_p) bool rt_delete(radix_tree *tree, uint64 key) { - rt_node *node; - rt_node *stack[RT_MAX_LEVEL] = {0}; + rt_node_ptr node; + rt_node_ptr stack[RT_MAX_LEVEL] = {0}; int shift; int level; bool deleted; @@ -1683,12 +1761,12 @@ rt_delete(radix_tree *tree, uint64 key) * Descend the tree to search the key while building a stack of nodes we * visited. */ - node = tree->root; - shift = tree->root->shift; + node = rt_node_ptr_encoded(tree->root); + shift = NODE_SHIFT(node); level = -1; while (shift > 0) { - rt_node *child; + rt_pointer child; /* Push the current node to the stack */ stack[++level] = node; @@ -1696,7 +1774,7 @@ rt_delete(radix_tree *tree, uint64 key) if (!rt_node_search_inner(node, key, RT_ACTION_FIND, &child)) return false; - node = child; + node = rt_node_ptr_encoded(child); shift -= RT_NODE_SPAN; } @@ -1745,7 +1823,7 @@ rt_delete(radix_tree *tree, uint64 key) */ if (level == 0) { - tree->root = NULL; + tree->root = InvalidRTPointer; tree->max_val = 0; } @@ -1757,6 +1835,7 @@ rt_iter * rt_begin_iterate(radix_tree *tree) { MemoryContext old_ctx; + rt_node_ptr root; rt_iter *iter; int top_level; @@ -1766,17 +1845,18 @@ rt_begin_iterate(radix_tree *tree) iter->tree = tree; /* empty tree */ - if (!iter->tree) + if (!RTPointerIsValid(iter->tree)) return iter; - top_level = iter->tree->root->shift / RT_NODE_SPAN; + root = rt_node_ptr_encoded(iter->tree->root); + top_level = NODE_SHIFT(root) / RT_NODE_SPAN; iter->stack_len = top_level; /* * Descend to the left most leaf node from the root. The key is being * constructed while descending to the leaf. */ - rt_update_iter_stack(iter, iter->tree->root, top_level); + rt_update_iter_stack(iter, root, top_level); MemoryContextSwitchTo(old_ctx); @@ -1787,14 +1867,15 @@ rt_begin_iterate(radix_tree *tree) * Update each node_iter for inner nodes in the iterator node stack. */ static void -rt_update_iter_stack(rt_iter *iter, rt_node *from_node, int from) +rt_update_iter_stack(rt_iter *iter, rt_node_ptr from_node, int from) { int level = from; - rt_node *node = from_node; + rt_node_ptr node = from_node; for (;;) { rt_node_iter *node_iter = &(iter->stack[level--]); + bool found PG_USED_FOR_ASSERTS_ONLY; node_iter->node = node; node_iter->current_idx = -1; @@ -1804,10 +1885,10 @@ rt_update_iter_stack(rt_iter *iter, rt_node *from_node, int from) return; /* Advance to the next slot in the inner node */ - node = rt_node_inner_iterate_next(iter, node_iter); + found = rt_node_inner_iterate_next(iter, node_iter, &node); /* We must find the first children in the node */ - Assert(node); + Assert(found); } } @@ -1824,7 +1905,7 @@ rt_iterate_next(rt_iter *iter, uint64 *key_p, uint64 *value_p) for (;;) { - rt_node *child = NULL; + rt_node_ptr child = InvalidRTNodePtr; uint64 value; int level; bool found; @@ -1845,14 +1926,12 @@ rt_iterate_next(rt_iter *iter, uint64 *key_p, uint64 *value_p) */ for (level = 1; level <= iter->stack_len; level++) { - child = rt_node_inner_iterate_next(iter, &(iter->stack[level])); - - if (child) + if (rt_node_inner_iterate_next(iter, &(iter->stack[level]), &child)) break; } /* the iteration finished */ - if (!child) + if (!RTNodePtrIsValid(child)) return false; /* @@ -1884,18 +1963,19 @@ rt_iter_update_key(rt_iter *iter, uint8 chunk, uint8 shift) * Advance the slot in the inner node. Return the child if exists, otherwise * null. */ -static inline rt_node * -rt_node_inner_iterate_next(rt_iter *iter, rt_node_iter *node_iter) +static inline bool +rt_node_inner_iterate_next(rt_iter *iter, rt_node_iter *node_iter, rt_node_ptr *child_p) { - rt_node *child = NULL; + rt_node_ptr node = node_iter->node; + rt_pointer child; bool found = false; uint8 key_chunk; - switch (node_iter->node->kind) + switch (NODE_KIND(node)) { case RT_NODE_KIND_4: { - rt_node_inner_4 *n4 = (rt_node_inner_4 *) node_iter->node; + rt_node_inner_4 *n4 = (rt_node_inner_4 *) node.decoded; node_iter->current_idx++; if (node_iter->current_idx >= n4->base.n.count) @@ -1908,7 +1988,7 @@ rt_node_inner_iterate_next(rt_iter *iter, rt_node_iter *node_iter) } case RT_NODE_KIND_32: { - rt_node_inner_32 *n32 = (rt_node_inner_32 *) node_iter->node; + rt_node_inner_32 *n32 = (rt_node_inner_32 *) node.decoded; node_iter->current_idx++; if (node_iter->current_idx >= n32->base.n.count) @@ -1921,7 +2001,7 @@ rt_node_inner_iterate_next(rt_iter *iter, rt_node_iter *node_iter) } case RT_NODE_KIND_128: { - rt_node_inner_128 *n128 = (rt_node_inner_128 *) node_iter->node; + rt_node_inner_128 *n128 = (rt_node_inner_128 *) node.decoded; int i; for (i = node_iter->current_idx + 1; i < RT_NODE_MAX_SLOTS; i++) @@ -1941,7 +2021,7 @@ rt_node_inner_iterate_next(rt_iter *iter, rt_node_iter *node_iter) } case RT_NODE_KIND_256: { - rt_node_inner_256 *n256 = (rt_node_inner_256 *) node_iter->node; + rt_node_inner_256 *n256 = (rt_node_inner_256 *) node.decoded; int i; for (i = node_iter->current_idx + 1; i < RT_NODE_MAX_SLOTS; i++) @@ -1962,9 +2042,12 @@ rt_node_inner_iterate_next(rt_iter *iter, rt_node_iter *node_iter) } if (found) - rt_iter_update_key(iter, key_chunk, node_iter->node->shift); + { + rt_iter_update_key(iter, key_chunk, NODE_SHIFT(node)); + *child_p = rt_node_ptr_encoded(child); + } - return child; + return found; } /* @@ -1972,19 +2055,18 @@ rt_node_inner_iterate_next(rt_iter *iter, rt_node_iter *node_iter) * is set to value_p, otherwise return false. */ static inline bool -rt_node_leaf_iterate_next(rt_iter *iter, rt_node_iter *node_iter, - uint64 *value_p) +rt_node_leaf_iterate_next(rt_iter *iter, rt_node_iter *node_iter, uint64 *value_p) { - rt_node *node = node_iter->node; + rt_node_ptr node = node_iter->node; bool found = false; uint64 value; uint8 key_chunk; - switch (node->kind) + switch (NODE_KIND(node)) { case RT_NODE_KIND_4: { - rt_node_leaf_4 *n4 = (rt_node_leaf_4 *) node_iter->node; + rt_node_leaf_4 *n4 = (rt_node_leaf_4 *) node.decoded; node_iter->current_idx++; if (node_iter->current_idx >= n4->base.n.count) @@ -1997,7 +2079,7 @@ rt_node_leaf_iterate_next(rt_iter *iter, rt_node_iter *node_iter, } case RT_NODE_KIND_32: { - rt_node_leaf_32 *n32 = (rt_node_leaf_32 *) node_iter->node; + rt_node_leaf_32 *n32 = (rt_node_leaf_32 *) node.decoded; node_iter->current_idx++; if (node_iter->current_idx >= n32->base.n.count) @@ -2010,7 +2092,7 @@ rt_node_leaf_iterate_next(rt_iter *iter, rt_node_iter *node_iter, } case RT_NODE_KIND_128: { - rt_node_leaf_128 *n128 = (rt_node_leaf_128 *) node_iter->node; + rt_node_leaf_128 *n128 = (rt_node_leaf_128 *) node.decoded; int i; for (i = node_iter->current_idx + 1; i < RT_NODE_MAX_SLOTS; i++) @@ -2030,7 +2112,7 @@ rt_node_leaf_iterate_next(rt_iter *iter, rt_node_iter *node_iter, } case RT_NODE_KIND_256: { - rt_node_leaf_256 *n256 = (rt_node_leaf_256 *) node_iter->node; + rt_node_leaf_256 *n256 = (rt_node_leaf_256 *) node.decoded; int i; for (i = node_iter->current_idx + 1; i < RT_NODE_MAX_SLOTS; i++) @@ -2052,7 +2134,7 @@ rt_node_leaf_iterate_next(rt_iter *iter, rt_node_iter *node_iter, if (found) { - rt_iter_update_key(iter, key_chunk, node_iter->node->shift); + rt_iter_update_key(iter, key_chunk, NODE_SHIFT(node)); *value_p = value; } @@ -2089,16 +2171,16 @@ rt_memory_usage(radix_tree *tree) * Verify the radix tree node. */ static void -rt_verify_node(rt_node *node) +rt_verify_node(rt_node_ptr node) { #ifdef USE_ASSERT_CHECKING - Assert(node->count >= 0); + Assert(NODE_COUNT(node) >= 0); - switch (node->kind) + switch (NODE_KIND(node)) { case RT_NODE_KIND_4: { - rt_node_base_4 *n4 = (rt_node_base_4 *) node; + rt_node_base_4 *n4 = (rt_node_base_4 *) node.decoded; for (int i = 1; i < n4->n.count; i++) Assert(n4->chunks[i - 1] < n4->chunks[i]); @@ -2107,7 +2189,7 @@ rt_verify_node(rt_node *node) } case RT_NODE_KIND_32: { - rt_node_base_32 *n32 = (rt_node_base_32 *) node; + rt_node_base_32 *n32 = (rt_node_base_32 *) node.decoded; for (int i = 1; i < n32->n.count; i++) Assert(n32->chunks[i - 1] < n32->chunks[i]); @@ -2116,7 +2198,7 @@ rt_verify_node(rt_node *node) } case RT_NODE_KIND_128: { - rt_node_base_128 *n128 = (rt_node_base_128 *) node; + rt_node_base_128 *n128 = (rt_node_base_128 *) node.decoded; int cnt = 0; for (int i = 0; i < RT_NODE_MAX_SLOTS; i++) @@ -2126,10 +2208,10 @@ rt_verify_node(rt_node *node) /* Check if the corresponding slot is used */ if (NODE_IS_LEAF(node)) - Assert(node_leaf_128_is_slot_used((rt_node_leaf_128 *) node, + Assert(node_leaf_128_is_slot_used((rt_node_leaf_128 *) n128, n128->slot_idxs[i])); else - Assert(node_inner_128_is_slot_used((rt_node_inner_128 *) node, + Assert(node_inner_128_is_slot_used((rt_node_inner_128 *) n128, n128->slot_idxs[i])); cnt++; @@ -2142,7 +2224,7 @@ rt_verify_node(rt_node *node) { if (NODE_IS_LEAF(node)) { - rt_node_leaf_256 *n256 = (rt_node_leaf_256 *) node; + rt_node_leaf_256 *n256 = (rt_node_leaf_256 *) node.decoded; int cnt = 0; for (int i = 0; i < RT_NODE_NSLOTS_BITS(RT_NODE_MAX_SLOTS); i++) @@ -2163,9 +2245,11 @@ rt_verify_node(rt_node *node) void rt_stats(radix_tree *tree) { + rt_node_ptr root = rt_node_ptr_encoded(tree->root); + ereport(LOG, (errmsg("num_keys = %lu, height = %u, n4 = %u, n32 = %u, n128 = %u, n256 = %u", tree->num_keys, - tree->root->shift / RT_NODE_SPAN, + NODE_SHIFT(root) / RT_NODE_SPAN, tree->cnt[0], tree->cnt[1], tree->cnt[2], @@ -2173,42 +2257,44 @@ rt_stats(radix_tree *tree) } static void -rt_dump_node(rt_node *node, int level, bool recurse) +rt_dump_node(rt_node_ptr node, int level, bool recurse) { + rt_node *n = node.decoded; char space[128] = {0}; fprintf(stderr, "[%s] kind %d, count %u, shift %u, chunk 0x%X:\n", NODE_IS_LEAF(node) ? "LEAF" : "INNR", - (node->kind == RT_NODE_KIND_4) ? 4 : - (node->kind == RT_NODE_KIND_32) ? 32 : - (node->kind == RT_NODE_KIND_128) ? 128 : 256, - node->count, node->shift, node->chunk); + (NODE_KIND(node) == RT_NODE_KIND_4) ? 4 : + (NODE_KIND(node) == RT_NODE_KIND_32) ? 32 : + (NODE_KIND(node) == RT_NODE_KIND_128) ? 128 : 256, + n->count, n->shift, n->chunk); if (level > 0) sprintf(space, "%*c", level * 4, ' '); - switch (node->kind) + switch (NODE_KIND(node)) { case RT_NODE_KIND_4: { - for (int i = 0; i < node->count; i++) + for (int i = 0; i < NODE_COUNT(node); i++) { if (NODE_IS_LEAF(node)) { - rt_node_leaf_4 *n4 = (rt_node_leaf_4 *) node; + rt_node_leaf_4 *n4 = (rt_node_leaf_4 *) node.decoded; fprintf(stderr, "%schunk 0x%X value 0x%lX\n", space, n4->base.chunks[i], n4->values[i]); } else { - rt_node_inner_4 *n4 = (rt_node_inner_4 *) node; + rt_node_inner_4 *n4 = (rt_node_inner_4 *) node.decoded; fprintf(stderr, "%schunk 0x%X ->", space, n4->base.chunks[i]); if (recurse) - rt_dump_node(n4->children[i], level + 1, recurse); + rt_dump_node(rt_node_ptr_encoded(n4->children[i]), + level + 1, recurse); else fprintf(stderr, "\n"); } @@ -2217,25 +2303,26 @@ rt_dump_node(rt_node *node, int level, bool recurse) } case RT_NODE_KIND_32: { - for (int i = 0; i < node->count; i++) + for (int i = 0; i < NODE_KIND(node); i++) { if (NODE_IS_LEAF(node)) { - rt_node_leaf_32 *n32 = (rt_node_leaf_32 *) node; + rt_node_leaf_32 *n32 = (rt_node_leaf_32 *) node.decoded; fprintf(stderr, "%schunk 0x%X value 0x%lX\n", space, n32->base.chunks[i], n32->values[i]); } else { - rt_node_inner_32 *n32 = (rt_node_inner_32 *) node; + rt_node_inner_32 *n32 = (rt_node_inner_32 *) node.decoded; fprintf(stderr, "%schunk 0x%X ->", space, n32->base.chunks[i]); if (recurse) { - rt_dump_node(n32->children[i], level + 1, recurse); + rt_dump_node(rt_node_ptr_encoded(n32->children[i]), + level + 1, recurse); } else fprintf(stderr, "\n"); @@ -2245,7 +2332,7 @@ rt_dump_node(rt_node *node, int level, bool recurse) } case RT_NODE_KIND_128: { - rt_node_base_128 *b128 = (rt_node_base_128 *) node; + rt_node_base_128 *b128 = (rt_node_base_128 *) node.decoded; fprintf(stderr, "slot_idxs "); for (int i = 0; i < RT_NODE_MAX_SLOTS; i++) @@ -2257,7 +2344,7 @@ rt_dump_node(rt_node *node, int level, bool recurse) } if (NODE_IS_LEAF(node)) { - rt_node_leaf_128 *n = (rt_node_leaf_128 *) node; + rt_node_leaf_128 *n = (rt_node_leaf_128 *) node.decoded; fprintf(stderr, ", isset-bitmap:"); for (int i = 0; i < 16; i++) @@ -2287,7 +2374,7 @@ rt_dump_node(rt_node *node, int level, bool recurse) space, i); if (recurse) - rt_dump_node(node_inner_128_get_child(n128, i), + rt_dump_node(rt_node_ptr_encoded(node_inner_128_get_child(n128, i)), level + 1, recurse); else fprintf(stderr, "\n"); @@ -2301,7 +2388,7 @@ rt_dump_node(rt_node *node, int level, bool recurse) { if (NODE_IS_LEAF(node)) { - rt_node_leaf_256 *n256 = (rt_node_leaf_256 *) node; + rt_node_leaf_256 *n256 = (rt_node_leaf_256 *) node.decoded; if (!node_leaf_256_is_chunk_used(n256, i)) continue; @@ -2311,7 +2398,7 @@ rt_dump_node(rt_node *node, int level, bool recurse) } else { - rt_node_inner_256 *n256 = (rt_node_inner_256 *) node; + rt_node_inner_256 *n256 = (rt_node_inner_256 *) node.decoded; if (!node_inner_256_is_chunk_used(n256, i)) continue; @@ -2320,8 +2407,8 @@ rt_dump_node(rt_node *node, int level, bool recurse) space, i); if (recurse) - rt_dump_node(node_inner_256_get_child(n256, i), level + 1, - recurse); + rt_dump_node(rt_node_ptr_encoded(node_inner_256_get_child(n256, i)), + level + 1, recurse); else fprintf(stderr, "\n"); } @@ -2334,14 +2421,14 @@ rt_dump_node(rt_node *node, int level, bool recurse) void rt_dump_search(radix_tree *tree, uint64 key) { - rt_node *node; + rt_node_ptr node; int shift; int level = 0; elog(NOTICE, "-----------------------------------------------------------"); elog(NOTICE, "max_val = %lu (0x%lX)", tree->max_val, tree->max_val); - if (!tree->root) + if (!RTPointerIsValid(tree->root)) { elog(NOTICE, "tree is empty"); return; @@ -2354,11 +2441,11 @@ rt_dump_search(radix_tree *tree, uint64 key) return; } - node = tree->root; - shift = tree->root->shift; + node = rt_node_ptr_encoded(tree->root); + shift = NODE_SHIFT(node); while (shift >= 0) { - rt_node *child; + rt_pointer child; rt_dump_node(node, level, false); @@ -2375,7 +2462,7 @@ rt_dump_search(radix_tree *tree, uint64 key) if (!rt_node_search_inner(node, key, RT_ACTION_FIND, &child)) break; - node = child; + node = rt_node_ptr_encoded(child); shift -= RT_NODE_SPAN; level++; } @@ -2384,6 +2471,8 @@ rt_dump_search(radix_tree *tree, uint64 key) void rt_dump(radix_tree *tree) { + rt_node_ptr root; + for (int i = 0; i < RT_NODE_KIND_COUNT; i++) fprintf(stderr, "%s\tinner_size%lu\tinner_blocksize %lu\tleaf_size %lu\tleaf_blocksize %lu\n", rt_node_kind_info[i].name, @@ -2393,12 +2482,13 @@ rt_dump(radix_tree *tree) rt_node_kind_info[i].leaf_blocksize); fprintf(stderr, "max_val = %lu\n", tree->max_val); - if (!tree->root) + if (!RTPointerIsValid(tree->root)) { fprintf(stderr, "empty tree\n"); return; } - rt_dump_node(tree->root, 0, true); + root = rt_node_ptr_encoded(tree->root); + rt_dump_node(root, 0, true); } #endif -- 2.31.1