MaskRay created this revision.
MaskRay added reviewers: EricWF, sammccall.
Herald added subscribers: llvm-commits, cfe-commits, kadircet, arphaman,
dexonsmith, jkorous.
Herald added projects: clang, LLVM.
Deprecate the begin-end form because the standard std::partition_point
can be easily used as a replacement.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D63718
Files:
clang-tools-extra/clangd/index/dex/PostingList.cpp
llvm/include/llvm/ADT/STLExtras.h
llvm/include/llvm/CodeGen/SlotIndexes.h
llvm/unittests/ADT/STLExtrasTest.cpp
Index: llvm/unittests/ADT/STLExtrasTest.cpp
===================================================================
--- llvm/unittests/ADT/STLExtrasTest.cpp
+++ llvm/unittests/ADT/STLExtrasTest.cpp
@@ -470,11 +470,6 @@
}
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,
Index: llvm/include/llvm/CodeGen/SlotIndexes.h
===================================================================
--- llvm/include/llvm/CodeGen/SlotIndexes.h
+++ llvm/include/llvm/CodeGen/SlotIndexes.h
@@ -492,8 +492,9 @@
/// 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
Index: llvm/include/llvm/ADT/STLExtras.h
===================================================================
--- llvm/include/llvm/ADT/STLExtras.h
+++ llvm/include/llvm/ADT/STLExtras.h
@@ -1322,44 +1322,22 @@
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;
-}
-
+/// \deprecated Use std::partition_point.
/// 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); });
+ return std::partition_point(Lo, Hi, [&](const Val &V) { 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>
auto bsearch(R &&Range, Predicate P) -> decltype(adl_begin(Range)) {
- return bsearch(adl_begin(Range), adl_end(Range), P);
+ return llvm::bsearch(adl_begin(Range), adl_end(Range),
+ std::forward<Predicate>(P));
}
/// Wrapper function around std::equal to detect if all elements
Index: clang-tools-extra/clangd/index/dex/PostingList.cpp
===================================================================
--- clang-tools-extra/clangd/index/dex/PostingList.cpp
+++ clang-tools-extra/clangd/index/dex/PostingList.cpp
@@ -50,8 +50,8 @@
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();
}
@@ -103,8 +103,8 @@
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();
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
