Diff: hash_table.cpp

Revision:

8:2e18a96e0c77

Parent:

7:1912b4a2e4fe

--- a/hash_table.cpp	Tue Nov 24 11:21:33 2020 +0000
+++ b/hash_table.cpp	Tue Nov 24 12:35:16 2020 +0000
@@ -1,30 +1,33 @@
+//=================================================================
 // Copyright 2020 Georgia Tech.  All rights reserved.
 // The materials provided by the instructor in this course are for
 // the use of the students currently enrolled in the course.
 // Copyrighted course materials may not be further disseminated.
 // This file must not be made publicly available anywhere.
+//=================================================================
+
 /*
- Student Name:
- Date:
- 
+ Student Name: Kate Blake
+ Date: 11/2/2020
+
 =======================
 ECE 2035 Project 2-1:
 =======================
 This file provides definition for the structs and functions declared in the
 header file. It also contains helper functions that are not accessible from
 outside of the file.
- 
+
 FOR FULL CREDIT, BE SURE TO TRY MULTIPLE TEST CASES and DOCUMENT YOUR CODE.
- 
+
 ===================================
 Naming conventions in this file:
 ===================================
 1. All struct names use camel case where the first letter is capitalized.
   e.g. "HashTable", or "HashTableEntry"
- 
+
 2. Variable names with a preceding underscore "_" will not be called directly.
   e.g. "_HashTable", "_HashTableEntry"
- 
+
   Recall that in C, we have to type "struct" together with the name of the struct
   in order to initialize a new variable. To avoid this, in hash_table.h
   we use typedef to provide new "nicknames" for "struct _HashTable" and
@@ -33,23 +36,23 @@
     - "HashTable myNewTable;"
      or
     - "HashTableEntry myNewHashTableEntry;"
- 
+
   The preceding underscore "_" simply provides a distinction between the names
   of the actual struct defition and the "nicknames" that we use to initialize
   new structs.
   [See Hidden Definitions section for more information.]
- 
+
 3. Functions, their local variables and arguments are named with camel case, where
   the first letter is lower-case.
   e.g. "createHashTable" is a function. One of its arguments is "numBuckets".
        It also has a local variable called "newTable".
- 
+
 4. The name of a struct member is divided by using underscores "_". This serves
   as a distinction between function local variables and struct members.
   e.g. "num_buckets" is a member of "HashTable".
- 
+
 */
- 
+
 /****************************************************************************
 * Include the Public Interface
 *
@@ -59,8 +62,8 @@
 * correctness, but it is better than nothing!
 ***************************************************************************/
 #include "hash_table.h"
- 
- 
+
+
 /****************************************************************************
 * Include other private dependencies
 *
@@ -69,8 +72,8 @@
 ***************************************************************************/
 #include <stdlib.h>   // For malloc and free
 #include <stdio.h>    // For printf
- 
- 
+
+
 /****************************************************************************
 * Hidden Definitions
 *
@@ -86,14 +89,14 @@
   /** The array of pointers to the head of a singly linked list, whose nodes
       are HashTableEntry objects */
   HashTableEntry** buckets;
- 
+
   /** The hash function pointer */
   HashFunction hash;
- 
+
   /** The number of buckets in the hash table */
   unsigned int num_buckets;
 };
- 
+
 /**
  * This structure represents a hash table entry.
  * Use "HashTableEntry" instead when you are creating a new variable. [See top comments]
@@ -101,18 +104,18 @@
 struct _HashTableEntry {
   /** The key for the hash table entry */
   unsigned int key;
- 
+
   /** The value associated with this hash table entry */
   void* value;
- 
+
   /**
   * A pointer pointing to the next hash table entry
   * NULL means there is no next entry (i.e. this is the tail)
   */
   HashTableEntry* next;
 };
- 
- 
+
+
 /****************************************************************************
 * Private Functions
 *
@@ -131,9 +134,20 @@
 * @return The pointer to the hash table entry
 */
 static HashTableEntry* createHashTableEntry(unsigned int key, void* value) {
- 
+    //allocate memory for new hash table entry
+    HashTableEntry* newHashTableEntry = (HashTableEntry*)malloc(sizeof(HashTableEntry));
+
+    //assign key var in struct to key parameter
+    newHashTableEntry->key = key;
+    //assign value var in struct to value parameter
+    newHashTableEntry->value = value;
+    //assign next var to default NULL
+    newHashTableEntry->next = NULL;
+
+    //return the new entry
+    return newHashTableEntry;
 }
