diff options
| -rw-r--r-- | src/base/addr_range_map.hh | 53 |
1 files changed, 52 insertions, 1 deletions
diff --git a/src/base/addr_range_map.hh b/src/base/addr_range_map.hh index 5c627bef5..417d66346 100644 --- a/src/base/addr_range_map.hh +++ b/src/base/addr_range_map.hh @@ -54,7 +54,7 @@ * address decoding. The value stored is a template type and can be * e.g. a port identifier, or a pointer. */ -template <typename V> +template <typename V, int max_cache_size=0> class AddrRangeMap { private: @@ -124,18 +124,23 @@ class AddrRangeMap 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()); } @@ -177,6 +182,31 @@ class AddrRangeMap 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 @@ -190,8 +220,20 @@ class AddrRangeMap const_iterator find(const AddrRange &r, std::function<bool(const AddrRange)> 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()) @@ -202,6 +244,7 @@ class AddrRangeMap do { i = next; if (cond(i->first)) { + addNewEntryToCache(i); return i; } // Keep looking if the next range merges with the current one. @@ -212,6 +255,14 @@ class AddrRangeMap } 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<const_iterator> cache; }; #endif //__BASE_ADDR_RANGE_MAP_HH__ |