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 (lambxsy@google.com)
 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:
 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:
 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  
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  
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  
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:
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  
184    void TearDown() {
185      for (int i = 0;i < kNumberTestCases; ++i)
186        ::operator delete(map_data[i]);
187    }
188  
189  
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  
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  
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  
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  
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  
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  
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  
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  
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  
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  
385  int main(int argc, char *argv[]) {
386    ::testing::InitGoogleTest(&argc, argv);
387  
388    return RUN_ALL_TESTS();
389  }