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?
User | Revision | Line number | New 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 |