This is an archive of the discontinued LLVM Phabricator instance.

[ADT] llvm::bsearch, binary search for mere mortals
ClosedPublic

Authored by sammccall on Apr 16 2019, 9:12 AM.

Details

Summary

Add to STLExtras a binary search function with a simple mental model:
You provide a range and a predicate which is true above a certain point.
bsearch() tells you that point.
Overloads are provided for integers, iterators, and containers.

This is more suitable than std:: alternatives in many cases:

  • std::binary_search only indicates presence/absence
  • upper_bound/lower_bound give you the opportunity to pick the wrong one
  • all of the options have confusing names and definitions when your predicate doesn't have simple "less than" semantics
  • all of the options require iterators
  • we plumb around a useless value parameter that should be a lambda capture

The API is inspired by Go's standard library, but we add an extra parameter as
well as some overloads and templates to show how clever C++ is.

Diff Detail

Event Timeline

sammccall created this revision.Apr 16 2019, 9:12 AM
sammccall updated this revision to Diff 195401.Apr 16 2019, 9:14 AM

Predicate, not compare.

Harbormaster completed remote builds in B30629: Diff 195401.
ilya-biryukov added inline comments.Apr 16 2019, 9:17 AM
include/llvm/ADT/STLExtras.h
1317

Maybe use /2 instead of >>1?

gribozavr accepted this revision.Apr 16 2019, 9:25 AM
This revision is now accepted and ready to land.Apr 16 2019, 9:25 AM
jkorous added inline comments.
include/llvm/ADT/STLExtras.h
1315

Wouldn't size_t be better than unsigned for the use-case below?

1317

I'd consider adding assert(Hi > Lo).

This revision was automatically updated to reflect the committed changes.
sammccall marked 3 inline comments as done.

hi sammccall, when I run "check-all", some waring/error print out in STLExtrasTest.cpp as follow. My version is llvm:0ee120077 and clang:d87ee8e678. Could you please fix it or guide me how to fix it?

myLLVM/llvm/unittests/ADT/STLExtrasTest.cpp: In lambda function:
myLLVM/llvm/unittests/ADT/STLExtrasTest.cpp:475:58: warning: comparison of unsigned expression >= 0 is always true [-Wtype-limits]

EXPECT_EQ(5u, bsearch(5, 10, [](unsigned X) { return X >= 0; }));
                                                       ^

myLLVM/llvm/utils/unittest/googletest/include/gtest/gtest_pred_impl.h:77:52: note: in definition of macro 'GTEST_ASSERT_'

if (const ::testing::AssertionResult gtest_ar = (expression)) \
                                                 ^

myLLVM/llvm/utils/unittest/googletest/include/gtest/gtest_pred_impl.h:162:3: note: in expansion of macro 'GTEST_PRED_FORMAT2_'

GTEST_PRED_FORMAT2_(pred_format, v1, v2, GTEST_NONFATAL_FAILURE_)
^

myLLVM/llvm/utils/unittest/googletest/include/gtest/gtest.h:1923:3: note: in expansion of macro 'EXPECT_PRED_FORMAT2'

EXPECT_PRED_FORMAT2(::testing::internal:: \
^

myLLVM/llvm/unittests/ADT/STLExtrasTest.cpp:475:3: note: in expansion of macro 'EXPECT_EQ'

EXPECT_EQ(5u, bsearch(5, 10, [](unsigned X) { return X >= 0; }));
^

myLLVM/llvm/unittests/ADT/STLExtrasTest.cpp: In lambda function:
myLLVM/llvm/unittests/ADT/STLExtrasTest.cpp:483:67: warning: comparison of unsigned expression >= 0 is always true [-Wtype-limits]

bsearch(V.begin(), V.end(), [](unsigned X) { return X >= 0; }));
                                                      ^

myLLVM/llvm/utils/unittest/googletest/include/gtest/gtest_pred_impl.h:77:52: note: in definition of macro 'GTEST_ASSERT_'

if (const ::testing::AssertionResult gtest_ar = (expression)) \
                                                    ^

myLLVM/llvm/utils/unittest/googletest/include/gtest/gtest_pred_impl.h:162:3: note: in expansion of macro 'GTEST_PRED_FORMAT2_'

GTEST_PRED_FORMAT2_(pred_format, v1, v2, GTEST_NONFATAL_FAILURE_)
^

myLLVM/llvm/utils/unittest/googletest/include/gtest/gtest.h:1923:3: note: in expansion of macro 'EXPECT_PRED_FORMAT2'

EXPECT_PRED_FORMAT2(::testing::internal:: \
^

myLLVM/llvm/unittests/ADT/STLExtrasTest.cpp:482:3: note: in expansion of macro 'EXPECT_EQ'

EXPECT_EQ(V.begin(),
^

myLLVM/llvm/unittests/ADT/STLExtrasTest.cpp: In lambda function:
myLLVM/llvm/unittests/ADT/STLExtrasTest.cpp:489:61: warning: comparison of unsigned expression >= 0 is always true [-Wtype-limits]

EXPECT_EQ(V.begin(), bsearch(V, [](unsigned X) { return X >= 0; }));
                                                          ^

myLLVM/llvm/utils/unittest/googletest/include/gtest/gtest_pred_impl.h:77:52: note: in definition of macro 'GTEST_ASSERT_'

if (const ::testing::AssertionResult gtest_ar = (expression)) \
                                                 ^

myLLVM/llvm/utils/unittest/googletest/include/gtest/gtest_pred_impl.h:162:3: note: in expansion of macro 'GTEST_PRED_FORMAT2_'

GTEST_PRED_FORMAT2_(pred_format, v1, v2, GTEST_NONFATAL_FAILURE_)
^

myLLVM/llvm/utils/unittest/googletest/include/gtest/gtest.h:1923:3: note: in expansion of macro 'EXPECT_PRED_FORMAT2'

EXPECT_PRED_FORMAT2(::testing::internal:: \
^

myLLVM/llvm/unittests/ADT/STLExtrasTest.cpp:489:3: note: in expansion of macro 'EXPECT_EQ'

EXPECT_EQ(V.begin(), bsearch(V, [](unsigned X) { return X >= 0; }));
^

ormris added a subscriber: ormris.Apr 22 2019, 9:58 AM