diff options
| -rw-r--r-- | src/base/range_map.hh | 61 |
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(); } |