diff options
Diffstat (limited to 'xdelta3/cpp-btree/btree_test.cc')
-rw-r--r-- | xdelta3/cpp-btree/btree_test.cc | 270 |
1 files changed, 270 insertions, 0 deletions
diff --git a/xdelta3/cpp-btree/btree_test.cc b/xdelta3/cpp-btree/btree_test.cc new file mode 100644 index 0000000..6b1837d --- /dev/null +++ b/xdelta3/cpp-btree/btree_test.cc | |||
@@ -0,0 +1,270 @@ | |||
1 | // Copyright 2013 Google Inc. All Rights Reserved. | ||
2 | // | ||
3 | // Licensed under the Apache License, Version 2.0 (the "License"); | ||
4 | // you may not use this file except in compliance with the License. | ||
5 | // You may obtain a copy of the License at | ||
6 | // | ||
7 | // http://www.apache.org/licenses/LICENSE-2.0 | ||
8 | // | ||
9 | // Unless required by applicable law or agreed to in writing, software | ||
10 | // distributed under the License is distributed on an "AS IS" BASIS, | ||
11 | // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | ||
12 | // See the License for the specific language governing permissions and | ||
13 | // limitations under the License. | ||
14 | |||
15 | #include "gtest/gtest.h" | ||
16 | #include "btree_map.h" | ||
17 | #include "btree_set.h" | ||
18 | #include "btree_test.h" | ||
19 | |||
20 | namespace btree { | ||
21 | namespace { | ||
22 | |||
23 | template <typename K, int N> | ||
24 | void SetTest() { | ||
25 | typedef TestAllocator<K> TestAlloc; | ||
26 | ASSERT_EQ(sizeof(btree_set<K>), sizeof(void*)); | ||
27 | BtreeTest<btree_set<K, std::less<K>, std::allocator<K>, N>, std::set<K> >(); | ||
28 | BtreeAllocatorTest<btree_set<K, std::less<K>, TestAlloc, N> >(); | ||
29 | } | ||
30 | |||
31 | template <typename K, int N> | ||
32 | void MapTest() { | ||
33 | typedef TestAllocator<K> TestAlloc; | ||
34 | ASSERT_EQ(sizeof(btree_map<K, K>), sizeof(void*)); | ||
35 | BtreeTest<btree_map<K, K, std::less<K>, std::allocator<K>, N>, std::map<K, K> >(); | ||
36 | BtreeAllocatorTest<btree_map<K, K, std::less<K>, TestAlloc, N> >(); | ||
37 | BtreeMapTest<btree_map<K, K, std::less<K>, std::allocator<K>, N> >(); | ||
38 | } | ||
39 | |||
40 | TEST(Btree, set_int32_32) { SetTest<int32_t, 32>(); } | ||
41 | TEST(Btree, set_int32_64) { SetTest<int32_t, 64>(); } | ||
42 | TEST(Btree, set_int32_128) { SetTest<int32_t, 128>(); } | ||
43 | TEST(Btree, set_int32_256) { SetTest<int32_t, 256>(); } | ||
44 | TEST(Btree, set_int64_256) { SetTest<int64_t, 256>(); } | ||
45 | TEST(Btree, set_string_256) { SetTest<std::string, 256>(); } | ||
46 | TEST(Btree, set_pair_256) { SetTest<std::pair<int, int>, 256>(); } | ||
47 | TEST(Btree, map_int32_256) { MapTest<int32_t, 256>(); } | ||
48 | TEST(Btree, map_int64_256) { MapTest<int64_t, 256>(); } | ||
49 | TEST(Btree, map_string_256) { MapTest<std::string, 256>(); } | ||
50 | TEST(Btree, map_pair_256) { MapTest<std::pair<int, int>, 256>(); } | ||
51 | |||
52 | // Large-node tests | ||
53 | TEST(Btree, map_int32_1024) { MapTest<int32_t, 1024>(); } | ||
54 | TEST(Btree, map_int32_1032) { MapTest<int32_t, 1032>(); } | ||
55 | TEST(Btree, map_int32_1040) { MapTest<int32_t, 1040>(); } | ||
56 | TEST(Btree, map_int32_1048) { MapTest<int32_t, 1048>(); } | ||
57 | TEST(Btree, map_int32_1056) { MapTest<int32_t, 1056>(); } | ||
58 | |||
59 | TEST(Btree, map_int32_2048) { MapTest<int32_t, 2048>(); } | ||
60 | TEST(Btree, map_int32_4096) { MapTest<int32_t, 4096>(); } | ||
61 | TEST(Btree, set_int32_1024) { SetTest<int32_t, 1024>(); } | ||
62 | TEST(Btree, set_int32_2048) { SetTest<int32_t, 2048>(); } | ||
63 | TEST(Btree, set_int32_4096) { SetTest<int32_t, 4096>(); } | ||
64 | TEST(Btree, map_string_1024) { MapTest<std::string, 1024>(); } | ||
65 | TEST(Btree, map_string_2048) { MapTest<std::string, 2048>(); } | ||
66 | TEST(Btree, map_string_4096) { MapTest<std::string, 4096>(); } | ||
67 | TEST(Btree, set_string_1024) { SetTest<std::string, 1024>(); } | ||
68 | TEST(Btree, set_string_2048) { SetTest<std::string, 2048>(); } | ||
69 | TEST(Btree, set_string_4096) { SetTest<std::string, 4096>(); } | ||
70 | |||
71 | template <typename K, int N> | ||
72 | void MultiSetTest() { | ||
73 | typedef TestAllocator<K> TestAlloc; | ||
74 | ASSERT_EQ(sizeof(btree_multiset<K>), sizeof(void*)); | ||
75 | BtreeMultiTest<btree_multiset<K, std::less<K>, std::allocator<K>, N>, | ||
76 | std::multiset<K> >(); | ||
77 | BtreeAllocatorTest<btree_multiset<K, std::less<K>, TestAlloc, N> >(); | ||
78 | } | ||
79 | |||
80 | template <typename K, int N> | ||
81 | void MultiMapTest() { | ||
82 | typedef TestAllocator<K> TestAlloc; | ||
83 | ASSERT_EQ(sizeof(btree_multimap<K, K>), sizeof(void*)); | ||
84 | BtreeMultiTest<btree_multimap<K, K, std::less<K>, std::allocator<K>, N>, | ||
85 | std::multimap<K, K> >(); | ||
86 | BtreeMultiMapTest<btree_multimap<K, K, std::less<K>, std::allocator<K>, N> >(); | ||
87 | BtreeAllocatorTest<btree_multimap<K, K, std::less<K>, TestAlloc, N> >(); | ||
88 | } | ||
89 | |||
90 | TEST(Btree, multiset_int32_256) { MultiSetTest<int32_t, 256>(); } | ||
91 | TEST(Btree, multiset_int64_256) { MultiSetTest<int64_t, 256>(); } | ||
92 | TEST(Btree, multiset_string_256) { MultiSetTest<std::string, 256>(); } | ||
93 | TEST(Btree, multiset_pair_256) { MultiSetTest<std::pair<int, int>, 256>(); } | ||
94 | TEST(Btree, multimap_int32_256) { MultiMapTest<int32_t, 256>(); } | ||
95 | TEST(Btree, multimap_int64_256) { MultiMapTest<int64_t, 256>(); } | ||
96 | TEST(Btree, multimap_string_256) { MultiMapTest<std::string, 256>(); } | ||
97 | TEST(Btree, multimap_pair_256) { MultiMapTest<std::pair<int, int>, 256>(); } | ||
98 | |||
99 | // Large-node tests | ||
100 | TEST(Btree, multimap_int32_1024) { MultiMapTest<int32_t, 1024>(); } | ||
101 | TEST(Btree, multimap_int32_2048) { MultiMapTest<int32_t, 2048>(); } | ||
102 | TEST(Btree, multimap_int32_4096) { MultiMapTest<int32_t, 4096>(); } | ||
103 | TEST(Btree, multiset_int32_1024) { MultiSetTest<int32_t, 1024>(); } | ||
104 | TEST(Btree, multiset_int32_2048) { MultiSetTest<int32_t, 2048>(); } | ||
105 | TEST(Btree, multiset_int32_4096) { MultiSetTest<int32_t, 4096>(); } | ||
106 | TEST(Btree, multimap_string_1024) { MultiMapTest<std::string, 1024>(); } | ||
107 | TEST(Btree, multimap_string_2048) { MultiMapTest<std::string, 2048>(); } | ||
108 | TEST(Btree, multimap_string_4096) { MultiMapTest<std::string, 4096>(); } | ||
109 | TEST(Btree, multiset_string_1024) { MultiSetTest<std::string, 1024>(); } | ||
110 | TEST(Btree, multiset_string_2048) { MultiSetTest<std::string, 2048>(); } | ||
111 | TEST(Btree, multiset_string_4096) { MultiSetTest<std::string, 4096>(); } | ||
112 | |||
113 | // Verify that swapping btrees swaps the key comparision functors. | ||
114 | struct SubstringLess { | ||
115 | SubstringLess() : n(2) {} | ||
116 | SubstringLess(size_t length) | ||
117 | : n(length) { | ||
118 | } | ||
119 | bool operator()(const std::string &a, const std::string &b) const { | ||
120 | std::string as(a.data(), std::min(n, a.size())); | ||
121 | std::string bs(b.data(), std::min(n, b.size())); | ||
122 | return as < bs; | ||
123 | } | ||
124 | size_t n; | ||
125 | }; | ||
126 | |||
127 | TEST(Btree, SwapKeyCompare) { | ||
128 | typedef btree_set<std::string, SubstringLess> SubstringSet; | ||
129 | SubstringSet s1(SubstringLess(1), SubstringSet::allocator_type()); | ||
130 | SubstringSet s2(SubstringLess(2), SubstringSet::allocator_type()); | ||
131 | |||
132 | ASSERT_TRUE(s1.insert("a").second); | ||
133 | ASSERT_FALSE(s1.insert("aa").second); | ||
134 | |||
135 | ASSERT_TRUE(s2.insert("a").second); | ||
136 | ASSERT_TRUE(s2.insert("aa").second); | ||
137 | ASSERT_FALSE(s2.insert("aaa").second); | ||
138 | |||
139 | swap(s1, s2); | ||
140 | |||
141 | ASSERT_TRUE(s1.insert("b").second); | ||
142 | ASSERT_TRUE(s1.insert("bb").second); | ||
143 | ASSERT_FALSE(s1.insert("bbb").second); | ||
144 | |||
145 | ASSERT_TRUE(s2.insert("b").second); | ||
146 | ASSERT_FALSE(s2.insert("bb").second); | ||
147 | } | ||
148 | |||
149 | TEST(Btree, UpperBoundRegression) { | ||
150 | // Regress a bug where upper_bound would default-construct a new key_compare | ||
151 | // instead of copying the existing one. | ||
152 | typedef btree_set<std::string, SubstringLess> SubstringSet; | ||
153 | SubstringSet my_set(SubstringLess(3)); | ||
154 | my_set.insert("aab"); | ||
155 | my_set.insert("abb"); | ||
156 | // We call upper_bound("aaa"). If this correctly uses the length 3 | ||
157 | // comparator, aaa < aab < abb, so we should get aab as the result. | ||
158 | // If it instead uses the default-constructed length 2 comparator, | ||
159 | // aa == aa < ab, so we'll get abb as our result. | ||
160 | SubstringSet::iterator it = my_set.upper_bound("aaa"); | ||
161 | ASSERT_TRUE(it != my_set.end()); | ||
162 | EXPECT_EQ("aab", *it); | ||
163 | } | ||
164 | |||
165 | |||
166 | TEST(Btree, IteratorIncrementBy) { | ||
167 | // Test that increment_by returns the same position as increment. | ||
168 | const int kSetSize = 2341; | ||
169 | btree_set<int32_t> my_set; | ||
170 | for (int i = 0; i < kSetSize; ++i) { | ||
171 | my_set.insert(i); | ||
172 | } | ||
173 | |||
174 | { | ||
175 | // Simple increment vs. increment by. | ||
176 | btree_set<int32_t>::iterator a = my_set.begin(); | ||
177 | btree_set<int32_t>::iterator b = my_set.begin(); | ||
178 | a.increment(); | ||
179 | b.increment_by(1); | ||
180 | EXPECT_EQ(*a, *b); | ||
181 | } | ||
182 | |||
183 | btree_set<int32_t>::iterator a = my_set.begin(); | ||
184 | for (int i = 1; i < kSetSize; ++i) { | ||
185 | ++a; | ||
186 | // increment_by | ||
187 | btree_set<int32_t>::iterator b = my_set.begin(); | ||
188 | b.increment_by(i); | ||
189 | EXPECT_EQ(*a, *b) << ": i=" << i; | ||
190 | } | ||
191 | } | ||
192 | |||
193 | TEST(Btree, Comparison) { | ||
194 | const int kSetSize = 1201; | ||
195 | btree_set<int64_t> my_set; | ||
196 | for (int i = 0; i < kSetSize; ++i) { | ||
197 | my_set.insert(i); | ||
198 | } | ||
199 | btree_set<int64_t> my_set_copy(my_set); | ||
200 | EXPECT_TRUE(my_set_copy == my_set); | ||
201 | EXPECT_TRUE(my_set == my_set_copy); | ||
202 | EXPECT_FALSE(my_set_copy != my_set); | ||
203 | EXPECT_FALSE(my_set != my_set_copy); | ||
204 | |||
205 | my_set.insert(kSetSize); | ||
206 | EXPECT_FALSE(my_set_copy == my_set); | ||
207 | EXPECT_FALSE(my_set == my_set_copy); | ||
208 | EXPECT_TRUE(my_set_copy != my_set); | ||
209 | EXPECT_TRUE(my_set != my_set_copy); | ||
210 | |||
211 | my_set.erase(kSetSize - 1); | ||
212 | EXPECT_FALSE(my_set_copy == my_set); | ||
213 | EXPECT_FALSE(my_set == my_set_copy); | ||
214 | EXPECT_TRUE(my_set_copy != my_set); | ||
215 | EXPECT_TRUE(my_set != my_set_copy); | ||
216 | |||
217 | btree_map<std::string, int64_t> my_map; | ||
218 | for (int i = 0; i < kSetSize; ++i) { | ||
219 | my_map[std::string(i, 'a')] = i; | ||
220 | } | ||
221 | btree_map<std::string, int64_t> my_map_copy(my_map); | ||
222 | EXPECT_TRUE(my_map_copy == my_map); | ||
223 | EXPECT_TRUE(my_map == my_map_copy); | ||
224 | EXPECT_FALSE(my_map_copy != my_map); | ||
225 | EXPECT_FALSE(my_map != my_map_copy); | ||
226 | |||
227 | ++my_map_copy[std::string(7, 'a')]; | ||
228 | EXPECT_FALSE(my_map_copy == my_map); | ||
229 | EXPECT_FALSE(my_map == my_map_copy); | ||
230 | EXPECT_TRUE(my_map_copy != my_map); | ||
231 | EXPECT_TRUE(my_map != my_map_copy); | ||
232 | |||
233 | my_map_copy = my_map; | ||
234 | my_map["hello"] = kSetSize; | ||
235 | EXPECT_FALSE(my_map_copy == my_map); | ||
236 | EXPECT_FALSE(my_map == my_map_copy); | ||
237 | EXPECT_TRUE(my_map_copy != my_map); | ||
238 | EXPECT_TRUE(my_map != my_map_copy); | ||
239 | |||
240 | my_map.erase(std::string(kSetSize - 1, 'a')); | ||
241 | EXPECT_FALSE(my_map_copy == my_map); | ||
242 | EXPECT_FALSE(my_map == my_map_copy); | ||
243 | EXPECT_TRUE(my_map_copy != my_map); | ||
244 | EXPECT_TRUE(my_map != my_map_copy); | ||
245 | } | ||
246 | |||
247 | TEST(Btree, RangeCtorSanity) { | ||
248 | typedef btree_set<int, std::less<int>, std::allocator<int>, 256> test_set; | ||
249 | typedef btree_map<int, int, std::less<int>, std::allocator<int>, 256> | ||
250 | test_map; | ||
251 | typedef btree_multiset<int, std::less<int>, std::allocator<int>, 256> | ||
252 | test_mset; | ||
253 | typedef btree_multimap<int, int, std::less<int>, std::allocator<int>, 256> | ||
254 | test_mmap; | ||
255 | std::vector<int> ivec; | ||
256 | ivec.push_back(1); | ||
257 | std::map<int, int> imap; | ||
258 | imap.insert(std::make_pair(1, 2)); | ||
259 | test_mset tmset(ivec.begin(), ivec.end()); | ||
260 | test_mmap tmmap(imap.begin(), imap.end()); | ||
261 | test_set tset(ivec.begin(), ivec.end()); | ||
262 | test_map tmap(imap.begin(), imap.end()); | ||
263 | EXPECT_EQ(1, tmset.size()); | ||
264 | EXPECT_EQ(1, tmmap.size()); | ||
265 | EXPECT_EQ(1, tset.size()); | ||
266 | EXPECT_EQ(1, tmap.size()); | ||
267 | } | ||
268 | |||
269 | } // namespace | ||
270 | } // namespace btree | ||