Carter Montgomery / Mbed 2 deprecated 2035_Final_Project

Adventure game written for ECE2035 at the Georgia Institute of Technology

Dependencies:   mbed wave_player 4DGL-uLCD-SE MMA8452

hash_table.cpp@5:93a4c396c1af, 2019-10-26 (annotated)

Committer:
trmontgomery
Date:
Sat Oct 26 15:44:26 2019 +0000
Revision:
5:93a4c396c1af
Parent:
2:0876296d9473 
test

Who changed what in which revision?

UserRevisionLine numberNew contents of line
rconnorlawson 0:35660d7952f7 1 /*
trmontgomery 2:0876296d9473 2 Student Name: Tiffany Montgomery
rconnorlawson 0:35660d7952f7 3 Date:
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) {
trmontgomery 2:0876296d9473 129 HashTableEntry* entryptr = (HashTableEntry*)malloc(sizeof(HashTableEntry)); //allocate memory for the hash table entry
trmontgomery 2:0876296d9473 130 if (entryptr == NULL) return NULL; //if malloc fails return NULL pointer
trmontgomery 2:0876296d9473 131
trmontgomery 2:0876296d9473 132 //initialize hash table entry values
trmontgomery 2:0876296d9473 133 entryptr->key = key;
trmontgomery 2:0876296d9473 134 entryptr->value = value;
trmontgomery 2:0876296d9473 135 entryptr ->next = NULL;
trmontgomery 2:0876296d9473 136 return entryptr; //return a pointer to the entry
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) {
trmontgomery 2:0876296d9473 150 unsigned int ind = hashTable->hash(key); //get the bucket index
trmontgomery 2:0876296d9473 151 HashTableEntry* entryptr = hashTable->buckets[ind]; //get a pointer to the head of the bucket the item is in
trmontgomery 2:0876296d9473 152
trmontgomery 2:0876296d9473 153 while(entryptr){ //while entryptr is not NULL
trmontgomery 2:0876296d9473 154 if (entryptr-> key == key){
trmontgomery 2:0876296d9473 155 return entryptr;
trmontgomery 2:0876296d9473 156 }
trmontgomery 2:0876296d9473 157 entryptr = entryptr -> next;
trmontgomery 2:0876296d9473 158 }
trmontgomery 2:0876296d9473 159 return NULL; //return null pointer if the entry does not exist
rconnorlawson 0:35660d7952f7 160 }
rconnorlawson 0:35660d7952f7 161
rconnorlawson 0:35660d7952f7 162 /****************************************************************************
rconnorlawson 0:35660d7952f7 163 * Public Interface Functions
rconnorlawson 0:35660d7952f7 164 *
rconnorlawson 0:35660d7952f7 165 * These functions implement the public interface as specified in the header
rconnorlawson 0:35660d7952f7 166 * file, and make use of the private functions and hidden definitions in the
rconnorlawson 0:35660d7952f7 167 * above sections.
rconnorlawson 0:35660d7952f7 168 ****************************************************************************/
rconnorlawson 0:35660d7952f7 169 // The createHashTable is provided for you as a starting point.
rconnorlawson 0:35660d7952f7 170 HashTable* createHashTable(HashFunction hashFunction, unsigned int numBuckets) {
rconnorlawson 0:35660d7952f7 171 // The hash table has to contain at least one bucket. Exit gracefully if
rconnorlawson 0:35660d7952f7 172 // this condition is not met.
rconnorlawson 0:35660d7952f7 173 if (numBuckets==0) {
rconnorlawson 0:35660d7952f7 174 printf("Hash table has to contain at least 1 bucket...\n");
rconnorlawson 0:35660d7952f7 175 exit(1);
rconnorlawson 0:35660d7952f7 176 }
rconnorlawson 0:35660d7952f7 177
rconnorlawson 0:35660d7952f7 178 // Allocate memory for the new HashTable struct on heap.
rconnorlawson 0:35660d7952f7 179 HashTable* newTable = (HashTable*)malloc(sizeof(HashTable));
rconnorlawson 0:35660d7952f7 180
rconnorlawson 0:35660d7952f7 181 // Initialize the components of the new HashTable struct.
rconnorlawson 0:35660d7952f7 182 newTable->hash = hashFunction;
rconnorlawson 0:35660d7952f7 183 newTable->num_buckets = numBuckets;
rconnorlawson 0:35660d7952f7 184 newTable->buckets = (HashTableEntry**)malloc(numBuckets*sizeof(HashTableEntry*));
rconnorlawson 0:35660d7952f7 185
rconnorlawson 0:35660d7952f7 186 // As the new buckets are empty, init each bucket as NULL.
rconnorlawson 0:35660d7952f7 187 unsigned int i;
rconnorlawson 0:35660d7952f7 188 for (i=0; i<numBuckets; ++i) {
rconnorlawson 0:35660d7952f7 189 newTable->buckets[i] = NULL;
rconnorlawson 0:35660d7952f7 190 }
rconnorlawson 0:35660d7952f7 191
rconnorlawson 0:35660d7952f7 192 // Return the new HashTable struct.
rconnorlawson 0:35660d7952f7 193 return newTable;
rconnorlawson 0:35660d7952f7 194 }
rconnorlawson 0:35660d7952f7 195
rconnorlawson 0:35660d7952f7 196 void destroyHashTable(HashTable* hashTable) {
trmontgomery 2:0876296d9473 197
trmontgomery 2:0876296d9473 198 //check to see if the hash table has been created
trmontgomery 2:0876296d9473 199 if (hashTable != NULL){
trmontgomery 2:0876296d9473 200
trmontgomery 2:0876296d9473 201 //iterate through each bucket and destroy each element
trmontgomery 2:0876296d9473 202 for (int i = 0; i < hashTable -> num_buckets; i++){
trmontgomery 2:0876296d9473 203 HashTableEntry* entryptr;
trmontgomery 2:0876296d9473 204 while(hashTable -> buckets[i]){ //while there is at least one element in the list
trmontgomery 2:0876296d9473 205 entryptr = hashTable -> buckets[i];
trmontgomery 2:0876296d9473 206 hashTable -> buckets[i] = entryptr ->next; //increment the head pointer
trmontgomery 2:0876296d9473 207 if(entryptr ->value) free(entryptr ->value); //free the value
trmontgomery 2:0876296d9473 208 if (entryptr) free(entryptr); //free the hashtable entry
trmontgomery 2:0876296d9473 209 }
trmontgomery 2:0876296d9473 210 }
trmontgomery 2:0876296d9473 211 free(hashTable -> buckets); //free pointer to bucket array
trmontgomery 2:0876296d9473 212 free(hashTable); //free hash table struct
trmontgomery 2:0876296d9473 213 }
rconnorlawson 0:35660d7952f7 214 }
rconnorlawson 0:35660d7952f7 215
rconnorlawson 0:35660d7952f7 216 void* insertItem(HashTable* hashTable, unsigned int key, void* value) {
trmontgomery 2:0876296d9473 217 HashTableEntry* entryptr;
trmontgomery 2:0876296d9473 218 if ((entryptr = findItem(hashTable, key))){ //if the key is in the hash table
trmontgomery 2:0876296d9473 219 void* temp = entryptr -> value;
trmontgomery 2:0876296d9473 220 entryptr -> value = value;
trmontgomery 2:0876296d9473 221 return temp;
trmontgomery 2:0876296d9473 222 }
trmontgomery 2:0876296d9473 223
trmontgomery 2:0876296d9473 224 //create entry if key is not in hash table
trmontgomery 2:0876296d9473 225 entryptr = createHashTableEntry(key, value);
trmontgomery 2:0876296d9473 226 if(entryptr == NULL) return NULL;
trmontgomery 2:0876296d9473 227 int ind = hashTable -> hash(key);
trmontgomery 2:0876296d9473 228
trmontgomery 2:0876296d9473 229 //insert entry at the head of the linked list
trmontgomery 2:0876296d9473 230 entryptr -> next = hashTable -> buckets[ind];
trmontgomery 2:0876296d9473 231 hashTable -> buckets[ind] = entryptr;
trmontgomery 2:0876296d9473 232 return NULL;
rconnorlawson 0:35660d7952f7 233
rconnorlawson 0:35660d7952f7 234 }
rconnorlawson 0:35660d7952f7 235
rconnorlawson 0:35660d7952f7 236 void* getItem(HashTable* hashTable, unsigned int key) {
trmontgomery 2:0876296d9473 237 HashTableEntry* entryptr;
trmontgomery 2:0876296d9473 238 entryptr = findItem(hashTable, key);
trmontgomery 2:0876296d9473 239 if(entryptr == NULL) return NULL;
trmontgomery 2:0876296d9473 240 if (entryptr -> value) return entryptr -> value; //return value at key if key is present in the table
trmontgomery 2:0876296d9473 241 return NULL;
rconnorlawson 0:35660d7952f7 242 }
rconnorlawson 0:35660d7952f7 243
rconnorlawson 0:35660d7952f7 244 void* removeItem(HashTable* hashTable, unsigned int key) {
trmontgomery 2:0876296d9473 245 unsigned int ind = hashTable -> hash(key);
trmontgomery 2:0876296d9473 246 HashTableEntry* entryptr = hashTable -> buckets[ind];
trmontgomery 2:0876296d9473 247 if(entryptr == NULL) return NULL; //check if list is empty
trmontgomery 2:0876296d9473 248
trmontgomery 2:0876296d9473 249 //if the item to be removed is at the end of the list
trmontgomery 2:0876296d9473 250 if(entryptr -> key == key){ //find the key
trmontgomery 2:0876296d9473 251 hashTable -> buckets[ind] = entryptr -> next; //increment the head pointer
trmontgomery 2:0876296d9473 252 void* val = entryptr ->value; //store value
trmontgomery 2:0876296d9473 253 free(entryptr);
trmontgomery 2:0876296d9473 254 return val;
trmontgomery 2:0876296d9473 255 }
trmontgomery 2:0876296d9473 256
trmontgomery 2:0876296d9473 257 //if item to be removed is in the middle of the list or at the end of the list
trmontgomery 2:0876296d9473 258 while(entryptr->next){
trmontgomery 2:0876296d9473 259 if(entryptr->next->key == key){ //check to see if the next entry matches the key
trmontgomery 2:0876296d9473 260 HashTableEntry* temp = entryptr ->next;
trmontgomery 2:0876296d9473 261 entryptr -> next = entryptr ->next->next; //increment entryptr
trmontgomery 2:0876296d9473 262 void* val = temp -> value;
trmontgomery 2:0876296d9473 263 free(temp);
trmontgomery 2:0876296d9473 264 return val;
trmontgomery 2:0876296d9473 265 }
trmontgomery 2:0876296d9473 266 entryptr = entryptr ->next;
trmontgomery 2:0876296d9473 267 }
trmontgomery 2:0876296d9473 268 return NULL;
rconnorlawson 0:35660d7952f7 269
rconnorlawson 0:35660d7952f7 270 }
rconnorlawson 0:35660d7952f7 271
rconnorlawson 0:35660d7952f7 272 void deleteItem(HashTable* hashTable, unsigned int key) {
trmontgomery 2:0876296d9473 273 unsigned int ind = hashTable -> hash(key);
trmontgomery 2:0876296d9473 274 HashTableEntry* entryptr = hashTable -> buckets[ind];
trmontgomery 2:0876296d9473 275
trmontgomery 2:0876296d9473 276 //if first item matches the key
trmontgomery 2:0876296d9473 277 if(entryptr && entryptr -> key == key){
trmontgomery 2:0876296d9473 278 hashTable -> buckets[ind] = entryptr -> next;
trmontgomery 2:0876296d9473 279 if(entryptr -> value) free(entryptr ->value); //if the entry still contains a value
trmontgomery 2:0876296d9473 280 free(entryptr);
trmontgomery 2:0876296d9473 281 }
trmontgomery 2:0876296d9473 282
trmontgomery 2:0876296d9473 283 //if key is in the middle of or at the end of the list
trmontgomery 2:0876296d9473 284 while(entryptr && entryptr->next){
trmontgomery 2:0876296d9473 285 if(entryptr->next->key == key){
trmontgomery 2:0876296d9473 286 HashTableEntry* temp = entryptr ->next;
trmontgomery 2:0876296d9473 287 entryptr -> next = entryptr ->next->next; //increment entryptr
trmontgomery 2:0876296d9473 288 if(entryptr -> value) free(temp -> value); //if the entry still contains a value
trmontgomery 2:0876296d9473 289 free(temp);
trmontgomery 2:0876296d9473 290 }
trmontgomery 2:0876296d9473 291 entryptr = entryptr ->next;
trmontgomery 2:0876296d9473 292 }
rconnorlawson 0:35660d7952f7 293
rconnorlawson 0:35660d7952f7 294 }