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

   1 // Copyright (C) 2014-2019 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-options "-std=gnu++17" }
  19
  20 #include <functional>
  21 #include <cstring>
  22 #include <cctype>
  23 #ifdef _GLIBCXX_USE_WCHAR_T
  24 # include <cwchar>
  25 #endif
  26 #include <algorithm>
  27 #include <testsuite_hooks.h>
  28
  29 #ifndef __cpp_lib_boyer_moore_searcher
  30 # error "Feature-test macro for searchers missing"
  31 #elif __cpp_lib_boyer_moore_searcher < 201603
  32 # error "Feature-test macro for searchers has wrong value"
  33 #endif
  34
  35 using std::default_searcher;
  36 using std::boyer_moore_searcher;
  37 using std::boyer_moore_horspool_searcher;
  38
  39 void
  40 test01()
  41 {
  42   const char s[] = { 'a', (char)-97, 'a', '\0' };
  43   const char* needles[] = {
  44     s, "", "a", "aa", "aaa", "ab", "cd", "abcd", "abcdabcd", "abcabcd"
  45   };
  46   const char* haystacks[] = {
  47     s, "", "a", "aa", "aaa", "ab", "cd", "abcd", "abcdabcd", "abcabcd",
  48     "aaaaaaa", "aabaa", "aaacab", "cdabcdab", "abcdabcd", "xyzabcdxyz"
  49   };
  50
  51   for (auto n : needles)
  52   {
  53     auto nlen = std::strlen(n);
  54     auto ne = n + nlen;
  55     default_searcher d(n, ne);
  56     boyer_moore_searcher bm(n, ne);
  57     boyer_moore_horspool_searcher bmh(n, ne);
  58     for (auto h : haystacks)
  59     {
  60       auto he = h + std::strlen(h);
  61       auto res = std::search(h, he, n, ne);
  62       auto d_res = d(h, he);
  63       VERIFY( d_res.first == res );
  64       if (res == he)
  65         VERIFY( d_res.second == d_res.first );
  66       else
  67         VERIFY( d_res.second == (d_res.first + nlen) );
  68       auto bm_res = bm(h, he);
  69       VERIFY( bm_res.first == res );
  70       if (res == he)
  71         VERIFY( bm_res.second == bm_res.first );
  72       else
  73         VERIFY( bm_res.second == (bm_res.first + nlen) );
  74       auto bmh_res = bmh(h, he);
  75       VERIFY( bmh_res.first == res );
  76       if (res == he)
  77         VERIFY( bmh_res.second == bmh_res.first );
  78       else
  79         VERIFY( bmh_res.second == (bmh_res.first + nlen) );
  80     }
  81   }
  82 }
  83
  84 void
  85 test02()
  86 {
  87 #ifdef _GLIBCXX_USE_WCHAR_T
  88   const wchar_t s[] = { L'a', (wchar_t)-97, L'a', L'\0' };
  89   const wchar_t* needles[] = {
  90     s, L"", L"a", L"aa", L"aaa", L"ab", L"cd", L"abcd", L"abcdabcd", L"abcabcd"
  91   };
  92   const wchar_t* haystacks[] = {
  93     s, L"", L"a", L"aa", L"aaa", L"ab", L"cd", L"abcd", L"abcdabcd", L"abcabcd",
  94     L"aaaaaaa", L"aabaa", L"aaacab", L"cdabcdab", L"abcdabcd", L"xyzabcdxyz"
  95   };
  96
  97   for (auto n : needles)
  98   {
  99     auto nlen = std::wcslen(n);
 100     auto ne = n + nlen;
 101     default_searcher d(n, ne);
 102     boyer_moore_searcher bm(n, ne);
 103     boyer_moore_horspool_searcher bmh(n, ne);
 104     for (auto h : haystacks)
 105     {
 106       auto he = h + std::wcslen(h);
 107       auto res = std::search(h, he, n, ne);
 108       auto d_res = d(h, he);
 109       VERIFY( d_res.first == res );
 110       if (res == he)
 111         VERIFY( d_res.second == d_res.first );
 112       else
 113         VERIFY( d_res.second == (d_res.first + nlen) );
 114       auto bm_res = bm(h, he);
 115       VERIFY( bm_res.first == res );
 116       if (res == he)
 117         VERIFY( bm_res.second == bm_res.first );
 118       else
 119         VERIFY( bm_res.second == (bm_res.first + nlen) );
 120       auto bmh_res = bmh(h, he);
 121       VERIFY( bmh_res.first == res );
 122       if (res == he)
 123         VERIFY( bmh_res.second == bmh_res.first );
 124       else
 125         VERIFY( bmh_res.second == (bmh_res.first + nlen) );
 126     }
 127   }
 128 #endif
 129 }
 130
 131 void
 132 test03()
 133 {
 134   // custom predicate
 135   struct
 136   {
 137     static unsigned char
 138     norm(unsigned char c) { return std::isalnum(c) ? c : '#'; }
 139
 140     // equality
 141     bool operator()(char l, char r) const { return norm(l) == norm(r); }
 142
 143     // hash
 144     std::size_t operator()(char c) const { return std::hash<char>{}(norm(c)); }
 145   } eq;
 146
 147   const char* needle = " foo 123 ";
 148   const char* haystack = "*****foo*123******";
 149   auto nlen = std::strlen(needle);
 150   const char* ne = needle + nlen;
 151   const char* he = haystack + std::strlen(haystack);
 152
 153   default_searcher d(needle, ne, eq);
 154   boyer_moore_searcher bm(needle, ne, eq, eq);
 155   boyer_moore_horspool_searcher bmh(needle, ne, eq, eq);
 156
 157   auto res = std::search(haystack, he, needle, ne, eq);
 158   auto d_res = d(haystack, he);
 159   VERIFY( d_res.first == res );
 160   if (res == he)
 161     VERIFY( d_res.second == d_res.first );
 162   else
 163     VERIFY( d_res.second == (d_res.first + nlen) );
 164   auto bm_res = bm(haystack, he);
 165   VERIFY( bm_res.first == res );
 166   if (res == he)
 167     VERIFY( bm_res.second == bm_res.first );
 168   else
 169     VERIFY( bm_res.second == (bm_res.first + nlen) );
 170   auto bmh_res = bmh(haystack, he);
 171   VERIFY( bmh_res.first == res );
 172   if (res == he)
 173     VERIFY( bmh_res.second == bmh_res.first );
 174   else
 175     VERIFY( bmh_res.second == (bmh_res.first + nlen) );
 176 }
 177
 178 int
 179 main()
 180 {
 181   test01();
 182   test02();
 183   test03();
 184 }