File content as of revision 22:33f1a0dff46c:

//=================================================================
// 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: Kate Blake
 Date: 11/2/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) {
    //allocate memory for new hash table entry
    HashTableEntry* newHashTableEntry = (HashTableEntry*)malloc(sizeof(HashTableEntry));

    //assign key var in struct to key parameter
    newHashTableEntry->key = key;
    //assign value var in struct to value parameter
    newHashTableEntry->value = value;
    //assign next var to default NULL
    newHashTableEntry->next = NULL;

    //return the new entry
    return newHashTableEntry;
}

/**
* 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) {
    //check to make sure recieved valid hashTable
    if (hashTable != NULL) {
      //bucketNum variable to track what array space it takes up
      unsigned int bucketNum = hashTable->hash(key);
      //make sure the bucket exists
      if (hashTable->buckets[bucketNum] != NULL) {
        //currentEntry for tracking nested entries
        HashTableEntry* currentEntry = hashTable->buckets[bucketNum];
        //while loop for nested search
        while (currentEntry->key != key && currentEntry->next != NULL) {
          currentEntry = currentEntry->next;
        }
        //did we find it?
        if (currentEntry-> key == key) {
          return currentEntry;
        }
      }
    }
    //otherwise return NULL
  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) {
  //make sure a hashtable exists to destroy
    if (hashTable != NULL) {
      unsigned int i;
      //search the buckets for entries to free
      for (i=0; i<hashTable->num_buckets; ++i) {
        if (hashTable->buckets[i] != NULL) {
          HashTableEntry* currentEntry = hashTable->buckets[i];
          HashTableEntry* pastEntry;
          //get the nested entries as well
          while (currentEntry -> next != NULL) {
              pastEntry = currentEntry;
              currentEntry = currentEntry -> next;
              if (pastEntry -> value != NULL) {
                //freeee them
                free(pastEntry->value);
                pastEntry->value = NULL;
              }
              //free them all
              if (pastEntry != NULL) {
                free(pastEntry);
                pastEntry = NULL;
              }
          }
          if (currentEntry -> value != NULL) {
            //make sure you catch all those bad boys
                free(currentEntry->value);
                currentEntry->value = NULL;
              }
            //this catches the one the while loop ignores
          if (currentEntry != NULL) {
            free(currentEntry);
            currentEntry = NULL;
          }
        }
      }
     //see if theres anything in the buckets 
      if (hashTable->buckets != NULL) {
        //empty the buckets
        free(hashTable->buckets);
        hashTable->buckets = NULL;
      }
      //double check that hashtable just to be safe before freeing
      if (hashTable != NULL) {
        free(hashTable);
        hashTable = NULL;
      }
    }
}

void* insertItem(HashTable* hashTable, unsigned int key, void* value) {
  //make sure a valid hashtable is provided
    if (hashTable == NULL) {
      return NULL;
    }
    //find what bucket this boys in
    unsigned int bucketNum = hashTable->hash(key);
    //create the entry for the boy
    HashTableEntry* hashTableEntry = createHashTableEntry(key, value);
    //checks if theres something already in the bucket
    if (hashTable->buckets[bucketNum] != NULL) {
      //are the keys the same?
      if (hashTable->buckets[bucketNum]->key == key) {
        //if so grab old value
        void* oldval = hashTable->buckets[bucketNum]->value;
        //free the old boy
        if (hashTable->buckets[bucketNum] != NULL) {
          free(hashTable->buckets[bucketNum]); 
        }
        //overwrite
        hashTable->buckets[bucketNum] = hashTableEntry;
        //return old value
        return oldval;
      } else {
        //check for nested keys
        HashTableEntry* currentEntry = hashTable->buckets[bucketNum];
        HashTableEntry* pastEntry;
        while(currentEntry->next !=NULL && currentEntry-> key != key){
          //if there is another nested entry and the keys dont match keep cycling through the nested
          pastEntry = currentEntry;
          currentEntry = currentEntry->next;
        }
        //if the keys match take the old value replace it and return the old value
        if (currentEntry-> key == key) {
          void* oldval = currentEntry->value;
          if (hashTable->buckets[bucketNum] != NULL) {
            free(currentEntry);
          }
          //append to where old entry was
        pastEntry->next = hashTableEntry;
        return oldval;
        } 
        //otherwise append to end of nested chain
        currentEntry->next = hashTableEntry;
      }
    } else {
      //if the bucket is uninhabited the boy now lives there
      hashTable->buckets[bucketNum] = hashTableEntry;
    }
    return NULL;
}

void* getItem(HashTable* hashTable, unsigned int key) {
  //make sure a valid hashtable was provided
    if (hashTable == NULL) {
      return NULL;
    }
    //find which bucket it is
    unsigned int bucketNum = hashTable -> hash(key);
    //make sure bucket isnt empty
    if (hashTable->buckets[bucketNum] == NULL) {
      return NULL;
    } else {
      //otherwise find the entry
      HashTableEntry* foundHashEntry = findItem(hashTable, key);
      //make sure entry is valid
      if (foundHashEntry != NULL) {
        //return entry
        return foundHashEntry->value;
      }
      return NULL;
    }
}

void* removeItem(HashTable* hashTable, unsigned int key) {
  //make sure valid hashtable is provided
  if (hashTable == NULL) {
      return NULL;
    }
  //initialize booleans to check for nesting conditions and bucket number
  unsigned int isNested = 0;
  unsigned int isntTail = 1;
  unsigned int bucketNum = hashTable->hash(key);
  //make sure bucket isnt empty
  if (hashTable->buckets[bucketNum] != NULL) {
    //define entries for nesting
    HashTableEntry* currentEntry = hashTable->buckets[bucketNum];
    HashTableEntry* pastEntry;
    HashTableEntry* futureEntry;
    //check for nesting and update variables as needed
    while (currentEntry->next !=NULL && currentEntry->key !=key) {
      pastEntry = currentEntry;
      currentEntry = currentEntry->next;
      isNested = 1;
      if (currentEntry->next == NULL) {
        isntTail = 0;
      } else {
        futureEntry = currentEntry -> next;
      }
    }
    //make sure entry is valid
    if (currentEntry != NULL){
      //check for sandwiched entry to be removed
      if (isNested == 1 && isntTail == 1) {
        pastEntry->next = futureEntry;
        //otherwise assume its the tail if its nested
      } else if (isNested == 1) {
        pastEntry->next = NULL;
      } 
      //assign removed entry to return
      void* removedEntryVal = currentEntry->value;
      //double check for valid entry
      if (currentEntry != NULL) {
        //check whether it is only thing in bucket
        if (currentEntry->next !=NULL && isNested == 0) {
          futureEntry = currentEntry->next;
          hashTable->buckets[bucketNum] = futureEntry;
        } else if (isntTail == 1 && isNested == 0) {
          hashTable->buckets[bucketNum] = NULL;
        }
        //free removed entry
        free(currentEntry);
        currentEntry = NULL;
      }
      //return the entry
    return removedEntryVal;
    }
  }
  return NULL;
}

void deleteItem(HashTable* hashTable, unsigned int key) {
  if (hashTable == NULL) {
    printf("Hash table doesn't exist.\n");
    exit(1);
  } 
  //initialize booleans to check for nesting conditions and bucket number
  unsigned int isNested = 0;
  unsigned int isntTail = 1;
  unsigned int bucketNum = hashTable->hash(key);
  //make sure bucket isnt empty
  if (hashTable->buckets[bucketNum] != NULL) {
    //define entries for nesting
    HashTableEntry* currentEntry = hashTable->buckets[bucketNum];
    HashTableEntry* pastEntry;
    HashTableEntry* futureEntry;
    //check for nesting and update variables as needed
    while (currentEntry->next !=NULL && currentEntry->key !=key) {
      pastEntry = currentEntry;
      currentEntry = currentEntry->next;
      isNested = 1;
      if (currentEntry->next == NULL) {
        isntTail = 0;
      } else {
        futureEntry = currentEntry -> next;
      }
    }
    //make sure entry is valid
    if (currentEntry != NULL){
      //check for sandwiched entry to be removed
      if (isNested == 1 && isntTail == 1) {
        pastEntry->next = futureEntry;
        //otherwise assume its the tail if its nested
      } else if (isNested == 1) {
        pastEntry->next = NULL;
      } 
      //double check for valid entry
      if (currentEntry != NULL) {
        //check whether it is only thing in bucket
        if (currentEntry->next !=NULL && isNested == 0) {
          futureEntry = currentEntry->next;
          hashTable->buckets[bucketNum] = futureEntry;
        } else if (isntTail == 1 && isNested == 0) {
          hashTable->buckets[bucketNum] = NULL;
        }
        if (currentEntry -> value != NULL) {
            //free value
                free(currentEntry->value);
                currentEntry->value = NULL;
              }
        //free removed entry
        free(currentEntry);
        currentEntry = NULL;
      }
    }
  }
}