0

I've been on this pset for some time now and everythin seems to be working except that there are some memory leaks and I really can't understand why. I've checked a lot of other people's codes but I can't find my mistake so if anyone could help I would be really grateful. The error that i'm getting is:

==4048== HEAP SUMMARY:
==4048==     in use at exit: 12,018,888 bytes in 214,623 blocks
==4048==   total heap usage: 286,187 allocs, 71,564 frees, 16,036,512 bytes allocated
==4048== 
==4048== 4,005,792 bytes in 71,532 blocks are definitely lost in loss record 1 of 2
==4048==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4048==    by 0x401235: create_new_node (dictionary.c:77)
==4048==    by 0x4013A4: load (dictionary.c:115)
==4048==    by 0x4009B4: main (speller.c:40)
==4048== 
==4048== 8,013,096 bytes in 143,091 blocks are definitely lost in loss record 2 of 2
==4048==    at 0x4C2FB0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==4048==    by 0x401235: create_new_node (dictionary.c:77)
==4048==    by 0x4013B1: load (dictionary.c:116)
==4048==    by 0x4009B4: main (speller.c:40)
==4048== 
==4048== LEAK SUMMARY:
==4048==    definitely lost: 12,018,888 bytes in 214,623 blocks
==4048==    indirectly lost: 0 bytes in 0 blocks
==4048==      possibly lost: 0 bytes in 0 blocks
==4048==    still reachable: 0 bytes in 0 blocks
==4048==         suppressed: 0 bytes in 0 blocks
==4048== 
==4048== For counts of detected and suppressed errors, rerun with: -v
==4048== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)

which means that I'm not freeing everything as I think I am. my code is:

// Implements a dictionary's functionality

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

#include "dictionary.h"

// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

// Number of buckets in hash table
const unsigned int N = 2000000;

// Contador de palabras en el diccionario.
unsigned int count = 0;

// No se cargó el diccionario.
bool loaded = false;

// Hash table
node *table[N];

// Returns true if word is in dictionary else false
bool check(const char *word)
{

    int lenght = strlen(word) + 1;
    char palabra[lenght];

    for (int i = 0; i < lenght; i++)
    {
        palabra[i] = tolower(word[i]);
    }

    palabra[lenght] = '\0';

    int index = hash(palabra);
    node *cursor = table[index];
    {
        while (cursor != NULL)
        {
            if (strcmp(cursor -> word, palabra) == 0)
            {
                return true;
            }
            cursor = cursor -> next;
        }
    }
    return false;
}

// Hashes word to a number. djb2 by Dan Bernstein.
unsigned int hash (const char *word)
{
    unsigned int valor_hash = 0;
    unsigned int largo = strlen(word);
    for (int i = 0; i < largo ; i ++)
    {
        valor_hash = (valor_hash << 2) ^ word[i];
    }
    return valor_hash % (N-1);
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // Abrimos el archivo.
    FILE *archivo = fopen(dictionary, "r");
    // Checkeemos que el archivo sea válido.
    if (archivo == NULL)
    {
        printf("Could not load.\n");
        return false;
    }

    // Array que contiene una palabra de tammaño LENGHT+1 para meter
    // Las palabras del archivo del diccionario.
    char palabra [LENGTH + 1];

    // Leer cadenas del archivo hasta el final del archivo.
    // Agarramos la primera palabra del archivo, que es una string
    // y lo ponemos en la array palabra hasta que el archivo termine.
    while ( fscanf(archivo, "%s", palabra) != EOF)
    {
        // Sacamos el número hash de la palabra para saber en cual linked list ponerla.
        int index = hash(palabra);

        // Alocamos espacio y creamos un nuevo node para la hash table.
        node *n = malloc(sizeof(node));

        // Checkeamos que haya espacio para el nuevo node.
        if (n == NULL)
        {
            unload();
            return false;
        }

        // Copiamos lo que esté en la palabra al node que estamos creando.
        strcpy(n->word, palabra);
        n -> next = NULL;

        // Cabeza de la linked list.
        node* head = NULL;

        // Si esa linked list está vacía.
        if (table[index] == NULL)
        {
            head = n;
            table[index] = n;
        }
        // Le ponemos el valor de la palabra que tenemos.
        else
        {
            table[index] = n;
            n -> next = head;
            n = head;
        }

        // Contador de palabras en el diccionario.
        count++;

    }
    // Cerrar diccionario.
    fclose(archivo);
    loaded = true;
    return true;
}

// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
    if (!loaded)
    {
        return 0;
    }
    return count;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    // Loop que vaya por la cantidad N de linked lists de la hash table.
    for (int i = 0; i < N; i++)
    {
        // Nodo que apunta a la linked list numero "I".
        node *cursor = table[i];

        // Hasta llegar al final.
        while (cursor != NULL)
        {
            // Hacemos una copia.
            node *tmp = cursor;
            // El cursor apunta a el siguiente nodo.
            cursor = cursor -> next;
            // Liberamos la memoria alocada.
            free(tmp);
        }
    }
    loaded = false;
    return true;
}
0
2

The nodes created here if (!create_new_node(palabra)) (one for each dictionary word) are never freed.

1
  • what do you mean? I thought that wasn't creating any space and that It just check to see if the the node had been created. Also I tried to run valgrind deleting that checking and it came better (more frees) but still leaking. – Irina pérez Jun 1 '20 at 20:40
0

OK I FIXED IT. The problem was in my load function. This is what I initially had:

// Si esa linked list está vacía.
        if (table[index] == NULL)
        {
            n -> next = NULL;
            table[index] = n;
        }
        // Le ponemos el valor de la palabra que tenemos.
        else
        {
            table[index] = n;
            n -> next = table[index]
            n = head;
        }

I simply changed it to this:

// Le ponemos el valor de la palabra que tenemos.
        n -> next = table[index];
        table[index] = n;

aaaand for some reason it worked?? I thought I was being smarter by using a pointer to the head and having and if/else depending if that linked list had a node before but it seems that it only made it worse, I dont really get why though, if someone could explain why it would be amazing.

You must log in to answer this question.

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