Nikhil Patel / Mbed 2 deprecated rpg_game

ECE 2035 final project

Dependencies:   mbed wave_player 4DGL-uLCD-SE MMA8452

hash_table.cpp@2:22d36e7740f1, 2019-04-15 (annotated)

Committer:
npatel387
Date:
Mon Apr 15 12:25:08 2019 +0000
Revision:
2:22d36e7740f1
Parent:
0:35660d7952f7 
final;

Who changed what in which revision?

UserRevisionLine numberNew contents of line
rconnorlawson 0:35660d7952f7 1 /*
npatel387 2:22d36e7740f1 2 Student Name: Nikhil Patel
npatel387 2:22d36e7740f1 3 Date: 11-8-18
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
npatel387 2:22d36e7740f1 33 of the actual struct definition 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) {
npatel387 2:22d36e7740f1 129 HashTableEntry* node = (HashTableEntry*)malloc(sizeof(HashTableEntry));
npatel387 2:22d36e7740f1 130 node->value = value;
npatel387 2:22d36e7740f1 131 node->key = key;
npatel387 2:22d36e7740f1 132 node->next = NULL;
npatel387 2:22d36e7740f1 133 return node;
rconnorlawson 0:35660d7952f7 134 }
rconnorlawson 0:35660d7952f7 135
rconnorlawson 0:35660d7952f7 136 /**
rconnorlawson 0:35660d7952f7 137 * findItem
rconnorlawson 0:35660d7952f7 138 *
rconnorlawson 0:35660d7952f7 139 * Helper function that checks whether there exists the hash table entry that
rconnorlawson 0:35660d7952f7 140 * contains a specific key.
rconnorlawson 0:35660d7952f7 141 *
rconnorlawson 0:35660d7952f7 142 * @param hashTable The pointer to the hash table.
rconnorlawson 0:35660d7952f7 143 * @param key The key corresponds to the hash table entry
rconnorlawson 0:35660d7952f7 144 * @return The pointer to the hash table entry, or NULL if key does not exist
rconnorlawson 0:35660d7952f7 145 */
rconnorlawson 0:35660d7952f7 146 static HashTableEntry* findItem(HashTable* hashTable, unsigned int key) {
npatel387 2:22d36e7740f1 147 int bucketNum = hashTable->hash(key);
npatel387 2:22d36e7740f1 148 HashTableEntry* this_entry = hashTable->buckets[bucketNum];
npatel387 2:22d36e7740f1 149 while(this_entry) {
npatel387 2:22d36e7740f1 150 if(this_entry->key == key) {
npatel387 2:22d36e7740f1 151 return this_entry;
npatel387 2:22d36e7740f1 152 }
npatel387 2:22d36e7740f1 153 this_entry = this_entry->next;
npatel387 2:22d36e7740f1 154 }
npatel387 2:22d36e7740f1 155 return NULL;
rconnorlawson 0:35660d7952f7 156 }
rconnorlawson 0:35660d7952f7 157
rconnorlawson 0:35660d7952f7 158 /****************************************************************************
rconnorlawson 0:35660d7952f7 159 * Public Interface Functions
rconnorlawson 0:35660d7952f7 160 *
rconnorlawson 0:35660d7952f7 161 * These functions implement the public interface as specified in the header
rconnorlawson 0:35660d7952f7 162 * file, and make use of the private functions and hidden definitions in the
rconnorlawson 0:35660d7952f7 163 * above sections.
rconnorlawson 0:35660d7952f7 164 ****************************************************************************/
rconnorlawson 0:35660d7952f7 165 // The createHashTable is provided for you as a starting point.
rconnorlawson 0:35660d7952f7 166 HashTable* createHashTable(HashFunction hashFunction, unsigned int numBuckets) {
rconnorlawson 0:35660d7952f7 167 // The hash table has to contain at least one bucket. Exit gracefully if
rconnorlawson 0:35660d7952f7 168 // this condition is not met.
rconnorlawson 0:35660d7952f7 169 if (numBuckets==0) {
rconnorlawson 0:35660d7952f7 170 printf("Hash table has to contain at least 1 bucket...\n");
rconnorlawson 0:35660d7952f7 171 exit(1);
rconnorlawson 0:35660d7952f7 172 }
rconnorlawson 0:35660d7952f7 173
rconnorlawson 0:35660d7952f7 174 // Allocate memory for the new HashTable struct on heap.
rconnorlawson 0:35660d7952f7 175 HashTable* newTable = (HashTable*)malloc(sizeof(HashTable));
rconnorlawson 0:35660d7952f7 176
rconnorlawson 0:35660d7952f7 177 // Initialize the components of the new HashTable struct.
rconnorlawson 0:35660d7952f7 178 newTable->hash = hashFunction;
rconnorlawson 0:35660d7952f7 179 newTable->num_buckets = numBuckets;
rconnorlawson 0:35660d7952f7 180 newTable->buckets = (HashTableEntry**)malloc(numBuckets*sizeof(HashTableEntry*));
rconnorlawson 0:35660d7952f7 181
npatel387 2:22d36e7740f1 182 // As the new buckets contain indeterminant values, init each bucket as NULL.
rconnorlawson 0:35660d7952f7 183 unsigned int i;
rconnorlawson 0:35660d7952f7 184 for (i=0; i<numBuckets; ++i) {
rconnorlawson 0:35660d7952f7 185 newTable->buckets[i] = NULL;
rconnorlawson 0:35660d7952f7 186 }
rconnorlawson 0:35660d7952f7 187
rconnorlawson 0:35660d7952f7 188 // Return the new HashTable struct.
rconnorlawson 0:35660d7952f7 189 return newTable;
rconnorlawson 0:35660d7952f7 190 }
rconnorlawson 0:35660d7952f7 191
rconnorlawson 0:35660d7952f7 192 void destroyHashTable(HashTable* hashTable) {
npatel387 2:22d36e7740f1 193 unsigned int i = 0; //init counter
npatel387 2:22d36e7740f1 194 for(i=0; i<hashTable->num_buckets; ++i){ //loop through each bucket
npatel387 2:22d36e7740f1 195 HashTableEntry* iterator = hashTable->buckets[i]; //start at head of bucket
npatel387 2:22d36e7740f1 196 while(iterator){ //until reach end of linked list at bucket
npatel387 2:22d36e7740f1 197 HashTableEntry* tmp = iterator->next; //store the next node
npatel387 2:22d36e7740f1 198 free(iterator->value); //free the node's value
npatel387 2:22d36e7740f1 199 free(iterator); //free the node itself
npatel387 2:22d36e7740f1 200 iterator = tmp; //restore the next node
npatel387 2:22d36e7740f1 201 }
npatel387 2:22d36e7740f1 202 }
npatel387 2:22d36e7740f1 203 free(hashTable->buckets); //free the buckets
npatel387 2:22d36e7740f1 204 free(hashTable); //free the hash table itself
rconnorlawson 0:35660d7952f7 205 }
rconnorlawson 0:35660d7952f7 206
rconnorlawson 0:35660d7952f7 207 void* insertItem(HashTable* hashTable, unsigned int key, void* value) {
npatel387 2:22d36e7740f1 208 HashTableEntry* this_entry = findItem(hashTable,key); //will return a non-NULL value if the key exists
npatel387 2:22d36e7740f1 209 if(this_entry){ //if key already exists
npatel387 2:22d36e7740f1 210 void* replacedVal = this_entry->value; //get the value being replaces
npatel387 2:22d36e7740f1 211 this_entry->value = value; //replace the original value
npatel387 2:22d36e7740f1 212 return replacedVal; //return the value that was replaced
npatel387 2:22d36e7740f1 213 }
npatel387 2:22d36e7740f1 214 else{ //if key doesn't already exist
npatel387 2:22d36e7740f1 215 HashTableEntry* newNode = createHashTableEntry(key,value); //create a new node
npatel387 2:22d36e7740f1 216 int bucketNum = hashTable->hash(key); //get the bucket num where it will be added
npatel387 2:22d36e7740f1 217 if(hashTable->buckets[bucketNum] == NULL){ //if the bucket is empty
npatel387 2:22d36e7740f1 218 hashTable->buckets[bucketNum] = newNode; //the head of the bucket is the new node
npatel387 2:22d36e7740f1 219 return NULL; //return NULL to show nothing was replaced
npatel387 2:22d36e7740f1 220 }
npatel387 2:22d36e7740f1 221 else{ //if the bucket already has a linked list started
npatel387 2:22d36e7740f1 222 HashTableEntry* iterator = hashTable->buckets[bucketNum]; //first node
npatel387 2:22d36e7740f1 223 while(iterator){ //until the end of the linked list
npatel387 2:22d36e7740f1 224 if(iterator->next == NULL){ //reached tail of list
npatel387 2:22d36e7740f1 225 iterator->next = newNode; //place new node at tail
npatel387 2:22d36e7740f1 226 return NULL; //return NULL to show nothing was replaced
npatel387 2:22d36e7740f1 227 }
npatel387 2:22d36e7740f1 228 iterator = iterator->next; //go on to the next node
npatel387 2:22d36e7740f1 229 }
npatel387 2:22d36e7740f1 230 }
npatel387 2:22d36e7740f1 231 }
npatel387 2:22d36e7740f1 232 return NULL;
rconnorlawson 0:35660d7952f7 233 }
rconnorlawson 0:35660d7952f7 234
rconnorlawson 0:35660d7952f7 235 void* getItem(HashTable* hashTable, unsigned int key) {
npatel387 2:22d36e7740f1 236 int bucketNum = hashTable->hash(key); //get the bucket number of the item
npatel387 2:22d36e7740f1 237 HashTableEntry* this_entry = hashTable->buckets[bucketNum]; //get the head of the bucket
npatel387 2:22d36e7740f1 238 while(this_entry) { //loop through the bucket's linked list
npatel387 2:22d36e7740f1 239 if(this_entry->key == key) { //if the node's key matches to input
npatel387 2:22d36e7740f1 240 return this_entry->value; //return the matching value
npatel387 2:22d36e7740f1 241 }
npatel387 2:22d36e7740f1 242 this_entry = this_entry->next; //go on to next node
npatel387 2:22d36e7740f1 243 }
npatel387 2:22d36e7740f1 244 return NULL; //No node with such a key
rconnorlawson 0:35660d7952f7 245 }
rconnorlawson 0:35660d7952f7 246
rconnorlawson 0:35660d7952f7 247 void* removeItem(HashTable* hashTable, unsigned int key) {
npatel387 2:22d36e7740f1 248 int bucketNum = hashTable->hash(key); //bucket number where item is
npatel387 2:22d36e7740f1 249 HashTableEntry* iterator = hashTable->buckets[bucketNum]; //head of bucket
npatel387 2:22d36e7740f1 250 HashTableEntry* this_entry = findItem(hashTable,key); //get address/NULL of item
npatel387 2:22d36e7740f1 251 if(this_entry == NULL) //key doesnt exist
npatel387 2:22d36e7740f1 252 return NULL;
npatel387 2:22d36e7740f1 253 else{ //key exists
npatel387 2:22d36e7740f1 254 void* val = this_entry->value; //store key's value address
npatel387 2:22d36e7740f1 255 if(iterator == this_entry) { //item is first in linked list
npatel387 2:22d36e7740f1 256 hashTable->buckets[bucketNum] = this_entry->next; //unlink first node from list
npatel387 2:22d36e7740f1 257 free(this_entry); //free the first node
npatel387 2:22d36e7740f1 258 return val; //return the value of node removed
npatel387 2:22d36e7740f1 259 }
npatel387 2:22d36e7740f1 260 else{ //item isn't the first in the linked list
npatel387 2:22d36e7740f1 261 while(iterator){ //iterate through the linked list
npatel387 2:22d36e7740f1 262 if(iterator->next->key == key){ //if next node has key
npatel387 2:22d36e7740f1 263 iterator->next = this_entry->next; //unlink it from the list
npatel387 2:22d36e7740f1 264 free(this_entry); //free it
npatel387 2:22d36e7740f1 265 return val; //return the value of node removed
npatel387 2:22d36e7740f1 266 }
npatel387 2:22d36e7740f1 267 iterator = iterator->next; //go on to next node
npatel387 2:22d36e7740f1 268 }
npatel387 2:22d36e7740f1 269 }
npatel387 2:22d36e7740f1 270 }
npatel387 2:22d36e7740f1 271 return NULL;
rconnorlawson 0:35660d7952f7 272 }
rconnorlawson 0:35660d7952f7 273
rconnorlawson 0:35660d7952f7 274 void deleteItem(HashTable* hashTable, unsigned int key) {
npatel387 2:22d36e7740f1 275 int bucketNum = hashTable->hash(key); //bucket where item is
npatel387 2:22d36e7740f1 276 HashTableEntry* iterator = hashTable->buckets[bucketNum]; //head of bucket
npatel387 2:22d36e7740f1 277 HashTableEntry* this_entry = findItem(hashTable,key); //get address/NULL of item
npatel387 2:22d36e7740f1 278 if(this_entry == NULL) //key doesnt exist
npatel387 2:22d36e7740f1 279 return; //do nothing
npatel387 2:22d36e7740f1 280 else{ //key exists
npatel387 2:22d36e7740f1 281 if(iterator == this_entry) { // item is first node of linked list
npatel387 2:22d36e7740f1 282 hashTable->buckets[bucketNum] = this_entry->next; //unlink first node from list
npatel387 2:22d36e7740f1 283 free(this_entry->value); //free the node's value
npatel387 2:22d36e7740f1 284 free(this_entry); //free the node
npatel387 2:22d36e7740f1 285 }
npatel387 2:22d36e7740f1 286 else{ //item isn't first node in list
npatel387 2:22d36e7740f1 287 while(iterator){ //iterate through list
npatel387 2:22d36e7740f1 288 if(iterator->next->key == key){ //if next node has key
npatel387 2:22d36e7740f1 289 iterator->next = this_entry->next; //unlink node from list
npatel387 2:22d36e7740f1 290 free(this_entry->value); //free node's value
npatel387 2:22d36e7740f1 291 free(this_entry); //free node
npatel387 2:22d36e7740f1 292 return;
npatel387 2:22d36e7740f1 293 }
npatel387 2:22d36e7740f1 294 iterator = iterator->next; //go to next node
npatel387 2:22d36e7740f1 295 }
npatel387 2:22d36e7740f1 296 }
npatel387 2:22d36e7740f1 297 }
npatel387 2:22d36e7740f1 298 }