1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
// Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
#include <vespa/vdslib/bucketdistribution.h>
#include <gtest/gtest.h>
using namespace vdslib;
void
assertDistribution(uint32_t numColumns, uint32_t numBucketBits, const uint32_t expected[])
{
BucketDistribution bd(numColumns, numBucketBits);
EXPECT_EQ(numColumns, bd.getNumColumns());
EXPECT_EQ((uint32_t)(1 << numBucketBits), bd.getNumBuckets());
for (uint32_t i = 0; i < bd.getNumBuckets(); ++i) {
EXPECT_EQ(expected[i], bd.getColumn(document::BucketId(16, i)));
}
}
TEST(BucketDistributionTest, testDistribution)
{
const uint32_t expected4[] = {
10, 11, 9, 6, 4, 8, 14, 1, 13, 2, 12, 3, 5, 7, 15, 0 };
assertDistribution(16, 4, expected4);
const uint32_t expected5[] = {
11, 12, 11, 13, 8, 13, 8, 9, 4, 5, 6, 12, 10, 15, 1, 1, 7, 9, 14, 2, 2, 14, 3, 3, 4, 5, 6, 7, 10, 15, 0, 0 };
assertDistribution(16, 5, expected5);
const uint32_t expected6[] = {
13, 13, 13, 13, 9, 11, 8, 9, 11, 14, 9, 11, 14, 14, 8, 10, 11, 14, 4, 5, 5, 6, 6, 7, 8, 10, 12, 15, 1, 1, 1, 1,
6, 7, 8, 10, 12, 15, 2, 2, 2, 2, 12, 15, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6, 7, 7, 9, 10, 12, 15, 0, 0, 0, 0 };
assertDistribution(16, 6, expected6);
const uint32_t expected7[] = {
14, 14, 14, 13, 11, 14, 14, 10, 13, 14, 10, 12, 8, 8, 9, 10, 9, 10, 11, 12, 13, 15, 11, 12, 13, 13, 15, 8, 8, 9, 10, 11,
11, 12, 13, 15, 4, 4, 5, 5, 5, 5, 15, 6, 6, 7, 7, 7, 8, 9, 9, 10, 11, 12, 14, 15, 1, 1, 1, 1, 1, 1, 1, 1,
6, 6, 6, 7, 7, 8, 8, 9, 10, 11, 12, 13, 15, 2, 2, 2, 2, 2, 2, 2, 2, 12, 13, 15, 3, 3, 3, 3, 3, 3, 3, 3,
4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 9, 9, 10, 11, 12, 14, 15, 0, 0, 0, 0, 0, 0, 0, 0 };
assertDistribution(16, 7, expected7);
const uint32_t expected8[] = {
15, 14, 15, 15, 12, 14, 15, 12, 12, 11, 12, 13, 14, 13, 13, 13, 14, 15, 15, 9, 14, 9, 15, 10, 11, 11, 12, 8, 8, 8, 8, 9,
9, 10, 10, 10, 11, 11, 12, 13, 13, 14, 10, 11, 11, 12, 13, 13, 14, 13, 13, 14, 15, 7, 8, 8, 8, 9, 9, 9, 10, 10, 10, 11,
10, 10, 11, 11, 12, 13, 13, 14, 15, 4, 4, 4, 4, 15, 5, 5, 5, 5, 5, 5, 5, 15, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7,
8, 8, 8, 9, 9, 9, 10, 10, 11, 11, 12, 12, 13, 14, 14, 15, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 10, 10, 11, 11, 12, 12, 13, 14, 14, 15, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 12, 12, 13, 14, 14, 15, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7,
8, 8, 8, 9, 9, 9, 10, 10, 11, 11, 12, 12, 13, 14, 15, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
assertDistribution(16, 8, expected8);
const uint32_t expected9[] = {
15, 15, 15, 15, 14, 14, 15, 13, 13, 13, 13, 13, 14, 14, 15, 12, 14, 15, 15, 11, 11, 12, 13, 13, 13, 14, 14, 15, 15, 10, 12, 12,
12, 13, 13, 13, 14, 14, 15, 15, 9, 9, 9, 10, 10, 11, 11, 11, 12, 12, 12, 12, 13, 13, 14, 15, 15, 8, 8, 8, 8, 9, 9, 9,
9, 9, 9, 10, 9, 10, 10, 10, 10, 11, 11, 11, 11, 12, 12, 12, 12, 13, 13, 14, 14, 14, 10, 10, 10, 11, 11, 11, 12, 12, 12, 12,
13, 13, 14, 14, 14, 15, 15, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 11,
10, 10, 10, 11, 11, 11, 11, 12, 12, 12, 13, 13, 13, 14, 14, 14, 15, 15, 4, 4, 4, 4, 4, 4, 4, 15, 15, 5, 5, 5, 5, 5,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 14, 14, 14, 15, 15, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7,
8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 12, 12, 12, 13, 13, 13, 14, 14, 15, 15, 15,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9,
9, 9, 10, 10, 10, 10, 11, 11, 11, 11, 12, 12, 12, 13, 13, 13, 14, 14, 14, 15, 15, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 12, 12, 12, 13, 13, 13, 14, 14, 14, 15, 15,
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5,
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 12, 12, 12, 13, 13, 13, 14, 14, 15, 15, 15,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
assertDistribution(16, 9, expected9);
}
TEST(BucketDistributionTest, testNumBucketBits)
{
BucketDistribution bd(1, 4);
for (uint32_t i = 0; i <= 0xf; ++i) {
EXPECT_EQ(0u, bd.getColumn(document::BucketId(32, (rand() << 4) & i)));
}
bd.reset();
bd.setNumColumns(1);
bd.setNumBucketBits(8);
for (uint32_t i = 0; i <= 0xff; ++i) {
EXPECT_EQ(0u, bd.getColumn(document::BucketId(32, (rand() << 8) & i)));
}
bd.reset();
bd.setNumColumns(1);
bd.setNumBucketBits(16);
for (uint32_t i = 0; i <= 0xffff; ++i) {
EXPECT_EQ(0u, bd.getColumn(document::BucketId(32, (rand() << 16) & i)));
}
}
|
