hash_table.cpp

00001 /*
00002  Student Name: Randall Kliman
00003  Date: 11/9/18
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   HashTableEntry* this_entry;   //create pointer to entry we will create
00130   this_entry = (HashTableEntry*)malloc(sizeof(HashTableEntry)); // Allocate our entry
00131   //if(!this_entry) return this_entry;      //if this entry is null, return null
00132   this_entry->key = key;
00133   this_entry->value = value;      //Initialize entry fields
00134   this_entry->next = NULL;
00135   return this_entry;      //Return pointer to entry
00136 }
00137 
00138 /**
00139 * findItem
00140 *
00141 * Helper function that checks whether there exists the hash table entry that
00142 * contains a specific key.
00143 *
00144 * @param hashTable The pointer to the hash table.
00145 * @param key The key corresponds to the hash table entry
00146 * @return The pointer to the hash table entry, or NULL if key does not exist
00147 */
00148 static HashTableEntry* findItem(HashTable* hashTable, unsigned int key) {
00149   unsigned int bucket = (hashTable->hash)(key); //Find which bucket our entry is in
00150 
00151   HashTableEntry * this_entry = hashTable->buckets[bucket]; //gets head
00152   while (this_entry) {    //Iterates through the list to find the entry
00153     if(this_entry->key == key) return this_entry; //If this is what we are looking for
00154     this_entry = this_entry->next; //Iterate
00155   }
00156   return this_entry; //This should return NULL, since this_entry->next will be NULL if it cannot find the appropriate key
00157 }
00158 
00159 /****************************************************************************
00160 * Public Interface Functions
00161 *
00162 * These functions implement the public interface as specified in the header
00163 * file, and make use of the private functions and hidden definitions in the
00164 * above sections.
00165 ****************************************************************************/
00166 // The createHashTable is provided for you as a starting point.
00167 HashTable* createHashTable(HashFunction hashFunction, unsigned int numBuckets) {
00168   // The hash table has to contain at least one bucket. Exit gracefully if
00169   // this condition is not met.
00170   if (numBuckets==0) {
00171     printf("Hash table has to contain at least 1 bucket...\n");
00172     exit(1);
00173   }
00174 
00175   // Allocate memory for the new HashTable struct on heap.
00176   HashTable* newTable = (HashTable*)malloc(sizeof(HashTable));
00177 
00178   // Initialize the components of the new HashTable struct.
00179   newTable->hash = hashFunction;
00180   newTable->num_buckets = numBuckets;
00181   newTable->buckets = (HashTableEntry**)malloc(numBuckets*sizeof(HashTableEntry*));
00182 
00183   // As the new buckets contain indeterminant values, init each bucket as NULL.
00184   unsigned int i;
00185   for (i=0; i<numBuckets; ++i) {
00186     newTable->buckets[i] = NULL;
00187   }
00188 
00189   // Return the new HashTable struct.
00190   return newTable;
00191 }
00192 
00193 /*
00194 * destroyHashTable
00195 *
00196 * This function systematically frees all data allocated within the hash table
00197 *
00198 *@param hashTable The hash table that will be destroyed
00199 */
00200 void destroyHashTable(HashTable* hashTable) {
00201   //Iterates through buckets
00202   for(int i = 0; i < hashTable->num_buckets;i++){
00203     //Iterates through the linked list of a bucket and systematically frees each entry
00204     while(hashTable->buckets[i]){
00205       deleteItem(hashTable,hashTable->buckets[i]->key);
00206     }
00207   }
00208   free(hashTable->buckets); //free the bucket array;
00209   free(hashTable);    //free the hashTable "object"
00210 }
00211 
00212 /*
00213 * insertItem
00214 *
00215 * This function inserts an item into our hash table based on the hash of our key.
00216 * If it an entry already exists for the key, then we replace the current value of the
00217 * target entry with a new value and return a pointer to the old value. If an entry
00218 * does not already exist, create it at the front of a list and return a pointer
00219 * to the value we inserted.
00220 *
00221 *@param hashTable The hash table to look in
00222 *@param key The key of the entry we want to remove
00223 *@return a pointer to either the value we insert, or the value we are replacing
00224 */
00225 void* insertItem(HashTable* hashTable, unsigned int key, void* value) {
00226   int bucket = (hashTable->hash)(key); //Find which bucket our entry is in
00227   HashTableEntry* this_entry;
00228 
00229   //Overwrite Case: replace item value, return old value
00230   this_entry = findItem(hashTable,key);
00231   if(this_entry){
00232     void* itemval;
00233     itemval = this_entry->value;
00234     this_entry->value = value;
00235     return itemval;
00236   }
00237   //If nothing exists in our bucket, create a first entry
00238   HashTableEntry* he = createHashTableEntry(key,value);
00239   //otherwise, create an entry at the beginning of the bucket list
00240   if(!he){return NULL;}
00241   he->next = hashTable->buckets[bucket];
00242   hashTable->buckets[bucket] = he;
00243   return NULL;
00244 }
00245 
00246 /*
00247 * getItem
00248 *
00249 * This function finds data within a hash table
00250 *
00251 *@param hashTable The hash table to look in
00252 *@param key The key of the entry we are looking for
00253 *@return NULL if we don't find it, a pointer to the value if we do
00254 */
00255 void* getItem(HashTable* hashTable, unsigned int key) {
00256   HashTableEntry * hp = findItem(hashTable,key); //finds the item we are looking for
00257   if(!hp) return NULL; //if we look for the item and don't find it, return null
00258   return hp->value;   //otherwise, return the value of the entry we are looking for
00259 }
00260 
00261 /*
00262 * removeItem
00263 *
00264 * This function deletes entries within a hash table, but preserves the value of the deleted entry
00265 *
00266 *@param hashTable The hash table to look in
00267 *@param key The key of the entry we want to remove
00268 *@return NULL if we don't find it, a pointer to the value if we do
00269 */
00270 void* removeItem(HashTable* hashTable, unsigned int key) {
00271   unsigned int bucket = hashTable->hash(key); //Find which bucket our entry is in
00272 
00273   HashTableEntry* this_entry= hashTable->buckets[bucket];
00274   HashTableEntry* tmp;
00275 
00276   //If this entry doesn't exist, return NULL
00277   if(!this_entry) return NULL;
00278 
00279   //If this entry is the first entry, return value of entry
00280   //and make the head point to the next entry
00281   if(this_entry->key == key){
00282     void* val = this_entry->value;  //store current entry value
00283     hashTable->buckets[bucket] = this_entry->next; //head points to next entry in list
00284     free(this_entry); //deallocate entry
00285     return val; //return current value
00286   }
00287 
00288   //Destroys entries in the middle of lists by iterating through the list starting
00289   //at the head and only stopping when it sees that the next-next value is what we are looking for.
00290   //Then it deletes the entry from the list and stitches up the pointers pointing to and from the
00291   //entry we just deleted. This function will preserve and return the value of the destroyed entry, however
00292   while(this_entry->next){
00293     if(this_entry->next->key == key){
00294       tmp = this_entry->next;//temp value to store our target
00295       void* val = this_entry->next->value; //preserves target's value
00296       this_entry->next = this_entry->next->next;  //stitches up pointers
00297       free(tmp); //destroy temp/target entry
00298       return val; //if not what we were looking for, continue iterating through our list
00299     }
00300     this_entry = this_entry->next;
00301   }
00302   return NULL;
00303 }
00304 
00305 /*
00306 * deleteItem
00307 *
00308 * This function deletes entries within a hash table
00309 *
00310 *@param hashTable The hash table to look in
00311 *@param key The key of the entry we want to remove
00312 */
00313 void deleteItem(HashTable* hashTable, unsigned int key) {
00314   unsigned int bucket = hashTable->hash(key); //Find which bucket our entry is in
00315 
00316   HashTableEntry* this_entry= hashTable->buckets[bucket];
00317   HashTableEntry* tmp;
00318 
00319   //If this entry doesn't exist, return NULL
00320   if(!this_entry) return;
00321 
00322   //If this entry is the first entry, return value of entry
00323   //and make the head point to the next entry
00324   if(this_entry->key == key){
00325     hashTable->buckets[bucket] = this_entry->next; //head points to next entry in list
00326     free(this_entry->value);    //free the value of the entry
00327     free(this_entry);           //free the entry itself
00328     return;
00329   }
00330 
00331   //Destroys entries in the middle of lists by iterating through the list starting
00332   //at the head and only stopping when it sees that the next-next value is what we are looking for.
00333   //Then it deletes the entry from the list and stitches up the pointers pointing to and from the
00334   //entry we just deleted.
00335   while(this_entry->next){
00336     if(this_entry->next->key == key){
00337       tmp = this_entry->next;  //temp value to store our target
00338       free(this_entry->next->value);  //destroy the value of the taget entry
00339       this_entry->next = this_entry->next->next;  //stitches up pointers
00340       free(tmp);      //destroy temp/target entry
00341       return;
00342     }
00343     this_entry = this_entry->next; //if not what we were looking for, continue iterating through our list
00344   }
00345   return;
00346 }