diff --git a/src/include/lib/radixtree.h b/src/include/lib/radixtree.h index aca9984ecb..87131cc59b 100644 --- a/src/include/lib/radixtree.h +++ b/src/include/lib/radixtree.h @@ -216,6 +216,9 @@ #define RT_CLASS_16_HI RT_MAKE_NAME(class_32_max) #define RT_CLASS_48 RT_MAKE_NAME(class_48) #define RT_CLASS_256 RT_MAKE_NAME(class_256) +#define RT_VALUE_CALLBACK RT_MAKE_NAME(value_callback) + +typedef void (*RT_VALUE_CALLBACK) (RT_VALUE_TYPE * value, void * caller_data); /* generate forward declarations necessary to use the radix tree */ #ifdef RT_DECLARE @@ -239,7 +242,7 @@ RT_SCOPE RT_RADIX_TREE *RT_CREATE(MemoryContext ctx, Size max_bytes); #endif RT_SCOPE void RT_FREE(RT_RADIX_TREE * tree); -RT_SCOPE RT_VALUE_TYPE *RT_FIND(RT_RADIX_TREE * tree, uint64 key); +RT_SCOPE bool RT_FIND(RT_RADIX_TREE * tree, uint64 key, RT_VALUE_CALLBACK val_callback, void * val_data); #ifdef RT_VARLEN_VALUE RT_SCOPE bool RT_SET(RT_RADIX_TREE * tree, uint64 key, RT_VALUE_TYPE * value_p, @@ -264,7 +267,6 @@ RT_SCOPE void RT_STATS(RT_RADIX_TREE * tree); #endif /* RT_DECLARE */ - /* generate implementation of the radix tree */ #ifdef RT_DEFINE @@ -1018,26 +1020,31 @@ RT_NODE_SEARCH(RT_NODE * node, uint8 chunk) } /* - * Search the given key in the radix tree. Return the pointer to the value if found, - * otherwise return NULL. + * Search the given key in the radix tree. + * If found, execute callback find_cb and return true, + * otherwise return false. * * Since the function returns the slot (to support variable-length values), the caller * needs to maintain control until it's finished with the value. */ -RT_SCOPE RT_VALUE_TYPE * -RT_FIND(RT_RADIX_TREE * tree, uint64 key) +RT_SCOPE bool +RT_FIND(RT_RADIX_TREE * tree, uint64 key, RT_VALUE_CALLBACK val_callback, void * val_data) { RT_NODE_PTR node; RT_PTR_ALLOC *slot = NULL; + RT_VALUE_TYPE *value; int shift; #ifdef RT_SHMEM Assert(tree->ctl->magic == RT_RADIX_TREE_MAGIC); #endif + RT_LOCK_SHARED(tree); + if (!RT_PTR_ALLOC_IS_VALID(tree->ctl->root) || key > tree->ctl->max_val) { - return NULL; + RT_UNLOCK(tree); + return false; } node.alloc = tree->ctl->root; @@ -1050,7 +1057,10 @@ RT_FIND(RT_RADIX_TREE * tree, uint64 key) RT_PTR_SET_LOCAL(tree, &node); slot = RT_NODE_SEARCH(node.local, RT_GET_KEY_CHUNK(key, shift)); if (slot == NULL) - return NULL; + { + RT_UNLOCK(tree); + return false; + } node.alloc = *slot; shift -= RT_SPAN; @@ -1058,13 +1068,19 @@ RT_FIND(RT_RADIX_TREE * tree, uint64 key) if (RT_VALUE_IS_EMBEDDABLE) { - return (RT_VALUE_TYPE *) slot; + value = (RT_VALUE_TYPE *) slot; } else { RT_PTR_SET_LOCAL(tree, &node); - return (RT_VALUE_TYPE *) node.local; + value = (RT_VALUE_TYPE *) node.local; } + + val_callback(value, val_data); + + RT_UNLOCK(tree); + + return true; } /***************** INSERTION *****************/ diff --git a/src/test/modules/test_radixtree/test_radixtree.c b/src/test/modules/test_radixtree/test_radixtree.c index d5ca139b18..64a52276b6 100644 --- a/src/test/modules/test_radixtree/test_radixtree.c +++ b/src/test/modules/test_radixtree/test_radixtree.c @@ -116,10 +116,15 @@ static const test_spec test_specs[] = { #define RT_DEFINE #define RT_USE_DELETE #define RT_VALUE_TYPE TestValueType -/* #define RT_SHMEM */ +#define RT_SHMEM #define RT_DEBUG #include "lib/radixtree.h" +static void +rt_copy_value_callback(TestValueType *value, void * caller_data) +{ + memcpy((TestValueType*) caller_data, value, sizeof(TestValueType)); +} /* * Return the number of keys in the radix tree. @@ -140,6 +145,7 @@ test_empty(void) rt_radix_tree *radixtree; rt_iter *iter; uint64 key; + TestValueType v; TestValueType *val; #ifdef RT_SHMEM @@ -154,13 +160,13 @@ test_empty(void) radixtree = rt_create(CurrentMemoryContext, work_mem); #endif - if (rt_find(radixtree, 0) != NULL) + if (rt_find(radixtree, 0, rt_copy_value_callback, &v)) elog(ERROR, "rt_find on empty tree found a value"); - if (rt_find(radixtree, 1) != NULL) + if (rt_find(radixtree, 1, rt_copy_value_callback, &v)) elog(ERROR, "rt_find on empty tree found a value"); - if (rt_find(radixtree, PG_UINT64_MAX) != NULL) + if (rt_find(radixtree, PG_UINT64_MAX, rt_copy_value_callback, &v)) elog(ERROR, "rt_find on empty tree found a value"); if (rt_delete(radixtree, 0)) @@ -236,15 +242,16 @@ test_basic(int children, int height, bool reverse) /* look up keys */ for (int i = 0; i < children; i++) { - TestValueType *value; + TestValueType value; + bool found; - value = rt_find(radixtree, keys[i]); + found = rt_find(radixtree, keys[i], rt_copy_value_callback, (void *) &value); - if (value == NULL) + if (!found) elog(ERROR, "could not find key 0x" UINT64_HEX_FORMAT, keys[i]); - if (*value != (TestValueType) keys[i]) + if (value != (TestValueType) keys[i]) elog(ERROR, "rt_find returned 0x" UINT64_HEX_FORMAT ", expected " UINT64_HEX_FORMAT, - *value, (TestValueType) keys[i]); + value, (TestValueType) keys[i]); } /* update keys */ @@ -267,14 +274,16 @@ test_basic(int children, int height, bool reverse) /* look up keys after deleting and re-inserting */ for (int i = 0; i < children; i++) { - TestValueType *value; + TestValueType value; + bool found; + + found = rt_find(radixtree, keys[i], rt_copy_value_callback, (void *) &value); - value = rt_find(radixtree, keys[i]); - if (value == NULL) + if (!found) elog(ERROR, "could not find key 0x" UINT64_HEX_FORMAT, keys[i]); - if (*value != (TestValueType) keys[i]) + if (value != (TestValueType) keys[i]) elog(ERROR, "rt_find returned 0x" UINT64_HEX_FORMAT ", expected " UINT64_HEX_FORMAT, - *value, (TestValueType) keys[i]); + value, (TestValueType) keys[i]); } /* iterate over the tree */ @@ -311,10 +320,11 @@ test_basic(int children, int height, bool reverse) } for (int i = 0; i < children; i++) { - TestValueType *value; + TestValueType value; + bool found; - value = rt_find(radixtree, keys[i]); - if (value != NULL) + found = rt_find(radixtree, keys[i], rt_copy_value_callback, (void *) &value); + if (found) elog(ERROR, "found deleted key 0x" UINT64_HEX_FORMAT, keys[i]); } @@ -336,15 +346,17 @@ check_search_on_node(rt_radix_tree *radixtree, uint8 shift, int start, int end) for (int i = start; i <= end; i++) { uint64 key = ((uint64) i << shift); - TestValueType *val; + TestValueType val; + bool found; + + found = rt_find(radixtree, key, rt_copy_value_callback, (void *) &val); - val = rt_find(radixtree, key); - if (val == NULL) + if (!found) elog(ERROR, "key 0x" UINT64_HEX_FORMAT " is not found on node-%d", key, end); - if (*val != (TestValueType) key) + if (val != (TestValueType) key) elog(ERROR, "rt_find with key 0x" UINT64_HEX_FORMAT " returns 0x" UINT64_HEX_FORMAT ", expected 0x" UINT64_HEX_FORMAT, - key, *val, key); + key, val, key); } } @@ -620,7 +632,7 @@ test_pattern(const test_spec * spec) bool found; bool expected; uint64 x; - TestValueType *v; + TestValueType v; /* * Pick next value to probe at random. We limit the probes to the @@ -647,14 +659,13 @@ test_pattern(const test_spec * spec) } /* Is it present according to rt_search() ? */ - v = rt_find(radixtree, x); - found = (v != NULL); + found = rt_find(radixtree, x, rt_copy_value_callback, (void*) &v); if (found != expected) elog(ERROR, "mismatch at 0x" UINT64_HEX_FORMAT ": %d vs %d", x, found, expected); - if (found && (*v != (TestValueType) x)) + if (found && (v != (TestValueType) x)) elog(ERROR, "found 0x" UINT64_HEX_FORMAT ", expected 0x" UINT64_HEX_FORMAT, - *v, x); + v, x); } endtime = GetCurrentTimestamp(); if (rt_test_stats) @@ -715,7 +726,8 @@ test_pattern(const test_spec * spec) for (n = 0; n < 1; n++) { uint64 x; - TestValueType *v; + TestValueType v; + bool found; /* * Pick next value to probe at random. We limit the probes to the @@ -727,15 +739,15 @@ test_pattern(const test_spec * spec) x = pg_prng_uint64_range(&pg_global_prng_state, 0, last_int + 1000); /* Is it present according to rt_find() ? */ - v = rt_find(radixtree, x); + found = rt_find(radixtree, x, rt_copy_value_callback, (void*) &v); - if (!v) + if (!found) continue; /* If the key is found, delete it and check again */ if (!rt_delete(radixtree, x)) elog(ERROR, "could not delete key 0x" UINT64_HEX_FORMAT, x); - if (rt_find(radixtree, x) != NULL) + if (rt_find(radixtree, x, rt_copy_value_callback, (void*) &v)) elog(ERROR, "found deleted key 0x" UINT64_HEX_FORMAT, x); if (rt_delete(radixtree, x)) elog(ERROR, "deleted already-deleted key 0x" UINT64_HEX_FORMAT, x);