hash_table.cpp

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