0

I think I've implemented load in a (mostly) correct way. For the most part it seems to be sorting and loading into the hashtable correctly but I'm not sure.

The problem I'm running into is that I seem to be losing the pointers to linked lists from each hashtable entry. It seems to be happening at the end of either my load or link functions. I noticed this because when I try to implement size or check, I can see with gdb that every entry in my hashtable is NULL (some entries should have linked lists).

I know it's bad form to post full functions but I'm at a loss here, I've tried looking at values with gdb and luckily I don't have any errors or (much) memory leaking when looking with valgrind.

Here's the code for the load function (it calls another function called 'link' that is below)

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

    for (int i = 0; i < HASH_LENGTH; i++)
    {
        hashtable[i] = malloc(sizeof(node));
        if (hashtable[i] == NULL)
        {
            free(hashtable[i]);
            printf("error allocating mem to hashtable.\n");
            return false;
        }
        hashtable[i]->word = NULL;
        hashtable[i]->next = NULL;
    }

    // spell-check each word in text
    while (!EOF)
    {
        node* new_node = malloc(sizeof(node));
        if (new_node == NULL)
        {
            free(new_node);
            printf("error allocating mem to new_node.\n");
            return false;
        }

        fscanf(fp, "%s", new_node->word);

        if (new_node->word == 0)
        {
            printf("error reading word to new_node.\n");
            free(new_node);
            return false;
        }
        new_node->next = NULL;

        link(new_node, hashtable);
    }

    return true;
}

And the link function:

void link(node* new_node, node* hashtable[])
{
    unsigned int h = hash(new_node->word);
    // this will return the index of the hash table 
    // we then insert the word into the linked list at that index
    // we want the list to be sorted


    // at hashtable[h] insert into linked list
    if (hashtable[h]->word == NULL)
    {
        (hashtable[h])->word = new_node->word;
        (hashtable[h])->next = NULL;
    }
    // put node in proper place in list
    else
    {
        node* cursor = hashtable[h];

        // for each node, run strcmp with current node
        if (strcmp(new_node->word, cursor->word) > 0)
        {
            while (strcmp(new_node->word, cursor->word) > 0)
            {    
                 if (cursor->next == NULL)
                 {
                    new_node->next = NULL;
                    cursor->next = new_node;
                 }
                 else if (strcmp(new_node->word, (cursor->next)->word) < 0)
                 {
                     new_node->next = cursor->next;
                     cursor->next = new_node;
                 }
                 else
                 {   
                      cursor = cursor->next;
                 }
             }
        }
        else if (strcmp(new_node->word, cursor->word) == 0)
        {
            free(new_node);
        }
        else if (strcmp(new_node->word, cursor->word) < 0)
        {
            node* tmp = malloc(sizeof(node));
            if (tmp == NULL)
            {
                free(tmp);
                printf("error allocating mem to tmp.\n");
            }
            tmp->next = (hashtable[h])->next;
            tmp->word = (hashtable[h])->word;
            (hashtable[h])->word = new_node->word;
            (hashtable[h])->next = new_node->next;
            new_node->word = tmp->word;
            new_node->next = tmp->next;
            free(tmp);
        }

    }
}
2
  • You're not sure if your load is working? Try writing a test code to navigate and print out some words in the hash table. – ronga Oct 29 '15 at 8:11
  • I was able to figure it out. It turns out there was a few things wrong with my load function. Thanks for the help! On to unload now.. – jamesasefa Oct 29 '15 at 20:11

You must log in to answer this question.

Browse other questions tagged .