From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Date: Mon, 6 May 2019 17:34:45 +0300 From: Vladimir Davydov Subject: Re: [PATCH v5 3/4] salad: introduce bps_tree_delete_identical routine Message-ID: <20190506143445.redgeum66gy7onex@esperanza> References: <9a18d47fe9c8f9a8e0bc98de9aec98f8c7723216.1557142159.git.kshcherbatov@tarantool.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <9a18d47fe9c8f9a8e0bc98de9aec98f8c7723216.1557142159.git.kshcherbatov@tarantool.org> To: Kirill Shcherbatov Cc: tarantool-patches@freelists.org List-ID: On Mon, May 06, 2019 at 02:57:40PM +0300, Kirill Shcherbatov wrote: > 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 This looks ugly. Let's require the caller to always define BPS_TREE_IDENTICAL - it's not a big deal. > #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 I guess it should also return -1 if the element was found but not deleted, in other words it should return 0 iff the element has been deleted. > + */ > +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 > + Could you please reuse the existing tree for the test rather than introducing a new one? > /* 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); Please check the return value as well. > + if (struct_tree_find(&tree, 1) != NULL) > + fail("deletion of identical element completed", "false"); > + struct_tree_destroy(&tree); > + footer(); > +} > + > int > main(void) > {