Adding support for overlapping ranges to RangeMap.

src/processor/range_map.h

 // Copyright (c) 2006, Google Inc.
 // All rights reserved.
 //
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 // notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
@@ skipping 34 matching lines @@
 
 
 namespace google_breakpad {
 
 // Forward declarations (for later friend declarations of specialized template).
 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);
+  // 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 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.
   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;
 
   // Empties the range map, restoring it to the state it was when it was
   // initially created.
   void Clear();
 
  private:
   // Friend declarations.
   friend class ModuleComparer;
   friend class RangeMapSerializer<AddressType, EntryType>;
 
   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:
     // The base address of the range.  The high address does not need to
     // 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_;
   };
 
   // Convenience types.
   typedef std::map<AddressType, Range> AddressToRangeMap;
   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_;
 };
 
 
 }  // namespace google_breakpad
 
 
 #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.