File content as of revision 2:5645cb2d9316:

/****************************************************************************
* 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));
}