Tarantool development patches archive
 help / color / mirror / Atom feed
From: Vladislav Shpilevoy <v.shpilevoy@tarantool.org>
To: tarantool-patches@freelists.org
Cc: vdavydov.dev@gmail.com
Subject: [PATCH 1/1] salad: fix mhash 'random' method
Date: Fri,  1 Mar 2019 00:25:28 +0300	[thread overview]
Message-ID: <5f5c5a5994698deef183a31f46e8efaa9f4cd399.1551389056.git.v.shpilevoy@tarantool.org> (raw)

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 <stdint.h>
 #include <stdio.h>
+#include <stdbool.h>
 #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)

             reply	other threads:[~2019-02-28 21:25 UTC|newest]

Thread overview: 3+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-02-28 21:25 Vladislav Shpilevoy [this message]
2019-02-28 22:04 ` [tarantool-patches] " Konstantin Osipov
2019-03-01  9:40   ` [tarantool-patches] " 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=5f5c5a5994698deef183a31f46e8efaa9f4cd399.1551389056.git.v.shpilevoy@tarantool.org \
    --to=v.shpilevoy@tarantool.org \
    --cc=tarantool-patches@freelists.org \
    --cc=vdavydov.dev@gmail.com \
    --subject='Re: [PATCH 1/1] salad: fix mhash '\''random'\'' method' \
    /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