hash_table.cpp

00001 /*
00002  Student Name: Tiffany Montgomery
00003  Date:
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* entryptr = (HashTableEntry*)malloc(sizeof(HashTableEntry)); //allocate memory for the hash table entry
00130     if (entryptr == NULL) return NULL; //if malloc fails return NULL pointer
00131     
00132     //initialize hash table entry values
00133     entryptr->key = key;
00134     entryptr->value = value;
00135     entryptr ->next = NULL;
00136     return entryptr; //return a pointer to the entry
00137 }
00138 
00139 /**
00140 * findItem
00141 *
00142 * Helper function that checks whether there exists the hash table entry that
00143 * contains a specific key.
00144 *
00145 * @param hashTable The pointer to the hash table.
00146 * @param key The key corresponds to the hash table entry
00147 * @return The pointer to the hash table entry, or NULL if key does not exist
00148 */
00149 static HashTableEntry* findItem(HashTable* hashTable, unsigned int key) {
00150     unsigned int ind = hashTable->hash(key); //get the bucket index
00151     HashTableEntry* entryptr = hashTable->buckets[ind]; //get a pointer to the head of the bucket the item is in
00152     
00153     while(entryptr){ //while entryptr is not NULL
00154         if (entryptr-> key == key){
00155             return entryptr;
00156         }
00157         entryptr = entryptr -> next;
00158     }
00159     return NULL; //return null pointer if the entry does not exist
00160 }
00161 
00162 /****************************************************************************
00163 * Public Interface Functions
00164 *
00165 * These functions implement the public interface as specified in the header
00166 * file, and make use of the private functions and hidden definitions in the
00167 * above sections.
00168 ****************************************************************************/
00169 // The createHashTable is provided for you as a starting point.
00170 HashTable* createHashTable(HashFunction hashFunction, unsigned int numBuckets) {
00171   // The hash table has to contain at least one bucket. Exit gracefully if
00172   // this condition is not met.
00173   if (numBuckets==0) {
00174     printf("Hash table has to contain at least 1 bucket...\n");
00175     exit(1);
00176   }
00177 
00178   // Allocate memory for the new HashTable struct on heap.
00179   HashTable* newTable = (HashTable*)malloc(sizeof(HashTable));
00180 
00181   // Initialize the components of the new HashTable struct.
00182   newTable->hash = hashFunction;
00183   newTable->num_buckets = numBuckets;
00184   newTable->buckets = (HashTableEntry**)malloc(numBuckets*sizeof(HashTableEntry*));
00185 
00186   // As the new buckets are empty, init each bucket as NULL.
00187   unsigned int i;
00188   for (i=0; i<numBuckets; ++i) {
00189     newTable->buckets[i] = NULL;
00190   }
00191 
00192   // Return the new HashTable struct.
00193   return newTable;
00194 }
00195 
00196 void destroyHashTable(HashTable* hashTable) {
00197     
00198     //check to see if the hash table has been created
00199     if (hashTable != NULL){
00200         
00201         //iterate through each bucket and destroy each element
00202         for (int i = 0; i < hashTable -> num_buckets; i++){
00203             HashTableEntry* entryptr;
00204             while(hashTable -> buckets[i]){ //while there is at least one element in the list
00205                 entryptr = hashTable -> buckets[i];
00206                 hashTable -> buckets[i] = entryptr ->next; //increment the head pointer
00207                 if(entryptr ->value) free(entryptr ->value); //free the value
00208                 if (entryptr) free(entryptr); //free the hashtable entry
00209             }
00210         }
00211         free(hashTable -> buckets); //free pointer to bucket array
00212         free(hashTable); //free hash table struct
00213     }
00214 }
00215 
00216 void* insertItem(HashTable* hashTable, unsigned int key, void* value) {
00217     HashTableEntry* entryptr;
00218     if ((entryptr = findItem(hashTable, key))){ //if the key is in the hash table
00219         void* temp = entryptr -> value;
00220         entryptr -> value = value;
00221         return temp;
00222     }
00223     
00224     //create entry if key is not in hash table
00225     entryptr = createHashTableEntry(key, value);
00226     if(entryptr == NULL) return NULL;
00227     int ind = hashTable -> hash(key);
00228     
00229     //insert entry at the head of the linked list
00230     entryptr -> next = hashTable -> buckets[ind];
00231     hashTable -> buckets[ind] = entryptr;
00232     return NULL;
00233 
00234 }
00235 
00236 void* getItem(HashTable* hashTable, unsigned int key) {
00237     HashTableEntry* entryptr;
00238     entryptr = findItem(hashTable, key);
00239     if(entryptr == NULL) return NULL;
00240     if (entryptr -> value) return entryptr -> value;  //return value at key if key is present in the table
00241     return NULL;
00242 }
00243 
00244 void* removeItem(HashTable* hashTable, unsigned int key) {
00245     unsigned int ind = hashTable -> hash(key);
00246     HashTableEntry* entryptr = hashTable -> buckets[ind];
00247     if(entryptr == NULL) return NULL; //check if list is empty
00248     
00249     //if the item to be removed is at the end of the list
00250     if(entryptr -> key == key){ //find the key
00251         hashTable -> buckets[ind] = entryptr -> next; //increment the head pointer
00252         void* val = entryptr ->value; //store value
00253         free(entryptr);
00254         return val;
00255     }
00256     
00257     //if item to be removed is in the middle of the list or at the end of the list
00258     while(entryptr->next){
00259         if(entryptr->next->key == key){ //check to see if the next entry matches the key
00260             HashTableEntry* temp = entryptr ->next;
00261             entryptr -> next = entryptr ->next->next; //increment entryptr
00262             void* val = temp -> value;
00263             free(temp);
00264             return val;
00265         }
00266         entryptr = entryptr ->next;
00267     }
00268     return NULL;
00269 
00270 }
00271 
00272 void deleteItem(HashTable* hashTable, unsigned int key) {
00273     unsigned int ind = hashTable -> hash(key);
00274     HashTableEntry* entryptr = hashTable -> buckets[ind];
00275     
00276     //if first item matches the key
00277     if(entryptr && entryptr -> key == key){
00278         hashTable -> buckets[ind] = entryptr -> next;
00279         if(entryptr -> value) free(entryptr ->value); //if the entry still contains a value
00280         free(entryptr);
00281     }
00282     
00283     //if key is in the middle of or at the end of the list
00284     while(entryptr && entryptr->next){
00285         if(entryptr->next->key == key){
00286             HashTableEntry* temp = entryptr ->next; 
00287             entryptr -> next = entryptr ->next->next; //increment entryptr
00288             if(entryptr -> value) free(temp -> value); //if the entry still contains a value
00289             free(temp);
00290         }
00291         entryptr = entryptr ->next;
00292     }
00293 
00294 }