From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: From: Vladislav Shpilevoy Subject: [PATCH 1/1] salad: fix mhash 'random' method Date: Fri, 1 Mar 2019 00:25:28 +0300 Message-Id: <5f5c5a5994698deef183a31f46e8efaa9f4cd399.1551389056.git.v.shpilevoy@tarantool.org> To: tarantool-patches@freelists.org Cc: vdavydov.dev@gmail.com List-ID: Mhash 'random' method is supposed to return a valid node id given an arbitrary integer, likely generated randomly. But on some values it was returning 'end' marker despite emptiness of the container. This was because of confusion in usage of mh_size() and mh_end(). Mh_size() means real number of objects, stored in the cache, while mh_end() means hash capacity, or 'number of buckets' as it is named. Generally capacity is bigger than size, and sometimes it led to a situation like this: size = 1 capacity = 4 rnd = 3 [0] [1] [2] [3] - - x - When code iterates only 'size' times, looking for an element starting from 'rnd' position, it will not find anything. It should iterate 'capacity' times instead. --- Branch: https://github.com/tarantool/tarantool/tree/gerold103/mhash-random-fix src/lib/salad/mhash.h | 11 +++--- test/unit/CMakeLists.txt | 2 ++ test/unit/mhash.c | 64 +++++++++++++++++++++++++++++++++- test/unit/mhash.result | 14 ++++++++ test/unit/mhash_bytemap.result | 14 ++++++++ 5 files changed, 97 insertions(+), 8 deletions(-) diff --git a/src/lib/salad/mhash.h b/src/lib/salad/mhash.h index a9b0e4d90..b555cad4c 100644 --- a/src/lib/salad/mhash.h +++ b/src/lib/salad/mhash.h @@ -238,13 +238,10 @@ _mh(get)(struct _mh(t) *h, const mh_node_t *node, static inline mh_int_t _mh(random)(struct _mh(t) *h, mh_int_t rnd) { - for (mh_int_t i = 0; i < mh_size(h); i++, rnd++) { - rnd %= h->n_buckets; - if (mh_exist(h, rnd)) - return rnd; - } - - return h->n_buckets; + mh_int_t res = mh_next(h, rnd % mh_end(h)); + if (res != mh_end(h)) + return res; + return mh_first(h); } static inline mh_int_t diff --git a/test/unit/CMakeLists.txt b/test/unit/CMakeLists.txt index 04bc659e7..c13528400 100644 --- a/test/unit/CMakeLists.txt +++ b/test/unit/CMakeLists.txt @@ -25,7 +25,9 @@ add_executable(uri.test uri.c unit.c) target_link_libraries(uri.test uri unit) add_executable(queue.test queue.c) add_executable(mhash.test mhash.c) +target_link_libraries(mhash.test unit) add_executable(mhash_bytemap.test mhash_bytemap.c) +target_link_libraries(mhash_bytemap.test unit) add_executable(rope_basic.test rope_basic.c) target_link_libraries(rope_basic.test salad) add_executable(rope_avl.test rope_avl.c) diff --git a/test/unit/mhash.c b/test/unit/mhash.c index 72f9b57fa..5f37ae8d4 100644 --- a/test/unit/mhash.c +++ b/test/unit/mhash.c @@ -1,5 +1,6 @@ #include #include +#include #include "unit.h" #ifndef bytemap @@ -38,6 +39,7 @@ struct mh_i32_collision_node_t { static void mhash_int32_id_test() { header(); + plan(0); int k; struct mh_i32_t *h; #define init() ({ mh_i32_new(); }) @@ -59,12 +61,14 @@ static void mhash_int32_id_test() #include "mhash_body.c" footer(); + check_plan(); } static void mhash_int32_collision_test() { header(); + plan(0); int k; struct mh_i32_collision_t *h; #define init() ({ mh_i32_collision_new(); }) @@ -86,11 +90,69 @@ static void mhash_int32_collision_test() #include "mhash_body.c" footer(); + check_plan(); +} + +static void +mhash_random_test(void) +{ + header(); + plan(3); + struct mh_i32_t *h = mh_i32_new(); + const int end = 100; + int i, size; + bool is_found[end], all_is_found[end]; + memset(all_is_found, 1, sizeof(all_is_found)); + + for (i = 0; i < end; ++i) { + if (mh_i32_random(h, i) != mh_end(h)) + break; + } + is(i, end, "empty random is always 'end'"); + + for (i = 0; i < end; ++i) { + struct mh_i32_node_t node = {i, i}; + mh_int_t rc = mh_i32_put(h, &node, NULL, NULL); + int j; + for (j = 0; j < end; ++j) { + if (mh_i32_random(h, j) != rc) + break; + } + mh_i32_del(h, rc, NULL); + if (j != end) + break; + } + is(i, end, "one element is always found"); + + for (i = 0, size = sizeof(bool); i < end; ++i, size += sizeof(bool)) { + struct mh_i32_node_t *n, node = {i, i}; + mh_i32_put(h, &node, NULL, NULL); + memset(is_found, 0, sizeof(is_found)); + for (int j = 0; j < end; ++j) { + mh_int_t rc = mh_i32_random(h, j); + n = mh_i32_node(h, rc); + is_found[n->key] = true; + } + if (memcmp(is_found, all_is_found, size) != 0) + break; + } + is(i, end, "incremental random from mutable hash"); + + mh_i32_delete(h); + check_plan(); + footer(); } int main(void) { + header(); + plan(3); + mhash_int32_id_test(); mhash_int32_collision_test(); - return 0; + mhash_random_test(); + + int rc = check_plan(); + footer(); + return rc; } diff --git a/test/unit/mhash.result b/test/unit/mhash.result index ff958136a..fc757fa35 100644 --- a/test/unit/mhash.result +++ b/test/unit/mhash.result @@ -1,4 +1,18 @@ + *** main *** +1..3 *** mhash_int32_id_test *** + 1..0 *** mhash_int32_id_test: done *** +ok 1 - subtests *** mhash_int32_collision_test *** + 1..0 *** mhash_int32_collision_test: done *** +ok 2 - subtests + *** mhash_random_test *** + 1..3 + ok 1 - empty random is always 'end' + ok 2 - one element is always found + ok 3 - incremental random from mutable hash +ok 3 - subtests + *** mhash_random_test: done *** + *** main: done *** diff --git a/test/unit/mhash_bytemap.result b/test/unit/mhash_bytemap.result index ff958136a..fc757fa35 100644 --- a/test/unit/mhash_bytemap.result +++ b/test/unit/mhash_bytemap.result @@ -1,4 +1,18 @@ + *** main *** +1..3 *** mhash_int32_id_test *** + 1..0 *** mhash_int32_id_test: done *** +ok 1 - subtests *** mhash_int32_collision_test *** + 1..0 *** mhash_int32_collision_test: done *** +ok 2 - subtests + *** mhash_random_test *** + 1..3 + ok 1 - empty random is always 'end' + ok 2 - one element is always found + ok 3 - incremental random from mutable hash +ok 3 - subtests + *** mhash_random_test: done *** + *** main: done *** -- 2.17.2 (Apple Git-113)