hash_table.cpp

00001 /*
00002  Student Name: Chuong Dong
00003  Date: 03/27/2019
00004 
00005 =======================
00006 ECE 2035 Project 2-1:
00007 =======================
00008 This file provides definition for the structs and functions declared in the
00009 header file. It also contains helper functions that are not accessible from
00010 outside of the file.
00011 
00012 FOR FULL CREDIT, BE SURE TO TRY MULTIPLE TEST CASES and DOCUMENT YOUR CODE.
00013 
00014 ===================================
00015 Naming conventions in this file:
00016 ===================================
00017 1. All struct names use camel case where the first letter is capitalized.
00018   e.g. "HashTable", or "HashTableEntry"
00019 
00020 2. Variable names with a preceding underscore "_" will not be called directly.
00021   e.g. "_HashTable", "_HashTableEntry"
00022 
00023   Recall that in C, we have to type "struct" together with the name of the struct
00024   in order to initialize a new variable. To avoid this, in hash_table.h
00025   we use typedef to provide new "nicknames" for "struct _HashTable" and
00026   "struct _HashTableEntry". As a result, we can create new struct variables
00027   by just using:
00028     - "HashTable myNewTable;"
00029      or
00030     - "HashTableEntry myNewHashTableEntry;"
00031 
00032   The preceding underscore "_" simply provides a distinction between the names
00033   of the actual struct defition and the "nicknames" that we use to initialize
00034   new structs.
00035   [See Hidden Definitions section for more information.]
00036 
00037 3. Functions, their local variables and arguments are named with camel case, where
00038   the first letter is lower-case.
00039   e.g. "createHashTable" is a function. One of its arguments is "numBuckets".
00040        It also has a local variable called "newTable".
00041 
00042 4. The name of a struct member is divided by using underscores "_". This serves
00043   as a distinction between function local variables and struct members.
00044   e.g. "num_buckets" is a member of "HashTable".
00045 
00046 */
00047 
00048 /****************************************************************************
00049 * Include the Public Interface
00050 *
00051 * By including the public interface at the top of the file, the compiler can
00052 * enforce that the function declarations in the the header are not in
00053 * conflict with the definitions in the file. This is not a guarantee of
00054 * correctness, but it is better than nothing!
00055 ***************************************************************************/
00056 #include "hash_table.h"
00057 
00058 
00059 /****************************************************************************
00060 * Include other private dependencies
00061 *
00062 * These other modules are used in the implementation of the hash table module,
00063 * but are not required by users of the hash table.
00064 ***************************************************************************/
00065 #include <stdlib.h>   // For malloc and free
00066 #include <stdio.h>    // For printf
00067 
00068 
00069 /****************************************************************************
00070 * Hidden Definitions
00071 *
00072 * These definitions are not available outside of this file. However, because
00073 * the are forward declared in hash_table.h, the type names are
00074 * available everywhere and user code can hold pointers to these structs.
00075 ***************************************************************************/
00076 /**
00077  * This structure represents an a hash table.
00078  * Use "HashTable" instead when you are creating a new variable. [See top comments]
00079  */
00080 struct _HashTable {
00081   /** The array of pointers to the head of a singly linked list, whose nodes
00082       are HashTableEntry objects */
00083   HashTableEntry** buckets;
00084 
00085   /** The hash function pointer */
00086   HashFunction hash;
00087 
00088   /** The number of buckets in the hash table */
00089   unsigned int num_buckets;
00090 };
00091 
00092 /**
00093  * This structure represents a hash table entry.
00094  * Use "HashTableEntry" instead when you are creating a new variable. [See top comments]
00095  */
00096 struct _HashTableEntry {
00097   /** The key for the hash table entry */
00098   unsigned int key;
00099 
00100   /** The value associated with this hash table entry */
00101   void* value;
00102 
00103   /**
00104   * A pointer pointing to the next hash table entry
00105   * NULL means there is no next entry (i.e. this is the tail)
00106   */
00107   HashTableEntry* next;
00108 };
00109 
00110 
00111 /****************************************************************************
00112 * Private Functions
00113 *
00114 * These functions are not available outside of this file, since they are not
00115 * declared in hash_table.h.
00116 ***************************************************************************/
00117 /**
00118 * createHashTableEntry
00119 *
00120 * Helper function that creates a hash table entry by allocating memory for it on
00121 * the heap. It initializes the entry with key and value, initialize pointer to
00122 * the next entry as NULL, and return the pointer to this hash table entry.
00123 *
00124 * @param key The key corresponds to the hash table entry
00125 * @param value The value stored in the hash table entry
00126 * @return The pointer to the hash table entry
00127 */
00128 static HashTableEntry* createHashTableEntry(unsigned int key, void* value) {
00129     /** Create a pointer pointing to an empty hash table entry **/
00130     HashTableEntry* HTEPointer = (HashTableEntry*)malloc(sizeof(HashTableEntry));
00131     if(HTEPointer) { // if the pointer is not null -> malloc successfully
00132         HTEPointer->key = key; // assign the key 
00133         HTEPointer->value = value;// assign the value
00134         HTEPointer->next = NULL; // set the next pointer pointing to null
00135         return HTEPointer; // return the pointer to the hash table entry
00136     } else { // this pointer is null -> malloc fail
00137         fprintf(stderr, "Can not allocate space for more Hash Table Entry... Try freeing some stuff!\n");
00138         return NULL;
00139     }
00140 }
00141 
00142 /**
00143 * findItem
00144 *
00145 * Helper function that checks whether there exists the hash table entry that
00146 * contains a specific key.
00147 *
00148 * @param hashTable The pointer to the hash table.
00149 * @param key The key corresponds to the hash table entry
00150 * @return The pointer to the hash table entry, or NULL if key does not exist
00151 */
00152 static HashTableEntry* findItem(HashTable* hashTable, unsigned int key) {
00153     if(hashTable) { // check if hashTable is pointing to null or not
00154         /** get the index in buckets from the key **/
00155         unsigned int index = hashTable->hash(key);
00156         /** create a pointer pointing to the first Hash table entry in the right bucket **/
00157         HashTableEntry* HTE = hashTable->buckets[index];
00158         if(HTE) { // if the pointer is not null
00159             while(HTE) { // loop until HTE becomes null
00160                 /** if the key in the hash table entry matches the given key **/
00161                 if(HTE->key == key) {
00162                     return HTE; // return the pointer to the right entry
00163                 }
00164                 HTE = HTE->next; // if not found, the pointer point to the next entry
00165             }
00166         } else { // the pointer is null, return null
00167             return NULL;
00168         }
00169         return NULL; // if after the search and still haven't found a match, return null
00170     } else { // hash table pointing to null, so return null
00171         return NULL;
00172     }
00173 }
00174 
00175 /****************************************************************************
00176 * Public Interface Functions
00177 *
00178 * These functions implement the public interface as specified in the header
00179 * file, and make use of the private functions and hidden definitions in the
00180 * above sections.
00181 ****************************************************************************/
00182 // The createHashTable is provided for you as a starting point.
00183 HashTable* createHashTable(HashFunction hashFunction, unsigned int numBuckets) {
00184   // The hash table has to contain at least one bucket. Exit gracefully if
00185   // this condition is not met.
00186   if (numBuckets==0) {
00187     printf("Hash table has to contain at least 1 bucket...\n");
00188     exit(1);
00189   }
00190 
00191   // Allocate memory for the new HashTable struct on heap.
00192   HashTable* newTable = (HashTable*)malloc(sizeof(HashTable));
00193 
00194   // Initialize the components of the new HashTable struct.
00195   newTable->hash = hashFunction;
00196   newTable->num_buckets = numBuckets;
00197   newTable->buckets = (HashTableEntry**)malloc(numBuckets*sizeof(HashTableEntry*));
00198 
00199   // As the new buckets contain indeterminant values, init each bucket as NULL.
00200   unsigned int i;
00201   for (i=0; i<numBuckets; ++i) {
00202     newTable->buckets[i] = NULL;
00203   }
00204 
00205   // Return the new HashTable struct.
00206   return newTable;
00207 }
00208 
00209 HashTableEntry* destroyHashTableEntry(HashTableEntry* hashTableEntry); // helper function
00210 void destroyHashTable(HashTable* hashTable){
00211     if (hashTable) { // if the pointer is not null, destroy it
00212         if (hashTable->buckets) { // if the pointer to the buckets is not null, destroy
00213             /** for loop to go through every bucket **/
00214             for (int i = 0; i < hashTable->num_buckets; i++) {
00215                 /** create a pointer pointing to the first HTE of the bucket **/
00216                 HashTableEntry* HTE = hashTable->buckets[i];
00217                 while(HTE){ // loop to destroy until the pointer point to null
00218                     // destroy the entry and return the next pointer to nextHTE
00219                     free(HTE->value);
00220                     HashTableEntry* nextEntry = destroyHashTableEntry(HTE);
00221                     HTE = nextEntry;
00222                 }
00223             } // done freeing all the buckets
00224             free(hashTable->buckets); // free the array of pointer to the buckets
00225         }
00226         free(hashTable); // finally free the hash table
00227     } // else there is nothing to be done
00228 }
00229 
00230 void* insertItem(HashTable* hashTable, unsigned int key, void* value) {
00231     if(!hashTable) { // if hashTable point to null, return null
00232         return NULL;
00233     }   
00234     /** get the index in the buckets from the given key **/
00235     unsigned int index = hashTable->hash(key);
00236     /** find the entry that has the same key with the function findKey **/
00237     HashTableEntry* findResult = findItem(hashTable, key);
00238     if(!findResult) { //if findResult is null -> no entry with the key
00239         if(!hashTable->buckets[index]) { // if the bucket is empty
00240             /**insert it directly in the first position in the bucket **/
00241             HashTableEntry* result = createHashTableEntry(key, value);
00242             hashTable->buckets[index] = result;
00243             return NULL;
00244         } // else we insert it at the end
00245         /** HTE point to the first entry in the bucket **/
00246         HashTableEntry* HTE = hashTable->buckets[index];
00247         while(HTE) { // loop until HTE point to null or until return
00248             if(!HTE->next) { // if the next pointer point to null, insert the entry
00249                 HTE->next = createHashTableEntry(key, value);
00250                 return NULL;
00251             }
00252             // HTE points to the next entry
00253             HTE = HTE->next;
00254         }// if we haven't return after this loop, return null
00255         return NULL;
00256     } // else find result is legit, we just change the value
00257     void* result = findResult->value; // store the old value
00258     findResult->value = value; // update the value in the entry
00259     return result;
00260 }
00261 
00262 void* getItem(HashTable* hashTable, unsigned int key) {
00263     if(!hashTable) { // if hashTable point to null, return null
00264         return NULL;
00265     }
00266     /** item point to the entry with the given key **/
00267     HashTableEntry* item = findItem(hashTable, key);
00268     if(item) { // if item is not pointing to null
00269         return item->value; // return that entry's value
00270     } else { // else the item is pointing to null, return null
00271         return NULL; 
00272     }
00273 }
00274 
00275 void* removeItem(HashTable* hashTable, unsigned int key) {
00276     if(!hashTable) { // if hashTable point to null, return null
00277         return NULL;
00278     }
00279     /** removeHTE points to the entry to be removed **/
00280     HashTableEntry* removeHTE = findItem(hashTable, key);
00281     if(!removeHTE) { // if removeHTE points to null, return null
00282         return NULL;
00283     }
00284     /** get the index in buckets from the given key **/
00285     unsigned int index = hashTable->hash(key);
00286     /** HTE points to the first entry in the bucket **/
00287     HashTableEntry* HTE = hashTable->buckets[index];
00288     if(HTE == removeHTE) { // if the entry to be removed in also the first entry
00289         void* result = removeHTE->value; // store the old value into result
00290         /** free the entry and store the pointer to next(which is null) into the bucket **/
00291         hashTable->buckets[index] = destroyHashTableEntry(removeHTE);
00292         return result; // return the old value
00293     } // else we have to look for the entry with the right key
00294     while(HTE) { // loop until HTE points to null
00295         /** if the next pointer of HTE point to the entry to be removed **/
00296         if(HTE->next == removeHTE) {
00297             void* result = removeHTE->value; // store the old value into result
00298             /** free the entry and store the next pointer to the next value of the deleted entry **/
00299             removeHTE = destroyHashTableEntry(removeHTE);
00300             return result;
00301         }
00302         HTE = HTE->next; // HTE point to the next entry
00303     }// if after the while loop we haven't return, return null
00304     return NULL;
00305 }
00306 
00307 void deleteItem(HashTable* hashTable, unsigned int key) {
00308     free(removeItem(hashTable, key));//free the value returned after remove the item
00309 }
00310 
00311 /**
00312  * destroyHashTableEntry
00313  *
00314  * Destroy the hash table entry being passed in. Freeing key, value and next
00315  * Return the next value(HashTableEntry *)
00316  */
00317 HashTableEntry* destroyHashTableEntry(HashTableEntry* hashTableEntry) {
00318     HashTableEntry* result = hashTableEntry->next;
00319     //free(hashTableEntry->value);
00320     free(hashTableEntry);
00321     return result;
00322 }