gem5  v21.1.0.2
addr_range_map.hh
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2012, 2018 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 
41 #ifndef __BASE_ADDR_RANGE_MAP_HH__
42 #define __BASE_ADDR_RANGE_MAP_HH__
43 
44 #include <cstddef>
45 #include <functional>
46 #include <list>
47 #include <map>
48 #include <utility>
49 
50 #include "base/addr_range.hh"
51 #include "base/types.hh"
52 
53 namespace gem5
54 {
55 
61 template <typename V, int max_cache_size=0>
63 {
64  private:
65  typedef std::map<AddrRange, V> RangeMap;
66 
67  public:
72  typedef typename RangeMap::iterator iterator;
73  typedef typename RangeMap::const_iterator const_iterator; // end of api_addr_range
75 
90  contains(const AddrRange &r) const
91  {
92  return find(r, [r](const AddrRange r1) { return r.isSubset(r1); });
93  }
94  iterator
96  {
97  return find(r, [r](const AddrRange r1) { return r.isSubset(r1); });
98  } // end of api_addr_range
100 
115  contains(Addr r) const
116  {
117  return contains(RangeSize(r, 1));
118  }
119  iterator
121  {
122  return contains(RangeSize(r, 1));
123  } // end of api_addr_range
125 
140  intersects(const AddrRange &r) const
141  {
142  return find(r, [r](const AddrRange r1) { return r.intersects(r1); });
143  }
144  iterator
146  {
147  return find(r, [r](const AddrRange r1) { return r.intersects(r1); });
148  } // end of api_addr_range
150 
154  iterator
155  insert(const AddrRange &r, const V& d)
156  {
157  if (intersects(r) != end())
158  return tree.end();
159 
160  return tree.insert(std::make_pair(r, d)).first;
161  }
162 
166  void
168  {
169  cache.remove(p);
170  tree.erase(p);
171  }
172 
176  void
178  {
179  for (auto it = p; it != q; it++) {
180  cache.remove(p);
181  }
182  tree.erase(p,q);
183  }
184 
188  void
190  {
191  cache.erase(cache.begin(), cache.end());
192  tree.erase(tree.begin(), tree.end());
193  }
194 
199  begin() const
200  {
201  return tree.begin();
202  }
203 
207  iterator
209  {
210  return tree.begin();
211  }
212 
217  end() const
218  {
219  return tree.end();
220  }
221 
225  iterator
226  end()
227  {
228  return tree.end();
229  }
230 
234  std::size_t
235  size() const
236  {
237  return tree.size();
238  }
239 
243  bool
244  empty() const
245  {
246  return tree.empty();
247  }
248 
249  private:
255  void
257  {
258  if (max_cache_size != 0) {
259  // If there's a cache, add this element to it.
260  if (cache.size() >= max_cache_size) {
261  // If the cache is full, move the last element to the
262  // front and overwrite it with the new value. This
263  // avoids creating or destroying elements of the list.
264  auto last = cache.end();
265  last--;
266  *last = it;
267  if (max_cache_size > 1)
268  cache.splice(cache.begin(), cache, last);
269  } else {
270  cache.push_front(it);
271  }
272  }
273  }
274 
286  iterator
287  find(const AddrRange &r, std::function<bool(const AddrRange)> cond)
288  {
289  // Check the cache first
290  for (auto c = cache.begin(); c != cache.end(); c++) {
291  auto it = *c;
292  if (cond(it->first)) {
293  // If this entry matches, promote it to the front
294  // of the cache and return it.
295  cache.splice(cache.begin(), cache, c);
296  return it;
297  }
298  }
299 
300  iterator next = tree.upper_bound(r);
301  if (next != end() && cond(next->first)) {
302  addNewEntryToCache(next);
303  return next;
304  }
305  if (next == begin())
306  return end();
307  next--;
308 
309  iterator i;
310  do {
311  i = next;
312  if (cond(i->first)) {
314  return i;
315  }
316  // Keep looking if the next range merges with the current one.
317  } while (next != begin() &&
318  (--next)->first.mergesWith(i->first));
319 
320  return end();
321  }
322 
324  find(const AddrRange &r, std::function<bool(const AddrRange)> cond) const
325  {
326  return const_cast<AddrRangeMap *>(this)->find(r, cond);
327  }
328 
330 
338 };
339 
340 } // namespace gem5
341 
342 #endif //__BASE_ADDR_RANGE_MAP_HH__
gem5::AddrRangeMap::erase
void erase(iterator p)
Definition: addr_range_map.hh:167
gem5::AddrRangeMap
The AddrRangeMap uses an STL map to implement an interval tree for address decoding.
Definition: addr_range_map.hh:62
gem5::AddrRangeMap::find
const_iterator find(const AddrRange &r, std::function< bool(const AddrRange)> cond) const
Definition: addr_range_map.hh:324
gem5::RangeSize
AddrRange RangeSize(Addr start, Addr size)
Definition: addr_range.hh:661
gem5::AddrRangeMap::empty
bool empty() const
Definition: addr_range_map.hh:244
gem5::AddrRangeMap::find
iterator find(const AddrRange &r, std::function< bool(const AddrRange)> cond)
Find entry that satisfies a condition on an address range.
Definition: addr_range_map.hh:287
gem5::ArmISA::i
Bitfield< 7 > i
Definition: misc_types.hh:66
gem5::AddrRangeMap::contains
const_iterator contains(const AddrRange &r) const
Find entry that contains the given address range.
Definition: addr_range_map.hh:90
gem5::AddrRangeMap::const_iterator
RangeMap::const_iterator const_iterator
Definition: addr_range_map.hh:73
gem5::AddrRangeMap::begin
const_iterator begin() const
Definition: addr_range_map.hh:199
gem5::ArmISA::d
Bitfield< 9 > d
Definition: misc_types.hh:63
gem5::MipsISA::p
Bitfield< 0 > p
Definition: pra_constants.hh:326
gem5::AddrRangeMap::iterator
RangeMap::iterator iterator
Definition: addr_range_map.hh:72
gem5::AddrRangeMap::end
const_iterator end() const
Definition: addr_range_map.hh:217
gem5::AddrRangeMap::intersects
iterator intersects(const AddrRange &r)
Definition: addr_range_map.hh:145
gem5::ArmISA::c
Bitfield< 29 > c
Definition: misc_types.hh:53
gem5::AddrRangeMap::contains
iterator contains(Addr r)
Definition: addr_range_map.hh:120
gem5::Addr
uint64_t Addr
Address type This will probably be moved somewhere else in the near future.
Definition: types.hh:147
gem5::AddrRangeMap::contains
const_iterator contains(Addr r) const
Find entry that contains the given address.
Definition: addr_range_map.hh:115
gem5::AddrRangeMap::clear
void clear()
Definition: addr_range_map.hh:189
gem5::AddrRangeMap::erase
void erase(iterator p, iterator q)
Definition: addr_range_map.hh:177
gem5::AddrRangeMap::contains
iterator contains(const AddrRange &r)
Definition: addr_range_map.hh:95
gem5::AddrRangeMap::addNewEntryToCache
void addNewEntryToCache(iterator it) const
Add an address range map entry to the cache.
Definition: addr_range_map.hh:256
addr_range.hh
gem5::ArmISA::q
Bitfield< 27 > q
Definition: misc_types.hh:55
gem5::AddrRangeMap::intersects
const_iterator intersects(const AddrRange &r) const
Find entry that intersects with the given address range.
Definition: addr_range_map.hh:140
gem5::AddrRangeMap::begin
iterator begin()
Definition: addr_range_map.hh:208
gem5::AddrRangeMap::cache
std::list< iterator > cache
A list of iterator that correspond to the max_cache_size most recently used entries in the address ra...
Definition: addr_range_map.hh:337
types.hh
gem5::AddrRangeMap::RangeMap
std::map< AddrRange, V > RangeMap
Definition: addr_range_map.hh:65
gem5::AddrRangeMap::insert
iterator insert(const AddrRange &r, const V &d)
Definition: addr_range_map.hh:155
gem5::AddrRangeMap::end
iterator end()
Definition: addr_range_map.hh:226
gem5::MipsISA::r
r
Definition: pra_constants.hh:98
gem5::AddrRangeMap::tree
RangeMap tree
Definition: addr_range_map.hh:329
gem5::AddrRange
The AddrRange class encapsulates an address range, and supports a number of tests to check if two ran...
Definition: addr_range.hh:71
std::list< iterator >
gem5
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....
Definition: decoder.cc:40
gem5::ArmISA::cond
cond
Definition: pcstate.hh:62
gem5::AddrRangeMap::size
std::size_t size() const
Definition: addr_range_map.hh:235

Generated on Tue Sep 21 2021 12:24:52 for gem5 by doxygen 1.8.17