Здравствуйте, netch80, Вы писали:

S>> Ты серьезно? Там поиск по хэштаблице.

N>Прекратите курить эти опилки, плохой дым получается. Никакие хэш-таблицы непригодны в принципе, потому, что поиск должен срабатывать по _неточному_ совпадению (базовый адрес плюс длина сети покрывает этот адрес) с наиболее длинным префиксом. Хэш-таблицы срабатывают только при полном совпадении.
N>Всякие AVL/RB/B-tree тоже не годятся, потому что может быть, что совпадает не тот, у кого ближайший базовый адрес, а тот, у кого сеть накрывает этот адрес.

N>Там Radix tree в бинарном варианте. При совпадении пары baseaddr+prefixlen у двух записей срабатывает метрика (меньше — важнее).
N>Бывает ещё больше параметров.

N>Поясняю на примере: пусть есть записи:

N>10.1.2.0/23 (то есть 10.1.2.0...10.1.3.255)
N>10.1.0.0/16 (то есть 10.1.0.0...10.1.255.255) с метрикой 10.
N>10.1.0.0/16 опять же, с метрикой 20.
N>10.0.0.0/8 (то есть 10.0.0.0...10.255.255.255)
N>10.1.3.0/27 (то есть 10.1.3.0...10.1.3.31)

N>Для 10.1.3.4 сработать должен 10.1.3.0/27, потому что у него самый длинный префикс.

N>Для 10.1.244.1 сработает 10.1.0.0/16 с метрикой 10, базовые адреса и длины префикса одинаковые, включается метрика.

N>(Метрика задаётся источником. Например 0 — directly connected, 1 — static, дальше идут в определённом порядке внутренние динамические протоколы, потом внешние.)

Спасибо буду знать. Я про то, что никто не будет просто чесать по всем адресам, будет алгоритм для как минимум бинарного поиска.
В твоем примере это деревья.
Shmj то пишет, что проблемы в процессоре. При бинарном поиске все эти затраты нивелируются