From 571d1fc63ec4c239015fbb2de98c2ea515da3326 Mon Sep 17 00:00:00 2001 From: John Naylor Date: Thu, 4 Sep 2025 15:22:23 +0700 Subject: [PATCH v2 7/8] RT_ITER_STAGE_DELETE Allow staging the current key for deletion. It will be deleted at next node iteration or when ending iteration. WIP: This could be a callback facility. We'll need something to help lossify pages, which requires both deletion and insertion. --- src/include/lib/radixtree.h | 41 ++++++++ .../expected/test_radixtree.out | 2 + .../modules/test_radixtree/test_radixtree.c | 98 +++++++++++++++++++ 3 files changed, 141 insertions(+) diff --git a/src/include/lib/radixtree.h b/src/include/lib/radixtree.h index 080d5abe8b2..9db4d9a3615 100644 --- a/src/include/lib/radixtree.h +++ b/src/include/lib/radixtree.h @@ -184,6 +184,7 @@ #define RT_BEGIN_ITERATE RT_MAKE_NAME(begin_iterate) #define RT_BEGIN_ITERATE_AT RT_MAKE_NAME(begin_iterate_at) #define RT_ITERATE_NEXT RT_MAKE_NAME(iterate_next) +#define RT_ITER_STAGE_DELETE RT_MAKE_NAME(iter_stage_delete) #define RT_END_ITERATE RT_MAKE_NAME(end_iterate) #define RT_DELETE RT_MAKE_NAME(delete) #define RT_MEMORY_USAGE RT_MAKE_NAME(memory_usage) @@ -293,6 +294,7 @@ RT_SCOPE bool RT_DELETE(RT_RADIX_TREE * tree, uint64 key); RT_SCOPE RT_ITER *RT_BEGIN_ITERATE(RT_RADIX_TREE * tree); RT_SCOPE RT_ITER *RT_BEGIN_ITERATE_AT(RT_RADIX_TREE * tree, uint64 key); RT_SCOPE RT_VALUE_TYPE *RT_ITERATE_NEXT(RT_ITER * iter, uint64 *key_p); +RT_SCOPE void RT_ITER_STAGE_DELETE(RT_ITER * iter); RT_SCOPE void RT_END_ITERATE(RT_ITER * iter); RT_SCOPE uint64 RT_MEMORY_USAGE(RT_RADIX_TREE * tree); @@ -747,6 +749,10 @@ struct RT_ITER /* The key constructed during iteration */ uint64 key; + + /* state for deletion that happens during iteration */ + uint64 to_delete[RT_NODE_MAX_SLOTS]; + int num_to_delete; }; @@ -2112,6 +2118,7 @@ RT_BEGIN_ITERATE_AT(RT_RADIX_TREE * tree, uint64 key) iter->node_iters[level].idx = RT_GET_KEY_CHUNK(key, level * RT_SPAN); } + iter->key = key; return iter; } @@ -2230,6 +2237,10 @@ RT_SCOPE RT_VALUE_TYPE * RT_ITERATE_NEXT(RT_ITER * iter, uint64 *key_p) { RT_PTR_ALLOC *slot = NULL; +restart: + /* guard against starting iteration larger than max val */ + if (iter->key > iter->tree->ctl->max_val) + return NULL; while (iter->cur_level <= iter->top_level) { @@ -2261,6 +2272,23 @@ RT_ITERATE_NEXT(RT_ITER * iter, uint64 *key_p) iter->cur_level--; iter->node_iters[iter->cur_level].node = node; } + else if (iter->num_to_delete > 0) + { + // WIP test overflow + /* zero out lowest byte */ + uint64 leaf_min_key = iter->key & ~((uint64) RT_CHUNK_MASK); + RT_RADIX_TREE *save_tree = iter->tree; + + Assert(iter->cur_level == 0); + + RT_END_ITERATE(iter); + if (leaf_min_key < (PG_UINT64_MAX & ~((uint64) RT_CHUNK_MASK))) + { + /* restart at lowest possible key for next iteration */ + iter = RT_BEGIN_ITERATE_AT(save_tree, leaf_min_key + RT_NODE_MAX_SLOTS); + goto restart; + } + } else { /* Not found the child slot, move up the tree */ @@ -2273,12 +2301,24 @@ RT_ITERATE_NEXT(RT_ITER * iter, uint64 *key_p) return NULL; } +RT_SCOPE void +RT_ITER_STAGE_DELETE(RT_ITER * iter) +{ + iter->to_delete[iter->num_to_delete++] = iter->key; +} + /* * Terminate the iteration. The caller is responsible for releasing any locks. */ RT_SCOPE void RT_END_ITERATE(RT_ITER * iter) { + for (int i = 0; i < iter->num_to_delete; i++) + { + bool deleted = RT_DELETE(iter->tree, iter->to_delete[i]); + Assert(deleted); + } + pfree(iter); } @@ -3020,6 +3060,7 @@ RT_DUMP_NODE(RT_NODE * node) #undef RT_BEGIN_ITERATE #undef RT_BEGIN_ITERATE_AT #undef RT_ITERATE_NEXT +#undef RT_ITER_STAGE_DELETE #undef RT_END_ITERATE #undef RT_DELETE #undef RT_MEMORY_USAGE diff --git a/src/test/modules/test_radixtree/expected/test_radixtree.out b/src/test/modules/test_radixtree/expected/test_radixtree.out index 14aceecfede..ea65e64f371 100644 --- a/src/test/modules/test_radixtree/expected/test_radixtree.out +++ b/src/test/modules/test_radixtree/expected/test_radixtree.out @@ -34,6 +34,8 @@ NOTICE: testing node node-256 with shift 8 and ascending keys NOTICE: testing node node-256 with shift 8 and descending keys NOTICE: testing node node-256 with shift 56 and ascending keys NOTICE: testing node node-256 with shift 56 and descending keys +NOTICE: testing iteration with delete at shift 0 +NOTICE: testing iteration with delete at shift 8 test_radixtree ---------------- diff --git a/src/test/modules/test_radixtree/test_radixtree.c b/src/test/modules/test_radixtree/test_radixtree.c index a5465a3a2a6..b2a433e8023 100644 --- a/src/test/modules/test_radixtree/test_radixtree.c +++ b/src/test/modules/test_radixtree/test_radixtree.c @@ -332,6 +332,101 @@ test_basic(rt_node_class_test_elem *test_info, int shift, bool asc) #endif } +static void +test_iter_delete(int shift) +{ + rt_radix_tree *radixtree; + rt_iter *iter; + uint64 iterkey; + TestValueType *iterval; + + /* limit memory usage by limiting the key space */ + //int num_keys = 2; + uint64 keys[2] = {7 << shift, 17 << shift}; +#ifdef TEST_SHARED_RT + int tranche_id = LWLockNewTrancheId("test_radix_tree"); + dsa_area *dsa; + + dsa = dsa_create(tranche_id); + radixtree = rt_create(dsa, tranche_id); +#else + MemoryContext radixtree_ctx; + + radixtree_ctx = SlabContextCreate(CurrentMemoryContext, + "test_radix_tree", + SLAB_DEFAULT_BLOCK_SIZE, + sizeof(TestValueType)); + radixtree = rt_create(radixtree_ctx); +#endif + + elog(NOTICE, "testing iteration with delete at shift %d", + shift); + + rt_set(radixtree, keys[0], &keys[0]); + rt_set(radixtree, keys[1], &keys[1]); + rt_stats(radixtree); + + /* begin at last key */ + iter = rt_begin_iterate_at(radixtree, keys[1]); + + /* expect the value we started at */ + iterval = rt_iterate_next(iter, &iterkey); + EXPECT_TRUE(iterval != NULL); + EXPECT_EQ_U64(iterkey, keys[1]); + EXPECT_EQ_U64(*iterval, keys[1]); + + /* ...and no more */ + iterval = rt_iterate_next(iter, &iterkey); + EXPECT_TRUE(iterval == NULL); + + /* begin lower than first key */ + Assert(keys[0] > 0); + iter = rt_begin_iterate_at(radixtree, 0); + + /* advance to first key */ + iterval = rt_iterate_next(iter, &iterkey); + EXPECT_TRUE(iterval != NULL); + EXPECT_EQ_U64(iterkey, keys[0]); + EXPECT_EQ_U64(*iterval, keys[0]); + + /* stage it for deletion */ + rt_iter_stage_delete(iter); + + /* get next key/value, should be the last one */ + iterval = rt_iterate_next(iter, &iterkey); + EXPECT_TRUE(iterval != NULL); + EXPECT_EQ_U64(iterkey, keys[1]); + EXPECT_EQ_U64(*iterval, keys[1]); + + /* commit deletion */ + rt_end_iterate(iter); + EXPECT_TRUE(rt_num_entries(radixtree) == 1); + + rt_stats(radixtree); + + /* begin after last key, making sure root node has lowest possible chunk */ + + Assert(keys[1] < 65536 + 1); + rt_begin_iterate_at(radixtree, 65536 + 1); + /* should find nothing */ + iterval = rt_iterate_next(iter, &iterkey); + EXPECT_TRUE(iterval == NULL); + + /* delete everything through the iterator */ + + for (TestValueType i = 1000; i< 2000; i++) + rt_set(radixtree, i, &i); + + iter = rt_begin_iterate(radixtree); + while ((iterval = rt_iterate_next(iter, &iterkey)) != NULL) + { + Assert (*iterval = iterkey); + rt_iter_stage_delete(iter); + } + rt_end_iterate(iter); + EXPECT_TRUE(rt_num_entries(radixtree) == 0); +} + static int key_cmp(const void *a, const void *b) { @@ -503,5 +598,8 @@ test_radixtree(PG_FUNCTION_ARGS) test_random(); + test_iter_delete(0); + test_iter_delete(8); + PG_RETURN_VOID(); } -- 2.51.0