File content as of revision 5:37ed7d5744a6:

/*
 Student Name: Kori Alejandro
 Date: 3/27/2019

=======================
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* this_node= (HashTableEntry *) malloc(sizeof(HashTableEntry));
  if (!this_node) return NULL;
  this_node -> key = key; //sets new key
  this_node -> value = value; // sets new value
  this_node -> next = NULL; //sets next value to be NULL
  return this_node; //return HTE
}

/**
* 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 k) {            // finds and returns the node when searching for a specific key
  HashTableEntry* this_node = hashTable -> buckets[hashTable -> hash(k)]; // finds first node in that bucket number
  while (this_node){ // loops through until this_node is empty/null
    if (this_node ->key ==k) return this_node; // if key found in the node, return thatnode where it is found
    this_node= this_node -> next; // goes to next node
  }
  return NULL; //if not found 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.
  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) {
  unsigned int num_buckets = hashTable -> num_buckets;// number of buckets
  HashTableEntry * temp;
  for (unsigned int i=0; i< num_buckets; i++){// iterates through each bucket
    HashTableEntry * this_node= hashTable -> buckets[i];//first entry in the bucket
     while (this_node != NULL){
       temp= this_node -> next;// saves next HTE
       free(this_node -> value); // frees value
       free(this_node); // frees node
       this_node=temp; // next node
     }
   }
  free(hashTable -> buckets); // free buckets
  free(hashTable); // what else do I need to free?
}

void* insertItem(HashTable* hashTable, unsigned int key, void* value) {                                //
  //find bucket that key is in then insert a new HTE at the end of that bucket
  // HashTableEntry * this_node= hashTable -> buckets[hashTable-> hash(key)]; //1st bucket entry
  // if (this_node == NULL) return NULL; // if bucket is empty- key and value not found
  // HashTableEntry * temp;
  //void* old= getItem(hashTable, key);// necessary??
  //while (this_node){
  // temp= this_node;//saves previous
  // this_node= this_node -> next;
  //}
  //temp -> next = createHashTableEntry(key, value);// creates HTE at end- does this set the 'next' address to be the HTE?
  // return old;
   // ---------------------------------------------------return old value if replaced or NULL if not replaced???
  //replacing value in existing node
   HashTableEntry * this_node = findItem(hashTable, key); //find the node the key is in
   if (this_node)
     {
       void* temp = this_node -> value; //old value
       this_node -> value = value; // replaces old value with new value
       return temp;
     }
   else{// if NULLL
     HashTableEntry * entry= createHashTableEntry(key, value); // creates HTE w key and value
     entry -> next = hashTable -> buckets[hashTable -> hash(key)];// links the next value of our new HTE to the first HTE of the bucket
     hashTable -> buckets[hashTable -> hash(key)]=entry;// inserts HTE at the beginning
     return NULL;
   }
}

void* getItem(HashTable* hashTable, unsigned int key) {
  HashTableEntry *this_node= findItem(hashTable, key);//finds the node for the key
  if (this_node == NULL) return NULL; // if key not found
  return this_node -> value; // return value
}

void deleteItem(HashTable* hashTable, unsigned int key) {
  //HashTableEntry * this_node= findItem(hashTable, key); //finds the node
  //void * value= getItem(hashTable, key);//gets the value
  //if (this_node == NULL) return NULL; //do I need to output NULL if node not found
  //free(this_node); //need to free hash table entry from the heap-- is this done correctly?-- need to connect previous and next entries when deleting HTE- EDGE cases
  //deleteItem(hashTable, key);
  //return value; //returns value
  void* old= removeItem(hashTable, key);
  if (old) free(old);
}

void* removeItem(HashTable* hashTable, unsigned int key) {
  //HashTableEntry * adr = hashTable -> buckets[hashTable -> hash(key)];//desired bucket address
  //HashTableEntry * temp= adr -> next; //
  //void* val;
  //if (adr == NULL) return NULL; // if null intial bucket
  //if ( adr -> key== key){ // desired key in head of bucket
    //hashTable -> buckets[hashTable-> hash(key)] = temp; // if you free first address need to set it to the next address.
    //val= adr -> value;
    //free(adr); // free HTE
    //return val;
    //}
  //adr= hashTable -> buckets[hashTable-> hash(key)]; // reset adr if in first
  //if (adr == NULL) return NULL;
  //HashTableEntry * temp2;
  //while (adr){
    //temp= adr; // saves previous entry
    //adr= adr -> next; // current entry
    //temp2= adr -> next;// saves next entry
    //if (adr -> key ==key){
      //temp -> next =temp2; //links previous and next
      //val= adr -> value;
      //free(adr); // free HTE
      //return val;
      // }
    //}
  //return NULL; //shouldnt need but failsafe
  //Edge cases: null intial bucket, desired key not in head of bucket, is first node match- doesnt - go to next node, 
  //}
  HashTableEntry * this_node= findItem(hashTable, key);// node we want to delete 
  HashTableEntry * adr = hashTable -> buckets[hashTable -> hash(key)];// intial address of the bucket
  void* val; // initialize  a variable to hold the value inside of the node before it is freed
  if (this_node == NULL) return NULL;
  if (adr == NULL) return NULL;
  if (adr == this_node) // accounts for if the first address is the node we want to free
    {
      hashTable -> buckets[hashTable -> hash(key)] = this_node -> next;
      val= this_node -> value;// saves value into a variable so that you can return it 
      free(this_node);
      return val;
    }
    else{
      while (this_node != NULL){ // while this node is not null
    if (adr -> next == this_node){
       adr-> next= this_node -> next;//links first and last nodes when this_node is deleted
       val = this_node -> value; 
       free(this_node);
       return val;
    }
      else{
        adr= adr -> next;//increments the address to the next node for comparison 
      }
      }
    return NULL;// fail safe
    }
}