summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/base/addr_range_map.hh124
-rw-r--r--src/mem/physical.cc10
-rw-r--r--src/mem/xbar.cc11
-rw-r--r--src/unittest/rangemaptest.cc11
4 files changed, 95 insertions, 61 deletions
diff --git a/src/base/addr_range_map.hh b/src/base/addr_range_map.hh
index 30bd62456..5c627bef5 100644
--- a/src/base/addr_range_map.hh
+++ b/src/base/addr_range_map.hh
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2012 ARM Limited
+ * Copyright (c) 2012, 2018 ARM Limited
* All rights reserved
*
* The license below extends only to copyright in the software and shall
@@ -59,71 +59,63 @@ class AddrRangeMap
{
private:
typedef std::map<AddrRange, V> RangeMap;
- RangeMap tree;
public:
typedef typename RangeMap::iterator iterator;
typedef typename RangeMap::const_iterator const_iterator;
+ /**
+ * Find entry that contains the given address range
+ *
+ * Searches through the ranges in the address map and returns an
+ * iterator to the entry which range is a superset of the input
+ * address range. Returns end() if none found.
+ *
+ * @param r An input address range
+ * @return An iterator that contains the input address range
+ */
const_iterator
- find(const AddrRange &r) const
+ contains(const AddrRange &r) const
{
- if (tree.empty())
- return tree.end();
-
- const_iterator i = tree.upper_bound(r);
-
- if (i == tree.begin()) {
- if (i->first.intersects(r)) {
- return i;
- } else {
- return tree.end();
- }
- }
-
- --i;
-
- if (i->first.intersects(r))
- return i;
-
- // if we are looking at an interleaved range, also step
- // backwards through the ranges while we are looking at ranges
- // that are part of the same contigous chunk
- if (i->first.interleaved()) {
- AddrRange orig_range = i->first;
-
- while (i != tree.begin() && i->first.mergesWith(orig_range)) {
- --i;
- if (i->first.intersects(r)) {
- return i;
- }
- }
-
- // we could leave the loop based on reaching the first
- // element, so we must still check for an intersection
- if (i->first.intersects(r))
- return i;
- }
-
- return tree.end();
+ return find(r, [r](const AddrRange r1) { return r.isSubset(r1); });
}
+ /**
+ * Find entry that contains the given address
+ *
+ * Searches through the ranges in the address map and returns an
+ * iterator to the entry which range is a superset of the input
+ * address. Returns end() if none found.
+ *
+ * @param r An input address
+ * @return An iterator that contains the input address
+ */
const_iterator
- find(const Addr &r) const
+ contains(Addr r) const
{
- return find(RangeSize(r, 1));
+ return contains(RangeSize(r, 1));
}
- bool
- intersect(const AddrRange &r) const
+ /**
+ * Find entry that intersects with the given address range
+ *
+ * Searches through the ranges in the address map and returns an
+ * iterator to the first entry which range intersects with the
+ * input address.
+ *
+ * @param r An input address
+ * @return An iterator that intersects with the input address range
+ */
+ const_iterator
+ intersects(const AddrRange &r) const
{
- return find(r) != tree.end();
+ return find(r, [r](const AddrRange r1) { return r.intersects(r1); });
}
const_iterator
insert(const AddrRange &r, const V& d)
{
- if (intersect(r))
+ if (intersects(r) != end())
return tree.end();
return tree.insert(std::make_pair(r, d)).first;
@@ -182,6 +174,44 @@ class AddrRangeMap
{
return tree.empty();
}
+
+ private:
+ /**
+ * Find entry that satisfies a condition on an address range
+ *
+ * Searches through the ranges in the address map and returns an
+ * iterator to the entry that satisfies the input conidition on
+ * the input address range. Returns end() if none found.
+ *
+ * @param r An input address range
+ * @param f A condition on an address range
+ * @return An iterator that contains the input address range
+ */
+ const_iterator
+ find(const AddrRange &r, std::function<bool(const AddrRange)> cond) const
+ {
+ const_iterator next = tree.upper_bound(r);
+ if (next != end() && cond(next->first)) {
+ return next;
+ }
+ if (next == begin())
+ return end();
+ next--;
+
+ const_iterator i;
+ do {
+ i = next;
+ if (cond(i->first)) {
+ return i;
+ }
+ // Keep looking if the next range merges with the current one.
+ } while (next != begin() &&
+ (--next)->first.mergesWith(i->first));
+
+ return end();
+ }
+
+ RangeMap tree;
};
#endif //__BASE_ADDR_RANGE_MAP_HH__
diff --git a/src/mem/physical.cc b/src/mem/physical.cc
index 586f1c475..c7dbb3bcb 100644
--- a/src/mem/physical.cc
+++ b/src/mem/physical.cc
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2012, 2014 ARM Limited
+ * Copyright (c) 2012, 2014, 2018 ARM Limited
* All rights reserved
*
* The license below extends only to copyright in the software and shall
@@ -241,7 +241,7 @@ PhysicalMemory::isMemAddr(Addr addr) const
return true;
} else {
// lookup in the interval tree
- const auto& r = addrMap.find(addr);
+ const auto& r = addrMap.contains(addr);
if (r == addrMap.end()) {
// not in the cache, and not in the tree
return false;
@@ -298,7 +298,7 @@ PhysicalMemory::access(PacketPtr pkt)
} else {
// do not update the cache here, as we typically call
// isMemAddr before calling access
- const auto& m = addrMap.find(addr);
+ const auto& m = addrMap.contains(addr);
assert(m != addrMap.end());
m->second->access(pkt);
}
@@ -314,7 +314,7 @@ PhysicalMemory::functionalAccess(PacketPtr pkt)
} else {
// do not update the cache here, as we typically call
// isMemAddr before calling functionalAccess
- const auto& m = addrMap.find(addr);
+ const auto& m = addrMap.contains(addr);
assert(m != addrMap.end());
m->second->functionalAccess(pkt);
}
@@ -406,7 +406,7 @@ PhysicalMemory::unserialize(CheckpointIn &cp)
UNSERIALIZE_CONTAINER(lal_addr);
UNSERIALIZE_CONTAINER(lal_cid);
for (size_t i = 0; i < lal_addr.size(); ++i) {
- const auto& m = addrMap.find(lal_addr[i]);
+ const auto& m = addrMap.contains(lal_addr[i]);
m->second->addLockedAddr(LockedAddr(lal_addr[i], lal_cid[i]));
}
diff --git a/src/mem/xbar.cc b/src/mem/xbar.cc
index db0bf180e..1984a94aa 100644
--- a/src/mem/xbar.cc
+++ b/src/mem/xbar.cc
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2011-2015 ARM Limited
+ * Copyright (c) 2011-2015, 2018 ARM Limited
* All rights reserved
*
* The license below extends only to copyright in the software and shall
@@ -333,7 +333,7 @@ BaseXBar::findPort(Addr addr)
return dest_id;
// Check the address map interval tree
- auto i = portMap.find(addr);
+ auto i = portMap.contains(addr);
if (i != portMap.end()) {
dest_id = i->second;
updatePortCache(dest_id, i->first);
@@ -420,8 +420,9 @@ BaseXBar::recvRangeChange(PortID master_port_id)
DPRINTF(AddrRanges, "Adding range %s for id %d\n",
r.to_string(), master_port_id);
if (portMap.insert(r, master_port_id) == portMap.end()) {
- PortID conflict_id = portMap.find(r)->second;
- fatal("%s has two ports responding within range %s:\n\t%s\n\t%s\n",
+ PortID conflict_id = portMap.intersects(r)->second;
+ fatal("%s has two ports responding within range "
+ "%s:\n\t%s\n\t%s\n",
name(),
r.to_string(),
masterPorts[master_port_id]->getSlavePort().name(),
@@ -496,7 +497,7 @@ BaseXBar::recvRangeChange(PortID master_port_id)
}
}
- // also check that no range partially overlaps with the
+ // also check that no range partially intersects with the
// default range, this has to be done after all ranges are set
// as there are no guarantees for when the default range is
// update with respect to the other ones
diff --git a/src/unittest/rangemaptest.cc b/src/unittest/rangemaptest.cc
index 6975f66ef..88e1c4d66 100644
--- a/src/unittest/rangemaptest.cc
+++ b/src/unittest/rangemaptest.cc
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2012 ARM Limited
+ * Copyright (c) 2012, 2018 ARM Limited
* All rights reserved
*
* The license below extends only to copyright in the software and shall
@@ -59,11 +59,14 @@ main()
i = r.insert(RangeIn(60, 90), 3);
assert(i != r.end());
- i = r.find(RangeIn(20, 30));
+ i = r.intersects(RangeIn(20, 30));
assert(i != r.end());
cout << i->first.to_string() << " " << i->second << endl;
- i = r.find(RangeIn(55, 55));
+ i = r.contains(RangeIn(55, 55));
+ assert(i == r.end());
+
+ i = r.intersects(RangeIn(55, 55));
assert(i == r.end());
i = r.insert(RangeIn(0, 12), 1);
@@ -72,7 +75,7 @@ main()
i = r.insert(RangeIn(0, 9), 1);
assert(i != r.end());
- i = r.find(RangeIn(20, 30));
+ i = r.contains(RangeIn(20, 30));
assert(i != r.end());
cout << i->first.to_string() << " " << i->second << endl;
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-03 05:42:31 +0000