Hung Nguyen / Mbed 2 deprecated snake-game

tao lao

Dependencies:   mbed wave_player 4DGL-uLCD-SE MMA8452

hash_table.h@3:33bf11645fe1, 2020-11-24 (annotated)

Committer:
hnguyen403
Date:
Tue Nov 24 05:05:10 2020 +0000
Revision:
3:33bf11645fe1
Parent:
2:4947d6a82971 
tao lao;

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