[ADT] Implement llvm::bsearch() with std::partition_point()

[MaskRay]

Summary

Delete the begin-end form because the standard std::partition_point
can be easily used as a replacement.

The ranges-style llvm::bsearch will be renamed to llvm::partition_point.

The name "bsearch" doesn't meet people's expectation because in C:

If two or more members compare equal, which member is returned is unspecified.

[MaskRay]

Delete the begin-end form

[MaskRay]

@sammccall Ping :)

[MaskRay]

Ping

[sammccall]

Funny, the int version was the original motivation and now seems totally unused. And apparently none of us know the standard library very well.
Thanks for cleaning this up.

clang-tools-extra/clangd/index/dex/PostingList.cpp

public:
   /// equal or higher than the given one.
   void advanceTo(DocID ID) override {
     assert(!reachedEnd() &&
            "Posting List iterator can't advance() at the end.");
     if (ID <= peek())
       return;
     advanceToChunk(ID);
     // Try to find ID within current chunk.
-    CurrentID = llvm::bsearch(CurrentID, DecompressedChunk.end(),
-                              [&](const DocID D) { return D >= ID; });
+    CurrentID = std::partition_point(CurrentID, DecompressedChunk.end(),
+                                     [&](const DocID D) { return D < ID; });
     normalizeCursor();
   }
 
   DocID peek() const override {
     assert(!reachedEnd() && "Posting List iterator can't peek() at the end.");
     return *CurrentID;
   }
 
void normalizeCursor() {
     CurrentID = DecompressedChunk.begin();
   }
 
   /// Advances CurrentChunk to the chunk which might contain ID.
   void advanceToChunk(DocID ID) {
     if ((CurrentChunk != Chunks.end() - 1) &&
         ((CurrentChunk + 1)->Head <= ID)) {
       CurrentChunk =
-          llvm::bsearch(CurrentChunk + 1, Chunks.end(),
-                        [&](const Chunk &C) { return C.Head >= ID; });
+          std::partition_point(CurrentChunk + 1, Chunks.end(),
+                               [&](const Chunk &C) { return C.Head < ID; });
       --CurrentChunk;
       DecompressedChunk = CurrentChunk->decompress();
       CurrentID = DecompressedChunk.begin();
     }
   }
 
   const Token *Tok;
   llvm::ArrayRef<Chunk> Chunks;

llvm/include/llvm/ADT/STLExtras.h

void stable_sort(R &&Range) {
   std::stable_sort(adl_begin(Range), adl_end(Range));
 }
 
 template <typename R, typename Compare>
 void stable_sort(R &&Range, Compare C) {
   std::stable_sort(adl_begin(Range), adl_end(Range), C);
 }
 
-/// Binary search for the first index where a predicate is true.
-/// Returns the first I in [Lo, Hi) where C(I) is true, or Hi if it never is.
-/// Requires that C is always false below some limit, and always true above it.
-///
-/// Example:
-///   size_t DawnModernEra = bsearch(1776, 2050, [](size_t Year){
-///     return Presidents.for(Year).twitterHandle() != None;
-///   });
-///
-/// Note the return value differs from std::binary_search!
-template <typename Predicate>
-size_t bsearch(size_t Lo, size_t Hi, Predicate P) {
-  while (Lo != Hi) {
-    assert(Hi > Lo);
-    size_t Mid = Lo + (Hi - Lo) / 2;
-    if (P(Mid))
-      Hi = Mid;
-    else
-      Lo = Mid + 1;
-  }
-  return Hi;
-}
-
-/// Binary search for the first iterator where a predicate is true.
-/// Returns the first I in [Lo, Hi) where C(*I) is true, or Hi if it never is.
-/// Requires that C is always false below some limit, and always true above it.
-template <typename It, typename Predicate,
-          typename Val = decltype(*std::declval<It>())>
-It bsearch(It Lo, It Hi, Predicate P) {
-  return std::lower_bound(Lo, Hi, 0u,
-                          [&](const Val &V, unsigned) { return !P(V); });
-}
-
 /// Binary search for the first iterator in a range where a predicate is true.
 /// Requires that C is always false below some limit, and always true above it.
-template <typename R, typename Predicate>
+template <typename R, typename Predicate,
+          typename Val = decltype(*adl_begin(std::declval<R>()))>
 auto bsearch(R &&Range, Predicate P) -> decltype(adl_begin(Range)) {
-  return bsearch(adl_begin(Range), adl_end(Range), P);
+  return std::partition_point(adl_begin(Range), adl_end(Range),
+                              [&](const Val &V) { return !P(V); });
 }
 
 /// Wrapper function around std::equal to detect if all elements
 /// in a container are same.
 template <typename R>
 bool is_splat(R &&Range) {
   size_t range_size = size(Range);
   return range_size != 0 && (range_size == 1 ||

llvm/include/llvm/CodeGen/SlotIndexes.h

public:
 
     /// Iterator over the idx2MBBMap (sorted pairs of slot index of basic block
     /// begin and basic block)
     using MBBIndexIterator = SmallVectorImpl<IdxMBBPair>::const_iterator;
 
     /// Move iterator to the next IdxMBBPair where the SlotIndex is greater or
     /// equal to \p To.
     MBBIndexIterator advanceMBBIndex(MBBIndexIterator I, SlotIndex To) const {
-      return llvm::bsearch(I, idx2MBBMap.end(),
-                           [=](const IdxMBBPair &IM) { return To <= IM.first; });
+      return std::partition_point(
+          I, idx2MBBMap.end(),
+          [=](const IdxMBBPair &IM) { return IM.first < To; });
     }
 
     /// Get an iterator pointing to the IdxMBBPair with the biggest SlotIndex
     /// that is greater or equal to \p Idx.
     MBBIndexIterator findMBBIndex(SlotIndex Idx) const {
       return advanceMBBIndex(idx2MBBMap.begin(), Idx);
     }
 

llvm/unittests/ADT/STLExtrasTest.cpp

TEST(STLExtrasTest, to_address) {
   EXPECT_EQ(V3.get(), to_address(V3));
   EXPECT_EQ(V4.get(), to_address(V4));
 
   V3.reset(V1);
   EXPECT_EQ(V1, to_address(V3));
 }
 
 TEST(STLExtrasTest, bsearch) {
-  // Integer version.
-  EXPECT_EQ(7u, bsearch(5, 10, [](unsigned X) { return X >= 7; }));
-  EXPECT_EQ(5u, bsearch(5, 10, [](unsigned X) { return X >= 1; }));
-  EXPECT_EQ(10u, bsearch(5, 10, [](unsigned X) { return X >= 50; }));
-
-  // Iterator version.
   std::vector<int> V = {1, 3, 5, 7, 9};
-  EXPECT_EQ(V.begin() + 3,
-            bsearch(V.begin(), V.end(), [](unsigned X) { return X >= 7; }));
-  EXPECT_EQ(V.begin(),
-            bsearch(V.begin(), V.end(), [](unsigned X) { return X >= 1; }));
-  EXPECT_EQ(V.end(),
-            bsearch(V.begin(), V.end(), [](unsigned X) { return X >= 50; }));
 
   // Range version.
   EXPECT_EQ(V.begin() + 3, bsearch(V, [](unsigned X) { return X >= 7; }));
   EXPECT_EQ(V.begin(), bsearch(V, [](unsigned X) { return X >= 1; }));
   EXPECT_EQ(V.end(), bsearch(V, [](unsigned X) { return X >= 50; }));
 }
 
 } // namespace