ECE 2035 final project
Dependencies: mbed wave_player 4DGL-uLCD-SE MMA8452
hash_table.cpp
- Committer:
- npatel387
- Date:
- 2019-04-15
- Revision:
- 2:22d36e7740f1
- Parent:
- 0:35660d7952f7
File content as of revision 2:22d36e7740f1:
/* Student Name: Nikhil Patel Date: 11-8-18 ======================= 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 "struct _HashTableEntry". As a result, we can create new struct variables by just using: - "HashTable myNewTable;" or - "HashTableEntry myNewHashTableEntry;" The preceding underscore "_" simply provides a distinction between the names of the actual struct definition 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 * * By including the public interface at the top of the file, the compiler can * enforce that the function declarations in the the header are not in * conflict with the definitions in the file. This is not a guarantee of * correctness, but it is better than nothing! ***************************************************************************/ #include "hash_table.h" /**************************************************************************** * Include other private dependencies * * These other modules are used in the implementation of the hash table module, * but are not required by users of the hash table. ***************************************************************************/ #include <stdlib.h> // For malloc and free #include <stdio.h> // For printf /**************************************************************************** * Hidden Definitions * * These definitions are not available outside of this file. However, because * the are forward declared in hash_table.h, the type names are * available everywhere and user code can hold pointers to these structs. ***************************************************************************/ /** * This structure represents an a hash table. * Use "HashTable" instead when you are creating a new variable. [See top comments] */ struct _HashTable { /** 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] */ 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 * * These functions are not available outside of this file, since they are not * declared in hash_table.h. ***************************************************************************/ /** * createHashTableEntry * * Helper function that creates a hash table entry by allocating memory for it on * the heap. It initializes the entry with key and value, initialize pointer to * the next entry as NULL, and return the pointer to this hash table entry. * * @param key The key corresponds to the hash table entry * @param value The value stored in the hash table entry * @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; } /** * findItem * * Helper function that checks whether there exists the hash table entry that * contains a specific key. * * @param hashTable The pointer to the hash table. * @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 */ 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; } /**************************************************************************** * Public Interface Functions * * These functions implement the public interface as specified in the header * file, and make use of the private functions and hidden definitions in the * above sections. ****************************************************************************/ // The createHashTable is provided for you as a starting point. HashTable* createHashTable(HashFunction hashFunction, unsigned int numBuckets) { // The hash table has to contain at least one bucket. Exit gracefully if // this condition is not met. if (numBuckets==0) { 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 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) { 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) { 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 } } } }