hash_table.cpp

00001 /****************************************************************************
00002 * Include the Public Interface
00003 *
00004 * By including the public interface at the top of the file, the compiler can
00005 * enforce that the function declarations in the the header are not in
00006 * conflict with the definitions in the file. This is not a guarantee of
00007 * correctness, but it is better than nothing!
00008 ***************************************************************************/
00009 #include "hash_table.h"
00010 
00011 
00012 /****************************************************************************
00013 * Include other private dependencies
00014 *
00015 * These other modules are used in the implementation of the hash table module,
00016 * but are not required by users of the hash table.
00017 ***************************************************************************/
00018 #include <stdlib.h>   // For malloc and free
00019 #include <stdio.h>    // For printf
00020 
00021 
00022 /****************************************************************************
00023 * Hidden Definitions
00024 *
00025 * These definitions are not available outside of this file. However, because
00026 * the are forward declared in hash_table.h, the type names are
00027 * available everywhere and user code can hold pointers to these structs.
00028 ***************************************************************************/
00029 /**
00030  * This structure represents an a hash table.
00031  */
00032 struct _HashTable {
00033   /** The array of pointers to the head of a singly linked list, whose nodes
00034       are HashTableEntry objects */
00035   HashTableEntry** buckets;
00036 
00037   /** The hash function pointer */
00038   HashFunction hash;
00039 
00040   /** The number of buckets in the hash table */
00041   unsigned int num_buckets;
00042 };
00043 
00044 /**
00045  * This structure represents a hash table entry.
00046  */
00047 struct _HashTableEntry {
00048   /** The key for the hash table entry */
00049   unsigned int key;
00050 
00051   /** The value associated with this hash table entry */
00052   void* value;
00053 
00054   /**
00055   * A pointer pointing to the next hash table entry
00056   * NULL means there is no next entry (i.e. this is the tail)
00057   */
00058   HashTableEntry* next;
00059 };
00060 
00061 
00062 /****************************************************************************
00063 * Private Functions
00064 *
00065 * These functions are not available outside of this file, since they are not
00066 * declared in hash_table.h.
00067 ***************************************************************************/
00068 /**
00069 * createHashTableEntry
00070 *
00071 * Helper function that creates a hash table entry by allocating memory for it on
00072 * the heap. It initializes the entry with key and value, initialize pointer to
00073 * the next entry as NULL, and return the pointer to this hash table entry.
00074 *
00075 * @param key The key corresponds to the hash table entry
00076 * @param value The value stored in the hash table entry
00077 * @return The pointer to the hash table entry
00078 */
00079 static HashTableEntry* createHashTableEntry(unsigned int key, void* value) {
00080   // Create an initialize a new hash table entry.
00081   HashTableEntry* newEntry = (HashTableEntry*)malloc(sizeof(HashTableEntry));
00082   newEntry->key = key;
00083   newEntry->value = value;
00084   newEntry->next = NULL;
00085 
00086   return newEntry;
00087 }
00088 
00089 /**
00090 * findItem
00091 *
00092 * Helper function that checks whether there exists the hash table entry that
00093 * contains a specific key.
00094 *
00095 * @param myHashTable The pointer to the hash table.
00096 * @param key The key corresponds to the hash table entry
00097 * @return The pointer to the hash table entry, or NULL if key does not exist
00098 */
00099 static HashTableEntry* findItem(HashTable* myHashTable, unsigned int key) {
00100   unsigned int bucketNum = myHashTable->hash(key);  // Get the bucket number.
00101   HashTableEntry* temp = myHashTable->buckets[bucketNum]; // Get the head entry.
00102 
00103   if (temp == NULL) return NULL;  // If there's nothing in the bucket, return NULL.
00104 
00105   while (temp!=NULL) {
00106     if (temp->key==key) return temp; // Return the hash table entry if the key is found.
00107     temp = temp->next;  // Otherwise, move to next node.
00108   }
00109 
00110   return NULL;  // Return NULL if key is not present.
00111 }
00112 
00113 /****************************************************************************
00114 * Public Interface Functions
00115 *
00116 * These functions implement the public interface as specified in the header
00117 * file, and make use of the private functions and hidden definitions in the
00118 * above sections.
00119 ****************************************************************************/
00120 HashTable* createHashTable(HashFunction myHashFunc, unsigned int numBuckets) {
00121   // The hash table has to contain at least one bucket. Exit gracefully if
00122   // this condition is not met.
00123   if (numBuckets==0) {
00124     printf("Hash table has to contain at least 1 bucket...\n");
00125     exit(1);
00126   }
00127 
00128   // Allocate memory for the new HashTable struct on heap.
00129   HashTable* newTable = (HashTable*)malloc(sizeof(HashTable));
00130 
00131   // Initialize the components of the new HashTable struct.
00132   newTable->hash = myHashFunc;
00133   newTable->num_buckets = numBuckets;
00134   newTable->buckets = (HashTableEntry**)malloc(numBuckets*sizeof(HashTableEntry*));
00135 
00136   // As the new buckets contain indeterminant values, init each bucket as NULL.
00137   unsigned int i;
00138   for (i=0; i<numBuckets; ++i) {
00139     newTable->buckets[i] = NULL;
00140   }
00141 
00142   // Return the newly created hash table.
00143   return newTable;
00144 }
00145 
00146 void destroyHashTable(HashTable* myHashTable) {
00147   unsigned int i;
00148   HashTableEntry* temp;
00149   HashTableEntry* next;
00150 
00151   // Loop through each bucket of the hash table to remove all items.
00152   for (i=0; i<myHashTable->num_buckets; ++i) {
00153      temp = myHashTable->buckets[i];  // set temp to be the first entry of the ith bucket
00154 
00155     // delete all entries
00156     while (temp != NULL) {
00157       next = temp->next;
00158       free(temp->value);
00159       free(temp);
00160       temp = next;
00161     }
00162   }
00163 
00164   // free buckets
00165   free(myHashTable->buckets);
00166 
00167   // free hash table
00168   free(myHashTable);
00169 }
00170 
00171 void* insertItem(HashTable* myHashTable, unsigned int key, void* value) {
00172   // First, we want to check if the key is present in the hash table.
00173   HashTableEntry* temp = findItem(myHashTable, key);
00174 
00175   if (temp) {
00176     // The key is present in the hash table.
00177     void* oldValue = temp->value;
00178     temp->value = value;
00179     return oldValue;
00180   } else {
00181     // The key is not present in the hash table.
00182     temp = createHashTableEntry(key, value);
00183     temp->next = myHashTable->buckets[myHashTable->hash(key)];
00184     myHashTable->buckets[myHashTable->hash(key)] = temp;
00185     return NULL;  // Return NULL as nothing is overwritten.
00186   }
00187 }
00188 
00189 void* getItem(HashTable* myHashTable, unsigned int key) {
00190   // First, we want to check if the key is present in the hash table.
00191   HashTableEntry* temp = findItem(myHashTable, key);
00192 
00193   if (temp) // if the key exists
00194     return temp->value;
00195   else  // return NULL if the key does not exist
00196     return NULL;
00197 }
00198 
00199 void* removeItem(HashTable* myHashTable, unsigned int key) {
00200   // Reference: https://www.geeksforgeeks.org/linked-list-set-3-deleting-node/
00201   unsigned int bucketNum = myHashTable->hash(key);  // get the bucket number
00202   HashTableEntry* temp = myHashTable->buckets[bucketNum]; // get the head entry
00203   HashTableEntry* prev;
00204 
00205   // If head holds the key
00206   if (temp != NULL && temp->key == key) {
00207     myHashTable->buckets[bucketNum] = temp->next;  // Change head
00208     void* oldValue = temp->value; // hold the old value
00209     free(temp);
00210     return oldValue;
00211   }
00212 
00213   // Search for the key to be removed
00214   while (temp != NULL && temp->key != key) {
00215     prev = temp;
00216     temp = temp->next;
00217   }
00218 
00219   // If the key is not present in the list
00220   if (temp == NULL) return NULL;
00221 
00222   // Unlink the node from list
00223   prev->next = temp->next;
00224   void* oldValue = temp->value; // hold the old value
00225   free(temp);
00226 
00227   return oldValue;
00228 }
00229 
00230 void deleteItem(HashTable* myHashTable, unsigned int key) {
00231   // remove the entry and free the returned data
00232   free(removeItem(myHashTable, key));
00233 }