v9-0004-PoC-tag-the-node-kind-to-rt_pointer.patch
application/octet-stream
Filename: v9-0004-PoC-tag-the-node-kind-to-rt_pointer.patch
Type: application/octet-stream
Part: 1
Patch
Format: format-patch
Series: patch v9-0004
Subject: PoC: tag the node kind to rt_pointer.
| File | + | − |
|---|---|---|
| src/backend/lib/radixtree.c | 375 | 285 |
From 624fd0577546a746f0538b98ab7456adc4ca1bd5 Mon Sep 17 00:00:00 2001
From: Masahiko Sawada <sawada.mshk@gmail.com>
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