From 9d7c715c46f8af4f1c44eada2b7dcb23c55ade3b Mon Sep 17 00:00:00 2001
From: Andreas Hansson <andreas.hansson@arm.com>
Date: Mon, 26 Mar 2012 05:37:00 -0400
Subject: [PATCH] range_map: Enable const find and iteration

This patch adds const access functions to the range_map to enable its use
in a const context, similar to the STL container classes.
---
 src/base/range_map.hh | 61 ++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 55 insertions(+), 6 deletions(-)

diff --git a/src/base/range_map.hh b/src/base/range_map.hh
index d6df32e08..0be228228 100644
--- a/src/base/range_map.hh
+++ b/src/base/range_map.hh
@@ -36,6 +36,12 @@
 
 #include "base/range.hh"
 
+/**
+ * The range_map uses an STL map to implement an interval tree. The
+ * type of both the key (range) and the value are template
+ * parameters. It can, for example, be used for address decoding,
+ * using a range of addresses to map to ports.
+ */
 template <class T,class V>
 class range_map
 {
@@ -45,9 +51,34 @@ class range_map
 
   public:
     typedef typename RangeMap::iterator iterator;
+    typedef typename RangeMap::const_iterator const_iterator;
+
+    template <class U>
+    const_iterator
+    find(const Range<U> &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();
+    }
 
     template <class U>
-    const iterator
+    iterator
     find(const Range<U> &r)
     {
         iterator i;
@@ -62,7 +93,7 @@ class range_map
                 return tree.end();
         }
 
-        i--;
+        --i;
 
         if (i->first.start <= r.end && i->first.end >= r.start)
             return i;
@@ -71,7 +102,14 @@ class range_map
     }
 
     template <class U>
-    const iterator
+    const_iterator
+    find(const U &r) const
+    {
+        return find(RangeSize(r, 1));
+    }
+
+    template <class U>
+    iterator
     find(const U &r)
     {
         return find(RangeSize(r, 1));
@@ -88,7 +126,6 @@ class range_map
         return false;
     }
 
-
     template <class U,class W>
     iterator
     insert(const Range<U> &r, const W d)
@@ -123,12 +160,24 @@ class range_map
         tree.erase(tree.begin(), tree.end());
     }
 
+    const_iterator
+    begin() const
+    {
+        return tree.begin();
+    }
+
     iterator
     begin()
     {
         return tree.begin();
     }
 
+    const_iterator
+    end() const
+    {
+        return tree.end();
+    }
+
     iterator
     end()
     {
@@ -136,13 +185,13 @@ class range_map
     }
 
     size_t
-    size()
+    size() const
     {
         return tree.size();
     }
 
     bool
-    empty()
+    empty() const
     {
         return tree.empty();
     }
-- 
2.30.2