Diff: hash_table.cpp

Revision:

2:22d36e7740f1

Parent:

0:35660d7952f7

--- a/hash_table.cpp	Wed Apr 04 21:11:07 2018 +0000
+++ b/hash_table.cpp	Mon Apr 15 12:25:08 2019 +0000
@@ -1,6 +1,6 @@
 /*
- Student Name:
- Date:
+ Student Name: Nikhil Patel
+ Date: 11-8-18
 
 =======================
 ECE 2035 Project 2-1:
@@ -30,7 +30,7 @@
     - "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
+  of the actual struct definition and the "nicknames" that we use to initialize
   new structs.
   [See Hidden Definitions section for more information.]
 
@@ -126,7 +126,11 @@
 * @return The pointer to the hash table entry
 */
 static HashTableEntry* createHashTableEntry(unsigned int key, void* value) {
-
+    HashTableEntry* node = (HashTableEntry*)malloc(sizeof(HashTableEntry));
+    node->value = value;
+    node->key = key;
+    node->next = NULL;
+    return node;
 }
 
 /**
@@ -140,7 +144,15 @@
 * @return The pointer to the hash table entry, or NULL if key does not exist
 */
 static HashTableEntry* findItem(HashTable* hashTable, unsigned int key) {
-
+    int bucketNum = hashTable->hash(key);
+    HashTableEntry* this_entry = hashTable->buckets[bucketNum];
+    while(this_entry) {
+      if(this_entry->key == key) {
+        return this_entry;
+      }
+      this_entry = this_entry->next;
+    }
+    return NULL;
 }
 
 /****************************************************************************
@@ -167,7 +179,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;
@@ -178,21 +190,109 @@
 }
 
 void destroyHashTable(HashTable* hashTable) {
-
+    unsigned int i = 0; //init counter
+    for(i=0; i<hashTable->num_buckets; ++i){ //loop through each bucket
+        HashTableEntry* iterator = hashTable->buckets[i]; //start at head of bucket
+        while(iterator){ //until reach end of linked list at bucket
+            HashTableEntry* tmp = iterator->next; //store the next node
+            free(iterator->value); //free the node's value
+            free(iterator); //free the node itself
+            iterator = tmp; //restore the next node
+        }
+    }
+    free(hashTable->buckets); //free the buckets
+    free(hashTable); //free the hash table itself
 }
 
 void* insertItem(HashTable* hashTable, unsigned int key, void* value) {
-
+    HashTableEntry* this_entry = findItem(hashTable,key); //will return a non-NULL value if the key exists
+    if(this_entry){ //if key already exists
+        void* replacedVal = this_entry->value; //get the value being replaces
+        this_entry->value = value; //replace the original value
+        return replacedVal; //return the value that was replaced
+    }
+    else{ //if key doesn't already exist
+        HashTableEntry* newNode = createHashTableEntry(key,value); //create a new node
+        int bucketNum = hashTable->hash(key); //get the bucket num where it will be added
+        if(hashTable->buckets[bucketNum] == NULL){ //if the bucket is empty
+            hashTable->buckets[bucketNum] = newNode; //the head of the bucket is the new node
+            return NULL; //return NULL to show nothing was replaced
+        }
+        else{ //if the bucket already has a linked list started
+            HashTableEntry* iterator = hashTable->buckets[bucketNum]; //first node
+            while(iterator){ //until the end of the linked list
+                if(iterator->next == NULL){ //reached tail of list
+                    iterator->next = newNode; //place new node at tail
+                    return NULL; //return NULL to show nothing was replaced
+                }
+                iterator = iterator->next; //go on to the next node
+            }
+        }
+    }
+    return NULL;
 }
 
 void* getItem(HashTable* hashTable, unsigned int key) {
-
+    int bucketNum = hashTable->hash(key); //get the bucket number of the item
+    HashTableEntry* this_entry = hashTable->buckets[bucketNum]; //get the head of the bucket
+    while(this_entry) { //loop through the bucket's linked list
+        if(this_entry->key == key) { //if the node's key matches to input
+            return this_entry->value; //return the matching value
+        }
+        this_entry = this_entry->next; //go on to next node
+    }
+    return NULL; //No node with such a key
 }
 
 void* removeItem(HashTable* hashTable, unsigned int key) {
-
+        int bucketNum = hashTable->hash(key); //bucket number where item is
+        HashTableEntry* iterator = hashTable->buckets[bucketNum]; //head of bucket
+        HashTableEntry* this_entry = findItem(hashTable,key); //get address/NULL of item
+        if(this_entry == NULL) //key doesnt exist
+            return NULL;
+        else{ //key exists
+            void* val = this_entry->value; //store key's value address
+            if(iterator == this_entry) { //item is first in linked list
+                hashTable->buckets[bucketNum] = this_entry->next; //unlink first node from list
+                free(this_entry); //free the first node
+                return val; //return the value of node removed
+            }
+            else{ //item isn't the first in the linked list
+                while(iterator){ //iterate through the linked list
+                    if(iterator->next->key == key){ //if next node has key
+                        iterator->next = this_entry->next; //unlink it from the list
+                        free(this_entry); //free it
+                        return val; //return the value of node removed
+                    }
+                    iterator = iterator->next; //go on to next node
+                }
+            }
+        }
+        return NULL;
 }
 
 void deleteItem(HashTable* hashTable, unsigned int key) {
-
-}
\ No newline at end of file
+    int bucketNum = hashTable->hash(key); //bucket where item is
+    HashTableEntry* iterator = hashTable->buckets[bucketNum]; //head of bucket
+    HashTableEntry* this_entry = findItem(hashTable,key); //get address/NULL of item
+    if(this_entry == NULL) //key doesnt exist
+        return; //do nothing
+    else{ //key exists
+        if(iterator == this_entry) { // item is first node of linked list
+            hashTable->buckets[bucketNum] = this_entry->next; //unlink first node from list
+            free(this_entry->value); //free the node's value
+            free(this_entry); //free the node
+        }
+        else{ //item isn't first node in list
+            while(iterator){ //iterate through list
+                if(iterator->next->key == key){ //if next node has key
+                    iterator->next = this_entry->next; //unlink node from list
+                    free(this_entry->value); //free node's value
+                    free(this_entry); //free node
+                    return;
+                }
+                iterator = iterator->next; //go to next node
+            }
+        }
+    }
+}