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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
#include "util/sorted_uniform.hh"
#include "util/key_value_packing.hh"
#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int.hpp>
#include <boost/random/variate_generator.hpp>
#include <boost/scoped_array.hpp>
#include <boost/unordered_map.hpp>
#define BOOST_TEST_MODULE SortedUniformTest
#include <boost/test/unit_test.hpp>
#include <algorithm>
#include <limits>
#include <vector>
namespace util {
namespace {
template <class Map, class Key, class Value> void Check(const Map &map, const boost::unordered_map<Key, Value> &reference, const Key key) {
typename boost::unordered_map<Key, Value>::const_iterator ref = reference.find(key);
typename Map::ConstIterator i = typename Map::ConstIterator();
if (ref == reference.end()) {
BOOST_CHECK(!map.Find(key, i));
} else {
// g++ can't tell that require will crash and burn.
BOOST_REQUIRE(map.Find(key, i));
BOOST_CHECK_EQUAL(ref->second, i->GetValue());
}
}
typedef SortedUniformMap<AlignedPacking<uint64_t, uint32_t> > TestMap;
BOOST_AUTO_TEST_CASE(empty) {
char buf[TestMap::Size(0)];
TestMap map(buf, TestMap::Size(0));
map.FinishedInserting();
TestMap::ConstIterator i;
BOOST_CHECK(!map.Find(42, i));
}
BOOST_AUTO_TEST_CASE(one) {
char buf[TestMap::Size(1)];
TestMap map(buf, sizeof(buf));
Entry<uint64_t, uint32_t> e;
e.Set(42,2);
map.Insert(e);
map.FinishedInserting();
TestMap::ConstIterator i = TestMap::ConstIterator();
BOOST_REQUIRE(map.Find(42, i));
BOOST_CHECK(i == map.begin());
BOOST_CHECK(!map.Find(43, i));
BOOST_CHECK(!map.Find(41, i));
}
template <class Key> void RandomTest(Key upper, size_t entries, size_t queries) {
typedef unsigned char Value;
typedef SortedUniformMap<AlignedPacking<Key, unsigned char> > Map;
boost::scoped_array<char> buffer(new char[Map::Size(entries)]);
Map map(buffer.get(), entries);
boost::mt19937 rng;
boost::uniform_int<Key> range_key(0, upper);
boost::uniform_int<Value> range_value(0, 255);
boost::variate_generator<boost::mt19937&, boost::uniform_int<Key> > gen_key(rng, range_key);
boost::variate_generator<boost::mt19937&, boost::uniform_int<unsigned char> > gen_value(rng, range_value);
boost::unordered_map<Key, unsigned char> reference;
Entry<Key, unsigned char> ent;
for (size_t i = 0; i < entries; ++i) {
Key key = gen_key();
unsigned char value = gen_value();
if (reference.insert(std::make_pair(key, value)).second) {
ent.Set(key, value);
map.Insert(Entry<Key, unsigned char>(ent));
}
}
map.FinishedInserting();
// Random queries.
for (size_t i = 0; i < queries; ++i) {
const Key key = gen_key();
Check<Map, Key, unsigned char>(map, reference, key);
}
typename boost::unordered_map<Key, unsigned char>::const_iterator it = reference.begin();
for (size_t i = 0; (i < queries) && (it != reference.end()); ++i, ++it) {
Check<Map, Key, unsigned char>(map, reference, it->second);
}
}
BOOST_AUTO_TEST_CASE(basic) {
RandomTest<uint8_t>(11, 10, 200);
}
BOOST_AUTO_TEST_CASE(tiny_dense_random) {
RandomTest<uint8_t>(11, 50, 200);
}
BOOST_AUTO_TEST_CASE(small_dense_random) {
RandomTest<uint8_t>(100, 100, 200);
}
BOOST_AUTO_TEST_CASE(small_sparse_random) {
RandomTest<uint8_t>(200, 15, 200);
}
BOOST_AUTO_TEST_CASE(medium_sparse_random) {
RandomTest<uint16_t>(32000, 1000, 2000);
}
BOOST_AUTO_TEST_CASE(sparse_random) {
RandomTest<uint64_t>(std::numeric_limits<uint64_t>::max(), 100000, 2000);
}
} // namespace
} // namespace util
|
