From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp39.i.mail.ru (smtp39.i.mail.ru [94.100.177.99]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dev.tarantool.org (Postfix) with ESMTPS id 311C946970E for ; Sun, 19 Jan 2020 23:18:17 +0300 (MSK) From: Chris Sosnin Date: Sun, 19 Jan 2020 23:18:15 +0300 Message-Id: <20200119201815.71286-1-k.sosnin@tarantool.org> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Subject: [Tarantool-patches] [PATCH v2] box: add binary search for _session_settings space List-Id: Tarantool development patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: v.shpilevoy@tarantool.org Cc: tarantool-patches@dev.tarantool.org 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)