diff options
author | Edward Welbourne <edward.welbourne@qt.io> | 2019-05-27 19:13:54 +0200 |
---|---|---|
committer | Edward Welbourne <edward.welbourne@qt.io> | 2019-07-10 17:05:30 +0200 |
commit | a9aa206b7b8ac4e69f8c46233b4080e00e845ff5 (patch) | |
tree | 0d19cb1f1a3b9d79d322e6e63f6f72160977ca67 /src/corelib/text/qstringmatcher.cpp | |
parent | 85d3061c1cd4617ef09cb381320611c27da205a5 (diff) |
Move text-related code out of corelib/tools/ to corelib/text/
This includes byte array, string, char, unicode, locale, collation and
regular expressions.
Change-Id: I8b125fa52c8c513eb57a0f1298b91910e5a0d786
Reviewed-by: Volker Hilsheimer <volker.hilsheimer@qt.io>
Diffstat (limited to 'src/corelib/text/qstringmatcher.cpp')
-rw-r--r-- | src/corelib/text/qstringmatcher.cpp | 348 |
1 files changed, 348 insertions, 0 deletions
diff --git a/src/corelib/text/qstringmatcher.cpp b/src/corelib/text/qstringmatcher.cpp new file mode 100644 index 0000000000..167a467480 --- /dev/null +++ b/src/corelib/text/qstringmatcher.cpp @@ -0,0 +1,348 @@ +/**************************************************************************** +** +** Copyright (C) 2016 The Qt Company Ltd. +** Copyright (C) 2019 Mail.ru Group. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtCore module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include "qstringmatcher.h" + +QT_BEGIN_NAMESPACE + +static void bm_init_skiptable(const ushort *uc, qsizetype len, uchar *skiptable, Qt::CaseSensitivity cs) +{ + int l = int(qMin(len, qsizetype(255))); + memset(skiptable, l, 256 * sizeof(uchar)); + uc += len - l; + if (cs == Qt::CaseSensitive) { + while (l--) { + skiptable[*uc & 0xff] = l; + ++uc; + } + } else { + const ushort *start = uc; + while (l--) { + skiptable[foldCase(uc, start) & 0xff] = l; + ++uc; + } + } +} + +static inline qsizetype bm_find(const ushort *uc, qsizetype l, qsizetype index, const ushort *puc, qsizetype pl, + const uchar *skiptable, Qt::CaseSensitivity cs) +{ + if (pl == 0) + return index > l ? -1 : index; + const qsizetype pl_minus_one = pl - 1; + + const ushort *current = uc + index + pl_minus_one; + const ushort *end = uc + l; + if (cs == Qt::CaseSensitive) { + while (current < end) { + qsizetype skip = skiptable[*current & 0xff]; + if (!skip) { + // possible match + while (skip < pl) { + if (*(current - skip) != puc[pl_minus_one-skip]) + break; + ++skip; + } + if (skip > pl_minus_one) // we have a match + return (current - uc) - pl_minus_one; + + // in case we don't have a match we are a bit inefficient as we only skip by one + // when we have the non matching char in the string. + if (skiptable[*(current - skip) & 0xff] == pl) + skip = pl - skip; + else + skip = 1; + } + if (current > end - skip) + break; + current += skip; + } + } else { + while (current < end) { + qsizetype skip = skiptable[foldCase(current, uc) & 0xff]; + if (!skip) { + // possible match + while (skip < pl) { + if (foldCase(current - skip, uc) != foldCase(puc + pl_minus_one - skip, puc)) + break; + ++skip; + } + if (skip > pl_minus_one) // we have a match + return (current - uc) - pl_minus_one; + // in case we don't have a match we are a bit inefficient as we only skip by one + // when we have the non matching char in the string. + if (skiptable[foldCase(current - skip, uc) & 0xff] == pl) + skip = pl - skip; + else + skip = 1; + } + if (current > end - skip) + break; + current += skip; + } + } + return -1; // not found +} + +/*! + \class QStringMatcher + \inmodule QtCore + \brief The QStringMatcher class holds a sequence of characters that + can be quickly matched in a Unicode string. + + \ingroup tools + \ingroup string-processing + + This class is useful when you have a sequence of \l{QChar}s that + you want to repeatedly match against some strings (perhaps in a + loop), or when you want to search for the same sequence of + characters multiple times in the same string. Using a matcher + object and indexIn() is faster than matching a plain QString with + QString::indexOf() if repeated matching takes place. This class + offers no benefit if you are doing one-off string matches. + + Create the QStringMatcher with the QString you want to search + for. Then call indexIn() on the QString that you want to search. + + \sa QString, QByteArrayMatcher, QRegExp +*/ + +/*! + Constructs an empty string matcher that won't match anything. + Call setPattern() to give it a pattern to match. +*/ +QStringMatcher::QStringMatcher() + : d_ptr(nullptr), q_cs(Qt::CaseSensitive) +{ + memset(q_data, 0, sizeof(q_data)); +} + +/*! + Constructs a string matcher that will search for \a pattern, with + case sensitivity \a cs. + + Call indexIn() to perform a search. +*/ +QStringMatcher::QStringMatcher(const QString &pattern, Qt::CaseSensitivity cs) + : d_ptr(nullptr), q_pattern(pattern), q_cs(cs) +{ + p.uc = pattern.unicode(); + p.len = pattern.size(); + bm_init_skiptable((const ushort *)p.uc, p.len, p.q_skiptable, cs); +} + +/*! + \fn QStringMatcher::QStringMatcher(const QChar *uc, int length, Qt::CaseSensitivity cs) + \since 4.5 + + Constructs a string matcher that will search for the pattern referred to + by \a uc with the given \a length and case sensitivity specified by \a cs. +*/ +QStringMatcher::QStringMatcher(const QChar *uc, int len, Qt::CaseSensitivity cs) + : QStringMatcher(QStringView(uc, len), cs) +{ +} + +/*! + \fn QStringMatcher::QStringMatcher(QStringView pattern, Qt::CaseSensitivity cs = Qt::CaseSensitive) + \since 5.14 + + Constructs a string matcher that will search for \a pattern, with + case sensitivity \a cs. + + Call indexIn() to perform a search. +*/ +QStringMatcher::QStringMatcher(QStringView str, Qt::CaseSensitivity cs) + : d_ptr(nullptr), q_cs(cs) +{ + p.uc = str.data(); + p.len = int(str.size()); + bm_init_skiptable((const ushort *)p.uc, p.len, p.q_skiptable, cs); +} +/*! + Copies the \a other string matcher to this string matcher. +*/ +QStringMatcher::QStringMatcher(const QStringMatcher &other) + : d_ptr(nullptr) +{ + operator=(other); +} + +/*! + Destroys the string matcher. +*/ +QStringMatcher::~QStringMatcher() +{ + Q_UNUSED(d_ptr); +} + +/*! + Assigns the \a other string matcher to this string matcher. +*/ +QStringMatcher &QStringMatcher::operator=(const QStringMatcher &other) +{ + if (this != &other) { + q_pattern = other.q_pattern; + q_cs = other.q_cs; + memcpy(q_data, other.q_data, sizeof(q_data)); + } + return *this; +} + +/*! + Sets the string that this string matcher will search for to \a + pattern. + + \sa pattern(), setCaseSensitivity(), indexIn() +*/ +void QStringMatcher::setPattern(const QString &pattern) +{ + q_pattern = pattern; + p.uc = pattern.unicode(); + p.len = pattern.size(); + bm_init_skiptable((const ushort *)pattern.unicode(), pattern.size(), p.q_skiptable, q_cs); +} + +/*! + \fn QString QStringMatcher::pattern() const + + Returns the string pattern that this string matcher will search + for. + + \sa setPattern() +*/ + +QString QStringMatcher::pattern() const +{ + if (!q_pattern.isEmpty()) + return q_pattern; + return QString(p.uc, p.len); +} + +/*! + Sets the case sensitivity setting of this string matcher to \a + cs. + + \sa caseSensitivity(), setPattern(), indexIn() +*/ +void QStringMatcher::setCaseSensitivity(Qt::CaseSensitivity cs) +{ + if (cs == q_cs) + return; + bm_init_skiptable((const ushort *)p.uc, p.len, p.q_skiptable, cs); + q_cs = cs; +} + +/*! + Searches the string \a str from character position \a from + (default 0, i.e. from the first character), for the string + pattern() that was set in the constructor or in the most recent + call to setPattern(). Returns the position where the pattern() + matched in \a str, or -1 if no match was found. + + \sa setPattern(), setCaseSensitivity() +*/ +int QStringMatcher::indexIn(const QString &str, int from) const +{ + return int(indexIn(QStringView(str), from)); +} + +/*! + \since 4.5 + + Searches the string starting at \a str (of length \a length) from + character position \a from (default 0, i.e. from the first + character), for the string pattern() that was set in the + constructor or in the most recent call to setPattern(). Returns + the position where the pattern() matched in \a str, or -1 if no + match was found. + + \sa setPattern(), setCaseSensitivity() +*/ +int QStringMatcher::indexIn(const QChar *str, int length, int from) const +{ + return int(indexIn(QStringView(str, length), from)); +} + +/*! + \since 5.14 + + Searches the string \a str from character position \a from + (default 0, i.e. from the first character), for the string + pattern() that was set in the constructor or in the most recent + call to setPattern(). Returns the position where the pattern() + matched in \a str, or -1 if no match was found. + + \sa setPattern(), setCaseSensitivity() +*/ +qsizetype QStringMatcher::indexIn(QStringView str, qsizetype from) const +{ + if (from < 0) + from = 0; + return bm_find((const ushort *)str.data(), str.size(), from, + (const ushort *)p.uc, p.len, + p.q_skiptable, q_cs); +} + +/*! + \fn Qt::CaseSensitivity QStringMatcher::caseSensitivity() const + + Returns the case sensitivity setting for this string matcher. + + \sa setCaseSensitivity() +*/ + +/*! + \internal +*/ + +qsizetype qFindStringBoyerMoore( + QStringView haystack, qsizetype haystackOffset, + QStringView needle, Qt::CaseSensitivity cs) +{ + uchar skiptable[256]; + bm_init_skiptable((const ushort *)needle.data(), needle.size(), skiptable, cs); + if (haystackOffset < 0) + haystackOffset = 0; + return bm_find((const ushort *)haystack.data(), haystack.size(), haystackOffset, + (const ushort *)needle.data(), needle.size(), skiptable, cs); +} + +QT_END_NAMESPACE |