![](/media/cache/img/default_profile.jpg.50x50_q85.jpg)
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?
User | Revision | Line number | New 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 |