Соответствующая структура данных для буфера пакетов

Question

Как реализовать буфер пакетов, где каждый пакет имеет форму:

typedef struct{
   int32 IP;     //4-byte IP-address
   int16 ID;     //unique sequence id
}t_Packet;

Какая должна быть наиболее подходящая структура данных, которая:

(1) позволяет собиратьне менее 8000 таких пакетов (быстрые операции вставки и удаления)
(2) позволяет очень быструю фильтрацию по IP-адресу, так что будут выбраны только пакеты с данным IP
(3) позволяет очень быстро найти операцию, используя идентификаторклавиша
(4) позволяет очень быстро (2), затем (3) в пределах отфильтрованных результатов?

Размер ОЗУ имеет значение, например, невозможно использовать огромную таблицу поиска.

Answer 1

Вы можете использовать Patricia Trie для фильтрации IP-адресов. Я считаю, что большинство сетевых маршрутизаторов используют эту структуру данных для IP-адресов IPV4. В литературе также есть другие попытки, разработанные для IP-адресов, которые вы можете использовать. Вот один из них: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.4871

Соответствуя каждому IP-адресу, теперь вы можете иметь хеш-таблицу на основе идентификатора.

Если IP-адреса являются «достаточно» случайными, вам может быть лучше использовать хеш-таблицу для фильтрации по IP, однако, поскольку IP-адреса хорошо вписываются в слово большинства машин, что делает поиск по хешу действительно быстрым и три не может действительно сэкономить вам много места.

Конечно, правильный выбор зависит от вашей ситуации ...

Answer 2

Создайте два индекса для данных (сохраняйте их последовательно для быстрых вставок и т. Д.), Один - дерево, разделенное по идентификатору, другой - дерево, разделенное по IP.

Если вы не можете позволить себе, по крайней мере, 8000 * sizeof (Packet) + 8000 * 12 + 8000 * 12 для данных + два индекса, то, честно говоря, перебор только 8000 элементов не займет много времени.

Это было бы намного проще реализовать на c ++, чем на c (хотя бы потому, что вы могли бы использовать boost :: multi_index или аналогичный)