tools/qstringmatcher.cpp

Source codeSwitch to Preprocessed file
LineSource CodeCoverage
1/**************************************************************************** -
2** -
3** Copyright (C) 2012 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:362973
yes
Evaluation Count:189
189-362973
52 while (l--) {
evaluated: l--
TRUEFALSE
yes
Evaluation Count:4400897
yes
Evaluation Count:362040
362040-4400897
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:4400259
4400259
56 } else {
executed: }
Execution Count:361619
361619
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:6096
yes
Evaluation Count:189
189-6096
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:6096
6096
62 }
executed: }
Execution Count:189
189
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:365490
34-365490
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:364511
yes
Evaluation Count:1212
1212-364511
75 while (current < end) {
evaluated: current < end
TRUEFALSE
yes
Evaluation Count:30302292
yes
Evaluation Count:56226
56226-30302292
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:214839
yes
Evaluation Count:30473768
214839-30473768
78 // possible match -
79 while (skip < pl) {
evaluated: skip < pl
TRUEFALSE
yes
Evaluation Count:728772
yes
Evaluation Count:196931
196931-728772
80 if (*(current - skip) != puc[pl_minus_one-skip])
evaluated: *(current - skip) != puc[pl_minus_one-skip]
TRUEFALSE
yes
Evaluation Count:17109
yes
Evaluation Count:709471
17109-709471
81 break;
executed: break;
Execution Count:17109
17109
82 skip++;
executed (the execution status of this line is deduced): skip++;
-
83 }
executed: }
Execution Count:712546
712546
84 if (skip > pl_minus_one) // we have a match
evaluated: skip > pl_minus_one
TRUEFALSE
yes
Evaluation Count:196975
yes
Evaluation Count:17109
17109-196975
85 return (current - uc) - pl_minus_one;
executed: return (current - uc) - pl_minus_one;
Execution Count:197102
197102
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:1972
yes
Evaluation Count:15137
1972-15137
90 skip = pl - skip;
executed: skip = pl - skip;
Execution Count:1972
1972
91 else -
92 skip = 1;
executed: skip = 1;
Execution Count:15137
15137
93 } -
94 if (current > end - skip)
evaluated: current > end - skip
TRUEFALSE
yes
Evaluation Count:106318
yes
Evaluation Count:30473377
106318-30473377
95 break;
executed: break;
Execution Count:106318
106318
96 current += skip;
executed (the execution status of this line is deduced): current += skip;
-
97 }
executed: }
Execution Count:30255380
30255380
98 } else {
executed: }
Execution Count:162544
162544
99 while (current < end) {
evaluated: current < end
TRUEFALSE
yes
Evaluation Count:1442
yes
Evaluation Count:315
315-1442
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:239
yes
Evaluation Count:1203
239-1203
102 // possible match -
103 while (skip < pl) {
evaluated: skip < pl
TRUEFALSE
yes
Evaluation Count:9568
yes
Evaluation Count:201
201-9568
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:38
yes
Evaluation Count:9530
38-9530
105 break;
executed: break;
Execution Count:38
38
106 skip++;
executed (the execution status of this line is deduced): skip++;
-
107 }
executed: }
Execution Count:9530
9530
108 if (skip > pl_minus_one) // we have a match
evaluated: skip > pl_minus_one
TRUEFALSE
yes
Evaluation Count:201
yes
Evaluation Count:38
38-201
109 return (current - uc) - pl_minus_one;
executed: return (current - uc) - pl_minus_one;
Execution Count:201
201
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:22
yes
Evaluation Count:16
16-22
113 skip = pl - skip;
executed: skip = pl - skip;
Execution Count:22
22
114 else -
115 skip = 1;
executed: skip = 1;
Execution Count:16
16
116 } -
117 if (current > end - skip)
evaluated: current > end - skip
TRUEFALSE
yes
Evaluation Count:696
yes
Evaluation Count:545
545-696
118 break;
executed: break;
Execution Count:696
696
119 current += skip;
executed (the execution status of this line is deduced): current += skip;
-
120 }
executed: }
Execution Count:545
545
121 }
executed: }
Execution Count:1011
1011
122 return -1; // not found
executed: return -1;
Execution Count:163555
163555
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:198
198
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:361644
361644
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:165480
1-165480
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:165481
165481
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:165481
165481
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:165481
165481
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:199802
0-199802
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:199915
199915
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:199915
199915
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:199915
199915
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:208
0-208
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:208
208
320 (const ushort *)needle, needleLen, skiptable, cs);
executed: return bm_find((const ushort *)haystack, haystackLen, haystackOffset, (const ushort *)needle, needleLen, skiptable, cs);
Execution Count:208
208
321} -
322 -
323QT_END_NAMESPACE -
324 -
Source codeSwitch to Preprocessed file
Generated by Squish Coco Non-Commercial