summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/base/range_map.hh61
1 files 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();
}