KHTML
khtml_filter.cpp
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 #include "khtml_filter_p.h"
00024 #include <QDebug>
00025
00026
00027 #define HASH_P (1997)
00028 #define HASH_Q (17509)
00029
00030 #define HASH_MOD (523)
00031
00032 namespace khtml {
00033
00034 void FilterSet::addFilter(const QString& filterStr)
00035 {
00036 QString filter = filterStr;
00037
00038 if (filter.startsWith(QLatin1Char('!')))
00039 return;
00040
00041
00042 int first = 0;
00043 int last = filter.length() - 1;
00044 if (filter.startsWith(QLatin1String("@@")))
00045 first = 2;
00046
00047
00048 int dollar = filter.lastIndexOf(QLatin1Char('$'));
00049 if (dollar != -1)
00050 last = dollar - 1;
00051
00052
00053 if (first > last)
00054 return;
00055
00056 filter = filter.mid(first, last - first + 1);
00057
00058
00059 if (filter.length()>2 && filter.startsWith(QLatin1Char('/')) && filter.endsWith(QLatin1Char('/')))
00060 {
00061 QString inside = filter.mid(1, filter.length()-2);
00062 QRegExp rx(inside);
00063 reFilters.append(rx);
00064
00065 }
00066 else
00067 {
00068
00069
00070
00071
00072 first = 0;
00073 last = filter.length() - 1;
00074
00075 while (first < filter.length() && filter[first] == QLatin1Char('*'))
00076 ++first;
00077
00078 while (last >= 0 && filter[last] == QLatin1Char('*'))
00079 --last;
00080
00081 if (first > last)
00082 filter = QLatin1String("*");
00083 else
00084 filter = filter.mid(first, last - first + 1);
00085
00086
00087 if (filter.contains("*") || filter.contains("?"))
00088 {
00089
00090
00091 int aPos = filter.indexOf('*');
00092 if (aPos < 0)
00093 aPos = filter.length();
00094 int qPos = filter.indexOf('?');
00095 if (qPos < 0)
00096 qPos = filter.length();
00097 int pos = qMin(aPos, qPos);
00098 if (pos > 7) {
00099 QRegExp rx;
00100
00101 rx.setPatternSyntax(QRegExp::Wildcard);
00102 rx.setPattern(filter.mid(pos));
00103
00104 stringFiltersMatcher.addWildedString(filter.mid(0, pos), rx);
00105
00106 } else {
00107 QRegExp rx;
00108
00109 rx.setPatternSyntax(QRegExp::Wildcard);
00110 rx.setPattern(filter);
00111 reFilters.append(rx);
00112 }
00113 }
00114 else
00115 {
00116
00117 stringFiltersMatcher.addString(filter);
00118 }
00119 }
00120 }
00121
00122 bool FilterSet::isUrlMatched(const QString& url)
00123 {
00124 if (stringFiltersMatcher.isMatched(url))
00125 return true;
00126
00127 for (int c = 0; c < reFilters.size(); ++c)
00128 {
00129 if (url.contains(reFilters[c]))
00130 return true;
00131 }
00132
00133 return false;
00134 }
00135
00136 QString FilterSet::urlMatchedBy(const QString& url)
00137 {
00138 QString by;
00139
00140 if (stringFiltersMatcher.isMatched(url, &by))
00141 return by;
00142
00143 for (int c = 0; c < reFilters.size(); ++c)
00144 {
00145 if (url.contains(reFilters[c]))
00146 {
00147 by = reFilters[c].pattern();
00148 break;
00149 }
00150 }
00151
00152 return by;
00153 }
00154
00155 void FilterSet::clear()
00156 {
00157 reFilters.clear();
00158 stringFiltersMatcher.clear();
00159 }
00160
00161
00162 void StringsMatcher::addString(const QString& pattern)
00163 {
00164 if (pattern.length() < 8) {
00165
00166 shortStringFilters.append(pattern);
00167 } else {
00168
00169
00170 stringFilters.append(pattern);
00171 int ind = stringFilters.size() - 1;
00172 int current = 0;
00173
00174
00175
00176
00177
00178
00179 int len = pattern.length();
00180 for (int k = len - 8; k < len; ++k)
00181 current = (current * HASH_P + pattern[k].unicode()) % HASH_Q;
00182
00183
00184 WTF::HashMap<int, QVector<int> >::iterator it = stringFiltersHash.find(current + 1);
00185 if (it == stringFiltersHash.end()) {
00186 QVector<int> list;
00187 list.append(ind);
00188 stringFiltersHash.add(current + 1, list);
00189 fastLookUp.setBit(current);
00190 } else {
00191 it->second.append(ind);
00192 }
00193 }
00194 }
00195
00196 void StringsMatcher::addWildedString(const QString& prefix, const QRegExp& rx)
00197 {
00198 rePrefixes.append(prefix);
00199 reFilters.append(rx);
00200 int index = -rePrefixes.size();
00201
00202 int current = 0;
00203 for (int k = 0; k < 8; ++k)
00204 current = (current * HASH_P + prefix[k].unicode()) % HASH_Q;
00205
00206
00207 WTF::HashMap<int, QVector<int> >::iterator it = stringFiltersHash.find(current + 1);
00208 if (it == stringFiltersHash.end()) {
00209 QVector<int> list;
00210 list.append(index);
00211 stringFiltersHash.add(current + 1, list);
00212 fastLookUp.setBit(current);
00213 } else {
00214 it->second.append(index);
00215 }
00216 }
00217
00218 bool StringsMatcher::isMatched(const QString& str, QString *by) const
00219 {
00220
00221 for (int i = 0; i < shortStringFilters.size(); ++i) {
00222 if (str.contains(shortStringFilters[i]))
00223 {
00224 if (by != 0) *by = shortStringFilters[i];
00225 return true;
00226 }
00227 }
00228
00229 int len = str.length();
00230 int k;
00231
00232 int current = 0;
00233 int next = 0;
00234
00235 for (k = 0; k < 8 && k < len; ++k)
00236 current = (current * HASH_P + str[k].unicode()) % HASH_Q;
00237
00238 WTF::HashMap<int, QVector<int> >::const_iterator hashEnd = stringFiltersHash.end();
00239
00240 for (k = 7; k < len; ++k, current = next) {
00241
00242
00243 if (k + 1 < len)
00244 next = (HASH_P * ((current + HASH_Q - ((HASH_MOD * str[k - 7].unicode()) % HASH_Q)) % HASH_Q) + str[k + 1].unicode()) % HASH_Q;
00245
00246 if (!fastLookUp.testBit(current))
00247 continue;
00248
00249
00250 WTF::HashMap<int, QVector<int> >::const_iterator it = stringFiltersHash.find(current + 1);
00251
00252
00253 if (it != hashEnd) {
00254 for (int j = 0; j < it->second.size(); ++j) {
00255 int index = it->second[j];
00256
00257 if (index >= 0) {
00258 int flen = stringFilters[index].length();
00259 if (k - flen + 1 >= 0 && stringFilters[index] == str.midRef(k - flen + 1 , flen))
00260 {
00261 if (by != 0) *by = stringFilters[index];
00262 return true;
00263 }
00264 } else {
00265 index = -index - 1;
00266 int flen = rePrefixes[index].length();
00267 if (k - 8 + flen < len && rePrefixes[index] == str.midRef(k - 7, flen) &&
00268 str.indexOf(reFilters[index], k - 7 + flen) == k - 7 + flen)
00269 {
00270 if (by != 0) *by = rePrefixes[index]+reFilters[index].pattern();
00271 return true;
00272 }
00273 }
00274 }
00275 }
00276 }
00277
00278 return false;
00279 }
00280
00281 void StringsMatcher::clear()
00282 {
00283 stringFilters.clear();
00284 shortStringFilters.clear();
00285 reFilters.clear();
00286 rePrefixes.clear();
00287 stringFiltersHash.clear();
00288 fastLookUp.resize(HASH_Q);
00289 fastLookUp.fill(0, 0, HASH_Q);
00290 }
00291
00292 }
00293
00294