我在写代理服务器。它将不同的规则应用于列表中匹配的网站。例如,我们可以阻止列表A和使用其他代理获取的名单B.匹配(搜索)C列表中的URL(实施白名单或黑名单)的最佳方法?
例如内容,列表A:
.google.com
blogger.com
sourceforge.net
ytimg.com
http://media-cache-*.pinterest.com/*
images-amazon.com
*.amazonaws.com
twitter.com
fbcdn.net
google-analytics.com
staticflickr.com
B组:
ytimg.com
youtube.com
目前,比赛功能是:
struct proxy_t *
match_list(char *url) {
// 2KB line should be enough
char buf[2048];
int pos = 0, size;
struct acllist *al = config->acl_h;
struct acl *node = al->data;
while (node != NULL) { // iterate list
pos = 0; // position in list file
size = strlen(node->data); // node->data holds a URL list
while (1) { // iterate each line in list
readline(buf, node->data, &pos, size);
if (buf[0] == 0) break;
if (strcasestr(url, buf) != NULL
|| !fnmatch(buf, url, FNM_CASEFOLD)) {
return node->proxy;
}
}
node = node->next;
}
printf("Not Matched\n");
return config->default_proxy;
}
也就是说,迭代两个列表文件,逐行读取,使用strcasestr和fnmatch匹配一个URL。
它工作正常。但是,如果列表变得越来越大,比如说每个列表和5个列表有10000行,那么我认为它不是一个有效的解决方案,因为它是一个O(N)算法。
我正在考虑为每条比赛线添加一个计数器。通过排序匹配线可以减少平均搜索长度。像这样:
.google.com|150
blogger.com|76
sourceforge.net|43
ytimg.com|22
有没有其他的想法呢?
这不是关于解析URL。这是关于如何有效地匹配URL列表。 – strongwillow 2013-02-12 09:08:46
您可能想要查看哈希表来存储URL或某种搜索树。 – 2013-02-12 09:16:39
谢谢大家。我终于整理出来了。无论使用散列表还是搜索树,都可以使用它的域(xxx.xx)。一旦我们找到节点(也是链表的头部),迭代列表并将其与** fnmatch **和** strstr **进行匹配。 – strongwillow 2013-02-13 06:58:34