I have been working on the problem set speller for the last days and so far this is what I have. Unfortunately, it does not compile and I am a bit lost. I would be really grateful if somebody can help me out and tell me, what I am doing wrong.
// Implements a dictionary's functionality
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
#include <strings.h>
#include <stdlib.h>
#include "dictionary.h"
#define HASHTABLE_SIZE 65536
// A struct for a node
typedef struct node
{
// Length is up to 45 + 1 for the Null
char word[LENGTH + 1];
// A pointer to the next node
struct node *next;
}
node;
node *hashtable[HASHTABLE_SIZE];
node *head = NULL;
// Hashes words
// Thanks to the husband of reddit user delipity for providing the function
// https://www.reddit.com/r/cs50/comments/1x6vc8/pset6_trie_vs_hashtable/
int hash_it(char *word)
{
unsigned int hash = 0;
for (int i = 0, n = strlen(word); i < n; i++)
{
hash = (hash << 2) ^ word[i];
}
return hash % HASHTABLE_SIZE;
}
// A global var counter to keep track of all words in the dictionary
int counter = 0;
// A global var for the check function
int hashIndexForWord;
// Returns true if word is in dictionary else false
bool check(const char *word)
{
// Making a new variable with the capacity to store the word + 1 for the \0
char copyWord[strlen(word) + 1];
strcpy(copyWord, word);
// A pointer to the beginning of a node
node *cursor = hashtable[hash_it(copyWord)];
while (cursor != NULL)
{
// Checks if the word is in the dictionary
if (strcasecmp(cursor -> word, copyWord) == 0)
{
return true;
}
else
{
// Move the cursor to the next node
cursor = cursor -> next;
}
}
return false;
}
// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
// Load up a file and open it for reading
FILE *file;
file = fopen(dictionary, "r");
char word[LENGTH + 1];
// Making each of buckets of the table NULL
for (int i = 0; i < HASHTABLE_SIZE; i++)
{
hashtable[i] = NULL;
}
int hashIndex;
// Reading through the dictionary file, looking for a string
// then putting it in a variable called word, until the EOF is reached
while (fscanf(file, "%s", word) != EOF)
{
// Allocating a memory for a new node of size for a node
node *new_node = malloc(sizeof(node));
//node *head = malloc(sizeof(node));
// Checking if malloc succeeded
if (new_node == NULL)
{
// If it does return null, unload the dictionary and return false
unload();
return false;
}
// If it succeeds copy the word into the node
strcpy(new_node->word, word);
// Hashing the word and getting the index
hashIndex = hash_it(word);
// Pointing to the first element of the table
new_node -> next = head;
// Assigning the head to be the new element
head = new_node;
// Hashing the word and inserting a word to that place
hashtable[hashIndex] = new_node;
counter++;
}
// After the dictionary is loaded, close the file and return true
fclose(file);
return true;
}
// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
// TODO
return counter;
}
// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
// Make a cursor pointing to the head
node *cursor = head;
while (cursor != NULL)
{
// A temporary node pointing to cursor
node *temp = cursor;
// Move the cursor to next
cursor = cursor -> next;
// Free the temp
free(temp);
}
return true;
// When to return false?
}
In all of the functions I get a couple of undefined referenced and invalid symbol indexes that do not let the code compile:
undefined reference to `__ubsan_handle_nonnull_arg'
undefined reference to `__ubsan_handle_shift_out_of_bounds'
undefined reference to `__ubsan_handle_type_mismatch'
undefined reference to `__ubsan_handle_add_overflow'
undefined reference to `__ubsan_handle_divrem_overflow'
UBSAN_SANITIZE := n
. I could not find references about the required libraries. See also kernel.org/doc/html/v4.16/dev-tools/ubsan.html or google "ubsan" – Dispense