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..22b1d4f787086466817d8a46031e117e7f095e2c 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,
+  // 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.

[mmandlis, 2016/06/02 23:50:59]

typo - higher

[ivanpe, 2016/06/03 03:56:56]

Done.

+  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.

[mmandlis, 2016/06/02 23:50:59]

could you, please, add comment on what entry_delta is?

[ivanpe, 2016/06/03 03:56:55]

Done.

   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;

[mmandlis, 2016/06/02 23:50:59]

optional - probably not worth doing, but just smth to consider.
All methods here take entry_base, entry_delta and entry_size. Maybe it's worth
defining an EntryAddress class with these 3 fields?

[ivanpe, 2016/06/03 03:56:55]

Acknowledged.

 
   // Returns the number of ranges stored in the RangeMap.
   int GetCount() const;
@@ -99,12 +108,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 +128,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 +140,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_;
 };