From: Aleksandr Lyapunov <alyapunov@tarantool.org>
To: Ilya Kosarev <i.kosarev@tarantool.org>,
Nikita Pettik <korablev@tarantool.org>
Cc: tarantool-patches@dev.tarantool.org
Subject: Re: [Tarantool-patches] [PATCH 2/2] memtx: make tuple compare hints optional
Date: Wed, 21 Oct 2020 12:54:12 +0300 [thread overview]
Message-ID: <8f24eadb-ef3c-730a-caad-27b03b1deecd@tarantool.org> (raw)
In-Reply-To: <1603198666.603600853@f437.i.mail.ru>
Actually I remember some problems with bool template parameters..
Now I didn't find them. Changed to bool and everything works fine. thanks!
On 10/20/20 3:57 PM, Ilya Kosarev wrote:
>
>
> Вторник, 20 октября 2020, 15:38 +03:00 от Nikita Pettik
> <korablev@tarantool.org>:
> On 20 Oct 15:34, Ilya Kosarev wrote:
> >
> > Hi,
> >
> > Thanks for the patch!
> >
> > LGTM, i checked for the number of compilers that if with
> the templated
> > agrument is being processed at the compile time so that there
> are no jumps
> > in asm code.
> >
> > What i think is needed is the enum like the following:
> > enum {
> > NOT_HINTED = 0 ,
> > HINTED = 1 ,
> > };
>
> I like this way. Btw why not using just boolean type?
>
> I think there was an idea to implement more than one type of hints.
> Also it doesn’t really matter as far as we have the proper constants.
>
>
> > to avoid using <0> & <1>. If needed i can push such patch to the
> branch.
> > >Понедельник, 19 октября 2020, 12:52 +03:00 от Aleksandr
> Lyapunov <alyapunov@tarantool.org
> </compose?To=alyapunov@tarantool.org>>:
> > >
> > >Since 9fba29abb4e05babb9b23b4413bd8083f0fba933 (memtx:
> introduce tuple
> > >compare hint) memtx tree key data (indexes) started to contain
> extra 8
> > >bytes as a hint. Now it is optional and can be turned off in an
> index
> > >options with "hint = false" entry.
> > >
> > >Closes #4927
> > >
> > >@TarantoolBot document
> > >Title: memtx: optional tuple compare hints
> > >Update the documentation for an index creation to reflect that
> there is
> > >now an option to turn off hints for the index.
> > >---
> > > src/box/index_def.c | 2 +
> > > src/box/index_def.h | 6 +
> > > src/box/lua/schema.lua | 53 ++++
> > > src/box/lua/space.cc | 7 +
> > > src/box/memtx_engine.c | 2 +
> > > src/box/memtx_tree.cc | 599 ++++++++++++++++++++++++------------
> > > src/lib/salad/bps_tree.h | 19 ++
> > > test/box/alter.result | 103 ++++++-
> > > test/box/alter.test.lua | 34 ++
> > > test/box/errinj.result | 3 +-
> > > test/box/tree_pk.result | 314 +++++++++++++++++++
> > > test/box/tree_pk.test.lua | 115 +++++++
> > > test/box/tree_pk_multipart.result | 153 +++++++++
> > > test/box/tree_pk_multipart.test.lua | 64 ++++
> > > 14 files changed, 1269 insertions(+), 205 deletions(-)
> > >
> > >diff --git a/src/box/index_def.c b/src/box/index_def.c
> > >index 9802961..79394b8 100644
> > >--- a/src/box/index_def.c
> > >+++ b/src/box/index_def.c
> > >@@ -51,6 +51,7 @@ const struct index_opts index_opts_default = {
> > > /* .lsn = */ 0,
> > > /* .stat = */ NULL,
> > > /* .func = */ 0,
> > >+ /* .hint = */ true,
> > > };
> > >
> > > const struct opt_def index_opts_reg[] = {
> > >@@ -66,6 +67,7 @@ const struct opt_def index_opts_reg[] = {
> > > OPT_DEF("lsn", OPT_INT64, struct index_opts, lsn),
> > > OPT_DEF("func", OPT_UINT32, struct index_opts, func_id),
> > > OPT_DEF_LEGACY("sql"),
> > >+ OPT_DEF("hint", OPT_BOOL, struct index_opts, hint),
> > > OPT_END,
> > > };
> > >
> > >diff --git a/src/box/index_def.h b/src/box/index_def.h
> > >index d928b23..2180a69 100644
> > >--- a/src/box/index_def.h
> > >+++ b/src/box/index_def.h
> > >@@ -165,6 +165,10 @@ struct index_opts {
> > > struct index_stat *stat;
> > > /** Identifier of the functional index function. */
> > > uint32_t func_id;
> > >+ /**
> > >+ * Use hint optimization for tree index.
> > >+ */
> > >+ bool hint;
> > > };
> > >
> > > extern const struct index_opts index_opts_default;
> > >@@ -211,6 +215,8 @@ index_opts_cmp(const struct index_opts *o1,
> const struct index_opts *o2)
> > > return o1->bloom_fpr < o2->bloom_fpr ? -1 : 1;
> > > if (o1->func_id != o2->func_id)
> > > return o1->func_id - o2->func_id;
> > >+ if (o1->hint != o2->hint)
> > >+ return o1->hint - o2->hint;
> > > return 0;
> > > }
> > >
> > >diff --git a/src/box/lua/schema.lua b/src/box/lua/schema.lua
> > >index 1131af7..9cc1289 100644
> > >--- a/src/box/lua/schema.lua
> > >+++ b/src/box/lua/schema.lua
> > >@@ -1000,8 +1000,31 @@ local index_options = {
> > > page_size = 'number',
> > > bloom_fpr = 'number',
> > > func = 'number, string',
> > >+ hint = 'boolean',
> > > }
> > >
> > >+local function jsonpaths_from_idx_parts(parts)
> > >+ local paths = {}
> > >+
> > >+ for _, part in pairs(parts) do
> > >+ if type(part.path) == 'string' then
> > >+ table.insert(paths, part.path)
> > >+ end
> > >+ end
> > >+
> > >+ return paths
> > >+end
> > >+
> > >+local function is_multikey_index(parts)
> > >+ for _, path in pairs(jsonpaths_from_idx_parts(parts)) do
> > >+ if path:find('[*]', 1, true) then
> > >+ return true
> > >+ end
> > >+ end
> > >+
> > >+ return false
> > >+end
> > >+
> > > --
> > > -- check_param_table() template for alter index,
> > > -- includes all index options.
> > >@@ -1076,6 +1099,15 @@ box.schema.index.create =
> function(space_id, name, options)
> > > options_defaults = {}
> > > end
> > > options = update_param_table(options, options_defaults)
> > >+ if options.hint and
> > >+ (options.type ~= 'tree' or box.space[space_id].engine ~=
> 'memtx') then
> > >+ box.error(box.error.MODIFY_INDEX, name, space.name,
> > >+ "hint is only reasonable with memtx tree index")
> > >+ end
> > >+ if options.hint and options.func then
> > >+ box.error(box.error.MODIFY_INDEX, name, space.name,
> > >+ "functional index can't use hints")
> > >+ end
> > >
> > > local _index = box.space[box.schema.INDEX_ID]
> > > local _vindex = box.space[box.schema.VINDEX_ID]
> > >@@ -1115,6 +1147,7 @@ box.schema.index.create =
> function(space_id, name, options)
> > > run_size_ratio = options.run_size_ratio,
> > > bloom_fpr = options.bloom_fpr,
> > > func = options.func,
> > >+ hint = options.hint,
> > > }
> > > local field_type_aliases = {
> > > num = 'unsigned'; -- Deprecated since 1.7.2
> > >@@ -1135,6 +1168,10 @@ box.schema.index.create =
> function(space_id, name, options)
> > > if parts_can_be_simplified then
> > > parts = simplify_index_parts(parts)
> > > end
> > >+ if options.hint and is_multikey_index(parts) then
> > >+ box.error(box.error.MODIFY_INDEX, name, space.name,
> > >+ "multikey index can't use hints")
> > >+ end
> > > if index_opts.func ~= nil and type(index_opts.func) ==
> 'string' then
> > > index_opts.func = func_id_by_name(index_opts.func)
> > > end
> > >@@ -1253,6 +1290,17 @@ box.schema.index.alter =
> function(space_id, index_id, options)
> > > index_opts[k] = options[k]
> > > end
> > > end
> > >+ if options.hint and
> > >+ (options.type ~= 'tree' or box.space[space_id].engine ~=
> 'memtx') then
> > >+ box.error(box.error.MODIFY_INDEX, space.index[index_id].name,
> > >+ space.name,
> > >+ "hint is only reasonable with memtx tree index")
> > >+ end
> > >+ if options.hint and options.func then
> > >+ box.error(box.error.MODIFY_INDEX, space.index[index_id].name,
> > >+ space.name,
> > >+ "functional index can't use hints")
> > >+ end
> > > if options.parts then
> > > local parts_can_be_simplified
> > > parts, parts_can_be_simplified =
> > >@@ -1262,6 +1310,11 @@ box.schema.index.alter =
> function(space_id, index_id, options)
> > > parts = simplify_index_parts(parts)
> > > end
> > > end
> > >+ if options.hint and is_multikey_index(parts) then
> > >+ box.error(box.error.MODIFY_INDEX, space.index[index_id].name,
> > >+ space.name,
> > >+ "multikey index can't use hints")
> > >+ end
> > > if index_opts.func ~= nil and type(index_opts.func) ==
> 'string' then
> > > index_opts.func = func_id_by_name(index_opts.func)
> > > end
> > >diff --git a/src/box/lua/space.cc b/src/box/lua/space.cc
> > >index 177c588..1ea993c 100644
> > >--- a/src/box/lua/space.cc
> > >+++ b/src/box/lua/space.cc
> > >@@ -344,6 +344,13 @@ lbox_fillspace(struct lua_State *L, struct
> space *space, int i)
> > > lua_pushnumber(L, index_opts->dimension);
> > > lua_setfield(L, -2, "dimension");
> > > }
> > >+ if (space_is_memtx(space) && index_def->type == TREE) {
> > >+ lua_pushboolean(L, index_opts->hint);
> > >+ lua_setfield(L, -2, "hint");
> > >+ } else {
> > >+ lua_pushnil(L);
> > >+ lua_setfield(L, -2, "hint");
> > >+ }
> > >
> > > if (index_opts->func_id > 0) {
> > > lua_pushstring(L, "func");
> > >diff --git a/src/box/memtx_engine.c b/src/box/memtx_engine.c
> > >index 8147557 ..43000ba 100644
> > >--- a/src/box/memtx_engine.c
> > >+++ b/src/box/memtx_engine.c
> > >@@ -1398,6 +1398,8 @@
> memtx_index_def_change_requires_rebuild(struct index *index,
> > > return true;
> > > if (old_def->opts.func_id != new_def->opts.func_id)
> > > return true;
> > >+ if (old_def->opts.hint != new_def->opts.hint)
> > >+ return true;
> > >
> > > const struct key_def *old_cmp_def, *new_cmp_def;
> > > if (index_depends_on_pk(index)) {
> > >diff --git a/src/box/memtx_tree.cc b/src/box/memtx_tree.cc
> > >index d3b993b..17d58c5 100644
> > >--- a/src/box/memtx_tree.cc
> > >+++ b/src/box/memtx_tree.cc
> > >@@ -45,23 +45,51 @@
> > > /**
> > > * Struct that is used as a key in BPS tree definition.
> > > */
> > >-struct memtx_tree_key_data {
> > >+struct memtx_tree_key_data_common {
> > > /** Sequence of msgpacked search fields. */
> > > const char *key;
> > > /** Number of msgpacked search fields. */
> > > uint32_t part_count;
> > >+};
> > >+
> > >+template <int USE_HINT>
> > >+struct memtx_tree_key_data;
> > >+
> > >+template <>
> > >+struct memtx_tree_key_data<0> : memtx_tree_key_data_common {
> > >+ static constexpr hint_t hint = HINT_NONE;
> > >+ void set_hint(hint_t) { assert(false); }
> > >+};
> > >+
> > >+template <>
> > >+struct memtx_tree_key_data<1> : memtx_tree_key_data_common {
> > > /** Comparison hint, see tuple_hint(). */
> > > hint_t hint;
> > >+ void set_hint(hint_t h) { hint = h; }
> > > };
> > >
> > > /**
> > > * Struct that is used as a elem in BPS tree definition.
> > > */
> > >-struct memtx_tree_data {
> > >+struct memtx_tree_data_common {
> > > /* Tuple that this node is represents. */
> > > struct tuple *tuple;
> > >+};
> > >+
> > >+template <int USE_HINT>
> > >+struct memtx_tree_data;
> > >+
> > >+template <>
> > >+struct memtx_tree_data<0> : memtx_tree_data_common {
> > >+ static constexpr hint_t hint = HINT_NONE;
> > >+ void set_hint(hint_t) { assert(false); }
> > >+};
> > >+
> > >+template <>
> > >+struct memtx_tree_data<1> : memtx_tree_data<0> {
> > > /** Comparison hint, see key_hint(). */
> > > hint_t hint;
> > >+ void set_hint(hint_t h) { hint = h; }
> > > };
> > >
> > > /**
> > >@@ -73,8 +101,8 @@ struct memtx_tree_data {
> > > * @retval false - Otherwise.
> > > */
> > > static bool
> > >-memtx_tree_data_is_equal(const struct memtx_tree_data *a,
> > >- const struct memtx_tree_data *b)
> > >+memtx_tree_data_is_equal(const struct memtx_tree_data_common *a,
> > >+ const struct memtx_tree_data_common *b)
> > > {
> > > return a->tuple == b->tuple;
> > > }
> > >@@ -89,12 +117,28 @@ memtx_tree_data_is_equal(const struct
> memtx_tree_data *a,
> > > (b)->part_count, (b)->hint, arg)
> > > #define BPS_TREE_IS_IDENTICAL(a, b)
> memtx_tree_data_is_equal(&a, &b)
> > > #define BPS_TREE_NO_DEBUG 1
> > >-#define bps_tree_elem_t struct memtx_tree_data
> > >-#define bps_tree_key_t struct memtx_tree_key_data *
> > > #define bps_tree_arg_t struct key_def *
> > >
> > >+#define BPS_TREE_NAMESPACE NS_NO_HINT
> > >+#define bps_tree_elem_t struct memtx_tree_data<0>
> > >+#define bps_tree_key_t struct memtx_tree_key_data<0> *
> > >+
> > > #include "salad/bps_tree.h"
> > >
> > >+#undef BPS_TREE_NAMESPACE
> > >+#undef bps_tree_elem_t
> > >+#undef bps_tree_key_t
> > >+
> > >+#define BPS_TREE_NAMESPACE NS_USE_HINT
> > >+#define bps_tree_elem_t struct memtx_tree_data<1>
> > >+#define bps_tree_key_t struct memtx_tree_key_data<1> *
> > >+
> > >+#include "salad/bps_tree.h"
> > >+
> > >+#undef BPS_TREE_NAMESPACE
> > >+#undef bps_tree_elem_t
> > >+#undef bps_tree_key_t
> > >+
> > > #undef BPS_TREE_NAME
> > > #undef BPS_TREE_BLOCK_SIZE
> > > #undef BPS_TREE_EXTENT_SIZE
> > >@@ -102,66 +146,119 @@ memtx_tree_data_is_equal(const struct
> memtx_tree_data *a,
> > > #undef BPS_TREE_COMPARE_KEY
> > > #undef BPS_TREE_IS_IDENTICAL
> > > #undef BPS_TREE_NO_DEBUG
> > >-#undef bps_tree_elem_t
> > >-#undef bps_tree_key_t
> > > #undef bps_tree_arg_t
> > >
> > >+using namespace NS_NO_HINT;
> > >+using namespace NS_USE_HINT;
> > >+
> > >+template <int USE_HINT>
> > >+struct memtx_tree_selector;
> > >+
> > >+template <>
> > >+struct memtx_tree_selector<0> : NS_NO_HINT::memtx_tree {};
> > >+
> > >+template <>
> > >+struct memtx_tree_selector<1> : NS_USE_HINT::memtx_tree {};
> > >+
> > >+template <int USE_HINT>
> > >+using memtx_tree_t = struct memtx_tree_selector<USE_HINT>;
> > >+
> > >+template <int USE_HINT>
> > >+struct memtx_tree_iterator_selector;
> > >+
> > >+template <>
> > >+struct memtx_tree_iterator_selector<0> {
> > >+ using type = NS_NO_HINT::memtx_tree_iterator;
> > >+};
> > >+
> > >+template <>
> > >+struct memtx_tree_iterator_selector<1> {
> > >+ using type = NS_USE_HINT::memtx_tree_iterator;
> > >+};
> > >+
> > >+template <int USE_HINT>
> > >+using memtx_tree_iterator_t = typename
> memtx_tree_iterator_selector<USE_HINT>::type;
> > >+
> > >+static void
> > >+invalidate_tree_iterator(NS_NO_HINT::memtx_tree_iterator *itr)
> > >+{
> > >+ *itr = NS_NO_HINT::memtx_tree_invalid_iterator();
> > >+}
> > >+
> > >+static void
> > >+invalidate_tree_iterator(NS_USE_HINT::memtx_tree_iterator *itr)
> > >+{
> > >+ *itr = NS_USE_HINT::memtx_tree_invalid_iterator();
> > >+}
> > >+
> > >+template <int USE_HINT>
> > > struct memtx_tree_index {
> > > struct index base;
> > >- struct memtx_tree tree;
> > >- struct memtx_tree_data *build_array;
> > >+ memtx_tree_t<USE_HINT> tree;
> > >+ struct memtx_tree_data<USE_HINT> *build_array;
> > > size_t build_array_size, build_array_alloc_size;
> > > struct memtx_gc_task gc_task;
> > >- struct memtx_tree_iterator gc_iterator;
> > >+ memtx_tree_iterator_t<USE_HINT> gc_iterator;
> > > };
> > >
> > > /* {{{ Utilities.
> *************************************************/
> > >
> > >+template <class TREE>
> > > static inline struct key_def *
> > >-memtx_tree_cmp_def(struct memtx_tree *tree)
> > >+memtx_tree_cmp_def(TREE *tree)
> > > {
> > > return tree->arg;
> > > }
> > >
> > >+template <int USE_HINT>
> > > static int
> > > memtx_tree_qcompare(const void* a, const void *b, void *c)
> > > {
> > >- const struct memtx_tree_data *data_a = (struct
> memtx_tree_data *)a;
> > >- const struct memtx_tree_data *data_b = (struct
> memtx_tree_data *)b;
> > >+ const struct memtx_tree_data<USE_HINT> *data_a =
> > >+ (struct memtx_tree_data<USE_HINT> *)a;
> > >+ const struct memtx_tree_data<USE_HINT> *data_b =
> > >+ (struct memtx_tree_data<USE_HINT> *)b;
> > > struct key_def *key_def = (struct key_def *)c;
> > > return tuple_compare(data_a->tuple, data_a->hint, data_b->tuple,
> > > data_b->hint, key_def);
> > > }
> > >
> > > /* {{{ MemtxTree Iterators
> ****************************************/
> > >+template <int USE_HINT>
> > > struct tree_iterator {
> > > struct iterator base;
> > >- struct memtx_tree_iterator tree_iterator;
> > >+ memtx_tree_iterator_t<USE_HINT> tree_iterator;
> > > enum iterator_type type;
> > >- struct memtx_tree_key_data key_data;
> > >- struct memtx_tree_data current;
> > >+ struct memtx_tree_key_data<USE_HINT> key_data;
> > >+ struct memtx_tree_data<USE_HINT> current;
> > > /** Memory pool the iterator was allocated from. */
> > > struct mempool *pool;
> > > };
> > >
> > >-static_assert(sizeof(struct tree_iterator) <= MEMTX_ITERATOR_SIZE,
> > >- "sizeof(struct tree_iterator) must be less than or equal "
> > >+static_assert(sizeof(struct tree_iterator<0>) <=
> MEMTX_ITERATOR_SIZE,
> > >+ "sizeof(struct tree_iterator<0>) must be less than or equal "
> > >+ "to MEMTX_ITERATOR_SIZE");
> > >+static_assert(sizeof(struct tree_iterator<1>) <=
> MEMTX_ITERATOR_SIZE,
> > >+ "sizeof(struct tree_iterator<1>) must be less than or equal "
> > > "to MEMTX_ITERATOR_SIZE");
> > >
> > >+template <int USE_HINT>
> > > static void
> > > tree_iterator_free(struct iterator *iterator);
> > >
> > >-static inline struct tree_iterator *
> > >-tree_iterator(struct iterator *it)
> > >+template <int USE_HINT>
> > >+static inline struct tree_iterator<USE_HINT> *
> > >+get_tree_iterator(struct iterator *it)
> > > {
> > >- assert(it->free == tree_iterator_free);
> > >- return (struct tree_iterator *) it;
> > >+ assert(it->free == &tree_iterator_free<USE_HINT>);
> > >+ return (struct tree_iterator<USE_HINT> *) it;
> > > }
> > >
> > >+template <int USE_HINT>
> > > static void
> > > tree_iterator_free(struct iterator *iterator)
> > > {
> > >- struct tree_iterator *it = tree_iterator(iterator);
> > >+ struct tree_iterator<USE_HINT> *it =
> get_tree_iterator<USE_HINT>(iterator);
> > > struct tuple *tuple = it->current.tuple;
> > > if (tuple != NULL)
> > > tuple_unref(tuple);
> > >@@ -176,14 +273,15 @@ tree_iterator_dummie(struct iterator
> *iterator, struct tuple **ret)
> > > return 0;
> > > }
> > >
> > >+template <int USE_HINT>
> > > static int
> > > tree_iterator_next_base(struct iterator *iterator, struct
> tuple **ret)
> > > {
> > >- struct memtx_tree_index *index =
> > >- (struct memtx_tree_index *)iterator->index;
> > >- struct tree_iterator *it = tree_iterator(iterator);
> > >+ struct memtx_tree_index<USE_HINT> *index =
> > >+ (struct memtx_tree_index<USE_HINT> *)iterator->index;
> > >+ struct tree_iterator<USE_HINT> *it =
> get_tree_iterator<USE_HINT>(iterator);
> > > assert(it->current.tuple != NULL);
> > >- struct memtx_tree_data *check =
> > >+ struct memtx_tree_data<USE_HINT> *check =
> > > memtx_tree_iterator_get_elem(&index->tree, &it->tree_iterator);
> > > if (check == NULL || !memtx_tree_data_is_equal(check,
> &it->current)) {
> > > it->tree_iterator = memtx_tree_upper_bound_elem(&index->tree,
> > >@@ -192,7 +290,7 @@ tree_iterator_next_base(struct iterator
> *iterator, struct tuple **ret)
> > > memtx_tree_iterator_next(&index->tree, &it->tree_iterator);
> > > }
> > > tuple_unref(it->current.tuple);
> > >- struct memtx_tree_data *res =
> > >+ struct memtx_tree_data<USE_HINT> *res =
> > > memtx_tree_iterator_get_elem(&index->tree, &it->tree_iterator);
> > > if (res == NULL) {
> > > iterator->next = tree_iterator_dummie;
> > >@@ -206,14 +304,15 @@ tree_iterator_next_base(struct iterator
> *iterator, struct tuple **ret)
> > > return 0;
> > > }
> > >
> > >+template <int USE_HINT>
> > > static int
> > > tree_iterator_prev_base(struct iterator *iterator, struct
> tuple **ret)
> > > {
> > >- struct memtx_tree_index *index =
> > >- (struct memtx_tree_index *)iterator->index;
> > >- struct tree_iterator *it = tree_iterator(iterator);
> > >+ struct memtx_tree_index<USE_HINT> *index =
> > >+ (struct memtx_tree_index<USE_HINT> *)iterator->index;
> > >+ struct tree_iterator<USE_HINT> *it =
> get_tree_iterator<USE_HINT>(iterator);
> > > assert(it->current.tuple != NULL);
> > >- struct memtx_tree_data *check =
> > >+ struct memtx_tree_data<USE_HINT> *check =
> > > memtx_tree_iterator_get_elem(&index->tree, &it->tree_iterator);
> > > if (check == NULL || !memtx_tree_data_is_equal(check,
> &it->current)) {
> > > it->tree_iterator = memtx_tree_lower_bound_elem(&index->tree,
> > >@@ -221,7 +320,7 @@ tree_iterator_prev_base(struct iterator
> *iterator, struct tuple **ret)
> > > }
> > > memtx_tree_iterator_prev(&index->tree, &it->tree_iterator);
> > > tuple_unref(it->current.tuple);
> > >- struct memtx_tree_data *res =
> > >+ struct memtx_tree_data<USE_HINT> *res =
> > > memtx_tree_iterator_get_elem(&index->tree, &it->tree_iterator);
> > > if (!res) {
> > > iterator->next = tree_iterator_dummie;
> > >@@ -235,14 +334,15 @@ tree_iterator_prev_base(struct iterator
> *iterator, struct tuple **ret)
> > > return 0;
> > > }
> > >
> > >+template <int USE_HINT>
> > > static int
> > > tree_iterator_next_equal_base(struct iterator *iterator,
> struct tuple **ret)
> > > {
> > >- struct memtx_tree_index *index =
> > >- (struct memtx_tree_index *)iterator->index;
> > >- struct tree_iterator *it = tree_iterator(iterator);
> > >+ struct memtx_tree_index<USE_HINT> *index =
> > >+ (struct memtx_tree_index<USE_HINT> *)iterator->index;
> > >+ struct tree_iterator<USE_HINT> *it =
> get_tree_iterator<USE_HINT>(iterator);
> > > assert(it->current.tuple != NULL);
> > >- struct memtx_tree_data *check =
> > >+ struct memtx_tree_data<USE_HINT> *check =
> > > memtx_tree_iterator_get_elem(&index->tree, &it->tree_iterator);
> > > if (check == NULL || !memtx_tree_data_is_equal(check,
> &it->current)) {
> > > it->tree_iterator = memtx_tree_upper_bound_elem(&index->tree,
> > >@@ -251,7 +351,7 @@ tree_iterator_next_equal_base(struct
> iterator *iterator, struct tuple **ret)
> > > memtx_tree_iterator_next(&index->tree, &it->tree_iterator);
> > > }
> > > tuple_unref(it->current.tuple);
> > >- struct memtx_tree_data *res =
> > >+ struct memtx_tree_data<USE_HINT> *res =
> > > memtx_tree_iterator_get_elem(&index->tree, &it->tree_iterator);
> > > /* Use user key def to save a few loops. */
> > > if (res == NULL ||
> > >@@ -271,14 +371,15 @@ tree_iterator_next_equal_base(struct
> iterator *iterator, struct tuple **ret)
> > > return 0;
> > > }
> > >
> > >+template <int USE_HINT>
> > > static int
> > > tree_iterator_prev_equal_base(struct iterator *iterator,
> struct tuple **ret)
> > > {
> > >- struct memtx_tree_index *index =
> > >- (struct memtx_tree_index *)iterator->index;
> > >- struct tree_iterator *it = tree_iterator(iterator);
> > >+ struct memtx_tree_index<USE_HINT> *index =
> > >+ (struct memtx_tree_index<USE_HINT> *)iterator->index;
> > >+ struct tree_iterator<USE_HINT> *it =
> get_tree_iterator<USE_HINT>(iterator);
> > > assert(it->current.tuple != NULL);
> > >- struct memtx_tree_data *check =
> > >+ struct memtx_tree_data<USE_HINT> *check =
> > > memtx_tree_iterator_get_elem(&index->tree, &it->tree_iterator);
> > > if (check == NULL || !memtx_tree_data_is_equal(check,
> &it->current)) {
> > > it->tree_iterator = memtx_tree_lower_bound_elem(&index->tree,
> > >@@ -286,7 +387,7 @@ tree_iterator_prev_equal_base(struct
> iterator *iterator, struct tuple **ret)
> > > }
> > > memtx_tree_iterator_prev(&index->tree, &it->tree_iterator);
> > > tuple_unref(it->current.tuple);
> > >- struct memtx_tree_data *res =
> > >+ struct memtx_tree_data<USE_HINT> *res =
> > > memtx_tree_iterator_get_elem(&index->tree, &it->tree_iterator);
> > > /* Use user key def to save a few loops. */
> > > if (res == NULL ||
> > >@@ -307,28 +408,30 @@ tree_iterator_prev_equal_base(struct
> iterator *iterator, struct tuple **ret)
> > > }
> > >
> > > #define WRAP_ITERATOR_METHOD(name) \
> > >+template <int USE_HINT> \
> > > static int \
> > > name(struct iterator *iterator, struct tuple **ret) \
> > > { \
> > >- struct memtx_tree *tree = \
> > >- &((struct memtx_tree_index *)iterator->index)->tree; \
> > >- struct tree_iterator *it = tree_iterator(iterator); \
> > >- struct memtx_tree_iterator *ti = &it->tree_iterator; \
> > >+ memtx_tree_t<USE_HINT> *tree = \
> > >+ &((struct memtx_tree_index<USE_HINT> *)iterator->index)->tree; \
> > >+ struct tree_iterator<USE_HINT> *it = \
> > >+ get_tree_iterator<USE_HINT>(iterator); \
> > >+ memtx_tree_iterator_t<USE_HINT> *ti = &it->tree_iterator; \
> > > uint32_t iid = iterator->index->def->iid; \
> > > bool is_multikey = iterator->index->def->key_def->is_multikey; \
> > > struct txn *txn = in_txn(); \
> > > struct space *space = space_by_id(iterator->space_id); \
> > > bool is_rw = txn != NULL; \
> > > do { \
> > >- int rc = name##_base(iterator, ret); \
> > >+ int rc = name##_base<USE_HINT>(iterator, ret); \
> > > if (rc != 0 || *ret == NULL) \
> > > return rc; \
> > > uint32_t mk_index = 0; \
> > > if (is_multikey) { \
> > >- struct memtx_tree_data *check = \
> > >+ struct memtx_tree_data<USE_HINT> *check = \
> > > memtx_tree_iterator_get_elem(tree, ti); \
> > > assert(check != NULL); \
> > >- mk_index = check->hint; \
> > >+ mk_index = (uint32_t)check->hint; \
> > > } \
> > > *ret = memtx_tx_tuple_clarify(txn, space, *ret, \
> > > iid, mk_index, is_rw); \
> > >@@ -347,27 +450,28 @@
> WRAP_ITERATOR_METHOD(tree_iterator_prev_equal);
> > >
> > > #undef WRAP_ITERATOR_METHOD
> > >
> > >+template <int USE_HINT>
> > > static void
> > >-tree_iterator_set_next_method(struct tree_iterator *it)
> > >+tree_iterator_set_next_method(struct tree_iterator<USE_HINT> *it)
> > > {
> > > assert(it->current.tuple != NULL);
> > > switch (it->type) {
> > > case ITER_EQ:
> > >- it->base.next = tree_iterator_next_equal;
> > >+ it->base.next = tree_iterator_next_equal<USE_HINT>;
> > > break;
> > > case ITER_REQ:
> > >- it->base.next = tree_iterator_prev_equal;
> > >+ it->base.next = tree_iterator_prev_equal<USE_HINT>;
> > > break;
> > > case ITER_ALL:
> > >- it->base.next = tree_iterator_next;
> > >+ it->base.next = tree_iterator_next<USE_HINT>;
> > > break;
> > > case ITER_LT:
> > > case ITER_LE:
> > >- it->base.next = tree_iterator_prev;
> > >+ it->base.next = tree_iterator_prev<USE_HINT>;
> > > break;
> > > case ITER_GE:
> > > case ITER_GT:
> > >- it->base.next = tree_iterator_next;
> > >+ it->base.next = tree_iterator_next<USE_HINT>;
> > > break;
> > > default:
> > > /* The type was checked in initIterator */
> > >@@ -375,15 +479,16 @@ tree_iterator_set_next_method(struct
> tree_iterator *it)
> > > }
> > > }
> > >
> > >+template <int USE_HINT>
> > > static int
> > > tree_iterator_start(struct iterator *iterator, struct tuple **ret)
> > > {
> > > *ret = NULL;
> > >- struct memtx_tree_index *index =
> > >- (struct memtx_tree_index *)iterator->index;
> > >- struct tree_iterator *it = tree_iterator(iterator);
> > >+ struct memtx_tree_index<USE_HINT> *index =
> > >+ (struct memtx_tree_index<USE_HINT> *)iterator->index;
> > >+ struct tree_iterator<USE_HINT> *it =
> get_tree_iterator<USE_HINT>(iterator);
> > > it->base.next = tree_iterator_dummie;
> > >- struct memtx_tree *tree = &index->tree;
> > >+ memtx_tree_t<USE_HINT> *tree = &index->tree;
> > >�� enum iterator_type type = it->type;
> > > bool exact = false;
> > > assert(it->current.tuple == NULL);
> > >@@ -423,8 +528,8 @@ tree_iterator_start(struct iterator
> *iterator, struct tuple **ret)
> > > }
> > > }
> > >
> > >- struct memtx_tree_data *res = memtx_tree_iterator_get_elem(tree,
> > >- &it->tree_iterator);
> > >+ struct memtx_tree_data<USE_HINT> *res =
> > >+ memtx_tree_iterator_get_elem(tree, &it->tree_iterator);
> > > if (!res)
> > > return 0;
> > > *ret = res->tuple;
> > >@@ -454,14 +559,16 @@ tree_iterator_start(struct iterator
> *iterator, struct tuple **ret)
> > >
> > > /* {{{ MemtxTree
> **********************************************************/
> > >
> > >+template <int USE_HINT>
> > > static void
> > >-memtx_tree_index_free(struct memtx_tree_index *index)
> > >+memtx_tree_index_free(struct memtx_tree_index<USE_HINT> *index)
> > > {
> > > memtx_tree_destroy(&index->tree);
> > > free(index->build_array);
> > > free(index);
> > > }
> > >
> > >+template <int USE_HINT>
> > > static void
> > > memtx_tree_index_gc_run(struct memtx_gc_task *task, bool *done)
> > > {
> > >@@ -475,14 +582,14 @@ memtx_tree_index_gc_run(struct
> memtx_gc_task *task, bool *done)
> > > enum { YIELD_LOOPS = 10 };
> > > #endif
> > >
> > >- struct memtx_tree_index *index = container_of(task,
> > >- struct memtx_tree_index, gc_task);
> > >- struct memtx_tree *tree = &index->tree;
> > >- struct memtx_tree_iterator *itr = &index->gc_iterator;
> > >+ struct memtx_tree_index<USE_HINT> *index = container_of(task,
> > >+ struct memtx_tree_index<USE_HINT>, gc_task);
> > >+ memtx_tree_t<USE_HINT> *tree = &index->tree;
> > >+ memtx_tree_iterator_t<USE_HINT> *itr = &index->gc_iterator;
> > >
> > > unsigned int loops = 0;
> > > while (!memtx_tree_iterator_is_invalid(itr)) {
> > >- struct memtx_tree_data *res =
> > >+ struct memtx_tree_data<USE_HINT> *res =
> > > memtx_tree_iterator_get_elem(tree, itr);
> > > memtx_tree_iterator_next(tree, itr);
> > > tuple_unref(res->tuple);
> > >@@ -494,23 +601,32 @@ memtx_tree_index_gc_run(struct
> memtx_gc_task *task, bool *done)
> > > *done = true;
> > > }
> > >
> > >+template <int USE_HINT>
> > > static void
> > > memtx_tree_index_gc_free(struct memtx_gc_task *task)
> > > {
> > >- struct memtx_tree_index *index = container_of(task,
> > >- struct memtx_tree_index, gc_task);
> > >+ struct memtx_tree_index<USE_HINT> *index = container_of(task,
> > >+ struct memtx_tree_index<USE_HINT>, gc_task);
> > > memtx_tree_index_free(index);
> > > }
> > >
> > >-static const struct memtx_gc_task_vtab
> memtx_tree_index_gc_vtab = {
> > >- .run = memtx_tree_index_gc_run,
> > >- .free = memtx_tree_index_gc_free,
> > >+template <int USE_HINT>
> > >+static struct memtx_gc_task_vtab * get_memtx_tree_index_gc_vtab()
> > >+{
> > >+ static memtx_gc_task_vtab tab =
> > >+ {
> > >+ .run = memtx_tree_index_gc_run<USE_HINT>,
> > >+ .free = memtx_tree_index_gc_free<USE_HINT>,
> > >+ };
> > >+ return &tab;
> > > };
> > >
> > >+template <int USE_HINT>
> > > static void
> > > memtx_tree_index_destroy(struct index *base)
> > > {
> > >- struct memtx_tree_index *index = (struct memtx_tree_index *)base;
> > >+ struct memtx_tree_index<USE_HINT> *index =
> > >+ (struct memtx_tree_index<USE_HINT> *)base;
> > > struct memtx_engine *memtx = (struct memtx_engine *)base->engine;
> > > if (base->def->iid == 0) {
> > > /*
> > >@@ -518,7 +634,7 @@ memtx_tree_index_destroy(struct index *base)
> > > * in the index, which may take a while. Schedule a
> > > * background task in order not to block tx thread.
> > > */
> > >- index->gc_task.vtab = &memtx_tree_index_gc_vtab;
> > >+ index->gc_task.vtab = get_memtx_tree_index_gc_vtab<USE_HINT>();
> > > index->gc_iterator = memtx_tree_iterator_first(&index->tree);
> > > memtx_engine_schedule_gc(memtx, &index->gc_task);
> > > } else {
> > >@@ -530,10 +646,12 @@ memtx_tree_index_destroy(struct index *base)
> > > }
> > > }
> > >
> > >+template <int USE_HINT>
> > > static void
> > > memtx_tree_index_update_def(struct index *base)
> > > {
> > >- struct memtx_tree_index *index = (struct memtx_tree_index *)base;
> > >+ struct memtx_tree_index<USE_HINT> *index =
> > >+ (struct memtx_tree_index<USE_HINT> *)base;
> > > struct index_def *def = base->def;
> > > /*
> > > * We use extended key def for non-unique and nullable
> > >@@ -553,51 +671,62 @@ memtx_tree_index_depends_on_pk(struct
> index *base)
> > > return !def->opts.is_unique || def->key_def->is_nullable;
> > > }
> > >
> > >+template <int USE_HINT>
> > > static ssize_t
> > > memtx_tree_index_size(struct index *base)
> > > {
> > >- struct memtx_tree_index *index = (struct memtx_tree_index *)base;
> > >+ struct memtx_tree_index<USE_HINT> *index =
> > >+ (struct memtx_tree_index<USE_HINT> *)base;
> > > return memtx_tree_size(&index->tree);
> > > }
> > >
> > >+template <int USE_HINT>
> > > static ssize_t
> > > memtx_tree_index_bsize(struct index *base)
> > > {
> > >- struct memtx_tree_index *index = (struct memtx_tree_index *)base;
> > >+ struct memtx_tree_index<USE_HINT> *index =
> > >+ (struct memtx_tree_index<USE_HINT> *)base;
> > > return memtx_tree_mem_used(&index->tree);
> > > }
> > >
> > >+template <int USE_HINT>
> > > static int
> > > memtx_tree_index_random(struct index *base, uint32_t rnd,
> struct tuple **result)
> > > {
> > >- struct memtx_tree_index *index = (struct memtx_tree_index *)base;
> > >- struct memtx_tree_data *res = memtx_tree_random(&index->tree,
> rnd);
> > >+ struct memtx_tree_index<USE_HINT> *index =
> > >+ (struct memtx_tree_index<USE_HINT> *)base;
> > >+ struct memtx_tree_data<USE_HINT> *res =
> memtx_tree_random(&index->tree, rnd);
> > > *result = res != NULL ? res->tuple : NULL;
> > > return 0;
> > > }
> > >
> > >+template <int USE_HINT>
> > > static ssize_t
> > > memtx_tree_index_count(struct index *base, enum iterator_type
> type,
> > > const char *key, uint32_t part_count)
> > > {
> > > if (type == ITER_ALL)
> > >- return memtx_tree_index_size(base); /* optimization */
> > >+ return memtx_tree_index_size<USE_HINT>(base); /* optimization */
> > > return generic_index_count(base, type, key, part_count);
> > > }
> > >
> > >+template <int USE_HINT>
> > > static int
> > > memtx_tree_index_get(struct index *base, const char *key,
> > > uint32_t part_count, struct tuple **result)
> > > {
> > > 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_index<USE_HINT> *index =
> > >+ (struct memtx_tree_index<USE_HINT> *)base;
> > > struct key_def *cmp_def = memtx_tree_cmp_def(&index->tree);
> > >- struct memtx_tree_key_data key_data;
> > >+ struct memtx_tree_key_data<USE_HINT> key_data;
> > > key_data.key = key;
> > > key_data.part_count = part_count;
> > >- key_data.hint = key_hint(key, part_count, cmp_def);
> > >- struct memtx_tree_data *res = memtx_tree_find(&index->tree,
> &key_data);
> > >+ if (USE_HINT)
> > >+ key_data.set_hint(key_hint(key, part_count, cmp_def));
> > >+ struct memtx_tree_data<USE_HINT> *res =
> > >+ memtx_tree_find(&index->tree, &key_data);
> > > if (res == NULL) {
> > > *result = NULL;
> > > return 0;
> > >@@ -611,18 +740,21 @@ memtx_tree_index_get(struct index *base,
> const char *key,
> > > return 0;
> > > }
> > >
> > >+template <int USE_HINT>
> > > 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;
> > >+ struct memtx_tree_index<USE_HINT> *index =
> > >+ (struct memtx_tree_index<USE_HINT> *)base;
> > > struct key_def *cmp_def = memtx_tree_cmp_def(&index->tree);
> > > if (new_tuple) {
> > >- struct memtx_tree_data new_data;
> > >+ struct memtx_tree_data<USE_HINT> new_data;
> > > new_data.tuple = new_tuple;
> > >- new_data.hint = tuple_hint(new_tuple, cmp_def);
> > >- struct memtx_tree_data dup_data;
> > >+ if (USE_HINT)
> > >+ new_data.set_hint(tuple_hint(new_tuple, cmp_def));
> > >+ struct memtx_tree_data<USE_HINT> dup_data;
> > > dup_data.tuple = NULL;
> > >
> > > /* Try to optimistically replace the new_tuple. */
> > >@@ -652,9 +784,10 @@ memtx_tree_index_replace(struct index
> *base, struct tuple *old_tuple,
> > > }
> > > }
> > > if (old_tuple) {
> > >- struct memtx_tree_data old_data;
> > >+ struct memtx_tree_data<USE_HINT> old_data;
> > > old_data.tuple = old_tuple;
> > >- old_data.hint = tuple_hint(old_tuple, cmp_def);
> > >+ if (USE_HINT)
> > >+ old_data.set_hint(tuple_hint(old_tuple, cmp_def));
> > > memtx_tree_delete(&index->tree, old_data);
> > > }
> > > *result = old_tuple;
> > >@@ -667,13 +800,13 @@ memtx_tree_index_replace(struct index
> *base, struct tuple *old_tuple,
> > > * by all it's multikey indexes.
> > > */
> > > static int
> > >-memtx_tree_index_replace_multikey_one(struct memtx_tree_index
> *index,
> > >+memtx_tree_index_replace_multikey_one(struct
> memtx_tree_index<1> *index,
> > > struct tuple *old_tuple, struct tuple *new_tuple,
> > > enum dup_replace_mode mode, hint_t hint,
> > >- struct memtx_tree_data *replaced_data,
> > >+ struct memtx_tree_data<1> *replaced_data,
> > > bool *is_multikey_conflict)
> > > {
> > >- struct memtx_tree_data new_data, dup_data;
> > >+ struct memtx_tree_data<1> new_data, dup_data;
> > > new_data.tuple = new_tuple;
> > > new_data.hint = hint;
> > > dup_data.tuple = NULL;
> > >@@ -720,11 +853,11 @@
> memtx_tree_index_replace_multikey_one(struct memtx_tree_index *index,
> > > * delete operation is fault-tolerant.
> > > */
> > > static void
> > >-memtx_tree_index_replace_multikey_rollback(struct
> memtx_tree_index *index,
> > >+memtx_tree_index_replace_multikey_rollback(struct
> memtx_tree_index<1> *index,
> > > struct tuple *new_tuple, struct tuple *replaced_tuple,
> > > int err_multikey_idx)
> > > {
> > >- struct memtx_tree_data data;
> > >+ struct memtx_tree_data<1> data;
> > > if (replaced_tuple != NULL) {
> > > /* Restore replaced tuple index occurrences. */
> > > struct key_def *cmp_def = memtx_tree_cmp_def(&index->tree);
> > >@@ -798,7 +931,7 @@ memtx_tree_index_replace_multikey(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;
> > >+ struct memtx_tree_index<1> *index = (struct
> memtx_tree_index<1> *)base;
> > > struct key_def *cmp_def = memtx_tree_cmp_def(&index->tree);
> > > *result = NULL;
> > > if (new_tuple != NULL) {
> > >@@ -808,7 +941,7 @@ memtx_tree_index_replace_multikey(struct
> index *base, struct tuple *old_tuple,
> > > for (; (uint32_t) multikey_idx < multikey_count;
> > > multikey_idx++) {
> > > bool is_multikey_conflict;
> > >- struct memtx_tree_data replaced_data;
> > >+ struct memtx_tree_data<1> replaced_data;
> > > err = memtx_tree_index_replace_multikey_one(index,
> > > old_tuple, new_tuple, mode,
> > > multikey_idx, &replaced_data,
> > >@@ -833,7 +966,7 @@ memtx_tree_index_replace_multikey(struct
> index *base, struct tuple *old_tuple,
> > > }
> > > }
> > > if (old_tuple != NULL) {
> > >- struct memtx_tree_data data;
> > >+ struct memtx_tree_data<1> data;
> > > data.tuple = old_tuple;
> > > uint32_t multikey_count =
> > > tuple_multikey_count(old_tuple, cmp_def);
> > >@@ -865,7 +998,7 @@ struct func_key_undo {
> > > /** A link to organize entries in list. */
> > > struct rlist link;
> > > /** An inserted record copy. */
> > >- struct memtx_tree_data key;
> > >+ struct memtx_tree_data<1> key;
> > > };
> > >
> > > /** Allocate a new func_key_undo on given region. */
> > >@@ -888,7 +1021,7 @@ func_key_undo_new(struct region *region)
> > > * return a given index object in it's original state.
> > > */
> > > static void
> > >-memtx_tree_func_index_replace_rollback(struct memtx_tree_index
> *index,
> > >+memtx_tree_func_index_replace_rollback(struct
> memtx_tree_index<1> *index,
> > > struct rlist *old_keys,
> > > struct rlist *new_keys)
> > > {
> > >@@ -919,7 +1052,7 @@ memtx_tree_func_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;
> > >+ struct memtx_tree_index<1> *index = (struct
> memtx_tree_index<1> *)base;
> > > struct index_def *index_def = index->base.def;
> > > assert(index_def->key_def->for_func_index);
> > >
> > >@@ -952,7 +1085,7 @@ memtx_tree_func_index_replace(struct index
> *base, struct tuple *old_tuple,
> > > undo->key.hint = (hint_t)key;
> > > rlist_add(&new_keys, &undo->link);
> > > bool is_multikey_conflict;
> > >- struct memtx_tree_data old_data;
> > >+ struct memtx_tree_data<1> old_data;
> > > old_data.tuple = NULL;
> > > err = memtx_tree_index_replace_multikey_one(index,
> > > old_tuple, new_tuple,
> > >@@ -1015,7 +1148,7 @@ memtx_tree_func_index_replace(struct
> index *base, struct tuple *old_tuple,
> > > if (key_list_iterator_create(&it, old_tuple, index_def, false,
> > > func_index_key_dummy_alloc) != 0)
> > > goto end;
> > >- struct memtx_tree_data data, deleted_data;
> > >+ struct memtx_tree_data<1> data, deleted_data;
> > > data.tuple = old_tuple;
> > > const char *key;
> > > while (key_list_iterator_next(&it, &key) == 0 && key != NULL) {
> > >@@ -1040,11 +1173,13 @@ end:
> > > return rc;
> > > }
> > >
> > >+template <int USE_HINT>
> > > static struct iterator *
> > > memtx_tree_index_create_iterator(struct index *base, enum
> iterator_type type,
> > > const char *key, uint32_t part_count)
> > > {
> > >- struct memtx_tree_index *index = (struct memtx_tree_index *)base;
> > >+ struct memtx_tree_index<USE_HINT> *index =
> > >+ (struct memtx_tree_index<USE_HINT> *)base;
> > > struct memtx_engine *memtx = (struct memtx_engine *)base->engine;
> > > struct key_def *cmp_def = memtx_tree_cmp_def(&index->tree);
> > >
> > >@@ -1064,42 +1199,47 @@ memtx_tree_index_create_iterator(struct
> index *base, enum iterator_type type,
> > > key = NULL;
> > > }
> > >
> > >- struct tree_iterator *it = (struct tree_iterator *)
> > >+ struct tree_iterator<USE_HINT> *it = (struct
> tree_iterator<USE_HINT> *)
> > > mempool_alloc(&memtx->iterator_pool);
> > > if (it == NULL) {
> > >- diag_set(OutOfMemory, sizeof(struct tree_iterator),
> > >+ diag_set(OutOfMemory, sizeof(struct tree_iterator<USE_HINT>),
> > > "memtx_tree_index", "iterator");
> > > return NULL;
> > > }
> > > iterator_create(&it->base, base);
> > > it->pool = &memtx->iterator_pool;
> > >- it->base.next = tree_iterator_start;
> > >- it->base.free = tree_iterator_free;
> > >+ it->base.next = tree_iterator_start<USE_HINT>;
> > >+ it->base.free = tree_iterator_free<USE_HINT>;
> > > it->type = type;
> > > it->key_data.key = key;
> > > it->key_data.part_count = part_count;
> > >- it->key_data.hint = key_hint(key, part_count, cmp_def);
> > >- it->tree_iterator = memtx_tree_invalid_iterator();
> > >+ if (USE_HINT)
> > >+ it->key_data.set_hint(key_hint(key, part_count, cmp_def));
> > >+ invalidate_tree_iterator(&it->tree_iterator);
> > > it->current.tuple = NULL;
> > > return (struct iterator *)it;
> > > }
> > >
> > >+template <int USE_HINT>
> > > static void
> > > memtx_tree_index_begin_build(struct index *base)
> > > {
> > >- struct memtx_tree_index *index = (struct memtx_tree_index *)base;
> > >+ struct memtx_tree_index<USE_HINT> *index =
> > >+ (struct memtx_tree_index<USE_HINT> *)base;
> > > assert(memtx_tree_size(&index->tree) == 0);
> > > (void)index;
> > > }
> > >
> > >+template <int USE_HINT>
> > > static int
> > > memtx_tree_index_reserve(struct index *base, uint32_t size_hint)
> > > {
> > >- struct memtx_tree_index *index = (struct memtx_tree_index *)base;
> > >+ struct memtx_tree_index<USE_HINT> *index =
> > >+ (struct memtx_tree_index<USE_HINT> *)base;
> > > if (size_hint < index->build_array_alloc_size)
> > > return 0;
> > >- struct memtx_tree_data *tmp =
> > >- (struct memtx_tree_data *)
> > >+ struct memtx_tree_data<USE_HINT> *tmp =
> > >+ (struct memtx_tree_data<USE_HINT> *)
> > > realloc(index->build_array, size_hint * sizeof(*tmp));
> > > if (tmp == NULL) {
> > > diag_set(OutOfMemory, size_hint * sizeof(*tmp),
> > >@@ -1111,14 +1251,15 @@ memtx_tree_index_reserve(struct index
> *base, uint32_t size_hint)
> > > return 0;
> > > }
> > >
> > >+template <int USE_HINT>
> > > /** Initialize the next element of the index build_array. */
> > > static int
> > >-memtx_tree_index_build_array_append(struct memtx_tree_index
> *index,
> > >+memtx_tree_index_build_array_append(struct
> memtx_tree_index<USE_HINT> *index,
> > > struct tuple *tuple, hint_t hint)
> > > {
> > > if (index->build_array == NULL) {
> > > index->build_array =
> > >- (struct memtx_tree_data *)malloc(MEMTX_EXTENT_SIZE);
> > >+ (struct memtx_tree_data<USE_HINT> *)malloc(MEMTX_EXTENT_SIZE);
> > > if (index->build_array == NULL) {
> > > diag_set(OutOfMemory, MEMTX_EXTENT_SIZE,
> > > "memtx_tree_index", "build_next");
> > >@@ -1131,8 +1272,8 @@
> memtx_tree_index_build_array_append(struct memtx_tree_index *index,
> > > if (index->build_array_size == index->build_array_alloc_size) {
> > > index->build_array_alloc_size = index->build_array_alloc_size +
> > > DIV_ROUND_UP(index->build_array_alloc_size, 2);
> > >- struct memtx_tree_data *tmp =
> > >- (struct memtx_tree_data *)realloc(index->build_array,
> > >+ struct memtx_tree_data<USE_HINT> *tmp =
> > >+ (struct memtx_tree_data<USE_HINT> *)realloc(index->build_array,
> > > index->build_array_alloc_size * sizeof(*tmp));
> > > if (tmp == NULL) {
> > > diag_set(OutOfMemory, index->build_array_alloc_size *
> > >@@ -1141,17 +1282,20 @@
> memtx_tree_index_build_array_append(struct memtx_tree_index *index,
> > > }
> > > index->build_array = tmp;
> > > }
> > >- struct memtx_tree_data *elem =
> > >+ struct memtx_tree_data<USE_HINT> *elem =
> > > &index->build_array[index->build_array_size++];
> > > elem->tuple = tuple;
> > >- elem->hint = hint;
> > >+ if (USE_HINT)
> > >+ elem->set_hint(hint);
> > > return 0;
> > > }
> > >
> > >+template <int USE_HINT>
> > > static int
> > > memtx_tree_index_build_next(struct index *base, struct tuple
> *tuple)
> > > {
> > >- struct memtx_tree_index *index = (struct memtx_tree_index *)base;
> > >+ struct memtx_tree_index<USE_HINT> *index =
> > >+ (struct memtx_tree_index<USE_HINT> *)base;
> > > struct key_def *cmp_def = memtx_tree_cmp_def(&index->tree);
> > > return memtx_tree_index_build_array_append(index, tuple,
> > > tuple_hint(tuple, cmp_def));
> > >@@ -1160,7 +1304,7 @@ memtx_tree_index_build_next(struct index
> *base, struct tuple *tuple)
> > > static int
> > > memtx_tree_index_build_next_multikey(struct index *base,
> struct tuple *tuple)
> > > {
> > >- struct memtx_tree_index *index = (struct memtx_tree_index *)base;
> > >+ struct memtx_tree_index<1> *index = (struct
> memtx_tree_index<1> *)base;
> > > struct key_def *cmp_def = memtx_tree_cmp_def(&index->tree);
> > > uint32_t multikey_count = tuple_multikey_count(tuple, cmp_def);
> > > for (uint32_t multikey_idx = 0; multikey_idx < multikey_count;
> > >@@ -1175,7 +1319,7 @@
> memtx_tree_index_build_next_multikey(struct index *base, struct
> tuple *tuple)
> > > static int
> > > memtx_tree_func_index_build_next(struct index *base, struct
> tuple *tuple)
> > > {
> > >- struct memtx_tree_index *index = (struct memtx_tree_index *)base;
> > >+ struct memtx_tree_index<1> *index = (struct
> memtx_tree_index<1> *)base;
> > > struct index_def *index_def = index->base.def;
> > > assert(index_def->key_def->for_func_index);
> > >
> > >@@ -1211,8 +1355,9 @@ error:
> > > * of equal tuples (in terms of index's cmp_def and have same
> > > * tuple pointer). The build_array is expected to be sorted.
> > > */
> > >+template <int USE_HINT>
> > > static void
> > >-memtx_tree_index_build_array_deduplicate(struct
> memtx_tree_index *index,
> > >+memtx_tree_index_build_array_deduplicate(struct
> memtx_tree_index<USE_HINT> *index,
> > > void (*destroy)(struct tuple *tuple, const char *hint))
> > > {
> > > if (index->build_array_size == 0)
> > >@@ -1246,13 +1391,16 @@
> memtx_tree_index_build_array_deduplicate(struct memtx_tree_index
> *index,
> > > index->build_array_size = w_idx + 1;
> > > }
> > >
> > >+template <int USE_HINT>
> > > static void
> > > memtx_tree_index_end_build(struct index *base)
> > > {
> > >- struct memtx_tree_index *index = (struct memtx_tree_index *)base;
> > >+ struct memtx_tree_index<USE_HINT> *index =
> > >+ (struct memtx_tree_index<USE_HINT> *)base;
> > > struct key_def *cmp_def = memtx_tree_cmp_def(&index->tree);
> > > qsort_arg(index->build_array, index->build_array_size,
> > >- sizeof(index->build_array[0]), memtx_tree_qcompare, cmp_def);
> > >+ sizeof(index->build_array[0]),
> > >+ memtx_tree_qcompare<USE_HINT>, cmp_def);
> > > if (cmp_def->is_multikey) {
> > > /*
> > > * Multikey index may have equal(in terms of
> > >@@ -1261,9 +1409,9 @@ memtx_tree_index_end_build(struct index
> *base)
> > > * the following memtx_tree_build assumes that
> > > * all keys are unique.
> > > */
> > >- memtx_tree_index_build_array_deduplicate(index, NULL);
> > >+ memtx_tree_index_build_array_deduplicate<USE_HINT>(index, NULL);
> > > } else if (cmp_def->for_func_index) {
> > >- memtx_tree_index_build_array_deduplicate(index,
> > >+ memtx_tree_index_build_array_deduplicate<USE_HINT>(index,
> > > tuple_chunk_delete);
> > > }
> > > memtx_tree_build(&index->tree, index->build_array,
> > >@@ -1275,19 +1423,21 @@ memtx_tree_index_end_build(struct index
> *base)
> > > index->build_array_alloc_size = 0;
> > > }
> > >
> > >+template <int USE_HINT>
> > > struct tree_snapshot_iterator {
> > > struct snapshot_iterator base;
> > >- struct memtx_tree_index *index;
> > >- struct memtx_tree_iterator tree_iterator;
> > >+ struct memtx_tree_index<USE_HINT> *index;
> > >+ memtx_tree_iterator_t<USE_HINT> tree_iterator;
> > > struct memtx_tx_snapshot_cleaner cleaner;
> > > };
> > >
> > >+template <int USE_HINT>
> > > static void
> > > tree_snapshot_iterator_free(struct snapshot_iterator *iterator)
> > > {
> > >- assert(iterator->free == tree_snapshot_iterator_free);
> > >- struct tree_snapshot_iterator *it =
> > >- (struct tree_snapshot_iterator *)iterator;
> > >+ assert(iterator->free == &tree_snapshot_iterator_free<USE_HINT>);
> > >+ struct tree_snapshot_iterator<USE_HINT> *it =
> > >+ (struct tree_snapshot_iterator<USE_HINT> *)iterator;
> > > memtx_leave_delayed_free_mode((struct memtx_engine *)
> > > it->index->base.engine);
> > > memtx_tree_iterator_destroy(&it->index->tree, &it->tree_iterator);
> > >@@ -1296,17 +1446,18 @@ tree_snapshot_iterator_free(struct
> snapshot_iterator *iterator)
> > > free(iterator);
> > > }
> > >
> > >+template <int USE_HINT>
> > > static int
> > > tree_snapshot_iterator_next(struct snapshot_iterator *iterator,
> > > const char **data, uint32_t *size)
> > > {
> > >- assert(iterator->free == tree_snapshot_iterator_free);
> > >- struct tree_snapshot_iterator *it =
> > >- (struct tree_snapshot_iterator *)iterator;
> > >- struct memtx_tree *tree = &it->index->tree;
> > >+ assert(iterator->free == &tree_snapshot_iterator_free<USE_HINT>);
> > >+ struct tree_snapshot_iterator<USE_HINT> *it =
> > >+ (struct tree_snapshot_iterator<USE_HINT> *)iterator;
> > >+ memtx_tree_t<USE_HINT> *tree = &it->index->tree;
> > >
> > > while (true) {
> > >- struct memtx_tree_data *res =
> > >+ struct memtx_tree_data<USE_HINT> *res =
> > > memtx_tree_iterator_get_elem(tree, &it->tree_iterator);
> > >
> > > if (res == NULL) {
> > >@@ -1333,14 +1484,18 @@ tree_snapshot_iterator_next(struct
> snapshot_iterator *iterator,
> > > * index modifications will not affect the iteration results.
> > > * Must be destroyed by iterator->free after usage.
> > > */
> > >+template <int USE_HINT>
> > > static struct snapshot_iterator *
> > > memtx_tree_index_create_snapshot_iterator(struct index *base)
> > > {
> > >- struct memtx_tree_index *index = (struct memtx_tree_index *)base;
> > >- struct tree_snapshot_iterator *it =
> > >- (struct tree_snapshot_iterator *) calloc(1, sizeof(*it));
> > >+ struct memtx_tree_index<USE_HINT> *index =
> > >+ (struct memtx_tree_index<USE_HINT> *)base;
> > >+ struct tree_snapshot_iterator<USE_HINT> *it =
> > >+ (struct tree_snapshot_iterator<USE_HINT> *)
> > >+ calloc(1, sizeof(*it));
> > > if (it == NULL) {
> > >- diag_set(OutOfMemory, sizeof(struct tree_snapshot_iterator),
> > >+ diag_set(OutOfMemory,
> > >+ sizeof(struct tree_snapshot_iterator<USE_HINT>),
> > > "memtx_tree_index", "create_snapshot_iterator");
> > > return NULL;
> > > }
> > >@@ -1352,8 +1507,8 @@
> memtx_tree_index_create_snapshot_iterator(struct index *base)
> > > return NULL;
> > > }
> > >
> > >- it->base.free = tree_snapshot_iterator_free;
> > >- it->base.next = tree_snapshot_iterator_next;
> > >+ it->base.free = tree_snapshot_iterator_free<USE_HINT>;
> > >+ it->base.next = tree_snapshot_iterator_next<USE_HINT>;
> > > it->index = index;
> > > index_ref(base);
> > > it->tree_iterator = memtx_tree_iterator_first(&index->tree);
> > >@@ -1362,94 +1517,124 @@
> memtx_tree_index_create_snapshot_iterator(struct index *base)
> > > return (struct snapshot_iterator *) it;
> > > }
> > >
> > >-static const struct index_vtab memtx_tree_index_vtab = {
> > >- /* .destroy = */ memtx_tree_index_destroy,
> > >+static const struct index_vtab memtx_tree_no_hint_index_vtab = {
> > >+ /* .destroy = */ memtx_tree_index_destroy<0>,
> > > /* .commit_create = */ generic_index_commit_create,
> > > /* .abort_create = */ generic_index_abort_create,
> > > /* .commit_modify = */ generic_index_commit_modify,
> > > /* .commit_drop = */ generic_index_commit_drop,
> > >- /* .update_def = */ memtx_tree_index_update_def,
> > >+ /* .update_def = */ memtx_tree_index_update_def<0>,
> > > /* .depends_on_pk = */ memtx_tree_index_depends_on_pk,
> > > /* .def_change_requires_rebuild = */
> > > memtx_index_def_change_requires_rebuild,
> > >- /* .size = */ memtx_tree_index_size,
> > >- /* .bsize = */ memtx_tree_index_bsize,
> > >+ /* .size = */ memtx_tree_index_size<0>,
> > >+ /* .bsize = */ memtx_tree_index_bsize<0>,
> > > /* .min = */ generic_index_min,
> > > /* .max = */ generic_index_max,
> > >- /* .random = */ memtx_tree_index_random,
> > >- /* .count = */ memtx_tree_index_count,
> > >- /* .get = */ memtx_tree_index_get,
> > >- /* .replace = */ memtx_tree_index_replace,
> > >- /* .create_iterator = */ memtx_tree_index_create_iterator,
> > >+ /* .random = */ memtx_tree_index_random<0>,
> > >+ /* .count = */ memtx_tree_index_count<0>,
> > >+ /* .get = */ memtx_tree_index_get<0>,
> > >+ /* .replace = */ memtx_tree_index_replace<0>,
> > >+ /* .create_iterator = */ memtx_tree_index_create_iterator<0>,
> > > /* .create_snapshot_iterator = */
> > >- memtx_tree_index_create_snapshot_iterator,
> > >+ memtx_tree_index_create_snapshot_iterator<0>,
> > > /* .stat = */ generic_index_stat,
> > > /* .compact = */ generic_index_compact,
> > > /* .reset_stat = */ generic_index_reset_stat,
> > >- /* .begin_build = */ memtx_tree_index_begin_build,
> > >- /* .reserve = */ memtx_tree_index_reserve,
> > >- /* .build_next = */ memtx_tree_index_build_next,
> > >- /* .end_build = */ memtx_tree_index_end_build,
> > >+ /* .begin_build = */ memtx_tree_index_begin_build<0>,
> > >+ /* .reserve = */ memtx_tree_index_reserve<0>,
> > >+ /* .build_next = */ memtx_tree_index_build_next<0>,
> > >+ /* .end_build = */ memtx_tree_index_end_build<0>,
> > >+};
> > >+
> > >+static const struct index_vtab memtx_tree_use_hint_index_vtab = {
> > >+ /* .destroy = */ memtx_tree_index_destroy<1>,
> > >+ /* .commit_create = */ generic_index_commit_create,
> > >+ /* .abort_create = */ generic_index_abort_create,
> > >+ /* .commit_modify = */ generic_index_commit_modify,
> > >+ /* .commit_drop = */ generic_index_commit_drop,
> > >+ /* .update_def = */ memtx_tree_index_update_def<1>,
> > >+ /* .depends_on_pk = */ memtx_tree_index_depends_on_pk,
> > >+ /* .def_change_requires_rebuild = */
> > >+ memtx_index_def_change_requires_rebuild,
> > >+ /* .size = */ memtx_tree_index_size<1>,
> > >+ /* .bsize = */ memtx_tree_index_bsize<1>,
> > >+ /* .min = */ generic_index_min,
> > >+ /* .max = */ generic_index_max,
> > >+ /* .random = */ memtx_tree_index_random<1>,
> > >+ /* .count = */ memtx_tree_index_count<1>,
> > >+ /* .get = */ memtx_tree_index_get<1>,
> > >+ /* .replace = */ memtx_tree_index_replace<1>,
> > >+ /* .create_iterator = */ memtx_tree_index_create_iterator<1>,
> > >+ /* .create_snapshot_iterator = */
> > >+ memtx_tree_index_create_snapshot_iterator<1>,
> > >+ /* .stat = */ generic_index_stat,
> > >+ /* .compact = */ generic_index_compact,
> > >+ /* .reset_stat = */ generic_index_reset_stat,
> > >+ /* .begin_build = */ memtx_tree_index_begin_build<1>,
> > >+ /* .reserve = */ memtx_tree_index_reserve<1>,
> > >+ /* .build_next = */ memtx_tree_index_build_next<1>,
> > >+ /* .end_build = */ memtx_tree_index_end_build<1>,
> > > };
> > >
> > > static const struct index_vtab memtx_tree_index_multikey_vtab = {
> > >- /* .destroy = */ memtx_tree_index_destroy,
> > >+ /* .destroy = */ memtx_tree_index_destroy<1>,
> > > /* .commit_create = */ generic_index_commit_create,
> > > /* .abort_create = */ generic_index_abort_create,
> > > /* .commit_modify = */ generic_index_commit_modify,
> > > /* .commit_drop = */ generic_index_commit_drop,
> > >- /* .update_def = */ memtx_tree_index_update_def,
> > >+ /* .update_def = */ memtx_tree_index_update_def<1>,
> > > /* .depends_on_pk = */ memtx_tree_index_depends_on_pk,
> > > /* .def_change_requires_rebuild = */
> > > memtx_index_def_change_requires_rebuild,
> > >- /* .size = */ memtx_tree_index_size,
> > >- /* .bsize = */ memtx_tree_index_bsize,
> > >+ /* .size = */ memtx_tree_index_size<1>,
> > >+ /* .bsize = */ memtx_tree_index_bsize<1>,
> > > /* .min = */ generic_index_min,
> > > /* .max = */ generic_index_max,
> > >- /* .random = */ memtx_tree_index_random,
> > >- /* .count = */ memtx_tree_index_count,
> > >- /* .get = */ memtx_tree_index_get,
> > >+ /* .random = */ memtx_tree_index_random<1>,
> > >+ /* .count = */ memtx_tree_index_count<1>,
> > >+ /* .get = */ memtx_tree_index_get<1>,
> > > /* .replace = */ memtx_tree_index_replace_multikey,
> > >- /* .create_iterator = */ memtx_tree_index_create_iterator,
> > >+ /* .create_iterator = */ memtx_tree_index_create_iterator<1>,
> > > /* .create_snapshot_iterator = */
> > >- memtx_tree_index_create_snapshot_iterator,
> > >+ memtx_tree_index_create_snapshot_iterator<1>,
> > > /* .stat = */ generic_index_stat,
> > > /* .compact = */ generic_index_compact,
> > > /* .reset_stat = */ generic_index_reset_stat,
> > >- /* .begin_build = */ memtx_tree_index_begin_build,
> > >- /* .reserve = */ memtx_tree_index_reserve,
> > >+ /* .begin_build = */ memtx_tree_index_begin_build<1>,
> > >+ /* .reserve = */ memtx_tree_index_reserve<1>,
> > > /* .build_next = */ memtx_tree_index_build_next_multikey,
> > >- /* .end_build = */ memtx_tree_index_end_build,
> > >+ /* .end_build = */ memtx_tree_index_end_build<1>,
> > > };
> > >
> > > static const struct index_vtab memtx_tree_func_index_vtab = {
> > >- /* .destroy = */ memtx_tree_index_destroy,
> > >+ /* .destroy = */ memtx_tree_index_destroy<1>,
> > > /* .commit_create = */ generic_index_commit_create,
> > > /* .abort_create = */ generic_index_abort_create,
> > > /* .commit_modify = */ generic_index_commit_modify,
> > > /* .commit_drop = */ generic_index_commit_drop,
> > >- /* .update_def = */ memtx_tree_index_update_def,
> > >+ /* .update_def = */ memtx_tree_index_update_def<1>,
> > > /* .depends_on_pk = */ memtx_tree_index_depends_on_pk,
> > > /* .def_change_requires_rebuild = */
> > > memtx_index_def_change_requires_rebuild,
> > >- /* .size = */ memtx_tree_index_size,
> > >- /* .bsize = */ memtx_tree_index_bsize,
> > >+ /* .size = */ memtx_tree_index_size<1>,
> > >+ /* .bsize = */ memtx_tree_index_bsize<1>,
> > > /* .min = */ generic_index_min,
> > > /* .max = */ generic_index_max,
> > >- /* .random = */ memtx_tree_index_random,
> > >- /* .count = */ memtx_tree_index_count,
> > >- /* .get = */ memtx_tree_index_get,
> > >+ /* .random = */ memtx_tree_index_random<1>,
> > >+ /* .count = */ memtx_tree_index_count<1>,
> > >+ /* .get = */ memtx_tree_index_get<1>,
> > > /* .replace = */ memtx_tree_func_index_replace,
> > >- /* .create_iterator = */ memtx_tree_index_create_iterator,
> > >+ /* .create_iterator = */ memtx_tree_index_create_iterator<1>,
> > > /* .create_snapshot_iterator = */
> > >- memtx_tree_index_create_snapshot_iterator,
> > >+ memtx_tree_index_create_snapshot_iterator<1>,
> > > /* .stat = */ generic_index_stat,
> > > /* .compact = */ generic_index_compact,
> > > /* .reset_stat = */ generic_index_reset_stat,
> > >- /* .begin_build = */ memtx_tree_index_begin_build,
> > >- /* .reserve = */ memtx_tree_index_reserve,
> > >+ /* .begin_build = */ memtx_tree_index_begin_build<1>,
> > >+ /* .reserve = */ memtx_tree_index_reserve<1>,
> > > /* .build_next = */ memtx_tree_func_index_build_next,
> > >- /* .end_build = */ memtx_tree_index_end_build,
> > >+ /* .end_build = */ memtx_tree_index_end_build<1>,
> > > };
> > >
> > > /**
> > >@@ -1459,7 +1644,7 @@ static const struct index_vtab
> memtx_tree_func_index_vtab = {
> > > * key defintion is not completely initialized at that moment).
> > > */
> > > static const struct index_vtab memtx_tree_disabled_index_vtab = {
> > >- /* .destroy = */ memtx_tree_index_destroy,
> > >+ /* .destroy = */ memtx_tree_index_destroy<1>,
> > > /* .commit_create = */ generic_index_commit_create,
> > > /* .abort_create = */ generic_index_abort_create,
> > > /* .commit_modify = */ generic_index_commit_modify,
> > >@@ -1488,27 +1673,19 @@ static const struct index_vtab
> memtx_tree_disabled_index_vtab = {
> > > /* .end_build = */ generic_index_end_build,
> > > };
> > >
> > >-struct index *
> > >-memtx_tree_index_new(struct memtx_engine *memtx, struct
> index_def *def)
> > >+template <int USE_HINT>
> > >+static struct index *
> > >+memtx_tree_index_new_tpl(struct memtx_engine *memtx, struct
> index_def *def,
> > >+ const struct index_vtab *vtab)
> > > {
> > >- struct memtx_tree_index *index =
> > >- (struct memtx_tree_index *)calloc(1, sizeof(*index));
> > >+ struct memtx_tree_index<USE_HINT> *index =
> > >+ (struct memtx_tree_index<USE_HINT> *)
> > >+ calloc(1, sizeof(*index));
> > > if (index == NULL) {
> > > diag_set(OutOfMemory, sizeof(*index),
> > > "malloc", "struct memtx_tree_index");
> > > return NULL;
> > > }
> > >- const struct index_vtab *vtab;
> > >- if (def->key_def->for_func_index) {
> > >- if (def->key_def->func_index_func == NULL)
> > >- vtab = &memtx_tree_disabled_index_vtab;
> > >- else
> > >- vtab = &memtx_tree_func_index_vtab;
> > >- } else if (def->key_def->is_multikey) {
> > >- vtab = &memtx_tree_index_multikey_vtab;
> > >- } else {
> > >- vtab = &memtx_tree_index_vtab;
> > >- }
> > > if (index_create(&index->base, (struct engine *)memtx,
> > > vtab, def) != 0) {
> > > free(index);
> > >@@ -1524,3 +1701,23 @@ memtx_tree_index_new(struct memtx_engine
> *memtx, struct index_def *def)
> > > memtx_index_extent_free, memtx);
> > > return &index->base;
> > > }
> > >+
> > >+struct index *
> > >+memtx_tree_index_new(struct memtx_engine *memtx, struct
> index_def *def)
> > >+{
> > >+ const struct index_vtab *vtab;
> > >+ if (def->key_def->for_func_index) {
> > >+ if (def->key_def->func_index_func == NULL)
> > >+ vtab = &memtx_tree_disabled_index_vtab;
> > >+ else
> > >+ vtab = &memtx_tree_func_index_vtab;
> > >+ } else if (def->key_def->is_multikey) {
> > >+ vtab = &memtx_tree_index_multikey_vtab;
> > >+ } else if (def->opts.hint) {
> > >+ vtab = &memtx_tree_use_hint_index_vtab;
> > >+ } else {
> > >+ vtab = &memtx_tree_no_hint_index_vtab;
> > >+ return memtx_tree_index_new_tpl<0>(memtx, def, vtab);
> > >+ }
> > >+ return memtx_tree_index_new_tpl<1>(memtx, def, vtab);
> > >+}
> > >diff --git a/src/lib/salad/bps_tree.h b/src/lib/salad/bps_tree.h
> > >index ef5ae3d..0bb803a 100644
> > >--- a/src/lib/salad/bps_tree.h
> > >+++ b/src/lib/salad/bps_tree.h
> > >@@ -168,6 +168,17 @@
> > >
> > > /* {{{ BPS-tree interface settings */
> > > /**
> > >+ * Optional namespace for structs and functions.
> > >+ * Is set, struct and functions will have BPS_TREE_NAMESPACE::
> prefix.
> > >+ * For example one can #define BPS_TREE_NAMESPACE my along with
> > >+ * #define BPS_TREE_NAME _test, and use then
> > >+ * struct my::bps_tree_test my_tree;
> > >+ * my::bps_tree_test_create(&my_tree, ...);
> > >+ *
> > >+ * #define BPS_TREE_NAMESPACE
> > >+ */
> > >+
> > >+/**
> > > * Custom name for structs and functions.
> > > * Struct and functions will have bps_tree##BPS_TREE_NAME name
> or prefix.
> > > * For example one can #define BPS_TREE_NAME _test, and use then
> > >@@ -300,6 +311,10 @@
> > >
> > > /* }}} */
> > >
> > >+#ifdef BPS_TREE_NAMESPACE
> > >+namespace BPS_TREE_NAMESPACE {
> > >+#endif
> > >+
> > > /* {{{ BPS-tree internal settings */
> > > typedef int16_t bps_tree_pos_t;
> > > typedef uint32_t bps_tree_block_id_t;
> > >@@ -6188,3 +6203,7 @@
> bps_tree_debug_check_internal_functions(bool assertme)
> > > #undef bps_tree_debug_check_insert_and_move_to_left_inner
> > >
> > > /* }}} */
> > >+
> > >+#ifdef BPS_TREE_NAMESPACE
> > >+} /* namespace BPS_TREE_NAMESPACE { */
> > >+#endif
> > >diff --git a/test/box/alter.result b/test/box/alter.result
> > >index 237c2d8..5b412a7 100644
> > >--- a/test/box/alter.result
> > >+++ b/test/box/alter.result
> > >@@ -680,8 +680,9 @@ s.index.pk
> > > - type: unsigned
> > > is_nullable: false
> > > fieldno: 2
> > >- type: TREE
> > >+ hint: true
> > > id: 0
> > >+ type: TREE
> > > space_id: 731
> > > name: pk
> > > ...
> > >@@ -710,9 +711,10 @@ s.index.pk
> > > - type: unsigned
> > > is_nullable: false
> > > fieldno: 1
> > >- space_id: 731
> > >+ hint: true
> > > id: 0
> > > type: TREE
> > >+ space_id: 731
> > > name: pk
> > > ...
> > > s.index.secondary
> > >@@ -722,8 +724,9 @@ s.index.secondary
> > > - type: unsigned
> > > is_nullable: false
> > > fieldno: 2
> > >- type: TREE
> > >+ hint: true
> > > id: 1
> > >+ type: TREE
> > > space_id: 731
> > > name: secondary
> > > ...
> > >@@ -1559,3 +1562,97 @@ assert(err:match('does not exist') ~= nil)
> > > ---
> > > - true
> > > ...
> > >+-- hint
> > >+s = box.schema.create_space('test');
> > >+---
> > >+...
> > >+s:create_index('test1', {type='tree', parts={{1, 'uint'}}}).hint
> > >+---
> > >+- true
> > >+...
> > >+s:create_index('test2', {type='tree', parts={{2, 'uint'}},
> hint = true}).hint
> > >+---
> > >+- true
> > >+...
> > >+s:create_index('test3', {type='tree', parts={{3, 'uint'}},
> hint = false}).hint
> > >+---
> > >+- false
> > >+...
> > >+s:create_index('test4', {type='tree', parts={{4, 'string'}},
> hint = false}).hint
> > >+---
> > >+- false
> > >+...
> > >+s.index.test1.hint
> > >+---
> > >+- true
> > >+...
> > >+s.index.test2.hint
> > >+---
> > >+- true
> > >+...
> > >+s.index.test3.hint
> > >+---
> > >+- false
> > >+...
> > >+s.index.test4.hint
> > >+---
> > >+- false
> > >+...
> > >+N = 1000 box.begin() for i = 1,N do s:replace{i, i, i, '' ..
> i} end box.commit()
> > >+---
> > >+...
> > >+s.index.test1:bsize() == s.index.test2:bsize()
> > >+---
> > >+- true
> > >+...
> > >+s.index.test1:bsize() > s.index.test3:bsize()
> > >+---
> > >+- true
> > >+...
> > >+s.index.test1:bsize() > s.index.test4:bsize()
> > >+---
> > >+- true
> > >+...
> > >+s.index.test1:alter{hint=false}
> > >+---
> > >+...
> > >+s.index.test2:alter{hint=true}
> > >+---
> > >+...
> > >+s.index.test3:alter{name='test33', hint=false}
> > >+---
> > >+...
> > >+s.index.test4:alter{hint=true}
> > >+---
> > >+...
> > >+s.index.test1.hint
> > >+---
> > >+- false
> > >+...
> > >+s.index.test2.hint
> > >+---
> > >+- true
> > >+...
> > >+s.index.test33.hint
> > >+---
> > >+- false
> > >+...
> > >+s.index.test4.hint
> > >+---
> > >+- true
> > >+...
> > >+s.index.test1:bsize() < s.index.test2:bsize()
> > >+---
> > >+- true
> > >+...
> > >+s.index.test1:bsize() == s.index.test33:bsize()
> > >+---
> > >+- true
> > >+...
> > >+s.index.test1:bsize() < s.index.test4:bsize()
> > >+---
> > >+- true
> > >+...
> > >+s:drop()
> > >+---
> > >+...
> > >diff --git a/test/box/alter.test.lua b/test/box/alter.test.lua
> > >index abd08e2..2114186 100644
> > >--- a/test/box/alter.test.lua
> > >+++ b/test/box/alter.test.lua
> > >@@ -620,3 +620,37 @@ s:drop()
> > > s:alter({})
> > > ok, err = pcall(box.schema.space.alter, s.id, {})
> > > assert(err:match('does not exist') ~= nil)
> > >+
> > >+-- hint
> > >+s = box.schema.create_space('test');
> > >+s:create_index('test1', {type='tree', parts={{1, 'uint'}}}).hint
> > >+s:create_index('test2', {type='tree', parts={{2, 'uint'}},
> hint = true}).hint
> > >+s:create_index('test3', {type='tree', parts={{3, 'uint'}},
> hint = false}).hint
> > >+s:create_index('test4', {type='tree', parts={{4, 'string'}},
> hint = false}).hint
> > >+
> > >+s.index.test1.hint
> > >+s.index.test2.hint
> > >+s.index.test3.hint
> > >+s.index.test4.hint
> > >+
> > >+N = 1000 box.begin() for i = 1,N do s:replace{i, i, i, '' ..
> i} end box.commit()
> > >+
> > >+s.index.test1:bsize() == s.index.test2:bsize()
> > >+s.index.test1:bsize() > s.index.test3:bsize()
> > >+s.index.test1:bsize() > s.index.test4:bsize()
> > >+
> > >+s.index.test1:alter{hint=false}
> > >+s.index.test2:alter{hint=true}
> > >+s.index.test3:alter{name='test33', hint=false}
> > >+s.index.test4:alter{hint=true}
> > >+
> > >+s.index.test1.hint
> > >+s.index.test2.hint
> > >+s.index.test33.hint
> > >+s.index.test4.hint
> > >+
> > >+s.index.test1:bsize() < s.index.test2:bsize()
> > >+s.index.test1:bsize() == s.index.test33:bsize()
> > >+s.index.test1:bsize() < s.index.test4:bsize()
> > >+
> > >+s:drop()
> > >\ No newline at end of file
> > >diff --git a/test/box/errinj.result b/test/box/errinj.result
> > >index 613d22c..b8c2476 100644
> > >--- a/test/box/errinj.result
> > >+++ b/test/box/errinj.result
> > >@@ -1774,9 +1774,10 @@ rtreespace:create_index('pk',
> {if_not_exists = true})
> > > - type: unsigned
> > > is_nullable: false
> > > fieldno: 1
> > >+ hint: true
> > > id: 0
> > >- space_id: 512
> > > type: TREE
> > >+ space_id: 512
> > > name: pk
> > > ...
> > > rtreespace:create_index('target', {type='rtree', dimension =
> 3, parts={2, 'array'},unique = false, if_not_exists = true,})
> > >diff --git a/test/box/tree_pk.result b/test/box/tree_pk.result
> > >index df3c78b..18cb607 100644
> > >--- a/test/box/tree_pk.result
> > >+++ b/test/box/tree_pk.result
> > >@@ -852,3 +852,317 @@ box.internal.collation.drop('test')
> > > box.internal.collation.drop('test-ci')
> > > ---
> > > ...
> > >+-- hints
> > >+s = box.schema.space.create('test')
> > >+---
> > >+...
> > >+s:create_index('test', {type = 'tree', hint = 'true'} )
> > >+---
> > >+- error: Illegal parameters, options parameter 'hint' should
> be of type boolean
> > >+...
> > >+s:create_index('test', {type = 'hash', hint = true} )
> > >+---
> > >+- error: 'Can''t create or modify index ''test'' in space
> ''test'': hint is only reasonable
> > >+ with memtx tree index'
> > >+...
> > >+s:create_index('test', {type = 'hash'}):alter({hint = true})
> > >+---
> > >+- error: 'Can''t create or modify index ''test'' in space
> ''test'': hint is only reasonable
> > >+ with memtx tree index'
> > >+...
> > >+s:create_index('multikey', {hint = true, parts = {{2, 'int',
> path = '[*]'}}})
> > >+---
> > >+- error: 'Can''t create or modify index ''multikey'' in space
> ''test'': multikey index
> > >+ can''t use hints'
> > >+...
> > >+s:create_index('multikey', {parts = {{2, 'int', path =
> '[*]'}}}):alter({hint = true})
> > >+---
> > >+- error: 'Can''t create or modify index ''multikey'' in space
> ''test'': multikey index
> > >+ can''t use hints'
> > >+...
> > >+lua_code = [[function(tuple) return {tuple[1] + tuple[2]} end]]
> > >+---
> > >+...
> > >+box.schema.func.create('s', {body = lua_code, is_deterministic
> = true, is_sandboxed = true})
> > >+---
> > >+...
> > >+s:create_index('func', {hint = true, func = box.func.s.id,
> parts = {{1, 'unsigned'}}})
> > >+---
> > >+- error: 'Can''t create or modify index ''func'' in space
> ''test'': functional index
> > >+ can''t use hints'
> > >+...
> > >+s:drop()
> > >+---
> > >+...
> > >+s = box.schema.space.create('test', {engine = 'vinyl'})
> > >+---
> > >+...
> > >+s:create_index('test', {type = 'tree', hint = true} )
> > >+---
> > >+- error: 'Can''t create or modify index ''test'' in space
> ''test'': hint is only reasonable
> > >+ with memtx tree index'
> > >+...
> > >+s:drop()
> > >+---
> > >+...
> > >+-- numeric hints
> > >+s1 = box.schema.space.create('test1')
> > >+---
> > >+...
> > >+s1:create_index('test', {type = 'tree', hint = false}).hint
> > >+---
> > >+- false
> > >+...
> > >+s2 = box.schema.space.create('test2')
> > >+---
> > >+...
> > >+s2:create_index('test', {type = 'tree'}).hint
> > >+---
> > >+- true
> > >+...
> > >+N = 2000
> > >+---
> > >+...
> > >+box.begin() for i = 1,N do local v = math.random(10 * N)
> s1:replace{v} s2:replace{v} end box.commit()
> > >+---
> > >+...
> > >+s1:count() == s2:count()
> > >+---
> > >+- true
> > >+...
> > >+good = true r1 = s1:select{} r2 = s2:select{}
> > >+---
> > >+...
> > >+if #r1 ~= #r2 then good = false end
> > >+---
> > >+...
> > >+for k,v in pairs(r1) do if r2[k][1] ~= v[1] then good = false
> end end
> > >+---
> > >+...
> > >+good
> > >+---
> > >+- true
> > >+...
> > >+r1 = nil r2 = nil
> > >+---
> > >+...
> > >+function diff(t1, t2) if t1 then return t1[1] ~= t2[1] else
> return t2 ~= nil end end
> > >+---
> > >+...
> > >+for i = 1, N * 10 do if diff(s1:get{i}, s2:get{i}) then good =
> false end end
> > >+---
> > >+...
> > >+good
> > >+---
> > >+- true
> > >+...
> > >+s1.index[0]:bsize() < s2.index[0]:bsize()
> > >+---
> > >+- true
> > >+...
> > >+s1.index[0]:alter{hint=true}
> > >+---
> > >+...
> > >+s1.index[0]:bsize() == s2.index[0]:bsize()
> > >+---
> > >+- true
> > >+...
> > >+s2.index[0]:alter{hint=false}
> > >+---
> > >+...
> > >+s1.index[0]:bsize() > s2.index[0]:bsize()
> > >+---
> > >+- true
> > >+...
> > >+s1.index[0]:alter{hint=false}
> > >+---
> > >+...
> > >+s1.index[0]:bsize() == s2.index[0]:bsize()
> > >+---
> > >+- true
> > >+...
> > >+s1:drop()
> > >+---
> > >+...
> > >+s2:drop()
> > >+---
> > >+...
> > >+-- string hints
> > >+s1 = box.schema.space.create('test1')
> > >+---
> > >+...
> > >+s1:create_index('test', {type = 'tree', parts = {1, 'str'},
> hint = false}).hint
> > >+---
> > >+- false
> > >+...
> > >+s2 = box.schema.space.create('test2')
> > >+---
> > >+...
> > >+s2:create_index('test', {type = 'tree', parts = {1, 'str'}}).hint
> > >+---
> > >+- true
> > >+...
> > >+N = 1000
> > >+---
> > >+...
> > >+box.begin() for i = 1,N do local v = ''..math.random(10 * N)
> s1:replace{v} s2:replace{v} end box.commit()
> > >+---
> > >+...
> > >+s1:count() == s2:count()
> > >+---
> > >+- true
> > >+...
> > >+good = true r1 = s1:select{} r2 = s2:select{}
> > >+---
> > >+...
> > >+if #r1 ~= #r2 then good = false end
> > >+---
> > >+...
> > >+for k,v in pairs(r1) do if r2[k][1] ~= v[1] then good = false
> end end
> > >+---
> > >+...
> > >+good
> > >+---
> > >+- true
> > >+...
> > >+r1 = nil r2 = nil
> > >+---
> > >+...
> > >+function diff(t1, t2) if t1 then return t1[1] ~= t2[1] else
> return t2 ~= nil end end
> > >+---
> > >+...
> > >+for i = 1, N * 10 do v = ''..i if diff(s1:get{v}, s2:get{v})
> then good = false end end
> > >+---
> > >+...
> > >+good
> > >+---
> > >+- true
> > >+...
> > >+s1.index[0]:bsize() < s2.index[0]:bsize()
> > >+---
> > >+- true
> > >+...
> > >+s1.index[0]:alter{hint=true}
> > >+---
> > >+...
> > >+s1.index[0]:bsize() == s2.index[0]:bsize()
> > >+---
> > >+- true
> > >+...
> > >+s2.index[0]:alter{hint=false}
> > >+---
> > >+...
> > >+s1.index[0]:bsize() > s2.index[0]:bsize()
> > >+---
> > >+- true
> > >+...
> > >+s1.index[0]:alter{hint=false}
> > >+---
> > >+...
> > >+s1.index[0]:bsize() == s2.index[0]:bsize()
> > >+---
> > >+- true
> > >+...
> > >+s1:drop()
> > >+---
> > >+...
> > >+s2:drop()
> > >+---
> > >+...
> > >+-- string with collation hints
> > >+s1 = box.schema.space.create('test1')
> > >+---
> > >+...
> > >+s1:create_index('test', {type = 'tree', parts = {{1, 'str',
> collation = 'Unicode'}}, hint = false}).hint
> > >+---
> > >+- false
> > >+...
> > >+s2 = box.schema.space.create('test2')
> > >+---
> > >+...
> > >+s2:create_index('test', {type = 'tree', parts = {{1, 'str',
> collation = 'Unicode'}}}).hint
> > >+---
> > >+- true
> > >+...
> > >+N = 1000
> > >+---
> > >+...
> > >+syms = {'a', 'B', 'c', 'D', 'ж', 'Ё', '~', '1', '%', '2'}
> > >+---
> > >+...
> > >+syms_size = #syms
> > >+---
> > >+...
> > >+len = 20
> > >+---
> > >+...
> > >+vals = {}
> > >+---
> > >+...
> > >+for i = 1,2*N do str = '' for j=1,len do str = str ..
> syms[math.random(syms_size)] end vals[i] = str end
> > >+---
> > >+...
> > >+for i = 1,N do local v = vals[i] s1:replace{v} s2:replace{v} end
> > >+---
> > >+...
> > >+s1:count() == s2:count()
> > >+---
> > >+- true
> > >+...
> > >+good = true r1 = s1:select{} r2 = s2:select{}
> > >+---
> > >+...
> > >+if #r1 ~= #r2 then good = false end
> > >+---
> > >+...
> > >+for k,v in pairs(r1) do if r2[k][1] ~= v[1] then good = false
> end end
> > >+---
> > >+...
> > >+good
> > >+---
> > >+- true
> > >+...
> > >+r1 = nil r2 = nil
> > >+---
> > >+...
> > >+function diff(t1, t2) if t1 then return t1[1] ~= t2[1] else
> return t2 ~= nil end end
> > >+---
> > >+...
> > >+for i = 1, N * 2 do v = vals[i] if diff(s1:get{v}, s2:get{v})
> then good = false end end
> > >+---
> > >+...
> > >+good
> > >+---
> > >+- true
> > >+...
> > >+s1.index[0]:bsize() < s2.index[0]:bsize()
> > >+---
> > >+- true
> > >+...
> > >+s1.index[0]:alter{hint=true}
> > >+---
> > >+...
> > >+s1.index[0]:bsize() == s2.index[0]:bsize()
> > >+---
> > >+- true
> > >+...
> > >+s2.index[0]:alter{hint=false}
> > >+---
> > >+...
> > >+s1.index[0]:bsize() > s2.index[0]:bsize()
> > >+---
> > >+- true
> > >+...
> > >+s1.index[0]:alter{hint=false}
> > >+---
> > >+...
> > >+s1.index[0]:bsize() == s2.index[0]:bsize()
> > >+---
> > >+- true
> > >+...
> > >+s1:drop()
> > >+---
> > >+...
> > >+s2:drop()
> > >+---
> > >+...
> > >diff --git a/test/box/tree_pk.test.lua b/test/box/tree_pk.test.lua
> > >index 1190ab4..2f22ed9 100644
> > >--- a/test/box/tree_pk.test.lua
> > >+++ b/test/box/tree_pk.test.lua
> > >@@ -301,3 +301,118 @@ s:drop()
> > >
> > > box.internal.collation.drop('test')
> > > box.internal.collation.drop('test-ci')
> > >+
> > >+-- hints
> > >+s = box.schema.space.create('test')
> > >+s:create_index('test', {type = 'tree', hint = 'true'} )
> > >+s:create_index('test', {type = 'hash', hint = true} )
> > >+s:create_index('test', {type = 'hash'}):alter({hint = true})
> > >+s:create_index('multikey', {hint = true, parts = {{2, 'int',
> path = '[*]'}}})
> > >+s:create_index('multikey', {parts = {{2, 'int', path =
> '[*]'}}}):alter({hint = true})
> > >+lua_code = [[function(tuple) return {tuple[1] + tuple[2]} end]]
> > >+box.schema.func.create('s', {body = lua_code, is_deterministic
> = true, is_sandboxed = true})
> > >+s:create_index('func', {hint = true, func = box.func.s.id,
> parts = {{1, 'unsigned'}}})
> > >+s:drop()
> > >+
> > >+s = box.schema.space.create('test', {engine = 'vinyl'})
> > >+s:create_index('test', {type = 'tree', hint = true} )
> > >+s:drop()
> > >+
> > >+-- numeric hints
> > >+s1 = box.schema.space.create('test1')
> > >+s1:create_index('test', {type = 'tree', hint = false}).hint
> > >+s2 = box.schema.space.create('test2')
> > >+s2:create_index('test', {type = 'tree'}).hint
> > >+
> > >+N = 2000
> > >+box.begin() for i = 1,N do local v = math.random(10 * N)
> s1:replace{v} s2:replace{v} end box.commit()
> > >+s1:count() == s2:count()
> > >+
> > >+good = true r1 = s1:select{} r2 = s2:select{}
> > >+if #r1 ~= #r2 then good = false end
> > >+for k,v in pairs(r1) do if r2[k][1] ~= v[1] then good = false
> end end
> > >+good
> > >+r1 = nil r2 = nil
> > >+
> > >+function diff(t1, t2) if t1 then return t1[1] ~= t2[1] else
> return t2 ~= nil end end
> > >+for i = 1, N * 10 do if diff(s1:get{i}, s2:get{i}) then good =
> false end end
> > >+good
> > >+
> > >+s1.index[0]:bsize() < s2.index[0]:bsize()
> > >+s1.index[0]:alter{hint=true}
> > >+s1.index[0]:bsize() == s2.index[0]:bsize()
> > >+s2.index[0]:alter{hint=false}
> > >+s1.index[0]:bsize() > s2.index[0]:bsize()
> > >+s1.index[0]:alter{hint=false}
> > >+s1.index[0]:bsize() == s2.index[0]:bsize()
> > >+
> > >+s1:drop()
> > >+s2:drop()
> > >+
> > >+-- string hints
> > >+s1 = box.schema.space.create('test1')
> > >+s1:create_index('test', {type = 'tree', parts = {1, 'str'},
> hint = false}).hint
> > >+s2 = box.schema.space.create('test2')
> > >+s2:create_index('test', {type = 'tree', parts = {1, 'str'}}).hint
> > >+
> > >+N = 1000
> > >+box.begin() for i = 1,N do local v = ''..math.random(10 * N)
> s1:replace{v} s2:replace{v} end box.commit()
> > >+s1:count() == s2:count()
> > >+
> > >+good = true r1 = s1:select{} r2 = s2:select{}
> > >+if #r1 ~= #r2 then good = false end
> > >+for k,v in pairs(r1) do if r2[k][1] ~= v[1] then good = false
> end end
> > >+good
> > >+r1 = nil r2 = nil
> > >+
> > >+function diff(t1, t2) if t1 then return t1[1] ~= t2[1] else
> return t2 ~= nil end end
> > >+for i = 1, N * 10 do v = ''..i if diff(s1:get{v}, s2:get{v})
> then good = false end end
> > >+good
> > >+
> > >+s1.index[0]:bsize() < s2.index[0]:bsize()
> > >+s1.index[0]:alter{hint=true}
> > >+s1.index[0]:bsize() == s2.index[0]:bsize()
> > >+s2.index[0]:alter{hint=false}
> > >+s1.index[0]:bsize() > s2.index[0]:bsize()
> > >+s1.index[0]:alter{hint=false}
> > >+s1.index[0]:bsize() == s2.index[0]:bsize()
> > >+
> > >+s1:drop()
> > >+s2:drop()
> > >+
> > >+-- string with collation hints
> > >+s1 = box.schema.space.create('test1')
> > >+s1:create_index('test', {type = 'tree', parts = {{1, 'str',
> collation = 'Unicode'}}, hint = false}).hint
> > >+s2 = box.schema.space.create('test2')
> > >+s2:create_index('test', {type = 'tree', parts = {{1, 'str',
> collation = 'Unicode'}}}).hint
> > >+
> > >+N = 1000
> > >+syms = {'a', 'B', 'c', 'D', 'ж', 'Ё', '~', '1', '%', '2'}
> > >+syms_size = #syms
> > >+len = 20
> > >+vals = {}
> > >+for i = 1,2*N do str = '' for j=1,len do str = str ..
> syms[math.random(syms_size)] end vals[i] = str end
> > >+
> > >+for i = 1,N do local v = vals[i] s1:replace{v} s2:replace{v} end
> > >+s1:count() == s2:count()
> > >+
> > >+good = true r1 = s1:select{} r2 = s2:select{}
> > >+if #r1 ~= #r2 then good = false end
> > >+for k,v in pairs(r1) do if r2[k][1] ~= v[1] then good = false
> end end
> > >+good
> > >+r1 = nil r2 = nil
> > >+
> > >+function diff(t1, t2) if t1 then return t1[1] ~= t2[1] else
> return t2 ~= nil end end
> > >+for i = 1, N * 2 do v = vals[i] if diff(s1:get{v}, s2:get{v})
> then good = false end end
> > >+good
> > >+
> > >+s1.index[0]:bsize() < s2.index[0]:bsize()
> > >+s1.index[0]:alter{hint=true}
> > >+s1.index[0]:bsize() == s2.index[0]:bsize()
> > >+s2.index[0]:alter{hint=false}
> > >+s1.index[0]:bsize() > s2.index[0]:bsize()
> > >+s1.index[0]:alter{hint=false}
> > >+s1.index[0]:bsize() == s2.index[0]:bsize()
> > >+
> > >+s1:drop()
> > >+s2:drop()
> > >diff --git a/test/box/tree_pk_multipart.result
> b/test/box/tree_pk_multipart.result
> > >index 93219f6..3f6bb94 100644
> > >--- a/test/box/tree_pk_multipart.result
> > >+++ b/test/box/tree_pk_multipart.result
> > >@@ -542,3 +542,156 @@ space:drop()
> > > space = nil
> > > ---
> > > ...
> > >+-- hints
> > >+test_run:cmd("setopt delimiter ';'")
> > >+---
> > >+- true
> > >+...
> > >+function equal(res1, res2)
> > >+ if #res1 ~= #res2 then
> > >+ return false
> > >+ end
> > >+ for k,v in pairs(res1) do
> > >+ if res2[k][1] ~= v[1] or res2[k][2] ~= v[2] then
> > >+ return false
> > >+ end
> > >+ end
> > >+ return true
> > >+end
> > >+test_run:cmd("setopt delimiter ''");
> > >+---
> > >+...
> > >+-- num num
> > >+N1 = 100
> > >+---
> > >+...
> > >+t1 = {}
> > >+---
> > >+...
> > >+for i = 1,N1*2 do t1[i] = math.random(10000) * 10000 + i end
> > >+---
> > >+...
> > >+N2 = 5
> > >+---
> > >+...
> > >+t2 = {}
> > >+---
> > >+...
> > >+for i = 1,N2*2 do t2[i] = math.random(1000000) end
> > >+---
> > >+...
> > >+s1 = box.schema.space.create('test1')
> > >+---
> > >+...
> > >+s1:create_index('test', {type = 'tree', parts = {{1, 'num'},
> {2, 'num'}}, hint = false}).hint
> > >+---
> > >+- false
> > >+...
> > >+s2 = box.schema.space.create('test2')
> > >+---
> > >+...
> > >+s2:create_index('test', {type = 'tree', parts = {{1, 'num'},
> {2, 'num'}}, hint = true}).hint
> > >+---
> > >+- true
> > >+...
> > >+for j = 1,N2 do for i = 1,N1 do s1:replace{t1[i], t2[j]}
> s2:replace{t1[i], t2[j]} end end
> > >+---
> > >+...
> > >+s1:count() == s2:count()
> > >+---
> > >+- true
> > >+...
> > >+equal(s1:select{}, s2:select{})
> > >+---
> > >+- true
> > >+...
> > >+good = true
> > >+---
> > >+...
> > >+for i = 1,N1*2 do good = good and equal(s1:select{t1[i]},
> s2:select{t1[i]}) end
> > >+---
> > >+...
> > >+good
> > >+---
> > >+- true
> > >+...
> > >+for i = 1,N1*2 do for j=1,N2*2 do good = good and
> equal(s1:select{t1[i], t2[j]}, s2:select{t1[i], t2[j]}) end end
> > >+---
> > >+...
> > >+good
> > >+---
> > >+- true
> > >+...
> > >+s1:drop()
> > >+---
> > >+...
> > >+s2:drop()
> > >+---
> > >+...
> > >+-- str num
> > >+N1 = 100
> > >+---
> > >+...
> > >+t1 = {}
> > >+---
> > >+...
> > >+for i = 1,N1*2 do t1[i] = ''..(math.random(10000) * 10000 + i) end
> > >+---
> > >+...
> > >+N2 = 5
> > >+---
> > >+...
> > >+t2 = {}
> > >+---
> > >+...
> > >+for i = 1,N2*2 do t2[i] = math.random(1000000) end
> > >+---
> > >+...
> > >+s1 = box.schema.space.create('test1')
> > >+---
> > >+...
> > >+s1:create_index('test', {type = 'tree', parts = {{1, 'str'},
> {2, 'num'}}, hint = false}).hint
> > >+---
> > >+- false
> > >+...
> > >+s2 = box.schema.space.create('test2')
> > >+---
> > >+...
> > >+s2:create_index('test', {type = 'tree', parts = {{1, 'str'},
> {2, 'num'}}, hint = true}).hint
> > >+---
> > >+- true
> > >+...
> > >+for j = 1,N2 do for i = 1,N1 do s1:replace{t1[i], t2[j]}
> s2:replace{t1[i], t2[j]} end end
> > >+---
> > >+...
> > >+s1:count() == s2:count()
> > >+---
> > >+- true
> > >+...
> > >+equal(s1:select{}, s2:select{})
> > >+---
> > >+- true
> > >+...
> > >+good = true
> > >+---
> > >+...
> > >+for i = 1,N1*2 do good = good and equal(s1:select{t1[i]},
> s2:select{t1[i]}) end
> > >+---
> > >+...
> > >+good
> > >+---
> > >+- true
> > >+...
> > >+for i = 1,N1*2 do for j=1,N2*2 do good = good and
> equal(s1:select{t1[i], t2[j]}, s2:select{t1[i], t2[j]}) end end
> > >+---
> > >+...
> > >+good
> > >+---
> > >+- true
> > >+...
> > >+s1:drop()
> > >+---
> > >+...
> > >+s2:drop()
> > >+---
> > >+...
> > >diff --git a/test/box/tree_pk_multipart.test.lua
> b/test/box/tree_pk_multipart.test.lua
> > >index 7d3405f..cba3a98 100644
> > >--- a/test/box/tree_pk_multipart.test.lua
> > >+++ b/test/box/tree_pk_multipart.test.lua
> > >@@ -194,3 +194,67 @@ test_run:cmd("setopt delimiter ''");
> > > space:drop()
> > >
> > > space = nil
> > >+
> > >+
> > >+-- hints
> > >+test_run:cmd("setopt delimiter ';'")
> > >+function equal(res1, res2)
> > >+ if #res1 ~= #res2 then
> > >+ return false
> > >+ end
> > >+ for k,v in pairs(res1) do
> > >+ if res2[k][1] ~= v[1] or res2[k][2] ~= v[2] then
> > >+ return false
> > >+ end
> > >+ end
> > >+ return true
> > >+end
> > >+test_run:cmd("setopt delimiter ''");
> > >+
> > >+-- num num
> > >+N1 = 100
> > >+t1 = {}
> > >+for i = 1,N1*2 do t1[i] = math.random(10000) * 10000 + i end
> > >+N2 = 5
> > >+t2 = {}
> > >+for i = 1,N2*2 do t2[i] = math.random(1000000) end
> > >+
> > >+s1 = box.schema.space.create('test1')
> > >+s1:create_index('test', {type = 'tree', parts = {{1, 'num'},
> {2, 'num'}}, hint = false}).hint
> > >+s2 = box.schema.space.create('test2')
> > >+s2:create_index('test', {type = 'tree', parts = {{1, 'num'},
> {2, 'num'}}, hint = true}).hint
> > >+for j = 1,N2 do for i = 1,N1 do s1:replace{t1[i], t2[j]}
> s2:replace{t1[i], t2[j]} end end
> > >+s1:count() == s2:count()
> > >+equal(s1:select{}, s2:select{})
> > >+good = true
> > >+for i = 1,N1*2 do good = good and equal(s1:select{t1[i]},
> s2:select{t1[i]}) end
> > >+good
> > >+for i = 1,N1*2 do for j=1,N2*2 do good = good and
> equal(s1:select{t1[i], t2[j]}, s2:select{t1[i], t2[j]}) end end
> > >+good
> > >+
> > >+s1:drop()
> > >+s2:drop()
> > >+
> > >+-- str num
> > >+N1 = 100
> > >+t1 = {}
> > >+for i = 1,N1*2 do t1[i] = ''..(math.random(10000) * 10000 + i) end
> > >+N2 = 5
> > >+t2 = {}
> > >+for i = 1,N2*2 do t2[i] = math.random(1000000) end
> > >+
> > >+s1 = box.schema.space.create('test1')
> > >+s1:create_index('test', {type = 'tree', parts = {{1, 'str'},
> {2, 'num'}}, hint = false}).hint
> > >+s2 = box.schema.space.create('test2')
> > >+s2:create_index('test', {type = 'tree', parts = {{1, 'str'},
> {2, 'num'}}, hint = true}).hint
> > >+for j = 1,N2 do for i = 1,N1 do s1:replace{t1[i], t2[j]}
> s2:replace{t1[i], t2[j]} end end
> > >+s1:count() == s2:count()
> > >+equal(s1:select{}, s2:select{})
> > >+good = true
> > >+for i = 1,N1*2 do good = good and equal(s1:select{t1[i]},
> s2:select{t1[i]}) end
> > >+good
> > >+for i = 1,N1*2 do for j=1,N2*2 do good = good and
> equal(s1:select{t1[i], t2[j]}, s2:select{t1[i], t2[j]}) end end
> > >+good
> > >+
> > >+s1:drop()
> > >+s2:drop()
> > >--
> > >2.7.4
> > >
> > --
> > Ilya Kosarev
>
>
> --
> Ilya Kosarev
next prev parent reply other threads:[~2020-10-21 9:54 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-10-19 9:51 [Tarantool-patches] [PATCH 0/2] Make tree hint optional Aleksandr Lyapunov
2020-10-19 9:51 ` [Tarantool-patches] [PATCH 1/2] memtx: move memtx_tree.c to memtx_tree.cc Aleksandr Lyapunov
2020-10-19 9:51 ` [Tarantool-patches] [PATCH 2/2] memtx: make tuple compare hints optional Aleksandr Lyapunov
2020-10-20 12:34 ` Ilya Kosarev
2020-10-20 12:37 ` Nikita Pettik
2020-10-20 12:57 ` Ilya Kosarev
2020-10-21 9:54 ` Aleksandr Lyapunov [this message]
2020-10-20 1:01 ` [Tarantool-patches] [PATCH 0/2] Make tree hint optional Nikita Pettik
2020-10-21 17:02 ` Alexander V. Tikhonov
2020-10-21 17:06 ` Nikita Pettik
-- strict thread matches above, loose matches on Subject: below --
2020-10-19 9:26 Aleksandr Lyapunov
2020-10-19 9:26 ` [Tarantool-patches] [PATCH 2/2] memtx: make tuple compare hints optional Aleksandr Lyapunov
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=8f24eadb-ef3c-730a-caad-27b03b1deecd@tarantool.org \
--to=alyapunov@tarantool.org \
--cc=i.kosarev@tarantool.org \
--cc=korablev@tarantool.org \
--cc=tarantool-patches@dev.tarantool.org \
--subject='Re: [Tarantool-patches] [PATCH 2/2] memtx: make tuple compare hints optional' \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox