File searching

In the Linux shell, the file called nanpa. This file contains quite a comprehensive list of North American phone number prefixes, six digits long each, followed by a string describing the location served by phone numbers starting with this prefix. Again, on each line, the string is right next to the six digit prefix. It is suffixed with spaces so it is always exactly 25 digits long. Each line is separated from the next line by one next-line character . Hence each line consists of exactly 6 + 25 + 1 = 32 characters. The nanpa file is sorted by ascending prefixes. However, there are certain prefixes that do not correspond to any location: these prefixes do not figure in the file. With the script findlocation youll write for the section above, youll be able to search the nanpa file in O(n) using the Linux/UNIX/POSIX tools grep and sed. However, this method is not optimal from a complexity standpoint: a look-up in an ordered array or file can be done in O(log n). A typical POSIX-compatible environment supports the mmap system call. This system call allows for mapping the contents of a file on the filesystem, described by a file handle obtained with open, into memory: the mmap call returns a pointer which, when dereferenced, allows for reading the memory-mapped file by reading at the address given by the pointer, and for writing to the file, by writing to memory at the address provided by the pointer. For this section of the homework assignment, you must write, in C, a tool named findlocationfast which performs the same task as the script findlocation. The difference is that findlocationfast uses mmap to map the used file into memory. You are supposed to base your program only on the system calls open, lseek, mmap, munmap and close. You are not supposed to use level-3 buffered file manipulation calls, like fopen, fread, fprintf etc. Your tool may assume that the file to search is less than 2147483648 bytes in size. Your tool must not leak any memory, the memory-mapped region must be properly unmapped using munmap. All files opened must be properly closed. The status codes to be returned are the same as for findlocation. Your tool is not supposed to allocate any memory (using malloc or calloc) other than the memory obtained with mmap; using statically sized buffers on the stack is fine. The tool is not supposed to use strlen, strcmp, memset, memcpy or memmove; these functions are trivial to implement: just implement your own. The lookup algorithm must have O(log n) time complexity. The tool may gracefully1 fail on files that are non-regular or non-seekable.

For this section, you have to submit:

The source file findlocationfast.c which can be compiled to findlocationfast using gcc -Wall -O3 -o findlocationfast findlocationfast.c.