[Solved] Programming Assignment #4: HashyHash

In this program, you will implement hash tables with linear and quadraticprobing. Some of the functions in this assignment count the number ofcollisions that occur over a hash table’s lifetime and are designed to helpshow that the amortized cost of your hash table operations (insertion,search, and deletion) is really low when you have a good hash function.By completing this assignment, you will also learn a bit about functionpointers, and you will gain additional practice with dynamic memorymanagement.One of the very practical takeaways from this assignment is that you willlearn how to use valgrind to test your programs for memory leaks.When you’re finished, you will have a very solid implementation of hashtables that you can use for all kinds of things.AttachmentsHashyHash.h, primes.c, testcase*.c, output*.c, test-all.shDeliverablesHashyHash.c(Note: Capitalization of your filename matters!)1. OverviewIn this assignment, you will implement hash tables that use linear and quadratic probing and supportinsertion, search, and deletion operations. The hash tables will expand dynamically when they start toget too full, and they will keep track of how many operations have been performed on them, as well ashow many collisions have occurred over the course of their lifetimes.By tracking the number of operations performed on each hash table (insert, search, and delete), as wellas the total number of collisions encountered while executing those operations, you can gatherempirical data to demonstrate whether you have a good hash function that leads to few collisions onaverage. You can also use this data to convince yourself that, with very few collisions per operation onaverage, hash tables actually have the ability to yield very good runtimes for all the operations listed.Within each hash table, you will also store an indication of what probing mechanism is being used(linear or quadratic probing), as well as a pointer to the hash function that drives the hash table. Thatway, by passing a single hash table pointer to a function, you give that function everything it needs toknow in order to perform a variety of operations on the hash table.To facilitate all these goals, we have defined a powerful HashTable struct for you. (See Section 3,“HashyHash.h,” below.)2. Function PointersIn this assignment, each of your hash tables will be tightly coupled with a hash function that travelseverywhere your hash table goes, ensuring that you never get stuck in a situation where you want toperform an operation (insertion, search, or deletion) but have no idea what hash function was beingused with that hash table.These hash functions will be written outside of your hash table code, in our test case files. However,each of your hash tables will contain a pointer to one of those hash functions.I know what you’re thinking: “Whaattttt?! A pointer to a function?!” Yes, this is really happening. Andit’s not really any more complex than having a pointer to, say, an int or a double. Here’s how it works:First, suppose you have the following function in some source file:char mystery(int m, int n){return ‘a’ + (m * n * n * n) % 26;}Don’t worry too much about what that mystery() function does, because it’s total nonsense. The pointis, it takes two integers as its only input parameters, and it returns a single character (which happens tobe a character on the range ‘a’ through ‘z’).Inside any other function, you can declare a variable that is capable of pointing to mystery() like so:int main(void){// This just creates a function pointer. It is currently uninitialized.char (*foo)(int, int);return 0;}In general, the basic syntax for declaring a function pointer is:<return_type> (*<ptr_var_name>)(<input1_datatype>, <input2_datatype>, …);Setting up your function pointer to point to a function is super easy. The name of a function is basicallyalready a pointer (just like the name of an array is already a pointer to the base of that array). So, to setup our foo pointer to point to our mystery() function, we’d do this:int main(void){// This creates a function pointer and initializes it.char (*foo)(int, int) = mystery;return 0;}Voila! That foo variable is now a pointer to the mystery() function. We can still call mystery() directly,or we can call it by dereferencing foo – just like we can set the value of an integer variable directly orchange its value by dereferencing a pointer to that variable. The syntax for calling a function via afunction pointer is as follows:(*<ptr_var_name>)(<input1_value>, <input2_value>, …);For example:int main(void){char (*foo)(int, int) = mystery;printf(“Calling mystery indirectly: %c
”, (*foo)(5, 99));printf(“Calling mystery directly: %c
”, mystery(5, 99));return 0;}You’re probably asking, “Why would I ever need a function pointer?” or “Why is this happening tome?” This assignment provides one compelling example of the utility of function pointers: any timeyou need to strongly associate a function with a particular instance of some data structure (such as ahash table being strongly coupled with the hash function you’ve been using to insert keys into it),tucking a function pointer inside that data structure can help you achieve that.3. HashyHash.hWe have included a HashyHash.h header file that you must #include in your HashyHash.c source filelike so:#include “HashyHash.h”When including this header file, the capitalization of HashyHash.h matters! Filenames are casesensitive in Linux, and that is of course the operating system we’ll be using to test your code. You alsomust use quotes instead of angled brackets when including that header file, and you must not modifyHashyHash.h under any circumstances. If you’re using Code::Blocks, you will need to add theHashyHash.h header file to your project. See the instructions in Section 10, “Compilation and Testing(Code::Blocks).”In addition to some basic functional prototypes, the header file contains the following #definedirectives. These identifiers (UNUSED, DIRTY, HASH_ERR, and HASH_OK) will be used throughout yourcode. You should never hard-code a value like 0 or 1 in place of these identifiers. We might change theunderlying numeric values of these to something else when writing test cases to grade your program.// Use this to mark a cell unused. Do NOT use INT_MIN directly.#define UNUSED INT_MIN// Use this to mark a cell dirty. Do NOT use INT_MAX directly.#define DIRTY INT_MAX// Several functions require you to return this in the event of an error.#define HASH_ERR 0// Several functions require you to return this upon success.#define HASH_OK 1// Default capacity for new hash tables. See description of makeHashTable().#define DEFAULT_CAPACITY 5The header file also contains a ProbingType enum, which you will use to indicate whether each ofyour hash tables uses linear or quadratic probing. We used enums back in Program #1 (ChessMoves),but if you’re feeling a bit rusty on the syntax, please be sure to consult a C programming reference onthis topic.The header file also contains two struct definitions that you will use in this assignment: Firstly, there’s aHashStats struct. Each hash table has its own HashStats struct that contains two members, asdescribed below:typedef struct HashStats{// This field keeps track of how many insert, search, or delete operations// take place over this hash table’s lifetime.int opCount;// This field keeps track of how many collisions occur when performing// insert, search, or delete operations on this hash table.int collisions;} HashStats;After several operations have been performed on a hash table, dividing the number of collisions by thenumber of operations will tell you how many collisions took place per operation on average, which willgive you a clearer window into the average runtimes for these operations.Finally, HashyHash.h contains your HashTable struct:typedef struct HashTable{// Your hash table will store integer keys in this array.int *array;// The current capacity of your hash table (the length of ‘array’).int capacity;// The size of your hash table (the number of elements it contains).int size;// A pointer to the hash function for this hash table (initially NULL).unsigned int (*hashFunction)(int);// Probing type: LINEAR or QUADRATIC. Initialize to LINEAR by default.ProbingType probing;// A struct within a struct for maintaining stats on this hash table:// number of operations performed and number of collisions encountered.HashStats stats;} HashTable;4. Test Cases and the test-all.sh ScriptAs always, we’ve included multiple test cases with this assignment, which show some ways in whichwe might test your code. These test cases are not comprehensive. You should also create your own testcases if you want to test your code comprehensively.We’ve also included a script, test-all.sh, that will compile and run all test cases for you. You canrun it on Eustis by placing it in a directory with HashyHash.c, HashyHash.h, and all the test case files,and typing:bash test-all.sh5. OutputThe functions you write for this assignment should not produce any output. If your functions causeanything to print to the screen, it will interfere with our test case evaluation.Please be sure to disable or remove any printf() statements you have in your code before submittingthis assignment.6. Special Requirement: Using Valgrind to Test for Memory LeaksPart of the credit for this assignment will be awarded based on your ability to implement the programwithout memory leaks. To test for memory leaks, you can use a program called valgrind, which isinstalled on Eustis.To run your program through valgrind at the command line, compile your code with the -g flag andthen run valgrind, like so:gcc HashyHash.c testcase01.c -lm -gvalgrind –leak-check=yes ./a.outYou’ll want to repeat the above process for all the test cases released with this assignment.As you examine the output of valgrind, all you really need to know is that the magic phrase you’relooking for to indicate that you have no memory leaks is:All heap blocks were freed — no leaks are possibleFor help deciphering the output of valgrind, see the following link:http://valgrind.org/docs/manual/quick-start.html7. Prime Numbers and the primes.c Source FileThe primes.c file included with this assignment has a handy function that you’re welcome to copy andpaste into your HashyHash.c file. It uses the sqrt() function from math.h, so you’ll need to use the-lm flag to compile your source code:gcc HashyHash.c testcase01.c -lm8. Function RequirementsFunction descriptions for this assignment are included on the following several pages. Please do notinclude a main() function in your submission.HashTable *makeHashTable(int capacity);Description: This function creates a hash table. Start by dynamically allocating space for a newhash table, and then properly initializing all the members of that struct. Note that by default,hashFunction should be initialized to NULL, probing should be initialized to LINEAR, and arrayshould be initialized to a dynamically allocated integer array of length capacity. If the capacityparameter passed to this function is less than or equal to 0, you should use DEFAULT_CAPACITY(defined in HashyHash.h) to set the initial length of the array. All cells within the array shouldbe initialized to UNUSED (which is – you guessed it! – defined in HashyHash.h).Within this function, if any call to a memory allocation function fails, you should free anymemory that was dynamically allocated within this function up until that point and then returnNULL.Return Value: Return a pointer to the new hash table (or NULL if any call to a dynamic memoryallocation function fails).HashTable *destroyHashTable(HashTable *h);Description: Free all dynamically allocated memory associated with this hash table. Avoidsegmentation faults in the event that h is NULL.Return Value: NULLint setProbingMechanism(HashTable *h, ProbingType probing);Description: Within the hash table, set the probing field to either LINEAR or QUADRATIC,depending on the value of the probing parameter passed to this function.Return Value: If the function is successful, return HASH_OK (defined in HashyHash.h). If thefunction fails (either because h is NULL or because the function received a probing value otherthan LINEAR or QUADRATIC), return HASH_ERR (also defined in HashyHash.h).int setHashFunction(HashTable *h, unsigned int (*hashFunction)(int));Description: Within the hash table, set the hashFunction field to the hash function that ispassed as the second parameter to this function.Return Value: Return HASH_ERR if h is NULL. Otherwise, return HASH_OK (even if hashFunctionis NULL).int isAtLeastHalfEmpty(HashTable *h);Description: Determines whether the hash table is at least half empty.Runtime Restriction: This must be an O(1) function.Return Value: Return 1 if the hash table is at least half empty. If the hash table is less than halfempty (more than half full), or if h is NULL, return 0. (You may assume that the hash table’scapacity member will not be zero, although it’s good practice to guard against this, just in case.)int expandHashTable(HashTable *h);Description: Within the hash table, replace the array (whose length is currently capacity) with alonger array. If the hash table is set to use linear probing, the length of the new array should be(capacity * 2 + 1). If the hash table is set to use quadratic probing, the length of the new arrayshould be the first prime number that is greater than or equal to (capacity * 2 + 1). (Note thatthere is a handy function in primes.c that will help you generate prime numbers, and you’rewelcome to copy and paste it into your source code for this assignment.)After creating an expanded array, you should re-hash all the values from the old array (startingfrom index 0 and working your way up to index capacity – 1) into the new array. In doing so,you should increment the hash table’s collisions counter for each new collision that takes placeas you re-hash the old values into the new array. However, you should not increase the hashtable’s opCount counter for each of those insertion operations. (If our goal is to count theaverage number of collisions per operation performed on this hash table, then to be fair, ifinserting an element causes the table to expand, all the collisions that result should really beattributed to that one insertion operation – not all of the insertion operations that occur as a sideeffect when the hash table is expanded.) So, this function should affect the collisions count, butit should not affect the opCount of the hash table at all.After the array is expanded, all of its empty cells should be initialized to UNUSED, and it shouldnot have any cells marked as DIRTY.Within this function, be sure to free memory as needed in order to avoid memory leaks.Return Value: Return HASH_OK if the expansion of the hash table is successful. If it fails for anyreason (such as the failure of a memory allocation function), return HASH_ERR.int insert(HashTable *h, int key);Description: First and foremost, before even inserting the new element into the hash table,check that the hash table is still at least half empty – regardless of whether the table is usinglinear or quadratic probing. (You have a handy function that can do that for you.) If not, expandthe hash table as described above. (You have a handy function to do that for you, as well!)Using linear or quadratic probing (depending on the value of the hash table’s probing field) inconjunction with the hash table’s hashFunction, insert key into the hash table’s array. Be awarethat hashFunction might return very large values. You are responsible for modding by the tablelength to prevent array index out-of-bounds errors with the hash values produced by the hashfunction.While probing for a spot to insert key, increment the hash table’s collisions counter every time acollision occurs. (Note that finding an empty spot for the key should not count as a collision.)After you’ve inserted the key, increment the size and opCount for this hash table. (Each of thoseshould get incremented by 1.)Return Value: Return HASH_OK if the operation is successful. Otherwise, return HASH_ERR.(Some potential causes of failure include: h is NULL; within h, the hashFunction is NULL; orexpanding the hash table fails. As a failsafe measure, I also coded up my version of thisfunction to return HASH_ERR if it goes through capacity number of iterations without finding anopen spot to insert the key. That should not be possible if the table is expanding properly, butit’s a solid backup plan to help avoid an infinite loop just in case there’s a bug in the hash tableexpansion function.)int search(HashTable *h, int key);Description: Using linear or quadratic probing (depending on the value of the hash table’sprobing field) in conjunction with the hash table’s hashFunction, search for key in the hashtable’s array. Be aware that hashFunction might return very large values. You are responsiblefor modding by the table length to prevent array index out-of-bounds errors with the hashvalues produced by the hash function.While probing for the key, increment the hash table’s collisions counter every time a collisionoccurs with an element that is not the key. (Note that hitting an UNUSED cell should not count asa collision, and should allow us to return from the function right away. However, finding aDIRTY cell should count as a collision.) Note: The number of cells probed by this functionshould not exceed capacity. If you perform capacity iterations of your probing loop withoutfinding the key, break out and return.Be sure to increment the opCount for this hash table by 1 regardless of whether you find the keyor not.Return Value: If the key is found, return the index where it resides in the hash table.Otherwise, return -1. If h is NULL or the hashFunction member of the hash table is NULL, return-1. If there are multiple instances of key in the hash table, simply return the index of the firstone you encounter while probing.int delete(HashTable *h, int key);Description: Using linear or quadratic probing (depending on the value of the hash table’sprobing field) in conjunction with the hash table’s hashFunction, search for key in the hashtable’s array. If the key is found, delete it by setting the cell’s value to DIRTY.Be aware that hashFunction might return very large values. You are responsible for modding bythe table length to prevent array index out-of-bounds errors with the hash values produced bythe hash function.While probing for the key, increment the hash table’s collisions counter every time a collisionoccurs with an element that is not the key. (Note that hitting an UNUSED cell should not count asa collision, and should allow us to return from the function right away. However, finding aDIRTY cell should count as a collision and also requires that we continue searching through thetable.) Note: The number of cells probed by this function should not exceed capacity. If youperform capacity iterations of your probing loop without finding the key, break out and return.Be sure to increment the opCount for this hash table by 1 regardless of whether you find the keyor not, and decrement the size member if the key is successfully deleted.If you get a bit crafty, you can outsource most of the work for this function to your search()function. However, this is not strictly necessary.Side Note: A solid implementation of hash tables might shrink the array if it starts to get toosparse (in order to cut back on wasted memory), but we will avoid doing that in this assignment(simply to make our lives a bit easier).Return Value: If key is deleted successfully, return the index where it resided in the hash table.Otherwise, return -1. If h is NULL or the hashFunction member of the hash table is NULL, return-1. If there are multiple instances of key in the hash table, simply delete the first one youencounter while probing.double difficultyRating(void);Return Value: Return a double indicating how difficult you found this assignment on a scale of1.0 (ridiculously easy) through 5.0 (insanely difficult).double hoursSpent(void);Return Value: Return an estimate (greater than zero) of the number of hours you spent on thisassignment.9. Compilation and Testing (Linux/Mac Command Line)To compile multiple source files (.c files) at the command line:gcc HashyHash.c testcase01.c -lmBy default, this will produce an executable file called a.out, which you can run by typing:./a.outIf you want to name the executable file something else, use:gcc HashyHash.c testcase01.c -lm -o HashyHash.exe…and then run the program using:./HashyHash.exeRunning the program could potentially dump a lot of output to the screen. If you want to redirect youroutput to a text file in Linux, it’s easy. Just run the program using the following command, which willcreate a file called whatever.txt that contains the output from your program:./HashyHash.exe > whatever.txtLinux has a helpful command called diff for comparing the contents of two files, which is reallyhelpful here since we’ve provided several sample output files. You can see whether your outputmatches ours exactly by typing, e.g.:diff whatever.txt output01.txtIf the contents of whatever.txt and output01.txt are exactly the same, diff won’t have any output.It will just look like this:[email protected]:~$ diff whatever.txt output01.txt[email protected]:~$ _If the files differ, it will spit out some information about the lines that aren’t the same. For example:[email protected]:~$ diff whatever.txt output01.txt1c1< fail whale 🙁—> Success![email protected]:~$ _10.Compilation and Testing (Code::Blocks)The key to getting your program to include a custom header file in Code::Blocks (or any IDE) is tocreate a project. Here are the step-by-step instructions for creating a project in Code::Blocks andimporting HashyHash.h and the HashyHash.c file you’ve created (even if it’s just an empty file so far).1. Start Code::Blocks.2. Create a New Project (File → New → Project).3. Choose “Empty Project” and click “Go.”4. In the Project Wizard that opens, click “Next.”5. Input a title for your project (e.g., “HashyHash”).6. Pause to reflect on how much you’ve learned this semester. You are an impressive human being.7. Choose a folder (e.g., Desktop) where Code::Blocks can create a subdirectory for the project.8. Click “Finish.”Now you need to import your files. You have two options:1. Drag your source and header files into Code::Blocks. Then right click the tab for each file andchoose “Add file to active project.”– or –2. Go to Project → Add Files…. Then browse to the directory with the source and header files youwant to import. Select the files from the list (using CTRL-click to select multiple files). Click“Open.” In the dialog box that pops up, click “OK.”You should now be good to go. Try to build and run the project (F9). As a friendly reminder: Even ifyou develop your code with Code::Blocks on Windows, you ultimately have to transfer it to the Eustisserver to compile and test it there. See the following page (Section 9, “Compilation and Testing(Linux/Mac Command Line)”) for instructions on command line compilation in Linux