This revision was automatically updated to reflect the committed changes.
Closed by commit rL364719: [ADT] Implement llvm::bsearch() with
std::partition_point() (authored by MaskRay, committed by ).
Herald added subscribers: kristina, ilya-biryukov.
Changed prior to commit:
https://reviews.llvm.org/D63718?vs=206220&id=207218#toc
Repository:
rL LLVM
CHANGES SINCE LAST ACTION
https://reviews.llvm.org/D63718/new/
https://reviews.llvm.org/D63718
Files:
clang-tools-extra/trunk/clangd/index/dex/PostingList.cpp
llvm/trunk/include/llvm/ADT/STLExtras.h
llvm/trunk/include/llvm/CodeGen/SlotIndexes.h
llvm/trunk/unittests/ADT/STLExtrasTest.cpp
Index: llvm/trunk/unittests/ADT/STLExtrasTest.cpp
===================================================================
--- llvm/trunk/unittests/ADT/STLExtrasTest.cpp
+++ llvm/trunk/unittests/ADT/STLExtrasTest.cpp
@@ -470,19 +470,7 @@
}
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; }));
Index: llvm/trunk/include/llvm/ADT/STLExtras.h
===================================================================
--- llvm/trunk/include/llvm/ADT/STLExtras.h
+++ llvm/trunk/include/llvm/ADT/STLExtras.h
@@ -1322,44 +1322,13 @@
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
Index: llvm/trunk/include/llvm/CodeGen/SlotIndexes.h
===================================================================
--- llvm/trunk/include/llvm/CodeGen/SlotIndexes.h
+++ llvm/trunk/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: clang-tools-extra/trunk/clangd/index/dex/PostingList.cpp
===================================================================
--- clang-tools-extra/trunk/clangd/index/dex/PostingList.cpp
+++ clang-tools-extra/trunk/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
