The object of this assignment is to familiarize yourself with HashTables, dynamic memory allocation, more modules, makefiles and valgrind. (Son of "There are still no donuts to be counted for this assignment") The assignment is due April 1st at 11:59 pm (before midnight). The assignment will be turned in electronically via the turnin command. The name for the assignment is 352assign4, so when you are ready to submit your solutions, you'll need to do: turnin 352assign4 Makefile hash.h hash.c cstr.h cstr.c sizes.h Notice that there is no "main.c" for this assignment and none of the files you turnin will contain a "main": This is because you are truly writing some modules that we will test with the on-line test cases, where _WE_ write the main. The hash.{h,c} files contain the C source code for a HashTable module, and the cstr.{c,h} files contain C Source code for a simple C-style string module. The file sizes.h, of course, contains typedefs for the proper sizes, AND STILL DEPENDS ON YOU SETTING MACHINE32 or MACHINE64 properly (just copy it from your last assignment). YOU MUST DECOMPOSE YOUR PROGRAM INTO THE FILES AS DESCRIBED ABOVE OR YOU WILL LOSE CONSIDERABLE POINTS. When you are providing code for other people, you need to make sure the APIs and structure are as expected. Scenario: You are getting ready to write a C Preprocessor for one of the next assignments: one thing you notice you need is a data structure to map strings to strings (a HashTable). For example, whenever you see the following in your C source code: #define SIZE 10 you have to be able put the key ("SIZE") in a table and be able to lookup its value ("10") so when you see: int arr[SIZE]; You can textual replace SIZE with 10 to get: int arr[10]; This assignment is NOT writing the C preprocessor, it is only writing the major modules you will need in writing a C preprocessor (which may or may not be the next assignment...) There are 2 major modules for this assignment: (1) A very simple C-style string module: cstr.{h,c} (2) A reasonably complex HashTable module: hash.{h,c} The cstr module should support the following operations: /* Create a brand new copy of the given string on the heap */ char* StringConstruct (const char* s); /* Take a string constructed with the above, and give it back to memory */ void StringDestruct (char* s); /* Hash the given string into an int_u4 */ int_u4 StringHash (const char* s); The hash module should support the following operations: /* Create a HashTable with the given number of spaces */ HashTable* HashTableConstruct (int number_of_spaces); /* Destroy the HashTable and reclaim all of its string and table memory */ void HashTableDestruct (HashTable*); /* Return how many (key, value) pairs are currently in the table */ #define HASHTABLELENGTH(X) ((X)->length) /* Returns true is the table contains the given key. */ boolean HashTableContains (HashTable* this, const char* key); /* Insert the given key, value into the table. Copies the key and ** value into the table if they aren't there (and returns true ** indicating a new (key, value) pair was inserted). If the key was ** already in the table, it frees the old value and copies the new ** value in (returning false) */ boolean HashTableInsert (HashTable*this, const char* key, const char* value); /* Remove the given key, value from the table. Returns true if it ** finds and removes the (key, value) pair, false if the key was never ** there. */ boolean HashTableRemove (HashTable* this, const char* key); /* Lookup the given key and return a "reference" (not a copy) to the ** given value. If the (key) is in the table, this returns a peek at ** the value in the table (does not copy it: thus the user does not ** have to worry about freeing the return value, but he does have to ** be careful not to use the value before it gets freed from the ** table). If the key is NOT in the table, then it returns NULL */ char* HashTableLookup (HashTable* this, const char* key); Obviously, there will have to be a few more things than the prototypes above in your .h files but that's the crux of the interface for your modules. There is no apriori limit to how many items we can insert into tables, so performance may suffer if we exceed the number of spaces in the table (i.e., you will have to use dynamic memory allocation), but the table should still work with large number of items (see the onlone test cases). Also, you can have multiple instances of a HashTable. Makefile: Your makefile should support the following operations: make main # Builds both your cstr and hash modules and links them # in with whatever main.c is in the current directory make clean # Remove *.o, a.out, *.so, main files so we can start # with a clean environment to rebuild from scratch. Testing: This assignment will be tested in a variety of ways: (0) Do the test programs build with make? Although you don't provide a "main.c", the Makefile you provide should be able to support "make main" and compile and link your modules. We will supply the main.c to test your module. (1) Are your modules correct? We will have test cases that make sure lookups and inserts and deletes all work correctly so that we get the expected behavior. (2) Are your modules "memory clean"? Watching your memory allocation and deallocation is very important: If you forget to free a string, you will "leak" memory. If you write to a location you aren't supposed to (array bounds error), you will corrupt memory. We will be detecting these conditions using a program called valgrind which you will probably want to start using on your own programs. (3) Is it fast enough? Once the program works and is memory clean, there will be a testcase that makes sure that your program is reasonably fast: the whole purpose of a hash table is for speedy lookups: don't be implementing a (key, value) lookup using only linked lists. Also, DO NOT USE TREES (BST, AVL, RED-BLACK, etc.) to implement this assignment: implement some kind of hash table or you will be docked significant points.