Diff: hash_table/hash_table.cpp

Revision:

2:5645cb2d9316

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/hash_table/hash_table.cpp	Wed Mar 13 09:48:27 2019 -0400
@@ -0,0 +1,233 @@
+/****************************************************************************
+* Include the Public Interface
+*
+* By including the public interface at the top of the file, the compiler can
+* enforce that the function declarations in the the header are not in
+* conflict with the definitions in the file. This is not a guarantee of
+* correctness, but it is better than nothing!
+***************************************************************************/
+#include "hash_table.h"
+
+
+/****************************************************************************
+* Include other private dependencies
+*
+* These other modules are used in the implementation of the hash table module,
+* but are not required by users of the hash table.
+***************************************************************************/
+#include <stdlib.h>   // For malloc and free
+#include <stdio.h>    // For printf
+
+
+/****************************************************************************
+* Hidden Definitions
+*
+* These definitions are not available outside of this file. However, because
+* the are forward declared in hash_table.h, the type names are
+* available everywhere and user code can hold pointers to these structs.
+***************************************************************************/
+/**
+ * This structure represents an a hash table.
+ */
+struct _HashTable {
+  /** The array of pointers to the head of a singly linked list, whose nodes
+      are HashTableEntry objects */
+  HashTableEntry** buckets;
+
+  /** The hash function pointer */
+  HashFunction hash;
+
+  /** The number of buckets in the hash table */
+  unsigned int num_buckets;
+};
+
+/**
+ * This structure represents a hash table entry.
+ */
+struct _HashTableEntry {
+  /** The key for the hash table entry */
+  unsigned int key;
+
+  /** The value associated with this hash table entry */
+  void* value;
+
+  /**
+  * A pointer pointing to the next hash table entry
+  * NULL means there is no next entry (i.e. this is the tail)
+  */
+  HashTableEntry* next;
+};
+
+
+/****************************************************************************
+* Private Functions
+*
+* These functions are not available outside of this file, since they are not
+* declared in hash_table.h.
+***************************************************************************/
+/**
+* createHashTableEntry
+*
+* Helper function that creates a hash table entry by allocating memory for it on
+* the heap. It initializes the entry with key and value, initialize pointer to
+* the next entry as NULL, and return the pointer to this hash table entry.
+*
+* @param key The key corresponds to the hash table entry
+* @param value The value stored in the hash table entry
+* @return The pointer to the hash table entry
+*/
+static HashTableEntry* createHashTableEntry(unsigned int key, void* value) {
+  // Create an initialize a new hash table entry.
+  HashTableEntry* newEntry = (HashTableEntry*)malloc(sizeof(HashTableEntry));
+  newEntry->key = key;
+  newEntry->value = value;
+  newEntry->next = NULL;
+
+  return newEntry;
+}
+
+/**
+* findItem
+*
+* Helper function that checks whether there exists the hash table entry that
+* contains a specific key.
+*
+* @param myHashTable The pointer to the hash table.
+* @param key The key corresponds to the hash table entry
+* @return The pointer to the hash table entry, or NULL if key does not exist
+*/
+static HashTableEntry* findItem(HashTable* myHashTable, unsigned int key) {
+  unsigned int bucketNum = myHashTable->hash(key);  // Get the bucket number.
+  HashTableEntry* temp = myHashTable->buckets[bucketNum]; // Get the head entry.
+
+  if (temp == NULL) return NULL;  // If there's nothing in the bucket, return NULL.
+
+  while (temp!=NULL) {
+    if (temp->key==key) return temp; // Return the hash table entry if the key is found.
+    temp = temp->next;  // Otherwise, move to next node.
+  }
+
+  return NULL;  // Return NULL if key is not present.
+}
+
+/****************************************************************************
+* Public Interface Functions
+*
+* These functions implement the public interface as specified in the header
+* file, and make use of the private functions and hidden definitions in the
+* above sections.
+****************************************************************************/
+HashTable* createHashTable(HashFunction myHashFunc, unsigned int numBuckets) {
+  // The hash table has to contain at least one bucket. Exit gracefully if
+  // this condition is not met.
+  if (numBuckets==0) {
+    printf("Hash table has to contain at least 1 bucket...\n");
+    exit(1);
+  }
+
+  // Allocate memory for the new HashTable struct on heap.
+  HashTable* newTable = (HashTable*)malloc(sizeof(HashTable));
+
+  // Initialize the components of the new HashTable struct.
+  newTable->hash = myHashFunc;
+  newTable->num_buckets = numBuckets;
+  newTable->buckets = (HashTableEntry**)malloc(numBuckets*sizeof(HashTableEntry*));
+
+  // As the new buckets contain indeterminant values, init each bucket as NULL.
+  unsigned int i;
+  for (i=0; i<numBuckets; ++i) {
+    newTable->buckets[i] = NULL;
+  }
+
+  // Return the newly created hash table.
+  return newTable;
+}
+
+void destroyHashTable(HashTable* myHashTable) {
+  unsigned int i;
+  HashTableEntry* temp;
+  HashTableEntry* next;
+
+  // Loop through each bucket of the hash table to remove all items.
+  for (i=0; i<myHashTable->num_buckets; ++i) {
+     temp = myHashTable->buckets[i];  // set temp to be the first entry of the ith bucket
+
+    // delete all entries
+    while (temp != NULL) {
+      next = temp->next;
+      free(temp->value);
+      free(temp);
+      temp = next;
+    }
+  }
+
+  // free buckets
+  free(myHashTable->buckets);
+
+  // free hash table
+  free(myHashTable);
+}
+
+void* insertItem(HashTable* myHashTable, unsigned int key, void* value) {
+  // First, we want to check if the key is present in the hash table.
+  HashTableEntry* temp = findItem(myHashTable, key);
+
+  if (temp) {
+    // The key is present in the hash table.
+    void* oldValue = temp->value;
+    temp->value = value;
+    return oldValue;
+  } else {
+    // The key is not present in the hash table.
+    temp = createHashTableEntry(key, value);
+    temp->next = myHashTable->buckets[myHashTable->hash(key)];
+    myHashTable->buckets[myHashTable->hash(key)] = temp;
+    return NULL;  // Return NULL as nothing is overwritten.
+  }
+}
+
+void* getItem(HashTable* myHashTable, unsigned int key) {
+  // First, we want to check if the key is present in the hash table.
+  HashTableEntry* temp = findItem(myHashTable, key);
+
+  if (temp) // if the key exists
+    return temp->value;
+  else  // return NULL if the key does not exist
+    return NULL;
+}
+
+void* removeItem(HashTable* myHashTable, unsigned int key) {
+  // Reference: https://www.geeksforgeeks.org/linked-list-set-3-deleting-node/
+  unsigned int bucketNum = myHashTable->hash(key);  // get the bucket number
+  HashTableEntry* temp = myHashTable->buckets[bucketNum]; // get the head entry
+  HashTableEntry* prev;
+
+  // If head holds the key
+  if (temp != NULL && temp->key == key) {
+    myHashTable->buckets[bucketNum] = temp->next;  // Change head
+    void* oldValue = temp->value; // hold the old value
+    free(temp);
+    return oldValue;
+  }
+
+  // Search for the key to be removed
+  while (temp != NULL && temp->key != key) {
+    prev = temp;
+    temp = temp->next;
+  }
+
+  // If the key is not present in the list
+  if (temp == NULL) return NULL;
+
+  // Unlink the node from list
+  prev->next = temp->next;
+  void* oldValue = temp->value; // hold the old value
+  free(temp);
+
+  return oldValue;
+}
+
+void deleteItem(HashTable* myHashTable, unsigned int key) {
+  // remove the entry and free the returned data
+  free(removeItem(myHashTable, key));
+}