Diff: hash_table.cpp

Revision:

2:7ae1e676b120

Parent:

0:35660d7952f7

--- a/hash_table.cpp	Wed Apr 04 21:11:07 2018 +0000
+++ b/hash_table.cpp	Thu Apr 11 21:09:06 2019 +0000
@@ -1,6 +1,7 @@
 /*
- Student Name:
- Date:
+ Student Name: Jaden Truxal
+ Date: 3.23.19
+ valgrind --leak-check=full ./ht_tests
 
 =======================
 ECE 2035 Project 2-1:
@@ -127,6 +128,16 @@
 */
 static HashTableEntry* createHashTableEntry(unsigned int key, void* value) {
 
+//makes a new hashtable entry with a certain key, value and sets the next value to NULL
+  HashTableEntry* htEntry = (HashTableEntry*)malloc(sizeof(HashTableEntry));
+  if (!htEntry)
+    return NULL;
+  htEntry->key = key;
+  htEntry->value = value;
+  htEntry->next = NULL;
+
+  return htEntry;
+
 }
 
 /**
@@ -140,7 +151,16 @@
 * @return The pointer to the hash table entry, or NULL if key does not exist
 */
 static HashTableEntry* findItem(HashTable* hashTable, unsigned int key) {
-
+  //finds an item in the hashtable using the key provided, if the item isn't in the hashtable, 
+  int index = hashTable->hash(key);
+  HashTableEntry* htEntry = hashTable->buckets[index]; 
+  while(htEntry != NULL){
+    if(htEntry->key == key){
+      return htEntry;
+    }
+    htEntry = htEntry->next;
+  }
+  return NULL;
 }
 
 /****************************************************************************
@@ -167,7 +187,7 @@
   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;
@@ -177,22 +197,153 @@
   return newTable;
 }
 
-void destroyHashTable(HashTable* hashTable) {
+
+
+
+
+
+
 
-}
-
-void* insertItem(HashTable* hashTable, unsigned int key, void* value) {
+void destroyHashTable(HashTable* hashTable) {
+  //checks to make sure the hashtable has something in it
+  if (hashTable == NULL){
+    printf("Invalid Hash Table.");
+  }
+  //Goes through each bucket, freeing each value in each node and then the
+  //node itself. After, it frees the buckets and the hashtable ptr itself
+  HashTableEntry* next;
+  int i;
+  for(i = 0;i < hashTable->num_buckets; i++){
+    HashTableEntry* htEntry = hashTable->buckets[i];
+    while(htEntry != NULL){
+      next = htEntry->next;
+      //free node's value and ptr to node
+      free(htEntry->value);
+      free(htEntry);
+      htEntry = next;
+    }
+  }
+  free(hashTable->buckets);
+  free(hashTable);
 
 }
 
-void* getItem(HashTable* hashTable, unsigned int key) {
+
+
+
+
+
+
 
+void* insertItem(HashTable* hashTable, unsigned int key, void* value) {
+  int found = 0;
+  void* retval = NULL;
+  int index = hashTable->hash(key);
+  //Test for a Null Hash Table
+  if (hashTable == NULL){
+    printf("Invalid Hash Table.");
+    return NULL;
+  }
+  else{
+    //See if value is in the list. if value is in the list, return the node's old value
+    //and replace it with the new value that's read in
+    HashTableEntry* htEntry;
+    if((htEntry = findItem(hashTable, key))){
+      found = 1;
+      retval = htEntry->value;
+      htEntry->value = value; 
+    }
+
+
+    
+    //If entry wasn't found, create a new hash table entry for list 
+    //and put it at beginning of list.
+    if (!found){
+      HashTableEntry* newHtEntry = createHashTableEntry(key, value);
+      
+      //If the llist isn't empty insert it at the beginning
+      if(hashTable->buckets[index]){
+        newHtEntry->next = hashTable->buckets[index];
+      }
+      //point the bucket ptr to the head of the new hashtable entry
+      hashTable->buckets[index] = newHtEntry;
+      retval = NULL;
+
+    }
 }
+    return retval;
+  }
 
-void* removeItem(HashTable* hashTable, unsigned int key) {
+
+
+
+
+
+
+
+  
+
+
+
+
+
 
-}
+
+
+  void* removeItem(HashTable* hashTable, unsigned int key) {
+    void* retval = NULL;
+  //Test for a Null Hash Table
+    if (hashTable == NULL){
+      printf("Invalid Hash Table.");
+      return NULL;
+    }
+    else{
+    
+      int index = hashTable->hash(key);
+    //if the item is found, return the value of it, set the 
+      HashTableEntry* htEntry = hashTable->buckets[index];
+      if(htEntry == NULL){
+        return NULL;
+      }
+      else{
+        if(htEntry->key == key){
+          retval = htEntry->value;
+          if(htEntry->next){
+            hashTable->buckets[index] = htEntry->next;
+          }
+          else{
+            hashTable->buckets[index] = NULL;
+          }
+          free(htEntry);
+        }
+        else{
 
-void deleteItem(HashTable* hashTable, unsigned int key) {
+          //keep track of previous 
+          HashTableEntry* previous = htEntry;
+          while (htEntry->next != NULL){
+            previous = htEntry;
+            htEntry = htEntry->next;
+            if (htEntry->key == key){
+              retval = htEntry->value;
+              previous->next = htEntry->next;
+              free(htEntry);
+              break;
+            }
+          }
+        }
 
-}
\ No newline at end of file
+      }
+
+    }
+    return retval;
+  }
+
+
+
+
+
+
+  void deleteItem(HashTable* hashTable, unsigned int key) {
+    removeItem(hashTable, key);
+  }
+