From 2f2f41e12c5201b600d887d22ce5cb4afd2ff594 Mon Sep 17 00:00:00 2001
From: Jan Kratochvil <jan.kratochvil@redhat.com>
Date: Fri, 10 Jan 2020 15:14:38 +0100
Subject: [PATCH] RangeDataVector: Support custom sorting for D63540

As suggested by @labath extended RangeDataVector so that user can provide
custom sorting of the Entry's `data' field for D63540.
        https://reviews.llvm.org/D63540

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

Differential revision: https://reviews.llvm.org/D72460
---
 lldb/include/lldb/Utility/RangeMap.h    | 35 ++++++++++-----------------
 lldb/unittests/Utility/RangeMapTest.cpp | 42 +++++++++++++++++++++++++++++++++
 2 files changed, 54 insertions(+), 23 deletions(-)

diff --git a/lldb/include/lldb/Utility/RangeMap.h b/lldb/include/lldb/Utility/RangeMap.h
index 709b5d2..9e03073 100644
--- a/lldb/include/lldb/Utility/RangeMap.h
+++ b/lldb/include/lldb/Utility/RangeMap.h
@@ -599,36 +599,17 @@ struct RangeData : public Range<B, S> {
   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;
 
@@ -636,7 +617,14 @@ public:
 
   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
@@ -817,6 +805,7 @@ public:
 
 protected:
   Collection m_entries;
+  Compare m_compare;
 };
 
 // A simple range  with data class where you get to define the type of
diff --git a/lldb/unittests/Utility/RangeMapTest.cpp b/lldb/unittests/Utility/RangeMapTest.cpp
index ebb49cc..9f9b965 100644
--- a/lldb/unittests/Utility/RangeMapTest.cpp
+++ b/lldb/unittests/Utility/RangeMapTest.cpp
@@ -52,3 +52,45 @@ TEST(RangeDataVector, FindEntryThatContains_Overlap) {
   // 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);
+}
-- 
2.7.4