hash_table.h

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