[Tarantool-patches] [PATCH 2/4] box: add binary search for _session_settings space
Nikita Pettik
korablev at tarantool.org
Fri Apr 3 17:00:17 MSK 2020
On 30 Mar 12:13, Chris Sosnin wrote:
> As it is mentioned in implementation, it is important
> that _session_settings options are sorted by name, so
> there is no need in linear lookup and we can replace it
> with binary search.
>
> Closes #4712
> ---
Still I see no need for this patch. It is unclear which improvements
it introduces except for code complication.
> diff --git a/src/box/session_settings.c b/src/box/session_settings.c
> index 2ecf71f2d..5e4a50427 100644
> --- a/src/box/session_settings.c
> +++ b/src/box/session_settings.c
> @@ -81,6 +81,8 @@ struct session_settings_iterator {
> bool is_eq;
> /** True if the iterator should include equal keys. */
> bool is_including;
> + /** True if the iterator is pointing to an existing setting */
> + bool is_set;
> };
>
> static void
> @@ -92,6 +94,72 @@ session_settings_iterator_free(struct iterator *ptr)
> free(it);
> }
>
> +static int
> +session_settings_set_forward(int *sid, const char *key, bool is_eq,
> + bool is_including)
> +{
> + int low = 0, high = SESSION_SETTING_COUNT - 1;
> + if (key == NULL)
> + return 0;
> + while (low <= high) {
> + int index = (high + low) / 2;
> + const char *name = session_setting_strs[index];
> + int cmp = strcmp(name, key);
> + if (cmp == 0) {
> + if (is_including) {
> + *sid = index;
> + return 0;
> + }
> + *sid = ++index;
> + return index < SESSION_SETTING_COUNT ? 0 : -1;
> + }
> + if (cmp < 0)
> + low = index + 1;
> + else
> + high = index - 1;
> + }
> + if (is_eq) {
> + *sid = SESSION_SETTING_COUNT;
> + return -1;
> + }
> + assert(low > high);
> + *sid = low;
> + return low < SESSION_SETTING_COUNT ? 0 : -1;
> +}
> +
> +static int
> +session_settings_set_reverse(int *sid, const char *key, bool is_eq,
> + bool is_including)
> +{
> + int low = 0, high = SESSION_SETTING_COUNT - 1;
> + if (key == NULL)
> + return 0;
> + while (low <= high) {
> + int index = (high + low) / 2;
> + const char *name = session_setting_strs[index];
> + int cmp = strcmp(name, key);
> + if (cmp == 0) {
> + if (is_including) {
> + *sid = index;
> + return 0;
> + }
> + *sid = --index;
> + return index >= 0 ? 0 : -1;
> + }
> + if (cmp < 0)
> + low = index + 1;
> + else
> + high = index - 1;
> + }
> + if (is_eq) {
> + *sid = SESSION_SETTING_COUNT;
> + return -1;
> + }
> + assert(low > high);
> + *sid = high;
> + return high >= 0 ? 0 : -1;
> +}
> +
> static int
> session_settings_next(int *sid, const char *key, bool is_eq, bool is_including)
> {
> @@ -145,9 +213,15 @@ session_settings_iterator_next(struct iterator *iterator, struct tuple **result)
> int sid = it->setting_id;
> const char *key = it->key;
> bool is_including = it->is_including, is_eq = it->is_eq;
> - bool is_found = false;
> - if (session_settings_next(&sid, key, is_eq, is_including) == 0)
> - is_found = true;
> + bool is_found;
> + if (!it->is_set) {
> + it->is_set = true;
> + is_found = session_settings_set_forward(&sid, key, is_eq,
> + is_including) == 0;
> + } else {
> + is_found = session_settings_next(&sid, key, is_eq,
> + is_including) == 0;
> + }
> it->setting_id = sid + 1;
> if (!is_found) {
> *result = NULL;
> @@ -167,9 +241,15 @@ session_settings_iterator_prev(struct iterator *iterator, struct tuple **result)
> int sid = it->setting_id;
> const char *key = it->key;
> bool is_including = it->is_including, is_eq = it->is_eq;
> - bool is_found = false;
> - if (session_settings_prev(&sid, key, is_eq, is_including) == 0)
> - is_found = true;
> + bool is_found;
> + if (!it->is_set) {
> + it->is_set = true;
> + is_found = session_settings_set_reverse(&sid, key, is_eq,
> + is_including) == 0;
> + } else {
> + is_found = session_settings_prev(&sid, key, is_eq,
> + is_including) == 0;
> + }
> it->setting_id = sid - 1;
> if (!is_found) {
> *result = NULL;
> @@ -221,6 +301,7 @@ session_settings_index_create_iterator(struct index *base,
> it->is_eq = type == ITER_EQ || type == ITER_REQ;
> it->is_including = it->is_eq || type == ITER_GE || type == ITER_ALL ||
> type == ITER_LE;
> + it->is_set = false;
> it->format = index->format;
> if (!iterator_type_is_reverse(type)) {
> it->base.next = session_settings_iterator_next;
> @@ -244,7 +325,7 @@ session_settings_index_get(struct index *base, const char *key,
> key = mp_decode_str(&key, &len);
> key = tt_cstr(key, len);
> int sid = 0;
> - if (session_settings_next(&sid, key, true, true) != 0) {
> + if (session_settings_set_forward(&sid, key, true, true) != 0) {
> *result = NULL;
> return 0;
> }
> @@ -345,7 +426,7 @@ session_settings_space_execute_update(struct space *space, struct txn *txn,
> }
> key = mp_decode_str(&key, &key_len);
> key = tt_cstr(key, key_len);
> - if (session_settings_next(&sid, key, true, true) != 0) {
> + if (session_settings_set_forward(&sid, key, true, true) != 0) {
> *result = NULL;
> return 0;
> }
> diff --git a/test/box/gh-4511-access-settings-from-any-frontend.result b/test/box/gh-4511-access-settings-from-any-frontend.result
> index ed340d053..bae77192e 100644
> --- a/test/box/gh-4511-access-settings-from-any-frontend.result
> +++ b/test/box/gh-4511-access-settings-from-any-frontend.result
> @@ -82,6 +82,12 @@ function check_sorting(ss, ts, key)
> for _, it in pairs(iterators_list) do
> local view_space = ss:select({key}, {iterator = it})
> local test_space = ts:select({key}, {iterator = it})
> + if #view_space ~= #test_space then
> + return {
> + err = 'bad sorting', type = it, exp = test_space,
> + got = view_space
> + }
> + end
> for key, value in pairs(view_space) do
> if test_space[key].name ~= value.name then
> return {
> @@ -111,32 +117,37 @@ check_sorting(s, t, 'sql_d')
> check_sorting(s, t, 'sql_v')
> | ---
> | ...
> -check_sorting(s, t, 'sql_defer_foreign_keys')
> +check_sorting(s, t, 'z')
> | ---
> | ...
> -
> -t:drop()
> +check_sorting(s, t, 'sql_parser_debuf')
> + | ---
> + | ...
> +check_sorting(s, t, 'sql_parser_debuh')
> | ---
> | ...
>
> --- Check get() method of session_settings space.
> -s:get({'sql_defer_foreign_keys'})
> +name = nil
> | ---
> - | - ['sql_defer_foreign_keys', false]
> | ...
> -s:get({'sql_recursive_triggers'})
> +err = nil
> | ---
> - | - ['sql_recursive_triggers', true]
> | ...
> -s:get({'sql_reverse_unordered_selects'})
> +for _, tuple in t:pairs() do \
> + name = tuple.name \
> + err = check_sorting(s, t, name) \
> + if err then \
> + break \
> + end \
> +end
> | ---
> - | - ['sql_reverse_unordered_selects', false]
> | ...
> -s:get({'sql_default_engine'})
> +err and {err, name}
> | ---
> - | - ['sql_default_engine', 'memtx']
> + | - null
> | ...
> -s:get({'abcd'})
> +
> +t:drop()
> | ---
> | ...
>
> diff --git a/test/box/gh-4511-access-settings-from-any-frontend.test.lua b/test/box/gh-4511-access-settings-from-any-frontend.test.lua
> index 366874998..b243be15e 100644
> --- a/test/box/gh-4511-access-settings-from-any-frontend.test.lua
> +++ b/test/box/gh-4511-access-settings-from-any-frontend.test.lua
> @@ -36,6 +36,12 @@ function check_sorting(ss, ts, key)
> for _, it in pairs(iterators_list) do
> local view_space = ss:select({key}, {iterator = it})
> local test_space = ts:select({key}, {iterator = it})
> + if #view_space ~= #test_space then
> + return {
> + err = 'bad sorting', type = it, exp = test_space,
> + got = view_space
> + }
> + end
> for key, value in pairs(view_space) do
> if test_space[key].name ~= value.name then
> return {
> @@ -52,17 +58,23 @@ check_sorting(s, t)
> check_sorting(s, t, 'abcde')
> check_sorting(s, t, 'sql_d')
> check_sorting(s, t, 'sql_v')
> -check_sorting(s, t, 'sql_defer_foreign_keys')
> +check_sorting(s, t, 'z')
> +check_sorting(s, t, 'sql_parser_debuf')
> +check_sorting(s, t, 'sql_parser_debuh')
> +
> +name = nil
> +err = nil
> +for _, tuple in t:pairs() do \
> + name = tuple.name \
> + err = check_sorting(s, t, name) \
> + if err then \
> + break \
> + end \
> +end
> +err and {err, name}
>
> t:drop()
>
> --- Check get() method of session_settings space.
> -s:get({'sql_defer_foreign_keys'})
> -s:get({'sql_recursive_triggers'})
> -s:get({'sql_reverse_unordered_selects'})
> -s:get({'sql_default_engine'})
> -s:get({'abcd'})
> -
> -- Check pairs() method of session_settings space.
> t = {}
> for key, value in s:pairs() do table.insert(t, {key, value}) end
> --
> 2.21.1 (Apple Git-122.3)
>
More information about the Tarantool-patches
mailing list