1 // Copyright (c) 2006, 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 // range_map.h: Range maps. 31 // 32 // A range map associates a range of addresses with a specific object. This 33 // is useful when certain objects of variable size are located within an 34 // address space. The range map makes it simple to determine which object is 35 // associated with a specific address, which may be any address within the 36 // range associated with an object. 37 // 38 // Author: Mark Mentovai 39 40 #ifndef PROCESSOR_RANGE_MAP_H__ 41 #define PROCESSOR_RANGE_MAP_H__ 42 43 44 #include <map> 45 46 47 namespace google_breakpad { 48 49 // Forward declarations (for later friend declarations of specialized template). 50 template<class, class> class RangeMapSerializer; 51 52 template<typename AddressType, typename EntryType> 53 class RangeMap { 54 public: RangeMap()55 RangeMap() : map_() {} 56 57 // Inserts a range into the map. Returns false for a parameter error, 58 // or if the location of the range would conflict with a range already 59 // stored in the map. 60 bool StoreRange(const AddressType &base, 61 const AddressType &size, 62 const EntryType &entry); 63 64 // Locates the range encompassing the supplied address. If there is 65 // no such range, returns false. entry_base and entry_size, if non-NULL, 66 // are set to the base and size of the entry's range. 67 bool RetrieveRange(const AddressType &address, EntryType *entry, 68 AddressType *entry_base, AddressType *entry_size) const; 69 70 // Locates the range encompassing the supplied address, if one exists. 71 // If no range encompasses the supplied address, locates the nearest range 72 // to the supplied address that is lower than the address. Returns false 73 // if no range meets these criteria. entry_base and entry_size, if 74 // non-NULL, are set to the base and size of the entry's range. 75 bool RetrieveNearestRange(const AddressType &address, EntryType *entry, 76 AddressType *entry_base, AddressType *entry_size) 77 const; 78 79 // Treating all ranges as a list ordered by the address spaces that they 80 // occupy, locates the range at the index specified by index. Returns 81 // false if index is larger than the number of ranges stored. entry_base 82 // and entry_size, if non-NULL, are set to the base and size of the entry's 83 // range. 84 // 85 // RetrieveRangeAtIndex is not optimized for speedy operation. 86 bool RetrieveRangeAtIndex(int index, EntryType *entry, 87 AddressType *entry_base, AddressType *entry_size) 88 const; 89 90 // Returns the number of ranges stored in the RangeMap. 91 int GetCount() const; 92 93 // Empties the range map, restoring it to the state it was when it was 94 // initially created. 95 void Clear(); 96 97 private: 98 // Friend declarations. 99 friend class ModuleComparer; 100 friend class RangeMapSerializer<AddressType, EntryType>; 101 102 class Range { 103 public: Range(const AddressType & base,const EntryType & entry)104 Range(const AddressType &base, const EntryType &entry) 105 : base_(base), entry_(entry) {} 106 base()107 AddressType base() const { return base_; } entry()108 EntryType entry() const { return entry_; } 109 110 private: 111 // The base address of the range. The high address does not need to 112 // be stored, because RangeMap uses it as the key to the map. 113 const AddressType base_; 114 115 // The entry corresponding to a range. 116 const EntryType entry_; 117 }; 118 119 // Convenience types. 120 typedef std::map<AddressType, Range> AddressToRangeMap; 121 typedef typename AddressToRangeMap::const_iterator MapConstIterator; 122 typedef typename AddressToRangeMap::value_type MapValue; 123 124 // Maps the high address of each range to a EntryType. 125 AddressToRangeMap map_; 126 }; 127 128 129 } // namespace google_breakpad 130 131 132 #endif // PROCESSOR_RANGE_MAP_H__ 133