static_contained_range_map_unittest.cc
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_contained_range_map_unittest.cc: Unit tests for 30 // StaticContainedRangeMap. 31 // 32 // Author: Siyang Xie (lambxsy@google.com) 33 34 #ifdef HAVE_CONFIG_H 35 #include <config.h> // Must come first 36 #endif 37 38 #include "breakpad_googletest_includes.h" 39 #include "common/scoped_ptr.h" 40 #include "processor/contained_range_map-inl.h" 41 #include "processor/static_contained_range_map-inl.h" 42 #include "processor/simple_serializer-inl.h" 43 #include "processor/map_serializers-inl.h" 44 #include "processor/logging.h" 45 46 namespace { 47 48 typedef google_breakpad::ContainedRangeMap<unsigned int, int> CRMMap; 49 typedef google_breakpad::StaticContainedRangeMap<unsigned int, int> TestMap; 50 51 // Each element in test_data contains the expected result when calling 52 // RetrieveRange on an address. 53 const int test_data[] = { 54 0, // 0 55 0, // 1 56 0, // 2 57 0, // 3 58 0, // 4 59 0, // 5 60 0, // 6 61 0, // 7 62 9, // 8 63 7, // 9 64 1, // 10 65 5, // 11 66 6, // 12 67 6, // 13 68 6, // 14 69 6, // 15 70 6, // 16 71 6, // 17 72 6, // 18 73 5, // 19 74 7, // 20 75 8, // 21 76 0, // 22 77 0, // 23 78 0, // 24 79 0, // 25 80 0, // 26 81 0, // 27 82 0, // 28 83 0, // 29 84 10, // 30 85 10, // 31 86 10, // 32 87 11, // 33 88 11, // 34 89 11, // 35 90 0, // 36 91 0, // 37 92 0, // 38 93 0, // 39 94 14, // 40 95 14, // 41 96 14, // 42 97 14, // 43 98 15, // 44 99 15, // 45 100 15, // 46 101 15, // 47 102 0, // 48 103 0, // 49 104 19, // 50 105 18, // 51 106 18, // 52 107 18, // 53 108 18, // 54 109 18, // 55 110 18, // 56 111 18, // 57 112 18, // 58 113 20, // 59 114 21, // 60 115 25, // 61 116 26, // 62 117 26, // 63 118 26, // 64 119 26, // 65 120 26, // 66 121 26, // 67 122 24, // 68 123 22, // 69 124 30, // 70 125 30, // 71 126 30, // 72 127 30, // 73 128 31, // 74 129 31, // 75 130 30, // 76 131 32, // 77 132 32, // 78 133 30, // 79 134 34, // 80 135 35, // 81 136 36, // 82 137 39, // 83 138 38, // 84 139 37, // 85 140 43, // 86 141 44, // 87 142 41, // 88 143 45, // 89 144 42, // 90 145 0, // 91 146 0, // 92 147 0, // 93 148 0, // 94 149 0, // 95 150 0, // 96 151 0, // 97 152 0, // 98 153 0 // 99 154 }; 155 156 } // namespace 157 158 namespace google_breakpad { 159 160 class TestStaticCRMMap : public ::testing::Test { 161 protected: 162 void SetUp(); 163 164 // A referrence map for testing StaticCRMMap. 165 google_breakpad::ContainedRangeMap<unsigned int, int> crm_map_; 166 167 // Static version of crm_map using serialized data of crm_map. 168 // The goal of testing is to make sure TestMap provides same results for 169 // lookup operation(s) as CRMMap does. 170 google_breakpad::StaticContainedRangeMap<unsigned int, int> test_map_; 171 172 google_breakpad::ContainedRangeMapSerializer<unsigned int, int> serializer_; 173 174 scoped_array<char> serialized_data_; 175 }; 176 177 void TestStaticCRMMap::SetUp() { 178 // First, do the StoreRange tests. This validates the containment 179 // rules. 180 // We confirm the referrence map correctly stores data during setup. 181 ASSERT_TRUE (crm_map_.StoreRange(10, 10, 1)); 182 ASSERT_FALSE(crm_map_.StoreRange(10, 10, 2)); // exactly equal to 1 183 ASSERT_FALSE(crm_map_.StoreRange(11, 10, 3)); // begins inside 1 and extends up 184 ASSERT_FALSE(crm_map_.StoreRange( 9, 10, 4)); // begins below 1 and ends inside 185 ASSERT_TRUE (crm_map_.StoreRange(11, 9, 5)); // contained by existing 186 ASSERT_TRUE (crm_map_.StoreRange(12, 7, 6)); 187 ASSERT_TRUE (crm_map_.StoreRange( 9, 12, 7)); // contains existing 188 ASSERT_TRUE (crm_map_.StoreRange( 9, 13, 8)); 189 ASSERT_TRUE (crm_map_.StoreRange( 8, 14, 9)); 190 ASSERT_TRUE (crm_map_.StoreRange(30, 3, 10)); 191 ASSERT_TRUE (crm_map_.StoreRange(33, 3, 11)); 192 ASSERT_TRUE (crm_map_.StoreRange(30, 6, 12)); // storable but totally masked 193 ASSERT_TRUE (crm_map_.StoreRange(40, 8, 13)); // will be totally masked 194 ASSERT_TRUE (crm_map_.StoreRange(40, 4, 14)); 195 ASSERT_TRUE (crm_map_.StoreRange(44, 4, 15)); 196 ASSERT_FALSE(crm_map_.StoreRange(32, 10, 16)); // begins in #10, ends in #14 197 ASSERT_FALSE(crm_map_.StoreRange(50, 0, 17)); // zero length 198 ASSERT_TRUE (crm_map_.StoreRange(50, 10, 18)); 199 ASSERT_TRUE (crm_map_.StoreRange(50, 1, 19)); 200 ASSERT_TRUE (crm_map_.StoreRange(59, 1, 20)); 201 ASSERT_TRUE (crm_map_.StoreRange(60, 1, 21)); 202 ASSERT_TRUE (crm_map_.StoreRange(69, 1, 22)); 203 ASSERT_TRUE (crm_map_.StoreRange(60, 10, 23)); 204 ASSERT_TRUE (crm_map_.StoreRange(68, 1, 24)); 205 ASSERT_TRUE (crm_map_.StoreRange(61, 1, 25)); 206 ASSERT_TRUE (crm_map_.StoreRange(61, 8, 26)); 207 ASSERT_FALSE(crm_map_.StoreRange(59, 9, 27)); 208 ASSERT_FALSE(crm_map_.StoreRange(59, 10, 28)); 209 ASSERT_FALSE(crm_map_.StoreRange(59, 11, 29)); 210 ASSERT_TRUE (crm_map_.StoreRange(70, 10, 30)); 211 ASSERT_TRUE (crm_map_.StoreRange(74, 2, 31)); 212 ASSERT_TRUE (crm_map_.StoreRange(77, 2, 32)); 213 ASSERT_FALSE(crm_map_.StoreRange(72, 6, 33)); 214 ASSERT_TRUE (crm_map_.StoreRange(80, 3, 34)); 215 ASSERT_TRUE (crm_map_.StoreRange(81, 1, 35)); 216 ASSERT_TRUE (crm_map_.StoreRange(82, 1, 36)); 217 ASSERT_TRUE (crm_map_.StoreRange(83, 3, 37)); 218 ASSERT_TRUE (crm_map_.StoreRange(84, 1, 38)); 219 ASSERT_TRUE (crm_map_.StoreRange(83, 1, 39)); 220 ASSERT_TRUE (crm_map_.StoreRange(86, 5, 40)); 221 ASSERT_TRUE (crm_map_.StoreRange(88, 1, 41)); 222 ASSERT_TRUE (crm_map_.StoreRange(90, 1, 42)); 223 ASSERT_TRUE (crm_map_.StoreRange(86, 1, 43)); 224 ASSERT_TRUE (crm_map_.StoreRange(87, 1, 44)); 225 ASSERT_TRUE (crm_map_.StoreRange(89, 1, 45)); 226 ASSERT_TRUE (crm_map_.StoreRange(87, 4, 46)); 227 ASSERT_TRUE (crm_map_.StoreRange(87, 3, 47)); 228 ASSERT_FALSE(crm_map_.StoreRange(86, 2, 48)); 229 230 // Serialize crm_map to generate serialized data. 231 unsigned int size; 232 serialized_data_.reset(serializer_.Serialize(&crm_map_, &size)); 233 BPLOG(INFO) << "Serialized data size: " << size << " Bytes."; 234 235 // Construct test_map_ from serialized data. 236 test_map_ = TestMap(serialized_data_.get()); 237 } 238 239 TEST_F(TestStaticCRMMap, TestEmptyMap) { 240 CRMMap empty_crm_map; 241 242 unsigned int size; 243 scoped_array<char> serialized_data; 244 serialized_data.reset(serializer_.Serialize(&empty_crm_map, &size)); 245 scoped_ptr<TestMap> test_map(new TestMap(serialized_data.get())); 246 247 const unsigned int kCorrectSizeForEmptyMap = 16; 248 ASSERT_EQ(kCorrectSizeForEmptyMap, size); 249 250 const int *entry_test; 251 ASSERT_FALSE(test_map->RetrieveRange(-1, entry_test)); 252 ASSERT_FALSE(test_map->RetrieveRange(0, entry_test)); 253 ASSERT_FALSE(test_map->RetrieveRange(10, entry_test)); 254 } 255 256 TEST_F(TestStaticCRMMap, TestSingleElementMap) { 257 CRMMap crm_map; 258 // Test on one element: 259 int entry = 1; 260 crm_map.StoreRange(10, 10, entry); 261 262 unsigned int size; 263 scoped_array<char> serialized_data; 264 serialized_data.reset(serializer_.Serialize(&crm_map, &size)); 265 scoped_ptr<TestMap> test_map(new TestMap(serialized_data.get())); 266 267 const unsigned int kCorrectSizeForSingleElementMap = 40; 268 ASSERT_EQ(kCorrectSizeForSingleElementMap, size); 269 270 const int *entry_test; 271 ASSERT_FALSE(test_map->RetrieveRange(-1, entry_test)); 272 ASSERT_FALSE(test_map->RetrieveRange(0, entry_test)); 273 ASSERT_TRUE(test_map->RetrieveRange(10, entry_test)); 274 ASSERT_EQ(*entry_test, entry); 275 ASSERT_TRUE(test_map->RetrieveRange(13, entry_test)); 276 ASSERT_EQ(*entry_test, entry); 277 } 278 279 TEST_F(TestStaticCRMMap, TestRetrieveRangeEntries) { 280 CRMMap crm_map; 281 282 crm_map.StoreRange(2, 5, 0); 283 crm_map.StoreRange(2, 6, 1); 284 crm_map.StoreRange(2, 7, 2); 285 286 unsigned int size; 287 scoped_array<char> serialized_data; 288 serialized_data.reset(serializer_.Serialize(&crm_map, &size)); 289 scoped_ptr<TestMap> test_map(new TestMap(serialized_data.get())); 290 291 std::vector<const int*> entry_tests; 292 ASSERT_TRUE(test_map->RetrieveRanges(3, entry_tests)); 293 ASSERT_EQ(*entry_tests[0], 0); 294 ASSERT_EQ(*entry_tests[1], 1); 295 ASSERT_EQ(*entry_tests[2], 2); 296 } 297 298 TEST_F(TestStaticCRMMap, RunTestData) { 299 unsigned int test_high = sizeof(test_data) / sizeof(test_data[0]); 300 301 // Now, do the RetrieveRange tests. This further validates that the 302 // objects were stored properly and that retrieval returns the correct 303 // object. 304 // If GENERATE_TEST_DATA is defined, instead of the retrieval tests, a 305 // new test_data array will be printed. Exercise caution when doing this. 306 // Be sure to verify the results manually! 307 #ifdef GENERATE_TEST_DATA 308 printf(" const int test_data[] = {\n"); 309 #endif // GENERATE_TEST_DATA 310 311 for (unsigned int address = 0; address < test_high; ++address) { 312 const int *entryptr; 313 int value = 0; 314 if (test_map_.RetrieveRange(address, entryptr)) 315 value = *entryptr; 316 317 #ifndef GENERATE_TEST_DATA 318 // Don't use ASSERT inside the loop because it won't show the failed 319 // |address|, and the line number will always be the same. That makes 320 // it difficult to figure out which test failed. 321 EXPECT_EQ(value, test_data[address]) << "FAIL: retrieve address " 322 << address; 323 #else // !GENERATE_TEST_DATA 324 printf(" %d%c%s // %d\n", value, 325 address == test_high - 1 ? ' ' : ',', 326 value < 10 ? " " : "", 327 address); 328 #endif // !GENERATE_TEST_DATA 329 } 330 331 #ifdef GENERATE_TEST_DATA 332 printf(" };\n"); 333 #endif // GENERATE_TEST_DATA 334 } 335 336 } // namespace google_breakpad 337 338 int main(int argc, char *argv[]) { 339 ::testing::InitGoogleTest(&argc, argv); 340 341 return RUN_ALL_TESTS(); 342 }