Project 2: DNS Cache

You are an engineer at BSNL, and your job is to maintain a record of all DNS entries. A DNS entry (simplistically speaking) is a map from a hostname to the corresponding IP address (e.g., "" to ""). The hostname is a string of arbitrary length, and the IP address is a 4-byte integer represented as "b3.b2.b1.b0" where bi is an unsigned byte less than 255.

The most common operations at BSNL are:
  1. Add(String URL, IPaddr IP): Add this entry to the database
  2. DeleteEntry(String URL): Delete the entry corresponding to URL
  3. GetIPfromURL(String URL): Return the IP address corresponding to the URL. The IP address should be returned as a string in the form "" which the given URL resolves to. If the URL is not found in the database, you should return the string "NotFound".
  4. GetURLfromIP(IPaddr IP): Return the string corresponding to the URL which would resolve to the given IP address. If the IP address is not found in the database, you should return the string "NotFound".
  5. FindLowestFreeIP(): Return the string corresponding to the lowest available IP address in the form "". We will not try to insert more than 2^32 entries into your database, so this function should always return a valid IP address.
Once again, your program should be able to read commands from a file and output the result of each command on a separate line. No other text should be printed on the standard output. Sample input and output are given in the support files. A file called should contain the main() function. Also include a file called README that briefly lists the data structures you used and their purpose.

Competition: We will have a competition for the fastest implementation. The input will be a mixture of different commands (similar to sample_input). For the correct programs, we will rank the programs on the basis of their running time. Assume that all five operations are equally frequent.

Support files:
sample_output (notice that no output is printed on an Add operation)

Bonus points

Also implement in C.


winners (only amongst those programs which strictly conformed to the specifications)