qstringmatcher.cpp

Absolute File Name:

/home/qt/qt5_coco/qt5/qtbase/src/corelib/tools/qstringmatcher.cpp

Source code

Switch to Preprocessed file

Line Source Count

1 /**************************************************************************** -

2 ** -

4 ** Contact: https://www.qt.io/licensing/ -

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 The Qt Company. For licensing terms -

14 ** and conditions see https://www.qt.io/terms-conditions. For further -

15 ** information use the contact form at https://www.qt.io/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 3 as published by the Free Software -

20 ** Foundation and appearing in the file LICENSE.LGPL3 included in the -

21 ** packaging of this file. Please review the following information to -

22 ** ensure the GNU Lesser General Public License version 3 requirements -

23 ** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. -

24 ** -

25 ** GNU General Public License Usage -

26 ** Alternatively, this file may be used under the terms of the GNU -

27 ** General Public License version 2.0 or (at your option) the GNU General -

28 ** Public license version 3 or any later version approved by the KDE Free -

29 ** Qt Foundation. The licenses are as published by the Free Software -

30 ** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 -

31 ** included in the packaging of this file. Please review the following -

32 ** information to ensure the GNU General Public License requirements will -

33 ** be met: https://www.gnu.org/licenses/gpl-2.0.html and -

34 ** https://www.gnu.org/licenses/gpl-3.0.html. -

35 ** -

36 ** $QT_END_LICENSE$ -

37 ** -

38 ****************************************************************************/ -

39 -

40 #include "qstringmatcher.h" -

41 -

42 QT_BEGIN_NAMESPACE -

43 -

44 static void bm_init_skiptable(const ushort *uc, int len, uchar *skiptable, Qt::CaseSensitivity cs) -

45 { -

46 int l = qMin(len, 255); -

47 memset(skiptable, l, 256*sizeof(uchar)); -

48 uc += len - l; -

49 if (cs == Qt::CaseSensitive) { -

50 while (l--) { -

51 skiptable[*uc & 0xff] = l; -

52 uc++; -

53 } -

54 } else { -

55 const ushort *start = uc; -

56 while (l--) { -

57 skiptable[foldCase(uc, start) & 0xff] = l; -

58 uc++; -

59 } -

60 } -

61 } -

62 -

63 static inline int bm_find(const ushort *uc, uint l, int index, const ushort *puc, uint pl, -

64 const uchar *skiptable, Qt::CaseSensitivity cs) -

65 { -

66 if (pl == 0) -

67 return index > (int)l ? -1 : index; -

68 const uint pl_minus_one = pl - 1; -

69 -

70 const ushort *current = uc + index + pl_minus_one; -

71 const ushort *end = uc + l; -

72 if (cs == Qt::CaseSensitive) { -

73 while (current < end) { -

74 uint skip = skiptable[*current & 0xff]; -

75 if (!skip) { -

76 // possible match -

77 while (skip < pl) { -

78 if (*(current - skip) != puc[pl_minus_one-skip]) -

79 break; -

80 skip++; -

81 } -

82 if (skip > pl_minus_one) // we have a match -

83 return (current - uc) - pl_minus_one; -

84 -

85 // in case we don't have a match we are a bit inefficient as we only skip by one -

86 // when we have the non matching char in the string. -

87 if (skiptable[*(current - skip) & 0xff] == pl) -

88 skip = pl - skip; -

89 else -

90 skip = 1; -

91 } -

92 if (current > end - skip) -

93 break; -

94 current += skip; -

95 } -

96 } else { -

97 while (current < end) { -

98 uint skip = skiptable[foldCase(current, uc) & 0xff]; -

99 if (!skip) { -

100 // possible match -

101 while (skip < pl) { -

102 if (foldCase(current - skip, uc) != foldCase(puc + pl_minus_one - skip, puc)) -

103 break; -

104 skip++; -

105 } -

106 if (skip > pl_minus_one) // we have a match -

107 return (current - uc) - pl_minus_one; -

108 // in case we don't have a match we are a bit inefficient as we only skip by one -

109 // when we have the non matching char in the string. -

110 if (skiptable[foldCase(current - skip, uc) & 0xff] == pl) -

111 skip = pl - skip; -

112 else -

113 skip = 1; -

114 } -

115 if (current > end - skip) -

116 break; -

117 current += skip; -

118 } -

119 } -

120 return -1; // not found -

121 } -

