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
41typedef int ValueType;
42typedef int KeyType;
43typedef google_breakpad::StaticMap< KeyType, ValueType > TestMap;
44typedef std::map< KeyType, ValueType > StdMap;
45
46template<typename Key, typename Value>
47class 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
85class 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
97TEST_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
103TEST_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
120TEST_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
139class 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
314TEST_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
331TEST_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
348TEST_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
365TEST_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
382int main(int argc, char *argv[]) {
383  ::testing::InitGoogleTest(&argc, argv);
384
385  return RUN_ALL_TESTS();
386}
387