File content as of revision 10:0b2f37cef9b9:

//=================================================================
// Copyright 2020 Georgia Tech.  All rights reserved.
// The materials provided by the instructor in this course are for
// the use of the students currently enrolled in the course.
// Copyrighted course materials may not be further disseminated.
// This file must not be made publicly available anywhere.
//=================================================================

/*
 Student Name: Alvin Jorgih
 Date: 10/26/2020

=======================
ECE 2035 Project 2-1:
=======================
This file provides definition for the structs and functions declared in the
header file. It also contains helper functions that are not accessible from
outside of the file.

FOR FULL CREDIT, BE SURE TO TRY MULTIPLE TEST CASES and DOCUMENT YOUR CODE.

===================================
Naming conventions in this file:
===================================
1. All struct names use camel case where the first letter is capitalized.
  e.g. "HashTable", or "HashTableEntry"

2. Variable names with a preceding underscore "_" will not be called directly.
  e.g. "_HashTable", "_HashTableEntry"

  Recall that in C, we have to type "struct" together with the name of the struct
  in order to initialize a new variable. To avoid this, in hash_table.h
  we use typedef to provide new "nicknames" for "struct _HashTable" and
  "struct _HashTableEntry". As a result, we can create new struct variables
  by just using:
    - "HashTable myNewTable;"
     or
    - "HashTableEntry myNewHashTableEntry;"

  The preceding underscore "_" simply provides a distinction between the names
  of the actual struct defition and the "nicknames" that we use to initialize
  new structs.
  [See Hidden Definitions section for more information.]

3. Functions, their local variables and arguments are named with camel case, where
  the first letter is lower-case.
  e.g. "createHashTable" is a function. One of its arguments is "numBuckets".
       It also has a local variable called "newTable".

4. The name of a struct member is divided by using underscores "_". This serves
  as a distinction between function local variables and struct members.
  e.g. "num_buckets" is a member of "HashTable".

*/

/****************************************************************************
* 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.
 * Use "HashTable" instead when you are creating a new variable. [See top comments]
 */
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.
 * Use "HashTableEntry" instead when you are creating a new variable. [See top comments]
 */
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)
{
  // init hash table entry by allocating memory for it on the heap
  HashTableEntry *newEntry = (HashTableEntry *)malloc(sizeof(HashTableEntry));
  // init the key on the key field in the entry
  newEntry->key = key;
  // init the value on the value field in the entry
  newEntry->value = value;
  // init the value on the next field in the entry
  newEntry->next = NULL;
  // return to the hash table of the entry
  return newEntry;
}

/**
* findItem
*
* Helper function that checks whether there exists the hash table entry that
* contains a specific key.
*
* @param hashTable 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 *hashTable, unsigned int key)
{
  // initialize bucket key
  unsigned int bucketKey;
  // get the bucketkey by hashing the key and dereferencing the value
  bucketKey = hashTable->hash(key);
  // pointer to the bucket head, the first item in the bucket with
  // the corresponding input key
  HashTableEntry *bucketHead = hashTable->buckets[bucketKey];

  // edge case where there is nothing inside the bucket
  if (bucketHead == NULL) {
    return NULL;
  }

  // else if bucket is not NULL
  if (bucketHead != NULL)
  {
    // we loop through the items
    while (bucketHead != NULL)
    {
      // and if the key of one of the items matches with a key
      if (bucketHead->key == key)
      {
        // return the following item
        return bucketHead;
      }
      else
      {
        // else we continue traversing
        bucketHead = bucketHead->next;
      }
    }
  }
  return NULL;
}

/****************************************************************************
* 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.
****************************************************************************/
// The createHashTable is provided for you as a starting point.
HashTable *createHashTable(HashFunction hashFunction, 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.
  // size of HashTable: determined by the type of the HashTable
  // malloc: allocates size for the HashTable
  HashTable *newTable = (HashTable *)malloc(sizeof(HashTable));

  // Initialize the components of the new HashTable struct.
  // new table assigning value to hash
  // new table assigning value to num_buckets
  // new table assigning value to buckets
  newTable->hash = hashFunction;
  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 new HashTable struct.
  return newTable;
}

/**
 * destroyHashTable
 *
 * Destroy the hash table. The nodes (HashTableEntry objects) of singly linked
 * list, the values stored on the linked list, the buckets, and the hashtable
 * itself are freed from the heap. In other words, free all the allocated memory
 * on heap that is associated with heap, including the values that users store in
 * the hash table.
 *
 */
//need to ask Dr. Wills about this
void destroyHashTable(HashTable *hashTable)
{
  // iterate through each buckets, condition the number of buckets
  // if it is NULL, means no head, thus continue iteration
  // no direct access to num buckets, thus we use pointer to num buckets
  unsigned int i;
  // for loop to traverse through the hash table buckets
  for (i = 0; i < (hashTable->num_buckets); ++i)
  {
    //points to the value preceding the next one, for memory purposes
    HashTableEntry *pointer1 = hashTable->buckets[i];
    // if pointer1 is NULL, pointer 2 then will create SegFault
    if (pointer1 != NULL)
    {
      // pointer2 if they have a value for pointer 1
      HashTableEntry *pointer2 = pointer1->next;
      // while pointer2 is not NULL
      while (pointer2 != NULL)
      {
        // free the value of pointer1
        free(pointer1->value);
        // free the entry of pointer1
        free(pointer1);
        // pointer1 moves to pointer 2
        pointer1 = pointer2;
        // pointer 2 moves to the next after pointer 2
        pointer2 = pointer2->next;
      }
      // free the last value of the pointer
      free(pointer1->value);
      // free the pointer itself
      free(pointer1);
    }
  }

  // if everything is done, we free up the hashTable
  free(hashTable->buckets);
  // free the hashtable
  free(hashTable);
  // return
  return;
}

