1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/toolkit/crashreporter/google-breakpad/src/processor/static_map_unittest.cc Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,386 @@
1.4 +// Copyright (c) 2010 Google Inc.
1.5 +// All rights reserved.
1.6 +//
1.7 +// Redistribution and use in source and binary forms, with or without
1.8 +// modification, are permitted provided that the following conditions are
1.9 +// met:
1.10 +//
1.11 +// * Redistributions of source code must retain the above copyright
1.12 +// notice, this list of conditions and the following disclaimer.
1.13 +// * Redistributions in binary form must reproduce the above
1.14 +// copyright notice, this list of conditions and the following disclaimer
1.15 +// in the documentation and/or other materials provided with the
1.16 +// distribution.
1.17 +// * Neither the name of Google Inc. nor the names of its
1.18 +// contributors may be used to endorse or promote products derived from
1.19 +// this software without specific prior written permission.
1.20 +//
1.21 +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1.22 +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1.23 +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1.24 +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1.25 +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1.26 +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1.27 +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1.28 +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1.29 +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1.30 +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1.31 +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1.32 +
1.33 +// static_map_unittest.cc: Unit tests for StaticMap.
1.34 +//
1.35 +// Author: Siyang Xie (lambxsy@google.com)
1.36 +
1.37 +#include <climits>
1.38 +#include <map>
1.39 +
1.40 +#include "breakpad_googletest_includes.h"
1.41 +#include "processor/static_map-inl.h"
1.42 +
1.43 +
1.44 +typedef int ValueType;
1.45 +typedef int KeyType;
1.46 +typedef google_breakpad::StaticMap< KeyType, ValueType > TestMap;
1.47 +typedef std::map< KeyType, ValueType > StdMap;
1.48 +
1.49 +template<typename Key, typename Value>
1.50 +class SimpleMapSerializer {
1.51 + public:
1.52 + static char* Serialize(const std::map<Key, Value> &stdmap,
1.53 + unsigned int* size = NULL) {
1.54 + unsigned int size_per_node =
1.55 + sizeof(uint32_t) + sizeof(Key) + sizeof(Value);
1.56 + unsigned int memsize = sizeof(int32_t) + size_per_node * stdmap.size();
1.57 + if (size) *size = memsize;
1.58 +
1.59 + // Allocate memory for serialized data:
1.60 + char* mem = reinterpret_cast<char*>(operator new(memsize));
1.61 + char* address = mem;
1.62 +
1.63 + // Writer the number of nodes:
1.64 + new (address) uint32_t(static_cast<uint32_t>(stdmap.size()));
1.65 + address += sizeof(uint32_t);
1.66 +
1.67 + // Nodes' offset:
1.68 + uint32_t* offsets = reinterpret_cast<uint32_t*>(address);
1.69 + address += sizeof(uint32_t) * stdmap.size();
1.70 +
1.71 + // Keys:
1.72 + Key* keys = reinterpret_cast<Key*>(address);
1.73 + address += sizeof(Key) * stdmap.size();
1.74 +
1.75 + // Traversing map:
1.76 + typename std::map<Key, Value>::const_iterator iter = stdmap.begin();
1.77 + for (int index = 0; iter != stdmap.end(); ++iter, ++index) {
1.78 + offsets[index] = static_cast<unsigned int>(address - mem);
1.79 + keys[index] = iter->first;
1.80 + new (address) Value(iter->second);
1.81 + address += sizeof(Value);
1.82 + }
1.83 + return mem;
1.84 + }
1.85 +};
1.86 +
1.87 +
1.88 +class TestInvalidMap : public ::testing::Test {
1.89 + protected:
1.90 + void SetUp() {
1.91 + memset(data, 0, kMemorySize);
1.92 + }
1.93 +
1.94 + // 40 Bytes memory can hold a StaticMap with up to 3 nodes.
1.95 + static const int kMemorySize = 40;
1.96 + char data[kMemorySize];
1.97 + TestMap test_map;
1.98 +};
1.99 +
1.100 +TEST_F(TestInvalidMap, TestNegativeNumberNodes) {
1.101 + memset(data, 0xff, sizeof(uint32_t)); // Set the number of nodes = -1
1.102 + test_map = TestMap(data);
1.103 + ASSERT_FALSE(test_map.ValidateInMemoryStructure());
1.104 +}
1.105 +
1.106 +TEST_F(TestInvalidMap, TestWrongOffsets) {
1.107 + uint32_t* header = reinterpret_cast<uint32_t*>(data);
1.108 + const uint32_t kNumNodes = 2;
1.109 + const uint32_t kHeaderOffset =
1.110 + sizeof(uint32_t) + kNumNodes * (sizeof(uint32_t) + sizeof(KeyType));
1.111 +
1.112 + header[0] = kNumNodes;
1.113 + header[1] = kHeaderOffset + 3; // Wrong offset for first node
1.114 + test_map = TestMap(data);
1.115 + ASSERT_FALSE(test_map.ValidateInMemoryStructure());
1.116 +
1.117 + header[1] = kHeaderOffset; // Correct offset for first node
1.118 + header[2] = kHeaderOffset - 1; // Wrong offset for second node
1.119 + test_map = TestMap(data);
1.120 + ASSERT_FALSE(test_map.ValidateInMemoryStructure());
1.121 +}
1.122 +
1.123 +TEST_F(TestInvalidMap, TestUnSortedKeys) {
1.124 + uint32_t* header = reinterpret_cast<uint32_t*>(data);
1.125 + const uint32_t kNumNodes = 2;
1.126 + const uint32_t kHeaderOffset =
1.127 + sizeof(uint32_t) + kNumNodes * (sizeof(uint32_t) + sizeof(KeyType));
1.128 + header[0] = kNumNodes;
1.129 + header[1] = kHeaderOffset;
1.130 + header[2] = kHeaderOffset + sizeof(ValueType);
1.131 +
1.132 + KeyType* keys = reinterpret_cast<KeyType*>(
1.133 + data + (kNumNodes + 1) * sizeof(uint32_t));
1.134 + // Set keys in non-increasing order.
1.135 + keys[0] = 10;
1.136 + keys[1] = 7;
1.137 + test_map = TestMap(data);
1.138 + ASSERT_FALSE(test_map.ValidateInMemoryStructure());
1.139 +}
1.140 +
1.141 +
1.142 +class TestValidMap : public ::testing::Test {
1.143 + protected:
1.144 + void SetUp() {
1.145 + int testcase = 0;
1.146 +
1.147 + // Empty map.
1.148 + map_data[testcase] =
1.149 + serializer.Serialize(std_map[testcase], &size[testcase]);
1.150 + test_map[testcase] = TestMap(map_data[testcase]);
1.151 + ++testcase;
1.152 +
1.153 + // Single element.
1.154 + std_map[testcase].insert(std::make_pair(2, 8));
1.155 + map_data[testcase] =
1.156 + serializer.Serialize(std_map[testcase], &size[testcase]);
1.157 + test_map[testcase] = TestMap(map_data[testcase]);
1.158 + ++testcase;
1.159 +
1.160 + // 100 elements.
1.161 + for (int i = 0; i < 100; ++i)
1.162 + std_map[testcase].insert(std::make_pair(i, 2 * i));
1.163 + map_data[testcase] =
1.164 + serializer.Serialize(std_map[testcase], &size[testcase]);
1.165 + test_map[testcase] = TestMap(map_data[testcase]);
1.166 + ++testcase;
1.167 +
1.168 + // 1000 random elements.
1.169 + for (int i = 0; i < 1000; ++i)
1.170 + std_map[testcase].insert(std::make_pair(rand(), rand()));
1.171 + map_data[testcase] =
1.172 + serializer.Serialize(std_map[testcase], &size[testcase]);
1.173 + test_map[testcase] = TestMap(map_data[testcase]);
1.174 +
1.175 + // Set correct size of memory allocation for each test case.
1.176 + unsigned int size_per_node =
1.177 + sizeof(uint32_t) + sizeof(KeyType) + sizeof(ValueType);
1.178 + for (testcase = 0; testcase < kNumberTestCases; ++testcase) {
1.179 + correct_size[testcase] =
1.180 + sizeof(uint32_t) + std_map[testcase].size() * size_per_node;
1.181 + }
1.182 + }
1.183 +
1.184 + void TearDown() {
1.185 + for (int i = 0;i < kNumberTestCases; ++i)
1.186 + delete map_data[i];
1.187 + }
1.188 +
1.189 +
1.190 + void IteratorTester(int test_case) {
1.191 + // scan through:
1.192 + iter_test = test_map[test_case].begin();
1.193 + iter_std = std_map[test_case].begin();
1.194 +
1.195 + for (; iter_test != test_map[test_case].end() &&
1.196 + iter_std != std_map[test_case].end();
1.197 + ++iter_test, ++iter_std) {
1.198 + ASSERT_EQ(iter_test.GetKey(), iter_std->first);
1.199 + ASSERT_EQ(*(iter_test.GetValuePtr()), iter_std->second);
1.200 + }
1.201 + ASSERT_TRUE(iter_test == test_map[test_case].end()
1.202 + && iter_std == std_map[test_case].end());
1.203 +
1.204 + // Boundary testcase.
1.205 + if (!std_map[test_case].empty()) {
1.206 + // rear boundary case:
1.207 + iter_test = test_map[test_case].end();
1.208 + iter_std = std_map[test_case].end();
1.209 + --iter_std;
1.210 + --iter_test;
1.211 + ASSERT_EQ(iter_test.GetKey(), iter_std->first);
1.212 + ASSERT_EQ(*(iter_test.GetValuePtr()), iter_std->second);
1.213 +
1.214 + ++iter_test;
1.215 + ++iter_std;
1.216 + ASSERT_TRUE(iter_test == test_map[test_case].end());
1.217 +
1.218 + --iter_test;
1.219 + --iter_std;
1.220 + ASSERT_TRUE(iter_test != test_map[test_case].end());
1.221 + ASSERT_TRUE(iter_test == test_map[test_case].last());
1.222 + ASSERT_EQ(iter_test.GetKey(), iter_std->first);
1.223 + ASSERT_EQ(*(iter_test.GetValuePtr()), iter_std->second);
1.224 +
1.225 + // front boundary case:
1.226 + iter_test = test_map[test_case].begin();
1.227 + --iter_test;
1.228 + ASSERT_TRUE(iter_test == test_map[test_case].begin());
1.229 + }
1.230 + }
1.231 +
1.232 + void CompareLookupResult(int test_case) {
1.233 + bool found1 = (iter_test != test_map[test_case].end());
1.234 + bool found2 = (iter_std != std_map[test_case].end());
1.235 + ASSERT_EQ(found1, found2);
1.236 +
1.237 + if (found1 && found2) {
1.238 + ASSERT_EQ(iter_test.GetKey(), iter_std->first);
1.239 + ASSERT_EQ(*(iter_test.GetValuePtr()), iter_std->second);
1.240 + }
1.241 + }
1.242 +
1.243 + void FindTester(int test_case, const KeyType &key) {
1.244 + iter_test = test_map[test_case].find(key);
1.245 + iter_std = std_map[test_case].find(key);
1.246 + CompareLookupResult(test_case);
1.247 + }
1.248 +
1.249 + void LowerBoundTester(int test_case, const KeyType &key) {
1.250 + iter_test = test_map[test_case].lower_bound(key);
1.251 + iter_std = std_map[test_case].lower_bound(key);
1.252 + CompareLookupResult(test_case);
1.253 + }
1.254 +
1.255 + void UpperBoundTester(int test_case, const KeyType &key) {
1.256 + iter_test = test_map[test_case].upper_bound(key);
1.257 + iter_std = std_map[test_case].upper_bound(key);
1.258 + CompareLookupResult(test_case);
1.259 + }
1.260 +
1.261 + void LookupTester(int test_case) {
1.262 + StdMap::const_iterator iter;
1.263 + // Test find():
1.264 + for (iter = std_map[test_case].begin();
1.265 + iter != std_map[test_case].end();
1.266 + ++iter) {
1.267 + FindTester(test_case, iter->first);
1.268 + FindTester(test_case, iter->first + 1);
1.269 + FindTester(test_case, iter->first - 1);
1.270 + }
1.271 + FindTester(test_case, INT_MIN);
1.272 + FindTester(test_case, INT_MAX);
1.273 + // random test:
1.274 + for (int i = 0; i < rand()%5000 + 5000; ++i)
1.275 + FindTester(test_case, rand());
1.276 +
1.277 + // Test lower_bound():
1.278 + for (iter = std_map[test_case].begin();
1.279 + iter != std_map[test_case].end();
1.280 + ++iter) {
1.281 + LowerBoundTester(test_case, iter->first);
1.282 + LowerBoundTester(test_case, iter->first + 1);
1.283 + LowerBoundTester(test_case, iter->first - 1);
1.284 + }
1.285 + LowerBoundTester(test_case, INT_MIN);
1.286 + LowerBoundTester(test_case, INT_MAX);
1.287 + // random test:
1.288 + for (int i = 0; i < rand()%5000 + 5000; ++i)
1.289 + LowerBoundTester(test_case, rand());
1.290 +
1.291 + // Test upper_bound():
1.292 + for (iter = std_map[test_case].begin();
1.293 + iter != std_map[test_case].end();
1.294 + ++iter) {
1.295 + UpperBoundTester(test_case, iter->first);
1.296 + UpperBoundTester(test_case, iter->first + 1);
1.297 + UpperBoundTester(test_case, iter->first - 1);
1.298 + }
1.299 + UpperBoundTester(test_case, INT_MIN);
1.300 + UpperBoundTester(test_case, INT_MAX);
1.301 + // random test:
1.302 + for (int i = 0; i < rand()%5000 + 5000; ++i)
1.303 + UpperBoundTester(test_case, rand());
1.304 + }
1.305 +
1.306 + static const int kNumberTestCases = 4;
1.307 + StdMap std_map[kNumberTestCases];
1.308 + TestMap test_map[kNumberTestCases];
1.309 + TestMap::const_iterator iter_test;
1.310 + StdMap::const_iterator iter_std;
1.311 + char* map_data[kNumberTestCases];
1.312 + unsigned int size[kNumberTestCases];
1.313 + unsigned int correct_size[kNumberTestCases];
1.314 + SimpleMapSerializer<KeyType, ValueType> serializer;
1.315 +};
1.316 +
1.317 +TEST_F(TestValidMap, TestEmptyMap) {
1.318 + int test_case = 0;
1.319 + // Assert memory size allocated during serialization is correct.
1.320 + ASSERT_EQ(correct_size[test_case], size[test_case]);
1.321 +
1.322 + // Sanity check of serialized data:
1.323 + ASSERT_TRUE(test_map[test_case].ValidateInMemoryStructure());
1.324 + ASSERT_EQ(std_map[test_case].empty(), test_map[test_case].empty());
1.325 + ASSERT_EQ(std_map[test_case].size(), test_map[test_case].size());
1.326 +
1.327 + // Test Iterator.
1.328 + IteratorTester(test_case);
1.329 +
1.330 + // Test lookup operations.
1.331 + LookupTester(test_case);
1.332 +}
1.333 +
1.334 +TEST_F(TestValidMap, TestSingleElement) {
1.335 + int test_case = 1;
1.336 + // Assert memory size allocated during serialization is correct.
1.337 + ASSERT_EQ(correct_size[test_case], size[test_case]);
1.338 +
1.339 + // Sanity check of serialized data:
1.340 + ASSERT_TRUE(test_map[test_case].ValidateInMemoryStructure());
1.341 + ASSERT_EQ(std_map[test_case].empty(), test_map[test_case].empty());
1.342 + ASSERT_EQ(std_map[test_case].size(), test_map[test_case].size());
1.343 +
1.344 + // Test Iterator.
1.345 + IteratorTester(test_case);
1.346 +
1.347 + // Test lookup operations.
1.348 + LookupTester(test_case);
1.349 +}
1.350 +
1.351 +TEST_F(TestValidMap, Test100Elements) {
1.352 + int test_case = 2;
1.353 + // Assert memory size allocated during serialization is correct.
1.354 + ASSERT_EQ(correct_size[test_case], size[test_case]);
1.355 +
1.356 + // Sanity check of serialized data:
1.357 + ASSERT_TRUE(test_map[test_case].ValidateInMemoryStructure());
1.358 + ASSERT_EQ(std_map[test_case].empty(), test_map[test_case].empty());
1.359 + ASSERT_EQ(std_map[test_case].size(), test_map[test_case].size());
1.360 +
1.361 + // Test Iterator.
1.362 + IteratorTester(test_case);
1.363 +
1.364 + // Test lookup operations.
1.365 + LookupTester(test_case);
1.366 +}
1.367 +
1.368 +TEST_F(TestValidMap, Test1000RandomElements) {
1.369 + int test_case = 3;
1.370 + // Assert memory size allocated during serialization is correct.
1.371 + ASSERT_EQ(correct_size[test_case], size[test_case]);
1.372 +
1.373 + // Sanity check of serialized data:
1.374 + ASSERT_TRUE(test_map[test_case].ValidateInMemoryStructure());
1.375 + ASSERT_EQ(std_map[test_case].empty(), test_map[test_case].empty());
1.376 + ASSERT_EQ(std_map[test_case].size(), test_map[test_case].size());
1.377 +
1.378 + // Test Iterator.
1.379 + IteratorTester(test_case);
1.380 +
1.381 + // Test lookup operations.
1.382 + LookupTester(test_case);
1.383 +}
1.384 +
1.385 +int main(int argc, char *argv[]) {
1.386 + ::testing::InitGoogleTest(&argc, argv);
1.387 +
1.388 + return RUN_ALL_TESTS();
1.389 +}
