Tarantool development patches archive
 help / color / mirror / Atom feed
From: Chris Sosnin <k.sosnin@tarantool.org>
To: v.shpilevoy@tarantool.org, tarantool-patches@dev.tarantool.org
Subject: [Tarantool-patches] [PATCH v4 2/3] box: add binary search for _session_settings space
Date: Tue, 28 Jan 2020 15:50:42 +0300	[thread overview]
Message-ID: <00c4f2f6dde45fe05cafd32ec60eeaaa5cbce6cc.1580215539.git.k.sosnin@tarantool.org> (raw)
In-Reply-To: <cover.1580215539.git.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)

  parent reply	other threads:[~2020-01-28 12:50 UTC|newest]

Thread overview: 14+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-01-28 12:50 [Tarantool-patches] [PATCH v4 0/3] box: session settings fixes Chris Sosnin
2020-01-28 12:50 ` [Tarantool-patches] [PATCH v4 1/3] box: replace session_settings modules with a single array Chris Sosnin
2020-02-03 22:17   ` Vladislav Shpilevoy
2020-02-04 19:29     ` [Tarantool-patches] [PATCH 1/4] " Chris Sosnin
2020-02-06 22:14       ` Vladislav Shpilevoy
2020-01-28 12:50 ` Chris Sosnin [this message]
2020-02-03 22:17   ` [Tarantool-patches] [PATCH v4 2/3] box: add binary search for _session_settings space Vladislav Shpilevoy
2020-02-04 19:30     ` [Tarantool-patches] [PATCH 2/4] " Chris Sosnin
2020-02-06 22:15       ` Vladislav Shpilevoy
2020-01-28 12:50 ` [Tarantool-patches] [PATCH v4 3/3] box: provide a user friendly frontend for accessing session settings Chris Sosnin
2020-02-03 22:17   ` Vladislav Shpilevoy
2020-02-04 19:31     ` [Tarantool-patches] [PATCH 3/4] " Chris Sosnin
2020-02-06 22:15       ` Vladislav Shpilevoy
2020-02-03 22:17 ` [Tarantool-patches] [PATCH v4 0/3] box: session settings fixes Vladislav Shpilevoy

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=00c4f2f6dde45fe05cafd32ec60eeaaa5cbce6cc.1580215539.git.k.sosnin@tarantool.org \
    --to=k.sosnin@tarantool.org \
    --cc=tarantool-patches@dev.tarantool.org \
    --cc=v.shpilevoy@tarantool.org \
    --subject='Re: [Tarantool-patches] [PATCH v4 2/3] box: add binary search for _session_settings space' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox