gem5
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
addr_range_map.hh
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2012 ARM Limited
3  * All rights reserved
4  *
5  * The license below extends only to copyright in the software and shall
6  * not be construed as granting a license to any other intellectual
7  * property including but not limited to intellectual property relating
8  * to a hardware implementation of the functionality of the software
9  * licensed hereunder. You may use the software subject to the license
10  * terms below provided that you ensure that this notice is replicated
11  * unmodified and in its entirety in all distributions of the software,
12  * modified or unmodified, in source code or in binary form.
13  *
14  * Copyright (c) 2006 The Regents of The University of Michigan
15  * All rights reserved.
16  *
17  * Redistribution and use in source and binary forms, with or without
18  * modification, are permitted provided that the following conditions are
19  * met: redistributions of source code must retain the above copyright
20  * notice, this list of conditions and the following disclaimer;
21  * redistributions in binary form must reproduce the above copyright
22  * notice, this list of conditions and the following disclaimer in the
23  * documentation and/or other materials provided with the distribution;
24  * neither the name of the copyright holders nor the names of its
25  * contributors may be used to endorse or promote products derived from
26  * this software without specific prior written permission.
27  *
28  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
29  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
30  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
31  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
32  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
33  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
34  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
35  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
36  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
37  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
38  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
39  *
40  * Authors: Ali Saidi
41  * Andreas Hansson
42  */
43 
44 #ifndef __BASE_ADDR_RANGE_MAP_HH__
45 #define __BASE_ADDR_RANGE_MAP_HH__
46 
47 #include <map>
48 #include <utility>
49 
50 #include "base/addr_range.hh"
51 
57 template <typename V>
59 {
60  private:
61  typedef std::map<AddrRange, V> RangeMap;
63 
64  public:
65  typedef typename RangeMap::iterator iterator;
66  typedef typename RangeMap::const_iterator const_iterator;
67 
69  find(const AddrRange &r) const
70  {
71  if (tree.empty())
72  return tree.end();
73 
74  const_iterator i = tree.upper_bound(r);
75 
76  if (i == tree.begin()) {
77  if (i->first.intersects(r)) {
78  return i;
79  } else {
80  return tree.end();
81  }
82  }
83 
84  --i;
85 
86  if (i->first.intersects(r))
87  return i;
88 
89  // if we are looking at an interleaved range, also step
90  // backwards through the ranges while we are looking at ranges
91  // that are part of the same contigous chunk
92  if (i->first.interleaved()) {
93  AddrRange orig_range = i->first;
94 
95  while (i != tree.begin() && i->first.mergesWith(orig_range)) {
96  --i;
97  if (i->first.intersects(r)) {
98  return i;
99  }
100  }
101 
102  // we could leave the loop based on reaching the first
103  // element, so we must still check for an intersection
104  if (i->first.intersects(r))
105  return i;
106  }
107 
108  return tree.end();
109  }
110 
112  find(const Addr &r) const
113  {
114  return find(RangeSize(r, 1));
115  }
116 
117  bool
118  intersect(const AddrRange &r) const
119  {
120  return find(r) != tree.end();
121  }
122 
124  insert(const AddrRange &r, const V& d)
125  {
126  if (intersect(r))
127  return tree.end();
128 
129  return tree.insert(std::make_pair(r, d)).first;
130  }
131 
132  void
134  {
135  tree.erase(p);
136  }
137 
138  void
140  {
141  tree.erase(p,q);
142  }
143 
144  void
146  {
147  tree.erase(tree.begin(), tree.end());
148  }
149 
151  begin() const
152  {
153  return tree.begin();
154  }
155 
156  iterator
158  {
159  return tree.begin();
160  }
161 
163  end() const
164  {
165  return tree.end();
166  }
167 
168  iterator
169  end()
170  {
171  return tree.end();
172  }
173 
174  std::size_t
175  size() const
176  {
177  return tree.size();
178  }
179 
180  bool
181  empty() const
182  {
183  return tree.empty();
184  }
185 };
186 
187 #endif //__BASE_ADDR_RANGE_MAP_HH__
const_iterator end() const
AddrRange RangeSize(Addr start, Addr size)
Definition: addr_range.hh:398
const_iterator insert(const AddrRange &r, const V &d)
Bitfield< 7 > i
Definition: miscregs.hh:1378
bool intersect(const AddrRange &r) const
std::map< AddrRange, V > RangeMap
std::size_t size() const
The AddrRange class encapsulates an address range, and supports a number of tests to check if two ran...
Definition: addr_range.hh:72
void erase(iterator p, iterator q)
Bitfield< 27 > q
Definition: miscregs.hh:1367
RangeMap::iterator iterator
Bitfield< 9 > d
Definition: miscregs.hh:1375
const_iterator begin() const
const_iterator find(const Addr &r) const
The AddrRangeMap uses an STL map to implement an interval tree for address decoding.
uint64_t Addr
Address type This will probably be moved somewhere else in the near future.
Definition: types.hh:142
bool empty() const
const_iterator find(const AddrRange &r) const
iterator begin()
iterator end()
RangeMap::const_iterator const_iterator
Bitfield< 0 > p
void erase(iterator p)

Generated on Fri Jun 9 2017 13:03:40 for gem5 by doxygen 1.8.6