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