hmap_random_node: Improve distribution

Improve random distribution for an hmap with a small number of nodes
with the expense of the increased cpu cost.
It would be a fair trade-off because the situation is rather common
for bond, which is currently the only consumer of this API in tree.

Consider 2 items, 4 buckets, no collision.

    bucket 0   item 0
    bucket 1
    bucket 2
    bucket 3   item 1

The old algorithm picks item 0 if rand % 4 == 0.  (25%)
Otherwise it picks item 1.  (75%)

This change makes them 50%.

Acked-by: Ben Pfaff <blp@nicira.com>
Signed-off-by: YAMAMOTO Takashi <yamamoto@valinux.co.jp>

diff --git a/lib/hmap.c b/lib/hmap.c
index ec1de67..542d8b5 100644 (file)
--- a/lib/hmap.c
+++ b/lib/hmap.c
@@ -214,8 +214,8 @@ hmap_random_node(const struct hmap *hmap)
     size_t n, i;
 
     /* Choose a random non-empty bucket. */
-    for (i = random_uint32(); ; i++) {
-        bucket = hmap->buckets[i & hmap->mask];
+    for (;;) {
+        bucket = hmap->buckets[random_uint32() & hmap->mask];
         if (bucket) {
             break;
         }