hash_table.h

00001 //=================================================================
00002 // Copyright 2020 Georgia Tech.  All rights reserved.
00003 // The materials provided by the instructor in this course are for
00004 // the use of the students currently enrolled in the course.
00005 // Copyrighted course materials may not be further disseminated.
00006 // This file must not be made publicly available anywhere.
00007 //=================================================================
00008 
00009 /****************************************************************************
00010  * Include guards
00011  *
00012  * By using a preprecessor include guard like this one (along with the #endif
00013  * at the bottom of the file), we can guarantee that the public interface for
00014  * this module is only included once in each compilation unit. This prevents
00015  * transitive dependencies from mistakenly including headers many times, and
00016  * can also prevent infinite #include loops due to circular dependencies.
00017  ***************************************************************************/
00018 #ifndef HASHTABLE_H
00019 #define HASHTABLE_H
00020 
00021 /****************************************************************************
00022  * Forward Declarations
00023  *
00024  * These declarations are for interface types that are private to the module,
00025  * but are needed for external interfaces. Without a definition, the compiler
00026  * (and therefore the user) does not have access to information about the
00027  * member variables, and so the members cannot be used directly from modules
00028  * that include this header. However, we do know that these structures are
00029  * valid, and we can use pointers to them. This technique allows hiding the
00030  * implementation details of the hash table module behind a clean public
00031  * interface.
00032  ***************************************************************************/
00033  /**
00034   * This defines a type that is a pointer to a function which takes
00035   * an unsigned int argument and returns an unsigned int value.
00036   * The name of the type is "HashFunction".
00037   */
00038 typedef unsigned int (*HashFunction)(unsigned int key);
00039 
00040 /**
00041  * This defines a type that is a _HashTable struct. The definition for
00042  * _HashTable is implemented in hash_table.c.
00043  *
00044  * In other words, "HashTable" is an alternative name for "struct _HashTable".
00045  * "HashTable" can be used to create a new struct variable.
00046  */
00047 typedef struct _HashTable HashTable;
00048 
00049 /**
00050  * This defines a type that is a _HashTableEntry struct. The definition for
00051  * _HashTableEntry is implemented in hash_table.c.
00052  *
00053  * In other words, "HashTableEntry" is an alternative name for "struct _HashTableEntry".
00054  * "HashTableEntry" can be used to create a new struct variable.
00055  */
00056 typedef struct _HashTableEntry HashTableEntry;
00057 
00058 /**
00059  * createHashTable
00060  *
00061  * Creates a hash table by allocating memory for it on the heap. Initialize num_buckets
00062  * and hash based on function arguments. Allocate memory for buckets as an array of
00063  * pointers to HashTableEntry objects based on the number of buckets available.
00064  * Each bucket contains a singly linked list, whose nodes are HashTableEntry objects.
00065  *
00066  * @param myHashFunc The pointer to the custom hash function.
00067  * @param numBuckets The number of buckets available in the hash table.
00068  * @return a pointer to the new hash table
00069  */
00070 HashTable* createHashTable(HashFunction myHashFunc, unsigned int numBuckets);
00071 
00072 /**
00073  * destroyHashTable
00074  *
00075  * Destroy the hash table. The nodes (HashTableEntry objects) of singly linked
00076  * list, the values stored on the linked list, the buckets, and the hashtable
00077  * itself are freed from the heap. In other words, free all the allocated memory
00078  * on heap that is associated with heap, including the values that users store in
00079  * the hash table.
00080  *
00081  * @param myHashTable The pointer to the hash table.
00082  *
00083  */
00084 void destroyHashTable(HashTable* myHashTable);
00085 
00086 /**
00087  * insertItem
00088  *
00089  * Insert the value into the hash table based on the key.
00090  * In other words, create a new hash table entry and add it to a specific bucket.
00091  *
00092  * @param myHashTable The pointer to the hash table.
00093  * @param key The key that corresponds to the value.
00094  * @param value The value to be stored in the hash table.
00095  * @return old value if it is overwritten, or NULL if not replaced
00096  */
00097 void* insertItem(HashTable* myHashTable, unsigned int key, void* value);
00098 
00099 /**
00100  * getItem
00101  *
00102  * Get the value that corresponds to the key in the hash table.
00103  *
00104  * @param myHashTable The pointer to the hash table.
00105  * @param key The key that corresponds to the item.
00106  * @return the value corresponding to the key, or NULL if the key is not present
00107  */
00108 void* getItem(HashTable* myHashTable, unsigned int key);
00109 
00110 /**
00111  * removeItem
00112  *
00113  * Remove the item in hash table based on the key and return the value stored in it.
00114  * In other words, return the value and free the hash table entry from heap.
00115  *
00116  * @param myHashTable The pointer to the hash table.
00117  * @param key The key that corresponds to the item.
00118  * @return the pointer of the value corresponding to the key, or NULL if the key is not present
00119  */
00120 void* removeItem(HashTable* myHashTable, unsigned int key);
00121 
00122 /**
00123  * deleteItem
00124  *
00125  * Delete the item in the hash table based on the key. In other words, free the
00126  * value stored in the hash table entry and the hash table entry itself from
00127  * the heap.
00128  *
00129  * @param myHashTable The pointer to the hash table.
00130  * @param key The key that corresponds to the item.
00131  *
00132  */
00133 void deleteItem(HashTable* myHashTable, unsigned int key);
00134 
00135 #endif
00136