/**
 * insertItem
 *
 * Insert the value into the hash table based on the key.
 * In other words, create a new hash table entry and add it to a specific bucket.
 *
 */
void *insertItem(HashTable *hashTable, unsigned int key, void *value)
{
  // init index after hashing
  unsigned int bucketHashIndex = hashTable->hash(key);
  //init a pointer to the head of the bucket
  HashTableEntry *bucketHead = hashTable->buckets[bucketHashIndex];

  // while bucket head is not null
  while (bucketHead != NULL)
  {
    //if the bucket head has the same value like the key
    if (bucketHead->key == key)
    {
      // store the old value of the key to be returned
      void *oldValue = bucketHead->value;
      // change the bucket head value
      bucketHead->value = value;
      //return to the old value
      return oldValue;
    }

    // else keep traversing
    else
    {
      // reaching the last entry in the bucket
      bucketHead = bucketHead->next;
    }
  }

  // init new entry, should be here just because, if this is declared at the top
  // it will cause a memory leak due to the fact it may become unused
  HashTableEntry *newEntry = createHashTableEntry(key, value);

  // we are adding the entry from the front
  newEntry->next = hashTable->buckets[bucketHashIndex];
  hashTable->buckets[bucketHashIndex] = newEntry;

  return NULL;
}

/**
 * getItem
 *
 * Get the value that corresponds to the key in the hash table.
 *
 */
// get item utilizes the static function from findItem
void *getItem(HashTable *hashTable, unsigned int key)
{
  // call findItem and set it as a variable
  HashTableEntry *item = findItem(hashTable, key);
  // if it is not NULL, then we make another pointer to the value of the variable
  if (item != NULL)
  {
    // return the value of the item
    return item->value;
  }

  // else return NULL
  return NULL;
}

/**
 * removeItem
 *
 * Remove the item in hash table based on the key and return the value stored in it.
 * In other words, return the value and free the hash table entry from heap.
 *
 */
void *removeItem(HashTable *hashTable, unsigned int key)
{

  // we need to consider three cases: when the entry is on the head of the node
  // when the entry is sandwiched between two nodes
  // when the entry is at the end of the node
  // when the entry is not found

  int bucketKey = hashTable->hash(key);
  HashTableEntry *pointer1 = hashTable->buckets[bucketKey];

  // if the list is empty
  if (pointer1 == NULL) {
    return NULL;
  }

  // if the entry is not null
  if (pointer1 != NULL)
  {
    HashTableEntry *pointer2 = pointer1->next;
    // if the value of the key is in on the head of the node
    if (pointer1->key == key)
    {
      // deleted value saved to a variable called deleted value
      void *deletedValue = pointer1->value;
      // free the entry
      free(pointer1);
      // connects the head to the next pointer
      hashTable->buckets[bucketKey] = pointer2;
      // returns deleted value
      return deletedValue;
    }

    // when the entry is in the middle or at the end
    else
    {
      while (pointer2 != NULL)
      {
        if (pointer2->key == key)
        {
          // points to the deleted value
          void *deletedValue = pointer2->value;

          // if the key is in the last place
          if (pointer2->next == NULL)
          {
            // pointer points to NULL
            pointer1->next = NULL;
          }

          // if the entry is in the middle
          else
          {
            pointer1->next = pointer2->next;
          }
          // free the value of the second pointer
          free(pointer2);
          // return deleted value
          return deletedValue;
        }

        // else pointer next
        else
        {
          // pointer 1 is now pointer 2
          pointer1 = pointer2;
          // pointer 2 is now the next value of its first value
          pointer2 = pointer2->next;
        }
      }
    }
  }

  // else return NULL
  return NULL;
}

/**
 * deleteItem
 *
 * Delete the item in the hash table based on the key. In other words, free the
 * value stored in the hash table entry and the hash table entry itself from
 * the heap.
 *
 */
void deleteItem(HashTable *hashTable, unsigned int key)
{

  // we need to consider three cases: when the entry is on the head of the node
  // when the entry is sandwiched between two nodes
  // when the entry is at the end of the node
  // when the entry is not found

  int bucketKey = hashTable->hash(key);
  HashTableEntry *pointer1 = hashTable->buckets[bucketKey];

  // if the list is empty
  if (pointer1 ==  NULL) {
    return;
  }

  // if the entry is not null
  if (pointer1 != NULL)
  {
    HashTableEntry *pointer2 = pointer1->next;
    // if the value of the key is in on the head of the node
    if (pointer1->key == key)
    {
      // free the value of the pointer
      free(pointer1->value);
      pointer1->value = NULL;
      // free the entry
      free(pointer1);
      // connects the head to the next pointer
      hashTable->buckets[bucketKey] = pointer2;
      // returns deleted value
      return;
    }

    // when the entry is in the middle or at the end
    else
    {
      while (pointer2 != NULL)
      {
        if (pointer2->key == key)
        {
          // if the key is in the last place
          if (pointer2->next == NULL)
          {
            // pointer points to NULL
            pointer1->next = NULL;
          }

          // if the entry is in the middle
          else
          {
            pointer1->next = pointer2->next;
          }
          // free the value of the pointer
          free(pointer2->value);
          // free the value of the second pointer
          free(pointer2);
          // return deleted value
          return;
        }

        // else pointer next
        else
        {
          // pointer 1 is now pointer 2
          pointer1 = pointer2;
          // pointer 2 is now the next value of its first value
          pointer2 = pointer2->next;
        }
      }
    }
  }

  // else return if the value is not in the hash table
  return;
}