- 
+
 /**
 * findItem
 *
@@ -145,9 +159,28 @@
 * @return The pointer to the hash table entry, or NULL if key does not exist
 */
 static HashTableEntry* findItem(HashTable* hashTable, unsigned int key) {
- 
+    //check to make sure recieved valid hashTable
+    if (hashTable != NULL) {
+      //bucketNum variable to track what array space it takes up
+      unsigned int bucketNum = hashTable->hash(key);
+      //make sure the bucket exists
+      if (hashTable->buckets[bucketNum] != NULL) {
+        //currentEntry for tracking nested entries
+        HashTableEntry* currentEntry = hashTable->buckets[bucketNum];
+        //while loop for nested search
+        while (currentEntry->key != key && currentEntry->next != NULL) {
+          currentEntry = currentEntry->next;
+        }
+        //did we find it?
+        if (currentEntry-> key == key) {
+          return currentEntry;
+        }
+      }
+    }
+    //otherwise return NULL
+  return NULL;
 }
- 
+
 /****************************************************************************
 * Public Interface Functions
 *
@@ -163,40 +196,259 @@
     printf("Hash table has to contain at least 1 bucket...\n");
     exit(1);
   }
- 
+
   // Allocate memory for the new HashTable struct on heap.
   HashTable* newTable = (HashTable*)malloc(sizeof(HashTable));
- 
+
   // Initialize the components of the new HashTable struct.
   newTable->hash = hashFunction;
   newTable->num_buckets = numBuckets;
   newTable->buckets = (HashTableEntry**)malloc(numBuckets*sizeof(HashTableEntry*));
- 
-  // As the new buckets are empty, init each bucket as NULL.
+
+  // As the new buckets contain indeterminant values, init each bucket as NULL.
   unsigned int i;
   for (i=0; i<numBuckets; ++i) {
     newTable->buckets[i] = NULL;
   }
- 
+
   // Return the new HashTable struct.
   return newTable;
 }
- 
+
 void destroyHashTable(HashTable* hashTable) {
- 
+  //make sure a hashtable exists to destroy
+    if (hashTable != NULL) {
+      unsigned int i;
+      //search the buckets for entries to free
+      for (i=0; i<hashTable->num_buckets; ++i) {
+        if (hashTable->buckets[i] != NULL) {
+          HashTableEntry* currentEntry = hashTable->buckets[i];
+          HashTableEntry* pastEntry;
+          //get the nested entries as well
+          while (currentEntry -> next != NULL) {
+              pastEntry = currentEntry;
+              currentEntry = currentEntry -> next;
+              if (pastEntry -> value != NULL) {
+                //freeee them
+                free(pastEntry->value);
+                pastEntry->value = NULL;
+              }
+              //free them all
+              if (pastEntry != NULL) {
+                free(pastEntry);
+                pastEntry = NULL;
+              }
+          }
+          if (currentEntry -> value != NULL) {
+            //make sure you catch all those bad boys
+                free(currentEntry->value);
+                currentEntry->value = NULL;
+              }
+            //this catches the one the while loop ignores
+          if (currentEntry != NULL) {
+            free(currentEntry);
+            currentEntry = NULL;
+          }
+        }
+      }
+     //see if theres anything in the buckets 
+      if (hashTable->buckets != NULL) {
+        //empty the buckets
+        free(hashTable->buckets);
+        hashTable->buckets = NULL;
+      }
+      //double check that hashtable just to be safe before freeing
+      if (hashTable != NULL) {
+        free(hashTable);
+        hashTable = NULL;
+      }
+    }
 }
- 
+
 void* insertItem(HashTable* hashTable, unsigned int key, void* value) {
+  //make sure a valid hashtable is provided
+    if (hashTable == NULL) {
+      return NULL;
+    }
+    //find what bucket this boys in
+    unsigned int bucketNum = hashTable->hash(key);
+    //create the entry for the boy
+    HashTableEntry* hashTableEntry = createHashTableEntry(key, value);
+    //checks if theres something already in the bucket
+    if (hashTable->buckets[bucketNum] != NULL) {
+      //are the keys the same?
+      if (hashTable->buckets[bucketNum]->key == key) {
+        //if so grab old value
+        void* oldval = hashTable->buckets[bucketNum]->value;
+        //free the old boy
+        if (hashTable->buckets[bucketNum] != NULL) {
+          free(hashTable->buckets[bucketNum]); 
+        }
+        //overwrite
+        hashTable->buckets[bucketNum] = hashTableEntry;
+        //return old value
+        return oldval;
+      } else {
+        //check for nested keys
+        HashTableEntry* currentEntry = hashTable->buckets[bucketNum];
+        HashTableEntry* pastEntry;
+        while(currentEntry->next !=NULL && currentEntry-> key != key){
+          //if there is another nested entry and the keys dont match keep cycling through the nested
+          pastEntry = currentEntry;
+          currentEntry = currentEntry->next;
+        }
+        //if the keys match take the old value replace it and return the old value
+        if (currentEntry-> key == key) {
+          void* oldval = currentEntry->value;
+          if (hashTable->buckets[bucketNum] != NULL) {
+            free(currentEntry);
+          }
+          //append to where old entry was
+        pastEntry->next = hashTableEntry;
+        return oldval;
+        } 
+        //otherwise append to end of nested chain
+        currentEntry->next = hashTableEntry;
+      }
+    } else {
+      //if the bucket is uninhabited the boy now lives there
+      hashTable->buckets[bucketNum] = hashTableEntry;
+    }
+    return NULL;
 }
- 
+
 void* getItem(HashTable* hashTable, unsigned int key) {
- 
+  //make sure a valid hashtable was provided
+    if (hashTable == NULL) {
+      return NULL;
+    }
+    //find which bucket it is
+    unsigned int bucketNum = hashTable -> hash(key);
+    //make sure bucket isnt empty
+    if (hashTable->buckets[bucketNum] == NULL) {
+      return NULL;
+    } else {
+      //otherwise find the entry
+      HashTableEntry* foundHashEntry = findItem(hashTable, key);
+      //make sure entry is valid
+      if (foundHashEntry != NULL) {
+        //return entry
+        return foundHashEntry->value;
+      }
+      return NULL;
+    }
 }
- 
+
 void* removeItem(HashTable* hashTable, unsigned int key) {
- 
+  //make sure valid hashtable is provided
+  if (hashTable == NULL) {
+      return NULL;
+    }
+  //initialize booleans to check for nesting conditions and bucket number
+  unsigned int isNested = 0;
+  unsigned int isntTail = 1;
+  unsigned int bucketNum = hashTable->hash(key);
+  //make sure bucket isnt empty
+  if (hashTable->buckets[bucketNum] != NULL) {
+    //define entries for nesting
+    HashTableEntry* currentEntry = hashTable->buckets[bucketNum];
+    HashTableEntry* pastEntry;
+    HashTableEntry* futureEntry;
+    //check for nesting and update variables as needed
+    while (currentEntry->next !=NULL && currentEntry->key !=key) {
+      pastEntry = currentEntry;
+      currentEntry = currentEntry->next;
+      isNested = 1;
+      if (currentEntry->next == NULL) {
+        isntTail = 0;
+      } else {
+        futureEntry = currentEntry -> next;
+      }
+    }
+    //make sure entry is valid
+    if (currentEntry != NULL){
+      //check for sandwiched entry to be removed
+      if (isNested == 1 && isntTail == 1) {
+        pastEntry->next = futureEntry;
+        //otherwise assume its the tail if its nested
+      } else if (isNested == 1) {
+        pastEntry->next = NULL;
+      } 
+      //assign removed entry to return
+      void* removedEntryVal = currentEntry->value;
+      //double check for valid entry
+      if (currentEntry != NULL) {
+        //check whether it is only thing in bucket
+        if (currentEntry->next !=NULL && isNested == 0) {
+          futureEntry = currentEntry->next;
+          hashTable->buckets[bucketNum] = futureEntry;
+        } else if (isntTail == 1 && isNested == 0) {
+          hashTable->buckets[bucketNum] = NULL;
+        }
+        //free removed entry
+        free(currentEntry);
+        currentEntry = NULL;
+      }
+      //return the entry
+    return removedEntryVal;
+    }
+  }
+  return NULL;
 }
- 
+
 void deleteItem(HashTable* hashTable, unsigned int key) {
- 
-}
\ No newline at end of file
+  if (hashTable == NULL) {
+    printf("Hash table doesn't exist.\n");
+    exit(1);
+  } 
+  //initialize booleans to check for nesting conditions and bucket number
+  unsigned int isNested = 0;
+  unsigned int isntTail = 1;
+  unsigned int bucketNum = hashTable->hash(key);
+  //make sure bucket isnt empty
+  if (hashTable->buckets[bucketNum] != NULL) {
+    //define entries for nesting
+    HashTableEntry* currentEntry = hashTable->buckets[bucketNum];
+    HashTableEntry* pastEntry;
+    HashTableEntry* futureEntry;
+    //check for nesting and update variables as needed
+    while (currentEntry->next !=NULL && currentEntry->key !=key) {
+      pastEntry = currentEntry;
+      currentEntry = currentEntry->next;
+      isNested = 1;
+      if (currentEntry->next == NULL) {
+        isntTail = 0;
+      } else {
+        futureEntry = currentEntry -> next;
+      }
+    }
+    //make sure entry is valid
+    if (currentEntry != NULL){
+      //check for sandwiched entry to be removed
+      if (isNested == 1 && isntTail == 1) {
+        pastEntry->next = futureEntry;
+        //otherwise assume its the tail if its nested
+      } else if (isNested == 1) {
+        pastEntry->next = NULL;
+      } 
+      //double check for valid entry
+      if (currentEntry != NULL) {
+        //check whether it is only thing in bucket
+        if (currentEntry->next !=NULL && isNested == 0) {
+          futureEntry = currentEntry->next;
+          hashTable->buckets[bucketNum] = futureEntry;
+        } else if (isntTail == 1 && isNested == 0) {
+          hashTable->buckets[bucketNum] = NULL;
+        }
+        if (currentEntry -> value != NULL) {
+            //free value
+                free(currentEntry->value);
+                currentEntry->value = NULL;
+              }
+        //free removed entry
+        free(currentEntry);
+        currentEntry = NULL;
+      }
+    }
+  }
+}