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

project for 2035

Dependencies:   mbed wave_player 4DGL-uLCD-SE MMA8452

hash_table.cpp@2:4947d6a82971, 2020-10-23 (annotated)

Committer:
DCchico
Date:
Fri Oct 23 16:30:18 2020 -0400
Revision:
2:4947d6a82971
Parent:
1:10330bce85cb
Child:
3:9dde875cd65c
shell

Who changed what in which revision?

UserRevisionLine numberNew contents of line
DCchico 2:4947d6a82971 1 // Copyright 2020 Georgia Tech. All rights reserved.
DCchico 2:4947d6a82971 2 // The materials provided by the instructor in this course are for
DCchico 2:4947d6a82971 3 // the use of the students currently enrolled in the course.
DCchico 2:4947d6a82971 4 // Copyrighted course materials may not be further disseminated.
DCchico 2:4947d6a82971 5 // This file must not be made publicly available anywhere.
DCchico 1:10330bce85cb 6 /*
DCchico 1:10330bce85cb 7 Student Name:
DCchico 1:10330bce85cb 8 Date:
DCchico 1:10330bce85cb 9
DCchico 1:10330bce85cb 10 =======================
DCchico 1:10330bce85cb 11 ECE 2035 Project 2-1:
DCchico 1:10330bce85cb 12 =======================
DCchico 1:10330bce85cb 13 This file provides definition for the structs and functions declared in the
DCchico 1:10330bce85cb 14 header file. It also contains helper functions that are not accessible from
DCchico 1:10330bce85cb 15 outside of the file.
DCchico 1:10330bce85cb 16
DCchico 1:10330bce85cb 17 FOR FULL CREDIT, BE SURE TO TRY MULTIPLE TEST CASES and DOCUMENT YOUR CODE.
DCchico 1:10330bce85cb 18
DCchico 1:10330bce85cb 19 ===================================
DCchico 1:10330bce85cb 20 Naming conventions in this file:
DCchico 1:10330bce85cb 21 ===================================
DCchico 1:10330bce85cb 22 1. All struct names use camel case where the first letter is capitalized.
DCchico 1:10330bce85cb 23 e.g. "HashTable", or "HashTableEntry"
DCchico 1:10330bce85cb 24
DCchico 1:10330bce85cb 25 2. Variable names with a preceding underscore "_" will not be called directly.
DCchico 1:10330bce85cb 26 e.g. "_HashTable", "_HashTableEntry"
DCchico 1:10330bce85cb 27
DCchico 1:10330bce85cb 28 Recall that in C, we have to type "struct" together with the name of the struct
DCchico 1:10330bce85cb 29 in order to initialize a new variable. To avoid this, in hash_table.h
DCchico 1:10330bce85cb 30 we use typedef to provide new "nicknames" for "struct _HashTable" and
DCchico 1:10330bce85cb 31 "struct _HashTableEntry". As a result, we can create new struct variables
DCchico 1:10330bce85cb 32 by just using:
DCchico 1:10330bce85cb 33 - "HashTable myNewTable;"
DCchico 1:10330bce85cb 34 or
DCchico 1:10330bce85cb 35 - "HashTableEntry myNewHashTableEntry;"
DCchico 1:10330bce85cb 36
DCchico 1:10330bce85cb 37 The preceding underscore "_" simply provides a distinction between the names
DCchico 1:10330bce85cb 38 of the actual struct defition and the "nicknames" that we use to initialize
DCchico 1:10330bce85cb 39 new structs.
DCchico 1:10330bce85cb 40 [See Hidden Definitions section for more information.]
DCchico 1:10330bce85cb 41
DCchico 1:10330bce85cb 42 3. Functions, their local variables and arguments are named with camel case, where
DCchico 1:10330bce85cb 43 the first letter is lower-case.
DCchico 1:10330bce85cb 44 e.g. "createHashTable" is a function. One of its arguments is "numBuckets".
DCchico 1:10330bce85cb 45 It also has a local variable called "newTable".
DCchico 1:10330bce85cb 46
DCchico 1:10330bce85cb 47 4. The name of a struct member is divided by using underscores "_". This serves
DCchico 1:10330bce85cb 48 as a distinction between function local variables and struct members.
DCchico 1:10330bce85cb 49 e.g. "num_buckets" is a member of "HashTable".
DCchico 1:10330bce85cb 50
DCchico 1:10330bce85cb 51 */
DCchico 1:10330bce85cb 52
DCchico 1:10330bce85cb 53 /****************************************************************************
DCchico 1:10330bce85cb 54 * Include the Public Interface
DCchico 1:10330bce85cb 55 *
DCchico 1:10330bce85cb 56 * By including the public interface at the top of the file, the compiler can
DCchico 1:10330bce85cb 57 * enforce that the function declarations in the the header are not in
DCchico 1:10330bce85cb 58 * conflict with the definitions in the file. This is not a guarantee of
DCchico 1:10330bce85cb 59 * correctness, but it is better than nothing!
DCchico 1:10330bce85cb 60 ***************************************************************************/
DCchico 1:10330bce85cb 61 #include "hash_table.h"
DCchico 1:10330bce85cb 62
DCchico 1:10330bce85cb 63
DCchico 1:10330bce85cb 64 /****************************************************************************
DCchico 1:10330bce85cb 65 * Include other private dependencies
DCchico 1:10330bce85cb 66 *
DCchico 1:10330bce85cb 67 * These other modules are used in the implementation of the hash table module,
DCchico 1:10330bce85cb 68 * but are not required by users of the hash table.
DCchico 1:10330bce85cb 69 ***************************************************************************/
DCchico 1:10330bce85cb 70 #include <stdlib.h> // For malloc and free
DCchico 1:10330bce85cb 71 #include <stdio.h> // For printf
DCchico 1:10330bce85cb 72
DCchico 1:10330bce85cb 73
DCchico 1:10330bce85cb 74 /****************************************************************************
DCchico 1:10330bce85cb 75 * Hidden Definitions
DCchico 1:10330bce85cb 76 *
DCchico 1:10330bce85cb 77 * These definitions are not available outside of this file. However, because
DCchico 1:10330bce85cb 78 * the are forward declared in hash_table.h, the type names are
DCchico 1:10330bce85cb 79 * available everywhere and user code can hold pointers to these structs.
DCchico 1:10330bce85cb 80 ***************************************************************************/
DCchico 1:10330bce85cb 81 /**
DCchico 1:10330bce85cb 82 * This structure represents an a hash table.
DCchico 1:10330bce85cb 83 * Use "HashTable" instead when you are creating a new variable. [See top comments]
DCchico 1:10330bce85cb 84 */
DCchico 1:10330bce85cb 85 struct _HashTable {
DCchico 1:10330bce85cb 86 /** The array of pointers to the head of a singly linked list, whose nodes
DCchico 1:10330bce85cb 87 are HashTableEntry objects */
DCchico 1:10330bce85cb 88 HashTableEntry** buckets;
DCchico 1:10330bce85cb 89
DCchico 1:10330bce85cb 90 /** The hash function pointer */
DCchico 1:10330bce85cb 91 HashFunction hash;
DCchico 1:10330bce85cb 92
DCchico 1:10330bce85cb 93 /** The number of buckets in the hash table */
DCchico 1:10330bce85cb 94 unsigned int num_buckets;
DCchico 1:10330bce85cb 95 };
DCchico 1:10330bce85cb 96
DCchico 1:10330bce85cb 97 /**
DCchico 1:10330bce85cb 98 * This structure represents a hash table entry.
DCchico 1:10330bce85cb 99 * Use "HashTableEntry" instead when you are creating a new variable. [See top comments]
DCchico 1:10330bce85cb 100 */
DCchico 1:10330bce85cb 101 struct _HashTableEntry {
DCchico 1:10330bce85cb 102 /** The key for the hash table entry */
DCchico 1:10330bce85cb 103 unsigned int key;
DCchico 1:10330bce85cb 104
DCchico 1:10330bce85cb 105 /** The value associated with this hash table entry */
DCchico 1:10330bce85cb 106 void* value;
DCchico 1:10330bce85cb 107
DCchico 1:10330bce85cb 108 /**
DCchico 1:10330bce85cb 109 * A pointer pointing to the next hash table entry
DCchico 1:10330bce85cb 110 * NULL means there is no next entry (i.e. this is the tail)
DCchico 1:10330bce85cb 111 */
DCchico 1:10330bce85cb 112 HashTableEntry* next;
DCchico 1:10330bce85cb 113 };
DCchico 1:10330bce85cb 114
DCchico 1:10330bce85cb 115
DCchico 1:10330bce85cb 116 /****************************************************************************
DCchico 1:10330bce85cb 117 * Private Functions
DCchico 1:10330bce85cb 118 *
DCchico 1:10330bce85cb 119 * These functions are not available outside of this file, since they are not
DCchico 1:10330bce85cb 120 * declared in hash_table.h.
DCchico 1:10330bce85cb 121 ***************************************************************************/
DCchico 1:10330bce85cb 122 /**
DCchico 1:10330bce85cb 123 * createHashTableEntry
DCchico 1:10330bce85cb 124 *
DCchico 1:10330bce85cb 125 * Helper function that creates a hash table entry by allocating memory for it on
DCchico 1:10330bce85cb 126 * the heap. It initializes the entry with key and value, initialize pointer to
DCchico 1:10330bce85cb 127 * the next entry as NULL, and return the pointer to this hash table entry.
DCchico 1:10330bce85cb 128 *
DCchico 1:10330bce85cb 129 * @param key The key corresponds to the hash table entry
DCchico 1:10330bce85cb 130 * @param value The value stored in the hash table entry
DCchico 1:10330bce85cb 131 * @return The pointer to the hash table entry
DCchico 1:10330bce85cb 132 */
DCchico 1:10330bce85cb 133 static HashTableEntry* createHashTableEntry(unsigned int key, void* value) {
DCchico 1:10330bce85cb 134
DCchico 1:10330bce85cb 135 }
DCchico 1:10330bce85cb 136
DCchico 1:10330bce85cb 137 /**
DCchico 1:10330bce85cb 138 * findItem
DCchico 1:10330bce85cb 139 *
DCchico 1:10330bce85cb 140 * Helper function that checks whether there exists the hash table entry that
DCchico 1:10330bce85cb 141 * contains a specific key.
DCchico 1:10330bce85cb 142 *
DCchico 1:10330bce85cb 143 * @param hashTable The pointer to the hash table.
DCchico 1:10330bce85cb 144 * @param key The key corresponds to the hash table entry
DCchico 1:10330bce85cb 145 * @return The pointer to the hash table entry, or NULL if key does not exist
DCchico 1:10330bce85cb 146 */
DCchico 1:10330bce85cb 147 static HashTableEntry* findItem(HashTable* hashTable, unsigned int key) {
DCchico 1:10330bce85cb 148
DCchico 1:10330bce85cb 149 }
DCchico 1:10330bce85cb 150
DCchico 1:10330bce85cb 151 /****************************************************************************
DCchico 1:10330bce85cb 152 * Public Interface Functions
DCchico 1:10330bce85cb 153 *
DCchico 1:10330bce85cb 154 * These functions implement the public interface as specified in the header
DCchico 1:10330bce85cb 155 * file, and make use of the private functions and hidden definitions in the
DCchico 1:10330bce85cb 156 * above sections.
DCchico 1:10330bce85cb 157 ****************************************************************************/
DCchico 1:10330bce85cb 158 // The createHashTable is provided for you as a starting point.
DCchico 1:10330bce85cb 159 HashTable* createHashTable(HashFunction hashFunction, unsigned int numBuckets) {
DCchico 1:10330bce85cb 160 // The hash table has to contain at least one bucket. Exit gracefully if
DCchico 1:10330bce85cb 161 // this condition is not met.
DCchico 1:10330bce85cb 162 if (numBuckets==0) {
DCchico 1:10330bce85cb 163 printf("Hash table has to contain at least 1 bucket...\n");
DCchico 1:10330bce85cb 164 exit(1);
DCchico 1:10330bce85cb 165 }
DCchico 1:10330bce85cb 166
DCchico 1:10330bce85cb 167 // Allocate memory for the new HashTable struct on heap.
DCchico 1:10330bce85cb 168 HashTable* newTable = (HashTable*)malloc(sizeof(HashTable));
DCchico 1:10330bce85cb 169
DCchico 1:10330bce85cb 170 // Initialize the components of the new HashTable struct.
DCchico 1:10330bce85cb 171 newTable->hash = hashFunction;
DCchico 1:10330bce85cb 172 newTable->num_buckets = numBuckets;
DCchico 1:10330bce85cb 173 newTable->buckets = (HashTableEntry**)malloc(numBuckets*sizeof(HashTableEntry*));
DCchico 1:10330bce85cb 174
DCchico 1:10330bce85cb 175 // As the new buckets are empty, init each bucket as NULL.
DCchico 1:10330bce85cb 176 unsigned int i;
DCchico 1:10330bce85cb 177 for (i=0; i<numBuckets; ++i) {
DCchico 1:10330bce85cb 178 newTable->buckets[i] = NULL;
DCchico 1:10330bce85cb 179 }
DCchico 1:10330bce85cb 180
DCchico 1:10330bce85cb 181 // Return the new HashTable struct.
DCchico 1:10330bce85cb 182 return newTable;
DCchico 1:10330bce85cb 183 }
DCchico 1:10330bce85cb 184
DCchico 1:10330bce85cb 185 void destroyHashTable(HashTable* hashTable) {
DCchico 1:10330bce85cb 186
DCchico 1:10330bce85cb 187 }
DCchico 1:10330bce85cb 188
DCchico 1:10330bce85cb 189 void* insertItem(HashTable* hashTable, unsigned int key, void* value) {
DCchico 1:10330bce85cb 190 }
DCchico 1:10330bce85cb 191
DCchico 1:10330bce85cb 192 void* getItem(HashTable* hashTable, unsigned int key) {
DCchico 1:10330bce85cb 193
DCchico 1:10330bce85cb 194 }
DCchico 1:10330bce85cb 195
DCchico 1:10330bce85cb 196 void* removeItem(HashTable* hashTable, unsigned int key) {
DCchico 1:10330bce85cb 197
DCchico 1:10330bce85cb 198 }
DCchico 1:10330bce85cb 199
DCchico 1:10330bce85cb 200 void deleteItem(HashTable* hashTable, unsigned int key) {
DCchico 1:10330bce85cb 201
DCchico 1:10330bce85cb 202 }