알맞은 검색알고리즘과 데이터 구조에 대한 질문

linux kernel의 netfilter나 snort 의 소스를 보시면 어느정도 최적화된 방법을 찾으실 수 있습니다.

가장 간단한 방법은 질문하신 분이 말씀하신 것과 같이 선형적인 검사 방법입니다.

any 값을 허용하고 IP 필드는 사실 192.168.0/24 와 같은 값도 허용해야 하므로 입력된 주소 & 마스크 == 원하는 주소 와 같이 하나하나 비교해야 합니다.

조금 더 최적화된 방법을 찾으시면 필터링 규칙을 그룹화하는 방법이 있습니다.

소스주소가 any인 그룹, 대상주소가 80인 그룹, ... 등과 같이 해서 비교할 대상을 줄이는 방법입니다.

이론적으로 가장 빠른 방법은 모든 경우를 테이블로 만들어 한번의 lookup으로 찾는 방법입니다.

bool filterTable[ 0xFFFFFFFF /* source IP */ ][ 0xFFFF /* source port */ ][ 0xFFFFFFFF /* target IP */][ 0xFFFF /* target port */];

를 만들면 됩니다. 하지만 너무 많은 메모리를 소비하므로 앞의 구룹화하는 방법이나 해쉬테이블을 이용하는 방법 또는 snort와 같이 btree (오래되서 정확하지 않습니다)를 사용하시면 됩니다.

하하 문제를 다시 읽어보다보니 any 라는 놈이 있었군요.
그렇다면 각 any를 이용해 조합 가능한 종류별로 hash table을 만들어 사용하는 편이 낫겠군요.

128개의 record에, 4개의 field를 조합 가능한 set이 15개(모든 field가 any인것은 필요 없겠죠..)이므로,

하나의 어레이에 record 가 들어가고, (128*4)
hash table이 가지는 값으로 위의 인덱스를 가지면 되므로... (hash_table_size*1)
총 15개의 hash table이 사용되므로
(hash_table_size*15 + 128*4)의 메모리로 해결할 수 있습니다.
검색은 하나의 hash table에서 검색하는 정도이므로 속도도 크케 나빠지지 않을 것입니다.

처음에 데이터들을 초기화하는게 좀 xxx 같을지는 모르겠지만.
제한된 환경하에서는 최적일것 같군요...

int hash_table_size = 128 * 2/3;
record  _configure[128];
int  _hash_table_for____X[hash_table_size];
int  _hash_table_for___X_[hash_table_size];
int  _hash_table_for__X__[hash_table_size];
int  _hash_table_for_X___[hash_table_size];
int  _hash_table_for___XX[hash_table_size];
...
int  _hash_table_for_XXX_[hash_table_size];
int  _hash_table_for_XXXX[hash_table_size];