122 -

123 /*! -

124 \class QStringMatcher -

125 \inmodule QtCore -

126 \brief The QStringMatcher class holds a sequence of characters that -

127 can be quickly matched in a Unicode string. -

128 -

129 \ingroup tools -

130 \ingroup string-processing -

131 -

132 This class is useful when you have a sequence of \l{QChar}s that -

133 you want to repeatedly match against some strings (perhaps in a -

134 loop), or when you want to search for the same sequence of -

135 characters multiple times in the same string. Using a matcher -

136 object and indexIn() is faster than matching a plain QString with -

137 QString::indexOf() if repeated matching takes place. This class -

138 offers no benefit if you are doing one-off string matches. -

139 -

140 Create the QStringMatcher with the QString you want to search -

141 for. Then call indexIn() on the QString that you want to search. -

142 -

143 \sa QString, QByteArrayMatcher, QRegExp -

144 */ -

145 -

146 /*! -

147 Constructs an empty string matcher that won't match anything. -

148 Call setPattern() to give it a pattern to match. -

149 */ -

150 QStringMatcher::QStringMatcher() -

151 : d_ptr(0), q_cs(Qt::CaseSensitive) -

152 { -

153 memset(q_data, 0, sizeof(q_data)); -

154 } -

155 -

156 /*! -

157 Constructs a string matcher that will search for \a pattern, with -

158 case sensitivity \a cs. -

159 -

160 Call indexIn() to perform a search. -

161 */ -

162 QStringMatcher::QStringMatcher(const QString &pattern, Qt::CaseSensitivity cs) -

163 : d_ptr(0), q_pattern(pattern), q_cs(cs) -

164 { -

165 p.uc = pattern.unicode(); -

166 p.len = pattern.size(); -

167 bm_init_skiptable((const ushort *)p.uc, p.len, p.q_skiptable, cs); -

168 } -

169 -

170 /*! -

171 \fn QStringMatcher::QStringMatcher(const QChar *uc, int length, Qt::CaseSensitivity cs) -

172 \since 4.5 -

173 -

174 Constructs a string matcher that will search for the pattern referred to -

175 by \a uc with the given \a length and case sensitivity specified by \a cs. -

176 */ -

177 QStringMatcher::QStringMatcher(const QChar *uc, int len, Qt::CaseSensitivity cs) -

178 : d_ptr(0), q_cs(cs) -

179 { -

180 p.uc = uc; -

181 p.len = len; -

182 bm_init_skiptable((const ushort *)p.uc, len, p.q_skiptable, cs); -

183 } -

184 -

185 /*! -

186 Copies the \a other string matcher to this string matcher. -

187 */ -

188 QStringMatcher::QStringMatcher(const QStringMatcher &other) -

189 : d_ptr(0) -

190 { -

191 operator=(other); -

192 } -

193 -

194 /*! -

195 Destroys the string matcher. -

196 */ -

197 QStringMatcher::~QStringMatcher() -

198 { -

199 Q_UNUSED(d_ptr); -

200 } -

201 -

202 /*! -

203 Assigns the \a other string matcher to this string matcher. -

204 */ -

205 QStringMatcher &QStringMatcher::operator=(const QStringMatcher &other) -

206 { -

207 if (this != &other) { -

208 q_pattern = other.q_pattern; -

209 q_cs = other.q_cs; -

210 memcpy(q_data, other.q_data, sizeof(q_data)); -

211 } -

212 return *this; -

213 } -

214 -

215 /*! -

216 Sets the string that this string matcher will search for to \a -

217 pattern. -

218 -

219 \sa pattern(), setCaseSensitivity(), indexIn() -

220 */ -

221 void QStringMatcher::setPattern(const QString &pattern) -

