• Home
  • History
  • Annotate
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 // UNSUPPORTED: c++03, c++11, c++14
10 // XFAIL: libc++
11 
12 // <functional>
13 
14 // boyer_moore_horspool searcher
15 // template<class RandomAccessIterator1,
16 //          class Hash = hash<typename iterator_traits<RandomAccessIterator1>::value_type>,
17 //          class BinaryPredicate = equal_to<>>
18 // class boyer_moore_horspool_searcher {
19 // public:
20 //   boyer_moore_horspool_searcher(RandomAccessIterator1 pat_first, RandomAccessIterator1 pat_last,
21 //                                 Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate());
22 //
23 //   template<class RandomAccessIterator2>
24 //   pair<RandomAccessIterator2, RandomAccessIterator2>
25 //   operator()(RandomAccessIterator2 first, RandomAccessIterator2 last) const;
26 //
27 // private:
28 //   RandomAccessIterator1 pat_first_; // exposition only
29 //   RandomAccessIterator1 pat_last_;  // exposition only
30 //   Hash                  hash_;      // exposition only
31 //   BinaryPredicate       pred_;      // exposition only
32 // };
33 
34 #include <algorithm>
35 #include <functional>
36 #include <cassert>
37 
38 #include "test_macros.h"
39 #include "test_iterators.h"
40 
41 template <typename T> struct MyHash {
operator ()MyHash42     size_t operator () (T t) const { return static_cast<size_t>(t); }
43 };
44 
45 template <typename Iter1, typename Iter2>
do_search(Iter1 b1,Iter1 e1,Iter2 b2,Iter2 e2,Iter1 result,unsigned)46 void do_search(Iter1 b1, Iter1 e1, Iter2 b2, Iter2 e2, Iter1 result, unsigned /*max_count*/) {
47     std::boyer_moore_horspool_searcher<Iter2,
48                  MyHash<typename std::remove_cv<typename std::iterator_traits<Iter2>::value_type>::type>>
49           s{b2, e2};
50     assert(result == std::search(b1, e1, s));
51 }
52 
53 template <class Iter1, class Iter2>
54 void
test()55 test()
56 {
57     int ia[] = {0, 1, 2, 3, 4, 5};
58     const unsigned sa = sizeof(ia)/sizeof(ia[0]);
59     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia),    Iter1(ia),      0);
60     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+1),  Iter1(ia),      sa);
61     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+1),    Iter2(ia+2),  Iter1(ia+1),    sa);
62     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+2),  Iter1(ia),      0);
63     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
64     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
65     do_search(Iter1(ia), Iter1(ia),      Iter2(ia+2),    Iter2(ia+3),  Iter1(ia),      0);
66     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa);
67     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa);
68     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+sa), Iter1(ia),      sa*sa);
69     do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia),      Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa);
70     do_search(Iter1(ia), Iter1(ia+1),    Iter2(ia),      Iter2(ia+sa), Iter1(ia+1),    sa);
71     int ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};
72     const unsigned sb = sizeof(ib)/sizeof(ib[0]);
73     int ic[] = {1};
74     do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb);
75     int id[] = {1, 2};
76     do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2);
77     int ie[] = {1, 2, 3};
78     do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3);
79     int ig[] = {1, 2, 3, 4};
80     do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4);
81     int ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4};
82     const unsigned sh = sizeof(ih)/sizeof(ih[0]);
83     int ii[] = {1, 1, 2};
84     do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3),  sh*3);
85 }
86 
87 template <class Iter1, class Iter2>
88 void
test2()89 test2()
90 {
91     char ia[] = {0, 1, 2, 3, 4, 5};
92     const unsigned sa = sizeof(ia)/sizeof(ia[0]);
93     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia),    Iter1(ia),      0);
94     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+1),  Iter1(ia),      sa);
95     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+1),    Iter2(ia+2),  Iter1(ia+1),    sa);
96     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+2),  Iter1(ia),      0);
97     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
98     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+2),    Iter2(ia+3),  Iter1(ia+2),    sa);
99     do_search(Iter1(ia), Iter1(ia),      Iter2(ia+2),    Iter2(ia+3),  Iter1(ia),      0);
100     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-1), Iter2(ia+sa), Iter1(ia+sa-1), sa);
101     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia+sa-3), Iter2(ia+sa), Iter1(ia+sa-3), 3*sa);
102     do_search(Iter1(ia), Iter1(ia+sa),   Iter2(ia),      Iter2(ia+sa), Iter1(ia),      sa*sa);
103     do_search(Iter1(ia), Iter1(ia+sa-1), Iter2(ia),      Iter2(ia+sa), Iter1(ia+sa-1), (sa-1)*sa);
104     do_search(Iter1(ia), Iter1(ia+1),    Iter2(ia),      Iter2(ia+sa), Iter1(ia+1),    sa);
105     char ib[] = {0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4};
106     const unsigned sb = sizeof(ib)/sizeof(ib[0]);
107     char ic[] = {1};
108     do_search(Iter1(ib), Iter1(ib+sb), Iter2(ic), Iter2(ic+1), Iter1(ib+1), sb);
109     char id[] = {1, 2};
110     do_search(Iter1(ib), Iter1(ib+sb), Iter2(id), Iter2(id+2), Iter1(ib+1), sb*2);
111     char ie[] = {1, 2, 3};
112     do_search(Iter1(ib), Iter1(ib+sb), Iter2(ie), Iter2(ie+3), Iter1(ib+4), sb*3);
113     char ig[] = {1, 2, 3, 4};
114     do_search(Iter1(ib), Iter1(ib+sb), Iter2(ig), Iter2(ig+4), Iter1(ib+8), sb*4);
115     char ih[] = {0, 1, 1, 1, 1, 2, 3, 0, 1, 2, 3, 4};
116     const unsigned sh = sizeof(ih)/sizeof(ih[0]);
117     char ii[] = {1, 1, 2};
118     do_search(Iter1(ih), Iter1(ih+sh), Iter2(ii), Iter2(ii+3), Iter1(ih+3),  sh*3);
119 }
120 
main(int,char **)121 int main(int, char**) {
122     test<random_access_iterator<const int*>, random_access_iterator<const int*> >();
123     test2<random_access_iterator<const char*>, random_access_iterator<const char*> >();
124 
125   return 0;
126 }
127