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 (at) 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 41 typedef int ValueType; 42 typedef int KeyType; 43 typedef google_breakpad::StaticMap< KeyType, ValueType > TestMap; 44 typedef std::map< KeyType, ValueType > StdMap; 45 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; 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 85 class 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 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 } 102 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)); 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 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); 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 139 class 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 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]); 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 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]); 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 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]); 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 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]); 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 382 int main(int argc, char *argv[]) { 383 ::testing::InitGoogleTest(&argc, argv); 384 385 return RUN_ALL_TESTS(); 386 } 387
