[Tarantool-patches] [PATCH v2] box: add binary search for _session_settings space

[Chris Sosnin]

Vlad, thank you for your suggestions!
Instead of using module_id as a flag, I added an explicit 'is_set' variable.
It is more convenient to use if you take into consideration adding more
modules. The rest is according to your advice: we set an interator with
binary search (finding lower/upper bound to be precise) and then do linear
lookup.

See the whole patch below:

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
---
branch: https://github.com/tarantool/tarantool/tree/ksosnin/gh-4712-search-settings
issue: https://github.com/tarantool/tarantool/issues/4712

 src/box/session_settings.c | 92 ++++++++++++++++++++++++++++++++++++--
 1 file changed, 88 insertions(+), 4 deletions(-)

diff --git a/src/box/session_settings.c b/src/box/session_settings.c
index a969d3d10..441dd29ff 100644
--- a/src/box/session_settings.c
+++ b/src/box/session_settings.c
@@ -74,6 +74,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 the existing setting */
+	bool is_set;
 };
 
 static void
@@ -85,6 +87,69 @@ session_settings_iterator_free(struct iterator *ptr)
 	free(it);
 }
 
+static int
+session_settings_set_forward(const struct session_setting_module *module,
+			     int *sid, const char *key, bool is_eq,
+			     bool is_including)
+{
+	int count = module->setting_count;
+	int low = 0, high = count;
+	if (key == NULL)
+		return 0;
+	const char **name = module->settings;
+	while (low < high) {
+		int index = low + (high - low) / 2;
+		int cmp = strcmp(name[index], key);
+		if ((cmp < 0 && is_including) ||
+		    (cmp <= 0 && !is_including))
+			low = index + 1;
+		else
+			high = index;
+	}
+	if (low < count) {
+		int cmp = strcmp(name[low], key);
+		if ((cmp == 0 && is_including) ||
+		    (cmp > 0 && !is_eq)) {
+			*sid = low;
+			return 0;
+		}
+	}
+	*sid = count;
+	return -1;
+}
+
+static int
+session_settings_set_reverse(const struct session_setting_module *module,
+			     int *sid, const char *key, bool is_eq,
+			     bool is_including)
+{
+	int count = module->setting_count;
+	int low = -1, high = count - 1;
+	if (key == NULL)
+		return 0;
+	const char **name = module->settings;
+	while (low < high) {
+		int index = high - (high - low) / 2;
+		int cmp = strcmp(name[index], key);
+		if ((cmp > 0 && is_including) ||
+		    (cmp >= 0 && !is_including))
+			high = index - 1;
+		else
+			low = index;
+	}
+	if (high >= 0) {
+		int cmp = strcmp(name[high], key);
+		if ((cmp == 0 && is_including) ||
+		    (cmp < 0 && !is_eq)) {
+			*sid = high;
+			return 0;
+		}
+	}
+	*sid = count;
+	return -1;
+}
+
+
 static int
 session_settings_next_in_module(const struct session_setting_module *module,
 				int *sid, const char *key, bool is_eq,
@@ -148,6 +213,15 @@ session_settings_iterator_next(struct iterator *iterator, struct tuple **result)
 	bool is_found = false;
 	for (; mid < session_setting_type_MAX; ++mid, sid = 0) {
 		module = &session_setting_modules[mid];
+		if (!it->is_set) {
+			if (session_settings_set_forward(module, &sid, key,
+							 is_eq,
+							 is_including) == 0) {
+				it->is_set = true;
+				is_found = true;
+				break;
+			}
+		}
 		if (session_settings_next_in_module(module, &sid, key, is_eq,
 						    is_including) == 0) {
 			is_found = true;
@@ -178,6 +252,15 @@ session_settings_iterator_prev(struct iterator *iterator, struct tuple **result)
 	bool is_found = false;
 	for (; mid >= 0; --mid, sid = INT_MAX) {
 		module = &session_setting_modules[mid];
+		if (!it->is_set) {
+			if (session_settings_set_reverse(module, &sid, key,
+							 is_eq,
+							 is_including) == 0) {
+				it->is_set = true;
+				is_found = true;
+				break;
+			}
+		}
 		if (session_settings_prev_in_module(module, &sid, key, is_eq,
 						    is_including) == 0) {
 			is_found = true;
@@ -236,6 +319,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;
@@ -266,8 +350,8 @@ session_settings_index_get(struct index *base, const char *key,
 	struct session_setting_module *end = module + session_setting_type_MAX;
 	int sid = 0;
 	for (; module < end; ++module, sid = 0) {
-		if (session_settings_next_in_module(module, &sid, key, true,
-						    true) == 0)
+		if (session_settings_set_forward(module, &sid, key, true,
+						 true) == 0)
 			goto found;
 	}
 	*result = NULL;
@@ -373,8 +457,8 @@ session_settings_space_execute_update(struct space *space, struct txn *txn,
 	struct session_setting_module *module = &session_setting_modules[0];
 	struct session_setting_module *end = module + session_setting_type_MAX;
 	for (; module < end; ++module, sid = 0) {
-		if (session_settings_next_in_module(module, &sid, key, true,
-						    true) == 0)
+		if (session_settings_set_forward(module, &sid, key, true,
+						 true) == 0)
 			goto found;
 	}
 	*result = NULL;
-- 
2.21.0 (Apple Git-122.2)