Adding support for overlapping ranges to RangeMap.

src/processor/range_map.h

Index: src/processor/range_map.h
diff --git a/src/processor/range_map.h b/src/processor/range_map.h
index 2572e4927d85d15a747d07c268599360ed777961..30545484d5d6a8b033898b68b5550c71c58ac7dd 100644
--- a/src/processor/range_map.h
+++ b/src/processor/range_map.h
@@ -52,40 +52,49 @@ 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,
-                  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.
+  // 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 hugher address.
+  bool StoreRange(const AddressType &base, const AddressType &delta,

[Mark Mentovai, 2016/06/02 21:43:53]

Is anything ever stored with a delta other than 0, now or in the future? If
delta is just modified internally when shrink-down is on, but is always 0 here,
then we can eliminate this parameter.

If nonzero deltas are only used internally, provide a private method
(StoreRangeInternal()?) that accepts a delta argument, and remove the delta
argument from this public version. Have the public one call the internal private
version by passing 0 for the delta.

[ivanpe, 2016/06/02 22:54:02]

Yes, I agree that moving the delta to a private method would be better.
Initially I thought that we should keep it for future use, but after revisiting
this idea, I think that even if we decide to set a "delta" from the breakpad
client (which is likely not happening) it will have a slightly different meaning
so we are not going to use this same parameter for that anyways.

I moved it to a private StoreRangeInternal() method.

+                  const AddressType &size, const EntryType &entry);
+
+  // 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.
   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.
   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.
   //
   // 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;
@@ -101,10 +110,12 @@ class RangeMap {
 
   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 +123,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 +135,13 @@ class RangeMap {
   typedef typename AddressToRangeMap::const_iterator MapConstIterator;
   typedef typename AddressToRangeMap::value_type MapValue;
 
+  // Whether overlapping ranges can be shrunk down.  If true, then adding

[Mark Mentovai, 2016/06/02 21:43:53]

Don’t duplicate the comment from the setter. Either put it here or there, but
not both.

[ivanpe, 2016/06/02 22:54:02]

Done.

+  // 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.
+  bool enable_shrink_down_;
+
   // Maps the high address of each range to a EntryType.
   AddressToRangeMap map_;
 };
@@ -130,3 +151,4 @@ class RangeMap {
 
 
 #endif  // PROCESSOR_RANGE_MAP_H__
+

[Mark Mentovai, 2016/06/02 21:43:53]

Lose the blank line here, and actually at the end of a lot of (maybe all?) files
you’re touching.

[ivanpe, 2016/06/02 22:54:02]

Done.