我在寫代理服務器。它將不同的規則應用於列表中匹配的網站。例如,我們可以阻止列表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