Skip to content

Instantly share code, notes, and snippets.

@ayah527
Created May 8, 2021
Embed
What would you like to do?
#include "hashtable.h"
#include <stdlib.h>
/*
* This creates a new hash table of the specified size and with
* the given hash function and comparison function.
*/
HashTable *createHashTable(int size, unsigned int (*hashFunction)(void *),
int (*equalFunction)(void *, void *)) {
int i = 0;
HashTable *newTable = calloc(1, sizeof(HashTable));
newTable->size = size;
newTable->data = calloc(size, sizeof(struct HashBucket *));
for (i = 0; i < size; i++) {
newTable->data[i] = NULL;
}
newTable->hashFunction = hashFunction;
newTable->equalFunction = equalFunction;
return newTable;
}
/*
* This inserts a key/data pair into a hash table. To use this
* to store strings, simply cast the char * to a void * (e.g., to store
* the string referred to by the declaration char *string, you would
* call insertData(someHashTable, (void *) string, (void *) string).
*/
void insertData(HashTable *table, void *key, void *data) {
// -- TODO --
// HINT:
// 1. Find the right hash bucket location with table->hashFunction.
// 2. Allocate a new hash bucket struct.
// 3. Append to the linked list or create it if it does not yet exist.
int index = ((table -> hashFunction)(key)) % table -> size;
// finding location of given key
struct HashBucket *bucket2 = (struct HashBucket*)
calloc(1000, sizeof(struct HashBucket));
// making hashbucket
bucket2 -> key = key;
bucket2 -> data = data;
bucket2 -> next = table -> data[index];
// setting necessary variables within the bucket
table -> data[index] = bucket2;
// appending it
}
/*
* This returns the corresponding data for a given key.
* It returns NULL if the key is not found.
*/
void *findData(HashTable *table, void *key) {
// HINT:
// 1. Find the right hash bucket with table->hashFunction.
// 2. Walk the linked list and check for equality with table->equalFunction.
int index = ((table -> hashFunction)(key)) % table -> size;
struct HashBucket *pointer =
table -> data[index];
while (pointer != NULL) {
if ((table -> equalFunction)(pointer -> key, key) != 0) {
return pointer -> data;
}
pointer = pointer -> next;
}
return NULL;
}
/*
* Include the provided hash table library.
*/
#include "hashtable.h"
/*
* Include the header file.
*/
#include "philphix.h"
/*
* Standard IO and file routines.
*/
#include <stdio.h>
/*
* General utility routines (including malloc()).
*/
#include <stdlib.h>
/*
* Character utility routines.
*/
#include <ctype.h>
/*
* String utility routines.
*/
#include <string.h>
/*
* This hash table stores the dictionary.
*/
HashTable *dictionary;
/*
* The MAIN routine. You can safely print debugging information
* to standard error (stderr) as shown and it will be ignored in
* the grading process.
*/
int main(int argc, char **argv) {
if (argc != 2) {
fprintf(stderr, "Specify a dictionary\n");
return 1;
}
/*
* Allocate a hash table to store the dictionary.
*/
fprintf(stderr, "Creating hashtable\n");
dictionary = createHashTable(0x61C, &stringHash, &stringEquals);
fprintf(stderr, "Loading dictionary %s\n", argv[1]);
readDictionary(argv[1]);
fprintf(stderr, "Dictionary loaded\n");
//fprintf(stderr, "%c", getchar());
fprintf(stderr, "Processing stdin\n");
processInput();
/*
* The MAIN function in C should always return 0 as a way of telling
* whatever program invoked this that everything went OK.
*/
return 0;
}
/*
* This should hash a string to a bucket index. Void *s can be safely cast
* to a char * (null terminated string)
*/
unsigned int stringHash(void *s) {
// online reference: stackoverflow to replicate hash functions
char *d = (char *) s;
unsigned int hash = 5381;
int curr;
while ((curr = *d++)) {
hash = ((hash << 5) + hash) + curr;
}
return hash;
}
/*
* This should return a nonzero value if the two strings are identical
* (case sensitive comparison) and 0 otherwise.
*/
int stringEquals(void *s1, void *s2) {
const char *s11 = (char *) s1;
const char *s22 = (char *) s2;
//converting void values to char
if(strcmp(s11, s22) == 0) {
return 1;
} else {
return 0;
}
}
/*
* This function should read in every word and replacement from the dictionary
* and store it in the hash table. You should first open the file specified,
* then read the words one at a time and insert them into the dictionary.
* Once the file is read in completely, return. You will need to allocate
* (using malloc()) space for each word. As described in the spec, you
* can initially assume that no word is longer than 60 characters. However,
* for the final bit of your grade, you cannot assumed that words have a bounded
* length. You CANNOT assume that the specified file exists. If the file does
* NOT exist, you should print some message to standard error and call exit(61)
* to cleanly exit the program.
*/
void nullCheck(char* check) {
if (check == NULL) {
exit(61);
}
}
void readDictionary(char *dictName) {
// notes: (1) open file specified (2) iterate through (3) read
//the words as you iterate (4) malloc space for key and val then
//use insert data (5) how to break at lines ??
//sources: referred to stackoverflow to find open method & file methods
FILE *given = fopen(dictName, "r");
if (given == NULL) {
fprintf(stderr, "Given file does not exist. \n");
exit(61);
}
//char chars[60];
char *key = NULL;
char *val = NULL;
char *words = calloc(1, sizeof(char));
nullCheck(words);
int c;
int whitesp = 0;
size_t index = 0;
while ((c = fgetc(given)) != EOF) {
if (isspace(c) != 0) {
if (strlen(words) == 0) {
continue;
}
if ((whitesp == 0) && (key == NULL)) {
whitesp++;
key = calloc(strlen(words), sizeof(char));
nullCheck(key);
strcpy(key, words);
} else if ((whitesp == 1) && (val == NULL)) {
val = calloc(strlen(words), sizeof(char));
nullCheck(val);
strcpy(val, words);
}
if ((key != NULL) && (val != NULL)) {
insertData(dictionary, key, val);
whitesp = 0;
key = NULL;
val = NULL;
}
memset(words, 0, strlen(words));
index = 0;
} else {
words = realloc(words, (size_t) index + 2);
words[index] = (char) c;
index ++;
}
}
if ((key != NULL) && (val == NULL)) {
val = calloc(strlen(words), sizeof(char));
nullCheck(val);
strcpy(val, words);
if ((val != NULL) && (key != NULL)) {
insertData(dictionary, key, val);
whitesp = 0;
key = NULL;
val = NULL;
}
}
// note: tried freeing key & val and dictionary stopped working.
// guessing dictionary ends up pointing to the same pointer, which makes sense
free(words);
fclose(given);
}
/*
* This should process standard input (stdin) and perform replacements as
* described by the replacement set then print either the original text or
* the replacement to standard output (stdout) as specified in the spec (e.g.,
* if a replacement set of `taest test\n` was used and the string "this is
* a taest of this-proGram" was given to stdin, the output to stdout should be
* "this is a test of this-proGram"). All words should be checked
* against the replacement set as they are input, then with all but the first
* letter converted to lowercase, and finally with all letters converted
* to lowercase. Only if all 3 cases are not in the replacement set shoud
* it report the original word.
*
* Since we care about preserving whitespace and pass through all non alphabet
* characters untouched, scanf() is probably insufficent (since it only considers
* whitespace as breaking strings), meaning you will probably have
* to get characters from stdin one at a time.
*
* Do note that even under the initial assumption that no word is longer than 60
* characters, you may still encounter strings of non-alphabetic characters (e.g.,
* numbers and punctuation) which are longer than 60 characters. Again, for the
* final bit of your grade, you cannot assume words have a bounded length.
*/
char* datafind(char* key) {
char* rv = NULL;
int asAre = 0;
int firUpper = 0;
int i = 0;
char c = key[0];
char* sanitized = calloc(strlen(key), sizeof(char));
for (int i = 0; c != '\0'; i++) {
c = key[i];
if (isalpha(c) != 0) {
strcat(sanitized, &c);
}
}
c = key[i];
if (findData(dictionary, sanitized) != NULL) {
rv = findData(dictionary, sanitized);
asAre = 1;
}
for (i = 1; sanitized[i] != '\0'; i ++) { // changing all cases but first
sanitized[i] = tolower(sanitized[i]);
}
if (findData(dictionary, sanitized) != NULL) {
if (asAre != 1) {
rv = findData(dictionary, sanitized);
}
firUpper = 1;
}
for (i = 0; sanitized[i] != '\0'; i ++){ // changing all cases
sanitized[i] = tolower(sanitized[i]);
}
if (findData(dictionary, sanitized) != NULL) {
if (asAre != 1 && firUpper != 1) {
rv = findData(dictionary, sanitized);
}
}
free(sanitized);
return rv;
}
void processInput(){
// for each line
// tokenize words (strtok), loop through tokens
// stop when strtok returns null
int c;
int index = 0;
char* temp;
char* words = calloc(1, sizeof(char));
nullCheck(words);
int mark = 0;
while ((c = getchar()) != EOF) {
if (isalpha(c) == 0) {
if (mark == 0) {
mark = 1;
}
words[strlen(words)] = '\0';
temp = calloc(strlen(words), sizeof(char));
nullCheck(temp);
strcpy(temp, words);
char* check = datafind(temp);
if (check != NULL) {
fprintf(stdout, "%s", check);
} else {
fprintf(stdout, "%s", temp);
}
fprintf(stdout, "%c", c);
memset(words, 0, strlen(words));
mark = 0;
index = 0;
free(temp);
} else {
words = realloc(words, (size_t) index + 2);
words[index] = (char) c;
words[index + 1] = '\0';
index ++;
}
}
if (mark == 0) {
temp = calloc(strlen(words), sizeof(char));
nullCheck(temp);
strcpy(temp, words);
char* check = datafind(temp);
if (check != NULL) {
fprintf(stdout, "%s", check);
} else {
fprintf(stdout, "%s", temp);
}
free(temp);
}
free(words);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment