183e085b7a331c96237cf8e814f97b3ef4c36a70fjimblandy// Copyright (c) 2010 Google Inc. 27daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// All rights reserved. 33261e8b6eac44a41341f112821482bee6c940c98mmentovai// 47daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// Redistribution and use in source and binary forms, with or without 57daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// modification, are permitted provided that the following conditions are 67daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// met: 73261e8b6eac44a41341f112821482bee6c940c98mmentovai// 87daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// * Redistributions of source code must retain the above copyright 97daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// notice, this list of conditions and the following disclaimer. 107daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// * Redistributions in binary form must reproduce the above 117daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// copyright notice, this list of conditions and the following disclaimer 127daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// in the documentation and/or other materials provided with the 137daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// distribution. 147daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// * Neither the name of Google Inc. nor the names of its 157daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// contributors may be used to endorse or promote products derived from 167daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// this software without specific prior written permission. 173261e8b6eac44a41341f112821482bee6c940c98mmentovai// 187daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 197daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 207daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 217daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 227daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 237daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 247daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 257daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 267daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 277daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 287daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 293261e8b6eac44a41341f112821482bee6c940c98mmentovai 303261e8b6eac44a41341f112821482bee6c940c98mmentovai// range_map_unittest.cc: Unit tests for RangeMap 313261e8b6eac44a41341f112821482bee6c940c98mmentovai// 323261e8b6eac44a41341f112821482bee6c940c98mmentovai// Author: Mark Mentovai 333261e8b6eac44a41341f112821482bee6c940c98mmentovai 343261e8b6eac44a41341f112821482bee6c940c98mmentovai 35e1930985430ce289f4fe8525f51050e5d78cc44eted.mielczarek#include <limits.h> 36e1930985430ce289f4fe8525f51050e5d78cc44eted.mielczarek#include <stdio.h> 373261e8b6eac44a41341f112821482bee6c940c98mmentovai 388c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai#include "processor/range_map-inl.h" 3980e98391dc7ff361355e72c24c0fb222518bcdfcmmentovai 402cc15ba4327831f917ff55b87e6d5fc3c7750085ted.mielczarek@gmail.com#include "common/scoped_ptr.h" 4180e98391dc7ff361355e72c24c0fb222518bcdfcmmentovai#include "processor/linked_ptr.h" 4232b802dba3d49880a0414d066e71cdc20ab09901mmentovai#include "processor/logging.h" 433261e8b6eac44a41341f112821482bee6c940c98mmentovai 448647dde8cc03ef16b565dccc75574ee5f0d9cf72mmentovainamespace { 458647dde8cc03ef16b565dccc75574ee5f0d9cf72mmentovai 468647dde8cc03ef16b565dccc75574ee5f0d9cf72mmentovai 47e5dc60822e5938fea2ae892ccddb906641ba174emmentovaiusing google_breakpad::linked_ptr; 48e5dc60822e5938fea2ae892ccddb906641ba174emmentovaiusing google_breakpad::scoped_ptr; 49e5dc60822e5938fea2ae892ccddb906641ba174emmentovaiusing google_breakpad::RangeMap; 503261e8b6eac44a41341f112821482bee6c940c98mmentovai 513261e8b6eac44a41341f112821482bee6c940c98mmentovai 523261e8b6eac44a41341f112821482bee6c940c98mmentovai// A CountedObject holds an int. A global (not thread safe!) count of 533261e8b6eac44a41341f112821482bee6c940c98mmentovai// allocated CountedObjects is maintained to help test memory management. 543261e8b6eac44a41341f112821482bee6c940c98mmentovaiclass CountedObject { 5553d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai public: 56d9fb68c3e02166565fc75b0635519b42fd061982mmentovai explicit CountedObject(int id) : id_(id) { ++count_; } 5753d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai ~CountedObject() { --count_; } 583261e8b6eac44a41341f112821482bee6c940c98mmentovai 5953d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai static int count() { return count_; } 6053d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai int id() const { return id_; } 613261e8b6eac44a41341f112821482bee6c940c98mmentovai 6253d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai private: 6353d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai static int count_; 64d9fb68c3e02166565fc75b0635519b42fd061982mmentovai int id_; 653261e8b6eac44a41341f112821482bee6c940c98mmentovai}; 663261e8b6eac44a41341f112821482bee6c940c98mmentovai 673261e8b6eac44a41341f112821482bee6c940c98mmentovaiint CountedObject::count_; 683261e8b6eac44a41341f112821482bee6c940c98mmentovai 693261e8b6eac44a41341f112821482bee6c940c98mmentovai 703261e8b6eac44a41341f112821482bee6c940c98mmentovaitypedef int AddressType; 712fc823f5794737391e231c1dce6c2b0793213e53mmentovaitypedef RangeMap< AddressType, linked_ptr<CountedObject> > TestMap; 723261e8b6eac44a41341f112821482bee6c940c98mmentovai 733261e8b6eac44a41341f112821482bee6c940c98mmentovai 743261e8b6eac44a41341f112821482bee6c940c98mmentovai// RangeTest contains data to use for store and retrieve tests. See 753261e8b6eac44a41341f112821482bee6c940c98mmentovai// RunTests for descriptions of the tests. 763261e8b6eac44a41341f112821482bee6c940c98mmentovaistruct RangeTest { 773261e8b6eac44a41341f112821482bee6c940c98mmentovai // Base address to use for test 783261e8b6eac44a41341f112821482bee6c940c98mmentovai AddressType address; 793261e8b6eac44a41341f112821482bee6c940c98mmentovai 803261e8b6eac44a41341f112821482bee6c940c98mmentovai // Size of range to use for test 813261e8b6eac44a41341f112821482bee6c940c98mmentovai AddressType size; 823261e8b6eac44a41341f112821482bee6c940c98mmentovai 833261e8b6eac44a41341f112821482bee6c940c98mmentovai // Unique ID of range - unstorable ranges must have unique IDs too 84d9fb68c3e02166565fc75b0635519b42fd061982mmentovai int id; 853261e8b6eac44a41341f112821482bee6c940c98mmentovai 863261e8b6eac44a41341f112821482bee6c940c98mmentovai // Whether this range is expected to be stored successfully or not 87d9fb68c3e02166565fc75b0635519b42fd061982mmentovai bool expect_storable; 883261e8b6eac44a41341f112821482bee6c940c98mmentovai}; 893261e8b6eac44a41341f112821482bee6c940c98mmentovai 903261e8b6eac44a41341f112821482bee6c940c98mmentovai 913261e8b6eac44a41341f112821482bee6c940c98mmentovai// A RangeTestSet encompasses multiple RangeTests, which are run in 923261e8b6eac44a41341f112821482bee6c940c98mmentovai// sequence on the same RangeMap. 933261e8b6eac44a41341f112821482bee6c940c98mmentovaistruct RangeTestSet { 943261e8b6eac44a41341f112821482bee6c940c98mmentovai // An array of RangeTests 95d9fb68c3e02166565fc75b0635519b42fd061982mmentovai const RangeTest *range_tests; 963261e8b6eac44a41341f112821482bee6c940c98mmentovai 973261e8b6eac44a41341f112821482bee6c940c98mmentovai // The number of tests in the set 98d9fb68c3e02166565fc75b0635519b42fd061982mmentovai unsigned int range_test_count; 993261e8b6eac44a41341f112821482bee6c940c98mmentovai}; 1003261e8b6eac44a41341f112821482bee6c940c98mmentovai 1013261e8b6eac44a41341f112821482bee6c940c98mmentovai 1023261e8b6eac44a41341f112821482bee6c940c98mmentovai// StoreTest uses the data in a RangeTest and calls StoreRange on the 1033261e8b6eac44a41341f112821482bee6c940c98mmentovai// test RangeMap. It returns true if the expected result occurred, and 1043261e8b6eac44a41341f112821482bee6c940c98mmentovai// false if something else happened. 1058647dde8cc03ef16b565dccc75574ee5f0d9cf72mmentovaistatic bool StoreTest(TestMap *range_map, const RangeTest *range_test) { 1062fc823f5794737391e231c1dce6c2b0793213e53mmentovai linked_ptr<CountedObject> object(new CountedObject(range_test->id)); 1073261e8b6eac44a41341f112821482bee6c940c98mmentovai bool stored = range_map->StoreRange(range_test->address, 1083261e8b6eac44a41341f112821482bee6c940c98mmentovai range_test->size, 1093261e8b6eac44a41341f112821482bee6c940c98mmentovai object); 1103261e8b6eac44a41341f112821482bee6c940c98mmentovai 1113261e8b6eac44a41341f112821482bee6c940c98mmentovai if (stored != range_test->expect_storable) { 1123261e8b6eac44a41341f112821482bee6c940c98mmentovai fprintf(stderr, "FAILED: " 1133261e8b6eac44a41341f112821482bee6c940c98mmentovai "StoreRange id %d, expected %s, observed %s\n", 1143261e8b6eac44a41341f112821482bee6c940c98mmentovai range_test->id, 1153261e8b6eac44a41341f112821482bee6c940c98mmentovai range_test->expect_storable ? "storable" : "not storable", 1163261e8b6eac44a41341f112821482bee6c940c98mmentovai stored ? "stored" : "not stored"); 1173261e8b6eac44a41341f112821482bee6c940c98mmentovai return false; 1183261e8b6eac44a41341f112821482bee6c940c98mmentovai } 1193261e8b6eac44a41341f112821482bee6c940c98mmentovai 1203261e8b6eac44a41341f112821482bee6c940c98mmentovai return true; 1213261e8b6eac44a41341f112821482bee6c940c98mmentovai} 1223261e8b6eac44a41341f112821482bee6c940c98mmentovai 1233261e8b6eac44a41341f112821482bee6c940c98mmentovai 1243261e8b6eac44a41341f112821482bee6c940c98mmentovai// RetrieveTest uses the data in RangeTest and calls RetrieveRange on the 1253261e8b6eac44a41341f112821482bee6c940c98mmentovai// test RangeMap. If it retrieves the expected value (which can be no 1263261e8b6eac44a41341f112821482bee6c940c98mmentovai// map entry at the specified range,) it returns true, otherwise, it returns 1273261e8b6eac44a41341f112821482bee6c940c98mmentovai// false. RetrieveTest will check the values around the base address and 1283261e8b6eac44a41341f112821482bee6c940c98mmentovai// the high address of a range to guard against off-by-one errors. 1298647dde8cc03ef16b565dccc75574ee5f0d9cf72mmentovaistatic bool RetrieveTest(TestMap *range_map, const RangeTest *range_test) { 1303261e8b6eac44a41341f112821482bee6c940c98mmentovai for (unsigned int side = 0; side <= 1; ++side) { 1313261e8b6eac44a41341f112821482bee6c940c98mmentovai // When side == 0, check the low side (base address) of each range. 1323261e8b6eac44a41341f112821482bee6c940c98mmentovai // When side == 1, check the high side (base + size) of each range. 1333261e8b6eac44a41341f112821482bee6c940c98mmentovai 1343261e8b6eac44a41341f112821482bee6c940c98mmentovai // Check one-less and one-greater than the target address in addition 1353261e8b6eac44a41341f112821482bee6c940c98mmentovai // to the target address itself. 1363261e8b6eac44a41341f112821482bee6c940c98mmentovai 1373261e8b6eac44a41341f112821482bee6c940c98mmentovai // If the size of the range is only 1, don't check one greater than 1383261e8b6eac44a41341f112821482bee6c940c98mmentovai // the base or one less than the high - for a successfully stored 1393261e8b6eac44a41341f112821482bee6c940c98mmentovai // range, these tests would erroneously fail because the range is too 1403261e8b6eac44a41341f112821482bee6c940c98mmentovai // small. 1413261e8b6eac44a41341f112821482bee6c940c98mmentovai AddressType low_offset = -1; 1423261e8b6eac44a41341f112821482bee6c940c98mmentovai AddressType high_offset = 1; 1433261e8b6eac44a41341f112821482bee6c940c98mmentovai if (range_test->size == 1) { 144d9fb68c3e02166565fc75b0635519b42fd061982mmentovai if (!side) // When checking the low side, 145d9fb68c3e02166565fc75b0635519b42fd061982mmentovai high_offset = 0; // don't check one over the target. 146d9fb68c3e02166565fc75b0635519b42fd061982mmentovai else // When checking the high side, 147d9fb68c3e02166565fc75b0635519b42fd061982mmentovai low_offset = 0; // don't check one under the target. 1483261e8b6eac44a41341f112821482bee6c940c98mmentovai } 1493261e8b6eac44a41341f112821482bee6c940c98mmentovai 1503261e8b6eac44a41341f112821482bee6c940c98mmentovai for (AddressType offset = low_offset; offset <= high_offset; ++offset) { 1513261e8b6eac44a41341f112821482bee6c940c98mmentovai AddressType address = 1523261e8b6eac44a41341f112821482bee6c940c98mmentovai offset + 1533261e8b6eac44a41341f112821482bee6c940c98mmentovai (!side ? range_test->address : 1543261e8b6eac44a41341f112821482bee6c940c98mmentovai range_test->address + range_test->size - 1); 1553261e8b6eac44a41341f112821482bee6c940c98mmentovai 156d9fb68c3e02166565fc75b0635519b42fd061982mmentovai bool expected_result = false; // This is correct for tests not stored. 1573261e8b6eac44a41341f112821482bee6c940c98mmentovai if (range_test->expect_storable) { 158d9fb68c3e02166565fc75b0635519b42fd061982mmentovai if (offset == 0) // When checking the target address, 159d9fb68c3e02166565fc75b0635519b42fd061982mmentovai expected_result = true; // test should always succeed. 160d9fb68c3e02166565fc75b0635519b42fd061982mmentovai else if (offset == -1) // When checking one below the target, 161d9fb68c3e02166565fc75b0635519b42fd061982mmentovai expected_result = side; // should fail low and succeed high. 162d9fb68c3e02166565fc75b0635519b42fd061982mmentovai else // When checking one above the target, 163d9fb68c3e02166565fc75b0635519b42fd061982mmentovai expected_result = !side; // should succeed low and fail high. 1643261e8b6eac44a41341f112821482bee6c940c98mmentovai } 1653261e8b6eac44a41341f112821482bee6c940c98mmentovai 1662fc823f5794737391e231c1dce6c2b0793213e53mmentovai linked_ptr<CountedObject> object; 167df9901a45dac4b5162943f631168296f9d05ee20jessicag.feedback@gmail.com AddressType retrieved_base = AddressType(); 168df9901a45dac4b5162943f631168296f9d05ee20jessicag.feedback@gmail.com AddressType retrieved_size = AddressType(); 1692fc823f5794737391e231c1dce6c2b0793213e53mmentovai bool retrieved = range_map->RetrieveRange(address, &object, 1702fc823f5794737391e231c1dce6c2b0793213e53mmentovai &retrieved_base, 1712fc823f5794737391e231c1dce6c2b0793213e53mmentovai &retrieved_size); 1723261e8b6eac44a41341f112821482bee6c940c98mmentovai 1732fc823f5794737391e231c1dce6c2b0793213e53mmentovai bool observed_result = retrieved && object->id() == range_test->id; 1743261e8b6eac44a41341f112821482bee6c940c98mmentovai 175d9fb68c3e02166565fc75b0635519b42fd061982mmentovai if (observed_result != expected_result) { 1763261e8b6eac44a41341f112821482bee6c940c98mmentovai fprintf(stderr, "FAILED: " 1773261e8b6eac44a41341f112821482bee6c940c98mmentovai "RetrieveRange id %d, side %d, offset %d, " 1783261e8b6eac44a41341f112821482bee6c940c98mmentovai "expected %s, observed %s\n", 1793261e8b6eac44a41341f112821482bee6c940c98mmentovai range_test->id, 1803261e8b6eac44a41341f112821482bee6c940c98mmentovai side, 1813261e8b6eac44a41341f112821482bee6c940c98mmentovai offset, 1823261e8b6eac44a41341f112821482bee6c940c98mmentovai expected_result ? "true" : "false", 1833261e8b6eac44a41341f112821482bee6c940c98mmentovai observed_result ? "true" : "false"); 1843261e8b6eac44a41341f112821482bee6c940c98mmentovai return false; 1853261e8b6eac44a41341f112821482bee6c940c98mmentovai } 1862fc823f5794737391e231c1dce6c2b0793213e53mmentovai 1872fc823f5794737391e231c1dce6c2b0793213e53mmentovai // If a range was successfully retrieved, check that the returned 1882fc823f5794737391e231c1dce6c2b0793213e53mmentovai // bounds match the range as stored. 1892fc823f5794737391e231c1dce6c2b0793213e53mmentovai if (observed_result == true && 1902fc823f5794737391e231c1dce6c2b0793213e53mmentovai (retrieved_base != range_test->address || 1912fc823f5794737391e231c1dce6c2b0793213e53mmentovai retrieved_size != range_test->size)) { 1922fc823f5794737391e231c1dce6c2b0793213e53mmentovai fprintf(stderr, "FAILED: " 1932fc823f5794737391e231c1dce6c2b0793213e53mmentovai "RetrieveRange id %d, side %d, offset %d, " 1942fc823f5794737391e231c1dce6c2b0793213e53mmentovai "expected base/size %d/%d, observed %d/%d\n", 1952fc823f5794737391e231c1dce6c2b0793213e53mmentovai range_test->id, 1962fc823f5794737391e231c1dce6c2b0793213e53mmentovai side, 1972fc823f5794737391e231c1dce6c2b0793213e53mmentovai offset, 1982fc823f5794737391e231c1dce6c2b0793213e53mmentovai range_test->address, range_test->size, 1992fc823f5794737391e231c1dce6c2b0793213e53mmentovai retrieved_base, retrieved_size); 2002fc823f5794737391e231c1dce6c2b0793213e53mmentovai return false; 2012fc823f5794737391e231c1dce6c2b0793213e53mmentovai } 2022fc823f5794737391e231c1dce6c2b0793213e53mmentovai 2032fc823f5794737391e231c1dce6c2b0793213e53mmentovai // Now, check RetrieveNearestRange. The nearest range is always 2042fc823f5794737391e231c1dce6c2b0793213e53mmentovai // expected to be different from the test range when checking one 2052fc823f5794737391e231c1dce6c2b0793213e53mmentovai // less than the low side. 2062fc823f5794737391e231c1dce6c2b0793213e53mmentovai bool expected_nearest = range_test->expect_storable; 2072fc823f5794737391e231c1dce6c2b0793213e53mmentovai if (!side && offset < 0) 2082fc823f5794737391e231c1dce6c2b0793213e53mmentovai expected_nearest = false; 2092fc823f5794737391e231c1dce6c2b0793213e53mmentovai 2102fc823f5794737391e231c1dce6c2b0793213e53mmentovai linked_ptr<CountedObject> nearest_object; 211df9901a45dac4b5162943f631168296f9d05ee20jessicag.feedback@gmail.com AddressType nearest_base = AddressType(); 212df9901a45dac4b5162943f631168296f9d05ee20jessicag.feedback@gmail.com AddressType nearest_size = AddressType(); 2132fc823f5794737391e231c1dce6c2b0793213e53mmentovai bool retrieved_nearest = range_map->RetrieveNearestRange(address, 2142fc823f5794737391e231c1dce6c2b0793213e53mmentovai &nearest_object, 2152fc823f5794737391e231c1dce6c2b0793213e53mmentovai &nearest_base, 21697f1da43aecf3298541ffee69db4eaa76e104f14jimblandy &nearest_size); 2172fc823f5794737391e231c1dce6c2b0793213e53mmentovai 2182fc823f5794737391e231c1dce6c2b0793213e53mmentovai // When checking one greater than the high side, RetrieveNearestRange 2192fc823f5794737391e231c1dce6c2b0793213e53mmentovai // should usually return the test range. When a different range begins 2202fc823f5794737391e231c1dce6c2b0793213e53mmentovai // at that address, though, then RetrieveNearestRange should return the 2212fc823f5794737391e231c1dce6c2b0793213e53mmentovai // range at the address instead of the test range. 2222fc823f5794737391e231c1dce6c2b0793213e53mmentovai if (side && offset > 0 && nearest_base == address) { 2232fc823f5794737391e231c1dce6c2b0793213e53mmentovai expected_nearest = false; 2242fc823f5794737391e231c1dce6c2b0793213e53mmentovai } 2252fc823f5794737391e231c1dce6c2b0793213e53mmentovai 2262fc823f5794737391e231c1dce6c2b0793213e53mmentovai bool observed_nearest = retrieved_nearest && 2272fc823f5794737391e231c1dce6c2b0793213e53mmentovai nearest_object->id() == range_test->id; 2282fc823f5794737391e231c1dce6c2b0793213e53mmentovai 2292fc823f5794737391e231c1dce6c2b0793213e53mmentovai if (observed_nearest != expected_nearest) { 2302fc823f5794737391e231c1dce6c2b0793213e53mmentovai fprintf(stderr, "FAILED: " 2312fc823f5794737391e231c1dce6c2b0793213e53mmentovai "RetrieveNearestRange id %d, side %d, offset %d, " 2322fc823f5794737391e231c1dce6c2b0793213e53mmentovai "expected %s, observed %s\n", 2332fc823f5794737391e231c1dce6c2b0793213e53mmentovai range_test->id, 2342fc823f5794737391e231c1dce6c2b0793213e53mmentovai side, 2352fc823f5794737391e231c1dce6c2b0793213e53mmentovai offset, 2362fc823f5794737391e231c1dce6c2b0793213e53mmentovai expected_nearest ? "true" : "false", 2372fc823f5794737391e231c1dce6c2b0793213e53mmentovai observed_nearest ? "true" : "false"); 2382fc823f5794737391e231c1dce6c2b0793213e53mmentovai return false; 2392fc823f5794737391e231c1dce6c2b0793213e53mmentovai } 24097f1da43aecf3298541ffee69db4eaa76e104f14jimblandy 24197f1da43aecf3298541ffee69db4eaa76e104f14jimblandy // If a range was successfully retrieved, check that the returned 24297f1da43aecf3298541ffee69db4eaa76e104f14jimblandy // bounds match the range as stored. 24397f1da43aecf3298541ffee69db4eaa76e104f14jimblandy if (expected_nearest && 24497f1da43aecf3298541ffee69db4eaa76e104f14jimblandy (nearest_base != range_test->address || 24597f1da43aecf3298541ffee69db4eaa76e104f14jimblandy nearest_size != range_test->size)) { 24697f1da43aecf3298541ffee69db4eaa76e104f14jimblandy fprintf(stderr, "FAILED: " 24797f1da43aecf3298541ffee69db4eaa76e104f14jimblandy "RetrieveNearestRange id %d, side %d, offset %d, " 24897f1da43aecf3298541ffee69db4eaa76e104f14jimblandy "expected base/size %d/%d, observed %d/%d\n", 24997f1da43aecf3298541ffee69db4eaa76e104f14jimblandy range_test->id, 25097f1da43aecf3298541ffee69db4eaa76e104f14jimblandy side, 25197f1da43aecf3298541ffee69db4eaa76e104f14jimblandy offset, 25297f1da43aecf3298541ffee69db4eaa76e104f14jimblandy range_test->address, range_test->size, 25397f1da43aecf3298541ffee69db4eaa76e104f14jimblandy nearest_base, nearest_size); 25497f1da43aecf3298541ffee69db4eaa76e104f14jimblandy return false; 25597f1da43aecf3298541ffee69db4eaa76e104f14jimblandy } 2563261e8b6eac44a41341f112821482bee6c940c98mmentovai } 2573261e8b6eac44a41341f112821482bee6c940c98mmentovai } 2583261e8b6eac44a41341f112821482bee6c940c98mmentovai 2593261e8b6eac44a41341f112821482bee6c940c98mmentovai return true; 2603261e8b6eac44a41341f112821482bee6c940c98mmentovai} 2613261e8b6eac44a41341f112821482bee6c940c98mmentovai 2623261e8b6eac44a41341f112821482bee6c940c98mmentovai 263db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai// Test RetrieveRangeAtIndex, which is supposed to return objects in order 264db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai// according to their addresses. This test is performed by looping through 265db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai// the map, calling RetrieveRangeAtIndex for all possible indices in sequence, 266db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai// and verifying that each call returns a different object than the previous 267db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai// call, and that ranges are returned with increasing base addresses. Returns 268db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai// false if the test fails. 269db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovaistatic bool RetrieveIndexTest(TestMap *range_map, int set) { 270db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai linked_ptr<CountedObject> object; 271db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai CountedObject *last_object = NULL; 272db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai AddressType last_base = 0; 273db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai 274db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai int object_count = range_map->GetCount(); 275db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai for (int object_index = 0; object_index < object_count; ++object_index) { 276db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai AddressType base; 277db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai if (!range_map->RetrieveRangeAtIndex(object_index, &object, &base, NULL)) { 278db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai fprintf(stderr, "FAILED: RetrieveRangeAtIndex set %d index %d, " 279db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai "expected success, observed failure\n", 280db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai set, object_index); 281db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai return false; 282db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai } 283db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai 284db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai if (!object.get()) { 285db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai fprintf(stderr, "FAILED: RetrieveRangeAtIndex set %d index %d, " 286db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai "expected object, observed NULL\n", 287db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai set, object_index); 288db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai return false; 289db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai } 290db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai 291db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai // It's impossible to do these comparisons unless there's a previous 292db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai // object to compare against. 293db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai if (last_object) { 294db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai // The object must be different from the last one. 295db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai if (object->id() == last_object->id()) { 296db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai fprintf(stderr, "FAILED: RetrieveRangeAtIndex set %d index %d, " 297db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai "expected different objects, observed same objects (%d)\n", 298db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai set, object_index, object->id()); 299db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai return false; 300db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai } 301db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai 302db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai // Each object must have a base greater than the previous object's base. 303db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai if (base <= last_base) { 304db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai fprintf(stderr, "FAILED: RetrieveRangeAtIndex set %d index %d, " 305db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai "expected different bases, observed same bases (%d)\n", 306db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai set, object_index, base); 307db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai return false; 308db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai } 309db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai } 310db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai 311db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai last_object = object.get(); 312db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai last_base = base; 313db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai } 314db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai 315db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai // Make sure that RetrieveRangeAtIndex doesn't allow lookups at indices that 316db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai // are too high. 317db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai if (range_map->RetrieveRangeAtIndex(object_count, &object, NULL, NULL)) { 318db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai fprintf(stderr, "FAILED: RetrieveRangeAtIndex set %d index %d (too large), " 319db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai "expected failure, observed success\n", 320db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai set, object_count); 321db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai return false; 322db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai } 323db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai 324db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai return true; 325db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai} 326db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai 327b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com// Additional RetriveAtIndex test to expose the bug in RetrieveRangeAtIndex(). 328b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com// Bug info: RetrieveRangeAtIndex() previously retrieves the high address of 329b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com// entry, however, it is supposed to retrieve the base address of entry as 330b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com// stated in the comment in range_map.h. 331b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.comstatic bool RetriveAtIndexTest2() { 332b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com scoped_ptr<TestMap> range_map(new TestMap()); 333b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com 334b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com // Store ranges with base address = 2 * object_id: 335b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com const int range_size = 2; 336b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com for (int object_id = 0; object_id < 100; ++object_id) { 337b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com linked_ptr<CountedObject> object(new CountedObject(object_id)); 338b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com int base_address = 2 * object_id; 339b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com range_map->StoreRange(base_address, range_size, object); 340b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com } 341b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com 342b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com linked_ptr<CountedObject> object; 343b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com int object_count = range_map->GetCount(); 344b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com for (int object_index = 0; object_index < object_count; ++object_index) { 345b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com AddressType base; 346b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com if (!range_map->RetrieveRangeAtIndex(object_index, &object, &base, NULL)) { 347b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com fprintf(stderr, "FAILED: RetrieveAtIndexTest2 index %d, " 348b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com "expected success, observed failure\n", object_index); 349b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com return false; 350b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com } 351b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com 352b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com int expected_base = 2 * object->id(); 353b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com if (base != expected_base) { 354b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com fprintf(stderr, "FAILED: RetriveAtIndexTest2 index %d, " 355b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com "expected base %d, observed base %d", 356b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com object_index, expected_base, base); 357b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com return false; 358b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com } 359b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com } 360b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com 361b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com return true; 362b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com} 363b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com 364db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai 3653261e8b6eac44a41341f112821482bee6c940c98mmentovai// RunTests runs a series of test sets. 3668647dde8cc03ef16b565dccc75574ee5f0d9cf72mmentovaistatic bool RunTests() { 3673261e8b6eac44a41341f112821482bee6c940c98mmentovai // These tests will be run sequentially. The first set of tests exercises 3683261e8b6eac44a41341f112821482bee6c940c98mmentovai // most functions of RangeTest, and verifies all of the bounds-checking. 3693261e8b6eac44a41341f112821482bee6c940c98mmentovai const RangeTest range_tests_0[] = { 3703261e8b6eac44a41341f112821482bee6c940c98mmentovai { INT_MIN, 16, 1, true }, // lowest possible range 3713261e8b6eac44a41341f112821482bee6c940c98mmentovai { -2, 5, 2, true }, // a range through zero 3723261e8b6eac44a41341f112821482bee6c940c98mmentovai { INT_MAX - 9, 11, 3, false }, // tests anti-overflow 3733261e8b6eac44a41341f112821482bee6c940c98mmentovai { INT_MAX - 9, 10, 4, true }, // highest possible range 3743261e8b6eac44a41341f112821482bee6c940c98mmentovai { 5, 0, 5, false }, // tests anti-zero-size 3753261e8b6eac44a41341f112821482bee6c940c98mmentovai { 5, 1, 6, true }, // smallest possible range 3763261e8b6eac44a41341f112821482bee6c940c98mmentovai { -20, 15, 7, true }, // entirely negative 3773261e8b6eac44a41341f112821482bee6c940c98mmentovai 3783261e8b6eac44a41341f112821482bee6c940c98mmentovai { 10, 10, 10, true }, // causes the following tests to fail 3793261e8b6eac44a41341f112821482bee6c940c98mmentovai { 9, 10, 11, false }, // one-less base, one-less high 3803261e8b6eac44a41341f112821482bee6c940c98mmentovai { 9, 11, 12, false }, // one-less base, identical high 3813261e8b6eac44a41341f112821482bee6c940c98mmentovai { 9, 12, 13, false }, // completely contains existing 3823261e8b6eac44a41341f112821482bee6c940c98mmentovai { 10, 9, 14, false }, // identical base, one-less high 3833261e8b6eac44a41341f112821482bee6c940c98mmentovai { 10, 10, 15, false }, // exactly identical to existing range 3843261e8b6eac44a41341f112821482bee6c940c98mmentovai { 10, 11, 16, false }, // identical base, one-greater high 3853261e8b6eac44a41341f112821482bee6c940c98mmentovai { 11, 8, 17, false }, // contained completely within 3863261e8b6eac44a41341f112821482bee6c940c98mmentovai { 11, 9, 18, false }, // one-greater base, identical high 3873261e8b6eac44a41341f112821482bee6c940c98mmentovai { 11, 10, 19, false }, // one-greater base, one-greater high 3883261e8b6eac44a41341f112821482bee6c940c98mmentovai { 9, 2, 20, false }, // overlaps bottom by one 3893261e8b6eac44a41341f112821482bee6c940c98mmentovai { 10, 1, 21, false }, // overlaps bottom by one, contained 3903261e8b6eac44a41341f112821482bee6c940c98mmentovai { 19, 1, 22, false }, // overlaps top by one, contained 3913261e8b6eac44a41341f112821482bee6c940c98mmentovai { 19, 2, 23, false }, // overlaps top by one 3923261e8b6eac44a41341f112821482bee6c940c98mmentovai 3933261e8b6eac44a41341f112821482bee6c940c98mmentovai { 9, 1, 24, true }, // directly below without overlap 3943261e8b6eac44a41341f112821482bee6c940c98mmentovai { 20, 1, 25, true }, // directly above without overlap 3953261e8b6eac44a41341f112821482bee6c940c98mmentovai 3963261e8b6eac44a41341f112821482bee6c940c98mmentovai { 6, 3, 26, true }, // exactly between two ranges, gapless 3973261e8b6eac44a41341f112821482bee6c940c98mmentovai { 7, 3, 27, false }, // tries to span two ranges 3983261e8b6eac44a41341f112821482bee6c940c98mmentovai { 7, 5, 28, false }, // tries to span three ranges 3993261e8b6eac44a41341f112821482bee6c940c98mmentovai { 4, 20, 29, false }, // tries to contain several ranges 4003261e8b6eac44a41341f112821482bee6c940c98mmentovai 4013261e8b6eac44a41341f112821482bee6c940c98mmentovai { 30, 50, 30, true }, 4023261e8b6eac44a41341f112821482bee6c940c98mmentovai { 90, 25, 31, true }, 4033261e8b6eac44a41341f112821482bee6c940c98mmentovai { 35, 65, 32, false }, // tries to span two noncontiguous 4043261e8b6eac44a41341f112821482bee6c940c98mmentovai { 120, 10000, 33, true }, // > 8-bit 4053261e8b6eac44a41341f112821482bee6c940c98mmentovai { 20000, 20000, 34, true }, // > 8-bit 4063261e8b6eac44a41341f112821482bee6c940c98mmentovai { 0x10001, 0x10001, 35, true }, // > 16-bit 4073261e8b6eac44a41341f112821482bee6c940c98mmentovai 40853d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai { 27, -1, 36, false } // tests high < base 4093261e8b6eac44a41341f112821482bee6c940c98mmentovai }; 4103261e8b6eac44a41341f112821482bee6c940c98mmentovai 4113261e8b6eac44a41341f112821482bee6c940c98mmentovai // Attempt to fill the entire space. The entire space must be filled with 4123261e8b6eac44a41341f112821482bee6c940c98mmentovai // three stores because AddressType is signed for these tests, so RangeMap 4133261e8b6eac44a41341f112821482bee6c940c98mmentovai // treats the size as signed and rejects sizes that appear to be negative. 4143261e8b6eac44a41341f112821482bee6c940c98mmentovai // Even if these tests were run as unsigned, two stores would be needed 4153261e8b6eac44a41341f112821482bee6c940c98mmentovai // to fill the space because the entire size of the space could only be 4163261e8b6eac44a41341f112821482bee6c940c98mmentovai // described by using one more bit than would be present in AddressType. 4173261e8b6eac44a41341f112821482bee6c940c98mmentovai const RangeTest range_tests_1[] = { 4183261e8b6eac44a41341f112821482bee6c940c98mmentovai { INT_MIN, INT_MAX, 50, true }, // From INT_MIN to -2, inclusive 4193261e8b6eac44a41341f112821482bee6c940c98mmentovai { -1, 2, 51, true }, // From -1 to 0, inclusive 4203261e8b6eac44a41341f112821482bee6c940c98mmentovai { 1, INT_MAX, 52, true }, // From 1 to INT_MAX, inclusive 4213261e8b6eac44a41341f112821482bee6c940c98mmentovai { INT_MIN, INT_MAX, 53, false }, // Can't fill the space twice 4223261e8b6eac44a41341f112821482bee6c940c98mmentovai { -1, 2, 54, false }, 4233261e8b6eac44a41341f112821482bee6c940c98mmentovai { 1, INT_MAX, 55, false }, 4243261e8b6eac44a41341f112821482bee6c940c98mmentovai { -3, 6, 56, false }, // -3 to 2, inclusive - spans 3 ranges 4253261e8b6eac44a41341f112821482bee6c940c98mmentovai }; 4263261e8b6eac44a41341f112821482bee6c940c98mmentovai 4273261e8b6eac44a41341f112821482bee6c940c98mmentovai // A light round of testing to verify that RetrieveRange does the right 4283261e8b6eac44a41341f112821482bee6c940c98mmentovai // the right thing at the extremities of the range when nothing is stored 4293261e8b6eac44a41341f112821482bee6c940c98mmentovai // there. Checks are forced without storing anything at the extremities 4303261e8b6eac44a41341f112821482bee6c940c98mmentovai // by setting size = 0. 4313261e8b6eac44a41341f112821482bee6c940c98mmentovai const RangeTest range_tests_2[] = { 4323261e8b6eac44a41341f112821482bee6c940c98mmentovai { INT_MIN, 0, 100, false }, // makes RetrieveRange check low end 4333261e8b6eac44a41341f112821482bee6c940c98mmentovai { -1, 3, 101, true }, 4343261e8b6eac44a41341f112821482bee6c940c98mmentovai { INT_MAX, 0, 102, false }, // makes RetrieveRange check high end 4353261e8b6eac44a41341f112821482bee6c940c98mmentovai }; 4363261e8b6eac44a41341f112821482bee6c940c98mmentovai 4373261e8b6eac44a41341f112821482bee6c940c98mmentovai // Similar to the previous test set, but with a couple of ranges closer 4383261e8b6eac44a41341f112821482bee6c940c98mmentovai // to the extremities. 4393261e8b6eac44a41341f112821482bee6c940c98mmentovai const RangeTest range_tests_3[] = { 4403261e8b6eac44a41341f112821482bee6c940c98mmentovai { INT_MIN + 1, 1, 110, true }, 4413261e8b6eac44a41341f112821482bee6c940c98mmentovai { INT_MAX - 1, 1, 111, true }, 4423261e8b6eac44a41341f112821482bee6c940c98mmentovai { INT_MIN, 0, 112, false }, // makes RetrieveRange check low end 4433261e8b6eac44a41341f112821482bee6c940c98mmentovai { INT_MAX, 0, 113, false } // makes RetrieveRange check high end 4443261e8b6eac44a41341f112821482bee6c940c98mmentovai }; 4453261e8b6eac44a41341f112821482bee6c940c98mmentovai 4463261e8b6eac44a41341f112821482bee6c940c98mmentovai // The range map is cleared between sets of tests listed here. 4473261e8b6eac44a41341f112821482bee6c940c98mmentovai const RangeTestSet range_test_sets[] = { 4483261e8b6eac44a41341f112821482bee6c940c98mmentovai { range_tests_0, sizeof(range_tests_0) / sizeof(RangeTest) }, 4493261e8b6eac44a41341f112821482bee6c940c98mmentovai { range_tests_1, sizeof(range_tests_1) / sizeof(RangeTest) }, 4503261e8b6eac44a41341f112821482bee6c940c98mmentovai { range_tests_2, sizeof(range_tests_2) / sizeof(RangeTest) }, 4513261e8b6eac44a41341f112821482bee6c940c98mmentovai { range_tests_3, sizeof(range_tests_3) / sizeof(RangeTest) }, 45253d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai { range_tests_0, sizeof(range_tests_0) / sizeof(RangeTest) } // Run again 4533261e8b6eac44a41341f112821482bee6c940c98mmentovai }; 4543261e8b6eac44a41341f112821482bee6c940c98mmentovai 4553261e8b6eac44a41341f112821482bee6c940c98mmentovai // Maintain the range map in a pointer so that deletion can be meaningfully 4563261e8b6eac44a41341f112821482bee6c940c98mmentovai // tested. 4572466d8e993a800a17e00deda2f3a27e0505140e1mmentovai scoped_ptr<TestMap> range_map(new TestMap()); 4583261e8b6eac44a41341f112821482bee6c940c98mmentovai 4593261e8b6eac44a41341f112821482bee6c940c98mmentovai // Run all of the test sets in sequence. 4603261e8b6eac44a41341f112821482bee6c940c98mmentovai unsigned int range_test_set_count = sizeof(range_test_sets) / 4613261e8b6eac44a41341f112821482bee6c940c98mmentovai sizeof(RangeTestSet); 4623261e8b6eac44a41341f112821482bee6c940c98mmentovai for (unsigned int range_test_set_index = 0; 4633261e8b6eac44a41341f112821482bee6c940c98mmentovai range_test_set_index < range_test_set_count; 4643261e8b6eac44a41341f112821482bee6c940c98mmentovai ++range_test_set_index) { 465d9fb68c3e02166565fc75b0635519b42fd061982mmentovai const RangeTest *range_tests = 4663261e8b6eac44a41341f112821482bee6c940c98mmentovai range_test_sets[range_test_set_index].range_tests; 4673261e8b6eac44a41341f112821482bee6c940c98mmentovai unsigned int range_test_count = 4683261e8b6eac44a41341f112821482bee6c940c98mmentovai range_test_sets[range_test_set_index].range_test_count; 4693261e8b6eac44a41341f112821482bee6c940c98mmentovai 4703261e8b6eac44a41341f112821482bee6c940c98mmentovai // Run the StoreRange test, which validates StoreRange and initializes 4713261e8b6eac44a41341f112821482bee6c940c98mmentovai // the RangeMap with data for the RetrieveRange test. 4723261e8b6eac44a41341f112821482bee6c940c98mmentovai int stored_count = 0; // The number of ranges successfully stored 4733261e8b6eac44a41341f112821482bee6c940c98mmentovai for (unsigned int range_test_index = 0; 4743261e8b6eac44a41341f112821482bee6c940c98mmentovai range_test_index < range_test_count; 4753261e8b6eac44a41341f112821482bee6c940c98mmentovai ++range_test_index) { 476d9fb68c3e02166565fc75b0635519b42fd061982mmentovai const RangeTest *range_test = &range_tests[range_test_index]; 4773261e8b6eac44a41341f112821482bee6c940c98mmentovai if (!StoreTest(range_map.get(), range_test)) 4783261e8b6eac44a41341f112821482bee6c940c98mmentovai return false; 4793261e8b6eac44a41341f112821482bee6c940c98mmentovai 4803261e8b6eac44a41341f112821482bee6c940c98mmentovai if (range_test->expect_storable) 4813261e8b6eac44a41341f112821482bee6c940c98mmentovai ++stored_count; 4823261e8b6eac44a41341f112821482bee6c940c98mmentovai } 4833261e8b6eac44a41341f112821482bee6c940c98mmentovai 4843261e8b6eac44a41341f112821482bee6c940c98mmentovai // There should be exactly one CountedObject for everything successfully 4853261e8b6eac44a41341f112821482bee6c940c98mmentovai // stored in the RangeMap. 4863261e8b6eac44a41341f112821482bee6c940c98mmentovai if (CountedObject::count() != stored_count) { 4873261e8b6eac44a41341f112821482bee6c940c98mmentovai fprintf(stderr, "FAILED: " 4883261e8b6eac44a41341f112821482bee6c940c98mmentovai "stored object counts don't match, expected %d, observed %d\n", 4893261e8b6eac44a41341f112821482bee6c940c98mmentovai stored_count, 4903261e8b6eac44a41341f112821482bee6c940c98mmentovai CountedObject::count()); 4913261e8b6eac44a41341f112821482bee6c940c98mmentovai 4923261e8b6eac44a41341f112821482bee6c940c98mmentovai return false; 4933261e8b6eac44a41341f112821482bee6c940c98mmentovai } 4943261e8b6eac44a41341f112821482bee6c940c98mmentovai 495db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai // The RangeMap's own count of objects should also match. 496db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai if (range_map->GetCount() != stored_count) { 497db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai fprintf(stderr, "FAILED: stored object count doesn't match GetCount, " 498db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai "expected %d, observed %d\n", 499db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai stored_count, range_map->GetCount()); 500db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai 501db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai return false; 502db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai } 503db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai 5043261e8b6eac44a41341f112821482bee6c940c98mmentovai // Run the RetrieveRange test 5053261e8b6eac44a41341f112821482bee6c940c98mmentovai for (unsigned int range_test_index = 0; 5063261e8b6eac44a41341f112821482bee6c940c98mmentovai range_test_index < range_test_count; 5073261e8b6eac44a41341f112821482bee6c940c98mmentovai ++range_test_index) { 508d9fb68c3e02166565fc75b0635519b42fd061982mmentovai const RangeTest *range_test = &range_tests[range_test_index]; 5093261e8b6eac44a41341f112821482bee6c940c98mmentovai if (!RetrieveTest(range_map.get(), range_test)) 5103261e8b6eac44a41341f112821482bee6c940c98mmentovai return false; 5113261e8b6eac44a41341f112821482bee6c940c98mmentovai } 5123261e8b6eac44a41341f112821482bee6c940c98mmentovai 513db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai if (!RetrieveIndexTest(range_map.get(), range_test_set_index)) 514db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai return false; 515db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai 5163261e8b6eac44a41341f112821482bee6c940c98mmentovai // Clear the map between test sets. If this is the final test set, 5173261e8b6eac44a41341f112821482bee6c940c98mmentovai // delete the map instead to test destruction. 5183261e8b6eac44a41341f112821482bee6c940c98mmentovai if (range_test_set_index < range_test_set_count - 1) 5193261e8b6eac44a41341f112821482bee6c940c98mmentovai range_map->Clear(); 5203261e8b6eac44a41341f112821482bee6c940c98mmentovai else 5213261e8b6eac44a41341f112821482bee6c940c98mmentovai range_map.reset(); 5223261e8b6eac44a41341f112821482bee6c940c98mmentovai 5233261e8b6eac44a41341f112821482bee6c940c98mmentovai // Test that all stored objects are freed when the RangeMap is cleared 5243261e8b6eac44a41341f112821482bee6c940c98mmentovai // or deleted. 5253261e8b6eac44a41341f112821482bee6c940c98mmentovai if (CountedObject::count() != 0) { 5263261e8b6eac44a41341f112821482bee6c940c98mmentovai fprintf(stderr, "FAILED: " 5273261e8b6eac44a41341f112821482bee6c940c98mmentovai "did not free all objects after %s, %d still allocated\n", 5283261e8b6eac44a41341f112821482bee6c940c98mmentovai range_test_set_index < range_test_set_count - 1 ? "clear" 5293261e8b6eac44a41341f112821482bee6c940c98mmentovai : "delete", 5303261e8b6eac44a41341f112821482bee6c940c98mmentovai CountedObject::count()); 5313261e8b6eac44a41341f112821482bee6c940c98mmentovai 5323261e8b6eac44a41341f112821482bee6c940c98mmentovai return false; 5333261e8b6eac44a41341f112821482bee6c940c98mmentovai } 5343261e8b6eac44a41341f112821482bee6c940c98mmentovai } 5353261e8b6eac44a41341f112821482bee6c940c98mmentovai 536b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com if (!RetriveAtIndexTest2()) { 537b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com fprintf(stderr, "FAILED: did not pass RetrieveAtIndexTest2()\n"); 538b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com return false; 539b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com } 540b5b5f9e5205b7d31a401f245cdad44080cd7bfc9SiyangXie@gmail.com 5413261e8b6eac44a41341f112821482bee6c940c98mmentovai return true; 5423261e8b6eac44a41341f112821482bee6c940c98mmentovai} 5433261e8b6eac44a41341f112821482bee6c940c98mmentovai 5448647dde8cc03ef16b565dccc75574ee5f0d9cf72mmentovai 5458647dde8cc03ef16b565dccc75574ee5f0d9cf72mmentovai} // namespace 5468647dde8cc03ef16b565dccc75574ee5f0d9cf72mmentovai 5478647dde8cc03ef16b565dccc75574ee5f0d9cf72mmentovai 548d9fb68c3e02166565fc75b0635519b42fd061982mmentovaiint main(int argc, char **argv) { 54932b802dba3d49880a0414d066e71cdc20ab09901mmentovai BPLOG_INIT(&argc, &argv); 55032b802dba3d49880a0414d066e71cdc20ab09901mmentovai 5513261e8b6eac44a41341f112821482bee6c940c98mmentovai return RunTests() ? 0 : 1; 5523261e8b6eac44a41341f112821482bee6c940c98mmentovai} 553