OLD | NEW |
1 // Copyright (c) 2006, Google Inc. | 1 // Copyright (c) 2006, Google Inc. |
2 // All rights reserved. | 2 // All rights reserved. |
3 // | 3 // |
4 // Redistribution and use in source and binary forms, with or without | 4 // Redistribution and use in source and binary forms, with or without |
5 // modification, are permitted provided that the following conditions are | 5 // modification, are permitted provided that the following conditions are |
6 // met: | 6 // met: |
7 // | 7 // |
8 // * Redistributions of source code must retain the above copyright | 8 // * Redistributions of source code must retain the above copyright |
9 // notice, this list of conditions and the following disclaimer. | 9 // notice, this list of conditions and the following disclaimer. |
10 // * Redistributions in binary form must reproduce the above | 10 // * Redistributions in binary form must reproduce the above |
(...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
45 | 45 |
46 | 46 |
47 namespace google_breakpad { | 47 namespace google_breakpad { |
48 | 48 |
49 // Forward declarations (for later friend declarations of specialized template). | 49 // Forward declarations (for later friend declarations of specialized template). |
50 template<class, class> class RangeMapSerializer; | 50 template<class, class> class RangeMapSerializer; |
51 | 51 |
52 template<typename AddressType, typename EntryType> | 52 template<typename AddressType, typename EntryType> |
53 class RangeMap { | 53 class RangeMap { |
54 public: | 54 public: |
55 RangeMap() : map_() {} | 55 RangeMap() : enable_shrink_down_(false), map_() {} |
| 56 |
| 57 // |enable_shrink_down| tells whether overlapping ranges can be shrunk down. |
| 58 // If true, then adding a new range that overlaps with an existing one can |
| 59 // be a successful operation. The range which ends at the higher address |
| 60 // will be shrunk down by moving its start position to a higher address so |
| 61 // that it does not overlap anymore. |
| 62 void SetEnableShrinkDown(bool enable_shrink_down); |
56 | 63 |
57 // Inserts a range into the map. Returns false for a parameter error, | 64 // 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 | 65 // or if the location of the range would conflict with a range already |
59 // stored in the map. | 66 // stored in the map. If enable_shrink_down is true and there is an overlap |
60 bool StoreRange(const AddressType &base, | 67 // between the current range and some other range (already in the map), |
61 const AddressType &size, | 68 // shrink down the range which ends at a higher address. |
| 69 bool StoreRange(const AddressType &base, const AddressType &size, |
62 const EntryType &entry); | 70 const EntryType &entry); |
63 | 71 |
64 // Locates the range encompassing the supplied address. If there is | 72 // Locates the range encompassing the supplied address. If there is no such |
65 // no such range, returns false. entry_base and entry_size, if non-NULL, | 73 // range, returns false. entry_base, entry_delta, and entry_size, if |
66 // are set to the base and size of the entry's range. | 74 // non-NULL, are set to the base, delta, and size of the entry's range. |
| 75 // A positive entry delta (> 0) indicates that there was an overlap and the |
| 76 // entry was shrunk down (original start address was increased by delta). |
67 bool RetrieveRange(const AddressType &address, EntryType *entry, | 77 bool RetrieveRange(const AddressType &address, EntryType *entry, |
68 AddressType *entry_base, AddressType *entry_size) const; | 78 AddressType *entry_base, AddressType *entry_delta, |
| 79 AddressType *entry_size) const; |
69 | 80 |
70 // Locates the range encompassing the supplied address, if one exists. | 81 // Locates the range encompassing the supplied address, if one exists. |
71 // If no range encompasses the supplied address, locates the nearest range | 82 // If no range encompasses the supplied address, locates the nearest range |
72 // to the supplied address that is lower than the address. Returns false | 83 // 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 | 84 // if no range meets these criteria. entry_base, entry_delta, and entry_size, |
74 // non-NULL, are set to the base and size of the entry's range. | 85 // if non-NULL, are set to the base, delta, and size of the entry's range. |
| 86 // A positive entry delta (> 0) indicates that there was an overlap and the |
| 87 // entry was shrunk down (original start address was increased by delta). |
75 bool RetrieveNearestRange(const AddressType &address, EntryType *entry, | 88 bool RetrieveNearestRange(const AddressType &address, EntryType *entry, |
76 AddressType *entry_base, AddressType *entry_size) | 89 AddressType *entry_base, AddressType *entry_delta, |
77 const; | 90 AddressType *entry_size) const; |
78 | 91 |
79 // Treating all ranges as a list ordered by the address spaces that they | 92 // 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 | 93 // 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 | 94 // 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 | 95 // entry_delta, and entry_size, if non-NULL, are set to the base, delta, and |
83 // range. | 96 // size of the entry's range. |
| 97 // A positive entry delta (> 0) indicates that there was an overlap and the |
| 98 // entry was shrunk down (original start address was increased by delta). |
84 // | 99 // |
85 // RetrieveRangeAtIndex is not optimized for speedy operation. | 100 // RetrieveRangeAtIndex is not optimized for speedy operation. |
86 bool RetrieveRangeAtIndex(int index, EntryType *entry, | 101 bool RetrieveRangeAtIndex(int index, EntryType *entry, |
87 AddressType *entry_base, AddressType *entry_size) | 102 AddressType *entry_base, AddressType *entry_delta, |
88 const; | 103 AddressType *entry_size) const; |
89 | 104 |
90 // Returns the number of ranges stored in the RangeMap. | 105 // Returns the number of ranges stored in the RangeMap. |
91 int GetCount() const; | 106 int GetCount() const; |
92 | 107 |
93 // Empties the range map, restoring it to the state it was when it was | 108 // Empties the range map, restoring it to the state it was when it was |
94 // initially created. | 109 // initially created. |
95 void Clear(); | 110 void Clear(); |
96 | 111 |
97 private: | 112 private: |
98 // Friend declarations. | 113 // Friend declarations. |
99 friend class ModuleComparer; | 114 friend class ModuleComparer; |
100 friend class RangeMapSerializer<AddressType, EntryType>; | 115 friend class RangeMapSerializer<AddressType, EntryType>; |
101 | 116 |
| 117 // Same a StoreRange() with the only exception that the |delta| can be |
| 118 // passed in. |
| 119 bool StoreRangeInternal(const AddressType &base, const AddressType &delta, |
| 120 const AddressType &size, const EntryType &entry); |
| 121 |
102 class Range { | 122 class Range { |
103 public: | 123 public: |
104 Range(const AddressType &base, const EntryType &entry) | 124 Range(const AddressType &base, const AddressType &delta, |
105 : base_(base), entry_(entry) {} | 125 const EntryType &entry) |
| 126 : base_(base), delta_(delta), entry_(entry) {} |
106 | 127 |
107 AddressType base() const { return base_; } | 128 AddressType base() const { return base_; } |
| 129 AddressType delta() const { return delta_; } |
108 EntryType entry() const { return entry_; } | 130 EntryType entry() const { return entry_; } |
109 | 131 |
110 private: | 132 private: |
111 // The base address of the range. The high address does not need to | 133 // 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. | 134 // be stored, because RangeMap uses it as the key to the map. |
113 const AddressType base_; | 135 const AddressType base_; |
114 | 136 |
| 137 // The delta when the range is shrunk down. |
| 138 const AddressType delta_; |
| 139 |
115 // The entry corresponding to a range. | 140 // The entry corresponding to a range. |
116 const EntryType entry_; | 141 const EntryType entry_; |
117 }; | 142 }; |
118 | 143 |
119 // Convenience types. | 144 // Convenience types. |
120 typedef std::map<AddressType, Range> AddressToRangeMap; | 145 typedef std::map<AddressType, Range> AddressToRangeMap; |
121 typedef typename AddressToRangeMap::const_iterator MapConstIterator; | 146 typedef typename AddressToRangeMap::const_iterator MapConstIterator; |
122 typedef typename AddressToRangeMap::value_type MapValue; | 147 typedef typename AddressToRangeMap::value_type MapValue; |
123 | 148 |
| 149 // Whether overlapping ranges can be shrunk down. |
| 150 bool enable_shrink_down_; |
| 151 |
124 // Maps the high address of each range to a EntryType. | 152 // Maps the high address of each range to a EntryType. |
125 AddressToRangeMap map_; | 153 AddressToRangeMap map_; |
126 }; | 154 }; |
127 | 155 |
128 | 156 |
129 } // namespace google_breakpad | 157 } // namespace google_breakpad |
130 | 158 |
131 | 159 |
132 #endif // PROCESSOR_RANGE_MAP_H__ | 160 #endif // PROCESSOR_RANGE_MAP_H__ |
OLD | NEW |