From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: From: Vladimir Davydov Subject: [PATCH v2 6/7] vinyl: prepare for storing hints in vinyl data structures Date: Sat, 6 Apr 2019 23:01:53 +0300 Message-Id: In-Reply-To: References: In-Reply-To: References: To: tarantool-patches@freelists.org List-ID: 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 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 +#include + +#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