Yehowshua Immanuel / Mbed 2 deprecated Generic_Platformer

A lightweight game engine for the MBED.

Dependencies:   mbed 4DGL-uLCD-SE MMA8452

hash_table/hash_table.cpp@5:f86f447a295f, 2019-03-16 (annotated)

Committer:
Yehowshua
Date:
Sat Mar 16 05:26:30 2019 +0000
Revision:
5:f86f447a295f
Parent:
2:5645cb2d9316 
now with inputs

Who changed what in which revision?

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