Harris Barton / Mbed 2 deprecated P2-2_HarrisBarton_SnakeGame

P2-2 Harris Barton

Dependencies:   mbed wave_player 4DGL-uLCD-SE MMA8452

hash_table.h@1:10330bce85cb, 2020-10-23 (annotated)

Committer:
DCchico
Date:
Fri Oct 23 16:18:39 2020 -0400
Revision:
1:10330bce85cb
Child:
2:4947d6a82971
shell-code

Who changed what in which revision?

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