File content as of revision 4:2297a714936f:

/*
 Student Name:
 Date:

=======================
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
*/
//my code for createHashTableEntry
static HashTableEntry* createHashTableEntry(unsigned int key, void* value) {
    
    HashTableEntry *newHashTableEntry;
    
    newHashTableEntry = (HashTableEntry*) malloc(sizeof(HashTableEntry));//malloc space
    if(!newHashTableEntry){
        return NULL;
    }
    
    newHashTableEntry -> key = key;         //assign key
    newHashTableEntry -> value = value;     //assign value
    
    
    return newHashTableEntry;               //return the address of the HashTableEntry
}

/**
* 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
*/
//myCode
static HashTableEntry* findItem(HashTable* hashTable, unsigned int key) {
    
    HashTableEntry* this_node = hashTable -> buckets[hashTable->hash(key)];//head
    while(this_node){//while there is a next node
        if(this_node -> key == key){//if the nodes key is equal to one we are searching for
            return this_node;
        }
        this_node = this_node -> next;//goes to next node   
    }
    return NULL;//returns null if not 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;
}

/**
 * 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.
 *
 * @param myHashTable The pointer to the hash table.
 *
 */
 //mycode
void destroyHashTable(HashTable* hashTable) {//destroy everything
    unsigned int numBuckets = hashTable -> num_buckets;// pull num_buckets
    //hashTable -> buckets[i];
    for(int i = 0; i < numBuckets; i++){//loop thorugh every bucket
        HashTableEntry* this_node = hashTable -> buckets[i];
        
        while(this_node){//loop thorugh every node in a bucket
            HashTableEntry* temp = this_node -> next;
            free(this_node -> value);
            free(this_node);
            this_node = temp;
        }
    }
    free(hashTable);//MR
    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.
 *
 * @param myHashTable The pointer to the hash table.
 * @param key The key that corresponds to the value.
 * @param value The value to be stored in the hash table.
 * @return old value if it is overwritten, or NULL if not replaced
 */
 //my code
 //og had: void* insertItem(HashTable* hashTable, unsigned int key, void* value)
void* insertItem(HashTable* hashTable, unsigned int key, void* value) {
    HashTableEntry* this_node; 
    
    if(this_node = findItem(hashTable, key)){//key in list
        void* ret_value = this_node -> value;//save value
        this_node -> value = value;          //give new value
        return ret_value;                    //return old value
    }
    
    //key not in list
    this_node = createHashTableEntry(key, value);   //create new node
    int bHash = hashTable -> hash(key); //get the index of bucket it is in
    
    this_node ->next = hashTable -> buckets[bHash]; //this_node -> next = head
    hashTable -> buckets[bHash] = this_node;        //head = this_node
    return NULL;
    
}
/**
 * getItem
 *
 * Get the value that corresponds to the key in the hash table.
 *
 * @param myHashTable The pointer to the hash table.
 * @param key The key that corresponds to the item.
 * @return the value corresponding to the key, or NULL if the key is not present
 */
void* getItem(HashTable* hashTable, unsigned int key) {
    
    HashTableEntry* found_node = findItem(hashTable, key); //head_node = head
    
    //if it found the node return the value of it
    if(found_node){
        return found_node -> value;
    }
    //otherwise 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.
 *
 * @param myHashTable The pointer to the hash table.
 * @param key The key that corresponds to the item.
 * @return the pointer of the value corresponding to the key, or NULL if the key is not present
 */
void* removeItem(HashTable* hashTable, unsigned int key) {
    HashTableEntry* this_node = hashTable -> buckets[hashTable->hash(key)]; //this_node = head

    //case empty
    if(!this_node)
        return NULL;
    
    //case first element
    if(this_node -> key == key){
        void* ret_value = this_node -> value;//save the value
        hashTable -> buckets[hashTable->hash(key)] = this_node -> next;//set head to the next node
        //free all components
    
        free(this_node);
        return ret_value;
    }
    
    //case need to walk the list
    while(this_node -> next){//already checked first node
        if(this_node -> next -> key == key){//delete this if true
            HashTableEntry* temp_node = this_node -> next;
            void* ret_value = temp_node -> value;//save the value
            this_node -> next = this_node -> next -> next;
            
            free(temp_node);
            return ret_value;
            
        }
        this_node = this_node -> next;
    }
    
    return NULL;//did not find anything to remove
}
/**
 * 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.
 *
 * @param myHashTable The pointer to the hash table.
 * @param key The key that corresponds to the item.
 *
 */
 
 void deleteItem(HashTable* hashTable, unsigned int key){
     HashTableEntry* this_node = hashTable -> buckets[hashTable->hash(key)]; //this_node = head

    //case empty
    if(!this_node)
        return;
    
    //case first element
    if(this_node -> key == key){
        hashTable -> buckets[hashTable->hash(key)] = this_node -> next;//set head to the next node
        //free all components
        free(this_node -> value);
        free(this_node);
        return;
    }
    
    //case need to walk the list
    while(this_node -> next){//already checked first node
        if(this_node -> next -> key == key){//delete this if true
            HashTableEntry* temp_node = this_node -> next;
            
            this_node -> next = this_node -> next -> next;
            free(temp_node->value);
            free(temp_node);
            return;
            
        }
        this_node = this_node -> next;
    }
    
    return;
 }