LangleyMann
LangleyMann

Reputation: 11

Double free when trying to free memory allocated in a Chained Hashmap in C

Apologies in advance for the code dump, I can't really think of another way to show my issue properly. For a school project I have to make a bakery simulation and since it has to fit within certain parameters of time and space efficiency I figured the best way to implement a "recipe" system (which needs to accommodate an arbitrary amount of recipes each with an arbitrary number of ingredients listed) would be with a chained hashmap. I allocate some memory with malloc through the process, more specifically I allocate memory for each instance of the "Recipe" struct in the map, and also allocate memory for two arrays of, respectively, strings and ints, but when I try to free the memory by cycling through the hashmap I get a double free error that I can't seem to shake off no matter what I do. Here is the valgrind output.

==3362== Invalid free() / delete / delete[] / realloc()
==3362==    at 0x484988F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==3362==    by 0x10970E: hashClose (ChainedHashMap.c:140)
==3362==    by 0x10929E: main (ChainedHashMap.c:632)
==3362==  Address 0x1ffeffe310 is on thread 1's stack
==3362==  in frame #2, created by main (ChainedHashMap.c:604)

The hashmap works (like i imagine all c hashmaps) by using a struct as a base like so:

#define HASHSIZE_RECIPE 8
#define HASHSIZE_WAREHOUSE 15

struct Recipe
{
    char name[255]; 
    struct Recipe *p; 
    int count; 
    int *quantities; 
    char **ingredients;
};

struct Recipe *makeRecipe(char str[]) 
{
    struct Recipe *rec = malloc(sizeof(struct Recipe));

    strcpy(rec -> name, str);
    rec -> p = NULL;
    rec -> count = 0;
    rec -> quantities = NULL; 
    rec -> ingredients = NULL;

    return rec;
}

void addIng(char str[], struct Recipe *rec)
{
    if(rec -> count == 0) 
    {
        rec -> ingredients = malloc(1 * sizeof(char *));
    }
    else if(rec -> count > 0) 
    {
        rec -> ingredients = realloc(rec -> ingredients, (rec -> count +1) * sizeof(char *));
    }

    rec -> ingredients[rec -> count] = malloc(255 * sizeof(char)); 
    strcpy(rec -> ingredients[rec -> count], str); 
}

void addQuant(int qt, struct Recipe *rec) 
{
    if(rec -> count == 0)
    {
        rec -> quantities = malloc(1 * sizeof(int));
    }
    else if(rec -> count > 0)
    {
        rec -> quantities = realloc(rec -> quantities, (rec -> count +1) * sizeof(int));
    }

    rec -> quantities[rec -> count] = qt; 

    rec -> count++;
}

The code isn't commented because the comments are written in my mother tongue. I free the struct by calling this function, which seems to work on simple instances of the struct (manually created in the main function).

void deleteRecipe(struct Recipe *rec) 
{
    if(rec == NULL) //evita double free eventual
        return;

    if(rec -> ingredients != NULL) 
    {
        for (int i = 0; i < rec -> count; i++)
        {
            free(rec -> ingredients[i]); 
            rec -> ingredients[i] = NULL;
        }

        free(rec -> ingredients); 
        rec -> ingredients = NULL;
    }

    if(rec -> quantities != NULL) 
        free(rec -> quantities); 
    rec -> quantities = NULL;

    free(rec); 
    rec = NULL;
}

Now I use a pointer to place each struct into an array and crate the chained hashMap with this function:

void hashInit(struct Recipe arr[HASHSIZE_RECIPE])
{
    for(int i = 0; i < HASHSIZE_RECIPE; i++)
    {
        arr[i] = *makeRecipe("no_recipe");
    }

}

void hashInsert(struct Recipe arr[HASHSIZE_RECIPE], struct Recipe *rec) 
{
    if(hashSearch(arr, rec -> name) < HASHSIZE_RECIPE) 
    {
        printf("%s\n", "ignored");
        return;
    }
    unsigned long i = djb2(rec -> name) % HASHSIZE_RECIPE; 
    if(strcmp(arr[i].name, "no_recipe") == 0) 
    {
        arr[i] = *rec; 
        arr[i].p = NULL;
    }
    else
    {
    struct Recipe *temp = &arr[i];

    while(temp -> p != NULL)
    {
        temp = temp -> p;
    }

    temp -> p = rec; 
    rec -> p = NULL;
    }

    printf("added\n");
}

This works without problems, only I would like to free the hashmap once the program is over, I do so with this function

void hashClose(struct Recipe arr[HASHSIZE_RECIPE])
{
    for(int i = 0; i < HASHSIZE_RECIPE; i++)
    {
        struct Recipe *delete = &arr[i];

        while (delete != NULL)
        {
            struct Recipe *temp = delete -> p; 
            deleteRecipe(delete);
            delete = temp; 
        }
    }
}

This cause a series of double free errors that I simply can't understand the cause of, the delete function should also have accounted for the possibility of freeing NULL pointers. Any pointers (get it), please?

EDIT I didn't want to post this since its honestly a mess of a function and I think it works relatively like intended, but the mistake might indeed be here. The input for the project is delivered through a file which contains a series of instructions followed by data, with everything separated by spaces and the instructions are to use the standard input/output to handle this, so the main really only initializes a struct Recipe array, calls the initHash function on it, the closeHash function at the end, and the following inputReader function in between.

void inputReader(struct Recipe recipeBook[HASHSIZE_RECIPE])
{
    char inpt[255];
    while(gotFunct || scanf("%s", inpt) > 0) 
    {
        gotFunct = false;

        if(strcmp(inpt, "add_recipe") == 0)
        {
            if(scanf("%s", inpt) > 0) 
            {
                int quant = 0;

                struct Recipe *temp = makeRecipe(inpt);

                while(isNotAFunction(inpt)) 
                {
                    addIng(inpt, temp);
                    if(scanf("%i", &quant) > 0)
                    {addQuant(quant, temp);} 
                }

                hashInsert(recipeBook, temp); 

                gotFunct = true; 
            }

        } //(the function then proceeds with other cases, they do not cause the same issue though. 
}

This is the isNotAFunction function, it's a simple if case checker

bool isNotAFunction(char s[255])
{
    if(scanf("%s", s) > 0)
    {
        if(strcmp(s, "add_recipe") == 0 ||
           strcmp(s, "remove_recipe") == 0 ||
           strcmp(s, "delivery") == 0 ||
           strcmp(s, "order") == 0)
        {
            return false;
        }
        else
        {
            return true; 
        }
    }
    else
    {
        return false; 
    }
}

calling this with the following input should work and reproduce the issue:

Pancakes flour 150 milk 200 egg 2 sugar 30 butter 20 baking_powder 5 Smoothie banana 1 yogurt 150 honey 20 strawberry 100 orange_juice 200 Salad lettuce 100 cucumber 50 tomato 80 olive_oil 15 lemon_juice 10 feta_cheese 50 Omelette egg 3 milk 50 cheese 30 salt 5 pepper 2 butter 10 Pasta spaghetti 200 olive_oil 20 garlic 5 cherry_tomatoes 100 basil 10 parmesan 30 Sandwich bread 2 ham 50 cheese 40 lettuce 20 mayonnaise 10 tomato 30 Cookies flour 250 sugar 150 butter 100 egg 1 vanilla 5 chocolate_chips 100 Soup chicken_broth 500 carrot 50 celery 30 onion 40 salt 5 noodles 100 parsley 10

Upvotes: 1

Views: 88

Answers (0)

Related Questions