[PATCH v1 3/4] box: introduce tuple compare hint

[Vladimir Davydov]

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;
>  	/**