RangeDataVector: Support custom sorting for D63540

[jankratochvil]

Summary

As suggested by @labath extended RangeDataVector so that user can provide custom sorting of the Entry's `data' field.

[jankratochvil]

lldb/include/lldb/Utility/RangeMap.h

602

These functions were used just by RangeDataVector (=after I removed them LLDB still builds fine) which no longer uses them so I removed them.

[labath]

Looks good. Thanks.

lldb/include/lldb/Utility/RangeMap.h

struct RangeData : public Range<B, S> {
 
   DataType data;
 
   RangeData() : Range<B, S>(), data() {}
 
   RangeData(B base, S size) : Range<B, S>(base, size), data() {}
 
   RangeData(B base, S size, DataType d) : Range<B, S>(base, size), data(d) {}
-
-  bool operator<(const RangeData &rhs) const {
-    if (this->base == rhs.base) {
-      if (this->size == rhs.size)
-        return this->data < rhs.data;
-      else
-        return this->size < rhs.size;
-    }
-    return this->base < rhs.base;
-  }
-
-  bool operator==(const RangeData &rhs) const {
-    return this->GetRangeBase() == rhs.GetRangeBase() &&
-           this->GetByteSize() == rhs.GetByteSize() && this->data == rhs.data;
-  }
-
-  bool operator!=(const RangeData &rhs) const {
-    return this->GetRangeBase() != rhs.GetRangeBase() ||
-           this->GetByteSize() != rhs.GetByteSize() || this->data != rhs.data;
-  }
 };
 
-template <typename B, typename S, typename T, unsigned N = 0>
+template <typename B, typename S, typename T, unsigned N = 0,
+          class Compare = std::less<T>>
 class RangeDataVector {
 public:
   typedef lldb_private::Range<B, S> Range;
   typedef RangeData<B, S, T> Entry;
   typedef llvm::SmallVector<Entry, N> Collection;
 
-  RangeDataVector() = default;
+  RangeDataVector(Compare compare = Compare()) : m_compare(compare) {}
 
   ~RangeDataVector() = default;
 
   void Append(const Entry &entry) { m_entries.push_back(entry); }
 
   void Sort() {
     if (m_entries.size() > 1)
-      std::stable_sort(m_entries.begin(), m_entries.end());
+      std::stable_sort(m_entries.begin(), m_entries.end(),
+                       [&compare = m_compare](const Entry &a, const Entry &b) {
+                         if (a.base != b.base)
+                           return a.base < b.base;
+                         if (a.size != b.size)
+                           return a.size < b.size;
+                         return compare(a.data, b.data);
+                       });
   }
 
 #ifdef ASSERT_RANGEMAP_ARE_SORTED
   bool IsSorted() const {
     typename Collection::const_iterator pos, end, prev;
     // First we determine if we can combine any of the Entry objects so we
     // don't end up allocating and making a new collection for no reason
     for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
#endif
   Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); }
 
   const Entry *Back() const {
     return (m_entries.empty() ? nullptr : &m_entries.back());
   }
 
 protected:
   Collection m_entries;
+  Compare m_compare;
 };
 
 // A simple range  with data class where you get to define the type of
 // the range base "B", the type used for the range byte size "S", and the type
 // for the associated data "T".
 template <typename B, typename T> struct AddressData {
   typedef B BaseType;
   typedef T DataType;

lldb/unittests/Utility/RangeMapTest.cpp

TEST(RangeDataVector, FindEntryThatContains_Overlap) {
   // With overlapping intervals, the intention seems to be to return the first
   // interval which contains the address.
   EXPECT_THAT(Map.FindEntryThatContains(25), EntryIs(0));
 
   // However, this does not always succeed.
   // TODO: This should probably return the range (0, 40) as well.
   EXPECT_THAT(Map.FindEntryThatContains(35), nullptr);
 }
+
+TEST(RangeDataVector, CustomSort) {
+  // First the default ascending order sorting of the data field.
+  auto Map = RangeDataVectorT();
+  Map.Append(EntryT(0, 10, 50));
+  Map.Append(EntryT(0, 10, 52));
+  Map.Append(EntryT(0, 10, 53));
+  Map.Append(EntryT(0, 10, 51));
+  Map.Sort();
+
+  EXPECT_THAT(Map.GetSize(), 4);
+  EXPECT_THAT(Map.GetEntryRef(0).data, 50);
+  EXPECT_THAT(Map.GetEntryRef(1).data, 51);
+  EXPECT_THAT(Map.GetEntryRef(2).data, 52);
+  EXPECT_THAT(Map.GetEntryRef(3).data, 53);
+
+  // And then a custom descending order sorting of the data field.
+  class CtorParam {};
+  class CustomSort {
+  public:
+    CustomSort(CtorParam) {}
+    bool operator()(const uint32_t a_data, const uint32_t b_data) {
+      return a_data > b_data;
+    }
+  };
+  using RangeDataVectorCustomSortT =
+      RangeDataVector<uint32_t, uint32_t, uint32_t, 0, CustomSort>;
+  using EntryT = RangeDataVectorT::Entry;
+
+  auto MapC = RangeDataVectorCustomSortT(CtorParam());
+  MapC.Append(EntryT(0, 10, 50));
+  MapC.Append(EntryT(0, 10, 52));
+  MapC.Append(EntryT(0, 10, 53));
+  MapC.Append(EntryT(0, 10, 51));
+  MapC.Sort();
+
+  EXPECT_THAT(MapC.GetSize(), 4);
+  EXPECT_THAT(MapC.GetEntryRef(0).data, 53);
+  EXPECT_THAT(MapC.GetEntryRef(1).data, 52);
+  EXPECT_THAT(MapC.GetEntryRef(2).data, 51);
+  EXPECT_THAT(MapC.GetEntryRef(3).data, 50);
+}