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 void FilterSet::clear()
00137 {
00138 reFilters.clear();
00139 stringFiltersMatcher.clear();
00140 }
00141
00142
00143 void StringsMatcher::addString(const QString& pattern)
00144 {
00145 if (pattern.length() < 8) {
00146
00147 shortStringFilters.append(pattern);
00148 } else {
00149
00150
00151 stringFilters.append(pattern);
00152 int ind = stringFilters.size() - 1;
00153 int current = 0;
00154
00155
00156
00157
00158
00159
00160 int len = pattern.length();
00161 for (int k = len - 8; k < len; ++k)
00162 current = (current * HASH_P + pattern[k].unicode()) % HASH_Q;
00163
00164
00165 WTF::HashMap<int, QVector<int> >::iterator it = stringFiltersHash.find(current + 1);
00166 if (it == stringFiltersHash.end()) {
00167 QVector<int> list;
00168 list.append(ind);
00169 stringFiltersHash.add(current + 1, list);
00170 fastLookUp.setBit(current);
00171 } else {
00172 it->second.append(ind);
00173 }
00174 }
00175 }
00176
00177 void StringsMatcher::addWildedString(const QString& prefix, const QRegExp& rx)
00178 {
00179 rePrefixes.append(prefix);
00180 reFilters.append(rx);
00181 int index = -rePrefixes.size();
00182
00183 int current = 0;
00184 for (int k = 0; k < 8; ++k)
00185 current = (current * HASH_P + prefix[k].unicode()) % HASH_Q;
00186
00187
00188 WTF::HashMap<int, QVector<int> >::iterator it = stringFiltersHash.find(current + 1);
00189 if (it == stringFiltersHash.end()) {
00190 QVector<int> list;
00191 list.append(index);
00192 stringFiltersHash.add(current + 1, list);
00193 fastLookUp.setBit(current);
00194 } else {
00195 it->second.append(index);
00196 }
00197 }
00198
00199 bool StringsMatcher::isMatched(const QString& str) const
00200 {
00201
00202 for (int i = 0; i < shortStringFilters.size(); ++i) {
00203 if (str.contains(shortStringFilters[i]))
00204 return true;
00205 }
00206
00207 int len = str.length();
00208 int k;
00209
00210 int current = 0;
00211 int next = 0;
00212
00213 for (k = 0; k < 8 && k < len; ++k)
00214 current = (current * HASH_P + str[k].unicode()) % HASH_Q;
00215
00216 WTF::HashMap<int, QVector<int> >::const_iterator hashEnd = stringFiltersHash.end();
00217
00218 for (k = 7; k < len; ++k, current = next) {
00219
00220
00221 if (k + 1 < len)
00222 next = (HASH_P * ((current + HASH_Q - ((HASH_MOD * str[k - 7].unicode()) % HASH_Q)) % HASH_Q) + str[k + 1].unicode()) % HASH_Q;
00223
00224 if (!fastLookUp.testBit(current))
00225 continue;
00226
00227
00228 WTF::HashMap<int, QVector<int> >::const_iterator it = stringFiltersHash.find(current + 1);
00229
00230
00231 if (it != hashEnd) {
00232 for (int j = 0; j < it->second.size(); ++j) {
00233 int index = it->second[j];
00234
00235 if (index >= 0) {
00236 int flen = stringFilters[index].length();
00237 if (k - flen + 1 >= 0 && stringFilters[index] == str.midRef(k - flen + 1 , flen))
00238 return true;
00239 } else {
00240 index = -index - 1;
00241 int flen = rePrefixes[index].length();
00242 if (k - 8 + flen < len && rePrefixes[index] == str.midRef(k - 7, flen) &&
00243 str.indexOf(reFilters[index], k - 7 + flen) == k - 7 + flen)
00244 return true;
00245 }
00246 }
00247 }
00248 }
00249
00250 return false;
00251 }
00252
00253 void StringsMatcher::clear()
00254 {
00255 stringFilters.clear();
00256 shortStringFilters.clear();
00257 reFilters.clear();
00258 rePrefixes.clear();
00259 stringFiltersHash.clear();
00260 fastLookUp.resize(HASH_Q);
00261 fastLookUp.fill(0, 0, HASH_Q);
00262 }
00263
00264 }
00265
00266