X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=src%2Fbase%2Faddr_range_map.hh;h=f43671ce5fe79ca30d4ae1c5483eef7777ae72ac;hb=0c50a0b4fe3956f9d2e08e75d47c9cbd79bf0268;hp=c35befdce32721898aa5b1381be31249c31edfbe;hpb=ffb6aec603c38e16ae91ea975c16fc3e8fb337e5;p=gem5.git diff --git a/src/base/addr_range_map.hh b/src/base/addr_range_map.hh index c35befdce..f43671ce5 100644 --- a/src/base/addr_range_map.hh +++ b/src/base/addr_range_map.hh @@ -1,5 +1,5 @@ /* - * Copyright (c) 2012 ARM Limited + * Copyright (c) 2012, 2018 ARM Limited * All rights reserved * * The license below extends only to copyright in the software and shall @@ -44,125 +44,107 @@ #ifndef __BASE_ADDR_RANGE_MAP_HH__ #define __BASE_ADDR_RANGE_MAP_HH__ +#include +#include +#include #include #include #include "base/addr_range.hh" +#include "base/types.hh" /** * The AddrRangeMap uses an STL map to implement an interval tree for * address decoding. The value stored is a template type and can be * e.g. a port identifier, or a pointer. */ -template +template class AddrRangeMap { private: typedef std::map RangeMap; - RangeMap tree; public: typedef typename RangeMap::iterator iterator; typedef typename RangeMap::const_iterator const_iterator; + /** + * Find entry that contains the given address range + * + * Searches through the ranges in the address map and returns an + * iterator to the entry which range is a superset of the input + * address range. Returns end() if none found. + * + * @param r An input address range + * @return An iterator that contains the input address range + */ const_iterator - find(const AddrRange &r) const - { - const_iterator i; - - i = tree.upper_bound(r); - - if (i == tree.begin()) { - if (i->first.start <= r.end && i->first.end >= r.start) - return i; - else - // Nothing could match, so return end() - return tree.end(); - } - - --i; - - if (i->first.start <= r.end && i->first.end >= r.start) - return i; - - return tree.end(); - } - - iterator - find(const AddrRange &r) + contains(const AddrRange &r) const { - iterator i; - - i = tree.upper_bound(r); - - if (i == tree.begin()) { - if (i->first.start <= r.end && i->first.end >= r.start) - return i; - else - // Nothing could match, so return end() - return tree.end(); - } - - --i; - - if (i->first.start <= r.end && i->first.end >= r.start) - return i; - - return tree.end(); + return find(r, [r](const AddrRange r1) { return r.isSubset(r1); }); } + /** + * Find entry that contains the given address + * + * Searches through the ranges in the address map and returns an + * iterator to the entry which range is a superset of the input + * address. Returns end() if none found. + * + * @param r An input address + * @return An iterator that contains the input address + */ const_iterator - find(const Addr &r) const + contains(Addr r) const { - return find(RangeSize(r, 1)); + return contains(RangeSize(r, 1)); } - iterator - find(const Addr &r) - { - return find(RangeSize(r, 1)); - } - - bool - intersect(const AddrRange &r) + /** + * Find entry that intersects with the given address range + * + * Searches through the ranges in the address map and returns an + * iterator to the first entry which range intersects with the + * input address. + * + * @param r An input address + * @return An iterator that intersects with the input address range + */ + const_iterator + intersects(const AddrRange &r) const { - iterator i; - i = find(r); - if (i != tree.end()) - return true; - return false; + return find(r, [r](const AddrRange r1) { return r.intersects(r1); }); } - iterator + const_iterator insert(const AddrRange &r, const V& d) { - if (intersect(r)) + if (intersects(r) != end()) return tree.end(); return tree.insert(std::make_pair(r, d)).first; } - std::size_t - erase(Addr k) - { - return tree.erase(k); - } - void erase(iterator p) { + cache.remove(p); tree.erase(p); } void erase(iterator p, iterator q) { + for (auto it = p; it != q; it++) { + cache.remove(p); + } tree.erase(p,q); } void clear() { + cache.erase(cache.begin(), cache.end()); tree.erase(tree.begin(), tree.end()); } @@ -201,6 +183,90 @@ class AddrRangeMap { return tree.empty(); } + + private: + /** + * Add an address range map entry to the cache. + * + * @param it Iterator to the entry in the address range map + */ + void + addNewEntryToCache(const_iterator it) const + { + if (max_cache_size != 0) { + // If there's a cache, add this element to it. + if (cache.size() >= max_cache_size) { + // If the cache is full, move the last element to the + // front and overwrite it with the new value. This + // avoids creating or destroying elements of the list. + auto last = cache.end(); + last--; + *last = it; + if (max_cache_size > 1) + cache.splice(cache.begin(), cache, last); + } else { + cache.push_front(it); + } + } + } + + /** + * Find entry that satisfies a condition on an address range + * + * Searches through the ranges in the address map and returns an + * iterator to the entry that satisfies the input conidition on + * the input address range. Returns end() if none found. + * + * @param r An input address range + * @param f A condition on an address range + * @return An iterator that contains the input address range + */ + const_iterator + find(const AddrRange &r, std::function cond) const + { + // Check the cache first + for (auto c = cache.begin(); c != cache.end(); c++) { + auto it = *c; + if (cond(it->first)) { + // If this entry matches, promote it to the front + // of the cache and return it. + cache.splice(cache.begin(), cache, c); + return it; + } + } + + const_iterator next = tree.upper_bound(r); + if (next != end() && cond(next->first)) { + addNewEntryToCache(next); + return next; + } + if (next == begin()) + return end(); + next--; + + const_iterator i; + do { + i = next; + if (cond(i->first)) { + addNewEntryToCache(i); + return i; + } + // Keep looking if the next range merges with the current one. + } while (next != begin() && + (--next)->first.mergesWith(i->first)); + + return end(); + } + + RangeMap tree; + + /** + * A list of iterator that correspond to the max_cache_size most + * recently used entries in the address range map. This mainly + * used to optimize lookups. The elements in the list should + * always be valid iterators of the tree. + */ + mutable std::list cache; }; #endif //__BASE_ADDR_RANGE_MAP_HH__