0

For pset5 I am using trie as a data structure to load words into the memory and the small dictionary loads just fine but for the large dictionary I always get a segmentation fault while loading the word "aardwolf". Using gdb it seems the value of the pointer to one of the nodes changes at that point and I get a "Cannot access memory at address xxx".

Here is my struct

#define SIZE 27 // 26 + 1 for apostrophe

typedef struct node {
    bool is_word;
    struct node* next[SIZE];
} node;

node* trie;

load():

bool load(const char *dictionary)
{
// open dictionary file 
FILE* fp = fopen(dictionary, "r");
if(fp == NULL) {
    printf("Could not open file");
    return false;
}

char * word = malloc(LENGTH+1 * sizeof(char));
node * trie = malloc(sizeof(node));

while(fscanf(fp, "%s", word) != EOF) {

    // prepare for new word
    node* head = trie;
    int x = 0;
    char c;

    // get each character of the word
    while((c = *word++)) {

        x = hash(c);

        // check if a path doesn't exists
        if(head->next[x] == NULL) {
            // create a new path
            node* new_node = calloc(1, sizeof(node));
            if(new_node == NULL) {
                unload();
                return false;
            }

            head->next[x] = new_node;
        }

        // move down the trie
        head = head->next[x];
    }

    // end the word
    head->is_word = true;
    ++dict_size;
}

// check whether there was an error
if (ferror(fp))
{
    fclose(fp);
    printf("Error reading %s.\n", dictionary);
    unload();
    return false;
}

fclose(fp);

return true;
}

and my hash function:

int hash(const char c) {
    return c == 39 ? SIZE - 1 : c % 97;
}
0

Your structure should also include some information whether the current node encodes a valid word.

Instead of LENGTH+1 * sizeof(char), you should write (LENGTH+1) * sizeof(char). Since char is usually 1, there's no difference, but if it weren't, you would want the extra parentheses.

In your check function, remember to tolower the letters, so you ignore the case.

After your inner while loop, you should mark the current node as encoding a word.

[edit] Don't forget initialising the structures, for example using calloc instead of malloc, which additionally overwrites the memory block with all zeroes.

[edit2] After discussion in chat, also found the following: local variable trie shadows global variable trie, and word is incremented, but never reset. The following did not segfault for me:

    char * word = malloc(LENGTH+1 * sizeof(char));
    char * word2 = word; // remember initial value
    trie = calloc(1, sizeof(node));

    while(fscanf(fp, "%s", word = word2) != EOF) {
7
  • hash transform to 0-26 only. For the apostrophe i.e ASCII 39, I return SIZE -1 which is 26 – Shalzz Jan 31 '17 at 8:37
  • Though this still doesn't help with my segmentation fault. – Shalzz Jan 31 '17 at 8:39
  • Oh, right, but where do you mark a node as representing an actual word? – Blauelf Jan 31 '17 at 9:01
  • Segfault is because you use malloc and don't initialise. Use calloc instead of malloc, so you get all zeroes, ehich means NULL for pointers and false for booleans. – Blauelf Jan 31 '17 at 9:09
  • Updated my code. Still getting a segfault. – Shalzz Jan 31 '17 at 10:05

You must log in to answer this question.

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