libstdc++-v3/testsuite/20_util/function_objects/searchers.cc

   1 // Copyright (C) 2014-2022 Free Software Foundation, Inc.
   2 //
   3 // This file is part of the GNU ISO C++ Library.  This library is free
   4 // software; you can redistribute it and/or modify it under the
   5 // terms of the GNU General Public License as published by the
   6 // Free Software Foundation; either version 3, or (at your option)
   7 // any later version.
   8
   9 // This library is distributed in the hope that it will be useful,
  10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 // GNU General Public License for more details.
  13
  14 // You should have received a copy of the GNU General Public License along
  15 // with this library; see the file COPYING3.  If not see
  16 // <http://www.gnu.org/licenses/>.
  17
  18 // { dg-do run { target c++17 } }
  19
  20 #include <functional>
  21 #include <string_view>
  22 #include <cstring>
  23 #include <cctype>
  24 #include <algorithm>
  25 #include <testsuite_hooks.h>
  26
  27 #ifndef __cpp_lib_boyer_moore_searcher
  28 # error "Feature-test macro for searchers missing"
  29 #elif __cpp_lib_boyer_moore_searcher < 201603
  30 # error "Feature-test macro for searchers has wrong value"
  31 #endif
  32
  33 using std::default_searcher;
  34 using std::boyer_moore_searcher;
  35 using std::boyer_moore_horspool_searcher;
  36
  37 void
  38 test01()
  39 {
  40   const char s[] = { 'a', (char)-97, 'a', '\0' };
  41   const char* needles[] = {
  42     s, "", "a", "aa", "aaa", "ab", "cd", "abcd", "abcdabcd", "abcabcd"
  43   };
  44   const char* haystacks[] = {
  45     s, "", "a", "aa", "aaa", "ab", "cd", "abcd", "abcdabcd", "abcabcd",
  46     "aaaaaaa", "aabaa", "aaacab", "cdabcdab", "abcdabcd", "xyzabcdxyz"
  47   };
  48
  49   for (auto n : needles)
  50   {
  51     auto nlen = std::strlen(n);
  52     auto ne = n + nlen;
  53     default_searcher d(n, ne);
  54     boyer_moore_searcher bm(n, ne);
  55     boyer_moore_horspool_searcher bmh(n, ne);
  56     for (auto h : haystacks)
  57     {
  58       auto he = h + std::strlen(h);
  59       auto res = std::search(h, he, n, ne);
  60       auto d_res = d(h, he);
  61       VERIFY( d_res.first == res );
  62       if (res == he)
  63         VERIFY( d_res.second == d_res.first );
  64       else
  65         VERIFY( d_res.second == (d_res.first + nlen) );
  66       auto bm_res = bm(h, he);
  67       VERIFY( bm_res.first == res );
  68       if (res == he)
  69         VERIFY( bm_res.second == bm_res.first );
  70       else
  71         VERIFY( bm_res.second == (bm_res.first + nlen) );
  72       auto bmh_res = bmh(h, he);
  73       VERIFY( bmh_res.first == res );
  74       if (res == he)
  75         VERIFY( bmh_res.second == bmh_res.first );
  76       else
  77         VERIFY( bmh_res.second == (bmh_res.first + nlen) );
  78     }
  79   }
  80 }
  81
  82 void
  83 test02()
  84 {
  85   const wchar_t s[] = { L'a', (wchar_t)-97, L'a', L'\0' };
  86   const wchar_t* needles[] = {
  87     s, L"", L"a", L"aa", L"aaa", L"ab", L"cd", L"abcd", L"abcdabcd", L"abcabcd"
  88   };
  89   const wchar_t* haystacks[] = {
  90     s, L"", L"a", L"aa", L"aaa", L"ab", L"cd", L"abcd", L"abcdabcd", L"abcabcd",
  91     L"aaaaaaa", L"aabaa", L"aaacab", L"cdabcdab", L"abcdabcd", L"xyzabcdxyz"
  92   };
  93
  94   for (auto n : needles)
  95   {
  96     auto nlen = std::char_traits<wchar_t>::length(n);
  97     auto ne = n + nlen;
  98     default_searcher d(n, ne);
  99     boyer_moore_searcher bm(n, ne);
 100     boyer_moore_horspool_searcher bmh(n, ne);
 101     for (auto h : haystacks)
 102     {
 103       auto he = h + std::char_traits<wchar_t>::length(h);
 104       auto res = std::search(h, he, n, ne);
 105       auto d_res = d(h, he);
 106       VERIFY( d_res.first == res );
 107       if (res == he)
 108         VERIFY( d_res.second == d_res.first );
 109       else
 110         VERIFY( d_res.second == (d_res.first + nlen) );
 111       auto bm_res = bm(h, he);
 112       VERIFY( bm_res.first == res );
 113       if (res == he)
 114         VERIFY( bm_res.second == bm_res.first );
 115       else
 116         VERIFY( bm_res.second == (bm_res.first + nlen) );
 117       auto bmh_res = bmh(h, he);
 118       VERIFY( bmh_res.first == res );
 119       if (res == he)
 120         VERIFY( bmh_res.second == bmh_res.first );
 121       else
 122         VERIFY( bmh_res.second == (bmh_res.first + nlen) );
 123     }
 124   }
 125 }
 126
 127 void
 128 test03()
 129 {
 130   // custom predicate
 131   struct
 132   {
 133     static unsigned char
 134     norm(unsigned char c) { return std::isalnum(c) ? c : '#'; }
 135
 136     // equality
 137     bool operator()(char l, char r) const { return norm(l) == norm(r); }
 138
 139     // hash
 140     std::size_t operator()(char c) const { return std::hash<char>{}(norm(c)); }
 141   } eq;
 142
 143   const char* needle = " foo 123 ";
 144   const char* haystack = "*****foo*123******";
 145   auto nlen = std::strlen(needle);
 146   const char* ne = needle + nlen;
 147   const char* he = haystack + std::strlen(haystack);
 148
 149   default_searcher d(needle, ne, eq);
 150   boyer_moore_searcher bm(needle, ne, eq, eq);
 151   boyer_moore_horspool_searcher bmh(needle, ne, eq, eq);
 152
 153   auto res = std::search(haystack, he, needle, ne, eq);
 154   auto d_res = d(haystack, he);
 155   VERIFY( d_res.first == res );
 156   if (res == he)
 157     VERIFY( d_res.second == d_res.first );
 158   else
 159     VERIFY( d_res.second == (d_res.first + nlen) );
 160   auto bm_res = bm(haystack, he);
 161   VERIFY( bm_res.first == res );
 162   if (res == he)
 163     VERIFY( bm_res.second == bm_res.first );
 164   else
 165     VERIFY( bm_res.second == (bm_res.first + nlen) );
 166   auto bmh_res = bmh(haystack, he);
 167   VERIFY( bmh_res.first == res );
 168   if (res == he)
 169     VERIFY( bmh_res.second == bmh_res.first );
 170   else
 171     VERIFY( bmh_res.second == (bmh_res.first + nlen) );
 172 }
 173
 174 int
 175 main()
 176 {
 177   test01();
 178   test02();
 179   test03();
 180 }