From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Date: Mon, 11 Feb 2019 18:57:20 +0300 From: Vladimir Davydov Subject: Re: [PATCH v1 3/4] box: introduce tuple compare hint Message-ID: <20190211155720.nj2lpk77ubiwu7hz@esperanza> References: <535f26d85705f8157737bca7ed4978d4c9a016f4.1549367041.git.kshcherbatov@tarantool.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <535f26d85705f8157737bca7ed4978d4c9a016f4.1549367041.git.kshcherbatov@tarantool.org> To: Kirill Shcherbatov Cc: tarantool-patches@freelists.org, Alexandr Lyapunov List-ID: On Tue, Feb 05, 2019 at 02:58:38PM +0300, Kirill Shcherbatov wrote: > +static uint64_t > +key_hint_string(const char *key, struct key_def *key_def) > +{ > + (void)key_def; > + assert(key_def->parts->type == FIELD_TYPE_STRING); > + assert(mp_typeof(*key) == MP_STR); > + uint32_t len; > + const unsigned char *str = > + (const unsigned char *)mp_decode_str(&key, &len); > + uint64_t result = 0; > + uint32_t process_len = MIN(len, 7); > + for (uint32_t i = 0; i < process_len; i++) { > + result <<= 9; > + result |= 0x100; > + result |= str[i]; > + } > + result <<= 9 * (7 - process_len); > + return result; I don't understand this part. I'd expect you to compare the strings byte-wise. Please add a comment explaining what's going on here. > diff --git a/src/box/tuple_compare.h b/src/box/tuple_compare.h > index e3a63204f..be96ba38c 100644 > --- a/src/box/tuple_compare.h > +++ b/src/box/tuple_compare.h > @@ -67,6 +67,46 @@ tuple_compare_create(const struct key_def *key_def); > tuple_compare_with_key_t > tuple_compare_with_key_create(const struct key_def *key_def); > > +/** > + * Get a comparison hint of a tuple. > + * Hint is such a function h(tuple) in terms of particular key_def that > + * has follows rules: the following rules > + * if h(t1) < h(t2) then t1 < t2; > + * if h(t1) > h(t2) then t1 > t2; > + * if t1 == t2 then h(t1) == h(t2); > + * These rules means that instead of direct tuple vs tuple (or tuple vs key) mean > + * comparison one may compare theirs hints first; and only if theirs hints > + * are equal compare the tuples themselves. > + * @param tuple - tuple to get hint of. > + * @param key_def - key_def that defines which comparison is used. > + * @return the hint. > + */ > +static inline uint64_t > +tuple_hint(const struct tuple *tuple, struct key_def *key_def) > +{ > + return key_def->tuple_hint(tuple, key_def); > +} > + > +/** > + * Get a comparison hint of a key. > + * @See tuple_hint for hint term definition. > + * @param key - key to get hint of. > + * @param key_def - key_def that defines which comparison is used. > + * @return the hint. > + */ > +static inline uint64_t > +key_hint(const char *key, struct key_def *key_def) > +{ > + return key_def->key_hint(key, key_def); > +} All the above functions should be defined in key_def.h, where 'hash' and 'compare' reside. > + > +/** > + * Initialize tuple_hint() and key_hint() functions for the key_def. > + * @param key_def key definition to set up. > + */ > +void > +tuple_hint_set(struct key_def *key_def); > + > #if defined(__cplusplus) > } /* extern "C" */ > #endif /* defined(__cplusplus) */ > diff --git a/src/coll.h b/src/coll.h > index 9c725712a..4030d38de 100644 > --- a/src/coll.h > +++ b/src/coll.h > @@ -47,6 +47,8 @@ typedef int (*coll_cmp_f)(const char *s, size_t s_len, const char *t, > typedef uint32_t (*coll_hash_f)(const char *s, size_t s_len, uint32_t *ph, > uint32_t *pcarry, struct coll *coll); > > +typedef uint64_t (*coll_hint_f)(const char *s, size_t s_len, struct coll *coll); > + > struct UCollator; > > /** > @@ -61,6 +63,7 @@ struct coll { > /** String comparator. */ > coll_cmp_f cmp; > coll_hash_f hash; > + coll_hint_f hint; Please add a comment. > /** Reference counter. */ > int refs; > /**