Corresponding data structure for packet buffer

Question

How to implement a packet buffer, where each packet has the form:

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

What should be the most appropriate data structure that:

(1) allows you to collect at least 8,000 such packages (quick input and delete operations)
(2) allows very fast filtering using the IP address, so that only packets with the specified IP address will be selected (3) allows you to very quickly find the operation using the identifier as the key
(4) allows very fast (2), then (3) in the filtered results?

RAM size matters, for example. impossible to use a huge search table.

Answer 1

You can use Patricia Trie to filter IP addresses. I believe most network routers use this data structure for IPV4 IP addresses. There are also other attempts in the literature for IP addresses that you can use. Here is one of them: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.4871

Responding to each IP address, you can now have a hash table based on the identifier.

If the IP addresses are “random enough”, you might be better off using a hash table for IP-based filtering, although since the IP addresses fit nicely into the words of most machines, making a hash search very fast and trie may not really save you a lot of space.

Of course, the right choice depends on your situation ...

Answer 2

Create two indexes for the data (do not store them sequentially for quick inserts, etc.), one tree is divided by ID, and the other is a tree divided by IP.

If you cannot afford at least 8000 * sizeof (Packet) + 8000 * 12 + 8000 * 12 for data + two indexes, then, frankly, repeating only 8000 elements will not take a very long time.

It would be much easier to implement in C ++ than c (if only because you could use boost :: multi_index or the like)