0

I'm on pset 4, speller, using a hash table.

I have a while loop in which I malloc memory that a node pointer points to. In the unload function I free this memory. My program works fine in all respects except valgrind

I see in valgrind that there were 286,189 allocs, 143,098 frees. Does anyone know why this is, since there were only 143,091 possible times the while loop could have run ( and therefore for memory to have been malloc'ed) because the size of the dictionary file is 143,091 (my program does have this value as the dictionary size).

Thanks for your help!

bool load(const char *dictionary)
{
    nw=0;
    int k = 0;
    while(dictionary[k] != '\0')
    {
        dictionary2[k]=dictionary[k];
        k++;
    }
    dictionary2[k] = '\0';
    // Initialize hash table
    for (int i = 0; i < N; i++)
    {
        hashtable[i] = NULL;
    }

    // Open dictionary
    FILE *file = fopen(dictionary, "r");
    if (file == NULL)
    {
        return false;
    }

    // Buffer for a word
    char word[LENGTH + 1];

    // Insert words into hash table
    int h = 0;
    int a = 0;

    while (fscanf(file, "%s", word) != EOF)
    {
        node *node3=malloc(sizeof(node));
        h = hash(word);
        //node3->word = malloc(sizeof(char)*(LENGTH + 1));
        node3->next = NULL;
        strcpy(node3->word, word);
        if (hashtable[h] == NULL)
        {
            hashtable[h] = node3;
            node3 = NULL;
        }
        else
        {
            node3->next = hashtable[h];
            hashtable[h] = node3;
        }
        nw++;
    }
    fclose(file);
    return true;
}


// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    if (load(dictionary2)==true)
    {
        return nw;
    }
    else
    {
        return 0;
    }
}

// Returns true if word is in dictionary else false
bool check(const char *worda)
{
    int i = hash(worda);
    int j = 0;
    char word1[46];
    while(worda[j]!='\0')
    {
        if (worda[j] == '\'')
        {
            word1[j]=worda[j];
        }
        else
        {
            word1[j]=tolower(worda[j]);
        }
        j++;
    }
    word1[j]='\0';
    node * next2 = NULL;
    if (hashtable[i]==NULL)
    {
        return false;
    }
    if (strcmp(word1,hashtable[i]->word)==0)
    {
        return true;
    }
    else if (hashtable[i]->next == NULL)
    {
        return false;
    }
    else
    {
        next2 = hashtable[i]->next;
        while (strcmp(word1, next2->word) != 0)
        {
            if (next2->next != NULL)
            {
                next2 = next2->next;
            }
            else
            {
                return false;
            }
        }
        return true;
    }
    return true;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    for (int m = 0; m<26; m++)
    {
        node *cursor = hashtable[m];
        while(cursor!= NULL)
        {
            node *temp = cursor;
            cursor = cursor->next;
            free(temp);
        }
    }
    return true;
}
3
  • Without seeing code, it's impossible to know. But sinde the number of allocs is almost exactly 2x what's expected, that's a big clue. Maybe there's a malloc somewhere else that you've overlooked, or you have nested loops?
    – Cliff B
    Oct 26, 2019 at 7:51
  • Ok I realized it's because the speller program calls the size function, which loads dictionary again. So I put unload() in the size function Now valgrind tells me i have exactly as many allocs as frees, but it still has memory leaks because apparently there were as many errors as frees
    – hli
    Oct 26, 2019 at 8:02
  • Ok I changed the size function and now it works..
    – hli
    Oct 26, 2019 at 8:07

1 Answer 1

1

Your size function shouldn't call the load function.

You must log in to answer this question.

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