Cong Vu / Mbed 2 deprecated Project2_cvu31

SNAKE GAME

Dependencies:   mbed wave_player 4DGL-uLCD-SE MMA8452

hash_table.h@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 // Copyright 2020 Georgia Tech. All rights reserved.
congvu 0:24041b847eb5 3 // The materials provided by the instructor in this course are for
congvu 0:24041b847eb5 4 // the use of the students currently enrolled in the course.
congvu 0:24041b847eb5 5 // Copyrighted course materials may not be further disseminated.
congvu 0:24041b847eb5 6 // This file must not be made publicly available anywhere.
congvu 0:24041b847eb5 7 //=================================================================
congvu 0:24041b847eb5 8
congvu 0:24041b847eb5 9 /****************************************************************************
congvu 0:24041b847eb5 10 * Include guards
congvu 0:24041b847eb5 11 *
congvu 0:24041b847eb5 12 * By using a preprecessor include guard like this one (along with the #endif
congvu 0:24041b847eb5 13 * at the bottom of the file), we can guarantee that the public interface for
congvu 0:24041b847eb5 14 * this module is only included once in each compilation unit. This prevents
congvu 0:24041b847eb5 15 * transitive dependencies from mistakenly including headers many times, and
congvu 0:24041b847eb5 16 * can also prevent infinite #include loops due to circular dependencies.
congvu 0:24041b847eb5 17 ***************************************************************************/
congvu 0:24041b847eb5 18 #ifndef HASHTABLE_H
congvu 0:24041b847eb5 19 #define HASHTABLE_H
congvu 0:24041b847eb5 20
congvu 0:24041b847eb5 21 /****************************************************************************
congvu 0:24041b847eb5 22 * Forward Declarations
congvu 0:24041b847eb5 23 *
congvu 0:24041b847eb5 24 * These declarations are for interface types that are private to the module,
congvu 0:24041b847eb5 25 * but are needed for external interfaces. Without a definition, the compiler
congvu 0:24041b847eb5 26 * (and therefore the user) does not have access to information about the
congvu 0:24041b847eb5 27 * member variables, and so the members cannot be used directly from modules
congvu 0:24041b847eb5 28 * that include this header. However, we do know that these structures are
congvu 0:24041b847eb5 29 * valid, and we can use pointers to them. This technique allows hiding the
congvu 0:24041b847eb5 30 * implementation details of the hash table module behind a clean public
congvu 0:24041b847eb5 31 * interface.
congvu 0:24041b847eb5 32 ***************************************************************************/
congvu 0:24041b847eb5 33 /**
congvu 0:24041b847eb5 34 * This defines a type that is a pointer to a function which takes
congvu 0:24041b847eb5 35 * an unsigned int argument and returns an unsigned int value.
congvu 0:24041b847eb5 36 * The name of the type is "HashFunction".
congvu 0:24041b847eb5 37 */
congvu 0:24041b847eb5 38 typedef unsigned int (*HashFunction)(unsigned int key);
congvu 0:24041b847eb5 39
congvu 0:24041b847eb5 40 /**
congvu 0:24041b847eb5 41 * This defines a type that is a _HashTable struct. The definition for
congvu 0:24041b847eb5 42 * _HashTable is implemented in hash_table.c.
congvu 0:24041b847eb5 43 *
congvu 0:24041b847eb5 44 * In other words, "HashTable" is an alternative name for "struct _HashTable".
congvu 0:24041b847eb5 45 * "HashTable" can be used to create a new struct variable.
congvu 0:24041b847eb5 46 */
congvu 0:24041b847eb5 47 typedef struct _HashTable HashTable;
congvu 0:24041b847eb5 48
congvu 0:24041b847eb5 49 /**
congvu 0:24041b847eb5 50 * This defines a type that is a _HashTableEntry struct. The definition for
congvu 0:24041b847eb5 51 * _HashTableEntry is implemented in hash_table.c.
congvu 0:24041b847eb5 52 *
congvu 0:24041b847eb5 53 * In other words, "HashTableEntry" is an alternative name for "struct _HashTableEntry".
congvu 0:24041b847eb5 54 * "HashTableEntry" can be used to create a new struct variable.
congvu 0:24041b847eb5 55 */
congvu 0:24041b847eb5 56 typedef struct _HashTableEntry HashTableEntry;
congvu 0:24041b847eb5 57
congvu 0:24041b847eb5 58 /**
congvu 0:24041b847eb5 59 * createHashTable
congvu 0:24041b847eb5 60 *
congvu 0:24041b847eb5 61 * Creates a hash table by allocating memory for it on the heap. Initialize num_buckets
congvu 0:24041b847eb5 62 * and hash based on function arguments. Allocate memory for buckets as an array of
congvu 0:24041b847eb5 63 * pointers to HashTableEntry objects based on the number of buckets available.
congvu 0:24041b847eb5 64 * Each bucket contains a singly linked list, whose nodes are HashTableEntry objects.
congvu 0:24041b847eb5 65 *
congvu 0:24041b847eb5 66 * @param myHashFunc The pointer to the custom hash function.
congvu 0:24041b847eb5 67 * @param numBuckets The number of buckets available in the hash table.
congvu 0:24041b847eb5 68 * @return a pointer to the new hash table
congvu 0:24041b847eb5 69 */
congvu 0:24041b847eb5 70 HashTable* createHashTable(HashFunction myHashFunc, unsigned int numBuckets);
congvu 0:24041b847eb5 71
congvu 0:24041b847eb5 72 /**
congvu 0:24041b847eb5 73 * destroyHashTable
congvu 0:24041b847eb5 74 *
congvu 0:24041b847eb5 75 * Destroy the hash table. The nodes (HashTableEntry objects) of singly linked
congvu 0:24041b847eb5 76 * list, the values stored on the linked list, the buckets, and the hashtable
congvu 0:24041b847eb5 77 * itself are freed from the heap. In other words, free all the allocated memory
congvu 0:24041b847eb5 78 * on heap that is associated with heap, including the values that users store in
congvu 0:24041b847eb5 79 * the hash table.
congvu 0:24041b847eb5 80 *
congvu 0:24041b847eb5 81 * @param myHashTable The pointer to the hash table.
congvu 0:24041b847eb5 82 *
congvu 0:24041b847eb5 83 */
congvu 0:24041b847eb5 84 void destroyHashTable(HashTable* myHashTable);
congvu 0:24041b847eb5 85
congvu 0:24041b847eb5 86 /**
congvu 0:24041b847eb5 87 * insertItem
congvu 0:24041b847eb5 88 *
congvu 0:24041b847eb5 89 * Insert the value into the hash table based on the key.
congvu 0:24041b847eb5 90 * In other words, create a new hash table entry and add it to a specific bucket.
congvu 0:24041b847eb5 91 *
congvu 0:24041b847eb5 92 * @param myHashTable The pointer to the hash table.
congvu 0:24041b847eb5 93 * @param key The key that corresponds to the value.
congvu 0:24041b847eb5 94 * @param value The value to be stored in the hash table.
congvu 0:24041b847eb5 95 * @return old value if it is overwritten, or NULL if not replaced
congvu 0:24041b847eb5 96 */
congvu 0:24041b847eb5 97 void* insertItem(HashTable* myHashTable, unsigned int key, void* value);
congvu 0:24041b847eb5 98
congvu 0:24041b847eb5 99 /**
congvu 0:24041b847eb5 100 * getItem
congvu 0:24041b847eb5 101 *
congvu 0:24041b847eb5 102 * Get the value that corresponds to the key in the hash table.
congvu 0:24041b847eb5 103 *
congvu 0:24041b847eb5 104 * @param myHashTable The pointer to the hash table.
congvu 0:24041b847eb5 105 * @param key The key that corresponds to the item.
congvu 0:24041b847eb5 106 * @return the value corresponding to the key, or NULL if the key is not present
congvu 0:24041b847eb5 107 */
congvu 0:24041b847eb5 108 void* getItem(HashTable* myHashTable, unsigned int key);
congvu 0:24041b847eb5 109
congvu 0:24041b847eb5 110 /**
congvu 0:24041b847eb5 111 * removeItem
congvu 0:24041b847eb5 112 *
congvu 0:24041b847eb5 113 * Remove the item in hash table based on the key and return the value stored in it.
congvu 0:24041b847eb5 114 * In other words, return the value and free the hash table entry from heap.
congvu 0:24041b847eb5 115 *
congvu 0:24041b847eb5 116 * @param myHashTable The pointer to the hash table.
congvu 0:24041b847eb5 117 * @param key The key that corresponds to the item.
congvu 0:24041b847eb5 118 * @return the pointer of the value corresponding to the key, or NULL if the key is not present
congvu 0:24041b847eb5 119 */
congvu 0:24041b847eb5 120 void* removeItem(HashTable* myHashTable, unsigned int key);
congvu 0:24041b847eb5 121
congvu 0:24041b847eb5 122 /**
congvu 0:24041b847eb5 123 * deleteItem
congvu 0:24041b847eb5 124 *
congvu 0:24041b847eb5 125 * Delete the item in the hash table based on the key. In other words, free the
congvu 0:24041b847eb5 126 * value stored in the hash table entry and the hash table entry itself from
congvu 0:24041b847eb5 127 * the heap.
congvu 0:24041b847eb5 128 *
congvu 0:24041b847eb5 129 * @param myHashTable The pointer to the hash table.
congvu 0:24041b847eb5 130 * @param key The key that corresponds to the item.
congvu 0:24041b847eb5 131 *
congvu 0:24041b847eb5 132 */
congvu 0:24041b847eb5 133 void deleteItem(HashTable* myHashTable, unsigned int key);
congvu 0:24041b847eb5 134
congvu 0:24041b847eb5 135 #endif
congvu 0:24041b847eb5 136