[Tarantool-patches] [PATCH v3 2/2] box: add binary search for _session_settings space
Chris Sosnin
k.sosnin at tarantool.org
Sun Jan 26 15:01:42 MSK 2020
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)
More information about the Tarantool-patches
mailing list