Due date:
First solution: Wed, May 24
Second solution: Tue May 30
START EARLY ON THIS ASSIGNMENT. DO NOT WAITIf you experience difficulty, ask for help early. Do not wait until the last minute to ask for help.
Try to turn in a high quality solution for your first version, so that the second version is just touch up. Do not skip the first version.
This is mainly an exercise in the use of dynamic memory allocation. It also uses a cgi program to process a web page query.
Hash tables are described in file table.cc.
The implementation has the difficulty that it has a fixed size table, and the table can fill up. Your assignment is to modify the table implementation so that the table does not fill up.
It is not acceptable merely to increase the fixed size to some very large value. That would be wasteful of memory when few things are actually put into the table. Instead, your new implementation must reallocate the table when it runs out of memory. Do this by adding another field to the table type, indicating the physical size of the array --- that is, how many slots the cell array currently has. When the cell array becomes nearly full, allocate a new, larger array, and copy everything that was in the old array into the new array. Be sure to update the field that indicates the physical size of the array of cells.
Watch out. In a hash table, the position of an item is computed based on a hash function, and the position computation depends on the physical size of the hash table. So when the physical size changes, the positions of entries also change. To copy the old values into the new array, you will need to do hashInsert calls, so that the positions are set correctly. Think about this.
When you allocate a new array, don't get just one more cell. If you do, then a growing hash table becomes very expensive, since each insertion needs to make a copy of the entire table. One idea is to double the size of the table when it is reallocated. At any rate, increase the size by some factor that is greater than one.
You will need to modify function hashFull. Do not delete it, since it is part of the data type, even if now a useless one. (It is possible, as far as you know, that someone has already written a program that uses these hash tables, and that employs function hashFull to ask whether the table is full. You need for such a program to continue to work with the new table implementation.) Your hash tables never fill up. Think carefully about the correct implementation of hashFull. Read the contract for hashFull to see what its advertised behavior is. How might some other program be using hashFull?
A second difficulty is that this implementation allows the table to become almost completely full. A hash table of the kind implemented here that is almost completely full is very inefficient to search. It is better to keep at least 1/4 of the cells empty. Modify the implementation to reallocate the table when it becomes 3/4 full. Be careful: if you use integer arithmetic, you might get incorrect results. For example, in C++, 3/4 is 0. How can you test whether x > (3/4)y using only integer arithmetic? Can you rearrange this inequality so that it does not require division?
File /export/stu/3510Abrahamson/prog1/form.html is a form that can be filled out. When the submit button is pushed, the values that were put into the form are passed to a cgi program called formquery.cgi. There is nothing really special about a cgi program; it is an ordinary program. The information on the form is sent to the cgi program as its standard input. For example, if you enter a name of Hilbert and a password of Topology, then the standard input to formquery.cgi will contain
LASTNAME=Hilbert&PASSWORD=TopologyProgram formquery.cgi is supposed to look up information in a file called grades. The lines are of the following form.
name password info name password info ...For example, file grades might contain the following.
Hilbert Topology A Grothendiek xxxxx B Dahl r:z$$ I am not finished grading your work. Sorry.The cgi program works by writing, to the standard output, a preamble describing what the form of the output is, followed by the page to show. To cause the web browser to display a new Html page, the preamble can be
Content-type = text/htmlThe Html page to be displayed follows the preamble in the standard output. (There is additional information provided to the cgi program. Some environment variables are set. For example, environment variable REQUEST_METHOD is set to POST and variable CONTENT_LENGTH is set to the number of characters passed to the cgi program in its standard input. The values of environment variables can be obtained from function getenv. We do not use these variables in this simple program.)
Most of formquery.cc is written for you. You need to write the main program. Write it. You will need to read the contracts of the prewritten functions. The main program should not be very long. Roughly 25 to 30 noncomment lines should suffice. That does not mean that you should not provide any comments!
Write a program to do the testing of the hash table implementation. Test things so that you think all aspects of the implementation have been tested. Do not be lulled into a false sense of security just because your program passes a few very simple tests. In the past, I have had assignments turned in whose tests did not even put enough things in the hash table to trigger a reallocation. As a result, the newly added code was never even run during the tests. Do not make that mistake. How can you be absolutely sure that you are running your new code?
After you are satisfied that the table implementation is working correctly, work on the cgi program. Compile it so that the executable code is put in file formquery.cgi. For example, a short compile line would be
g++ -g -Wall -o formquery.cgi formquery.cc table.cc(Of course, using a makefile is easier than typing this over and over.)
You can test your without using a web browser. Create your own grade file. Write some data files that are what the web browser might provide to your program. Run the program, redirecting the standard input to those files. For example, if you create a data file called testdata containing
LASTNAME=Hilbert&PASSWORD=Topologythen run your program using command
formquery.cgi <testdataThe program should print the Html page that would be sent to the browser for display.
When your cgi program works to your satisfaction, try it with a browser. Do the following.
http://darla.math.ecu.edu/~myid/prog1/formquery.htmlwhere you should replace myid by your login id.
Email me your solution, as described in the syllabus. Attach all three files table.h, table.cc and formquery.cc. Please do not rename them. Be sure that your name is in every file. Do not attach your test program. Do not put any part of your program in the body of the message.
I will compile and test your solution. I will also test your hash table implementation separately with another tester. Rest assured that I will insert many things into the table, enough to cause more than one reallocation. I will create more than one hash table as well, so your implementation must handle each hash table independently of any others. Be sure that your solution is prepared to link with my tester. It must, therefore, have the same function prototypes as the original implementation. If you change the function prototypes, it will be inconsistent with what my test program expects.
Note: Your solution is expected to compile. Solutions that do not compile will receive no credit, but will receive some feeback for the first version.