File content as of revision 23:06cbe894690d:

/*
 Student Name: Rony Stephan
 Date:11/2/21

=======================
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) {
    HashTableEntry* curr_node = (HashTableEntry*) malloc(sizeof(HashTableEntry));   //mallocs the size
    if(curr_node) {                                                                 //edge case, no size found(pointer is null)
      curr_node -> key = key;                                                       //sets key equal to parametrized key
      curr_node -> value = value;                                                   //sets value equal to parametrized value
      curr_node -> next = NULL;                                                     //sets next pointer equal to null(will later add at head)
    }

return curr_node;
}

/**
* 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) {
    unsigned int bucketNum = hashTable -> hash(key);                        //hashes the current key to find bucket number
    HashTableEntry* temp = hashTable -> buckets[bucketNum];                 //grabs the first entry at that linked list
    while(temp != NULL) {                                                   //while there is still a valid entry
      if(temp -> key == key) {                                              //if the key has been found
        return temp;                                                        //return the pointer to the node
      }         
      temp = temp -> next;                                                  //curr = curr.next
    }
    return NULL;                                                            //if code gets to this stage, it has not been found
}

/****************************************************************************
* 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.
  HashTable* newTable = (HashTable*)malloc(sizeof(HashTable));

  // Initialize the components of the new HashTable struct.
  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;
}

void destroyHashTable(HashTable* hashTable) {
    
    
    //First, loop through all buckets in the structure.

    unsigned int i;
    for (i = 0; i < hashTable->num_buckets; i++) {                  //for loop through all buckets
        if (hashTable->buckets[i]) {                                //if current bucket is not empty
            HashTableEntry *curr_node = hashTable -> buckets[i];    //sets current node to head of buckets  
            HashTableEntry *next_node = NULL;                       //initializes next node pointer(to delete from head)

            while(curr_node) {                                      //while current node is not null  
              next_node = curr_node -> next;                        //next node is current node's next
              free(curr_node->value);                               //free the current value at that node
              free(curr_node);                                      //free the current node
              curr_node = next_node;                                //current node = next node
            } 
        }
    }
    free(hashTable->buckets);                                       //free the buckets array as a whole
    free(hashTable);                                                //free the hashtable structure as a whole

 
}

void *insertItem(HashTable *hashTable, unsigned int key, void *value)
{

  HashTableEntry *curr_node = findItem(hashTable, key);           //find the current item in hashtable

  if (curr_node)                                                  //if node exists
  {                                                             
    void *old_value = curr_node->value;                           //store the old value
    curr_node->value = value;                                     //update value
    return old_value;                                             //return the old value
  }
  else
  {                                                              // node does not exist
    HashTableEntry *new_node = createHashTableEntry(key, value); //create new hashtable entry
    if (!(new_node))                                             //if malloc fails when creating item(maybe redundant)
    {              
      return NULL;
    }
    unsigned int bucketNum = hashTable->hash(key);              //find the bucket number
    HashTableEntry *head_node = hashTable->buckets[bucketNum];  //find the head node of current bucket

    new_node->next = head_node;                                 //set new node's next to current head
    hashTable->buckets[bucketNum] = new_node;                   // current bucket's head is new node;
    return NULL;                                                //return null as item is inserted
  }
}

void* getItem(HashTable* hashTable, unsigned int key) {
    HashTableEntry* item = findItem(hashTable, key);            //search for the item using findItem
    if(item != NULL) {                                          //if it has been found
      return item ->value;                                      //return the items value
    }
    else {                                                      //otherwise, return null
      return NULL;
    }
}

void* removeItem(HashTable* hashTable, unsigned int key) {
  // HashTableEntry* curr_node = findItem(hashTable, key);
  // if(!curr_node) {
  //   return NULL;
  // }
  // else{

    unsigned int bucketNum = hashTable->hash(key);                  //hash the current key to find bucket number 
    HashTableEntry *curr_node = hashTable->buckets[bucketNum];      //set current node equal to head of correct LL
    HashTableEntry* prev_node;                                      //initialize trailing pointer
    if(!curr_node){                                                 //if LL is empty, return NULL
      return NULL;                                                  
    }

    void* value_to_return;                                          //initialize value to return

    //CHECKING THE HEAD                                                                
    if(curr_node -> key == key){                                    //if the value is present in head
      value_to_return = curr_node->value;                           //store value of head
      hashTable->buckets[bucketNum] = curr_node ->next;             //set LL head to head.next
      free(curr_node);                                              //free current node and return value
      return value_to_return;
    }

    
    //EDGE CASE WHERE LL ONLY HAS ONE VALUE AND ITS NOT FOUND
    
    while(curr_node && curr_node -> next) {                        //while the current and next node are valid(curr_node starts at head, must have at least )
      if(curr_node -> next-> key == key) {                         //if the next node's key is correct
        prev_node = curr_node;                                     //set the node before deletion(prev_node) equal to curr_node

        HashTableEntry* node_to_remove = prev_node -> next;       //set the removal node equal to the node after prev_node
        value_to_return = node_to_remove -> value;                //store the value from the node to remove

        curr_node = node_to_remove -> next;                       //set the curr_node (after deletion) equal to removal node's next
        prev_node ->next = curr_node;                             //set before deletion's next to after deletion
        free(node_to_remove);                                     //free current node
        return value_to_return;                                   //return value at removal node
  
      }
      prev_node = curr_node;                                      //move previous node forward by one 
      curr_node = curr_node -> next;                              //move curr node forward by one
    }
    return NULL;                                                  //key not found, return null
  }




void deleteItem(HashTable* hashTable, unsigned int key) {
  free(removeItem(hashTable,key));                                 //frees the value returned by removeItem

}