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:
Serialize(const std::map<Key,Value> & stdmap,unsigned int * size=NULL)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:
SetUp()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 
TEST_F(TestInvalidMap,TestNegativeNumberNodes)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 
TEST_F(TestInvalidMap,TestWrongOffsets)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 
TEST_F(TestInvalidMap,TestUnSortedKeys)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:
SetUp()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 
TearDown()181   void TearDown() {
182     for (int i = 0;i < kNumberTestCases; ++i)
183       delete map_data[i];
184   }
185 
186 
IteratorTester(int test_case)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 
CompareLookupResult(int test_case)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 
FindTester(int test_case,const KeyType & key)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 
LowerBoundTester(int test_case,const KeyType & key)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 
UpperBoundTester(int test_case,const KeyType & key)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 
LookupTester(int test_case)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 
TEST_F(TestValidMap,TestEmptyMap)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 
TEST_F(TestValidMap,TestSingleElement)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 
TEST_F(TestValidMap,Test100Elements)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 
TEST_F(TestValidMap,Test1000RandomElements)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 
main(int argc,char * argv[])382 int main(int argc, char *argv[]) {
383   ::testing::InitGoogleTest(&argc, argv);
384 
385   return RUN_ALL_TESTS();
386 }
387