The Tor Browser / file comparison

comparison: toolkit/crashreporter/google-breakpad/src/processor/static_map_unittest.cc

toolkit/crashreporter/google-breakpad/src/processor/static_map_unittest.cc

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

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial