3

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 proceed.

thanks in advance.

srinuvenu
  • 475
  • 1
  • 5
  • 11
  • Patricia tries aka radix trees are common for this. This might be somewhat helpful. http://stackoverflow.com/questions/911947/algorithm-steps-to-find-longest-prefix-search-in-patricia-trie – Duck Mar 28 '11 at 19:27

4 Answers4

2

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.

Goz
  • 61,365
  • 24
  • 124
  • 204
1

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.

stu
  • 8,461
  • 18
  • 74
  • 112
1

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.

Argote
  • 2,155
  • 1
  • 15
  • 20
  • Hi thnaks for the reply, actually this logic i have to implement in a router of a datacenter, where some tousands of ip's will be addedand searched per second! so can this BST help me out! or can you suggest any standard way to achieve this reqt. – srinuvenu Mar 28 '11 at 18:10
  • Well, in that case I suggest implementing a set or a bloom filter (due to higher performance). – Argote Mar 28 '11 at 18:51
  • Though it's also be useful to know what you need to do with the IP addresses and whether or not you want to remove them at any point. – Argote Mar 28 '11 at 18:51
  • Hi, i have implemented the slution by converting the ipaddress to interger and stored in sorted linkerlist and started searching for the required string in that data structure..but the performance was very very bad hen i was going on adding >5000 ip's per sec and searching the list simultaneously! – srinuvenu Mar 30 '11 at 03:26
  • Well a LinkedList is obviously not the ideal tool for that job, as I mentioned you should use a set (probably with an internal tree or something) or a bloom filter (to check for negatives and THEN check for positives using something else). – Argote Mar 30 '11 at 04:42
0

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.

Zan Lynx
  • 53,022
  • 10
  • 79
  • 131
  • Thanks for the reply..i tried in different approaches, but was not successful can any body provide me c implementation for prefix tree to store and search for the ipaddress efficiently..thanks in advance for help – srinuvenu Mar 30 '11 at 03:28