0

I realise there are probably lots of other errors in my code (which you are welcome to point out...PLEASE) but when I use debug on this code, it shows a segmentation fault when calling the HASH function from the LOAD function. The char NEWSTRING is showing as being null and so for some reason isn't getting the word from the dictionary in the while loop where it is reading from the file. i tried to keep my hash function as ridiculously simple as possible so I can get it working first and then go back to improve it.

Any ideas?

EDIT: Amended following suggested changes in answer given

/**
 * Implements a dictionary's functionality.
 */

#include <stdbool.h>
#include "dictionary.h"
#include <stdio.h>
#include <strings.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

typedef struct node
{
    char word[LENGTH+1];
    struct node *next;
}
node;
node *hashtable[50];
int numofwords = 0;

/**
 * Returns true if word is in dictionary else false.
 */

bool check(char *searchword)
{

    // make the whole thing lowercase
    int len = strlen(searchword);
    char newword[len+1];


    for(int i = 0; i< len; i++){
        newword[i] = tolower(searchword[i]);
    }
    newword[len] = '\0';

    int x = hash(newword);
    node *current;
    current = hashtable[x];

    if (current == NULL){
        return false;
    }

    int cmpres = strcasecmp(current->word, newword);
    while(current != NULL){
        cmpres = strcasecmp(current->word, newword);
        if (cmpres == 0){
            return true;
        }
        current = current->next;
    }
    return false;
}

/**
 * Loads dictionary into memory. Returns true if successful else false.
 */
bool load(const char *dictionary)
{

    FILE* dict = fopen(dictionary, "r");
    if (dict == NULL)
    {
        printf("No valid dictionary to open.\n");
        return false;
    }

    char newstring [LENGTH+1];
    //make a new node for the word
    node *newnode = malloc(sizeof(node));
    while (fscanf(dict, "%s", newstring) != EOF){
        numofwords ++;
        int x = hash(newstring);
        //copy the newstring in to word
        strcpy(newnode->word, newstring);
        //replace head node with new node and link it to old head
        newnode->next = hashtable[x];
        hashtable[x] = newnode;
    }
    fclose(dict);
    return true;
}


/**
 * Returns number of words in dictionary if loaded else 0 if not yet loaded.
 */
unsigned int size(void)
{

    if (numofwords == 0){
        return 0;
    }
    else{
        return numofwords;
    }
}

/**
 * Unloads dictionary from memory. Returns true if successful else false.
 */
bool unload(void)
{
    // TODO
    int freed = 0;
    node *temp;
    node *current;
    for(int i = 0; i < 50; i++){
        current = hashtable[i];
        while(current != NULL){
            while(current->next != NULL){
                temp = current->next;
                free(current);
                freed++;
                current = temp;
            }
            break;
        }
        freed++;
    }
    free(temp);
    return true;
}

/**
 * Hashes a word
 */

 int hash(char *newstring){
     char y = newstring[0];
     int d = y - '0';
     while(d > 50){
         d = d - 50;
     }


     if (d < 0){
         return abs(d);
     }
     else{
         return d;
     }
 }
2

In check, what if hashtable[x] is NULL? Your loop should use something like while (current != NULL).

Also, use cmpres == 0 (is equal, return true) rather than == 1 (is greater than). strcasecmp returns an integer <0, 0, or >0, depending on how the two strings relate to each other, and only 0 means "equal".

In load, don't traverse the linked list (O(n)). Insert at the front instead (O(1)). And you need to give the new node's next property a value (then hashtable[x], the old head of the list). malloc allocates memory that may have any value, only global variables are zero by default.

Don't forget to fclose the dictionary.

[edit] I must have missed the char *newstring = NULL;. fscanf won't allocate that memory for you, and simply skips writing to NULL. That's probably the first reason for segfault in your code. Use char newstring[LENGTH+1]; instead.

Your second version of check is not really what I meant. I said while (current != NULL), because you want to compare the current node of the list as long as it's an actual node and not the list end (marked by a NULL). Inside the loop, if strcasecmp(current->word, searchword) == 0, you'd return true. After the loop, you'd return false. Having the NULL check before the strcasecmp protects you from another segfault.

Your second version of load does not allocate any nodes on the heap. Could be as easy as

        newnode = malloc(sizeof(node));
        if (newnode == NULL) {
            // ran out of heap memory, trying to quit gracefully
            unload();
            return false;
        }
        strcpy(newnode->word, newstring);
        newnode->next = hashtable[x];
        hashtable[x] = newnode;

There's nothing different for hashtable[x] being NULL.

Insertion at the head of the linked list is really fast (likely one of the reasons for the performance of the staff solution).

size and unload again should contain while(current != NULL){ (if current were NULL, accessing current->next would cause segfault), and size could be much faster if you counted the words on insertion, and just returned that global integer. An extra check for a dictionary size of 0 makes no sense, it does not change anything.

In unload, the whole point of temp = current->next; is that you cannot dereference current after free(current), so you need to use current = temp;.

And finally a really ugly one: Your hash function. It should return values between 0 and 49. But for the given input, it returns values -9 (word starting with ') or 2 (word starting with a letter). The hash function also needs to ignore the case of a word, or be fed with a word that has its case normalised already. Use tolower or toupper on any character you process.

Instead of 50 in all places, you could have a constant at the top (either a const int variable or a #define macro), so you could test different values (in case you used a better hash function) easily without having to change in all those places (and forgetting one). [/edit]

11
  • I 'think' I've made the changes you suggested but I'm still getting the same problem. It's still showing a segmentation fault and newstring being NULL having never taken the first word from the dictionary. I've edited my first post to reflect the changes. Oct 12 '17 at 12:02
  • Added a few more points. Seems like I did not really read your question, and totally missed the newstring topic.
    – Blauelf
    Oct 12 '17 at 14:06
  • Ok, I have gotten now to the point where the code is running but I'm not detecting any mispelled words. My output is: WORDS MISSPELLED: 0 WORDS IN DICTIONARY: 143091 WORDS IN TEXT: 9 TIME IN load: 0.03 TIME IN check: 0.00 TIME IN size: 0.00 TIME IN unload: 0.00 TIME IN TOTAL: 0.03 This is just with a small 9 word text document that I'm testing with. I have updated my code in the original post to reflect my changes. Any idea what is going on? Why is there so little time in load, and no time in check and unload? Oct 18 '17 at 13:36
  • set newword[len] = '\0';. Again, use while (current != NULL) as I wrote earlier! Remove if (hashtable[x] == NULL){ hashtable[x] = newnode; }else as that will make your first node installed have uninitialised next field, and you don't need that if-else. Remove the malloc from node *current = malloc(sizeof(node));, you never use that memory, but forget about it without freeing. You don't really need that variable either if you set newnode->next first. In unload, forget about while (current->next != NULL). Two loops are enough. And always return true from that one.
    – Blauelf
    Oct 18 '17 at 13:54
  • Oh, and your hash function still is pretty useless, but different now. Have you tested it with different strings? I don't think you will get all numbers from 0 to 49 from regular input.
    – Blauelf
    Oct 18 '17 at 13:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .