[Tarantool-patches] [PATCH v4 2/3] box: add binary search for _session_settings space

[Chris Sosnin <k.sosnin@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)