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