From c6394b202070aef28d2fa75617e930a6514a614d Mon Sep 17 00:00:00 2001 From: John Naylor Date: Tue, 2 Sep 2025 15:57:38 +0700 Subject: [PATCH v2 6/8] Add RT_BEGIN_ITERATE_AT Instead of beginning at the lowest key, start with any given key. The first call to RT_ITERATE_NEXT will return the start key/value if it exists, otherwise the next key. RT_BEGIN_ITERATE is now a thin wrapper around RT_BEGIN_ITERATE_AT --- src/include/lib/radixtree.h | 59 +++++++++++++------ .../modules/test_radixtree/test_radixtree.c | 55 ++++++++++++++++- 2 files changed, 92 insertions(+), 22 deletions(-) diff --git a/src/include/lib/radixtree.h b/src/include/lib/radixtree.h index 21cd0156fe9..080d5abe8b2 100644 --- a/src/include/lib/radixtree.h +++ b/src/include/lib/radixtree.h @@ -182,6 +182,7 @@ #define RT_SET_SLOT RT_MAKE_NAME (set_slot) #define RT_SET RT_MAKE_NAME(set) #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_END_ITERATE RT_MAKE_NAME(end_iterate) #define RT_DELETE RT_MAKE_NAME(delete) @@ -290,6 +291,7 @@ RT_SCOPE bool RT_SET(RT_RADIX_TREE * tree, uint64 key, RT_VALUE_TYPE * value_p); 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_END_ITERATE(RT_ITER * iter); @@ -726,11 +728,7 @@ typedef struct RT_NODE_ITER { RT_CHILD_PTR node; - /* - * The next index of the chunk array in RT_NODE_KIND_4 and RT_NODE_KIND_16 - * nodes, or the next chunk in RT_NODE_KIND_48 and RT_NODE_KIND_256 nodes. - * 0 for the initial value. - */ + // TODO: add next_chunk so idx can just save the last index int idx; } RT_NODE_ITER; @@ -2085,6 +2083,12 @@ RT_FREE(RT_RADIX_TREE * tree) */ RT_SCOPE RT_ITER * RT_BEGIN_ITERATE(RT_RADIX_TREE * tree) +{ + return RT_BEGIN_ITERATE_AT(tree, 0); +} + +RT_SCOPE RT_ITER * +RT_BEGIN_ITERATE_AT(RT_RADIX_TREE * tree, uint64 key) { RT_ITER *iter; RT_CHILD_PTR root; @@ -2101,7 +2105,12 @@ RT_BEGIN_ITERATE(RT_RADIX_TREE * tree) /* Set the root to start */ iter->cur_level = iter->top_level; iter->node_iters[iter->cur_level].node = root; - iter->node_iters[iter->cur_level].idx = 0; + + /* pre-fill iter stack for first key */ + for (int level = 0; level <= iter->top_level; level++) + { + iter->node_iters[level].idx = RT_GET_KEY_CHUNK(key, level * RT_SPAN); + } return iter; } @@ -2133,25 +2142,35 @@ RT_NODE_ITERATE_NEXT(RT_ITER * iter, int level) { RT_NODE_4 *n4 = (RT_NODE_4 *) (node.local); - if (node_iter->idx >= n4->base.count) - return NULL; + for (int i = 0; i < n4->base.count; i++) + { + if (n4->chunks[i] >= node_iter->idx) + { + slot = &n4->children[i]; + key_chunk = n4->chunks[i]; + node_iter->idx = key_chunk + 1; + goto update; + } + } - slot = &n4->children[node_iter->idx]; - key_chunk = n4->chunks[node_iter->idx]; - node_iter->idx++; - break; + return NULL; } case RT_NODE_KIND_16: { RT_NODE_16 *n16 = (RT_NODE_16 *) (node.local); - if (node_iter->idx >= n16->base.count) - return NULL; + for (int i = 0; i < n16->base.count; i++) + { + if (n16->chunks[i] >= node_iter->idx) + { + slot = &n16->children[i]; + key_chunk = n16->chunks[i]; + node_iter->idx = key_chunk + 1; + goto update; + } + } - slot = &n16->children[node_iter->idx]; - key_chunk = n16->chunks[node_iter->idx]; - node_iter->idx++; - break; + return NULL; } case RT_NODE_KIND_48: { @@ -2195,6 +2214,7 @@ RT_NODE_ITERATE_NEXT(RT_ITER * iter, int level) } } +update: /* Update the key */ iter->key &= ~(((uint64) RT_CHUNK_MASK) << (level * RT_SPAN)); iter->key |= (((uint64) key_chunk) << (level * RT_SPAN)); @@ -2240,11 +2260,11 @@ RT_ITERATE_NEXT(RT_ITER * iter, uint64 *key_p) iter->cur_level--; iter->node_iters[iter->cur_level].node = node; - iter->node_iters[iter->cur_level].idx = 0; } else { /* Not found the child slot, move up the tree */ + iter->node_iters[iter->cur_level].idx = 0; iter->cur_level++; } } @@ -2998,6 +3018,7 @@ RT_DUMP_NODE(RT_NODE * node) #undef RT_SET_SLOT #undef RT_SET #undef RT_BEGIN_ITERATE +#undef RT_BEGIN_ITERATE_AT #undef RT_ITERATE_NEXT #undef RT_END_ITERATE #undef RT_DELETE diff --git a/src/test/modules/test_radixtree/test_radixtree.c b/src/test/modules/test_radixtree/test_radixtree.c index 787162c8793..a5465a3a2a6 100644 --- a/src/test/modules/test_radixtree/test_radixtree.c +++ b/src/test/modules/test_radixtree/test_radixtree.c @@ -150,6 +150,10 @@ test_empty(void) EXPECT_TRUE(rt_iterate_next(iter, &key) == NULL); rt_end_iterate(iter); + iter = rt_begin_iterate_at(radixtree, 17); + EXPECT_TRUE(rt_iterate_next(iter, &key) == NULL); + rt_end_iterate(iter); + rt_free(radixtree); #ifdef TEST_SHARED_RT @@ -157,7 +161,7 @@ test_empty(void) #endif } -/* Basic set, find, and delete tests */ +/* Basic set, find, delete, and iteration tests */ static void test_basic(rt_node_class_test_elem *test_info, int shift, bool asc) { @@ -265,13 +269,58 @@ test_basic(rt_node_class_test_elem *test_info, int shift, bool asc) rt_end_iterate(iter); + /* test iteration beginning at the largest key */ + { + uint64 largest; + uint64 iterkey; + TestValueType *iterval; + uint64 maxkey = ~UINT64CONST(0); + + /* iteration is ordered by key, so adjust expected value accordingly */ + if (asc) + largest = keys[children - 1]; + else + largest = keys[0]; + + iter = rt_begin_iterate_at(radixtree, largest); + + /* expect the value we started at */ + iterval = rt_iterate_next(iter, &iterkey); + EXPECT_TRUE(iterval != NULL); + EXPECT_EQ_U64(iterkey, largest); + EXPECT_EQ_U64(*iterval, largest); + + /* ...and no more */ + iterval = rt_iterate_next(iter, &iterkey); + EXPECT_TRUE(iterval == NULL); + + rt_end_iterate(iter); + + /* insert maximum key */ + EXPECT_FALSE(rt_set(radixtree, maxkey, (TestValueType *) &maxkey)); + /* begin between orginal largest and max we just inserted */ + Assert(largest + 1 < maxkey); + iter = rt_begin_iterate_at(radixtree, largest + 1); + iterval = rt_iterate_next(iter, &iterkey); + EXPECT_TRUE(iterval != NULL); + EXPECT_EQ_U64(iterkey, maxkey); + EXPECT_EQ_U64(*iterval, maxkey); + rt_end_iterate(iter); + + /* delete maximum key */ + EXPECT_TRUE(rt_delete(radixtree, maxkey)); + iter = rt_begin_iterate_at(radixtree, largest + 1); + iterval = rt_iterate_next(iter, &iterkey); + EXPECT_TRUE(iterval == NULL); + rt_end_iterate(iter); + } + /* delete all keys again */ for (int i = 0; i < children; i++) EXPECT_TRUE(rt_delete(radixtree, keys[i])); /* test that all keys were deleted */ - for (int i = 0; i < children; i++) - EXPECT_TRUE(rt_find(radixtree, keys[i]) == NULL); + EXPECT_TRUE(rt_num_entries(radixtree) == 0); rt_stats(radixtree); -- 2.51.0