Cong Vu / Mbed 2 deprecated Project2_cvu31

SNAKE GAME

Dependencies:   mbed wave_player 4DGL-uLCD-SE MMA8452

hash_table.cpp@0:24041b847eb5, 2020-11-25 (annotated)

Committer:
congvu
Date:
Wed Nov 25 04:25:25 2020 +0000
Revision:
0:24041b847eb5
ECE2035 SNAKE GAME;

Who changed what in which revision?

UserRevisionLine numberNew contents of line
congvu 0:24041b847eb5 1 /****************************************************************************
congvu 0:24041b847eb5 2 * Include the Public Interface
congvu 0:24041b847eb5 3 *
congvu 0:24041b847eb5 4 * By including the public interface at the top of the file, the compiler can
congvu 0:24041b847eb5 5 * enforce that the function declarations in the the header are not in
congvu 0:24041b847eb5 6 * conflict with the definitions in the file. This is not a guarantee of
congvu 0:24041b847eb5 7 * correctness, but it is better than nothing!
congvu 0:24041b847eb5 8 ***************************************************************************/
congvu 0:24041b847eb5 9 #include "hash_table.h"
congvu 0:24041b847eb5 10
congvu 0:24041b847eb5 11
congvu 0:24041b847eb5 12 /****************************************************************************
congvu 0:24041b847eb5 13 * Include other private dependencies
congvu 0:24041b847eb5 14 *
congvu 0:24041b847eb5 15 * These other modules are used in the implementation of the hash table module,
congvu 0:24041b847eb5 16 * but are not required by users of the hash table.
congvu 0:24041b847eb5 17 ***************************************************************************/
congvu 0:24041b847eb5 18 #include <stdlib.h> // For malloc and free
congvu 0:24041b847eb5 19 #include <stdio.h> // For printf
congvu 0:24041b847eb5 20
congvu 0:24041b847eb5 21
congvu 0:24041b847eb5 22 /****************************************************************************
congvu 0:24041b847eb5 23 * Hidden Definitions
congvu 0:24041b847eb5 24 *
congvu 0:24041b847eb5 25 * These definitions are not available outside of this file. However, because
congvu 0:24041b847eb5 26 * the are forward declared in hash_table.h, the type names are
congvu 0:24041b847eb5 27 * available everywhere and user code can hold pointers to these structs.
congvu 0:24041b847eb5 28 ***************************************************************************/
congvu 0:24041b847eb5 29 /**
congvu 0:24041b847eb5 30 * This structure represents an a hash table.
congvu 0:24041b847eb5 31 */
congvu 0:24041b847eb5 32 struct _HashTable {
congvu 0:24041b847eb5 33 /** The array of pointers to the head of a singly linked list, whose nodes
congvu 0:24041b847eb5 34 are HashTableEntry objects */
congvu 0:24041b847eb5 35 HashTableEntry** buckets;
congvu 0:24041b847eb5 36
congvu 0:24041b847eb5 37 /** The hash function pointer */
congvu 0:24041b847eb5 38 HashFunction hash;
congvu 0:24041b847eb5 39
congvu 0:24041b847eb5 40 /** The number of buckets in the hash table */
congvu 0:24041b847eb5 41 unsigned int num_buckets;
congvu 0:24041b847eb5 42 };
congvu 0:24041b847eb5 43
congvu 0:24041b847eb5 44 /**
congvu 0:24041b847eb5 45 * This structure represents a hash table entry.
congvu 0:24041b847eb5 46 */
congvu 0:24041b847eb5 47 struct _HashTableEntry {
congvu 0:24041b847eb5 48 /** The key for the hash table entry */
congvu 0:24041b847eb5 49 unsigned int key;
congvu 0:24041b847eb5 50
congvu 0:24041b847eb5 51 /** The value associated with this hash table entry */
congvu 0:24041b847eb5 52 void* value;
congvu 0:24041b847eb5 53
congvu 0:24041b847eb5 54 /**
congvu 0:24041b847eb5 55 * A pointer pointing to the next hash table entry
congvu 0:24041b847eb5 56 * NULL means there is no next entry (i.e. this is the tail)
congvu 0:24041b847eb5 57 */
congvu 0:24041b847eb5 58 HashTableEntry* next;
congvu 0:24041b847eb5 59 };
congvu 0:24041b847eb5 60
congvu 0:24041b847eb5 61
congvu 0:24041b847eb5 62 /****************************************************************************
congvu 0:24041b847eb5 63 * Private Functions
congvu 0:24041b847eb5 64 *
congvu 0:24041b847eb5 65 * These functions are not available outside of this file, since they are not
congvu 0:24041b847eb5 66 * declared in hash_table.h.
congvu 0:24041b847eb5 67 ***************************************************************************/
congvu 0:24041b847eb5 68 /**
congvu 0:24041b847eb5 69 * createHashTableEntry
congvu 0:24041b847eb5 70 *
congvu 0:24041b847eb5 71 * Helper function that creates a hash table entry by allocating memory for it on
congvu 0:24041b847eb5 72 * the heap. It initializes the entry with key and value, initialize pointer to
congvu 0:24041b847eb5 73 * the next entry as NULL, and return the pointer to this hash table entry.
congvu 0:24041b847eb5 74 *
congvu 0:24041b847eb5 75 * @param key The key corresponds to the hash table entry
congvu 0:24041b847eb5 76 * @param value The value stored in the hash table entry
congvu 0:24041b847eb5 77 * @return The pointer to the hash table entry
congvu 0:24041b847eb5 78 */
congvu 0:24041b847eb5 79 static HashTableEntry* createHashTableEntry(unsigned int key, void* value) {
congvu 0:24041b847eb5 80 // Create an initialize a new hash table entry.
congvu 0:24041b847eb5 81 HashTableEntry* newEntry = (HashTableEntry*)malloc(sizeof(HashTableEntry));
congvu 0:24041b847eb5 82 newEntry->key = key;
congvu 0:24041b847eb5 83 newEntry->value = value;
congvu 0:24041b847eb5 84 newEntry->next = NULL;
congvu 0:24041b847eb5 85
congvu 0:24041b847eb5 86 return newEntry;
congvu 0:24041b847eb5 87 }
congvu 0:24041b847eb5 88
congvu 0:24041b847eb5 89 /**
congvu 0:24041b847eb5 90 * findItem
congvu 0:24041b847eb5 91 *
congvu 0:24041b847eb5 92 * Helper function that checks whether there exists the hash table entry that
congvu 0:24041b847eb5 93 * contains a specific key.
congvu 0:24041b847eb5 94 *
congvu 0:24041b847eb5 95 * @param myHashTable The pointer to the hash table.
congvu 0:24041b847eb5 96 * @param key The key corresponds to the hash table entry
congvu 0:24041b847eb5 97 * @return The pointer to the hash table entry, or NULL if key does not exist
congvu 0:24041b847eb5 98 */
congvu 0:24041b847eb5 99 static HashTableEntry* findItem(HashTable* myHashTable, unsigned int key) {
congvu 0:24041b847eb5 100 unsigned int bucketNum = myHashTable->hash(key); // Get the bucket number.
congvu 0:24041b847eb5 101 HashTableEntry* temp = myHashTable->buckets[bucketNum]; // Get the head entry.
congvu 0:24041b847eb5 102
congvu 0:24041b847eb5 103 if (temp == NULL) return NULL; // If there's nothing in the bucket, return NULL.
congvu 0:24041b847eb5 104
congvu 0:24041b847eb5 105 while (temp!=NULL) {
congvu 0:24041b847eb5 106 if (temp->key==key) return temp; // Return the hash table entry if the key is found.
congvu 0:24041b847eb5 107 temp = temp->next; // Otherwise, move to next node.
congvu 0:24041b847eb5 108 }
congvu 0:24041b847eb5 109
congvu 0:24041b847eb5 110 return NULL; // Return NULL if key is not present.
congvu 0:24041b847eb5 111 }
congvu 0:24041b847eb5 112
congvu 0:24041b847eb5 113 /****************************************************************************
congvu 0:24041b847eb5 114 * Public Interface Functions
congvu 0:24041b847eb5 115 *
congvu 0:24041b847eb5 116 * These functions implement the public interface as specified in the header
congvu 0:24041b847eb5 117 * file, and make use of the private functions and hidden definitions in the
congvu 0:24041b847eb5 118 * above sections.
congvu 0:24041b847eb5 119 ****************************************************************************/
congvu 0:24041b847eb5 120 HashTable* createHashTable(HashFunction myHashFunc, unsigned int numBuckets) {
congvu 0:24041b847eb5 121 // The hash table has to contain at least one bucket. Exit gracefully if
congvu 0:24041b847eb5 122 // this condition is not met.
congvu 0:24041b847eb5 123 if (numBuckets==0) {
congvu 0:24041b847eb5 124 printf("Hash table has to contain at least 1 bucket...\n");
congvu 0:24041b847eb5 125 exit(1);
congvu 0:24041b847eb5 126 }
congvu 0:24041b847eb5 127
congvu 0:24041b847eb5 128 // Allocate memory for the new HashTable struct on heap.
congvu 0:24041b847eb5 129 HashTable* newTable = (HashTable*)malloc(sizeof(HashTable));
congvu 0:24041b847eb5 130
congvu 0:24041b847eb5 131 // Initialize the components of the new HashTable struct.
congvu 0:24041b847eb5 132 newTable->hash = myHashFunc;
congvu 0:24041b847eb5 133 newTable->num_buckets = numBuckets;
congvu 0:24041b847eb5 134 newTable->buckets = (HashTableEntry**)malloc(numBuckets*sizeof(HashTableEntry*));
congvu 0:24041b847eb5 135
congvu 0:24041b847eb5 136 // As the new buckets contain indeterminant values, init each bucket as NULL.
congvu 0:24041b847eb5 137 unsigned int i;
congvu 0:24041b847eb5 138 for (i=0; i<numBuckets; ++i) {
congvu 0:24041b847eb5 139 newTable->buckets[i] = NULL;
congvu 0:24041b847eb5 140 }
congvu 0:24041b847eb5 141
congvu 0:24041b847eb5 142 // Return the newly created hash table.
congvu 0:24041b847eb5 143 return newTable;
congvu 0:24041b847eb5 144 }
congvu 0:24041b847eb5 145
congvu 0:24041b847eb5 146 void destroyHashTable(HashTable* myHashTable) {
congvu 0:24041b847eb5 147 unsigned int i;
congvu 0:24041b847eb5 148 HashTableEntry* temp;
congvu 0:24041b847eb5 149 HashTableEntry* next;
congvu 0:24041b847eb5 150
congvu 0:24041b847eb5 151 // Loop through each bucket of the hash table to remove all items.
congvu 0:24041b847eb5 152 for (i=0; i<myHashTable->num_buckets; ++i) {
congvu 0:24041b847eb5 153 temp = myHashTable->buckets[i]; // set temp to be the first entry of the ith bucket
congvu 0:24041b847eb5 154
congvu 0:24041b847eb5 155 // delete all entries
congvu 0:24041b847eb5 156 while (temp != NULL) {
congvu 0:24041b847eb5 157 next = temp->next;
congvu 0:24041b847eb5 158 free(temp->value);
congvu 0:24041b847eb5 159 free(temp);
congvu 0:24041b847eb5 160 temp = next;
congvu 0:24041b847eb5 161 }
congvu 0:24041b847eb5 162 }
congvu 0:24041b847eb5 163
congvu 0:24041b847eb5 164 // free buckets
congvu 0:24041b847eb5 165 free(myHashTable->buckets);
congvu 0:24041b847eb5 166
congvu 0:24041b847eb5 167 // free hash table
congvu 0:24041b847eb5 168 free(myHashTable);
congvu 0:24041b847eb5 169 }
congvu 0:24041b847eb5 170
congvu 0:24041b847eb5 171 void* insertItem(HashTable* myHashTable, unsigned int key, void* value) {
congvu 0:24041b847eb5 172 // First, we want to check if the key is present in the hash table.
congvu 0:24041b847eb5 173 HashTableEntry* temp = findItem(myHashTable, key);
congvu 0:24041b847eb5 174
congvu 0:24041b847eb5 175 if (temp) {
congvu 0:24041b847eb5 176 // The key is present in the hash table.
congvu 0:24041b847eb5 177 void* oldValue = temp->value;
congvu 0:24041b847eb5 178 temp->value = value;
congvu 0:24041b847eb5 179 return oldValue;
congvu 0:24041b847eb5 180 } else {
congvu 0:24041b847eb5 181 // The key is not present in the hash table.
congvu 0:24041b847eb5 182 temp = createHashTableEntry(key, value);
congvu 0:24041b847eb5 183 temp->next = myHashTable->buckets[myHashTable->hash(key)];
congvu 0:24041b847eb5 184 myHashTable->buckets[myHashTable->hash(key)] = temp;
congvu 0:24041b847eb5 185 return NULL; // Return NULL as nothing is overwritten.
congvu 0:24041b847eb5 186 }
congvu 0:24041b847eb5 187 }
congvu 0:24041b847eb5 188
congvu 0:24041b847eb5 189 void* getItem(HashTable* myHashTable, unsigned int key) {
congvu 0:24041b847eb5 190 // First, we want to check if the key is present in the hash table.
congvu 0:24041b847eb5 191 HashTableEntry* temp = findItem(myHashTable, key);
congvu 0:24041b847eb5 192
congvu 0:24041b847eb5 193 if (temp) // if the key exists
congvu 0:24041b847eb5 194 return temp->value;
congvu 0:24041b847eb5 195 else // return NULL if the key does not exist
congvu 0:24041b847eb5 196 return NULL;
congvu 0:24041b847eb5 197 }
congvu 0:24041b847eb5 198
congvu 0:24041b847eb5 199 void* removeItem(HashTable* myHashTable, unsigned int key) {
congvu 0:24041b847eb5 200 // Reference: https://www.geeksforgeeks.org/linked-list-set-3-deleting-node/
congvu 0:24041b847eb5 201 unsigned int bucketNum = myHashTable->hash(key); // get the bucket number
congvu 0:24041b847eb5 202 HashTableEntry* temp = myHashTable->buckets[bucketNum]; // get the head entry
congvu 0:24041b847eb5 203 HashTableEntry* prev;
congvu 0:24041b847eb5 204
congvu 0:24041b847eb5 205 // If head holds the key
congvu 0:24041b847eb5 206 if (temp != NULL && temp->key == key) {
congvu 0:24041b847eb5 207 myHashTable->buckets[bucketNum] = temp->next; // Change head
congvu 0:24041b847eb5 208 void* oldValue = temp->value; // hold the old value
congvu 0:24041b847eb5 209 free(temp);
congvu 0:24041b847eb5 210 return oldValue;
congvu 0:24041b847eb5 211 }
congvu 0:24041b847eb5 212
congvu 0:24041b847eb5 213 // Search for the key to be removed
congvu 0:24041b847eb5 214 while (temp != NULL && temp->key != key) {
congvu 0:24041b847eb5 215 prev = temp;
congvu 0:24041b847eb5 216 temp = temp->next;
congvu 0:24041b847eb5 217 }
congvu 0:24041b847eb5 218
congvu 0:24041b847eb5 219 // If the key is not present in the list
congvu 0:24041b847eb5 220 if (temp == NULL) return NULL;
congvu 0:24041b847eb5 221
congvu 0:24041b847eb5 222 // Unlink the node from list
congvu 0:24041b847eb5 223 prev->next = temp->next;
congvu 0:24041b847eb5 224 void* oldValue = temp->value; // hold the old value
congvu 0:24041b847eb5 225 free(temp);
congvu 0:24041b847eb5 226
congvu 0:24041b847eb5 227 return oldValue;
congvu 0:24041b847eb5 228 }
congvu 0:24041b847eb5 229
congvu 0:24041b847eb5 230 void deleteItem(HashTable* myHashTable, unsigned int key) {
congvu 0:24041b847eb5 231 // remove the entry and free the returned data
congvu 0:24041b847eb5 232 free(removeItem(myHashTable, key));
congvu 0:24041b847eb5 233 }