1// Copyright (C) 2023 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3
4#ifndef QSTATICLATIN1STRINGMATCHER_H
5#define QSTATICLATIN1STRINGMATCHER_H
6
7#include <functional>
8#include <iterator>
9#include <limits>
10
11#include <QtCore/q20algorithm.h>
12#include <QtCore/qlatin1stringmatcher.h>
13#include <QtCore/qstring.h>
14
15QT_BEGIN_NAMESPACE
16
17#ifdef Q_CC_GHS
18# define QT_STATIC_BOYER_MOORE_NOT_SUPPORTED
19#else
20namespace QtPrivate {
21template <class RandomIt1,
22 class Hash = std::hash<typename std::iterator_traits<RandomIt1>::value_type>,
23 class BinaryPredicate = std::equal_to<>>
24class q_boyer_moore_searcher
25{
26public:
27 constexpr q_boyer_moore_searcher(RandomIt1 pat_first, RandomIt1 pat_last) : m_skiptable{}
28 {
29 const size_t n = std::distance(pat_first, pat_last);
30 constexpr auto uchar_max = (std::numeric_limits<uchar>::max)();
31 uchar max = n > uchar_max ? uchar_max : uchar(n);
32 q20::fill(first: std::begin(arr&: m_skiptable), last: std::end(arr&: m_skiptable), value: max);
33 Hash hf;
34 RandomIt1 pattern = std::next(pat_first, n - max);
35 while (max--)
36 m_skiptable[hf(*pattern++)] = max;
37 }
38
39 template <class RandomIt2>
40 constexpr auto operator()(RandomIt2 first, RandomIt2 last, RandomIt1 pat_first,
41 RandomIt1 pat_last) const
42 {
43 struct R
44 {
45 RandomIt2 begin, end;
46 };
47 Hash hf;
48 BinaryPredicate pred;
49 auto pat_length = std::distance(pat_first, pat_last);
50 if (pat_length == 0)
51 return R{ first, first };
52
53 auto haystack_length = std::distance(first, last);
54 if (haystack_length < pat_length)
55 return R{ last, last };
56
57 const qsizetype pl_minus_one = qsizetype(pat_length - 1);
58 RandomIt2 current = first + pl_minus_one;
59
60 qsizetype skip = 0;
61 while (current < last - skip) {
62 current += skip;
63 skip = m_skiptable[hf(*current)];
64 if (!skip) {
65 // possible match
66 while (skip < pat_length) {
67 if (!pred(hf(*(current - skip)), hf(pat_first[pl_minus_one - skip])))
68 break;
69 skip++;
70 }
71 if (skip > pl_minus_one) { // we have a match
72 auto match = current + 1 - skip;
73 return R{ match, match + pat_length };
74 }
75
76 // If we don't have a match we are a bit inefficient as we only skip by one
77 // when we have the non matching char in the string.
78 if (m_skiptable[hf(*(current - skip))] == pat_length)
79 skip = pat_length - skip;
80 else
81 skip = 1;
82 }
83 }
84
85 return R{ last, last };
86 }
87
88private:
89 alignas(16) uchar m_skiptable[256];
90};
91} // namespace QtPrivate
92
93template <Qt::CaseSensitivity CS, size_t N>
94class QStaticLatin1StringMatcher
95{
96 static_assert(N > 2,
97 "QStaticLatin1StringMatcher makes no sense for finding a single-char pattern");
98
99 QLatin1StringView m_pattern;
100 using Hasher = std::conditional_t<CS == Qt::CaseSensitive, QtPrivate::QCaseSensitiveLatin1Hash,
101 QtPrivate::QCaseInsensitiveLatin1Hash>;
102 QtPrivate::q_boyer_moore_searcher<const char *, Hasher> m_searcher;
103
104public:
105 explicit constexpr QStaticLatin1StringMatcher(QLatin1StringView patternToMatch) noexcept
106 : m_pattern(patternToMatch),
107 m_searcher(patternToMatch.begin(), patternToMatch.begin() + N - 1)
108 {
109 }
110
111 constexpr qsizetype indexIn(QLatin1StringView haystack, qsizetype from = 0) const noexcept
112 { return indexIn_helper(haystack, from); }
113
114 constexpr qsizetype indexIn(QStringView haystack, qsizetype from = 0) const noexcept
115 { return indexIn_helper(haystack, from); }
116
117private:
118 template <typename String>
119 constexpr qsizetype indexIn_helper(String haystack, qsizetype from = 0) const noexcept
120 {
121 static_assert(QtPrivate::isLatin1OrUtf16View<String>);
122
123 if (from >= haystack.size())
124 return -1;
125
126 const auto start = [haystack]() constexpr {
127 if constexpr (std::is_same_v<String, QStringView>)
128 return haystack.utf16();
129 else
130 return haystack.begin();
131 }();
132 const auto begin = start + from;
133 const auto end = start + haystack.size();
134 const auto r = m_searcher(begin, end, m_pattern.begin(), m_pattern.end());
135 return r.begin == end ? -1 : std::distance(start, r.begin);
136 }
137};
138
139template <size_t N>
140constexpr auto qMakeStaticCaseSensitiveLatin1StringMatcher(const char (&patternToMatch)[N]) noexcept
141{
142 return QStaticLatin1StringMatcher<Qt::CaseSensitive, N>(
143 QLatin1StringView(patternToMatch, qsizetype(N) - 1));
144}
145
146template <size_t N>
147constexpr auto
148qMakeStaticCaseInsensitiveLatin1StringMatcher(const char (&patternToMatch)[N]) noexcept
149{
150 return QStaticLatin1StringMatcher<Qt::CaseInsensitive, N>(
151 QLatin1StringView(patternToMatch, qsizetype(N) - 1));
152}
153#endif
154
155QT_END_NAMESPACE
156
157#endif // QSTATICLATIN1STRINGMATCHER_H
158

source code of qtbase/src/corelib/text/qstaticlatin1stringmatcher.h