Correct logic bug in find optimization for vector<bool>. This fixes http://llvm.org/bugs/show_bug.cgi?id=16816

llvm-svn: 187908

2 files changed, 42 insertions, 0 deletions

diff --git a/libcxx/include/__bit_reference b/libcxx/include/__bit_reference
index 8ff3bf6d9ee..58d475e4368 100644
--- a/libcxx/include/__bit_reference
+++ b/libcxx/include/__bit_reference
@@ -173,6 +173,8 @@ __find_bool_true(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type
         __storage_type __b = *__first.__seg_ & __m;
         if (__b)
             return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b)));
+        if (__n == __dn)
+            return _It(__first.__seg_, __first.__ctz_ + __n);
         __n -= __dn;
         ++__first.__seg_;
     }
@@ -207,6 +209,8 @@ __find_bool_false(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type
         __storage_type __b = ~*__first.__seg_ & __m;
         if (__b)
             return _It(__first.__seg_, static_cast<unsigned>(_VSTD::__ctz(__b)));
+        if (__n == __dn)
+            return _It(__first.__seg_, __first.__ctz_ + __n);
         __n -= __dn;
         ++__first.__seg_;
     }
diff --git a/libcxx/test/containers/sequences/vector.bool/find.pass.cpp b/libcxx/test/containers/sequences/vector.bool/find.pass.cpp
new file mode 100644
index 00000000000..8bad87efff6
--- /dev/null
+++ b/libcxx/test/containers/sequences/vector.bool/find.pass.cpp
@@ -0,0 +1,38 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <vector>
+// vector<bool>
+
+// std::find with vector<bool>::iterator
+
+// http://llvm.org/bugs/show_bug.cgi?id=16816
+
+#include <vector>
+#include <cassert>
+
+int main()
+{
+    {
+        for (unsigned i = 1; i < 256; ++i)
+        {
+            std::vector<bool> b(i,true);
+            std::vector<bool>::iterator j = std::find(b.begin()+1, b.end(), false);
+            assert(j-b.begin() == i);
+        }
+    }
+    {
+        for (unsigned i = 1; i < 256; ++i)
+        {
+            std::vector<bool> b(i,false);
+            std::vector<bool>::iterator j = std::find(b.begin()+1, b.end(), true);
+            assert(j-b.begin() == i);
+        }
+    }
+}