Harris Barton / Mbed 2 deprecated P2-2_HarrisBarton_SnakeGame

P2-2 Harris Barton

Dependencies:   mbed wave_player 4DGL-uLCD-SE MMA8452

hash_table.h@3:e2fb359d6545, 2020-11-25 (annotated)

Committer:
hbarton7
Date:
Wed Nov 25 01:17:39 2020 +0000
Revision:
3:e2fb359d6545
Parent:
2:4947d6a82971 
P2-2 Harris Barton;

Who changed what in which revision?

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