From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: From: Kirill Shcherbatov Subject: [PATCH v5 3/4] salad: introduce bps_tree_delete_identical routine Date: Mon, 6 May 2019 14:57:40 +0300 Message-Id: <9a18d47fe9c8f9a8e0bc98de9aec98f8c7723216.1557142159.git.kshcherbatov@tarantool.org> In-Reply-To: References: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit To: tarantool-patches@freelists.org, vdavydov.dev@gmail.com Cc: Kirill Shcherbatov List-ID: A new routine bps_tree_delete_identical performs an element deletion if and only if the found element is identical to the routine argument. Needed for #1257 --- src/box/vy_cache.h | 4 +-- src/box/vy_mem.h | 4 +-- src/lib/salad/bps_tree.h | 35 +++++++++++++++++++++++ test/unit/bps_tree.cc | 60 +++++++++++++++++++++++++++++++++++++++ test/unit/bps_tree.result | 2 ++ 5 files changed, 101 insertions(+), 4 deletions(-) diff --git a/src/box/vy_cache.h b/src/box/vy_cache.h index a04290475..1f0143059 100644 --- a/src/box/vy_cache.h +++ b/src/box/vy_cache.h @@ -97,7 +97,7 @@ vy_cache_tree_key_cmp(struct vy_cache_node *a, struct vy_entry b, #define bps_tree_elem_t struct vy_cache_node * #define bps_tree_key_t struct vy_entry #define bps_tree_arg_t struct key_def * -#define BPS_TREE_NO_DEBUG +#define BPS_TREE_IDENTICAL(a, b) vy_entry_is_equal(a->entry, b->entry) #include "salad/bps_tree.h" @@ -109,7 +109,7 @@ vy_cache_tree_key_cmp(struct vy_cache_node *a, struct vy_entry b, #undef bps_tree_elem_t #undef bps_tree_key_t #undef bps_tree_arg_t -#undef BPS_TREE_NO_DEBUG +#undef BPS_TREE_IDENTICAL /** * Environment of the cache diff --git a/src/box/vy_mem.h b/src/box/vy_mem.h index 7df9a1817..35cca6334 100644 --- a/src/box/vy_mem.h +++ b/src/box/vy_mem.h @@ -121,10 +121,10 @@ vy_mem_tree_cmp_key(struct vy_entry entry, struct vy_mem_tree_key *key, #define BPS_TREE_EXTENT_SIZE VY_MEM_TREE_EXTENT_SIZE #define BPS_TREE_COMPARE(a, b, cmp_def) vy_mem_tree_cmp(a, b, cmp_def) #define BPS_TREE_COMPARE_KEY(a, b, cmp_def) vy_mem_tree_cmp_key(a, b, cmp_def) +#define BPS_TREE_IDENTICAL(a, b) vy_entry_is_equal(a, b) #define bps_tree_elem_t struct vy_entry #define bps_tree_key_t struct vy_mem_tree_key * #define bps_tree_arg_t struct key_def * -#define BPS_TREE_NO_DEBUG #include @@ -136,7 +136,7 @@ vy_mem_tree_cmp_key(struct vy_entry entry, struct vy_mem_tree_key *key, #undef bps_tree_elem_t #undef bps_tree_key_t #undef bps_tree_arg_t -#undef BPS_TREE_NO_DEBUG +#undef BPS_TREE_IDENTICAL /** @endcond false */ diff --git a/src/lib/salad/bps_tree.h b/src/lib/salad/bps_tree.h index 29eb8b81a..71e43e48a 100644 --- a/src/lib/salad/bps_tree.h +++ b/src/lib/salad/bps_tree.h @@ -280,6 +280,7 @@ */ #ifndef BPS_TREE_IDENTICAL #define BPS_TREE_IDENTICAL(a, b) (a == b) +#define BPS_TREE_IDENTICAL_STD 1 #endif /** @@ -360,6 +361,7 @@ typedef uint32_t bps_tree_block_id_t; #define bps_tree_insert _api_name(insert) #define bps_tree_insert_get_iterator _api_name(insert_get_iterator) #define bps_tree_delete _api_name(delete) +#define bps_tree_delete_identical _api_name(delete_identical) #define bps_tree_size _api_name(size) #define bps_tree_mem_used _api_name(mem_used) #define bps_tree_random _api_name(random) @@ -4516,6 +4518,33 @@ bps_tree_delete(struct bps_tree *tree, bps_tree_elem_t elem) return 0; } +/** + * @brief Delete an identical element from a tree (unlike + * bps_tree_delete this routine relies on BPS_TREE_IDENTICAL + * instead of BPS_TREE_COMPARE). + * @param tree - pointer to a tree + * @param elem - the element tot delete + * @return - true on success or false if the element was not found in tree + */ +static inline int +bps_tree_delete_identical(struct bps_tree *tree, bps_tree_elem_t elem) +{ + if (tree->root_id == (bps_tree_block_id_t)(-1)) + return -1; + struct bps_inner_path_elem path[BPS_TREE_MAX_DEPTH]; + struct bps_leaf_path_elem leaf_path_elem; + bool exact; + bps_tree_collect_path(tree, elem, path, &leaf_path_elem, &exact); + + if (!exact) + return -1; + + struct bps_leaf *leaf = leaf_path_elem.block; + if (BPS_TREE_IDENTICAL(leaf->elems[leaf_path_elem.insertion_point], elem)) + bps_tree_process_delete_leaf(tree, &leaf_path_elem); + return 0; +} + /** * @brief Recursively find a maximum element in subtree. * Used only for debug purposes @@ -6054,6 +6083,7 @@ bps_tree_debug_check_internal_functions(bool assertme) #undef bps_tree_find #undef bps_tree_insert #undef bps_tree_delete +#undef bps_tree_delete_identical #undef bps_tree_size #undef bps_tree_mem_used #undef bps_tree_random @@ -6155,4 +6185,9 @@ bps_tree_debug_check_internal_functions(bool assertme) #undef bps_tree_debug_check_move_to_left_inner #undef bps_tree_debug_check_insert_and_move_to_right_inner #undef bps_tree_debug_check_insert_and_move_to_left_inner + +#if defined(BPS_TREE_IDENTICAL_STD) +#undef BPS_TREE_IDENTICAL +#endif + /* }}} */ diff --git a/test/unit/bps_tree.cc b/test/unit/bps_tree.cc index 191dce95a..9132fad69 100644 --- a/test/unit/bps_tree.cc +++ b/test/unit/bps_tree.cc @@ -60,6 +60,46 @@ compare(type_t a, type_t b); #undef bps_tree_key_t #undef bps_tree_arg_t +struct elem_t { + long info; + long marker; +}; + +static bool +equal(const elem_t &a, const elem_t &b) +{ + return a.info == b.info && a.marker == b.marker; +} + +static int compare(const elem_t &a, const elem_t &b) +{ + return a.info < b.info ? -1 : a.info > b.info ? 1 : 0; +} + +static int compare_key(const elem_t &a, long b) +{ + return a.info < b ? -1 : a.info > b ? 1 : 0; +} + +#define BPS_TREE_NAME struct_tree +#define BPS_TREE_BLOCK_SIZE 128 /* value is to low specially for tests */ +#define BPS_TREE_EXTENT_SIZE 2048 /* value is to low specially for tests */ +#define BPS_TREE_IDENTICAL(a, b) equal(a, b) +#define BPS_TREE_COMPARE(a, b, arg) compare(a, b) +#define BPS_TREE_COMPARE_KEY(a, b, arg) compare_key(a, b) +#define bps_tree_elem_t struct elem_t +#define bps_tree_key_t long +#define bps_tree_arg_t int +#include "salad/bps_tree.h" +#undef BPS_TREE_NAME +#undef BPS_TREE_BLOCK_SIZE +#undef BPS_TREE_EXTENT_SIZE +#undef BPS_TREE_COMPARE +#undef BPS_TREE_COMPARE_KEY +#undef bps_tree_elem_t +#undef bps_tree_key_t +#undef bps_tree_arg_t + /* tree for approximate_count test */ #define BPS_TREE_NAME approx #define BPS_TREE_BLOCK_SIZE 128 /* value is to low specially for tests */ @@ -792,6 +832,25 @@ insert_get_iterator() footer(); } +static void +delete_identical_check() +{ + header(); + struct_tree tree; + struct_tree_create(&tree, 0, extent_alloc, extent_free, &extents_count); + struct elem_t e1 = {1, 1}; + struct_tree_insert(&tree, e1, NULL); + struct elem_t e2 = {1, 2}; + struct_tree_delete_identical(&tree, e2); + if (struct_tree_find(&tree, 1) == NULL) + fail("skip the deletion of non-identical element", "false"); + struct_tree_delete_identical(&tree, e1); + if (struct_tree_find(&tree, 1) != NULL) + fail("deletion of identical element completed", "false"); + struct_tree_destroy(&tree); + footer(); +} + int main(void) { @@ -806,4 +865,5 @@ main(void) if (extents_count != 0) fail("memory leak!", "true"); insert_get_iterator(); + delete_identical_check(); } diff --git a/test/unit/bps_tree.result b/test/unit/bps_tree.result index 8e1c3d4b6..dc21bf340 100644 --- a/test/unit/bps_tree.result +++ b/test/unit/bps_tree.result @@ -280,3 +280,5 @@ Count: 10575 *** approximate_count: done *** *** insert_get_iterator *** *** insert_get_iterator: done *** + *** delete_identical_check *** + *** delete_identical_check: done *** -- 2.21.0