trace: reimplement the DTRACE function so it doesn't use a vector

[gem5.git] / src / base / range_map.hh

diff --git a/src/base/range_map.hh b/src/base/range_map.hh
index 17ecb929003b7b44e196d672e56fbc23dea9de53..7714a00496c66ca3e3771ce879657fc895375478 100644 (file)
--- a/src/base/range_map.hh
+++ b/src/base/range_map.hh
@@ -31,10 +31,10 @@
 #ifndef __BASE_RANGE_MAP_HH__
 #define __BASE_RANGE_MAP_HH__
 
-#include "base/range.hh"
-
 #include <map>
 
+#include "base/range.hh"
+
 template <class T,class V>
 class range_map
 {
@@ -46,15 +46,20 @@ class range_map
     typedef typename RangeMap::iterator iterator;
 
     template <class U>
-    const iterator find(const Range<U> &r)
+    const iterator
+    find(const Range<U> &r)
     {
         iterator i;
 
         i = tree.upper_bound(r);
 
-        if (i == tree.begin())
-            // Nothing could match, so return end()
-            return tree.end();
+        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--;
 
@@ -65,7 +70,15 @@ class range_map
     }
 
     template <class U>
-    bool intersect(const Range<U> &r)
+    const iterator
+    find(const U &r)
+    {
+        return find(RangeSize(r, 1));
+    }
+
+    template <class U>
+    bool
+    intersect(const Range<U> &r)
     {
         iterator i;
         i = find(r);
@@ -76,7 +89,8 @@ class range_map
 
 
     template <class U,class W>
-    iterator insert(const Range<U> &r, const W d)
+    iterator
+    insert(const Range<U> &r, const W d)
     {
         if (intersect(r))
             return tree.end();
@@ -84,46 +98,177 @@ class range_map
         return tree.insert(std::make_pair<Range<T>,V>(r, d)).first;
     }
 
-    size_t erase(T k)
+    size_t
+    erase(T k)
     {
         return tree.erase(k);
     }
 
-    void erase(iterator p)
+    void
+    erase(iterator p)
     {
         tree.erase(p);
     }
 
-    void erase(iterator p, iterator q)
+    void
+    erase(iterator p, iterator q)
     {
         tree.erase(p,q);
     }
 
-    void clear()
+    void
+    clear()
     {
         tree.erase(tree.begin(), tree.end());
     }
 
-    iterator begin()
+    iterator
+    begin()
     {
         return tree.begin();
     }
 
-    iterator end()
+    iterator
+    end()
     {
         return tree.end();
     }
 
-    size_t size()
+    size_t
+    size()
     {
         return tree.size();
     }
 
-    bool empty()
+    bool
+    empty()
     {
         return tree.empty();
     }
 };
 
 
+template <class T,class V>
+class range_multimap
+{
+  private:
+    typedef std::multimap<Range<T>,V> RangeMap;
+    RangeMap tree;
+
+  public:
+    typedef typename RangeMap::iterator iterator;
+
+    template <class U>
+    std::pair<iterator,iterator> find(const Range<U> &r)
+    {
+        iterator i;
+        iterator j;
+
+        i = tree.lower_bound(r);
+
+        if (i == tree.begin()) {
+          if (i->first.start <= r.end && i->first.end >= r.start)
+                return std::make_pair<iterator, iterator>(i,i);
+          else
+            // Nothing could match, so return end()
+            return std::make_pair<iterator, iterator>(tree.end(), tree.end());
+        }
+        i--;
+
+        if (i->first.start <= r.end && i->first.end >= r.start) {
+            // we have at least one match
+            j = i;
+
+            i--;
+            while (i->first.start <= r.end && i->first.end >=
+                    r.start) {
+                if (i == tree.begin())
+                    break;
+                i--;
+            }
+            if (i == tree.begin() && i->first.start <= r.end && i->first.end >=
+                                        r.start)
+                return std::make_pair<iterator, iterator>(i,j);
+            i++;
+            return std::make_pair<iterator, iterator>(i,j);
+
+        }
+
+        return std::make_pair<iterator, iterator>(tree.end(), tree.end());
+    }
+
+    template <class U>
+    bool
+    intersect(const Range<U> &r)
+    {
+        std::pair<iterator,iterator> p;
+        p = find(r);
+        if (p.first != tree.end())
+            return true;
+        return false;
+    }
+
+
+    template <class U,class W>
+    iterator
+    insert(const Range<U> &r, const W d)
+    {
+        std::pair<iterator,iterator> p;
+        p = find(r);
+        if (p.first->first.start == r.start && p.first->first.end == r.end ||
+                p.first == tree.end())
+            return tree.insert(std::make_pair<Range<T>,V>(r, d));
+        else
+            return tree.end();
+    }
+
+    size_t
+    erase(T k)
+    {
+        return tree.erase(k);
+    }
+
+    void
+    erase(iterator p)
+    {
+        tree.erase(p);
+    }
+
+    void
+    erase(iterator p, iterator q)
+    {
+        tree.erase(p,q);
+    }
+
+    void
+    clear()
+    {
+        tree.erase(tree.begin(), tree.end());
+    }
+
+    iterator
+    begin()
+    {
+        return tree.begin();
+    }
+
+    iterator
+    end()
+    {
+        return tree.end();
+    }
+
+    size_t
+    size()
+    {
+        return tree.size();
+    }
+
+    bool
+    empty()
+    {
+        return tree.empty();
+    }
+};
+
 #endif //__BASE_RANGE_MAP_HH__