hash_table.cpp

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