[PATCH v5 3/4] salad: introduce bps_tree_delete_identical routine

[Vladimir Davydov]

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 <salad/bps_tree.h>
>  
> @@ -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)
>  {