Таблица поиска IP в памяти C

Question

В настоящее время я экспериментирую с libpcap и различными приложениями на Си и пытаюсь сделать следующее.После инициализации программы я хотел бы загрузить IP-адреса из файла и сохранить их в памяти.Когда я получаю некоторые детали пакета для обработки, я хотел бы сравнить IP с набором IP, загруженных в память.

Каков наилучший способ / структура данных для реализации этого в C?Мне нужно приспособиться к росту списка и эффективному сопоставлению, поэтому я чувствую, что простой массив поиска был бы неправильным решением.Помощь

Answer 1

Ну, вероятно, вы никогда не будете удалять IP во время выполнения, просто добавляя. Если список не станет огромным, его сортировка не принесет больших результатов.

Учитывая эти два факта, я бы, вероятно, просто сложил их все в массив (большого размера) и выполнял линейный поиск при необходимости. Следите за тем, где находится конец данных в массиве, и добавлять новые записи туда будет несложно.

Если это действительно слишком медленно, вы можете создать хеш-таблицу. Это должно быть настроено на основе типичного содержимого вашей IP-карты, чтобы избежать коллизий, конечно (и разработано и отлажено, так как C не имеет хеш-кодов в стандарте). Немного PITA, но должно быть выполнимо.

Я бы не стал беспокоиться о чем-то промежуточном (предположительно, используя бинарный поиск для поиска). Если вам так не хватает скорости, вы можете пройти весь путь до конца.

Answer 2

Абсолютно наименьший объем работы для действительно приличной производительности, вероятно, будет состоять в том, чтобы просто использовать массив uint32_t.

При загрузке ваших данных, бросить каждый IP в массив, используя realloc() выращивать его по мере необходимости.Не забудьте использовать вменяемый шаблон роста, удваивая выделенную длину каждый раз, когда он заканчивается, это обычное явление и, вероятно, будет работать хорошо.

После загрузки сортируйте массив с помощью простого вызова http://linux.die.net/man/3/qsort.

Затем вы можете быстро выполнить поиск в массиве, используя <a href="http://linux.die.net/man/3/bsearch" rel="nofollow">bsearch()</a>.

Так как в нем используются только стандартные функции, он будет очень маленьким в коде и, следовательно, простым для понимания и быстрым для написания.Никаких зависимостей и никакого времени, затрачиваемого на поиск разумных библиотек или на создание собственных структур данных более высокого уровня.Но поскольку он использует бинарный поиск, он будет довольно быстрым.

Answer 3

Многое зависит от количества IP-адресов, которые вы, вероятно, будете иметь в своей таблице.

Для небольшого числа сбалансированное двоичное дерево (например, дерево AVL) должно работать достаточно хорошо. Он требует значительных накладных расходов (2 указателя на узел), но, пока количество узлов невелико, это, вероятно, не является большой проблемой (если вы не ориентируетесь на систему с ограниченной памятью). Вы также можете использовать гибрид, где один узел хранит до N IP-адресов в массиве. При полуобращенном выборе N это может снизить затраты на указатель и улучшить использование кэша.

Если у вас больше 10 КБ или около того, возможно, стоит подумать об использовании три.

Если у вас может быть действительно большое число, вы можете рассмотреть возможность использования простого набора битов, один бит на IP-адрес.

Редактировать: я должен добавить, что это также может зависеть от частоты вставок / удалений по сравнению с поиском. Одна гибридная структура, которую я нашел полезной в многих ситуациях, состоит в том, чтобы начать с отсортированного основного массива, а затем при добавлении элементов хранить их в отдельном массиве, который не отсортирован. Когда / если вторичный массив становится слишком большим, вы сортируете его и объединяете с основным массивом.