hmap_random_node: Improve distribution
authorYAMAMOTO Takashi <yamamoto@valinux.co.jp>
Tue, 22 Apr 2014 04:34:36 +0000 (13:34 +0900)
committerYAMAMOTO Takashi <yamamoto@valinux.co.jp>
Thu, 24 Apr 2014 05:48:54 +0000 (14:48 +0900)
commite58f91a15a38ad2d26d77b77b2f1c84f6c6b06dc
tree8e76f295c36e3491e8db6dcfd48b70768a46768d
parent7d1700980b5dcf98003fdceb821d7967fad99786
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>
lib/hmap.c