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__