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>
SetTest()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>
MapTest()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
TEST(Btree,set_int32_32)40 TEST(Btree, set_int32_32) { SetTest<int32_t, 32>(); }
TEST(Btree,set_int32_64)41 TEST(Btree, set_int32_64) { SetTest<int32_t, 64>(); }
TEST(Btree,set_int32_128)42 TEST(Btree, set_int32_128) { SetTest<int32_t, 128>(); }
TEST(Btree,set_int32_256)43 TEST(Btree, set_int32_256) { SetTest<int32_t, 256>(); }
TEST(Btree,set_int64_256)44 TEST(Btree, set_int64_256) { SetTest<int64_t, 256>(); }
TEST(Btree,set_string_256)45 TEST(Btree, set_string_256) { SetTest<std::string, 256>(); }
TEST(Btree,set_pair_256)46 TEST(Btree, set_pair_256) { SetTest<std::pair<int, int>, 256>(); }
TEST(Btree,map_int32_256)47 TEST(Btree, map_int32_256) { MapTest<int32_t, 256>(); }
TEST(Btree,map_int64_256)48 TEST(Btree, map_int64_256) { MapTest<int64_t, 256>(); }
TEST(Btree,map_string_256)49 TEST(Btree, map_string_256) { MapTest<std::string, 256>(); }
TEST(Btree,map_pair_256)50 TEST(Btree, map_pair_256) { MapTest<std::pair<int, int>, 256>(); }
51
52 // Large-node tests
TEST(Btree,map_int32_1024)53 TEST(Btree, map_int32_1024) { MapTest<int32_t, 1024>(); }
TEST(Btree,map_int32_1032)54 TEST(Btree, map_int32_1032) { MapTest<int32_t, 1032>(); }
TEST(Btree,map_int32_1040)55 TEST(Btree, map_int32_1040) { MapTest<int32_t, 1040>(); }
TEST(Btree,map_int32_1048)56 TEST(Btree, map_int32_1048) { MapTest<int32_t, 1048>(); }
TEST(Btree,map_int32_1056)57 TEST(Btree, map_int32_1056) { MapTest<int32_t, 1056>(); }
58
TEST(Btree,map_int32_2048)59 TEST(Btree, map_int32_2048) { MapTest<int32_t, 2048>(); }
TEST(Btree,map_int32_4096)60 TEST(Btree, map_int32_4096) { MapTest<int32_t, 4096>(); }
TEST(Btree,set_int32_1024)61 TEST(Btree, set_int32_1024) { SetTest<int32_t, 1024>(); }
TEST(Btree,set_int32_2048)62 TEST(Btree, set_int32_2048) { SetTest<int32_t, 2048>(); }
TEST(Btree,set_int32_4096)63 TEST(Btree, set_int32_4096) { SetTest<int32_t, 4096>(); }
TEST(Btree,map_string_1024)64 TEST(Btree, map_string_1024) { MapTest<std::string, 1024>(); }
TEST(Btree,map_string_2048)65 TEST(Btree, map_string_2048) { MapTest<std::string, 2048>(); }
TEST(Btree,map_string_4096)66 TEST(Btree, map_string_4096) { MapTest<std::string, 4096>(); }
TEST(Btree,set_string_1024)67 TEST(Btree, set_string_1024) { SetTest<std::string, 1024>(); }
TEST(Btree,set_string_2048)68 TEST(Btree, set_string_2048) { SetTest<std::string, 2048>(); }
TEST(Btree,set_string_4096)69 TEST(Btree, set_string_4096) { SetTest<std::string, 4096>(); }
70
71 template <typename K, int N>
MultiSetTest()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>
MultiMapTest()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
TEST(Btree,multiset_int32_256)90 TEST(Btree, multiset_int32_256) { MultiSetTest<int32_t, 256>(); }
TEST(Btree,multiset_int64_256)91 TEST(Btree, multiset_int64_256) { MultiSetTest<int64_t, 256>(); }
TEST(Btree,multiset_string_256)92 TEST(Btree, multiset_string_256) { MultiSetTest<std::string, 256>(); }
TEST(Btree,multiset_pair_256)93 TEST(Btree, multiset_pair_256) { MultiSetTest<std::pair<int, int>, 256>(); }
TEST(Btree,multimap_int32_256)94 TEST(Btree, multimap_int32_256) { MultiMapTest<int32_t, 256>(); }
TEST(Btree,multimap_int64_256)95 TEST(Btree, multimap_int64_256) { MultiMapTest<int64_t, 256>(); }
TEST(Btree,multimap_string_256)96 TEST(Btree, multimap_string_256) { MultiMapTest<std::string, 256>(); }
TEST(Btree,multimap_pair_256)97 TEST(Btree, multimap_pair_256) { MultiMapTest<std::pair<int, int>, 256>(); }
98
99 // Large-node tests
TEST(Btree,multimap_int32_1024)100 TEST(Btree, multimap_int32_1024) { MultiMapTest<int32_t, 1024>(); }
TEST(Btree,multimap_int32_2048)101 TEST(Btree, multimap_int32_2048) { MultiMapTest<int32_t, 2048>(); }
TEST(Btree,multimap_int32_4096)102 TEST(Btree, multimap_int32_4096) { MultiMapTest<int32_t, 4096>(); }
TEST(Btree,multiset_int32_1024)103 TEST(Btree, multiset_int32_1024) { MultiSetTest<int32_t, 1024>(); }
TEST(Btree,multiset_int32_2048)104 TEST(Btree, multiset_int32_2048) { MultiSetTest<int32_t, 2048>(); }
TEST(Btree,multiset_int32_4096)105 TEST(Btree, multiset_int32_4096) { MultiSetTest<int32_t, 4096>(); }
TEST(Btree,multimap_string_1024)106 TEST(Btree, multimap_string_1024) { MultiMapTest<std::string, 1024>(); }
TEST(Btree,multimap_string_2048)107 TEST(Btree, multimap_string_2048) { MultiMapTest<std::string, 2048>(); }
TEST(Btree,multimap_string_4096)108 TEST(Btree, multimap_string_4096) { MultiMapTest<std::string, 4096>(); }
TEST(Btree,multiset_string_1024)109 TEST(Btree, multiset_string_1024) { MultiSetTest<std::string, 1024>(); }
TEST(Btree,multiset_string_2048)110 TEST(Btree, multiset_string_2048) { MultiSetTest<std::string, 2048>(); }
TEST(Btree,multiset_string_4096)111 TEST(Btree, multiset_string_4096) { MultiSetTest<std::string, 4096>(); }
112
113 // Verify that swapping btrees swaps the key comparision functors.
114 struct SubstringLess {
SubstringLessbtree::__anond68472110111::SubstringLess115 SubstringLess() : n(2) {}
SubstringLessbtree::__anond68472110111::SubstringLess116 SubstringLess(size_t length)
117 : n(length) {
118 }
operator ()btree::__anond68472110111::SubstringLess119 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
TEST(Btree,SwapKeyCompare)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
TEST(Btree,UpperBoundRegression)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
TEST(Btree,IteratorIncrementBy)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
TEST(Btree,Comparison)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
TEST(Btree,RangeCtorSanity)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
271