tools/qstringmatcher.cpp

Source codeSwitch to Preprocessed file
LineSource CodeCoverage
1/**************************************************************************** -
2** -
3** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies). -
4** Contact: http://www.qt-project.org/legal -
5** -
6** This file is part of the QtCore module of the Qt Toolkit. -
7** -
8** $QT_BEGIN_LICENSE:LGPL$ -
9** Commercial License Usage -
10** Licensees holding valid commercial Qt licenses may use this file in -
11** accordance with the commercial license agreement provided with the -
12** Software or, alternatively, in accordance with the terms contained in -
13** a written agreement between you and Digia. For licensing terms and -
14** conditions see http://qt.digia.com/licensing. For further information -
15** use the contact form at http://qt.digia.com/contact-us. -
16** -
17** GNU Lesser General Public License Usage -
18** Alternatively, this file may be used under the terms of the GNU Lesser -
19** General Public License version 2.1 as published by the Free Software -
20** Foundation and appearing in the file LICENSE.LGPL included in the -
21** packaging of this file. Please review the following information to -
22** ensure the GNU Lesser General Public License version 2.1 requirements -
23** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. -
24** -
25** In addition, as a special exception, Digia gives you certain additional -
26** rights. These rights are described in the Digia Qt LGPL Exception -
27** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. -
28** -
29** GNU General Public License Usage -
30** Alternatively, this file may be used under the terms of the GNU -
31** General Public License version 3.0 as published by the Free Software -
32** Foundation and appearing in the file LICENSE.GPL included in the -
33** packaging of this file. Please review the following information to -
34** ensure the GNU General Public License version 3.0 requirements will be -
35** met: http://www.gnu.org/copyleft/gpl.html. -
36** -
37** -
38** $QT_END_LICENSE$ -
39** -
40****************************************************************************/ -
41 -
42#include "qstringmatcher.h" -
43 -
44QT_BEGIN_NAMESPACE -
45 -
46static void bm_init_skiptable(const ushort *uc, int len, uchar *skiptable, Qt::CaseSensitivity cs) -
47{ -
48 int l = qMin(len, 255);
executed (the execution status of this line is deduced): int l = qMin(len, 255);
-
49 memset(skiptable, l, 256*sizeof(uchar));
executed (the execution status of this line is deduced): memset(skiptable, l, 256*sizeof(uchar));
-
50 uc += len - l;
executed (the execution status of this line is deduced): uc += len - l;
-
51 if (cs == Qt::CaseSensitive) {
evaluated: cs == Qt::CaseSensitive
TRUEFALSE
yes
Evaluation Count:363274
yes
Evaluation Count:196
196-363274
52 while (l--) {
evaluated: l--
TRUEFALSE
yes
Evaluation Count:4402100
yes
Evaluation Count:362450
362450-4402100
53 skiptable[*uc & 0xff] = l;
executed (the execution status of this line is deduced): skiptable[*uc & 0xff] = l;
-
54 uc++;
executed (the execution status of this line is deduced): uc++;
-
55 }
executed: }
Execution Count:4402031
4402031
56 } else {
executed: }
Execution Count:362157
362157
57 const ushort *start = uc;
executed (the execution status of this line is deduced): const ushort *start = uc;
-
58 while (l--) {
evaluated: l--
TRUEFALSE
yes
Evaluation Count:6258
yes
Evaluation Count:196
196-6258
59 skiptable[foldCase(uc, start) & 0xff] = l;
executed (the execution status of this line is deduced): skiptable[foldCase(uc, start) & 0xff] = l;
-
60 uc++;
executed (the execution status of this line is deduced): uc++;
-
61 }
executed: }
Execution Count:6258
6258
62 }
executed: }
Execution Count:196
196
63} -
64 -
65static inline int bm_find(const ushort *uc, uint l, int index, const ushort *puc, uint pl, -
66 const uchar *skiptable, Qt::CaseSensitivity cs) -
67{ -
68 if (pl == 0)
evaluated: pl == 0
TRUEFALSE
yes
Evaluation Count:34
yes
Evaluation Count:366322
34-366322
69 return index > (int)l ? -1 : index;
executed: return index > (int)l ? -1 : index;
Execution Count:34
34
70 const uint pl_minus_one = pl - 1;
executed (the execution status of this line is deduced): const uint pl_minus_one = pl - 1;
-
71 -
72 register const ushort *current = uc + index + pl_minus_one;
executed (the execution status of this line is deduced): register const ushort *current = uc + index + pl_minus_one;
-
73 const ushort *end = uc + l;
executed (the execution status of this line is deduced): const ushort *end = uc + l;
-
74 if (cs == Qt::CaseSensitive) {
evaluated: cs == Qt::CaseSensitive
TRUEFALSE
yes
Evaluation Count:365099
yes
Evaluation Count:1596
1596-365099
75 while (current < end) {
evaluated: current < end
TRUEFALSE
yes
Evaluation Count:34448589
yes
Evaluation Count:56502
56502-34448589
76 uint skip = skiptable[*current & 0xff];
executed (the execution status of this line is deduced): uint skip = skiptable[*current & 0xff];
-
77 if (!skip) {
evaluated: !skip
TRUEFALSE
yes
Evaluation Count:214917
yes
Evaluation Count:34619319
214917-34619319
78 // possible match -
79 while (skip < pl) {
evaluated: skip < pl
TRUEFALSE
yes
Evaluation Count:729602
yes
Evaluation Count:197278
197278-729602
80 if (*(current - skip) != puc[pl_minus_one-skip])
evaluated: *(current - skip) != puc[pl_minus_one-skip]
TRUEFALSE
yes
Evaluation Count:17128
yes
Evaluation Count:713188
17128-713188
81 break;
executed: break;
Execution Count:17128
17128
82 skip++;
executed (the execution status of this line is deduced): skip++;
-
83 }
executed: }
Execution Count:713561
713561
84 if (skip > pl_minus_one) // we have a match
evaluated: skip > pl_minus_one
TRUEFALSE
yes
Evaluation Count:197620
yes
Evaluation Count:17128
17128-197620
85 return (current - uc) - pl_minus_one;
executed: return (current - uc) - pl_minus_one;
Execution Count:197948
197948
86 -
87 // in case we don't have a match we are a bit inefficient as we only skip by one -
88 // when we have the non matching char in the string. -
89 if (skiptable[*(current - skip) & 0xff] == pl)
evaluated: skiptable[*(current - skip) & 0xff] == pl
TRUEFALSE
yes
Evaluation Count:1992
yes
Evaluation Count:15136
1992-15136
90 skip = pl - skip;
executed: skip = pl - skip;
Execution Count:1992
1992
91 else -
92 skip = 1;
executed: skip = 1;
Execution Count:15136
15136
93 } -
94 if (current > end - skip)
evaluated: current > end - skip
TRUEFALSE
yes
Evaluation Count:106478
yes
Evaluation Count:34729654
106478-34729654
95 break;
executed: break;
Execution Count:106478
106478
96 current += skip;
executed (the execution status of this line is deduced): current += skip;
-
97 }
executed: }
Execution Count:34336529
34336529
98 } else {
executed: }
Execution Count:162980
162980
99 while (current < end) {
evaluated: current < end
TRUEFALSE
yes
Evaluation Count:1586
yes
Evaluation Count:648
648-1586
100 uint skip = skiptable[foldCase(current, uc) & 0xff];
executed (the execution status of this line is deduced): uint skip = skiptable[foldCase(current, uc) & 0xff];
-
101 if (!skip) {
evaluated: !skip
TRUEFALSE
yes
Evaluation Count:273
yes
Evaluation Count:1313
273-1313
102 // possible match -
103 while (skip < pl) {
evaluated: skip < pl
TRUEFALSE
yes
Evaluation Count:9836
yes
Evaluation Count:209
209-9836
104 if (foldCase(current - skip, uc) != foldCase(puc + pl_minus_one - skip, puc))
evaluated: foldCase(current - skip, uc) != foldCase(puc + pl_minus_one - skip, puc)
TRUEFALSE
yes
Evaluation Count:64
yes
Evaluation Count:9772
64-9772
105 break;
executed: break;
Execution Count:64
64
106 skip++;
executed (the execution status of this line is deduced): skip++;
-
107 }
executed: }
Execution Count:9772
9772
108 if (skip > pl_minus_one) // we have a match
evaluated: skip > pl_minus_one
TRUEFALSE
yes
Evaluation Count:209
yes
Evaluation Count:64
64-209
109 return (current - uc) - pl_minus_one;
executed: return (current - uc) - pl_minus_one;
Execution Count:209
209
110 // in case we don't have a match we are a bit inefficient as we only skip by one -
111 // when we have the non matching char in the string. -
112 if (skiptable[foldCase(current - skip, uc) & 0xff] == pl)
evaluated: skiptable[foldCase(current - skip, uc) & 0xff] == pl
TRUEFALSE
yes
Evaluation Count:33
yes
Evaluation Count:31
31-33
113 skip = pl - skip;
executed: skip = pl - skip;
Execution Count:33
33
114 else -
115 skip = 1;
executed: skip = 1;
Execution Count:31
31
116 } -
117 if (current > end - skip)
evaluated: current > end - skip
TRUEFALSE
yes
Evaluation Count:739
yes
Evaluation Count:638
638-739
118 break;
executed: break;
Execution Count:739
739
119 current += skip;
executed (the execution status of this line is deduced): current += skip;
-
120 }
executed: }
Execution Count:638
638
121 }
executed: }
Execution Count:1387
1387
122 return -1; // not found
executed: return -1;
Execution Count:164367
164367
123} -
124 -
125/*! -
126 \class QStringMatcher -
127 \inmodule QtCore -
128 \brief The QStringMatcher class holds a sequence of characters that -
129 can be quickly matched in a Unicode string. -
130 -
131 \ingroup tools -
132 \ingroup string-processing -
133 -
134 This class is useful when you have a sequence of \l{QChar}s that -
135 you want to repeatedly match against some strings (perhaps in a -
136 loop), or when you want to search for the same sequence of -
137 characters multiple times in the same string. Using a matcher -
138 object and indexIn() is faster than matching a plain QString with -
139 QString::indexOf() if repeated matching takes place. This class -
140 offers no benefit if you are doing one-off string matches. -
141 -
142 Create the QStringMatcher with the QString you want to search -
143 for. Then call indexIn() on the QString that you want to search. -
144 -
145 \sa QString, QByteArrayMatcher, QRegExp -
146*/ -
147 -
148/*! -
149 Constructs an empty string matcher that won't match anything. -
150 Call setPattern() to give it a pattern to match. -
151*/ -
152QStringMatcher::QStringMatcher() -
153 : d_ptr(0), q_cs(Qt::CaseSensitive) -
154{ -
155 memset(q_data, 0, sizeof(q_data));
executed (the execution status of this line is deduced): memset(q_data, 0, sizeof(q_data));
-
156}
executed: }
Execution Count:14
14
157 -
158/*! -
159 Constructs a string matcher that will search for \a pattern, with -
160 case sensitivity \a cs. -
161 -
162 Call indexIn() to perform a search. -
163*/ -
164QStringMatcher::QStringMatcher(const QString &pattern, Qt::CaseSensitivity cs) -
165 : d_ptr(0), q_pattern(pattern), q_cs(cs) -
166{ -
167 p.uc = pattern.unicode();
executed (the execution status of this line is deduced): p.uc = pattern.unicode();
-
168 p.len = pattern.size();
executed (the execution status of this line is deduced): p.len = pattern.size();
-
169 bm_init_skiptable((const ushort *)p.uc, p.len, p.q_skiptable, cs);
executed (the execution status of this line is deduced): bm_init_skiptable((const ushort *)p.uc, p.len, p.q_skiptable, cs);
-
170}
executed: }
Execution Count:205
205
171 -
172/*! -
173 \fn QStringMatcher::QStringMatcher(const QChar *uc, int length, Qt::CaseSensitivity cs) -
174 \since 4.5 -
175 -
176 Constructs a string matcher that will search for the pattern referred to -
177 by \a uc with the given \a length and case sensitivity specified by \a cs. -
178*/ -
179QStringMatcher::QStringMatcher(const QChar *uc, int len, Qt::CaseSensitivity cs) -
180 : d_ptr(0), q_cs(cs) -
181{ -
182 p.uc = uc;
executed (the execution status of this line is deduced): p.uc = uc;
-
183 p.len = len;
executed (the execution status of this line is deduced): p.len = len;
-
184 bm_init_skiptable((const ushort *)p.uc, len, p.q_skiptable, cs);
executed (the execution status of this line is deduced): bm_init_skiptable((const ushort *)p.uc, len, p.q_skiptable, cs);
-
185}
executed: }
Execution Count:361842
361842
186 -
187/*! -
188 Copies the \a other string matcher to this string matcher. -
189*/ -
190QStringMatcher::QStringMatcher(const QStringMatcher &other) -
191 : d_ptr(0) -
192{ -
193 operator=(other);
executed (the execution status of this line is deduced): operator=(other);
-
194}
executed: }
Execution Count:1
1
195 -
196/*! -
197 Destroys the string matcher. -
198*/ -
199QStringMatcher::~QStringMatcher() -
200{ -
201} -
202 -
203/*! -
204 Assigns the \a other string matcher to this string matcher. -
205*/ -
206QStringMatcher &QStringMatcher::operator=(const QStringMatcher &other) -
207{ -
208 if (this != &other) {
partially evaluated: this != &other
TRUEFALSE
yes
Evaluation Count:1
no
Evaluation Count:0
0-1
209 q_pattern = other.q_pattern;
executed (the execution status of this line is deduced): q_pattern = other.q_pattern;
-
210 q_cs = other.q_cs;
executed (the execution status of this line is deduced): q_cs = other.q_cs;
-
211 memcpy(q_data, other.q_data, sizeof(q_data));
executed (the execution status of this line is deduced): memcpy(q_data, other.q_data, sizeof(q_data));
-
212 }
executed: }
Execution Count:1
1
213 return *this;
executed: return *this;
Execution Count:1
1
214} -
215 -
216/*! -
217 Sets the string that this string matcher will search for to \a -
218 pattern. -
219 -
220 \sa pattern(), setCaseSensitivity(), indexIn() -
221*/ -
222void QStringMatcher::setPattern(const QString &pattern) -
223{ -
224 q_pattern = pattern;
executed (the execution status of this line is deduced): q_pattern = pattern;
-
225 p.uc = pattern.unicode();
executed (the execution status of this line is deduced): p.uc = pattern.unicode();
-
226 p.len = pattern.size();
executed (the execution status of this line is deduced): p.len = pattern.size();
-
227 bm_init_skiptable((const ushort *)pattern.unicode(), pattern.size(), p.q_skiptable, q_cs);
executed (the execution status of this line is deduced): bm_init_skiptable((const ushort *)pattern.unicode(), pattern.size(), p.q_skiptable, q_cs);
-
228}
executed: }
Execution Count:12
12
229 -
230/*! -
231 \fn QString QStringMatcher::pattern() const -
232 -
233 Returns the string pattern that this string matcher will search -
234 for. -
235 -
236 \sa setPattern() -
237*/ -
238 -
239QString QStringMatcher::pattern() const -
240{ -
241 if (!q_pattern.isEmpty())
evaluated: !q_pattern.isEmpty()
TRUEFALSE
yes
Evaluation Count:1
yes
Evaluation Count:1
1
242 return q_pattern;
executed: return q_pattern;
Execution Count:1
1
243 return QString(p.uc, p.len);
executed: return QString(p.uc, p.len);
Execution Count:1
1
244} -
245 -
246/*! -
247 Sets the case sensitivity setting of this string matcher to \a -
248 cs. -
249 -
250 \sa caseSensitivity(), setPattern(), indexIn() -
251*/ -
252void QStringMatcher::setCaseSensitivity(Qt::CaseSensitivity cs) -
253{ -
254 if (cs == q_cs)
evaluated: cs == q_cs
TRUEFALSE
yes
Evaluation Count:3
yes
Evaluation Count:2
2-3
255 return;
executed: return;
Execution Count:3
3
256 bm_init_skiptable((const ushort *)q_pattern.unicode(), q_pattern.size(), p.q_skiptable, cs);
executed (the execution status of this line is deduced): bm_init_skiptable((const ushort *)q_pattern.unicode(), q_pattern.size(), p.q_skiptable, cs);
-
257 q_cs = cs;
executed (the execution status of this line is deduced): q_cs = cs;
-
258}
executed: }
Execution Count:2
2
259 -
260/*! -
261 Searches the string \a str from character position \a from -
262 (default 0, i.e. from the first character), for the string -
263 pattern() that was set in the constructor or in the most recent -
264 call to setPattern(). Returns the position where the pattern() -
265 matched in \a str, or -1 if no match was found. -
266 -
267 \sa setPattern(), setCaseSensitivity() -
268*/ -
269int QStringMatcher::indexIn(const QString &str, int from) const -
270{ -
271 if (from < 0)
evaluated: from < 0
TRUEFALSE
yes
Evaluation Count:1
yes
Evaluation Count:166263
1-166263
272 from = 0;
executed: from = 0;
Execution Count:1
1
273 return bm_find((const ushort *)str.unicode(), str.size(), from,
executed: return bm_find((const ushort *)str.unicode(), str.size(), from, (const ushort *)p.uc, p.len, p.q_skiptable, q_cs);
Execution Count:166264
166264
274 (const ushort *)p.uc, p.len,
executed: return bm_find((const ushort *)str.unicode(), str.size(), from, (const ushort *)p.uc, p.len, p.q_skiptable, q_cs);
Execution Count:166264
166264
275 p.q_skiptable, q_cs);
executed: return bm_find((const ushort *)str.unicode(), str.size(), from, (const ushort *)p.uc, p.len, p.q_skiptable, q_cs);
Execution Count:166264
166264
276} -
277 -
278/*! -
279 \since 4.5 -
280 -
281 Searches the string starting at \a str (of length \a length) from -
282 character position \a from (default 0, i.e. from the first -
283 character), for the string pattern() that was set in the -
284 constructor or in the most recent call to setPattern(). Returns -
285 the position where the pattern() matched in \a str, or -1 if no -
286 match was found. -
287 -
288 \sa setPattern(), setCaseSensitivity() -
289*/ -
290int QStringMatcher::indexIn(const QChar *str, int length, int from) const -
291{ -
292 if (from < 0)
partially evaluated: from < 0
TRUEFALSE
no
Evaluation Count:0
yes
Evaluation Count:199846
0-199846
293 from = 0;
never executed: from = 0;
0
294 return bm_find((const ushort *)str, length, from,
executed: return bm_find((const ushort *)str, length, from, (const ushort *)p.uc, p.len, p.q_skiptable, q_cs);
Execution Count:199947
199947
295 (const ushort *)p.uc, p.len,
executed: return bm_find((const ushort *)str, length, from, (const ushort *)p.uc, p.len, p.q_skiptable, q_cs);
Execution Count:199947
199947
296 p.q_skiptable, q_cs);
executed: return bm_find((const ushort *)str, length, from, (const ushort *)p.uc, p.len, p.q_skiptable, q_cs);
Execution Count:199947
199947
297} -
298 -
299/*! -
300 \fn Qt::CaseSensitivity QStringMatcher::caseSensitivity() const -
301 -
302 Returns the case sensitivity setting for this string matcher. -
303 -
304 \sa setCaseSensitivity() -
305*/ -
306 -
307/*! -
308 \internal -
309*/ -
310 -
311int qFindStringBoyerMoore( -
312 const QChar *haystack, int haystackLen, int haystackOffset, -
313 const QChar *needle, int needleLen, Qt::CaseSensitivity cs) -
314{ -
315 uchar skiptable[256];
executed (the execution status of this line is deduced): uchar skiptable[256];
-
316 bm_init_skiptable((const ushort *)needle, needleLen, skiptable, cs);
executed (the execution status of this line is deduced): bm_init_skiptable((const ushort *)needle, needleLen, skiptable, cs);
-
317 if (haystackOffset < 0)
partially evaluated: haystackOffset < 0
TRUEFALSE
no
Evaluation Count:0
yes
Evaluation Count:215
0-215
318 haystackOffset = 0;
never executed: haystackOffset = 0;
0
319 return bm_find((const ushort *)haystack, haystackLen, haystackOffset,
executed: return bm_find((const ushort *)haystack, haystackLen, haystackOffset, (const ushort *)needle, needleLen, skiptable, cs);
Execution Count:215
215
320 (const ushort *)needle, needleLen, skiptable, cs);
executed: return bm_find((const ushort *)haystack, haystackLen, haystackOffset, (const ushort *)needle, needleLen, skiptable, cs);
Execution Count:215
215
321} -
322 -
323QT_END_NAMESPACE -
324 -
Source codeSwitch to Preprocessed file
Generated by Squish Coco Non-Commercial