range_map.h revision 7daf246e4baf0837e25429668cc23e92b6afe3b3
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 473261e8b6eac44a41341f112821482bee6c940c98mmentovainamespace google_airbag { 483261e8b6eac44a41341f112821482bee6c940c98mmentovai 493261e8b6eac44a41341f112821482bee6c940c98mmentovai 503261e8b6eac44a41341f112821482bee6c940c98mmentovaitemplate<typename AddressType, typename EntryType> 513261e8b6eac44a41341f112821482bee6c940c98mmentovaiclass RangeMap { 5253d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai public: 5353d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai RangeMap() : map_() {} 5453d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai 5553d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai // Inserts a range into the map. Returns false for a parameter error, 5653d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai // or if the location of the range would conflict with a range already 5753d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai // stored in the map. 58d9fb68c3e02166565fc75b0635519b42fd061982mmentovai bool StoreRange(const AddressType &base, 59d9fb68c3e02166565fc75b0635519b42fd061982mmentovai const AddressType &size, 60d9fb68c3e02166565fc75b0635519b42fd061982mmentovai const EntryType &entry); 6153d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai 6253d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai // Locates the range encompassing the supplied address. If there is 6353d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai // no such range, or if there is a parameter error, returns false. 64d9fb68c3e02166565fc75b0635519b42fd061982mmentovai bool RetrieveRange(const AddressType &address, EntryType *entry) const; 6553d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai 6653d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai // Empties the range map, restoring it to the state it was when it was 6753d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai // initially created. 6853d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai void Clear(); 6953d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai 7053d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai private: 7153d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai class Range { 7253d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai public: 73d9fb68c3e02166565fc75b0635519b42fd061982mmentovai Range(const AddressType &base, const EntryType &entry) 7453d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai : base_(base), entry_(entry) {} 7553d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai 7653d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai AddressType base() const { return base_; } 7753d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai EntryType entry() const { return entry_; } 7853d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai 7953d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai private: 8053d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai // The base address of the range. The high address does not need to 8153d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai // be stored, because RangeMap uses it as the key to the map. 8253d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai const AddressType base_; 8353d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai 84d9fb68c3e02166565fc75b0635519b42fd061982mmentovai // The entry corresponding to a range. 85d9fb68c3e02166565fc75b0635519b42fd061982mmentovai const EntryType entry_; 8653d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai }; 8753d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai 88d9fb68c3e02166565fc75b0635519b42fd061982mmentovai // Convenience types. 89d9fb68c3e02166565fc75b0635519b42fd061982mmentovai typedef std::map<AddressType, Range> AddressToRangeMap; 908c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai typedef typename AddressToRangeMap::const_iterator MapConstIterator; 918c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai typedef typename AddressToRangeMap::value_type MapValue; 9253d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai 9353d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai // Maps the high address of each range to a EntryType. 9453d0f69d35375fe2ffd119ac7e4898083c0e071cmmentovai AddressToRangeMap map_; 953261e8b6eac44a41341f112821482bee6c940c98mmentovai}; 963261e8b6eac44a41341f112821482bee6c940c98mmentovai 973261e8b6eac44a41341f112821482bee6c940c98mmentovai 98d9fb68c3e02166565fc75b0635519b42fd061982mmentovai} // namespace google_airbag 993261e8b6eac44a41341f112821482bee6c940c98mmentovai 1003261e8b6eac44a41341f112821482bee6c940c98mmentovai 101d9fb68c3e02166565fc75b0635519b42fd061982mmentovai#endif // PROCESSOR_RANGE_MAP_H__ 102