Kate Blake / Mbed 2 deprecated Snake-game-fall2020-kateblake

project for 2035

Dependencies:   mbed wave_player 4DGL-uLCD-SE MMA8452

hash_table.cpp@8:2e18a96e0c77, 2020-11-24 (annotated)

Committer:
kblake9
Date:
Tue Nov 24 12:35:16 2020 +0000
Revision:
8:2e18a96e0c77
Parent:
7:1912b4a2e4fe 
fixed for now

Who changed what in which revision?

UserRevisionLine numberNew contents of line
kblake9 8:2e18a96e0c77 1 //=================================================================
DCchico 2:4947d6a82971 2 // Copyright 2020 Georgia Tech. All rights reserved.
DCchico 2:4947d6a82971 3 // The materials provided by the instructor in this course are for
DCchico 2:4947d6a82971 4 // the use of the students currently enrolled in the course.
DCchico 2:4947d6a82971 5 // Copyrighted course materials may not be further disseminated.
DCchico 2:4947d6a82971 6 // This file must not be made publicly available anywhere.
kblake9 8:2e18a96e0c77 7 //=================================================================
kblake9 8:2e18a96e0c77 8
DCchico 1:10330bce85cb 9 /*
kblake9 8:2e18a96e0c77 10 Student Name: Kate Blake
kblake9 8:2e18a96e0c77 11 Date: 11/2/2020
kblake9 8:2e18a96e0c77 12
DCchico 1:10330bce85cb 13 =======================
DCchico 1:10330bce85cb 14 ECE 2035 Project 2-1:
DCchico 1:10330bce85cb 15 =======================
DCchico 1:10330bce85cb 16 This file provides definition for the structs and functions declared in the
DCchico 1:10330bce85cb 17 header file. It also contains helper functions that are not accessible from
DCchico 1:10330bce85cb 18 outside of the file.
kblake9 8:2e18a96e0c77 19
DCchico 1:10330bce85cb 20 FOR FULL CREDIT, BE SURE TO TRY MULTIPLE TEST CASES and DOCUMENT YOUR CODE.
kblake9 8:2e18a96e0c77 21
DCchico 1:10330bce85cb 22 ===================================
DCchico 1:10330bce85cb 23 Naming conventions in this file:
DCchico 1:10330bce85cb 24 ===================================
DCchico 1:10330bce85cb 25 1. All struct names use camel case where the first letter is capitalized.
DCchico 1:10330bce85cb 26 e.g. "HashTable", or "HashTableEntry"
kblake9 8:2e18a96e0c77 27
DCchico 1:10330bce85cb 28 2. Variable names with a preceding underscore "_" will not be called directly.
DCchico 1:10330bce85cb 29 e.g. "_HashTable", "_HashTableEntry"
kblake9 8:2e18a96e0c77 30
DCchico 1:10330bce85cb 31 Recall that in C, we have to type "struct" together with the name of the struct
DCchico 1:10330bce85cb 32 in order to initialize a new variable. To avoid this, in hash_table.h
DCchico 1:10330bce85cb 33 we use typedef to provide new "nicknames" for "struct _HashTable" and
DCchico 1:10330bce85cb 34 "struct _HashTableEntry". As a result, we can create new struct variables
DCchico 1:10330bce85cb 35 by just using:
DCchico 1:10330bce85cb 36 - "HashTable myNewTable;"
DCchico 1:10330bce85cb 37 or
DCchico 1:10330bce85cb 38 - "HashTableEntry myNewHashTableEntry;"
kblake9 8:2e18a96e0c77 39
DCchico 1:10330bce85cb 40 The preceding underscore "_" simply provides a distinction between the names
DCchico 1:10330bce85cb 41 of the actual struct defition and the "nicknames" that we use to initialize
DCchico 1:10330bce85cb 42 new structs.
DCchico 1:10330bce85cb 43 [See Hidden Definitions section for more information.]
kblake9 8:2e18a96e0c77 44
DCchico 1:10330bce85cb 45 3. Functions, their local variables and arguments are named with camel case, where
DCchico 1:10330bce85cb 46 the first letter is lower-case.
DCchico 1:10330bce85cb 47 e.g. "createHashTable" is a function. One of its arguments is "numBuckets".
DCchico 1:10330bce85cb 48 It also has a local variable called "newTable".
kblake9 8:2e18a96e0c77 49
DCchico 1:10330bce85cb 50 4. The name of a struct member is divided by using underscores "_". This serves
DCchico 1:10330bce85cb 51 as a distinction between function local variables and struct members.
DCchico 1:10330bce85cb 52 e.g. "num_buckets" is a member of "HashTable".
kblake9 8:2e18a96e0c77 53
DCchico 1:10330bce85cb 54 */
kblake9 8:2e18a96e0c77 55
DCchico 1:10330bce85cb 56 /****************************************************************************
DCchico 1:10330bce85cb 57 * Include the Public Interface
DCchico 1:10330bce85cb 58 *
DCchico 1:10330bce85cb 59 * By including the public interface at the top of the file, the compiler can
DCchico 1:10330bce85cb 60 * enforce that the function declarations in the the header are not in
DCchico 1:10330bce85cb 61 * conflict with the definitions in the file. This is not a guarantee of
DCchico 1:10330bce85cb 62 * correctness, but it is better than nothing!
DCchico 1:10330bce85cb 63 ***************************************************************************/
DCchico 1:10330bce85cb 64 #include "hash_table.h"
kblake9 8:2e18a96e0c77 65
kblake9 8:2e18a96e0c77 66
DCchico 1:10330bce85cb 67 /****************************************************************************
DCchico 1:10330bce85cb 68 * Include other private dependencies
DCchico 1:10330bce85cb 69 *
DCchico 1:10330bce85cb 70 * These other modules are used in the implementation of the hash table module,
DCchico 1:10330bce85cb 71 * but are not required by users of the hash table.
DCchico 1:10330bce85cb 72 ***************************************************************************/
DCchico 1:10330bce85cb 73 #include <stdlib.h> // For malloc and free
DCchico 1:10330bce85cb 74 #include <stdio.h> // For printf
kblake9 8:2e18a96e0c77 75
kblake9 8:2e18a96e0c77 76
DCchico 1:10330bce85cb 77 /****************************************************************************
DCchico 1:10330bce85cb 78 * Hidden Definitions
DCchico 1:10330bce85cb 79 *
DCchico 1:10330bce85cb 80 * These definitions are not available outside of this file. However, because
DCchico 1:10330bce85cb 81 * the are forward declared in hash_table.h, the type names are
DCchico 1:10330bce85cb 82 * available everywhere and user code can hold pointers to these structs.
DCchico 1:10330bce85cb 83 ***************************************************************************/
DCchico 1:10330bce85cb 84 /**
DCchico 1:10330bce85cb 85 * This structure represents an a hash table.
DCchico 1:10330bce85cb 86 * Use "HashTable" instead when you are creating a new variable. [See top comments]
DCchico 1:10330bce85cb 87 */
DCchico 1:10330bce85cb 88 struct _HashTable {
DCchico 1:10330bce85cb 89 /** The array of pointers to the head of a singly linked list, whose nodes
DCchico 1:10330bce85cb 90 are HashTableEntry objects */
DCchico 1:10330bce85cb 91 HashTableEntry** buckets;
kblake9 8:2e18a96e0c77 92
DCchico 1:10330bce85cb 93 /** The hash function pointer */
DCchico 1:10330bce85cb 94 HashFunction hash;
kblake9 8:2e18a96e0c77 95
DCchico 1:10330bce85cb 96 /** The number of buckets in the hash table */
DCchico 1:10330bce85cb 97 unsigned int num_buckets;
DCchico 1:10330bce85cb 98 };
kblake9 8:2e18a96e0c77 99
DCchico 1:10330bce85cb 100 /**
DCchico 1:10330bce85cb 101 * This structure represents a hash table entry.
DCchico 1:10330bce85cb 102 * Use "HashTableEntry" instead when you are creating a new variable. [See top comments]
DCchico 1:10330bce85cb 103 */
DCchico 1:10330bce85cb 104 struct _HashTableEntry {
DCchico 1:10330bce85cb 105 /** The key for the hash table entry */
DCchico 1:10330bce85cb 106 unsigned int key;
kblake9 8:2e18a96e0c77 107
DCchico 1:10330bce85cb 108 /** The value associated with this hash table entry */
DCchico 1:10330bce85cb 109 void* value;
kblake9 8:2e18a96e0c77 110
DCchico 1:10330bce85cb 111 /**
DCchico 1:10330bce85cb 112 * A pointer pointing to the next hash table entry
DCchico 1:10330bce85cb 113 * NULL means there is no next entry (i.e. this is the tail)
DCchico 1:10330bce85cb 114 */
DCchico 1:10330bce85cb 115 HashTableEntry* next;
DCchico 1:10330bce85cb 116 };
kblake9 8:2e18a96e0c77 117
kblake9 8:2e18a96e0c77 118
DCchico 1:10330bce85cb 119 /****************************************************************************
DCchico 1:10330bce85cb 120 * Private Functions
DCchico 1:10330bce85cb 121 *
DCchico 1:10330bce85cb 122 * These functions are not available outside of this file, since they are not
DCchico 1:10330bce85cb 123 * declared in hash_table.h.
DCchico 1:10330bce85cb 124 ***************************************************************************/
DCchico 1:10330bce85cb 125 /**
DCchico 1:10330bce85cb 126 * createHashTableEntry
DCchico 1:10330bce85cb 127 *
DCchico 1:10330bce85cb 128 * Helper function that creates a hash table entry by allocating memory for it on
DCchico 1:10330bce85cb 129 * the heap. It initializes the entry with key and value, initialize pointer to
DCchico 1:10330bce85cb 130 * the next entry as NULL, and return the pointer to this hash table entry.
DCchico 1:10330bce85cb 131 *
DCchico 1:10330bce85cb 132 * @param key The key corresponds to the hash table entry
DCchico 1:10330bce85cb 133 * @param value The value stored in the hash table entry
DCchico 1:10330bce85cb 134 * @return The pointer to the hash table entry
DCchico 1:10330bce85cb 135 */
DCchico 1:10330bce85cb 136 static HashTableEntry* createHashTableEntry(unsigned int key, void* value) {
kblake9 8:2e18a96e0c77 137 //allocate memory for new hash table entry
kblake9 8:2e18a96e0c77 138 HashTableEntry* newHashTableEntry = (HashTableEntry*)malloc(sizeof(HashTableEntry));
kblake9 8:2e18a96e0c77 139
kblake9 8:2e18a96e0c77 140 //assign key var in struct to key parameter
kblake9 8:2e18a96e0c77 141 newHashTableEntry->key = key;
kblake9 8:2e18a96e0c77 142 //assign value var in struct to value parameter
kblake9 8:2e18a96e0c77 143 newHashTableEntry->value = value;
kblake9 8:2e18a96e0c77 144 //assign next var to default NULL
kblake9 8:2e18a96e0c77 145 newHashTableEntry->next = NULL;
kblake9 8:2e18a96e0c77 146
kblake9 8:2e18a96e0c77 147 //return the new entry
kblake9 8:2e18a96e0c77 148 return newHashTableEntry;
DCchico 1:10330bce85cb 149 }
kblake9 8:2e18a96e0c77 150
DCchico 1:10330bce85cb 151 /**
DCchico 1:10330bce85cb 152 * findItem
DCchico 1:10330bce85cb 153 *
DCchico 1:10330bce85cb 154 * Helper function that checks whether there exists the hash table entry that
DCchico 1:10330bce85cb 155 * contains a specific key.
DCchico 1:10330bce85cb 156 *
DCchico 1:10330bce85cb 157 * @param hashTable The pointer to the hash table.
DCchico 1:10330bce85cb 158 * @param key The key corresponds to the hash table entry
DCchico 1:10330bce85cb 159 * @return The pointer to the hash table entry, or NULL if key does not exist
DCchico 1:10330bce85cb 160 */
DCchico 1:10330bce85cb 161 static HashTableEntry* findItem(HashTable* hashTable, unsigned int key) {
kblake9 8:2e18a96e0c77 162 //check to make sure recieved valid hashTable
kblake9 8:2e18a96e0c77 163 if (hashTable != NULL) {
kblake9 8:2e18a96e0c77 164 //bucketNum variable to track what array space it takes up
kblake9 8:2e18a96e0c77 165 unsigned int bucketNum = hashTable->hash(key);
kblake9 8:2e18a96e0c77 166 //make sure the bucket exists
kblake9 8:2e18a96e0c77 167 if (hashTable->buckets[bucketNum] != NULL) {
kblake9 8:2e18a96e0c77 168 //currentEntry for tracking nested entries
kblake9 8:2e18a96e0c77 169 HashTableEntry* currentEntry = hashTable->buckets[bucketNum];
kblake9 8:2e18a96e0c77 170 //while loop for nested search
kblake9 8:2e18a96e0c77 171 while (currentEntry->key != key && currentEntry->next != NULL) {
kblake9 8:2e18a96e0c77 172 currentEntry = currentEntry->next;
kblake9 8:2e18a96e0c77 173 }
kblake9 8:2e18a96e0c77 174 //did we find it?
kblake9 8:2e18a96e0c77 175 if (currentEntry-> key == key) {
kblake9 8:2e18a96e0c77 176 return currentEntry;
kblake9 8:2e18a96e0c77 177 }
kblake9 8:2e18a96e0c77 178 }
kblake9 8:2e18a96e0c77 179 }
kblake9 8:2e18a96e0c77 180 //otherwise return NULL
kblake9 8:2e18a96e0c77 181 return NULL;
DCchico 1:10330bce85cb 182 }
kblake9 8:2e18a96e0c77 183
DCchico 1:10330bce85cb 184 /****************************************************************************
DCchico 1:10330bce85cb 185 * Public Interface Functions
DCchico 1:10330bce85cb 186 *
DCchico 1:10330bce85cb 187 * These functions implement the public interface as specified in the header
DCchico 1:10330bce85cb 188 * file, and make use of the private functions and hidden definitions in the
DCchico 1:10330bce85cb 189 * above sections.
DCchico 1:10330bce85cb 190 ****************************************************************************/
DCchico 1:10330bce85cb 191 // The createHashTable is provided for you as a starting point.
DCchico 1:10330bce85cb 192 HashTable* createHashTable(HashFunction hashFunction, unsigned int numBuckets) {
DCchico 1:10330bce85cb 193 // The hash table has to contain at least one bucket. Exit gracefully if
DCchico 1:10330bce85cb 194 // this condition is not met.
DCchico 1:10330bce85cb 195 if (numBuckets==0) {
DCchico 1:10330bce85cb 196 printf("Hash table has to contain at least 1 bucket...\n");
DCchico 1:10330bce85cb 197 exit(1);
DCchico 1:10330bce85cb 198 }
kblake9 8:2e18a96e0c77 199
DCchico 1:10330bce85cb 200 // Allocate memory for the new HashTable struct on heap.
DCchico 1:10330bce85cb 201 HashTable* newTable = (HashTable*)malloc(sizeof(HashTable));
kblake9 8:2e18a96e0c77 202
DCchico 1:10330bce85cb 203 // Initialize the components of the new HashTable struct.
DCchico 1:10330bce85cb 204 newTable->hash = hashFunction;
DCchico 1:10330bce85cb 205 newTable->num_buckets = numBuckets;
DCchico 1:10330bce85cb 206 newTable->buckets = (HashTableEntry**)malloc(numBuckets*sizeof(HashTableEntry*));
kblake9 8:2e18a96e0c77 207
kblake9 8:2e18a96e0c77 208 // As the new buckets contain indeterminant values, init each bucket as NULL.
DCchico 1:10330bce85cb 209 unsigned int i;
DCchico 1:10330bce85cb 210 for (i=0; i<numBuckets; ++i) {
DCchico 1:10330bce85cb 211 newTable->buckets[i] = NULL;
DCchico 1:10330bce85cb 212 }
kblake9 8:2e18a96e0c77 213
DCchico 1:10330bce85cb 214 // Return the new HashTable struct.
DCchico 1:10330bce85cb 215 return newTable;
DCchico 1:10330bce85cb 216 }
kblake9 8:2e18a96e0c77 217
DCchico 1:10330bce85cb 218 void destroyHashTable(HashTable* hashTable) {
kblake9 8:2e18a96e0c77 219 //make sure a hashtable exists to destroy
kblake9 8:2e18a96e0c77 220 if (hashTable != NULL) {
kblake9 8:2e18a96e0c77 221 unsigned int i;
kblake9 8:2e18a96e0c77 222 //search the buckets for entries to free
kblake9 8:2e18a96e0c77 223 for (i=0; i<hashTable->num_buckets; ++i) {
kblake9 8:2e18a96e0c77 224 if (hashTable->buckets[i] != NULL) {
kblake9 8:2e18a96e0c77 225 HashTableEntry* currentEntry = hashTable->buckets[i];
kblake9 8:2e18a96e0c77 226 HashTableEntry* pastEntry;
kblake9 8:2e18a96e0c77 227 //get the nested entries as well
kblake9 8:2e18a96e0c77 228 while (currentEntry -> next != NULL) {
kblake9 8:2e18a96e0c77 229 pastEntry = currentEntry;
kblake9 8:2e18a96e0c77 230 currentEntry = currentEntry -> next;
kblake9 8:2e18a96e0c77 231 if (pastEntry -> value != NULL) {
kblake9 8:2e18a96e0c77 232 //freeee them
kblake9 8:2e18a96e0c77 233 free(pastEntry->value);
kblake9 8:2e18a96e0c77 234 pastEntry->value = NULL;
kblake9 8:2e18a96e0c77 235 }
kblake9 8:2e18a96e0c77 236 //free them all
kblake9 8:2e18a96e0c77 237 if (pastEntry != NULL) {
kblake9 8:2e18a96e0c77 238 free(pastEntry);
kblake9 8:2e18a96e0c77 239 pastEntry = NULL;
kblake9 8:2e18a96e0c77 240 }
kblake9 8:2e18a96e0c77 241 }
kblake9 8:2e18a96e0c77 242 if (currentEntry -> value != NULL) {
kblake9 8:2e18a96e0c77 243 //make sure you catch all those bad boys
kblake9 8:2e18a96e0c77 244 free(currentEntry->value);
kblake9 8:2e18a96e0c77 245 currentEntry->value = NULL;
kblake9 8:2e18a96e0c77 246 }
kblake9 8:2e18a96e0c77 247 //this catches the one the while loop ignores
kblake9 8:2e18a96e0c77 248 if (currentEntry != NULL) {
kblake9 8:2e18a96e0c77 249 free(currentEntry);
kblake9 8:2e18a96e0c77 250 currentEntry = NULL;
kblake9 8:2e18a96e0c77 251 }
kblake9 8:2e18a96e0c77 252 }
kblake9 8:2e18a96e0c77 253 }
kblake9 8:2e18a96e0c77 254 //see if theres anything in the buckets
kblake9 8:2e18a96e0c77 255 if (hashTable->buckets != NULL) {
kblake9 8:2e18a96e0c77 256 //empty the buckets
kblake9 8:2e18a96e0c77 257 free(hashTable->buckets);
kblake9 8:2e18a96e0c77 258 hashTable->buckets = NULL;
kblake9 8:2e18a96e0c77 259 }
kblake9 8:2e18a96e0c77 260 //double check that hashtable just to be safe before freeing
kblake9 8:2e18a96e0c77 261 if (hashTable != NULL) {
kblake9 8:2e18a96e0c77 262 free(hashTable);
kblake9 8:2e18a96e0c77 263 hashTable = NULL;
kblake9 8:2e18a96e0c77 264 }
kblake9 8:2e18a96e0c77 265 }
DCchico 1:10330bce85cb 266 }
kblake9 8:2e18a96e0c77 267
DCchico 1:10330bce85cb 268 void* insertItem(HashTable* hashTable, unsigned int key, void* value) {
kblake9 8:2e18a96e0c77 269 //make sure a valid hashtable is provided
kblake9 8:2e18a96e0c77 270 if (hashTable == NULL) {
kblake9 8:2e18a96e0c77 271 return NULL;
kblake9 8:2e18a96e0c77 272 }
kblake9 8:2e18a96e0c77 273 //find what bucket this boys in
kblake9 8:2e18a96e0c77 274 unsigned int bucketNum = hashTable->hash(key);
kblake9 8:2e18a96e0c77 275 //create the entry for the boy
kblake9 8:2e18a96e0c77 276 HashTableEntry* hashTableEntry = createHashTableEntry(key, value);
kblake9 8:2e18a96e0c77 277 //checks if theres something already in the bucket
kblake9 8:2e18a96e0c77 278 if (hashTable->buckets[bucketNum] != NULL) {
kblake9 8:2e18a96e0c77 279 //are the keys the same?
kblake9 8:2e18a96e0c77 280 if (hashTable->buckets[bucketNum]->key == key) {
kblake9 8:2e18a96e0c77 281 //if so grab old value
kblake9 8:2e18a96e0c77 282 void* oldval = hashTable->buckets[bucketNum]->value;
kblake9 8:2e18a96e0c77 283 //free the old boy
kblake9 8:2e18a96e0c77 284 if (hashTable->buckets[bucketNum] != NULL) {
kblake9 8:2e18a96e0c77 285 free(hashTable->buckets[bucketNum]);
kblake9 8:2e18a96e0c77 286 }
kblake9 8:2e18a96e0c77 287 //overwrite
kblake9 8:2e18a96e0c77 288 hashTable->buckets[bucketNum] = hashTableEntry;
kblake9 8:2e18a96e0c77 289 //return old value
kblake9 8:2e18a96e0c77 290 return oldval;
kblake9 8:2e18a96e0c77 291 } else {
kblake9 8:2e18a96e0c77 292 //check for nested keys
kblake9 8:2e18a96e0c77 293 HashTableEntry* currentEntry = hashTable->buckets[bucketNum];
kblake9 8:2e18a96e0c77 294 HashTableEntry* pastEntry;
kblake9 8:2e18a96e0c77 295 while(currentEntry->next !=NULL && currentEntry-> key != key){
kblake9 8:2e18a96e0c77 296 //if there is another nested entry and the keys dont match keep cycling through the nested
kblake9 8:2e18a96e0c77 297 pastEntry = currentEntry;
kblake9 8:2e18a96e0c77 298 currentEntry = currentEntry->next;
kblake9 8:2e18a96e0c77 299 }
kblake9 8:2e18a96e0c77 300 //if the keys match take the old value replace it and return the old value
kblake9 8:2e18a96e0c77 301 if (currentEntry-> key == key) {
kblake9 8:2e18a96e0c77 302 void* oldval = currentEntry->value;
kblake9 8:2e18a96e0c77 303 if (hashTable->buckets[bucketNum] != NULL) {
kblake9 8:2e18a96e0c77 304 free(currentEntry);
kblake9 8:2e18a96e0c77 305 }
kblake9 8:2e18a96e0c77 306 //append to where old entry was
kblake9 8:2e18a96e0c77 307 pastEntry->next = hashTableEntry;
kblake9 8:2e18a96e0c77 308 return oldval;
kblake9 8:2e18a96e0c77 309 }
kblake9 8:2e18a96e0c77 310 //otherwise append to end of nested chain
kblake9 8:2e18a96e0c77 311 currentEntry->next = hashTableEntry;
kblake9 8:2e18a96e0c77 312 }
kblake9 8:2e18a96e0c77 313 } else {
kblake9 8:2e18a96e0c77 314 //if the bucket is uninhabited the boy now lives there
kblake9 8:2e18a96e0c77 315 hashTable->buckets[bucketNum] = hashTableEntry;
kblake9 8:2e18a96e0c77 316 }
kblake9 8:2e18a96e0c77 317 return NULL;
DCchico 1:10330bce85cb 318 }
kblake9 8:2e18a96e0c77 319
DCchico 1:10330bce85cb 320 void* getItem(HashTable* hashTable, unsigned int key) {
kblake9 8:2e18a96e0c77 321 //make sure a valid hashtable was provided
kblake9 8:2e18a96e0c77 322 if (hashTable == NULL) {
kblake9 8:2e18a96e0c77 323 return NULL;
kblake9 8:2e18a96e0c77 324 }
kblake9 8:2e18a96e0c77 325 //find which bucket it is
kblake9 8:2e18a96e0c77 326 unsigned int bucketNum = hashTable -> hash(key);
kblake9 8:2e18a96e0c77 327 //make sure bucket isnt empty
kblake9 8:2e18a96e0c77 328 if (hashTable->buckets[bucketNum] == NULL) {
kblake9 8:2e18a96e0c77 329 return NULL;
kblake9 8:2e18a96e0c77 330 } else {
kblake9 8:2e18a96e0c77 331 //otherwise find the entry
kblake9 8:2e18a96e0c77 332 HashTableEntry* foundHashEntry = findItem(hashTable, key);
kblake9 8:2e18a96e0c77 333 //make sure entry is valid
kblake9 8:2e18a96e0c77 334 if (foundHashEntry != NULL) {
kblake9 8:2e18a96e0c77 335 //return entry
kblake9 8:2e18a96e0c77 336 return foundHashEntry->value;
kblake9 8:2e18a96e0c77 337 }
kblake9 8:2e18a96e0c77 338 return NULL;
kblake9 8:2e18a96e0c77 339 }
DCchico 1:10330bce85cb 340 }
kblake9 8:2e18a96e0c77 341
DCchico 1:10330bce85cb 342 void* removeItem(HashTable* hashTable, unsigned int key) {
kblake9 8:2e18a96e0c77 343 //make sure valid hashtable is provided
kblake9 8:2e18a96e0c77 344 if (hashTable == NULL) {
kblake9 8:2e18a96e0c77 345 return NULL;
kblake9 8:2e18a96e0c77 346 }
kblake9 8:2e18a96e0c77 347 //initialize booleans to check for nesting conditions and bucket number
kblake9 8:2e18a96e0c77 348 unsigned int isNested = 0;
kblake9 8:2e18a96e0c77 349 unsigned int isntTail = 1;
kblake9 8:2e18a96e0c77 350 unsigned int bucketNum = hashTable->hash(key);
kblake9 8:2e18a96e0c77 351 //make sure bucket isnt empty
kblake9 8:2e18a96e0c77 352 if (hashTable->buckets[bucketNum] != NULL) {
kblake9 8:2e18a96e0c77 353 //define entries for nesting
kblake9 8:2e18a96e0c77 354 HashTableEntry* currentEntry = hashTable->buckets[bucketNum];
kblake9 8:2e18a96e0c77 355 HashTableEntry* pastEntry;
kblake9 8:2e18a96e0c77 356 HashTableEntry* futureEntry;
kblake9 8:2e18a96e0c77 357 //check for nesting and update variables as needed
kblake9 8:2e18a96e0c77 358 while (currentEntry->next !=NULL && currentEntry->key !=key) {
kblake9 8:2e18a96e0c77 359 pastEntry = currentEntry;
kblake9 8:2e18a96e0c77 360 currentEntry = currentEntry->next;
kblake9 8:2e18a96e0c77 361 isNested = 1;
kblake9 8:2e18a96e0c77 362 if (currentEntry->next == NULL) {
kblake9 8:2e18a96e0c77 363 isntTail = 0;
kblake9 8:2e18a96e0c77 364 } else {
kblake9 8:2e18a96e0c77 365 futureEntry = currentEntry -> next;
kblake9 8:2e18a96e0c77 366 }
kblake9 8:2e18a96e0c77 367 }
kblake9 8:2e18a96e0c77 368 //make sure entry is valid
kblake9 8:2e18a96e0c77 369 if (currentEntry != NULL){
kblake9 8:2e18a96e0c77 370 //check for sandwiched entry to be removed
kblake9 8:2e18a96e0c77 371 if (isNested == 1 && isntTail == 1) {
kblake9 8:2e18a96e0c77 372 pastEntry->next = futureEntry;
kblake9 8:2e18a96e0c77 373 //otherwise assume its the tail if its nested
kblake9 8:2e18a96e0c77 374 } else if (isNested == 1) {
kblake9 8:2e18a96e0c77 375 pastEntry->next = NULL;
kblake9 8:2e18a96e0c77 376 }
kblake9 8:2e18a96e0c77 377 //assign removed entry to return
kblake9 8:2e18a96e0c77 378 void* removedEntryVal = currentEntry->value;
kblake9 8:2e18a96e0c77 379 //double check for valid entry
kblake9 8:2e18a96e0c77 380 if (currentEntry != NULL) {
kblake9 8:2e18a96e0c77 381 //check whether it is only thing in bucket
kblake9 8:2e18a96e0c77 382 if (currentEntry->next !=NULL && isNested == 0) {
kblake9 8:2e18a96e0c77 383 futureEntry = currentEntry->next;
kblake9 8:2e18a96e0c77 384 hashTable->buckets[bucketNum] = futureEntry;
kblake9 8:2e18a96e0c77 385 } else if (isntTail == 1 && isNested == 0) {
kblake9 8:2e18a96e0c77 386 hashTable->buckets[bucketNum] = NULL;
kblake9 8:2e18a96e0c77 387 }
kblake9 8:2e18a96e0c77 388 //free removed entry
kblake9 8:2e18a96e0c77 389 free(currentEntry);
kblake9 8:2e18a96e0c77 390 currentEntry = NULL;
kblake9 8:2e18a96e0c77 391 }
kblake9 8:2e18a96e0c77 392 //return the entry
kblake9 8:2e18a96e0c77 393 return removedEntryVal;
kblake9 8:2e18a96e0c77 394 }
kblake9 8:2e18a96e0c77 395 }
kblake9 8:2e18a96e0c77 396 return NULL;
DCchico 1:10330bce85cb 397 }
kblake9 8:2e18a96e0c77 398
DCchico 1:10330bce85cb 399 void deleteItem(HashTable* hashTable, unsigned int key) {
kblake9 8:2e18a96e0c77 400 if (hashTable == NULL) {
kblake9 8:2e18a96e0c77 401 printf("Hash table doesn't exist.\n");
kblake9 8:2e18a96e0c77 402 exit(1);
kblake9 8:2e18a96e0c77 403 }
kblake9 8:2e18a96e0c77 404 //initialize booleans to check for nesting conditions and bucket number
kblake9 8:2e18a96e0c77 405 unsigned int isNested = 0;
kblake9 8:2e18a96e0c77 406 unsigned int isntTail = 1;
kblake9 8:2e18a96e0c77 407 unsigned int bucketNum = hashTable->hash(key);
kblake9 8:2e18a96e0c77 408 //make sure bucket isnt empty
kblake9 8:2e18a96e0c77 409 if (hashTable->buckets[bucketNum] != NULL) {
kblake9 8:2e18a96e0c77 410 //define entries for nesting
kblake9 8:2e18a96e0c77 411 HashTableEntry* currentEntry = hashTable->buckets[bucketNum];
kblake9 8:2e18a96e0c77 412 HashTableEntry* pastEntry;
kblake9 8:2e18a96e0c77 413 HashTableEntry* futureEntry;
kblake9 8:2e18a96e0c77 414 //check for nesting and update variables as needed
kblake9 8:2e18a96e0c77 415 while (currentEntry->next !=NULL && currentEntry->key !=key) {
kblake9 8:2e18a96e0c77 416 pastEntry = currentEntry;
kblake9 8:2e18a96e0c77 417 currentEntry = currentEntry->next;
kblake9 8:2e18a96e0c77 418 isNested = 1;
kblake9 8:2e18a96e0c77 419 if (currentEntry->next == NULL) {
kblake9 8:2e18a96e0c77 420 isntTail = 0;
kblake9 8:2e18a96e0c77 421 } else {
kblake9 8:2e18a96e0c77 422 futureEntry = currentEntry -> next;
kblake9 8:2e18a96e0c77 423 }
kblake9 8:2e18a96e0c77 424 }
kblake9 8:2e18a96e0c77 425 //make sure entry is valid
kblake9 8:2e18a96e0c77 426 if (currentEntry != NULL){
kblake9 8:2e18a96e0c77 427 //check for sandwiched entry to be removed
kblake9 8:2e18a96e0c77 428 if (isNested == 1 && isntTail == 1) {
kblake9 8:2e18a96e0c77 429 pastEntry->next = futureEntry;
kblake9 8:2e18a96e0c77 430 //otherwise assume its the tail if its nested
kblake9 8:2e18a96e0c77 431 } else if (isNested == 1) {
kblake9 8:2e18a96e0c77 432 pastEntry->next = NULL;
kblake9 8:2e18a96e0c77 433 }
kblake9 8:2e18a96e0c77 434 //double check for valid entry
kblake9 8:2e18a96e0c77 435 if (currentEntry != NULL) {
kblake9 8:2e18a96e0c77 436 //check whether it is only thing in bucket
kblake9 8:2e18a96e0c77 437 if (currentEntry->next !=NULL && isNested == 0) {
kblake9 8:2e18a96e0c77 438 futureEntry = currentEntry->next;
kblake9 8:2e18a96e0c77 439 hashTable->buckets[bucketNum] = futureEntry;
kblake9 8:2e18a96e0c77 440 } else if (isntTail == 1 && isNested == 0) {
kblake9 8:2e18a96e0c77 441 hashTable->buckets[bucketNum] = NULL;
kblake9 8:2e18a96e0c77 442 }
kblake9 8:2e18a96e0c77 443 if (currentEntry -> value != NULL) {
kblake9 8:2e18a96e0c77 444 //free value
kblake9 8:2e18a96e0c77 445 free(currentEntry->value);
kblake9 8:2e18a96e0c77 446 currentEntry->value = NULL;
kblake9 8:2e18a96e0c77 447 }
kblake9 8:2e18a96e0c77 448 //free removed entry
kblake9 8:2e18a96e0c77 449 free(currentEntry);
kblake9 8:2e18a96e0c77 450 currentEntry = NULL;
kblake9 8:2e18a96e0c77 451 }
kblake9 8:2e18a96e0c77 452 }
kblake9 8:2e18a96e0c77 453 }
kblake9 8:2e18a96e0c77 454 }