adblock plus定义的广告过滤列表非常好用，这里分析一下adblock plus的广告过滤规则
！ 开始表示注释
* 通配符，匹配任何字符串
@@ 以此开头表示白名单，
| 以此开始或者结束表示开始处或者结束处严格匹配，没有其他内容了
|| 以此开头会忽略协议规则进行匹配，比如忽略http，https等
^ 分隔符匹配除数字，字母，-，.,%以外的其他字符
$ 指明后面的是过滤类型，比如是是image还是script等
按照adblock plus的说法，这些最终都转换成了正则表达式来处理，具体怎么实现不是很清楚。
对于大多数情况来说运行最耗时间的就是匹配问题，类型，以及协议信息可以根据url分析出来，很容易分离，
因此这里重点介绍如何实现最核心的*，^的匹配，通过一个patternStep来减小嵌套次数
/*
get a much bigger step for *.
*/
static inline int patternStep( const char * s, const char * p)
{
//这里可以根据下一个字符多跳几个
char temp[8];
int step=0;
const char * t=p;
while(*t!='*' && *t!='^' && *t!='\0')
{
step++;
t++;
}
if(!step) //防止只有一个通配符的情况比如^,*
return 1;
memset(temp,0,sizeof(temp));
strncpy(temp,p,min(sizeof(temp)-1,step));
printf("temp=%s,step=%d\n",temp,step);
const char * res=strfind(s,temp);
if(!res) //没有找到
return strlen(s); //移动真整个字符串
else
return max(1,res-s); //找到第一个匹配的字符串的位置
}
/*
test if a given string and a pattern matches use adblock plus rule
give a string s and a pattern p ,
if they match,return 1, then return 0
*/
bool adbMatch(const char * s, const char * p,bool caseSensitivie=true) {
for (;;) {
switch(*p++) {
case '*' : // match 0-n of any characters
//这里可以根据下一个字符多跳几个
if (!*p) return true; // do trailing * quickly
while (!adbMatch(s, p,caseSensitivie))
{
if(!*s) return false;
s+=patternStep(s,p);
}
return true;
case '^':
if(isSeperator(*s))
{
s++;
break;
}
else
return false;//expect a sepetor,
case '\0': // end of pattern
return !*s;
default :
if (getCaseChar(*s++,caseSensitivie) !=
getCaseChar(*(p-1),caseSensitivie)) return false;
break;
}
}
}