From e688b95b63eaf219f5bea31b68494799106c6b58 Mon Sep 17 00:00:00 2001
From: =?utf8?q?Jos=C3=A9=20Fonseca?= <jose.r.fonseca@gmail.com>
Date: Thu, 1 Mar 2012 17:46:49 +0000
Subject: [PATCH] Warn when intersecting regions are found.

---
 retrace_stdc.cpp | 57 +++++++++++++++++++++++++++++++++---------------
 1 file changed, 39 insertions(+), 18 deletions(-)

diff --git a/retrace_stdc.cpp b/retrace_stdc.cpp
index d92590a..0db72b2 100644
--- a/retrace_stdc.cpp
+++ b/retrace_stdc.cpp
@@ -47,30 +47,45 @@ struct Region
 typedef std::map<unsigned long long, Region> RegionMap;
 static RegionMap regionMap;
 
-// Iterator to the first region that contains the address
+
+static inline bool
+contains(RegionMap::iterator &it, unsigned long long address) {
+    return it->first <= address && (it->first + it->second.size) > address;
+}
+
+
+static inline bool
+intersects(RegionMap::iterator &it, unsigned long long start, unsigned long long size) {
+    unsigned long it_start = it->first;
+    unsigned long it_stop  = it->first + it->second.size;
+    unsigned long stop = start + size;
+    return it_start < stop && start < it_stop;
+}
+
+
+// Iterator to the first region that contains the address, or the first after
 static RegionMap::iterator
 lowerBound(unsigned long long address) {
     RegionMap::iterator it = regionMap.lower_bound(address);
 
-    while (it != regionMap.begin() &&
-           it != regionMap.end() &&
-           it->first + it->second. size > address) {
-        --it;
+    while (it != regionMap.begin()) {
+        RegionMap::iterator pred = it;
+        --pred;
+        if (contains(pred, address)) {
+            it = pred;
+        } else {
+            break;
+        }
     }
 
     return it;
 }
 
-// Iterator to the first region that not contains the address
+// Iterator to the first region that starts after the address
 static RegionMap::iterator
 upperBound(unsigned long long address) {
     RegionMap::iterator it = regionMap.upper_bound(address);
 
-    while (it != regionMap.end() &&
-           it->first + it->second.size > address) {
-        ++it;
-    }
-
     return it;
 }
 
@@ -83,14 +98,21 @@ addRegion(unsigned long long address, void *buffer, unsigned long long size)
         return;
     }
 
-    // Forget all regions that intersect this new one.
+#ifndef NDEBUG
+    RegionMap::iterator start = lowerBound(address);
+    RegionMap::iterator stop = upperBound(address + size);
     if (0) {
-        RegionMap::iterator start = lowerBound(address);
-        if (start != regionMap.end()) {
-            RegionMap::iterator stop = upperBound(address + size);
-            regionMap.erase(start, stop);
+        // Forget all regions that intersect this new one.
+        regionMap.erase(start, stop);
+    } else {
+        for (RegionMap::iterator it = start; it != stop; ++it) {
+            std::cerr << std::hex << "warning: "
+                "region 0x" << address << "-0x" << (address + size) << " "
+                "intersects existing region 0x" << it->first << "-0x" << (it->first + it->second.size) << "\n" << std::dec;
+            assert(intersects(it, address, size));
         }
     }
+#endif
 
     assert(buffer);
 
@@ -114,8 +136,7 @@ lookupRegion(unsigned long long address) {
         }
     }
 
-    assert(it->first <= address);
-    assert(it->first + it->second.size >= address);
+    assert(contains(it, address));
     return it;
 }
 
-- 
2.45.2