[PATCH v3 5/7] memtx: rework memtx_tree to store arbitrary nodes

[Vladimir Davydov]

On Fri, Feb 22, 2019 at 06:42:30PM +0300, Kirill Shcherbatov wrote:
> diff --git a/src/box/CMakeLists.txt b/src/box/CMakeLists.txt
> index 5521e489e..dc8cc2cd5 100644
> --- a/src/box/CMakeLists.txt
> +++ b/src/box/CMakeLists.txt
> @@ -64,7 +64,7 @@ add_library(box STATIC
>      index_def.c
>      iterator_type.c
>      memtx_hash.c
> -    memtx_tree.c
> +    memtx_tree_decl.c
>      memtx_rtree.c
>      memtx_bitset.c
>      engine.c
> diff --git a/src/box/memtx_tree.c b/src/box/memtx_tree.c
> index 07d20473f..c48f96bf6 100644
> --- a/src/box/memtx_tree.c
> +++ b/src/box/memtx_tree.c
> @@ -152,25 +303,27 @@ tree_iterator_dummie(struct iterator *iterator, struct tuple **ret)
>  static int
>  tree_iterator_next(struct iterator *iterator, struct tuple **ret)
>  {
> -	struct tuple **res;
> -	struct tree_iterator *it = tree_iterator(iterator);
> -	assert(it->current_tuple != NULL);
> -	struct tuple **check = memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
> -	if (check == NULL || *check != it->current_tuple)
> +	struct tree_iterator *it = tree_iterator_cast(iterator);
> +	assert(MEMTX_TREE_ELEM_GET(&it->current) != NULL);
> +	memtx_tree_elem_t *check =
> +		memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
> +	if (check == NULL || !MEMTX_TREE_IDENTICAL(check, &it->current)) {
>  		it->tree_iterator =
> -			memtx_tree_upper_bound_elem(it->tree, it->current_tuple,
> -						    NULL);
> -	else
> +			memtx_tree_upper_bound_elem(it->tree, it->current, NULL);
> +	} else {
>  		memtx_tree_iterator_next(it->tree, &it->tree_iterator);
> -	tuple_unref(it->current_tuple);
> -	it->current_tuple = NULL;
> -	res = memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
> +	}
> +	tuple_unref(MEMTX_TREE_ELEM_GET(&it->current));
> +	memtx_tree_elem_t *res =
> +		memtx_tree_iterator_get_elem(it->tree, &it->tree_iterator);
>  	if (res == NULL) {
>  		iterator->next = tree_iterator_dummie;
> +		memset(&it->current, 0, sizeof(it->current));

This looks like encapsulation violation. Please either use
MEMTX_TREE_ELEM_SET for this or introduce MEMTX_TREE_ELEM_CLEAR
helper.

> @@ -490,26 +653,50 @@ memtx_tree_index_get(struct index *base, const char *key,
>  	assert(base->def->opts.is_unique &&
>  	       part_count == base->def->key_def->part_count);
>  	struct memtx_tree_index *index = (struct memtx_tree_index *)base;
> -	struct memtx_tree_key_data key_data;
> -	key_data.key = key;
> -	key_data.part_count = part_count;
> -	struct tuple **res = memtx_tree_find(&index->tree, &key_data);
> -	*result = res != NULL ? *res : NULL;
> +	memtx_tree_key_t key_data;
> +	struct key_def *cmp_def = memtx_tree_index_cmp_def(index);
> +	MEMTX_TREE_KEY_SET(&key_data, key, part_count, cmp_def);
> +	memtx_tree_elem_t *res = memtx_tree_find(&index->tree, &key_data);
> +	*result = res != NULL ? MEMTX_TREE_ELEM_GET(res) : NULL;
>  	return 0;
>  }
>  
> +static int
> +memtx_tree_index_insert_tuple(struct index *base, struct tuple *tuple,
> +			      struct tuple **replaced)
> +{
> +	struct memtx_tree_index *index = (struct memtx_tree_index *)base;
> +	memtx_tree_elem_t data;
> +	MEMTX_TREE_ELEM_SET(&data, tuple, index->tree.arg);

How is this going to work for multikey indexes?

> +	memtx_tree_elem_t data_replaced;
> +	memset(&data_replaced, 0, sizeof(data_replaced));
> +	int rc = memtx_tree_insert(&index->tree, data, &data_replaced);
> +	if (replaced != NULL)
> +		*replaced = MEMTX_TREE_ELEM_GET(&data_replaced);
> +	return rc;
> +}
> +
> +static void
> +memtx_tree_index_delete_tuple(struct index *base, struct tuple *tuple)
> +{
> +	struct memtx_tree_index *index = (struct memtx_tree_index *)base;
> +	memtx_tree_elem_t data;
> +	MEMTX_TREE_ELEM_SET(&data, tuple, index->tree.arg);
> +	memtx_tree_delete(&index->tree, data);
> +}
> +
>  static int
>  memtx_tree_index_replace(struct index *base, struct tuple *old_tuple,
>  			 struct tuple *new_tuple, enum dup_replace_mode mode,
>  			 struct tuple **result)
>  {
> -	struct memtx_tree_index *index = (struct memtx_tree_index *)base;
>  	if (new_tuple) {
>  		struct tuple *dup_tuple = NULL;
>  
>  		/* Try to optimistically replace the new_tuple. */
> -		int tree_res = memtx_tree_insert(&index->tree,
> -						 new_tuple, &dup_tuple);
> +		int tree_res =
> +			memtx_tree_index_insert_tuple(base, new_tuple,
> +						      &dup_tuple);
>  		if (tree_res) {
>  			diag_set(OutOfMemory, MEMTX_EXTENT_SIZE,
>  				 "memtx_tree_index", "replace");
> @@ -519,9 +706,9 @@ memtx_tree_index_replace(struct index *base, struct tuple *old_tuple,
>  		uint32_t errcode = replace_check_dup(old_tuple,
>  						     dup_tuple, mode);
>  		if (errcode) {
> -			memtx_tree_delete(&index->tree, new_tuple);
> +			memtx_tree_index_delete_tuple(base, new_tuple);
>  			if (dup_tuple)
> -				memtx_tree_insert(&index->tree, dup_tuple, 0);
> +				memtx_tree_index_insert_tuple(base, dup_tuple, 0);
>  			struct space *sp = space_cache_find(base->def->space_id);
>  			if (sp != NULL)
>  				diag_set(ClientError, errcode, base->def->name,
> @@ -533,9 +720,8 @@ memtx_tree_index_replace(struct index *base, struct tuple *old_tuple,
>  			return 0;
>  		}
>  	}
> -	if (old_tuple) {
> -		memtx_tree_delete(&index->tree, old_tuple);
> -	}
> +	if (old_tuple)
> +		memtx_tree_index_delete_tuple(base, old_tuple);
>  	*result = old_tuple;
>  	return 0;
>  }