From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtpng2.m.smailru.net (smtpng2.m.smailru.net [94.100.179.3]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dev.tarantool.org (Postfix) with ESMTPS id EE7174696C4 for ; Tue, 28 Jan 2020 15:50:45 +0300 (MSK) From: Chris Sosnin Date: Tue, 28 Jan 2020 15:50:42 +0300 Message-Id: <00c4f2f6dde45fe05cafd32ec60eeaaa5cbce6cc.1580215539.git.k.sosnin@tarantool.org> In-Reply-To: References: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Subject: [Tarantool-patches] [PATCH v4 2/3] box: add binary search for _session_settings space List-Id: Tarantool development patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: v.shpilevoy@tarantool.org, tarantool-patches@dev.tarantool.org 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 --- src/box/session_settings.c | 97 +++++++++++++++++-- ...1-access-settings-from-any-frontend.result | 37 ++++--- ...access-settings-from-any-frontend.test.lua | 28 ++++-- 3 files changed, 133 insertions(+), 29 deletions(-) diff --git a/src/box/session_settings.c b/src/box/session_settings.c index cdc2d1cf9..051ce0603 100644 --- a/src/box/session_settings.c +++ b/src/box/session_settings.c @@ -69,6 +69,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 @@ -80,6 +82,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_settings[index].name; + 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_settings[index].name; + 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) { @@ -130,12 +198,18 @@ session_settings_iterator_next(struct iterator *iterator, struct tuple **result) { struct session_settings_iterator *it = (struct session_settings_iterator *)iterator; - int sid = it->setting_id; + int rc, 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; + if (!it->is_set) { + it->is_set = true; + rc = session_settings_set_forward(&sid, key, is_eq, + is_including); + } else { + rc = session_settings_next(&sid, key, is_eq, is_including); + } + is_found = rc == 0; it->setting_id = sid + 1; if (!is_found) { *result = NULL; @@ -152,12 +226,18 @@ session_settings_iterator_prev(struct iterator *iterator, struct tuple **result) { struct session_settings_iterator *it = (struct session_settings_iterator *)iterator; - int sid = it->setting_id; + int rc, 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; + if (!it->is_set) { + it->is_set = true; + rc = session_settings_set_reverse(&sid, key, is_eq, + is_including); + } else { + rc = session_settings_prev(&sid, key, is_eq, is_including); + } + is_found = rc == 0; it->setting_id = sid - 1; if (!is_found) { *result = NULL; @@ -209,6 +289,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; @@ -232,7 +313,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) goto found; *result = NULL; return 0; @@ -334,7 +415,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) goto found; *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..f072bafae 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..40a58ad04 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)