From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtpng3.m.smailru.net (smtpng3.m.smailru.net [94.100.177.149]) (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 A0F7446970E for ; Fri, 10 Jan 2020 10:46:10 +0300 (MSK) Received: by smtpng3.m.smailru.net with esmtpa (envelope-from ) id 1ipozi-0001WV-8K for tarantool-patches@dev.tarantool.org; Fri, 10 Jan 2020 10:46:10 +0300 From: Chris Sosnin Date: Fri, 10 Jan 2020 10:46:09 +0300 Message-Id: <20200110074609.68016-1-k.sosnin@tarantool.org> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Subject: [Tarantool-patches] [PATCH] box: add binary search for _session settings space List-Id: Tarantool development patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: tarantool-patches@dev.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 --- 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 | 10 ++++++---- src/lib/core/util.c | 22 ++++++++++++++++++++++ src/trivia/util.h | 3 +++ 3 files changed, 31 insertions(+), 4 deletions(-) diff --git a/src/box/session_settings.c b/src/box/session_settings.c index a969d3d10..ec87641be 100644 --- a/src/box/session_settings.c +++ b/src/box/session_settings.c @@ -265,9 +265,10 @@ session_settings_index_get(struct index *base, const char *key, struct session_setting_module *module = &session_setting_modules[0]; struct session_setting_module *end = module + session_setting_type_MAX; int sid = 0; + int count = module->setting_count; for (; module < end; ++module, sid = 0) { - if (session_settings_next_in_module(module, &sid, key, true, - true) == 0) + if ((sid = str_bin_search(module->settings, key, + count)) != count) goto found; } *result = NULL; @@ -372,9 +373,10 @@ session_settings_space_execute_update(struct space *space, struct txn *txn, key = tt_cstr(key, key_len); struct session_setting_module *module = &session_setting_modules[0]; struct session_setting_module *end = module + session_setting_type_MAX; + int count = module->setting_count; for (; module < end; ++module, sid = 0) { - if (session_settings_next_in_module(module, &sid, key, true, - true) == 0) + if ((sid = str_bin_search(module->settings, key, + count)) != count) goto found; } *result = NULL; diff --git a/src/lib/core/util.c b/src/lib/core/util.c index ffa1d2b51..6553d6626 100644 --- a/src/lib/core/util.c +++ b/src/lib/core/util.c @@ -84,6 +84,28 @@ strnindex(const char **haystack, const char *needle, uint32_t len, uint32_t hmax return hmax; } +/** + * Same as strindex(), but assuming the array is sorted and it's + * size is known. + */ +uint32_t +str_bin_search(const char **haystack, const char *needle, uint32_t hmax) { + int cmp; + uint32_t index, start = 0; + uint32_t end = hmax; + while (start < end) { + index = (start + end) / 2; + cmp = strcmp(haystack[index], needle); + if (cmp < 0) + start = index + 1; + else + end = index; + } + if (start < hmax && strcmp(haystack[start], needle) == 0) + return start; + return hmax; +} + void close_all_xcpt(int fdc, ...) { diff --git a/src/trivia/util.h b/src/trivia/util.h index 8a3d22b38..5c1e3bd5d 100644 --- a/src/trivia/util.h +++ b/src/trivia/util.h @@ -98,6 +98,9 @@ strindex(const char **haystack, const char *needle, uint32_t hmax); uint32_t strnindex(const char **haystack, const char *needle, uint32_t len, uint32_t hmax); +uint32_t +str_bin_search(const char **haystack, const char *needle, uint32_t hmax); + #define nelem(x) (sizeof((x))/sizeof((x)[0])) #define field_sizeof(compound_type, field) sizeof(((compound_type *)NULL)->field) #ifndef lengthof -- 2.21.0 (Apple Git-122.2)