222 { -

223 q_pattern = pattern; -

224 p.uc = pattern.unicode(); -

225 p.len = pattern.size(); -

226 bm_init_skiptable((const ushort *)pattern.unicode(), pattern.size(), p.q_skiptable, q_cs); -

227 } -

228 -

229 /*! -

230 \fn QString QStringMatcher::pattern() const -

231 -

232 Returns the string pattern that this string matcher will search -

233 for. -

234 -

235 \sa setPattern() -

236 */ -

237 -

238 QString QStringMatcher::pattern() const -

239 { -

240 if (!q_pattern.isEmpty()) -

241 return q_pattern; -

242 return QString(p.uc, p.len); -

243 } -

244 -

245 /*! -

246 Sets the case sensitivity setting of this string matcher to \a -

247 cs. -

248 -

249 \sa caseSensitivity(), setPattern(), indexIn() -

250 */ -

251 void QStringMatcher::setCaseSensitivity(Qt::CaseSensitivity cs) -

252 { -

253

if (cs == q_cs)

cs == q_cs	Description
TRUE	evaluated 3 times by 1 test Evaluated by: tst_QStringMatcher
FALSE	evaluated 2 times by 1 test Evaluated by: tst_QStringMatcher

2-3

254

return;

executed 3 times by 1 test: return;

Executed by:

tst_QStringMatcher

255 bm_init_skiptable((const ushort *)pq_pattern.uc, punicode(), q_pattern.len,size(), p.q_skiptable, cs); -

256 q_cs = cs; -

257

}

executed 2 times by 1 test: end of block

Executed by:

tst_QStringMatcher

258 -

259 /*! -

260 Searches the string \a str from character position \a from -

261 (default 0, i.e. from the first character), for the string -

262 pattern() that was set in the constructor or in the most recent -

263 call to setPattern(). Returns the position where the pattern() -

264 matched in \a str, or -1 if no match was found. -

265 -

266 \sa setPattern(), setCaseSensitivity() -

267 */ -

268 int QStringMatcher::indexIn(const QString &str, int from) const -

269 { -

270 if (from < 0) -

271 from = 0; -

272 return bm_find((const ushort *)str.unicode(), str.size(), from, -

273 (const ushort *)p.uc, p.len, -

274 p.q_skiptable, q_cs); -

275 } -

276 -

277 /*! -

278 \since 4.5 -

279 -

280 Searches the string starting at \a str (of length \a length) from -

281 character position \a from (default 0, i.e. from the first -

282 character), for the string pattern() that was set in the -

283 constructor or in the most recent call to setPattern(). Returns -

284 the position where the pattern() matched in \a str, or -1 if no -

285 match was found. -

286 -

287 \sa setPattern(), setCaseSensitivity() -

288 */ -

289 int QStringMatcher::indexIn(const QChar *str, int length, int from) const -

290 { -

291 if (from < 0) -

292 from = 0; -

293 return bm_find((const ushort *)str, length, from, -

294 (const ushort *)p.uc, p.len, -

295 p.q_skiptable, q_cs); -

296 } -

297 -

298 /*! -

299 \fn Qt::CaseSensitivity QStringMatcher::caseSensitivity() const -

300 -

301 Returns the case sensitivity setting for this string matcher. -

302 -

303 \sa setCaseSensitivity() -

304 */ -

305 -

306 /*! -

307 \internal -

308 */ -

309 -

310 int qFindStringBoyerMoore( -

311 const QChar *haystack, int haystackLen, int haystackOffset, -

312 const QChar *needle, int needleLen, Qt::CaseSensitivity cs) -

313 { -

314 uchar skiptable[256]; -

315 bm_init_skiptable((const ushort *)needle, needleLen, skiptable, cs); -

316 if (haystackOffset < 0) -

317 haystackOffset = 0; -

318 return bm_find((const ushort *)haystack, haystackLen, haystackOffset, -

319 (const ushort *)needle, needleLen, skiptable, cs); -

320 } -

321 -

322 QT_END_NAMESPACE -

Source code

Switch to Preprocessed file

Generated by Squish Coco Non-Commercial 4.3.0-BETA-master-30-08-2018-4cb69e9