range_map.h revision e5dc60822e5938fea2ae892ccddb906641ba174e 
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
47namespace google_breakpad {
48
49
50template<typename AddressType, typename EntryType>
51class RangeMap {
52 public:
53  RangeMap() : map_() {}
54
55  // Inserts a range into the map.  Returns false for a parameter error,
56  // or if the location of the range would conflict with a range already
57  // stored in the map.
58  bool StoreRange(const AddressType &base,
59                  const AddressType &size,
60                  const EntryType &entry);
61
62  // Locates the range encompassing the supplied address.  If there is
63  // no such range, or if there is a parameter error, returns false.
64  // entry_base and entry_size, if non-NULL, are set to the base and size
65  // of the entry's range.
66  bool RetrieveRange(const AddressType &address, EntryType *entry,
67                     AddressType *entry_base, AddressType *entry_size) const;
68
69  // Locates the range encompassing the supplied address, if one exists.
70  // If no range encompasses the supplied address, locates the nearest range
71  // to the supplied address that is lower than the address.  Returns false
72  // if no range meets these criteria.  entry_base and entry_size, if
73  // non-NULL, are set to the base and size of the entry's range.
74  bool RetrieveNearestRange(const AddressType &address, EntryType *entry,
75                            AddressType *entry_base, AddressType *entry_size)
76                            const;
77
78  // Treating all ranges as a list ordered by the address spaces that they
79  // occupy, locates the range at the index specified by index.  Returns
80  // false if index is larger than the number of ranges stored, or if another
81  // parameter error occurs.  entry_base and entry_size, if non-NULL, are set
82  // to the base and size of the entry's range.
83  //
84  // RetrieveRangeAtIndex is not optimized for speedy operation.
85  bool RetrieveRangeAtIndex(int index, EntryType *entry,
86                            AddressType *entry_base, AddressType *entry_size)
87                            const;
88
89  // Returns the number of ranges stored in the RangeMap.
90  int GetCount() const;
91
92  // Empties the range map, restoring it to the state it was when it was
93  // initially created.
94  void Clear();
95
96 private:
97  class Range {
98   public:
99    Range(const AddressType &base, const EntryType &entry)
100        : base_(base), entry_(entry) {}
101
102    AddressType base() const { return base_; }
103    EntryType entry() const { return entry_; }
104
105   private:
106    // The base address of the range.  The high address does not need to
107    // be stored, because RangeMap uses it as the key to the map.
108    const AddressType base_;
109
110    // The entry corresponding to a range.
111    const EntryType entry_;
112  };
113
114  // Convenience types.
115  typedef std::map<AddressType, Range> AddressToRangeMap;
116  typedef typename AddressToRangeMap::const_iterator MapConstIterator;
117  typedef typename AddressToRangeMap::value_type MapValue;
118
119  // Maps the high address of each range to a EntryType.
120  AddressToRangeMap map_;
121};
122
123
124}  // namespace google_breakpad
125
126
127#endif  // PROCESSOR_RANGE_MAP_H__
128