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