calgorithmmemoryquadtree

How to free all memory blocks of a picture using quadree structure with different cases?


Few weeks ago, I was trying to implement a function to display a quadtree. My current problem is concerning the same work, so I pass you this link for all the context: How to display composed quadtrees using C language?
(I'm using a few features that come from this post)

the quadtree structure:

typedef struct block_image
{
    int allBlack; //boolean
    struct block_image * son[4];
}block_image;
typedef block_image *image;

Currently, I’m working on a function to free all memory blocks of a quadtree. For example, if a quadtree is white, there is nothing to do because the pointer to the structure is already NULL. If a quadtree is black, we free the pointer and set it to NULL. Else, if it is a composed picture, we take care of freeing the space of the different sons.

summary: returns all blocks of an image to the memory.

My current program:

void freeMemory(image myImage)
{
    if(myImage == NULL)
    {
        return;
    }
    else if(myImage->allBlack)
    {
        free(myImage);
        myImage = NULL;
    }
    else
    {
        freeMemory(myImage->son[0]);
        freeMemory(myImage->son[1]);
        freeMemory(myImage->son[2]);
        freeMemory(myImage->son[3]);
    }  
}

However, I am not sure how to check my function. For exemple, I decided to create a white quadree and a black quadtree. But when I used freeMemory fonction and normalDisplay to see the representation of the two quadrees before and after, there was no difference.

printf("\nfreeMemory\n\n");
image white = Build_white();
image black = Build_black();
printf("before\n");
normalDisplay(black);
printf("\n");
printf("after\n");
freeMemory(black);
normalDisplay(black);
printf("\n");
printf("before\n");
normalDisplay(white);
printf("\nafter\n");
freeMemory(white);
normalDisplay(white);   
printf("\n");

The result:

enter image description here

As you can see, there was no difference between display before and after memory.

And this is the simplest case, after that it should also work with composed images,e.g.

Someone advised me to use valgrind, telling me that for my program to work, there must be as many malloc() as free(). But I don't really know how to interpret the results (and if it is really useful).

the result (My variable names was not in english so, affichageNormal == normalDisplay, Rendmemoire == freeMemory and Construit_noir == Build_black)

enter image description here

P.S. I also have two function isWhite and isBlack to tell if a picture is black (no white elements) or white (no black element):

int isWhite(image myImage)
{
    if(myImage == NULL)
    {
        return 1;
    }
    else if(myImage->allBlack)
    {
        return 0;
    }
    else if(isWhite(myImage->son[0]) && isWhite(myImage->son[1]) && isWhite(myImage->son[2]) && isWhite(myImage->son[3]))
    {
        return 1;
    }
    return 0;
}


int isblack(image myImage)
{
    if(myImage == NULL)
    {
        return 0;
    }
    else if(myImage->allBlack)
    {
        return 1;
    }
    else if(isBlack(myImage->son[0]) && isBlack(myImage->son[1]) && isBlack(myImage->son[2]) && isBlack(myImage->son[3]))
    {
        return 1;
    }
    return 0;
}

It may be useful for the function.

Edit: In case of doubt I also add the code of normalDisplay :

void normalDisplay(image myImage)
{
    if(myImage == NULL)
    {
        printf("B");
    }
    else if(myImage->allBlack)
    {
        printf("N");
    }
    else
    {
        printf("+");
        normalDisplay(myImage->son[0]);
        normalDispay(myImage->son[1]);
        normalDisplay(myImage->son[2]);
        normalDisplay(myImage->son[3]);
    }
}

Solution

  • A robust way to free the memory from the quadtree is to make sure you feedback that a pointer no longer is pointing to valid memory. Since your current freeMemory only takes an block_image pointer, the function cannot convey this information back to the caller.

    Better would be to change its interface to provide this facitily with another level of indirection.

    void freeMemory(image *myImage) {
        if (myImage != NULL && *myImage != NULL) {
            int sonSize = sizeof((*myImage)->son) / sizeof((*myImage)->son[0]);
            while (sonSize) freeMemory(&(*myImage)->son[--sonSize]);
            free(*myImage);
            *myImage = NULL;
        }
    }
    

    On a side note, your original freeMemory does have a memory leak, but hoping you can figure that out.

    This way, *myImage = NULL will convey this change to the caller. On the calling side it would look something like this:

    puts("\nfreeMemory\n");
    image white = Build_white();
    image black = Build_black();
    puts("before");
    normalDisplay(black);
    puts("");
    puts("after");
    freeMemory(&black);
    normalDisplay(black);
    puts("");
    puts("before");
    normalDisplay(white);
    puts("\nafter");
    freeMemory(&white);
    normalDisplay(white);
    puts("");
    

    With this your normalDisplay will better provide you with an "image" of the situation.