Diff: hash_table.cpp

Revision:

7:1912b4a2e4fe

Parent:

3:9dde875cd65c

Child:

8:2e18a96e0c77

--- a/hash_table.cpp	Tue Nov 24 11:10:42 2020 +0000
+++ b/hash_table.cpp	Tue Nov 24 11:21:33 2020 +0000
@@ -1,33 +1,30 @@
-//=================================================================
 // 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: Kate Blake
- Date: 11/2/2020
-
+ Student Name:
+ Date:
+ 
 =======================
 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
@@ -36,23 +33,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
 *
@@ -62,8 +59,8 @@
 * correctness, but it is better than nothing!
 ***************************************************************************/
 #include "hash_table.h"
-
-
+ 
+ 
 /****************************************************************************
 * Include other private dependencies
 *
@@ -72,8 +69,8 @@
 ***************************************************************************/
 #include <stdlib.h>   // For malloc and free
 #include <stdio.h>    // For printf
-
-
+ 
+ 
 /****************************************************************************
 * Hidden Definitions
 *
@@ -89,14 +86,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]
@@ -104,18 +101,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
 *
@@ -134,20 +131,9 @@
 * @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
 *
@@ -159,28 +145,9 @@
 * @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
 *
@@ -196,259 +163,40 @@
     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 contain indeterminant values, init each bucket as NULL.
+ 
+  // As the new buckets are empty, 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) {
-  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;
-      }
-    }
-  }
-}
+ 
+}
\ No newline at end of file