1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
|
// Copyright (C) 2006 Google Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
// range_map.h: Range maps.
//
// A range map associates a range of addresses with a specific object. This
// is useful when certain objects of variable size are located within an
// address space. The range map makes it simple to determine which object is
// associated with a specific address, which may be any address within the
// range associated with an object.
//
// Author: Mark Mentovai
#ifndef PROCESSOR_RANGE_MAP_H__
#define PROCESSOR_RANGE_MAP_H__
#include <map>
namespace google_airbag {
template<typename AddressType, typename EntryType>
class RangeMap {
public:
RangeMap() : map_() {}
// Inserts a range into the map. Returns false for a parameter error,
// or if the location of the range would conflict with a range already
// stored in the map.
bool StoreRange(const AddressType &base,
const AddressType &size,
const EntryType &entry);
// Locates the range encompassing the supplied address. If there is
// no such range, or if there is a parameter error, returns false.
bool RetrieveRange(const AddressType &address, EntryType *entry) const;
// Empties the range map, restoring it to the state it was when it was
// initially created.
void Clear();
private:
class Range {
public:
Range(const AddressType &base, const EntryType &entry)
: base_(base), entry_(entry) {}
AddressType base() const { return base_; }
EntryType entry() const { return entry_; }
private:
// The base address of the range. The high address does not need to
// be stored, because RangeMap uses it as the key to the map.
const AddressType base_;
// The entry corresponding to a range.
const EntryType entry_;
};
// Convenience types.
typedef std::map<AddressType, Range> AddressToRangeMap;
typedef typename AddressToRangeMap::const_iterator const_iterator;
typedef typename AddressToRangeMap::value_type value_type;
// Maps the high address of each range to a EntryType.
AddressToRangeMap map_;
};
template<typename AddressType, typename EntryType>
bool RangeMap<AddressType, EntryType>::StoreRange(const AddressType &base,
const AddressType &size,
const EntryType &entry) {
AddressType high = base + size - 1;
// Check for undersize or overflow.
if (size <= 0 || high < base)
return false;
// Ensure that this range does not overlap with another one already in the
// map.
const_iterator iterator_base = map_.lower_bound(base);
const_iterator iterator_high = map_.lower_bound(high);
if (iterator_base != iterator_high) {
// Some other range begins in the space used by this range. It may be
// contained within the space used by this range, or it may extend lower.
// Regardless, it is an error.
return false;
}
if (iterator_high != map_.end()) {
if (iterator_high->second.base() <= high) {
// The range above this one overlaps with this one. It may fully
// contain this range, or it may begin within this range and extend
// higher. Regardless, it's an error.
return false;
}
}
// Store the range in the map by its high address, so that lower_bound can
// be used to quickly locate a range by address.
map_.insert(value_type(high, Range(base, entry)));
return true;
}
template<typename AddressType, typename EntryType>
bool RangeMap<AddressType, EntryType>::RetrieveRange(
const AddressType &address, EntryType *entry) const {
if (!entry)
return false;
const_iterator iterator = map_.lower_bound(address);
if (iterator == map_.end())
return false;
// The map is keyed by the high address of each range, so |address| is
// guaranteed to be lower than the range's high address. If |range| is
// not directly preceded by another range, it's possible for address to
// be below the range's low address, though. When that happens, address
// references something not within any range, so return false.
if (address < iterator->second.base())
return false;
*entry = iterator->second.entry();
return true;
}
template<typename AddressType, typename EntryType>
void RangeMap<AddressType, EntryType>::Clear() {
map_.clear();
}
} // namespace google_airbag
#endif // PROCESSOR_RANGE_MAP_H__
|
