Randall Kliman / Mbed 2 deprecated NEOPUNK

Important changes to repositories hosted on mbed.com

Mbed hosted mercurial repositories are deprecated and are due to be permanently deleted in July 2026.

To keep a copy of this software download the repository Zip archive or clone locally using Mercurial.

It is also possible to export all your personal repositories from the account settings page.

Dependencies:   mbed wave_player 4DGL-uLCD-SE MMA8452

hash_table.cpp@2:06c63d567719, 2018-11-30 (annotated)

Committer:
Sterofin
Date:
Fri Nov 30 02:53:05 2018 +0000
Revision:
2:06c63d567719
Parent:
0:35660d7952f7
Child:
5:a16af8f3fea9
doot

Who changed what in which revision?

UserRevisionLine numberNew contents of line
rconnorlawson 0:35660d7952f7 1 /*
Sterofin 2:06c63d567719 2 Student Name: Randall Kliman
Sterofin 2:06c63d567719 3 Date: 11/9/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
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) {
Sterofin 2:06c63d567719 129 HashTableEntry* this_entry; //create pointer to entry we will create
Sterofin 2:06c63d567719 130 this_entry = (HashTableEntry*)malloc(sizeof(HashTableEntry)); // Allocate our entry
Sterofin 2:06c63d567719 131 //if(!this_entry) return this_entry; //if this entry is null, return null
Sterofin 2:06c63d567719 132 this_entry->key = key;
Sterofin 2:06c63d567719 133 this_entry->value = value; //Initialize entry fields
Sterofin 2:06c63d567719 134 this_entry->next = NULL;
Sterofin 2:06c63d567719 135 return this_entry; //Return pointer to entry
rconnorlawson 0:35660d7952f7 136 }
rconnorlawson 0:35660d7952f7 137
rconnorlawson 0:35660d7952f7 138 /**
rconnorlawson 0:35660d7952f7 139 * findItem
rconnorlawson 0:35660d7952f7 140 *
rconnorlawson 0:35660d7952f7 141 * Helper function that checks whether there exists the hash table entry that
rconnorlawson 0:35660d7952f7 142 * contains a specific key.
rconnorlawson 0:35660d7952f7 143 *
rconnorlawson 0:35660d7952f7 144 * @param hashTable The pointer to the hash table.
rconnorlawson 0:35660d7952f7 145 * @param key The key corresponds to the hash table entry
rconnorlawson 0:35660d7952f7 146 * @return The pointer to the hash table entry, or NULL if key does not exist
rconnorlawson 0:35660d7952f7 147 */
rconnorlawson 0:35660d7952f7 148 static HashTableEntry* findItem(HashTable* hashTable, unsigned int key) {
Sterofin 2:06c63d567719 149 unsigned int bucket = (hashTable->hash)(key); //Find which bucket our entry is in
rconnorlawson 0:35660d7952f7 150
Sterofin 2:06c63d567719 151 HashTableEntry * this_entry = hashTable->buckets[bucket]; //gets head
Sterofin 2:06c63d567719 152 while (this_entry) { //Iterates through the list to find the entry
Sterofin 2:06c63d567719 153 if(this_entry->key == key) return this_entry; //If this is what we are looking for
Sterofin 2:06c63d567719 154 this_entry = this_entry->next; //Iterate
Sterofin 2:06c63d567719 155 }
Sterofin 2:06c63d567719 156 return this_entry; //This should return NULL, since this_entry->next will be NULL if it cannot find the appropriate key
rconnorlawson 0:35660d7952f7 157 }
rconnorlawson 0:35660d7952f7 158
rconnorlawson 0:35660d7952f7 159 /****************************************************************************
rconnorlawson 0:35660d7952f7 160 * Public Interface Functions
rconnorlawson 0:35660d7952f7 161 *
rconnorlawson 0:35660d7952f7 162 * These functions implement the public interface as specified in the header
rconnorlawson 0:35660d7952f7 163 * file, and make use of the private functions and hidden definitions in the
rconnorlawson 0:35660d7952f7 164 * above sections.
rconnorlawson 0:35660d7952f7 165 ****************************************************************************/
rconnorlawson 0:35660d7952f7 166 // The createHashTable is provided for you as a starting point.
rconnorlawson 0:35660d7952f7 167 HashTable* createHashTable(HashFunction hashFunction, unsigned int numBuckets) {
rconnorlawson 0:35660d7952f7 168 // The hash table has to contain at least one bucket. Exit gracefully if
rconnorlawson 0:35660d7952f7 169 // this condition is not met.
rconnorlawson 0:35660d7952f7 170 if (numBuckets==0) {
rconnorlawson 0:35660d7952f7 171 printf("Hash table has to contain at least 1 bucket...\n");
rconnorlawson 0:35660d7952f7 172 exit(1);
rconnorlawson 0:35660d7952f7 173 }
rconnorlawson 0:35660d7952f7 174
rconnorlawson 0:35660d7952f7 175 // Allocate memory for the new HashTable struct on heap.
rconnorlawson 0:35660d7952f7 176 HashTable* newTable = (HashTable*)malloc(sizeof(HashTable));
rconnorlawson 0:35660d7952f7 177
rconnorlawson 0:35660d7952f7 178 // Initialize the components of the new HashTable struct.
rconnorlawson 0:35660d7952f7 179 newTable->hash = hashFunction;
rconnorlawson 0:35660d7952f7 180 newTable->num_buckets = numBuckets;
rconnorlawson 0:35660d7952f7 181 newTable->buckets = (HashTableEntry**)malloc(numBuckets*sizeof(HashTableEntry*));
rconnorlawson 0:35660d7952f7 182
Sterofin 2:06c63d567719 183 // As the new buckets contain indeterminant values, init each bucket as NULL.
rconnorlawson 0:35660d7952f7 184 unsigned int i;
rconnorlawson 0:35660d7952f7 185 for (i=0; i<numBuckets; ++i) {
rconnorlawson 0:35660d7952f7 186 newTable->buckets[i] = NULL;
rconnorlawson 0:35660d7952f7 187 }
rconnorlawson 0:35660d7952f7 188
rconnorlawson 0:35660d7952f7 189 // Return the new HashTable struct.
rconnorlawson 0:35660d7952f7 190 return newTable;
rconnorlawson 0:35660d7952f7 191 }
rconnorlawson 0:35660d7952f7 192
Sterofin 2:06c63d567719 193 /*
Sterofin 2:06c63d567719 194 * destroyHashTable
Sterofin 2:06c63d567719 195 *
Sterofin 2:06c63d567719 196 * This function systematically frees all data allocated within the hash table
Sterofin 2:06c63d567719 197 *
Sterofin 2:06c63d567719 198 *@param hashTable The hash table that will be destroyed
Sterofin 2:06c63d567719 199 */
rconnorlawson 0:35660d7952f7 200 void destroyHashTable(HashTable* hashTable) {
Sterofin 2:06c63d567719 201 //Iterates through buckets
Sterofin 2:06c63d567719 202 for(int i = 0; i < hashTable->num_buckets;i++){
Sterofin 2:06c63d567719 203 //Iterates through the linked list of a bucket and systematically frees each entry
Sterofin 2:06c63d567719 204 while(hashTable->buckets[i]){
Sterofin 2:06c63d567719 205 deleteItem(hashTable,hashTable->buckets[i]->key);
Sterofin 2:06c63d567719 206 }
Sterofin 2:06c63d567719 207 }
Sterofin 2:06c63d567719 208 free(hashTable->buckets); //free the bucket array;
Sterofin 2:06c63d567719 209 free(hashTable); //free the hashTable "object"
rconnorlawson 0:35660d7952f7 210 }
rconnorlawson 0:35660d7952f7 211
Sterofin 2:06c63d567719 212 /*
Sterofin 2:06c63d567719 213 * insertItem
Sterofin 2:06c63d567719 214 *
Sterofin 2:06c63d567719 215 * This function inserts an item into our hash table based on the hash of our key.
Sterofin 2:06c63d567719 216 * If it an entry already exists for the key, then we replace the current value of the
Sterofin 2:06c63d567719 217 * target entry with a new value and return a pointer to the old value. If an entry
Sterofin 2:06c63d567719 218 * does not already exist, create it at the front of a list and return a pointer
Sterofin 2:06c63d567719 219 * to the value we inserted.
Sterofin 2:06c63d567719 220 *
Sterofin 2:06c63d567719 221 *@param hashTable The hash table to look in
Sterofin 2:06c63d567719 222 *@param key The key of the entry we want to remove
Sterofin 2:06c63d567719 223 *@return a pointer to either the value we insert, or the value we are replacing
Sterofin 2:06c63d567719 224 */
rconnorlawson 0:35660d7952f7 225 void* insertItem(HashTable* hashTable, unsigned int key, void* value) {
Sterofin 2:06c63d567719 226 int bucket = (hashTable->hash)(key); //Find which bucket our entry is in
Sterofin 2:06c63d567719 227 HashTableEntry* this_entry;
rconnorlawson 0:35660d7952f7 228
Sterofin 2:06c63d567719 229 //Overwrite Case: replace item value, return old value
Sterofin 2:06c63d567719 230 this_entry = findItem(hashTable,key);
Sterofin 2:06c63d567719 231 if(this_entry){
Sterofin 2:06c63d567719 232 void* itemval;
Sterofin 2:06c63d567719 233 itemval = this_entry->value;
Sterofin 2:06c63d567719 234 this_entry->value = value;
Sterofin 2:06c63d567719 235 return itemval;
Sterofin 2:06c63d567719 236 }
Sterofin 2:06c63d567719 237 //If nothing exists in our bucket, create a first entry
Sterofin 2:06c63d567719 238 HashTableEntry* he = createHashTableEntry(key,value);
Sterofin 2:06c63d567719 239 //otherwise, create an entry at the beginning of the bucket list
Sterofin 2:06c63d567719 240 if(!he){return NULL;}
Sterofin 2:06c63d567719 241 he->next = hashTable->buckets[bucket];
Sterofin 2:06c63d567719 242 hashTable->buckets[bucket] = he;
Sterofin 2:06c63d567719 243 return NULL;
Sterofin 2:06c63d567719 244 }
Sterofin 2:06c63d567719 245
Sterofin 2:06c63d567719 246 /*
Sterofin 2:06c63d567719 247 * getItem
Sterofin 2:06c63d567719 248 *
Sterofin 2:06c63d567719 249 * This function finds data within a hash table
Sterofin 2:06c63d567719 250 *
Sterofin 2:06c63d567719 251 *@param hashTable The hash table to look in
Sterofin 2:06c63d567719 252 *@param key The key of the entry we are looking for
Sterofin 2:06c63d567719 253 *@return NULL if we don't find it, a pointer to the value if we do
Sterofin 2:06c63d567719 254 */
Sterofin 2:06c63d567719 255 void* getItem(HashTable* hashTable, unsigned int key) {
Sterofin 2:06c63d567719 256 HashTableEntry * hp = findItem(hashTable,key); //finds the item we are looking for
Sterofin 2:06c63d567719 257 if(!hp) return NULL; //if we look for the item and don't find it, return null
Sterofin 2:06c63d567719 258 return hp->value; //otherwise, return the value of the entry we are looking for
rconnorlawson 0:35660d7952f7 259 }
rconnorlawson 0:35660d7952f7 260
Sterofin 2:06c63d567719 261 /*
Sterofin 2:06c63d567719 262 * removeItem
Sterofin 2:06c63d567719 263 *
Sterofin 2:06c63d567719 264 * This function deletes entries within a hash table, but preserves the value of the deleted entry
Sterofin 2:06c63d567719 265 *
Sterofin 2:06c63d567719 266 *@param hashTable The hash table to look in
Sterofin 2:06c63d567719 267 *@param key The key of the entry we want to remove
Sterofin 2:06c63d567719 268 *@return NULL if we don't find it, a pointer to the value if we do
Sterofin 2:06c63d567719 269 */
Sterofin 2:06c63d567719 270 void* removeItem(HashTable* hashTable, unsigned int key) {
Sterofin 2:06c63d567719 271 unsigned int bucket = (hashTable->hash)(key); //Find which bucket our entry is in
Sterofin 2:06c63d567719 272
Sterofin 2:06c63d567719 273 HashTableEntry* this_entry= hashTable->buckets[bucket];
Sterofin 2:06c63d567719 274 HashTableEntry* tmp;
Sterofin 2:06c63d567719 275
Sterofin 2:06c63d567719 276 //If this entry doesn't exist, return NULL
Sterofin 2:06c63d567719 277 if(!this_entry) return NULL;
rconnorlawson 0:35660d7952f7 278
Sterofin 2:06c63d567719 279 //If this entry is the first entry, return value of entry
Sterofin 2:06c63d567719 280 //and make the head point to the next entry
Sterofin 2:06c63d567719 281 if(this_entry->key == key){
Sterofin 2:06c63d567719 282 void* val = this_entry->value; //store current entry value
Sterofin 2:06c63d567719 283 hashTable->buckets[bucket] = this_entry->next; //head points to next entry in list
Sterofin 2:06c63d567719 284 free(this_entry); //deallocate entry
Sterofin 2:06c63d567719 285 return val; //return current value
Sterofin 2:06c63d567719 286 }
Sterofin 2:06c63d567719 287
Sterofin 2:06c63d567719 288 //Destroys entries in the middle of lists by iterating through the list starting
Sterofin 2:06c63d567719 289 //at the head and only stopping when it sees that the next-next value is what we are looking for.
Sterofin 2:06c63d567719 290 //Then it deletes the entry from the list and stitches up the pointers pointing to and from the
Sterofin 2:06c63d567719 291 //entry we just deleted. This function will preserve and return the value of the destroyed entry, however
Sterofin 2:06c63d567719 292 while(this_entry->next){
Sterofin 2:06c63d567719 293 if(this_entry->next->key == key){
Sterofin 2:06c63d567719 294 tmp = this_entry->next;//temp value to store our target
Sterofin 2:06c63d567719 295 void* val = this_entry->next->value; //preserves target's value
Sterofin 2:06c63d567719 296 this_entry->next = this_entry->next->next; //stitches up pointers
Sterofin 2:06c63d567719 297 free(tmp); //destroy temp/target entry
Sterofin 2:06c63d567719 298 return val; //if not what we were looking for, continue iterating through our list
Sterofin 2:06c63d567719 299 }
Sterofin 2:06c63d567719 300 this_entry = this_entry->next;
Sterofin 2:06c63d567719 301 }
Sterofin 2:06c63d567719 302 return NULL;
rconnorlawson 0:35660d7952f7 303 }
rconnorlawson 0:35660d7952f7 304
Sterofin 2:06c63d567719 305 /*
Sterofin 2:06c63d567719 306 * deleteItem
Sterofin 2:06c63d567719 307 *
Sterofin 2:06c63d567719 308 * This function deletes entries within a hash table
Sterofin 2:06c63d567719 309 *
Sterofin 2:06c63d567719 310 *@param hashTable The hash table to look in
Sterofin 2:06c63d567719 311 *@param key The key of the entry we want to remove
Sterofin 2:06c63d567719 312 */
Sterofin 2:06c63d567719 313 void deleteItem(HashTable* hashTable, unsigned int key) {
Sterofin 2:06c63d567719 314 unsigned int bucket = (hashTable->hash)(key); //Find which bucket our entry is in
rconnorlawson 0:35660d7952f7 315
Sterofin 2:06c63d567719 316 HashTableEntry* this_entry= hashTable->buckets[bucket];
Sterofin 2:06c63d567719 317 HashTableEntry* tmp;
Sterofin 2:06c63d567719 318
Sterofin 2:06c63d567719 319 //If this entry doesn't exist, return NULL
Sterofin 2:06c63d567719 320 if(!this_entry) return;
rconnorlawson 0:35660d7952f7 321
Sterofin 2:06c63d567719 322 //If this entry is the first entry, return value of entry
Sterofin 2:06c63d567719 323 //and make the head point to the next entry
Sterofin 2:06c63d567719 324 if(this_entry->key == key){
Sterofin 2:06c63d567719 325 hashTable->buckets[bucket] = this_entry->next; //head points to next entry in list
Sterofin 2:06c63d567719 326 free(this_entry->value); //free the value of the entry
Sterofin 2:06c63d567719 327 free(this_entry); //free the entry itself
Sterofin 2:06c63d567719 328 return;
Sterofin 2:06c63d567719 329 }
rconnorlawson 0:35660d7952f7 330
Sterofin 2:06c63d567719 331 //Destroys entries in the middle of lists by iterating through the list starting
Sterofin 2:06c63d567719 332 //at the head and only stopping when it sees that the next-next value is what we are looking for.
Sterofin 2:06c63d567719 333 //Then it deletes the entry from the list and stitches up the pointers pointing to and from the
Sterofin 2:06c63d567719 334 //entry we just deleted.
Sterofin 2:06c63d567719 335 while(this_entry->next){
Sterofin 2:06c63d567719 336 if(this_entry->next->key == key){
Sterofin 2:06c63d567719 337 tmp = this_entry->next; //temp value to store our target
Sterofin 2:06c63d567719 338 free(this_entry->next->value); //destroy the value of the taget entry
Sterofin 2:06c63d567719 339 this_entry->next = this_entry->next->next; //stitches up pointers
Sterofin 2:06c63d567719 340 free(tmp); //destroy temp/target entry
Sterofin 2:06c63d567719 341 return;
Sterofin 2:06c63d567719 342 }
Sterofin 2:06c63d567719 343 this_entry = this_entry->next; //if not what we were looking for, continue iterating through our list
Sterofin 2:06c63d567719 344 }
Sterofin 2:06c63d567719 345 return;
Sterofin 2:06c63d567719 346 }