michael@0: // Copyright (c) 2010 Google Inc.
michael@0: // All rights reserved.
michael@0: //
michael@0: // Redistribution and use in source and binary forms, with or without
michael@0: // modification, are permitted provided that the following conditions are
michael@0: // met:
michael@0: //
michael@0: //     * Redistributions of source code must retain the above copyright
michael@0: // notice, this list of conditions and the following disclaimer.
michael@0: //     * Redistributions in binary form must reproduce the above
michael@0: // copyright notice, this list of conditions and the following disclaimer
michael@0: // in the documentation and/or other materials provided with the
michael@0: // distribution.
michael@0: //     * Neither the name of Google Inc. nor the names of its
michael@0: // contributors may be used to endorse or promote products derived from
michael@0: // this software without specific prior written permission.
michael@0: //
michael@0: // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
michael@0: // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
michael@0: // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
michael@0: // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
michael@0: // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
michael@0: // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
michael@0: // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
michael@0: // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
michael@0: // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
michael@0: // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
michael@0: // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
michael@0: 
michael@0: // static_map_unittest.cc: Unit tests for StaticMap.
michael@0: //
michael@0: // Author: Siyang Xie (lambxsy@google.com)
michael@0: 
michael@0: #include <climits>
michael@0: #include <map>
michael@0: 
michael@0: #include "breakpad_googletest_includes.h"
michael@0: #include "processor/static_map-inl.h"
michael@0: 
michael@0: 
michael@0: typedef int ValueType;
michael@0: typedef int KeyType;
michael@0: typedef google_breakpad::StaticMap< KeyType, ValueType > TestMap;
michael@0: typedef std::map< KeyType, ValueType > StdMap;
michael@0: 
michael@0: template<typename Key, typename Value>
michael@0: class SimpleMapSerializer {
michael@0:  public:
michael@0:   static char* Serialize(const std::map<Key, Value> &stdmap,
michael@0:                    unsigned int* size = NULL) {
michael@0:     unsigned int size_per_node =
michael@0:         sizeof(uint32_t) + sizeof(Key) + sizeof(Value);
michael@0:     unsigned int memsize = sizeof(int32_t) + size_per_node * stdmap.size();
michael@0:     if (size) *size = memsize;
michael@0: 
michael@0:     // Allocate memory for serialized data:
michael@0:     char* mem = reinterpret_cast<char*>(operator new(memsize));
michael@0:     char* address = mem;
michael@0: 
michael@0:     // Writer the number of nodes:
michael@0:     new (address) uint32_t(static_cast<uint32_t>(stdmap.size()));
michael@0:     address += sizeof(uint32_t);
michael@0: 
michael@0:     // Nodes' offset:
michael@0:     uint32_t* offsets = reinterpret_cast<uint32_t*>(address);
michael@0:     address += sizeof(uint32_t) * stdmap.size();
michael@0: 
michael@0:     // Keys:
michael@0:     Key* keys = reinterpret_cast<Key*>(address);
michael@0:     address += sizeof(Key) * stdmap.size();
michael@0: 
michael@0:     // Traversing map:
michael@0:     typename std::map<Key, Value>::const_iterator iter = stdmap.begin();
michael@0:     for (int index = 0; iter != stdmap.end(); ++iter, ++index) {
michael@0:       offsets[index] = static_cast<unsigned int>(address - mem);
michael@0:       keys[index] = iter->first;
michael@0:       new (address) Value(iter->second);
michael@0:       address += sizeof(Value);
michael@0:     }
michael@0:     return mem;
michael@0:   }
michael@0: };
michael@0: 
michael@0: 
michael@0: class TestInvalidMap : public ::testing::Test {
michael@0:  protected:
michael@0:   void SetUp() {
michael@0:     memset(data, 0, kMemorySize);
michael@0:   }
michael@0: 
michael@0:   // 40 Bytes memory can hold a StaticMap with up to 3 nodes.
michael@0:   static const int kMemorySize = 40;
michael@0:   char data[kMemorySize];
michael@0:   TestMap test_map;
michael@0: };
michael@0: 
michael@0: TEST_F(TestInvalidMap, TestNegativeNumberNodes) {
michael@0:   memset(data, 0xff, sizeof(uint32_t));  // Set the number of nodes = -1
michael@0:   test_map = TestMap(data);
michael@0:   ASSERT_FALSE(test_map.ValidateInMemoryStructure());
michael@0: }
michael@0: 
michael@0: TEST_F(TestInvalidMap, TestWrongOffsets) {
michael@0:   uint32_t* header = reinterpret_cast<uint32_t*>(data);
michael@0:   const uint32_t kNumNodes = 2;
michael@0:   const uint32_t kHeaderOffset =
michael@0:         sizeof(uint32_t) + kNumNodes * (sizeof(uint32_t) + sizeof(KeyType));
michael@0: 
michael@0:   header[0] = kNumNodes;
michael@0:   header[1] = kHeaderOffset + 3;   // Wrong offset for first node
michael@0:   test_map = TestMap(data);
michael@0:   ASSERT_FALSE(test_map.ValidateInMemoryStructure());
michael@0: 
michael@0:   header[1] = kHeaderOffset;       // Correct offset for first node
michael@0:   header[2] = kHeaderOffset - 1;   // Wrong offset for second node
michael@0:   test_map = TestMap(data);
michael@0:   ASSERT_FALSE(test_map.ValidateInMemoryStructure());
michael@0: }
michael@0: 
michael@0: TEST_F(TestInvalidMap, TestUnSortedKeys) {
michael@0:   uint32_t* header = reinterpret_cast<uint32_t*>(data);
michael@0:   const uint32_t kNumNodes = 2;
michael@0:   const uint32_t kHeaderOffset =
michael@0:       sizeof(uint32_t) + kNumNodes * (sizeof(uint32_t) + sizeof(KeyType));
michael@0:   header[0] = kNumNodes;
michael@0:   header[1] = kHeaderOffset;
michael@0:   header[2] = kHeaderOffset + sizeof(ValueType);
michael@0: 
michael@0:   KeyType* keys = reinterpret_cast<KeyType*>(
michael@0:       data + (kNumNodes + 1) * sizeof(uint32_t));
michael@0:   // Set keys in non-increasing order.
michael@0:   keys[0] = 10;
michael@0:   keys[1] = 7;
michael@0:   test_map = TestMap(data);
michael@0:   ASSERT_FALSE(test_map.ValidateInMemoryStructure());
michael@0: }
michael@0: 
michael@0: 
michael@0: class TestValidMap : public ::testing::Test {
michael@0:  protected:
michael@0:   void SetUp() {
michael@0:     int testcase = 0;
michael@0: 
michael@0:     // Empty map.
michael@0:     map_data[testcase] =
michael@0:         serializer.Serialize(std_map[testcase], &size[testcase]);
michael@0:     test_map[testcase] = TestMap(map_data[testcase]);
michael@0:     ++testcase;
michael@0: 
michael@0:     // Single element.
michael@0:     std_map[testcase].insert(std::make_pair(2, 8));
michael@0:     map_data[testcase] =
michael@0:         serializer.Serialize(std_map[testcase], &size[testcase]);
michael@0:     test_map[testcase] = TestMap(map_data[testcase]);
michael@0:     ++testcase;
michael@0: 
michael@0:     // 100 elements.
michael@0:     for (int i = 0; i < 100; ++i)
michael@0:           std_map[testcase].insert(std::make_pair(i, 2 * i));
michael@0:     map_data[testcase] =
michael@0:         serializer.Serialize(std_map[testcase], &size[testcase]);
michael@0:     test_map[testcase] = TestMap(map_data[testcase]);
michael@0:     ++testcase;
michael@0: 
michael@0:     // 1000 random elements.
michael@0:     for (int i = 0; i < 1000; ++i)
michael@0:       std_map[testcase].insert(std::make_pair(rand(), rand()));
michael@0:     map_data[testcase] =
michael@0:         serializer.Serialize(std_map[testcase], &size[testcase]);
michael@0:     test_map[testcase] = TestMap(map_data[testcase]);
michael@0: 
michael@0:     // Set correct size of memory allocation for each test case.
michael@0:     unsigned int size_per_node =
michael@0:         sizeof(uint32_t) + sizeof(KeyType) + sizeof(ValueType);
michael@0:     for (testcase = 0; testcase < kNumberTestCases; ++testcase) {
michael@0:       correct_size[testcase] =
michael@0:           sizeof(uint32_t) + std_map[testcase].size() * size_per_node;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   void TearDown() {
michael@0:     for (int i = 0;i < kNumberTestCases; ++i)
michael@0:       delete map_data[i];
michael@0:   }
michael@0: 
michael@0: 
michael@0:   void IteratorTester(int test_case) {
michael@0:     // scan through:
michael@0:     iter_test = test_map[test_case].begin();
michael@0:     iter_std = std_map[test_case].begin();
michael@0: 
michael@0:     for (; iter_test != test_map[test_case].end() &&
michael@0:            iter_std != std_map[test_case].end();
michael@0:          ++iter_test, ++iter_std) {
michael@0:       ASSERT_EQ(iter_test.GetKey(), iter_std->first);
michael@0:       ASSERT_EQ(*(iter_test.GetValuePtr()), iter_std->second);
michael@0:     }
michael@0:     ASSERT_TRUE(iter_test == test_map[test_case].end()
michael@0:              && iter_std == std_map[test_case].end());
michael@0: 
michael@0:     // Boundary testcase.
michael@0:     if (!std_map[test_case].empty()) {
michael@0:       // rear boundary case:
michael@0:       iter_test = test_map[test_case].end();
michael@0:       iter_std = std_map[test_case].end();
michael@0:       --iter_std;
michael@0:       --iter_test;
michael@0:       ASSERT_EQ(iter_test.GetKey(), iter_std->first);
michael@0:       ASSERT_EQ(*(iter_test.GetValuePtr()), iter_std->second);
michael@0: 
michael@0:       ++iter_test;
michael@0:       ++iter_std;
michael@0:       ASSERT_TRUE(iter_test == test_map[test_case].end());
michael@0: 
michael@0:       --iter_test;
michael@0:       --iter_std;
michael@0:       ASSERT_TRUE(iter_test != test_map[test_case].end());
michael@0:       ASSERT_TRUE(iter_test == test_map[test_case].last());
michael@0:       ASSERT_EQ(iter_test.GetKey(), iter_std->first);
michael@0:       ASSERT_EQ(*(iter_test.GetValuePtr()), iter_std->second);
michael@0: 
michael@0:       // front boundary case:
michael@0:       iter_test = test_map[test_case].begin();
michael@0:       --iter_test;
michael@0:       ASSERT_TRUE(iter_test == test_map[test_case].begin());
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   void CompareLookupResult(int test_case) {
michael@0:     bool found1 = (iter_test != test_map[test_case].end());
michael@0:     bool found2 = (iter_std != std_map[test_case].end());
michael@0:     ASSERT_EQ(found1, found2);
michael@0: 
michael@0:     if (found1 && found2) {
michael@0:       ASSERT_EQ(iter_test.GetKey(), iter_std->first);
michael@0:       ASSERT_EQ(*(iter_test.GetValuePtr()), iter_std->second);
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   void FindTester(int test_case, const KeyType &key) {
michael@0:     iter_test = test_map[test_case].find(key);
michael@0:     iter_std = std_map[test_case].find(key);
michael@0:     CompareLookupResult(test_case);
michael@0:   }
michael@0: 
michael@0:   void LowerBoundTester(int test_case, const KeyType &key) {
michael@0:     iter_test = test_map[test_case].lower_bound(key);
michael@0:     iter_std = std_map[test_case].lower_bound(key);
michael@0:     CompareLookupResult(test_case);
michael@0:   }
michael@0: 
michael@0:   void UpperBoundTester(int test_case, const KeyType &key) {
michael@0:     iter_test = test_map[test_case].upper_bound(key);
michael@0:     iter_std = std_map[test_case].upper_bound(key);
michael@0:     CompareLookupResult(test_case);
michael@0:   }
michael@0: 
michael@0:   void LookupTester(int test_case) {
michael@0:     StdMap::const_iterator iter;
michael@0:     // Test find():
michael@0:     for (iter = std_map[test_case].begin();
michael@0:         iter != std_map[test_case].end();
michael@0:         ++iter) {
michael@0:       FindTester(test_case, iter->first);
michael@0:       FindTester(test_case, iter->first + 1);
michael@0:       FindTester(test_case, iter->first - 1);
michael@0:     }
michael@0:     FindTester(test_case, INT_MIN);
michael@0:     FindTester(test_case, INT_MAX);
michael@0:     // random test:
michael@0:     for (int i = 0; i < rand()%5000 + 5000; ++i)
michael@0:       FindTester(test_case, rand());
michael@0: 
michael@0:     // Test lower_bound():
michael@0:     for (iter = std_map[test_case].begin();
michael@0:         iter != std_map[test_case].end();
michael@0:         ++iter) {
michael@0:       LowerBoundTester(test_case, iter->first);
michael@0:       LowerBoundTester(test_case, iter->first + 1);
michael@0:       LowerBoundTester(test_case, iter->first - 1);
michael@0:     }
michael@0:     LowerBoundTester(test_case, INT_MIN);
michael@0:     LowerBoundTester(test_case, INT_MAX);
michael@0:     // random test:
michael@0:     for (int i = 0; i < rand()%5000 + 5000; ++i)
michael@0:       LowerBoundTester(test_case, rand());
michael@0: 
michael@0:     // Test upper_bound():
michael@0:     for (iter = std_map[test_case].begin();
michael@0:         iter != std_map[test_case].end();
michael@0:         ++iter) {
michael@0:       UpperBoundTester(test_case, iter->first);
michael@0:       UpperBoundTester(test_case, iter->first + 1);
michael@0:       UpperBoundTester(test_case, iter->first - 1);
michael@0:     }
michael@0:     UpperBoundTester(test_case, INT_MIN);
michael@0:     UpperBoundTester(test_case, INT_MAX);
michael@0:     // random test:
michael@0:     for (int i = 0; i < rand()%5000 + 5000; ++i)
michael@0:       UpperBoundTester(test_case, rand());
michael@0:   }
michael@0: 
michael@0:   static const int kNumberTestCases = 4;
michael@0:   StdMap std_map[kNumberTestCases];
michael@0:   TestMap test_map[kNumberTestCases];
michael@0:   TestMap::const_iterator iter_test;
michael@0:   StdMap::const_iterator iter_std;
michael@0:   char* map_data[kNumberTestCases];
michael@0:   unsigned int size[kNumberTestCases];
michael@0:   unsigned int correct_size[kNumberTestCases];
michael@0:   SimpleMapSerializer<KeyType, ValueType> serializer;
michael@0: };
michael@0: 
michael@0: TEST_F(TestValidMap, TestEmptyMap) {
michael@0:   int test_case = 0;
michael@0:   // Assert memory size allocated during serialization is correct.
michael@0:   ASSERT_EQ(correct_size[test_case], size[test_case]);
michael@0: 
michael@0:   // Sanity check of serialized data:
michael@0:   ASSERT_TRUE(test_map[test_case].ValidateInMemoryStructure());
michael@0:   ASSERT_EQ(std_map[test_case].empty(), test_map[test_case].empty());
michael@0:   ASSERT_EQ(std_map[test_case].size(), test_map[test_case].size());
michael@0: 
michael@0:   // Test Iterator.
michael@0:   IteratorTester(test_case);
michael@0: 
michael@0:   // Test lookup operations.
michael@0:   LookupTester(test_case);
michael@0: }
michael@0: 
michael@0: TEST_F(TestValidMap, TestSingleElement) {
michael@0:   int test_case = 1;
michael@0:   // Assert memory size allocated during serialization is correct.
michael@0:   ASSERT_EQ(correct_size[test_case], size[test_case]);
michael@0: 
michael@0:   // Sanity check of serialized data:
michael@0:   ASSERT_TRUE(test_map[test_case].ValidateInMemoryStructure());
michael@0:   ASSERT_EQ(std_map[test_case].empty(), test_map[test_case].empty());
michael@0:   ASSERT_EQ(std_map[test_case].size(), test_map[test_case].size());
michael@0: 
michael@0:   // Test Iterator.
michael@0:   IteratorTester(test_case);
michael@0: 
michael@0:   // Test lookup operations.
michael@0:   LookupTester(test_case);
michael@0: }
michael@0: 
michael@0: TEST_F(TestValidMap, Test100Elements) {
michael@0:   int test_case = 2;
michael@0:   // Assert memory size allocated during serialization is correct.
michael@0:   ASSERT_EQ(correct_size[test_case], size[test_case]);
michael@0: 
michael@0:   // Sanity check of serialized data:
michael@0:   ASSERT_TRUE(test_map[test_case].ValidateInMemoryStructure());
michael@0:   ASSERT_EQ(std_map[test_case].empty(), test_map[test_case].empty());
michael@0:   ASSERT_EQ(std_map[test_case].size(), test_map[test_case].size());
michael@0: 
michael@0:   // Test Iterator.
michael@0:   IteratorTester(test_case);
michael@0: 
michael@0:   // Test lookup operations.
michael@0:   LookupTester(test_case);
michael@0: }
michael@0: 
michael@0: TEST_F(TestValidMap, Test1000RandomElements) {
michael@0:   int test_case = 3;
michael@0:   // Assert memory size allocated during serialization is correct.
michael@0:   ASSERT_EQ(correct_size[test_case], size[test_case]);
michael@0: 
michael@0:   // Sanity check of serialized data:
michael@0:   ASSERT_TRUE(test_map[test_case].ValidateInMemoryStructure());
michael@0:   ASSERT_EQ(std_map[test_case].empty(), test_map[test_case].empty());
michael@0:   ASSERT_EQ(std_map[test_case].size(), test_map[test_case].size());
michael@0: 
michael@0:   // Test Iterator.
michael@0:   IteratorTester(test_case);
michael@0: 
michael@0:   // Test lookup operations.
michael@0:   LookupTester(test_case);
michael@0: }
michael@0: 
michael@0: int main(int argc, char *argv[]) {
michael@0:   ::testing::InitGoogleTest(&argc, argv);
michael@0: 
michael@0:   return RUN_ALL_TESTS();
michael@0: }