Adding support for overlapping ranges to RangeMap.

When enabled, adding of a new range that overlaps with an existing one can be a successful operation.  The range which ends at the higher address will be shrunk down by moving its start position to a higher address so that it does not overlap anymore.

This change is required to fix http://crbug/611824.  The actual fix will come in a separate CL.

R=mmandlis@chromium.org

Review URL: https://codereview.chromium.org/2029953003 .

1 files changed, 47 insertions, 19 deletions

diff --git a/src/processor/range_map.h b/src/processor/range_map.h
index 2572e492..985d992f 100644
--- a/src/processor/range_map.h
+++ b/src/processor/range_map.h
@@ -52,40 +52,55 @@ template<class, class> class RangeMapSerializer;
 template<typename AddressType, typename EntryType>
 class RangeMap {
  public:
-  RangeMap() : map_() {}
+  RangeMap() : enable_shrink_down_(false), map_() {}
+
+  // |enable_shrink_down| tells whether overlapping ranges can be shrunk down.
+  // If true, then adding a new range that overlaps with an existing one can
+  // be a successful operation.  The range which ends at the higher address
+  // will be shrunk down by moving its start position to a higher address so
+  // that it does not overlap anymore.
+  void SetEnableShrinkDown(bool enable_shrink_down);
 
   // Inserts a range into the map.  Returns false for a parameter error,
   // or if the location of the range would conflict with a range already
-  // stored in the map.
-  bool StoreRange(const AddressType &base,
-                  const AddressType &size,
+  // stored in the map.  If enable_shrink_down is true and there is an overlap
+  // between the current range and some other range (already in the map),
+  // shrink down the range which ends at a higher address.
+  bool StoreRange(const AddressType &base, const AddressType &size,
                   const EntryType &entry);
 
-  // Locates the range encompassing the supplied address.  If there is
-  // no such range, returns false.  entry_base and entry_size, if non-NULL,
-  // are set to the base and size of the entry's range.
+  // Locates the range encompassing the supplied address.  If there is no such
+  // range, returns false.  entry_base, entry_delta, and entry_size, if
+  // non-NULL, are set to the base, delta, and size of the entry's range.
+  // A positive entry delta (> 0) indicates that there was an overlap and the
+  // entry was shrunk down (original start address was increased by delta).
   bool RetrieveRange(const AddressType &address, EntryType *entry,
-                     AddressType *entry_base, AddressType *entry_size) const;
+                     AddressType *entry_base, AddressType *entry_delta,
+                     AddressType *entry_size) const;
 
   // Locates the range encompassing the supplied address, if one exists.
   // If no range encompasses the supplied address, locates the nearest range
   // to the supplied address that is lower than the address.  Returns false
-  // if no range meets these criteria.  entry_base and entry_size, if
-  // non-NULL, are set to the base and size of the entry's range.
+  // if no range meets these criteria.  entry_base, entry_delta, and entry_size,
+  // if non-NULL, are set to the base, delta, and size of the entry's range.
+  // A positive entry delta (> 0) indicates that there was an overlap and the
+  // entry was shrunk down (original start address was increased by delta).
   bool RetrieveNearestRange(const AddressType &address, EntryType *entry,
-                            AddressType *entry_base, AddressType *entry_size)
-                            const;
+                            AddressType *entry_base, AddressType *entry_delta,
+                            AddressType *entry_size) const;
 
   // Treating all ranges as a list ordered by the address spaces that they
   // occupy, locates the range at the index specified by index.  Returns
-  // false if index is larger than the number of ranges stored.  entry_base
-  // and entry_size, if non-NULL, are set to the base and size of the entry's
-  // range.
+  // false if index is larger than the number of ranges stored.  entry_base,
+  // entry_delta, and entry_size, if non-NULL, are set to the base, delta, and
+  // size of the entry's range.
+  // A positive entry delta (> 0) indicates that there was an overlap and the
+  // entry was shrunk down (original start address was increased by delta).
   //
   // RetrieveRangeAtIndex is not optimized for speedy operation.
   bool RetrieveRangeAtIndex(int index, EntryType *entry,
-                            AddressType *entry_base, AddressType *entry_size)
-                            const;
+                            AddressType *entry_base, AddressType *entry_delta,
+                            AddressType *entry_size) const;
 
   // Returns the number of ranges stored in the RangeMap.
   int GetCount() const;
@@ -99,12 +114,19 @@ class RangeMap {
   friend class ModuleComparer;
   friend class RangeMapSerializer<AddressType, EntryType>;
 
+  // Same a StoreRange() with the only exception that the |delta| can be
+  // passed in.
+  bool StoreRangeInternal(const AddressType &base, const AddressType &delta,
+                          const AddressType &size, const EntryType &entry);
+
   class Range {
    public:
-    Range(const AddressType &base, const EntryType &entry)
-        : base_(base), entry_(entry) {}
+    Range(const AddressType &base, const AddressType &delta,
+          const EntryType &entry)
+        : base_(base), delta_(delta), entry_(entry) {}
 
     AddressType base() const { return base_; }
+    AddressType delta() const { return delta_; }
     EntryType entry() const { return entry_; }
 
    private:
@@ -112,6 +134,9 @@ class RangeMap {
     // be stored, because RangeMap uses it as the key to the map.
     const AddressType base_;
 
+    // The delta when the range is shrunk down.
+    const AddressType delta_;
+
     // The entry corresponding to a range.
     const EntryType entry_;
   };
@@ -121,6 +146,9 @@ class RangeMap {
   typedef typename AddressToRangeMap::const_iterator MapConstIterator;
   typedef typename AddressToRangeMap::value_type MapValue;
 
+  // Whether overlapping ranges can be shrunk down.
+  bool enable_shrink_down_;
+
   // Maps the high address of each range to a EntryType.
   AddressToRangeMap map_;
 };