[PATCH v2 6/7] vinyl: prepare for storing hints in vinyl data structures
Vladimir Davydov
vdavydov.dev at gmail.com
Sat Apr 6 23:01:53 MSK 2019
This patch adds a helper struct vy_entry, which unites a statement with
a hint. We will use this struct to store hinted statements in vinyl data
structures, such as cache or memory tree.
Note, it's defined in a separate file to minimize dependencies.
---
src/box/key_def.h | 17 +++++++
src/box/tuple_compare.cc | 11 +++++
src/box/vy_entry.h | 79 +++++++++++++++++++++++++++++++++
src/box/vy_stmt.h | 113 +++++++++++++++++++++++++++++++++++++++++++++++
4 files changed, 220 insertions(+)
create mode 100644 src/box/vy_entry.h
diff --git a/src/box/key_def.h b/src/box/key_def.h
index c269482a..6205c278 100644
--- a/src/box/key_def.h
+++ b/src/box/key_def.h
@@ -570,6 +570,23 @@ int
key_compare(const char *key_a, const char *key_b, struct key_def *key_def);
/**
+ * Compare keys using the key definition and comparison hints.
+ * @param key_a key parts with MessagePack array header
+ * @param key_a_hint comparison hint of @a key_a
+ * @param key_b key_parts with MessagePack array header
+ * @param key_b_hint comparison hint of @a key_b
+ * @param key_def key definition
+ *
+ * @retval 0 if key_a == key_b
+ * @retval <0 if key_a < key_b
+ * @retval >0 if key_a > key_b
+ */
+int
+key_compare_hinted(const char *key_a, hint_t key_a_hint,
+ const char *key_b, hint_t key_b_hint,
+ struct key_def *key_def);
+
+/**
* Compare tuples using the key definition.
* @param tuple_a first tuple
* @param tuple_b second tuple
diff --git a/src/box/tuple_compare.cc b/src/box/tuple_compare.cc
index b80777c8..a3cabf19 100644
--- a/src/box/tuple_compare.cc
+++ b/src/box/tuple_compare.cc
@@ -817,6 +817,17 @@ key_compare(const char *key_a, const char *key_b, struct key_def *key_def)
}
}
+int
+key_compare_hinted(const char *key_a, hint_t key_a_hint,
+ const char *key_b, hint_t key_b_hint,
+ struct key_def *key_def)
+{
+ int rc = hint_cmp(key_a_hint, key_b_hint);
+ if (rc != 0)
+ return rc;
+ return key_compare(key_a, key_b, key_def);
+}
+
template <bool is_nullable, bool has_optional_parts>
static int
tuple_compare_sequential_hinted(struct tuple *tuple_a, hint_t tuple_a_hint,
diff --git a/src/box/vy_entry.h b/src/box/vy_entry.h
new file mode 100644
index 00000000..54ae68f0
--- /dev/null
+++ b/src/box/vy_entry.h
@@ -0,0 +1,79 @@
+#ifndef INCLUDES_TARANTOOL_BOX_VY_ENTRY_H
+#define INCLUDES_TARANTOOL_BOX_VY_ENTRY_H
+/*
+ * Copyright 2010-2016, Tarantool AUTHORS, please see AUTHORS file.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above
+ * copyright notice, this list of conditions and the
+ * following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following
+ * disclaimer in the documentation and/or other materials
+ * provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY AUTHORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
+ * AUTHORS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
+ * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+#include <stdbool.h>
+#include <stddef.h>
+
+#include "tuple_compare.h" /* hint_t */
+
+#if defined(__cplusplus)
+extern "C" {
+#endif /* defined(__cplusplus) */
+
+struct tuple;
+
+/**
+ * A helper struct that encapsulates a tuple with a comparison hint.
+ * It is used for storing statements in vinyl containers, e.g. cache
+ * or memory tree. Passed around by value.
+ */
+struct vy_entry {
+ struct tuple *stmt;
+ hint_t hint;
+};
+
+/**
+ * Return an entry that doesn't point to any statement.
+ */
+static inline struct vy_entry
+vy_entry_none(void)
+{
+ struct vy_entry entry;
+ entry.stmt = NULL;
+ entry.hint = HINT_NONE;
+ return entry;
+}
+
+/**
+ * Return true if two entries point to the same statements.
+ */
+static inline bool
+vy_entry_is_equal(struct vy_entry a, struct vy_entry b)
+{
+ return a.stmt == b.stmt && a.hint == b.hint;
+}
+
+#if defined(__cplusplus)
+} /* extern "C" */
+#endif /* defined(__cplusplus) */
+
+#endif /* INCLUDES_TARANTOOL_BOX_VY_ENTRY_H */
diff --git a/src/box/vy_stmt.h b/src/box/vy_stmt.h
index 6069e093..cc8a9c5d 100644
--- a/src/box/vy_stmt.h
+++ b/src/box/vy_stmt.h
@@ -41,6 +41,7 @@
#include "tuple.h"
#include "iproto_constants.h"
+#include "vy_entry.h"
#if defined(__cplusplus)
extern "C" {
@@ -363,6 +364,21 @@ vy_stmt_unref_if_possible(struct tuple *stmt)
}
/**
+ * Return a comparison hint of a vinyl statement.
+ */
+static inline hint_t
+vy_stmt_hint(struct tuple *stmt, struct key_def *key_def)
+{
+ if (vy_stmt_is_key(stmt)) {
+ const char *key = tuple_data(stmt);
+ uint32_t part_count = mp_decode_array(&key);
+ return key_hint(key, part_count, key_def);
+ } else {
+ return tuple_hint(stmt, key_def);
+ }
+}
+
+/**
* Compare two vinyl statements taking into account their
* formats (key or tuple).
*/
@@ -388,6 +404,36 @@ vy_stmt_compare(struct tuple *a, struct tuple *b, struct key_def *key_def)
}
/**
+ * Compare two vinyl statements taking into account their
+ * formats (key or tuple) and using comparison hints.
+ */
+static inline int
+vy_stmt_compare_hinted(struct tuple *a, hint_t a_hint,
+ struct tuple *b, hint_t b_hint,
+ struct key_def *key_def)
+{
+ bool a_is_tuple = !vy_stmt_is_key(a);
+ bool b_is_tuple = !vy_stmt_is_key(b);
+ if (a_is_tuple && b_is_tuple) {
+ return tuple_compare_hinted(a, a_hint, b, b_hint, key_def);
+ } else if (a_is_tuple && !b_is_tuple) {
+ const char *key = tuple_data(b);
+ uint32_t part_count = mp_decode_array(&key);
+ return tuple_compare_with_key_hinted(a, a_hint, key, part_count,
+ b_hint, key_def);
+ } else if (!a_is_tuple && b_is_tuple) {
+ const char *key = tuple_data(a);
+ uint32_t part_count = mp_decode_array(&key);
+ return -tuple_compare_with_key_hinted(b, b_hint, key, part_count,
+ a_hint, key_def);
+ } else {
+ assert(!a_is_tuple && !b_is_tuple);
+ return key_compare_hinted(tuple_data(a), a_hint,
+ tuple_data(b), b_hint, key_def);
+ }
+}
+
+/**
* Compare a vinyl statement (key or tuple) with a raw key
* (msgpack array).
*/
@@ -403,6 +449,25 @@ vy_stmt_compare_with_raw_key(struct tuple *stmt, const char *key,
}
/**
+ * Compare a vinyl statement (key or tuple) with a raw key
+ * (msgpack array) using comparison hints.
+ */
+static inline int
+vy_stmt_compare_with_raw_key_hinted(struct tuple *stmt, hint_t stmt_hint,
+ const char *key, hint_t key_hint,
+ struct key_def *key_def)
+{
+ if (!vy_stmt_is_key(stmt)) {
+ uint32_t part_count = mp_decode_array(&key);
+ return tuple_compare_with_key_hinted(stmt, stmt_hint,
+ key, part_count, key_hint,
+ key_def);
+ }
+ return key_compare_hinted(tuple_data(stmt), stmt_hint,
+ key, key_hint, key_def);
+}
+
+/**
* Create a key statement from raw MessagePack data.
* @param format Format of an index.
* @param key MessagePack data that contain an array of
@@ -664,6 +729,54 @@ vy_stmt_snprint(char *buf, int size, struct tuple *stmt);
const char *
vy_stmt_str(struct tuple *stmt);
+/**
+ * Create a key entry from a MessagePack array without a header.
+ */
+static inline struct vy_entry
+vy_entry_key_new(struct tuple_format *format, struct key_def *key_def,
+ const char *key, uint32_t part_count)
+{
+ struct vy_entry entry;
+ entry.stmt = vy_key_new(format, key, part_count);
+ if (entry.stmt == NULL)
+ return vy_entry_none();
+ entry.hint = key_hint(key, part_count, key_def);
+ return entry;
+}
+
+/**
+ * Create a key entry from a MessagePack array.
+ */
+static inline struct vy_entry
+vy_entry_key_from_msgpack(struct tuple_format *format, struct key_def *key_def,
+ const char *key)
+{
+ uint32_t part_count = mp_decode_array(&key);
+ return vy_entry_key_new(format, key_def, key, part_count);
+}
+
+/**
+ * Compare the statements stored in the given entries.
+ */
+static inline int
+vy_entry_compare(struct vy_entry a, struct vy_entry b, struct key_def *key_def)
+{
+ return vy_stmt_compare_hinted(a.stmt, a.hint, b.stmt, b.hint, key_def);
+}
+
+/**
+ * Compare a statement stored in the given entry with a raw key
+ * (msgpack array).
+ */
+static inline int
+vy_entry_compare_with_raw_key(struct vy_entry entry,
+ const char *key, hint_t key_hint,
+ struct key_def *key_def)
+{
+ return vy_stmt_compare_with_raw_key_hinted(entry.stmt, entry.hint,
+ key, key_hint, key_def);
+}
+
#if defined(__cplusplus)
} /* extern "C" */
#endif /* defined(__cplusplus) */
--
2.11.0
More information about the Tarantool-patches
mailing list