Diff: hash_table.cpp

Revision:

4:2297a714936f

Parent:

0:35660d7952f7

--- a/hash_table.cpp	Mon Oct 28 05:26:35 2019 +0000
+++ b/hash_table.cpp	Tue Nov 19 16:53:47 2019 +0000
@@ -125,8 +125,21 @@
 * @param value The value stored in the hash table entry
 * @return The pointer to the hash table entry
 */
+//my code for createHashTableEntry
 static HashTableEntry* createHashTableEntry(unsigned int key, void* value) {
-
+    
+    HashTableEntry *newHashTableEntry;
+    
+    newHashTableEntry = (HashTableEntry*) malloc(sizeof(HashTableEntry));//malloc space
+    if(!newHashTableEntry){
+        return NULL;
+    }
+    
+    newHashTableEntry -> key = key;         //assign key
+    newHashTableEntry -> value = value;     //assign value
+    
+    
+    return newHashTableEntry;               //return the address of the HashTableEntry
 }
 
 /**
@@ -139,8 +152,17 @@
 * @param key The key corresponds to the hash table entry
 * @return The pointer to the hash table entry, or NULL if key does not exist
 */
+//myCode
 static HashTableEntry* findItem(HashTable* hashTable, unsigned int key) {
-
+    
+    HashTableEntry* this_node = hashTable -> buckets[hashTable->hash(key)];//head
+    while(this_node){//while there is a next node
+        if(this_node -> key == key){//if the nodes key is equal to one we are searching for
+            return this_node;
+        }
+        this_node = this_node -> next;//goes to next node   
+    }
+    return NULL;//returns null if not found
 }
 
 /****************************************************************************
@@ -167,7 +189,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 +199,170 @@
   return newTable;
 }
 
-void destroyHashTable(HashTable* hashTable) {
-
+/**
+ * destroyHashTable
+ *
+ * Destroy the hash table. The nodes (HashTableEntry objects) of singly linked
+ * list, the values stored on the linked list, the buckets, and the hashtable
+ * itself are freed from the heap. In other words, free all the allocated memory
+ * on heap that is associated with heap, including the values that users store in
+ * the hash table.
+ *
+ * @param myHashTable The pointer to the hash table.
+ *
+ */
+ //mycode
+void destroyHashTable(HashTable* hashTable) {//destroy everything
+    unsigned int numBuckets = hashTable -> num_buckets;// pull num_buckets
+    //hashTable -> buckets[i];
+    for(int i = 0; i < numBuckets; i++){//loop thorugh every bucket
+        HashTableEntry* this_node = hashTable -> buckets[i];
+        
+        while(this_node){//loop thorugh every node in a bucket
+            HashTableEntry* temp = this_node -> next;
+            free(this_node -> value);
+            free(this_node);
+            this_node = temp;
+        }
+    }
+    free(hashTable);//MR
+    return;
 }
-
+/**
+ * insertItem
+ *
+ * Insert the value into the hash table based on the key.
+ * In other words, create a new hash table entry and add it to a specific bucket.
+ *
+ * @param myHashTable The pointer to the hash table.
+ * @param key The key that corresponds to the value.
+ * @param value The value to be stored in the hash table.
+ * @return old value if it is overwritten, or NULL if not replaced
+ */
+ //my code
+ //og had: void* insertItem(HashTable* hashTable, unsigned int key, void* value)
 void* insertItem(HashTable* hashTable, unsigned int key, void* value) {
-
+    HashTableEntry* this_node; 
+    
+    if(this_node = findItem(hashTable, key)){//key in list
+        void* ret_value = this_node -> value;//save value
+        this_node -> value = value;          //give new value
+        return ret_value;                    //return old value
+    }
+    
+    //key not in list
+    this_node = createHashTableEntry(key, value);   //create new node
+    int bHash = hashTable -> hash(key); //get the index of bucket it is in
+    
+    this_node ->next = hashTable -> buckets[bHash]; //this_node -> next = head
+    hashTable -> buckets[bHash] = this_node;        //head = this_node
+    return NULL;
+    
 }
-
+/**
+ * getItem
+ *
+ * Get the value that corresponds to the key in the hash table.
+ *
+ * @param myHashTable The pointer to the hash table.
+ * @param key The key that corresponds to the item.
+ * @return the value corresponding to the key, or NULL if the key is not present
+ */
 void* getItem(HashTable* hashTable, unsigned int key) {
+    
+    HashTableEntry* found_node = findItem(hashTable, key); //head_node = head
+    
+    //if it found the node return the value of it
+    if(found_node){
+        return found_node -> value;
+    }
+    //otherwise return null
+    return NULL;
+}
+/**
+ * removeItem
+ *
+ * Remove the item in hash table based on the key and return the value stored in it.
+ * In other words, return the value and free the hash table entry from heap.
+ *
+ * @param myHashTable The pointer to the hash table.
+ * @param key The key that corresponds to the item.
+ * @return the pointer of the value corresponding to the key, or NULL if the key is not present
+ */
+void* removeItem(HashTable* hashTable, unsigned int key) {
+    HashTableEntry* this_node = hashTable -> buckets[hashTable->hash(key)]; //this_node = head
 
-}
-
-void* removeItem(HashTable* hashTable, unsigned int key) {
-
+    //case empty
+    if(!this_node)
+        return NULL;
+    
+    //case first element
+    if(this_node -> key == key){
+        void* ret_value = this_node -> value;//save the value
+        hashTable -> buckets[hashTable->hash(key)] = this_node -> next;//set head to the next node
+        //free all components
+    
+        free(this_node);
+        return ret_value;
+    }
+    
+    //case need to walk the list
+    while(this_node -> next){//already checked first node
+        if(this_node -> next -> key == key){//delete this if true
+            HashTableEntry* temp_node = this_node -> next;
+            void* ret_value = temp_node -> value;//save the value
+            this_node -> next = this_node -> next -> next;
+            
+            free(temp_node);
+            return ret_value;
+            
+        }
+        this_node = this_node -> next;
+    }
+    
+    return NULL;//did not find anything to remove
 }
+/**
+ * deleteItem
+ *
+ * Delete the item in the hash table based on the key. In other words, free the
+ * value stored in the hash table entry and the hash table entry itself from
+ * the heap.
+ *
+ * @param myHashTable The pointer to the hash table.
+ * @param key The key that corresponds to the item.
+ *
+ */
+ 
+ void deleteItem(HashTable* hashTable, unsigned int key){
+     HashTableEntry* this_node = hashTable -> buckets[hashTable->hash(key)]; //this_node = head
 
-void deleteItem(HashTable* hashTable, unsigned int key) {
-
-}
\ No newline at end of file
+    //case empty
+    if(!this_node)
+        return;
+    
+    //case first element
+    if(this_node -> key == key){
+        hashTable -> buckets[hashTable->hash(key)] = this_node -> next;//set head to the next node
+        //free all components
+        free(this_node -> value);
+        free(this_node);
+        return;
+    }
+    
+    //case need to walk the list
+    while(this_node -> next){//already checked first node
+        if(this_node -> next -> key == key){//delete this if true
+            HashTableEntry* temp_node = this_node -> next;
+            
+            this_node -> next = this_node -> next -> next;
+            free(temp_node->value);
+            free(temp_node);
+            return;
+            
+        }
+        this_node = this_node -> next;
+    }
+    
+    return;
+ }
\ No newline at end of file