The Tor Browser: toolkit/crashreporter/google-breakpad/src/processor/static_map

Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.

     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.

    30 // static_map_unittest.cc: Unit tests for StaticMap.

    31 //

    32 // Author: Siyang Xie (lambxsy@google.com)

    34 #include <climits>

    35 #include <map>

    37 #include "breakpad_googletest_includes.h"

    38 #include "processor/static_map-inl.h"

    41 typedef int ValueType;

    42 typedef int KeyType;

    43 typedef google_breakpad::StaticMap< KeyType, ValueType > TestMap;

    44 typedef std::map< KeyType, ValueType > StdMap;

    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;

    56     // Allocate memory for serialized data:

    57     char* mem = reinterpret_cast<char*>(operator new(memsize));

    58     char* address = mem;

    60     // Writer the number of nodes:

    61     new (address) uint32_t(static_cast<uint32_t>(stdmap.size()));

    62     address += sizeof(uint32_t);

    64     // Nodes' offset:

    65     uint32_t* offsets = reinterpret_cast<uint32_t*>(address);

    66     address += sizeof(uint32_t) * stdmap.size();

    68     // Keys:

    69     Key* keys = reinterpret_cast<Key*>(address);

    70     address += sizeof(Key) * stdmap.size();

    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 };

    85 class TestInvalidMap : public ::testing::Test {

    86  protected:

    87   void SetUp() {

    88     memset(data, 0, kMemorySize);

    89   }

    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 };

    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 }

   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));

   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());

   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 }

   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);

   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 }

   139 class TestValidMap : public ::testing::Test {

   140  protected:

   141   void SetUp() {

   142     int testcase = 0;

   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;

   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;

   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;

   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]);

   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   }

   181   void TearDown() {

   182     for (int i = 0;i < kNumberTestCases; ++i)

   183       delete map_data[i];

   184   }

   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();

   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());

   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);

   211       ++iter_test;

   212       ++iter_std;

   213       ASSERT_TRUE(iter_test == test_map[test_case].end());

   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);

   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   }

   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);

   234     if (found1 && found2) {

   235       ASSERT_EQ(iter_test.GetKey(), iter_std->first);

   236       ASSERT_EQ(*(iter_test.GetValuePtr()), iter_std->second);

   237     }

   238   }

   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   }

   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   }

   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   }

   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());

   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());

   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   }

   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 };

   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]);

   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());

   324   // Test Iterator.

   325   IteratorTester(test_case);

   327   // Test lookup operations.

   328   LookupTester(test_case);

   329 }

   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]);

   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());

   341   // Test Iterator.

   342   IteratorTester(test_case);

   344   // Test lookup operations.

   345   LookupTester(test_case);

   346 }

   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]);

   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());

   358   // Test Iterator.

   359   IteratorTester(test_case);

   361   // Test lookup operations.

   362   LookupTester(test_case);

   363 }

   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]);

   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());

   375   // Test Iterator.

   376   IteratorTester(test_case);

   378   // Test lookup operations.

   379   LookupTester(test_case);

   380 }

   382 int main(int argc, char *argv[]) {

   383   ::testing::InitGoogleTest(&argc, argv);

   385   return RUN_ALL_TESTS();

   386 }

The Tor Browser / file revision

toolkit/crashreporter/google-breakpad/src/processor/static_map_unittest.cc@6474c204b198

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