1 //===----------------------------------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 // <algorithm> 10 11 // template<class ForwardIterator, class Size, class T, class BinaryPredicate> 12 // constexpr ForwardIterator // constexpr after C++17 13 // search_n(ForwardIterator first, ForwardIterator last, Size count, 14 // const T& value, BinaryPredicate pred); 15 16 #include <algorithm> 17 #include <cassert> 18 19 #include "test_macros.h" 20 #include "test_iterators.h" 21 #include "user_defined_integral.h" 22 23 #if TEST_STD_VER > 17 24 TEST_CONSTEXPR bool eq(int a, int b) { return a == b; } 25 26 TEST_CONSTEXPR bool test_constexpr() { 27 int ia[] = {0, 0, 1, 1, 2, 2}; 28 return (std::search_n(std::begin(ia), std::end(ia), 1, 0, eq) == ia) 29 && (std::search_n(std::begin(ia), std::end(ia), 2, 1, eq) == ia+2) 30 && (std::search_n(std::begin(ia), std::end(ia), 1, 3, eq) == std::end(ia)) 31 ; 32 } 33 #endif 34 35 struct count_equal 36 { 37 static unsigned count; 38 template <class T> 39 bool operator()(const T& x, const T& y) 40 {++count; return x == y;} 41 }; 42 43 unsigned count_equal::count = 0; 44 45 46 template <class Iter> 47 void 48 test() 49 { 50 int ia[] = {0, 1, 2, 3, 4, 5}; 51 const unsigned sa = sizeof(ia)/sizeof(ia[0]); 52 count_equal::count = 0; 53 assert(std::search_n(Iter(ia), Iter(ia+sa), 0, 0, count_equal()) == Iter(ia)); 54 assert(count_equal::count <= sa); 55 count_equal::count = 0; 56 assert(std::search_n(Iter(ia), Iter(ia+sa), 1, 0, count_equal()) == Iter(ia+0)); 57 assert(count_equal::count <= sa); 58 count_equal::count = 0; 59 assert(std::search_n(Iter(ia), Iter(ia+sa), 2, 0, count_equal()) == Iter(ia+sa)); 60 assert(count_equal::count <= sa); 61 count_equal::count = 0; 62 assert(std::search_n(Iter(ia), Iter(ia+sa), sa, 0, count_equal()) == Iter(ia+sa)); 63 assert(count_equal::count <= sa); 64 count_equal::count = 0; 65 assert(std::search_n(Iter(ia), Iter(ia+sa), 0, 3, count_equal()) == Iter(ia)); 66 assert(count_equal::count <= sa); 67 count_equal::count = 0; 68 assert(std::search_n(Iter(ia), Iter(ia+sa), 1, 3, count_equal()) == Iter(ia+3)); 69 assert(count_equal::count <= sa); 70 count_equal::count = 0; 71 assert(std::search_n(Iter(ia), Iter(ia+sa), 2, 3, count_equal()) == Iter(ia+sa)); 72 assert(count_equal::count <= sa); 73 count_equal::count = 0; 74 assert(std::search_n(Iter(ia), Iter(ia+sa), sa, 3, count_equal()) == Iter(ia+sa)); 75 assert(count_equal::count <= sa); 76 count_equal::count = 0; 77 assert(std::search_n(Iter(ia), Iter(ia+sa), 0, 5, count_equal()) == Iter(ia)); 78 assert(count_equal::count <= sa); 79 count_equal::count = 0; 80 assert(std::search_n(Iter(ia), Iter(ia+sa), 1, 5, count_equal()) == Iter(ia+5)); 81 assert(count_equal::count <= sa); 82 count_equal::count = 0; 83 assert(std::search_n(Iter(ia), Iter(ia+sa), 2, 5, count_equal()) == Iter(ia+sa)); 84 assert(count_equal::count <= sa); 85 count_equal::count = 0; 86 assert(std::search_n(Iter(ia), Iter(ia+sa), sa, 5, count_equal()) == Iter(ia+sa)); 87 assert(count_equal::count <= sa); 88 count_equal::count = 0; 89 90 int ib[] = {0, 0, 1, 1, 2, 2}; 91 const unsigned sb = sizeof(ib)/sizeof(ib[0]); 92 assert(std::search_n(Iter(ib), Iter(ib+sb), 0, 0, count_equal()) == Iter(ib)); 93 assert(count_equal::count <= sb); 94 count_equal::count = 0; 95 assert(std::search_n(Iter(ib), Iter(ib+sb), 1, 0, count_equal()) == Iter(ib+0)); 96 assert(count_equal::count <= sb); 97 count_equal::count = 0; 98 assert(std::search_n(Iter(ib), Iter(ib+sb), 2, 0, count_equal()) == Iter(ib+0)); 99 assert(count_equal::count <= sb); 100 count_equal::count = 0; 101 assert(std::search_n(Iter(ib), Iter(ib+sb), 3, 0, count_equal()) == Iter(ib+sb)); 102 assert(count_equal::count <= sb); 103 count_equal::count = 0; 104 assert(std::search_n(Iter(ib), Iter(ib+sb), sb, 0, count_equal()) == Iter(ib+sb)); 105 assert(count_equal::count <= sb); 106 count_equal::count = 0; 107 assert(std::search_n(Iter(ib), Iter(ib+sb), 0, 1, count_equal()) == Iter(ib)); 108 assert(count_equal::count <= sb); 109 count_equal::count = 0; 110 assert(std::search_n(Iter(ib), Iter(ib+sb), 1, 1, count_equal()) == Iter(ib+2)); 111 assert(count_equal::count <= sb); 112 count_equal::count = 0; 113 assert(std::search_n(Iter(ib), Iter(ib+sb), 2, 1, count_equal()) == Iter(ib+2)); 114 assert(count_equal::count <= sb); 115 count_equal::count = 0; 116 assert(std::search_n(Iter(ib), Iter(ib+sb), 3, 1, count_equal()) == Iter(ib+sb)); 117 assert(count_equal::count <= sb); 118 count_equal::count = 0; 119 assert(std::search_n(Iter(ib), Iter(ib+sb), sb, 1, count_equal()) == Iter(ib+sb)); 120 assert(count_equal::count <= sb); 121 count_equal::count = 0; 122 assert(std::search_n(Iter(ib), Iter(ib+sb), 0, 2, count_equal()) == Iter(ib)); 123 assert(count_equal::count <= sb); 124 count_equal::count = 0; 125 assert(std::search_n(Iter(ib), Iter(ib+sb), 1, 2, count_equal()) == Iter(ib+4)); 126 assert(count_equal::count <= sb); 127 count_equal::count = 0; 128 assert(std::search_n(Iter(ib), Iter(ib+sb), 2, 2, count_equal()) == Iter(ib+4)); 129 assert(count_equal::count <= sb); 130 count_equal::count = 0; 131 assert(std::search_n(Iter(ib), Iter(ib+sb), 3, 2, count_equal()) == Iter(ib+sb)); 132 assert(count_equal::count <= sb); 133 count_equal::count = 0; 134 assert(std::search_n(Iter(ib), Iter(ib+sb), sb, 2, count_equal()) == Iter(ib+sb)); 135 assert(count_equal::count <= sb); 136 count_equal::count = 0; 137 138 int ic[] = {0, 0, 0}; 139 const unsigned sc = sizeof(ic)/sizeof(ic[0]); 140 assert(std::search_n(Iter(ic), Iter(ic+sc), 0, 0, count_equal()) == Iter(ic)); 141 assert(count_equal::count <= sc); 142 count_equal::count = 0; 143 assert(std::search_n(Iter(ic), Iter(ic+sc), 1, 0, count_equal()) == Iter(ic)); 144 assert(count_equal::count <= sc); 145 count_equal::count = 0; 146 assert(std::search_n(Iter(ic), Iter(ic+sc), 2, 0, count_equal()) == Iter(ic)); 147 assert(count_equal::count <= sc); 148 count_equal::count = 0; 149 assert(std::search_n(Iter(ic), Iter(ic+sc), 3, 0, count_equal()) == Iter(ic)); 150 assert(count_equal::count <= sc); 151 count_equal::count = 0; 152 assert(std::search_n(Iter(ic), Iter(ic+sc), 4, 0, count_equal()) == Iter(ic+sc)); 153 assert(count_equal::count <= sc); 154 count_equal::count = 0; 155 156 // Check that we properly convert the size argument to an integral. 157 TEST_IGNORE_NODISCARD std::search_n(Iter(ic), Iter(ic+sc), UserDefinedIntegral<unsigned>(4), 0, count_equal()); 158 count_equal::count = 0; 159 } 160 161 class A { 162 public: 163 A(int x, int y) : x_(x), y_(y) {} 164 int x() const { return x_; } 165 int y() const { return y_; } 166 167 private: 168 int x_; 169 int y_; 170 }; 171 172 struct Pred { 173 bool operator()(const A& l, int r) const { return l.x() == r; } 174 }; 175 176 int main(int, char**) 177 { 178 test<forward_iterator<const int*> >(); 179 test<bidirectional_iterator<const int*> >(); 180 test<random_access_iterator<const int*> >(); 181 182 // test bug reported in https://reviews.llvm.org/D124079?#3661721 183 { 184 A a[] = {A(1, 2), A(2, 3), A(2, 4)}; 185 int value = 2; 186 auto result = std::search_n(a, a + 3, 1, value, Pred()); 187 assert(result == a + 1); 188 } 189 190 #if TEST_STD_VER > 17 191 static_assert(test_constexpr()); 192 #endif 193 194 return 0; 195 } 196