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