On Mon, Dec 23, 2002 at 01:49:46PM +0200, Michail Litvak wrote:
AVS> на примере это выглядит так AVS> есть таблица 10.10.10.0/24 AVS> 20.20.20.0/22 AVS> и так далее AVS> вот и нужно чтобы при проверке адреса 10.10.10.1/24 находилось его AVS> вхождение в таблицу. AVS> Сейчас это делается перебором всех значений таблицы, что занимает достаточно AVS> много времени :(. AVS> Может каким-то образом захешировать значения таблицы?
Если я правильно понимаю - то это делается через radix tree, реализацию смотреть внутрях linux kernel или *BSD. /me когда-то писал перловый модуль, но оно потерялось :(
вариант - table = set of cidr-element cidr-element = [ base-address , mask ] тогда range-table = set of [ base-address & mask , high-address ] high-address = base-address & mask + (~mask + 1) (все диапазоны адресов) или low-table = set of [ base-address ] hi-table = set of [ high-address ] теперь сортируем обе таблицы по возрастанию и ищем: low-index = minimal l : low-table [ l ] > addr high-index = minimal h : high-table [ h ] < addr теперь: addr входит во все cidr-блоки с номерами от 1..(l-1) до (h+1..N) (это утверждение надо обдумать..) =================================================================== uanog mailing list. To Unsubscribe: send mail to majordomo@uanog.kiev.ua with "unsubscribe uanog" in the body of the message