include/QtCore/qstaticlatin1stringmatcher.h

0001 // Copyright (C) 2023 The Qt Company Ltd.
0002 // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
0003
0004 #ifndef QSTATICLATIN1STRINGMATCHER_H
0005 #define QSTATICLATIN1STRINGMATCHER_H
0006
0007 #include <functional>
0008 #include <iterator>
0009 #include <limits>
0010
0011 #include <QtCore/q20algorithm.h>
0012 #include <QtCore/qlatin1stringmatcher.h>
0013 #include <QtCore/qstring.h>
0014
0015 QT_BEGIN_NAMESPACE
0016
0017 #ifdef Q_CC_GHS
0018 #  define QT_STATIC_BOYER_MOORE_NOT_SUPPORTED
0019 #else
0020 namespace QtPrivate {
0021 template <class RandomIt1,
0022           class Hash = std::hash<typename std::iterator_traits<RandomIt1>::value_type>,
0023           class BinaryPredicate = std::equal_to<>>
0024 class q_boyer_moore_searcher
0025 {
0026 public:
0027     constexpr q_boyer_moore_searcher(RandomIt1 pat_first, RandomIt1 pat_last) : m_skiptable{}
0028     {
0029         const size_t n = std::distance(pat_first, pat_last);
0030         constexpr auto uchar_max = (std::numeric_limits<uchar>::max)();
0031         uchar max = n > uchar_max ? uchar_max : uchar(n);
0032         q20::fill(std::begin(m_skiptable), std::end(m_skiptable), max);
0033         Hash hf;
0034         RandomIt1 pattern = std::next(pat_first, n - max);
0035         while (max--)
0036             m_skiptable[hf(*pattern++)] = max;
0037     }
0038
0039     template <class RandomIt2>
0040     constexpr auto operator()(RandomIt2 first, RandomIt2 last, RandomIt1 pat_first,
0041                               RandomIt1 pat_last) const
0042     {
0043         struct R
0044         {
0045             RandomIt2 begin, end;
0046         };
0047         Hash hf;
0048         BinaryPredicate pred;
0049         auto pat_length = std::distance(pat_first, pat_last);
0050         if (pat_length == 0)
0051             return R{ first, first };
0052
0053         auto haystack_length = std::distance(first, last);
0054         if (haystack_length < pat_length)
0055             return R{ last, last };
0056
0057         const qsizetype pl_minus_one = qsizetype(pat_length - 1);
0058         RandomIt2 current = first + pl_minus_one;
0059
0060         qsizetype skip = 0;
0061         while (current < last - skip) {
0062             current += skip;
0063             skip = m_skiptable[hf(*current)];
0064             if (!skip) {
0065                 // possible match
0066                 while (skip < pat_length) {
0067                     if (!pred(hf(*(current - skip)), hf(pat_first[pl_minus_one - skip])))
0068                         break;
0069                     skip++;
0070                 }
0071                 if (skip > pl_minus_one) { // we have a match
0072                     auto match = current + 1 - skip;
0073                     return R{ match, match + pat_length };
0074                 }
0075
0076                 // If we don't have a match we are a bit inefficient as we only skip by one
0077                 // when we have the non matching char in the string.
0078                 if (m_skiptable[hf(*(current - skip))] == pat_length)
0079                     skip = pat_length - skip;
0080                 else
0081                     skip = 1;
0082             }
0083         }
0084
0085         return R{ last, last };
0086     }
0087
0088 private:
0089     alignas(16) uchar m_skiptable[256];
0090 };
0091 } // namespace QtPrivate
0092
0093 template <Qt::CaseSensitivity CS, size_t N>
0094 class QStaticLatin1StringMatcher
0095 {
0096     static_assert(N > 2,
0097                   "QStaticLatin1StringMatcher makes no sense for finding a single-char pattern");
0098
0099     QLatin1StringView m_pattern;
0100     using Hasher = std::conditional_t<CS == Qt::CaseSensitive, QtPrivate::QCaseSensitiveLatin1Hash,
0101                                       QtPrivate::QCaseInsensitiveLatin1Hash>;
0102     QtPrivate::q_boyer_moore_searcher<const char *, Hasher> m_searcher;
0103
0104 public:
0105     explicit constexpr QStaticLatin1StringMatcher(QLatin1StringView patternToMatch) noexcept
0106         : m_pattern(patternToMatch),
0107           m_searcher(patternToMatch.begin(), patternToMatch.begin() + N - 1)
0108     {
0109     }
0110
0111     constexpr qsizetype indexIn(QLatin1StringView haystack, qsizetype from = 0) const noexcept
0112     { return indexIn_helper(haystack, from); }
0113
0114     constexpr qsizetype indexIn(QStringView haystack, qsizetype from = 0) const noexcept
0115     { return indexIn_helper(haystack, from); }
0116
0117 private:
0118     template <typename String>
0119     constexpr qsizetype indexIn_helper(String haystack, qsizetype from = 0) const noexcept
0120     {
0121         static_assert(QtPrivate::isLatin1OrUtf16View<String>);
0122
0123         if (from >= haystack.size())
0124             return -1;
0125
0126         const auto start = [haystack]() constexpr {
0127             if constexpr (std::is_same_v<String, QStringView>)
0128                 return haystack.utf16();
0129             else
0130                 return haystack.begin();
0131         }();
0132         const auto begin = start + from;
0133         const auto end = start + haystack.size();
0134         const auto r = m_searcher(begin, end, m_pattern.begin(), m_pattern.end());
0135         return r.begin == end ? -1 : std::distance(start, r.begin);
0136     }
0137 };
0138
0139 template <size_t N>
0140 constexpr auto qMakeStaticCaseSensitiveLatin1StringMatcher(const char (&patternToMatch)[N]) noexcept
0141 {
0142     return QStaticLatin1StringMatcher<Qt::CaseSensitive, N>(
0143             QLatin1StringView(patternToMatch, qsizetype(N) - 1));
0144 }
0145
0146 template <size_t N>
0147 constexpr auto
0148 qMakeStaticCaseInsensitiveLatin1StringMatcher(const char (&patternToMatch)[N]) noexcept
0149 {
0150     return QStaticLatin1StringMatcher<Qt::CaseInsensitive, N>(
0151             QLatin1StringView(patternToMatch, qsizetype(N) - 1));
0152 }
0153 #endif
0154
0155 QT_END_NAMESPACE
0156
0157 #endif // QSTATICLATIN1STRINGMATCHER_H