1 // Copyright 2010 Google LLC
2 //
3 // Redistribution and use in source and binary forms, with or without
4 // modification, are permitted provided that the following conditions are
5 // met:
6 //
7 // * Redistributions of source code must retain the above copyright
8 // notice, this list of conditions and the following disclaimer.
9 // * Redistributions in binary form must reproduce the above
10 // copyright notice, this list of conditions and the following disclaimer
11 // in the documentation and/or other materials provided with the
12 // distribution.
13 // * Neither the name of Google LLC nor the names of its
14 // contributors may be used to endorse or promote products derived from
15 // this software without specific prior written permission.
16 //
17 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
21 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28
29 // static_map_unittest.cc: Unit tests for StaticMap.
30 //
31 // Author: Siyang Xie ([email protected])
32
33 #ifdef HAVE_CONFIG_H
34 #include <config.h> // Must come first
35 #endif
36
37 #include <climits>
38 #include <map>
39
40 #include "breakpad_googletest_includes.h"
41 #include "processor/static_map-inl.h"
42
43
44 typedef int ValueType;
45 typedef int KeyType;
46 typedef google_breakpad::StaticMap< KeyType, ValueType > TestMap;
47 typedef std::map< KeyType, ValueType > StdMap;
48
49 template<typename Key, typename Value>
50 class SimpleMapSerializer {
51 public:
Serialize(const std::map<Key,Value> & stdmap,unsigned int * size=NULL)52 static char* Serialize(const std::map<Key, Value>& stdmap,
53 unsigned int* size = NULL) {
54 unsigned int size_per_node =
55 sizeof(uint32_t) + sizeof(Key) + sizeof(Value);
56 unsigned int memsize = sizeof(int32_t) + size_per_node * stdmap.size();
57 if (size) *size = memsize;
58
59 // Allocate memory for serialized data:
60 char* mem = reinterpret_cast<char*>(operator new(memsize));
61 char* address = mem;
62
63 // Writer the number of nodes:
64 new (address) uint32_t(static_cast<uint32_t>(stdmap.size()));
65 address += sizeof(uint32_t);
66
67 // Nodes' offset:
68 uint32_t* offsets = reinterpret_cast<uint32_t*>(address);
69 address += sizeof(uint32_t) * stdmap.size();
70
71 // Keys:
72 Key* keys = reinterpret_cast<Key*>(address);
73 address += sizeof(Key) * stdmap.size();
74
75 // Traversing map:
76 typename std::map<Key, Value>::const_iterator iter = stdmap.begin();
77 for (int index = 0; iter != stdmap.end(); ++iter, ++index) {
78 offsets[index] = static_cast<unsigned int>(address - mem);
79 keys[index] = iter->first;
80 new (address) Value(iter->second);
81 address += sizeof(Value);
82 }
83 return mem;
84 }
85 };
86
87
88 class TestInvalidMap : public ::testing::Test {
89 protected:
SetUp()90 void SetUp() {
91 memset(data, 0, kMemorySize);
92 }
93
94 // 40 Bytes memory can hold a StaticMap with up to 3 nodes.
95 static const int kMemorySize = 40;
96 char data[kMemorySize];
97 TestMap test_map;
98 };
99
TEST_F(TestInvalidMap,TestNegativeNumberNodes)100 TEST_F(TestInvalidMap, TestNegativeNumberNodes) {
101 memset(data, 0xff, sizeof(uint32_t)); // Set the number of nodes = -1
102 test_map = TestMap(data);
103 ASSERT_FALSE(test_map.ValidateInMemoryStructure());
104 }
105
TEST_F(TestInvalidMap,TestWrongOffsets)106 TEST_F(TestInvalidMap, TestWrongOffsets) {
107 uint32_t* header = reinterpret_cast<uint32_t*>(data);
108 const uint32_t kNumNodes = 2;
109 const uint32_t kHeaderOffset =
110 sizeof(uint32_t) + kNumNodes * (sizeof(uint32_t) + sizeof(KeyType));
111
112 header[0] = kNumNodes;
113 header[1] = kHeaderOffset + 3; // Wrong offset for first node
114 test_map = TestMap(data);
115 ASSERT_FALSE(test_map.ValidateInMemoryStructure());
116
117 header[1] = kHeaderOffset; // Correct offset for first node
118 header[2] = kHeaderOffset - 1; // Wrong offset for second node
119 test_map = TestMap(data);
120 ASSERT_FALSE(test_map.ValidateInMemoryStructure());
121 }
122
TEST_F(TestInvalidMap,TestUnSortedKeys)123 TEST_F(TestInvalidMap, TestUnSortedKeys) {
124 uint32_t* header = reinterpret_cast<uint32_t*>(data);
125 const uint32_t kNumNodes = 2;
126 const uint32_t kHeaderOffset =
127 sizeof(uint32_t) + kNumNodes * (sizeof(uint32_t) + sizeof(KeyType));
128 header[0] = kNumNodes;
129 header[1] = kHeaderOffset;
130 header[2] = kHeaderOffset + sizeof(ValueType);
131
132 KeyType* keys = reinterpret_cast<KeyType*>(
133 data + (kNumNodes + 1) * sizeof(uint32_t));
134 // Set keys in non-increasing order.
135 keys[0] = 10;
136 keys[1] = 7;
137 test_map = TestMap(data);
138 ASSERT_FALSE(test_map.ValidateInMemoryStructure());
139 }
140
141
142 class TestValidMap : public ::testing::Test {
143 protected:
SetUp()144 void SetUp() {
145 int testcase = 0;
146
147 // Empty map.
148 map_data[testcase] =
149 serializer.Serialize(std_map[testcase], &size[testcase]);
150 test_map[testcase] = TestMap(map_data[testcase]);
151 ++testcase;
152
153 // Single element.
154 std_map[testcase].insert(std::make_pair(2, 8));
155 map_data[testcase] =
156 serializer.Serialize(std_map[testcase], &size[testcase]);
157 test_map[testcase] = TestMap(map_data[testcase]);
158 ++testcase;
159
160 // 100 elements.
161 for (int i = 0; i < 100; ++i)
162 std_map[testcase].insert(std::make_pair(i, 2 * i));
163 map_data[testcase] =
164 serializer.Serialize(std_map[testcase], &size[testcase]);
165 test_map[testcase] = TestMap(map_data[testcase]);
166 ++testcase;
167
168 // 1000 random elements.
169 for (int i = 0; i < 1000; ++i)
170 std_map[testcase].insert(std::make_pair(rand(), rand()));
171 map_data[testcase] =
172 serializer.Serialize(std_map[testcase], &size[testcase]);
173 test_map[testcase] = TestMap(map_data[testcase]);
174
175 // Set correct size of memory allocation for each test case.
176 unsigned int size_per_node =
177 sizeof(uint32_t) + sizeof(KeyType) + sizeof(ValueType);
178 for (testcase = 0; testcase < kNumberTestCases; ++testcase) {
179 correct_size[testcase] =
180 sizeof(uint32_t) + std_map[testcase].size() * size_per_node;
181 }
182 }
183
TearDown()184 void TearDown() {
185 for (int i = 0;i < kNumberTestCases; ++i)
186 ::operator delete(map_data[i]);
187 }
188
189
IteratorTester(int test_case)190 void IteratorTester(int test_case) {
191 // scan through:
192 iter_test = test_map[test_case].begin();
193 iter_std = std_map[test_case].begin();
194
195 for (; iter_test != test_map[test_case].end() &&
196 iter_std != std_map[test_case].end();
197 ++iter_test, ++iter_std) {
198 ASSERT_EQ(iter_test.GetKey(), iter_std->first);
199 ASSERT_EQ(*(iter_test.GetValuePtr()), iter_std->second);
200 }
201 ASSERT_TRUE(iter_test == test_map[test_case].end()
202 && iter_std == std_map[test_case].end());
203
204 // Boundary testcase.
205 if (!std_map[test_case].empty()) {
206 // rear boundary case:
207 iter_test = test_map[test_case].end();
208 iter_std = std_map[test_case].end();
209 --iter_std;
210 --iter_test;
211 ASSERT_EQ(iter_test.GetKey(), iter_std->first);
212 ASSERT_EQ(*(iter_test.GetValuePtr()), iter_std->second);
213
214 ++iter_test;
215 ++iter_std;
216 ASSERT_TRUE(iter_test == test_map[test_case].end());
217
218 --iter_test;
219 --iter_std;
220 ASSERT_TRUE(iter_test != test_map[test_case].end());
221 ASSERT_TRUE(iter_test == test_map[test_case].last());
222 ASSERT_EQ(iter_test.GetKey(), iter_std->first);
223 ASSERT_EQ(*(iter_test.GetValuePtr()), iter_std->second);
224
225 // front boundary case:
226 iter_test = test_map[test_case].begin();
227 --iter_test;
228 ASSERT_TRUE(iter_test == test_map[test_case].begin());
229 }
230 }
231
CompareLookupResult(int test_case)232 void CompareLookupResult(int test_case) {
233 bool found1 = (iter_test != test_map[test_case].end());
234 bool found2 = (iter_std != std_map[test_case].end());
235 ASSERT_EQ(found1, found2);
236
237 if (found1 && found2) {
238 ASSERT_EQ(iter_test.GetKey(), iter_std->first);
239 ASSERT_EQ(*(iter_test.GetValuePtr()), iter_std->second);
240 }
241 }
242
FindTester(int test_case,const KeyType & key)243 void FindTester(int test_case, const KeyType& key) {
244 iter_test = test_map[test_case].find(key);
245 iter_std = std_map[test_case].find(key);
246 CompareLookupResult(test_case);
247 }
248
LowerBoundTester(int test_case,const KeyType & key)249 void LowerBoundTester(int test_case, const KeyType& key) {
250 iter_test = test_map[test_case].lower_bound(key);
251 iter_std = std_map[test_case].lower_bound(key);
252 CompareLookupResult(test_case);
253 }
254
UpperBoundTester(int test_case,const KeyType & key)255 void UpperBoundTester(int test_case, const KeyType& key) {
256 iter_test = test_map[test_case].upper_bound(key);
257 iter_std = std_map[test_case].upper_bound(key);
258 CompareLookupResult(test_case);
259 }
260
LookupTester(int test_case)261 void LookupTester(int test_case) {
262 StdMap::const_iterator iter;
263 // Test find():
264 for (iter = std_map[test_case].begin();
265 iter != std_map[test_case].end();
266 ++iter) {
267 FindTester(test_case, iter->first);
268 FindTester(test_case, iter->first + 1);
269 FindTester(test_case, iter->first - 1);
270 }
271 FindTester(test_case, INT_MIN);
272 FindTester(test_case, INT_MAX);
273 // random test:
274 for (int i = 0; i < rand()%5000 + 5000; ++i)
275 FindTester(test_case, rand());
276
277 // Test lower_bound():
278 for (iter = std_map[test_case].begin();
279 iter != std_map[test_case].end();
280 ++iter) {
281 LowerBoundTester(test_case, iter->first);
282 LowerBoundTester(test_case, iter->first + 1);
283 LowerBoundTester(test_case, iter->first - 1);
284 }
285 LowerBoundTester(test_case, INT_MIN);
286 LowerBoundTester(test_case, INT_MAX);
287 // random test:
288 for (int i = 0; i < rand()%5000 + 5000; ++i)
289 LowerBoundTester(test_case, rand());
290
291 // Test upper_bound():
292 for (iter = std_map[test_case].begin();
293 iter != std_map[test_case].end();
294 ++iter) {
295 UpperBoundTester(test_case, iter->first);
296 UpperBoundTester(test_case, iter->first + 1);
297 UpperBoundTester(test_case, iter->first - 1);
298 }
299 UpperBoundTester(test_case, INT_MIN);
300 UpperBoundTester(test_case, INT_MAX);
301 // random test:
302 for (int i = 0; i < rand()%5000 + 5000; ++i)
303 UpperBoundTester(test_case, rand());
304 }
305
306 static const int kNumberTestCases = 4;
307 StdMap std_map[kNumberTestCases];
308 TestMap test_map[kNumberTestCases];
309 TestMap::const_iterator iter_test;
310 StdMap::const_iterator iter_std;
311 char* map_data[kNumberTestCases];
312 unsigned int size[kNumberTestCases];
313 unsigned int correct_size[kNumberTestCases];
314 SimpleMapSerializer<KeyType, ValueType> serializer;
315 };
316
TEST_F(TestValidMap,TestEmptyMap)317 TEST_F(TestValidMap, TestEmptyMap) {
318 int test_case = 0;
319 // Assert memory size allocated during serialization is correct.
320 ASSERT_EQ(correct_size[test_case], size[test_case]);
321
322 // Sanity check of serialized data:
323 ASSERT_TRUE(test_map[test_case].ValidateInMemoryStructure());
324 ASSERT_EQ(std_map[test_case].empty(), test_map[test_case].empty());
325 ASSERT_EQ(std_map[test_case].size(), test_map[test_case].size());
326
327 // Test Iterator.
328 IteratorTester(test_case);
329
330 // Test lookup operations.
331 LookupTester(test_case);
332 }
333
TEST_F(TestValidMap,TestSingleElement)334 TEST_F(TestValidMap, TestSingleElement) {
335 int test_case = 1;
336 // Assert memory size allocated during serialization is correct.
337 ASSERT_EQ(correct_size[test_case], size[test_case]);
338
339 // Sanity check of serialized data:
340 ASSERT_TRUE(test_map[test_case].ValidateInMemoryStructure());
341 ASSERT_EQ(std_map[test_case].empty(), test_map[test_case].empty());
342 ASSERT_EQ(std_map[test_case].size(), test_map[test_case].size());
343
344 // Test Iterator.
345 IteratorTester(test_case);
346
347 // Test lookup operations.
348 LookupTester(test_case);
349 }
350
TEST_F(TestValidMap,Test100Elements)351 TEST_F(TestValidMap, Test100Elements) {
352 int test_case = 2;
353 // Assert memory size allocated during serialization is correct.
354 ASSERT_EQ(correct_size[test_case], size[test_case]);
355
356 // Sanity check of serialized data:
357 ASSERT_TRUE(test_map[test_case].ValidateInMemoryStructure());
358 ASSERT_EQ(std_map[test_case].empty(), test_map[test_case].empty());
359 ASSERT_EQ(std_map[test_case].size(), test_map[test_case].size());
360
361 // Test Iterator.
362 IteratorTester(test_case);
363
364 // Test lookup operations.
365 LookupTester(test_case);
366 }
367
TEST_F(TestValidMap,Test1000RandomElements)368 TEST_F(TestValidMap, Test1000RandomElements) {
369 int test_case = 3;
370 // Assert memory size allocated during serialization is correct.
371 ASSERT_EQ(correct_size[test_case], size[test_case]);
372
373 // Sanity check of serialized data:
374 ASSERT_TRUE(test_map[test_case].ValidateInMemoryStructure());
375 ASSERT_EQ(std_map[test_case].empty(), test_map[test_case].empty());
376 ASSERT_EQ(std_map[test_case].size(), test_map[test_case].size());
377
378 // Test Iterator.
379 IteratorTester(test_case);
380
381 // Test lookup operations.
382 LookupTester(test_case);
383 }
384
main(int argc,char * argv[])385 int main(int argc, char *argv[]) {
386 ::testing::InitGoogleTest(&argc, argv);
387
388 return RUN_ALL_TESTS();
389 }
390