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