[Tarantool-patches] [PATCH 2/4] box: add binary search for _session_settings space
Chris Sosnin
k.sosnin at tarantool.org
Mon Feb 17 15:12:10 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 93d1c8e22..874fc304a 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