Diff: hash_table.cpp

Revision:

2:0876296d9473

Parent:

0:35660d7952f7

--- a/hash_table.cpp	Wed Apr 04 21:11:07 2018 +0000
+++ b/hash_table.cpp	Tue Apr 17 17:17:20 2018 +0000
@@ -1,5 +1,5 @@
 /*
- Student Name:
+ Student Name: Tiffany Montgomery
  Date:
 
 =======================
@@ -126,7 +126,14 @@
 * @return The pointer to the hash table entry
 */
 static HashTableEntry* createHashTableEntry(unsigned int key, void* value) {
-
+    HashTableEntry* entryptr = (HashTableEntry*)malloc(sizeof(HashTableEntry)); //allocate memory for the hash table entry
+    if (entryptr == NULL) return NULL; //if malloc fails return NULL pointer
+    
+    //initialize hash table entry values
+    entryptr->key = key;
+    entryptr->value = value;
+    entryptr ->next = NULL;
+    return entryptr; //return a pointer to the entry
 }
 
 /**
@@ -140,7 +147,16 @@
 * @return The pointer to the hash table entry, or NULL if key does not exist
 */
 static HashTableEntry* findItem(HashTable* hashTable, unsigned int key) {
-
+    unsigned int ind = hashTable->hash(key); //get the bucket index
+    HashTableEntry* entryptr = hashTable->buckets[ind]; //get a pointer to the head of the bucket the item is in
+    
+    while(entryptr){ //while entryptr is not NULL
+        if (entryptr-> key == key){
+            return entryptr;
+        }
+        entryptr = entryptr -> next;
+    }
+    return NULL; //return null pointer if the entry does not exist
 }
 
 /****************************************************************************
@@ -178,21 +194,101 @@
 }
 
 void destroyHashTable(HashTable* hashTable) {
-
+    
+    //check to see if the hash table has been created
+    if (hashTable != NULL){
+        
+        //iterate through each bucket and destroy each element
+        for (int i = 0; i < hashTable -> num_buckets; i++){
+            HashTableEntry* entryptr;
+            while(hashTable -> buckets[i]){ //while there is at least one element in the list
+                entryptr = hashTable -> buckets[i];
+                hashTable -> buckets[i] = entryptr ->next; //increment the head pointer
+                if(entryptr ->value) free(entryptr ->value); //free the value
+                if (entryptr) free(entryptr); //free the hashtable entry
+            }
+        }
+        free(hashTable -> buckets); //free pointer to bucket array
+        free(hashTable); //free hash table struct
+    }
 }
 
 void* insertItem(HashTable* hashTable, unsigned int key, void* value) {
+    HashTableEntry* entryptr;
+    if ((entryptr = findItem(hashTable, key))){ //if the key is in the hash table
+        void* temp = entryptr -> value;
+        entryptr -> value = value;
+        return temp;
+    }
+    
+    //create entry if key is not in hash table
+    entryptr = createHashTableEntry(key, value);
+    if(entryptr == NULL) return NULL;
+    int ind = hashTable -> hash(key);
+    
+    //insert entry at the head of the linked list
+    entryptr -> next = hashTable -> buckets[ind];
+    hashTable -> buckets[ind] = entryptr;
+    return NULL;
 
 }
 
 void* getItem(HashTable* hashTable, unsigned int key) {
-
+    HashTableEntry* entryptr;
+    entryptr = findItem(hashTable, key);
+    if(entryptr == NULL) return NULL;
+    if (entryptr -> value) return entryptr -> value;  //return value at key if key is present in the table
+    return NULL;
 }
 
 void* removeItem(HashTable* hashTable, unsigned int key) {
+    unsigned int ind = hashTable -> hash(key);
+    HashTableEntry* entryptr = hashTable -> buckets[ind];
+    if(entryptr == NULL) return NULL; //check if list is empty
+    
+    //if the item to be removed is at the end of the list
+    if(entryptr -> key == key){ //find the key
+        hashTable -> buckets[ind] = entryptr -> next; //increment the head pointer
+        void* val = entryptr ->value; //store value
+        free(entryptr);
+        return val;
+    }
+    
+    //if item to be removed is in the middle of the list or at the end of the list
+    while(entryptr->next){
+        if(entryptr->next->key == key){ //check to see if the next entry matches the key
+            HashTableEntry* temp = entryptr ->next;
+            entryptr -> next = entryptr ->next->next; //increment entryptr
+            void* val = temp -> value;
+            free(temp);
+            return val;
+        }
+        entryptr = entryptr ->next;
+    }
+    return NULL;
 
 }
 
 void deleteItem(HashTable* hashTable, unsigned int key) {
+    unsigned int ind = hashTable -> hash(key);
+    HashTableEntry* entryptr = hashTable -> buckets[ind];
+    
+    //if first item matches the key
+    if(entryptr && entryptr -> key == key){
+        hashTable -> buckets[ind] = entryptr -> next;
+        if(entryptr -> value) free(entryptr ->value); //if the entry still contains a value
+        free(entryptr);
+    }
+    
+    //if key is in the middle of or at the end of the list
+    while(entryptr && entryptr->next){
+        if(entryptr->next->key == key){
+            HashTableEntry* temp = entryptr ->next; 
+            entryptr -> next = entryptr ->next->next; //increment entryptr
+            if(entryptr -> value) free(temp -> value); //if the entry still contains a value
+            free(temp);
+        }
+        entryptr = entryptr ->next;
+    }
 
 }
\ No newline at end of file