project for 2035
Dependencies: mbed wave_player 4DGL-uLCD-SE MMA8452
Diff: hash_table.cpp
- Revision:
- 3:9dde875cd65c
- Parent:
- 2:4947d6a82971
- Child:
- 7:1912b4a2e4fe
diff -r 4947d6a82971 -r 9dde875cd65c hash_table.cpp --- a/hash_table.cpp Fri Oct 23 16:30:18 2020 -0400 +++ b/hash_table.cpp Tue Nov 24 08:35:47 2020 +0000 @@ -1,30 +1,33 @@ +//================================================================= // 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: - Date: - + Student Name: Kate Blake + Date: 11/2/2020 + ======================= 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 @@ -33,23 +36,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 * @@ -59,8 +62,8 @@ * correctness, but it is better than nothing! ***************************************************************************/ #include "hash_table.h" - - + + /**************************************************************************** * Include other private dependencies * @@ -69,8 +72,8 @@ ***************************************************************************/ #include <stdlib.h> // For malloc and free #include <stdio.h> // For printf - - + + /**************************************************************************** * Hidden Definitions * @@ -86,14 +89,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] @@ -101,18 +104,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 * @@ -131,9 +134,20 @@ * @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 * @@ -145,9 +159,28 @@ * @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 * @@ -163,40 +196,259 @@ 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 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; } - + // 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) { - -} \ No newline at end of file + 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; + } + } + } +}