17daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// Copyright (c) 2006, 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.h: Range maps. 313261e8b6eac44a41341f112821482bee6c940c98mmentovai// 323261e8b6eac44a41341f112821482bee6c940c98mmentovai// A range map associates a range of addresses with a specific object. This 333261e8b6eac44a41341f112821482bee6c940c98mmentovai// is useful when certain objects of variable size are located within an 343261e8b6eac44a41341f112821482bee6c940c98mmentovai// address space. The range map makes it simple to determine which object is 353261e8b6eac44a41341f112821482bee6c940c98mmentovai// associated with a specific address, which may be any address within the 363261e8b6eac44a41341f112821482bee6c940c98mmentovai// range associated with an object. 373261e8b6eac44a41341f112821482bee6c940c98mmentovai// 383261e8b6eac44a41341f112821482bee6c940c98mmentovai// Author: Mark Mentovai 393261e8b6eac44a41341f112821482bee6c940c98mmentovai 403261e8b6eac44a41341f112821482bee6c940c98mmentovai#ifndef PROCESSOR_RANGE_MAP_H__ 413261e8b6eac44a41341f112821482bee6c940c98mmentovai#define PROCESSOR_RANGE_MAP_H__ 423261e8b6eac44a41341f112821482bee6c940c98mmentovai 433261e8b6eac44a41341f112821482bee6c940c98mmentovai 443261e8b6eac44a41341f112821482bee6c940c98mmentovai#include <map> 453261e8b6eac44a41341f112821482bee6c940c98mmentovai 463261e8b6eac44a41341f112821482bee6c940c98mmentovai 47e5dc60822e5938fea2ae892ccddb906641ba174emmentovainamespace google_breakpad { 483261e8b6eac44a41341f112821482bee6c940c98mmentovai 4908730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// Forward declarations (for later friend declarations of specialized template). 5008730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.comtemplate<class, class> class RangeMapSerializer; 513261e8b6eac44a41341f112821482bee6c940c98mmentovai 523261e8b6eac44a41341f112821482bee6c940c98mmentovaitemplate<typename AddressType, typename EntryType> 533261e8b6eac44a41341f112821482bee6c940c98mmentovaiclass RangeMap { 5453d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai public: 5553d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai RangeMap() : map_() {} 5653d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai 5753d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai // Inserts a range into the map. Returns false for a parameter error, 5853d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai // or if the location of the range would conflict with a range already 5953d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai // stored in the map. 60d9fb68c3e02166565fc75b0635519b42fd061982mmentovai bool StoreRange(const AddressType &base, 61d9fb68c3e02166565fc75b0635519b42fd061982mmentovai const AddressType &size, 62d9fb68c3e02166565fc75b0635519b42fd061982mmentovai const EntryType &entry); 6353d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai 6453d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai // Locates the range encompassing the supplied address. If there is 6565571f17edb82d122b5f6dc741bd7d4b9e315e1bmmentovai // no such range, returns false. entry_base and entry_size, if non-NULL, 6665571f17edb82d122b5f6dc741bd7d4b9e315e1bmmentovai // are set to the base and size of the entry's range. 672fc823f5794737391e231c1dce6c2b0793213e53mmentovai bool RetrieveRange(const AddressType &address, EntryType *entry, 682fc823f5794737391e231c1dce6c2b0793213e53mmentovai AddressType *entry_base, AddressType *entry_size) const; 692fc823f5794737391e231c1dce6c2b0793213e53mmentovai 702fc823f5794737391e231c1dce6c2b0793213e53mmentovai // Locates the range encompassing the supplied address, if one exists. 712fc823f5794737391e231c1dce6c2b0793213e53mmentovai // If no range encompasses the supplied address, locates the nearest range 722fc823f5794737391e231c1dce6c2b0793213e53mmentovai // to the supplied address that is lower than the address. Returns false 732fc823f5794737391e231c1dce6c2b0793213e53mmentovai // if no range meets these criteria. entry_base and entry_size, if 742fc823f5794737391e231c1dce6c2b0793213e53mmentovai // non-NULL, are set to the base and size of the entry's range. 752fc823f5794737391e231c1dce6c2b0793213e53mmentovai bool RetrieveNearestRange(const AddressType &address, EntryType *entry, 762fc823f5794737391e231c1dce6c2b0793213e53mmentovai AddressType *entry_base, AddressType *entry_size) 772fc823f5794737391e231c1dce6c2b0793213e53mmentovai const; 7853d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai 79db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai // Treating all ranges as a list ordered by the address spaces that they 80db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai // occupy, locates the range at the index specified by index. Returns 8165571f17edb82d122b5f6dc741bd7d4b9e315e1bmmentovai // false if index is larger than the number of ranges stored. entry_base 8265571f17edb82d122b5f6dc741bd7d4b9e315e1bmmentovai // and entry_size, if non-NULL, are set to the base and size of the entry's 8365571f17edb82d122b5f6dc741bd7d4b9e315e1bmmentovai // range. 84db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai // 85db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai // RetrieveRangeAtIndex is not optimized for speedy operation. 86db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai bool RetrieveRangeAtIndex(int index, EntryType *entry, 87db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai AddressType *entry_base, AddressType *entry_size) 88db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai const; 89db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai 90db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai // Returns the number of ranges stored in the RangeMap. 91db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai int GetCount() const; 92db3342a10ec30902aa9018b80e1d9a40bd01c487mmentovai 9353d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai // Empties the range map, restoring it to the state it was when it was 9453d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai // initially created. 9553d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai void Clear(); 9653d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai 9753d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai private: 9808730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com // Friend declarations. 9941f998fe5a0630506d6d2a1bae78b1be179fe850SiyangXie@gmail.com friend class ModuleComparer; 10008730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com friend class RangeMapSerializer<AddressType, EntryType>; 10108730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com 10253d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai class Range { 10353d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai public: 104d9fb68c3e02166565fc75b0635519b42fd061982mmentovai Range(const AddressType &base, const EntryType &entry) 10553d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai : base_(base), entry_(entry) {} 10653d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai 10753d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai AddressType base() const { return base_; } 10853d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai EntryType entry() const { return entry_; } 10953d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai 11053d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai private: 11153d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai // The base address of the range. The high address does not need to 11253d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai // be stored, because RangeMap uses it as the key to the map. 11353d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai const AddressType base_; 11453d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai 115d9fb68c3e02166565fc75b0635519b42fd061982mmentovai // The entry corresponding to a range. 116d9fb68c3e02166565fc75b0635519b42fd061982mmentovai const EntryType entry_; 11753d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai }; 11853d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai 119d9fb68c3e02166565fc75b0635519b42fd061982mmentovai // Convenience types. 120d9fb68c3e02166565fc75b0635519b42fd061982mmentovai typedef std::map<AddressType, Range> AddressToRangeMap; 1218c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai typedef typename AddressToRangeMap::const_iterator MapConstIterator; 1228c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai typedef typename AddressToRangeMap::value_type MapValue; 12353d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai 12453d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai // Maps the high address of each range to a EntryType. 12553d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai AddressToRangeMap map_; 1263261e8b6eac44a41341f112821482bee6c940c98mmentovai}; 1273261e8b6eac44a41341f112821482bee6c940c98mmentovai 1283261e8b6eac44a41341f112821482bee6c940c98mmentovai 129e5dc60822e5938fea2ae892ccddb906641ba174emmentovai} // namespace google_breakpad 1303261e8b6eac44a41341f112821482bee6c940c98mmentovai 1313261e8b6eac44a41341f112821482bee6c940c98mmentovai 132d9fb68c3e02166565fc75b0635519b42fd061982mmentovai#endif // PROCESSOR_RANGE_MAP_H__ 133