how to store and serach for an ipv4 ipaddress in c more efficiently_问答_开发者

how to store and serach for an ipv4 ipaddress in c more efficiently

开发者 https://www.devze.com 2023-02-20 13:17 出处：网络

i have a requirement like,an efficient data-structure in c should take ipv4 address as input and store it , search in that stored datastructre on demand basis.

相关专题：c

i have a requirement like,an efficient data-structure in c should take ipv4 address as input and store it , search in that stored datastructre on demand basis. can we convert the ipaddress in to string and store it in a data-structure and check for its existence?if so how can we achieve this! can you please give me your valuable inputs to pr开发者_StackOverflowoceed.

thanks in advance.

Instead of converting it to a string store it as a 32-bit integer. Insert a new one into the correct place in a linked list or array or other data structure and everything is good. Finding an item is pretty easy if the list is sorted as you can use a binary search to locate the item (or locate the insertion point).

Personally I'd use an array in a lot of cases. It means insertion is more complex (as you need to copy the members above the insertion point up 1 but it is relatively quick (until you start talking about thousands of entries).

If you do need to be able to handle thousands of addresses then maybe a map structure is better for you.

an ip address is 4 octets. An octet is 8 bits which is a byte, so you can store an ip address in 4 bytes or an int on 32 bit machines, if whatever implementation you're using has a 32 bit int.

You can probably implement a set and use that.

You could also create a sort of tree where each node contains an octet and has up to 256 children (which are the next octet). The root would simply have the pointers to the first sets of octets.

Another option is to store them as unsigned integers in a BST or something like that.

If you need to store and search a whole lot of IP addresses you might want to use a radix tree.

I believe that the Linux kernel uses its own variant of the radix tree data structure for its IP related code such as routing tables. You may want to look at it for ideas.

If you have few addresses or just want something simple use a hash set.

If this is for a real application and if you want to be forward looking, you should include support for IPv6 addresses as well. As time goes on more computer systems every year will be using IPv6 addressing with IPv4 NAT addresses only as backup.