Rony Stephan / Mbed 2 deprecated 2035_rpg_game_fall2021

2035 project 2

Dependencies:   mbed wave_player 4DGL-uLCD-SE MMA8452

hash_table.cpp@23:06cbe894690d, 2021-12-01 (annotated)

Committer:
ranroun3
Date:
Wed Dec 01 23:39:02 2021 +0000
Revision:
23:06cbe894690d
Parent:
6:291aef457c4e 
FINAL p2-2;

Who changed what in which revision?

UserRevisionLine numberNew contents of line
rconnorlawson 0:35660d7952f7 1 /*
ranroun3 6:291aef457c4e 2 Student Name: Rony Stephan
ranroun3 6:291aef457c4e 3 Date:11/2/21
rconnorlawson 0:35660d7952f7 4
rconnorlawson 0:35660d7952f7 5 =======================
rconnorlawson 0:35660d7952f7 6 ECE 2035 Project 2-1:
rconnorlawson 0:35660d7952f7 7 =======================
rconnorlawson 0:35660d7952f7 8 This file provides definition for the structs and functions declared in the
rconnorlawson 0:35660d7952f7 9 header file. It also contains helper functions that are not accessible from
rconnorlawson 0:35660d7952f7 10 outside of the file.
rconnorlawson 0:35660d7952f7 11
rconnorlawson 0:35660d7952f7 12 FOR FULL CREDIT, BE SURE TO TRY MULTIPLE TEST CASES and DOCUMENT YOUR CODE.
rconnorlawson 0:35660d7952f7 13
rconnorlawson 0:35660d7952f7 14 ===================================
rconnorlawson 0:35660d7952f7 15 Naming conventions in this file:
rconnorlawson 0:35660d7952f7 16 ===================================
rconnorlawson 0:35660d7952f7 17 1. All struct names use camel case where the first letter is capitalized.
rconnorlawson 0:35660d7952f7 18 e.g. "HashTable", or "HashTableEntry"
rconnorlawson 0:35660d7952f7 19
rconnorlawson 0:35660d7952f7 20 2. Variable names with a preceding underscore "_" will not be called directly.
rconnorlawson 0:35660d7952f7 21 e.g. "_HashTable", "_HashTableEntry"
rconnorlawson 0:35660d7952f7 22
rconnorlawson 0:35660d7952f7 23 Recall that in C, we have to type "struct" together with the name of the struct
rconnorlawson 0:35660d7952f7 24 in order to initialize a new variable. To avoid this, in hash_table.h
rconnorlawson 0:35660d7952f7 25 we use typedef to provide new "nicknames" for "struct _HashTable" and
rconnorlawson 0:35660d7952f7 26 "struct _HashTableEntry". As a result, we can create new struct variables
rconnorlawson 0:35660d7952f7 27 by just using:
rconnorlawson 0:35660d7952f7 28 - "HashTable myNewTable;"
rconnorlawson 0:35660d7952f7 29 or
rconnorlawson 0:35660d7952f7 30 - "HashTableEntry myNewHashTableEntry;"
rconnorlawson 0:35660d7952f7 31
rconnorlawson 0:35660d7952f7 32 The preceding underscore "_" simply provides a distinction between the names
rconnorlawson 0:35660d7952f7 33 of the actual struct defition and the "nicknames" that we use to initialize
rconnorlawson 0:35660d7952f7 34 new structs.
rconnorlawson 0:35660d7952f7 35 [See Hidden Definitions section for more information.]
rconnorlawson 0:35660d7952f7 36
rconnorlawson 0:35660d7952f7 37 3. Functions, their local variables and arguments are named with camel case, where
rconnorlawson 0:35660d7952f7 38 the first letter is lower-case.
rconnorlawson 0:35660d7952f7 39 e.g. "createHashTable" is a function. One of its arguments is "numBuckets".
rconnorlawson 0:35660d7952f7 40 It also has a local variable called "newTable".
rconnorlawson 0:35660d7952f7 41
rconnorlawson 0:35660d7952f7 42 4. The name of a struct member is divided by using underscores "_". This serves
rconnorlawson 0:35660d7952f7 43 as a distinction between function local variables and struct members.
rconnorlawson 0:35660d7952f7 44 e.g. "num_buckets" is a member of "HashTable".
rconnorlawson 0:35660d7952f7 45
rconnorlawson 0:35660d7952f7 46 */
rconnorlawson 0:35660d7952f7 47
rconnorlawson 0:35660d7952f7 48 /****************************************************************************
rconnorlawson 0:35660d7952f7 49 * Include the Public Interface
rconnorlawson 0:35660d7952f7 50 *
rconnorlawson 0:35660d7952f7 51 * By including the public interface at the top of the file, the compiler can
rconnorlawson 0:35660d7952f7 52 * enforce that the function declarations in the the header are not in
rconnorlawson 0:35660d7952f7 53 * conflict with the definitions in the file. This is not a guarantee of
rconnorlawson 0:35660d7952f7 54 * correctness, but it is better than nothing!
rconnorlawson 0:35660d7952f7 55 ***************************************************************************/
rconnorlawson 0:35660d7952f7 56 #include "hash_table.h"
rconnorlawson 0:35660d7952f7 57
rconnorlawson 0:35660d7952f7 58
rconnorlawson 0:35660d7952f7 59 /****************************************************************************
rconnorlawson 0:35660d7952f7 60 * Include other private dependencies
rconnorlawson 0:35660d7952f7 61 *
rconnorlawson 0:35660d7952f7 62 * These other modules are used in the implementation of the hash table module,
rconnorlawson 0:35660d7952f7 63 * but are not required by users of the hash table.
rconnorlawson 0:35660d7952f7 64 ***************************************************************************/
rconnorlawson 0:35660d7952f7 65 #include <stdlib.h> // For malloc and free
rconnorlawson 0:35660d7952f7 66 #include <stdio.h> // For printf
rconnorlawson 0:35660d7952f7 67
rconnorlawson 0:35660d7952f7 68
rconnorlawson 0:35660d7952f7 69 /****************************************************************************
rconnorlawson 0:35660d7952f7 70 * Hidden Definitions
rconnorlawson 0:35660d7952f7 71 *
rconnorlawson 0:35660d7952f7 72 * These definitions are not available outside of this file. However, because
rconnorlawson 0:35660d7952f7 73 * the are forward declared in hash_table.h, the type names are
rconnorlawson 0:35660d7952f7 74 * available everywhere and user code can hold pointers to these structs.
rconnorlawson 0:35660d7952f7 75 ***************************************************************************/
rconnorlawson 0:35660d7952f7 76 /**
rconnorlawson 0:35660d7952f7 77 * This structure represents an a hash table.
rconnorlawson 0:35660d7952f7 78 * Use "HashTable" instead when you are creating a new variable. [See top comments]
rconnorlawson 0:35660d7952f7 79 */
rconnorlawson 0:35660d7952f7 80 struct _HashTable {
rconnorlawson 0:35660d7952f7 81 /** The array of pointers to the head of a singly linked list, whose nodes
rconnorlawson 0:35660d7952f7 82 are HashTableEntry objects */
rconnorlawson 0:35660d7952f7 83 HashTableEntry** buckets;
rconnorlawson 0:35660d7952f7 84
rconnorlawson 0:35660d7952f7 85 /** The hash function pointer */
rconnorlawson 0:35660d7952f7 86 HashFunction hash;
rconnorlawson 0:35660d7952f7 87
rconnorlawson 0:35660d7952f7 88 /** The number of buckets in the hash table */
rconnorlawson 0:35660d7952f7 89 unsigned int num_buckets;
rconnorlawson 0:35660d7952f7 90 };
rconnorlawson 0:35660d7952f7 91
rconnorlawson 0:35660d7952f7 92 /**
rconnorlawson 0:35660d7952f7 93 * This structure represents a hash table entry.
rconnorlawson 0:35660d7952f7 94 * Use "HashTableEntry" instead when you are creating a new variable. [See top comments]
rconnorlawson 0:35660d7952f7 95 */
rconnorlawson 0:35660d7952f7 96 struct _HashTableEntry {
rconnorlawson 0:35660d7952f7 97 /** The key for the hash table entry */
rconnorlawson 0:35660d7952f7 98 unsigned int key;
rconnorlawson 0:35660d7952f7 99
rconnorlawson 0:35660d7952f7 100 /** The value associated with this hash table entry */
rconnorlawson 0:35660d7952f7 101 void* value;
rconnorlawson 0:35660d7952f7 102
rconnorlawson 0:35660d7952f7 103 /**
rconnorlawson 0:35660d7952f7 104 * A pointer pointing to the next hash table entry
rconnorlawson 0:35660d7952f7 105 * NULL means there is no next entry (i.e. this is the tail)
rconnorlawson 0:35660d7952f7 106 */
rconnorlawson 0:35660d7952f7 107 HashTableEntry* next;
rconnorlawson 0:35660d7952f7 108 };
rconnorlawson 0:35660d7952f7 109
rconnorlawson 0:35660d7952f7 110
rconnorlawson 0:35660d7952f7 111 /****************************************************************************
rconnorlawson 0:35660d7952f7 112 * Private Functions
rconnorlawson 0:35660d7952f7 113 *
rconnorlawson 0:35660d7952f7 114 * These functions are not available outside of this file, since they are not
rconnorlawson 0:35660d7952f7 115 * declared in hash_table.h.
rconnorlawson 0:35660d7952f7 116 ***************************************************************************/
rconnorlawson 0:35660d7952f7 117 /**
rconnorlawson 0:35660d7952f7 118 * createHashTableEntry
rconnorlawson 0:35660d7952f7 119 *
rconnorlawson 0:35660d7952f7 120 * Helper function that creates a hash table entry by allocating memory for it on
rconnorlawson 0:35660d7952f7 121 * the heap. It initializes the entry with key and value, initialize pointer to
rconnorlawson 0:35660d7952f7 122 * the next entry as NULL, and return the pointer to this hash table entry.
rconnorlawson 0:35660d7952f7 123 *
rconnorlawson 0:35660d7952f7 124 * @param key The key corresponds to the hash table entry
rconnorlawson 0:35660d7952f7 125 * @param value The value stored in the hash table entry
rconnorlawson 0:35660d7952f7 126 * @return The pointer to the hash table entry
rconnorlawson 0:35660d7952f7 127 */
rconnorlawson 0:35660d7952f7 128 static HashTableEntry* createHashTableEntry(unsigned int key, void* value) {
ranroun3 6:291aef457c4e 129 HashTableEntry* curr_node = (HashTableEntry*) malloc(sizeof(HashTableEntry)); //mallocs the size
ranroun3 6:291aef457c4e 130 if(curr_node) { //edge case, no size found(pointer is null)
ranroun3 6:291aef457c4e 131 curr_node -> key = key; //sets key equal to parametrized key
ranroun3 6:291aef457c4e 132 curr_node -> value = value; //sets value equal to parametrized value
ranroun3 6:291aef457c4e 133 curr_node -> next = NULL; //sets next pointer equal to null(will later add at head)
ranroun3 6:291aef457c4e 134 }
rconnorlawson 0:35660d7952f7 135
ranroun3 6:291aef457c4e 136 return curr_node;
rconnorlawson 0:35660d7952f7 137 }
rconnorlawson 0:35660d7952f7 138
rconnorlawson 0:35660d7952f7 139 /**
rconnorlawson 0:35660d7952f7 140 * findItem
rconnorlawson 0:35660d7952f7 141 *
rconnorlawson 0:35660d7952f7 142 * Helper function that checks whether there exists the hash table entry that
rconnorlawson 0:35660d7952f7 143 * contains a specific key.
rconnorlawson 0:35660d7952f7 144 *
rconnorlawson 0:35660d7952f7 145 * @param hashTable The pointer to the hash table.
rconnorlawson 0:35660d7952f7 146 * @param key The key corresponds to the hash table entry
rconnorlawson 0:35660d7952f7 147 * @return The pointer to the hash table entry, or NULL if key does not exist
rconnorlawson 0:35660d7952f7 148 */
rconnorlawson 0:35660d7952f7 149 static HashTableEntry* findItem(HashTable* hashTable, unsigned int key) {
ranroun3 6:291aef457c4e 150 unsigned int bucketNum = hashTable -> hash(key); //hashes the current key to find bucket number
ranroun3 6:291aef457c4e 151 HashTableEntry* temp = hashTable -> buckets[bucketNum]; //grabs the first entry at that linked list
ranroun3 6:291aef457c4e 152 while(temp != NULL) { //while there is still a valid entry
ranroun3 6:291aef457c4e 153 if(temp -> key == key) { //if the key has been found
ranroun3 6:291aef457c4e 154 return temp; //return the pointer to the node
ranroun3 6:291aef457c4e 155 }
ranroun3 6:291aef457c4e 156 temp = temp -> next; //curr = curr.next
ranroun3 6:291aef457c4e 157 }
ranroun3 6:291aef457c4e 158 return NULL; //if code gets to this stage, it has not been found
rconnorlawson 0:35660d7952f7 159 }
rconnorlawson 0:35660d7952f7 160
rconnorlawson 0:35660d7952f7 161 /****************************************************************************
rconnorlawson 0:35660d7952f7 162 * Public Interface Functions
rconnorlawson 0:35660d7952f7 163 *
rconnorlawson 0:35660d7952f7 164 * These functions implement the public interface as specified in the header
rconnorlawson 0:35660d7952f7 165 * file, and make use of the private functions and hidden definitions in the
rconnorlawson 0:35660d7952f7 166 * above sections.
rconnorlawson 0:35660d7952f7 167 ****************************************************************************/
rconnorlawson 0:35660d7952f7 168 // The createHashTable is provided for you as a starting point.
rconnorlawson 0:35660d7952f7 169 HashTable* createHashTable(HashFunction hashFunction, unsigned int numBuckets) {
rconnorlawson 0:35660d7952f7 170 // The hash table has to contain at least one bucket. Exit gracefully if
rconnorlawson 0:35660d7952f7 171 // this condition is not met.
rconnorlawson 0:35660d7952f7 172 if (numBuckets==0) {
rconnorlawson 0:35660d7952f7 173 printf("Hash table has to contain at least 1 bucket...\n");
rconnorlawson 0:35660d7952f7 174 exit(1);
rconnorlawson 0:35660d7952f7 175 }
rconnorlawson 0:35660d7952f7 176
rconnorlawson 0:35660d7952f7 177 // Allocate memory for the new HashTable struct on heap.
rconnorlawson 0:35660d7952f7 178 HashTable* newTable = (HashTable*)malloc(sizeof(HashTable));
rconnorlawson 0:35660d7952f7 179
rconnorlawson 0:35660d7952f7 180 // Initialize the components of the new HashTable struct.
rconnorlawson 0:35660d7952f7 181 newTable->hash = hashFunction;
rconnorlawson 0:35660d7952f7 182 newTable->num_buckets = numBuckets;
rconnorlawson 0:35660d7952f7 183 newTable->buckets = (HashTableEntry**)malloc(numBuckets*sizeof(HashTableEntry*));
rconnorlawson 0:35660d7952f7 184
ranroun3 6:291aef457c4e 185 // As the new buckets contain indeterminant values, init each bucket as NULL.
rconnorlawson 0:35660d7952f7 186 unsigned int i;
rconnorlawson 0:35660d7952f7 187 for (i=0; i<numBuckets; ++i) {
rconnorlawson 0:35660d7952f7 188 newTable->buckets[i] = NULL;
rconnorlawson 0:35660d7952f7 189 }
rconnorlawson 0:35660d7952f7 190
rconnorlawson 0:35660d7952f7 191 // Return the new HashTable struct.
rconnorlawson 0:35660d7952f7 192 return newTable;
rconnorlawson 0:35660d7952f7 193 }
rconnorlawson 0:35660d7952f7 194
rconnorlawson 0:35660d7952f7 195 void destroyHashTable(HashTable* hashTable) {
ranroun3 6:291aef457c4e 196
ranroun3 6:291aef457c4e 197
ranroun3 6:291aef457c4e 198 //First, loop through all buckets in the structure.
rconnorlawson 0:35660d7952f7 199
ranroun3 6:291aef457c4e 200 unsigned int i;
ranroun3 6:291aef457c4e 201 for (i = 0; i < hashTable->num_buckets; i++) { //for loop through all buckets
ranroun3 6:291aef457c4e 202 if (hashTable->buckets[i]) { //if current bucket is not empty
ranroun3 6:291aef457c4e 203 HashTableEntry *curr_node = hashTable -> buckets[i]; //sets current node to head of buckets
ranroun3 6:291aef457c4e 204 HashTableEntry *next_node = NULL; //initializes next node pointer(to delete from head)
ranroun3 6:291aef457c4e 205
ranroun3 6:291aef457c4e 206 while(curr_node) { //while current node is not null
ranroun3 6:291aef457c4e 207 next_node = curr_node -> next; //next node is current node's next
ranroun3 6:291aef457c4e 208 free(curr_node->value); //free the current value at that node
ranroun3 6:291aef457c4e 209 free(curr_node); //free the current node
ranroun3 6:291aef457c4e 210 curr_node = next_node; //current node = next node
ranroun3 6:291aef457c4e 211 }
ranroun3 6:291aef457c4e 212 }
ranroun3 6:291aef457c4e 213 }
ranroun3 6:291aef457c4e 214 free(hashTable->buckets); //free the buckets array as a whole
ranroun3 6:291aef457c4e 215 free(hashTable); //free the hashtable structure as a whole
ranroun3 6:291aef457c4e 216
ranroun3 6:291aef457c4e 217
rconnorlawson 0:35660d7952f7 218 }
rconnorlawson 0:35660d7952f7 219
ranroun3 6:291aef457c4e 220 void *insertItem(HashTable *hashTable, unsigned int key, void *value)
ranroun3 6:291aef457c4e 221 {
ranroun3 6:291aef457c4e 222
ranroun3 6:291aef457c4e 223 HashTableEntry *curr_node = findItem(hashTable, key); //find the current item in hashtable
rconnorlawson 0:35660d7952f7 224
ranroun3 6:291aef457c4e 225 if (curr_node) //if node exists
ranroun3 6:291aef457c4e 226 {
ranroun3 6:291aef457c4e 227 void *old_value = curr_node->value; //store the old value
ranroun3 6:291aef457c4e 228 curr_node->value = value; //update value
ranroun3 6:291aef457c4e 229 return old_value; //return the old value
ranroun3 6:291aef457c4e 230 }
ranroun3 6:291aef457c4e 231 else
ranroun3 6:291aef457c4e 232 { // node does not exist
ranroun3 6:291aef457c4e 233 HashTableEntry *new_node = createHashTableEntry(key, value); //create new hashtable entry
ranroun3 6:291aef457c4e 234 if (!(new_node)) //if malloc fails when creating item(maybe redundant)
ranroun3 6:291aef457c4e 235 {
ranroun3 6:291aef457c4e 236 return NULL;
ranroun3 6:291aef457c4e 237 }
ranroun3 6:291aef457c4e 238 unsigned int bucketNum = hashTable->hash(key); //find the bucket number
ranroun3 6:291aef457c4e 239 HashTableEntry *head_node = hashTable->buckets[bucketNum]; //find the head node of current bucket
ranroun3 6:291aef457c4e 240
ranroun3 6:291aef457c4e 241 new_node->next = head_node; //set new node's next to current head
ranroun3 6:291aef457c4e 242 hashTable->buckets[bucketNum] = new_node; // current bucket's head is new node;
ranroun3 6:291aef457c4e 243 return NULL; //return null as item is inserted
ranroun3 6:291aef457c4e 244 }
rconnorlawson 0:35660d7952f7 245 }
rconnorlawson 0:35660d7952f7 246
rconnorlawson 0:35660d7952f7 247 void* getItem(HashTable* hashTable, unsigned int key) {
ranroun3 6:291aef457c4e 248 HashTableEntry* item = findItem(hashTable, key); //search for the item using findItem
ranroun3 6:291aef457c4e 249 if(item != NULL) { //if it has been found
ranroun3 6:291aef457c4e 250 return item ->value; //return the items value
ranroun3 6:291aef457c4e 251 }
ranroun3 6:291aef457c4e 252 else { //otherwise, return null
ranroun3 6:291aef457c4e 253 return NULL;
ranroun3 6:291aef457c4e 254 }
rconnorlawson 0:35660d7952f7 255 }
rconnorlawson 0:35660d7952f7 256
rconnorlawson 0:35660d7952f7 257 void* removeItem(HashTable* hashTable, unsigned int key) {
ranroun3 6:291aef457c4e 258 // HashTableEntry* curr_node = findItem(hashTable, key);
ranroun3 6:291aef457c4e 259 // if(!curr_node) {
ranroun3 6:291aef457c4e 260 // return NULL;
ranroun3 6:291aef457c4e 261 // }
ranroun3 6:291aef457c4e 262 // else{
ranroun3 6:291aef457c4e 263
ranroun3 6:291aef457c4e 264 unsigned int bucketNum = hashTable->hash(key); //hash the current key to find bucket number
ranroun3 6:291aef457c4e 265 HashTableEntry *curr_node = hashTable->buckets[bucketNum]; //set current node equal to head of correct LL
ranroun3 6:291aef457c4e 266 HashTableEntry* prev_node; //initialize trailing pointer
ranroun3 6:291aef457c4e 267 if(!curr_node){ //if LL is empty, return NULL
ranroun3 6:291aef457c4e 268 return NULL;
ranroun3 6:291aef457c4e 269 }
ranroun3 6:291aef457c4e 270
ranroun3 6:291aef457c4e 271 void* value_to_return; //initialize value to return
ranroun3 6:291aef457c4e 272
ranroun3 6:291aef457c4e 273 //CHECKING THE HEAD
ranroun3 6:291aef457c4e 274 if(curr_node -> key == key){ //if the value is present in head
ranroun3 6:291aef457c4e 275 value_to_return = curr_node->value; //store value of head
ranroun3 6:291aef457c4e 276 hashTable->buckets[bucketNum] = curr_node ->next; //set LL head to head.next
ranroun3 6:291aef457c4e 277 free(curr_node); //free current node and return value
ranroun3 6:291aef457c4e 278 return value_to_return;
ranroun3 6:291aef457c4e 279 }
ranroun3 6:291aef457c4e 280
ranroun3 6:291aef457c4e 281
ranroun3 6:291aef457c4e 282 //EDGE CASE WHERE LL ONLY HAS ONE VALUE AND ITS NOT FOUND
ranroun3 6:291aef457c4e 283
ranroun3 6:291aef457c4e 284 while(curr_node && curr_node -> next) { //while the current and next node are valid(curr_node starts at head, must have at least )
ranroun3 6:291aef457c4e 285 if(curr_node -> next-> key == key) { //if the next node's key is correct
ranroun3 6:291aef457c4e 286 prev_node = curr_node; //set the node before deletion(prev_node) equal to curr_node
ranroun3 6:291aef457c4e 287
ranroun3 6:291aef457c4e 288 HashTableEntry* node_to_remove = prev_node -> next; //set the removal node equal to the node after prev_node
ranroun3 6:291aef457c4e 289 value_to_return = node_to_remove -> value; //store the value from the node to remove
ranroun3 6:291aef457c4e 290
ranroun3 6:291aef457c4e 291 curr_node = node_to_remove -> next; //set the curr_node (after deletion) equal to removal node's next
ranroun3 6:291aef457c4e 292 prev_node ->next = curr_node; //set before deletion's next to after deletion
ranroun3 6:291aef457c4e 293 free(node_to_remove); //free current node
ranroun3 6:291aef457c4e 294 return value_to_return; //return value at removal node
ranroun3 6:291aef457c4e 295
ranroun3 6:291aef457c4e 296 }
ranroun3 6:291aef457c4e 297 prev_node = curr_node; //move previous node forward by one
ranroun3 6:291aef457c4e 298 curr_node = curr_node -> next; //move curr node forward by one
ranroun3 6:291aef457c4e 299 }
ranroun3 6:291aef457c4e 300 return NULL; //key not found, return null
ranroun3 6:291aef457c4e 301 }
ranroun3 6:291aef457c4e 302
ranroun3 6:291aef457c4e 303
ranroun3 6:291aef457c4e 304
ranroun3 6:291aef457c4e 305
ranroun3 6:291aef457c4e 306 void deleteItem(HashTable* hashTable, unsigned int key) {
ranroun3 6:291aef457c4e 307 free(removeItem(hashTable,key)); //frees the value returned by removeItem
rconnorlawson 0:35660d7952f7 308
rconnorlawson 0:35660d7952f7 309 }
rconnorlawson 0:35660d7952f7 310