Thread: Free List?

Hey guys,
After expanding a program I wrote a couple of months ago and finding the memory cleaning section unsightly -bunch of flags and conditions to determine what I must and mustn't free- I stumbled upon the idea of using a “free list”; a list in which I store all the pointers that must be freed by the end of the program, those that must persist throughout its life. All temporary allocations that can be, are freed after use and are not included in this list.



I have to say I’ve never seen this concept before, but then again, I haven’t read many real world, programs. As far as I know this might be a common thing or regarded as evil as global variables.


Personally, I don’t see nothing wrong with it, but there could be pitfalls I’m not thinking of. What do guys think?

It's basically a kind of garbage collection mechanism.

The way that this is usually done is that you make your own header/source file and implement custom memory allocation functions.

A linked list works really well for keeping tabs on allocations, because you can free things in the middle of the list and then remove that element very easily.

Main file...

Code:

#include "GCMalloc.h"

...

banana = GCmalloc(numberOfElements * sizeof(*banana));

GCMalloc's implementation...

Code:

void *GCMalloc(size_t allocationSize)
{
    // malloc allocation size
    // if successful, add to list
    
    // return result
}

void GCfree(void *elementToFree)
{
    // free element and remove from list
}

void GCdispose(void)
{
    // for each element in list, GCfree
}


void *GCCalloc(size_t nmemb, size_t size)
{
    ...
}


// To provide a consistant implementation, you will also need to have...

void *GCRealloc(void *ptr, size_t size);
{
    ...
}

That last one didn't use the list, but it is important that you create a consistant interface to work with.

It'sbasically a kind of garbage collection mechanism.

Yes, exactly! I’m stealing that term for my function identifiers.

The way that this is usually done is...

I have to say linked lists were the first thing that popped into my mind when I first thought of this, but while implementing it I found a simple static void** variable would suffice and thought the linked list was a bit overkill. The ability to remove a single element without upsetting the whole thing does seem appealing though…
At first I was going to call the “add to the list” function after each pointer’s allocation, but I realized it’d be much better to call the function from a single place. Since I already have my own malloc wrapper -memalloc- which calls malloc and zeroes out the new allocation, I created an alternative memalloc_gc, which callst he gc function. I used a single function that handles everything,but I like your factored approach much better.

Code:

#define RESET_GC max_element_count = 4;initialized = 0;element_count = 0

static void execute_garbage_collector(_Bool insert_element, void *element)
{
    static unsigned int element_count;
    static unsigned int max_element_count = 4;
    static _Bool initialized;
    static void **elements;

    if (!initialized)
    {
        elements = malloc(max_element_count * sizeof(void*));
        initialized = 1;
    }
    if (insert_element)
    {
        if (element_count >= max_element_count)
        {
            elements = (void**)ft_realloc((void*)(elements - element_count),
            max_element_count * sizeof(void*), element_count * 2 * sizeof(void*));
            max_element_count = element_count * 2;
        }
        *elements++ = element;
        element_count++;
        return ;
    }
    max_element_count = element_count;
    elements -= element_count;
    while (element_count--)
        free(*elements++);
    free(elements - max_element_count);
    RESET_GC;
}

That is what I came up with. I used a low max element count to make sure the realloc section would trigger; I wasn’t too confident in it. Surprisingly I didn’t have to debug anything, it worked on first try which is a first for me! The define is just a hack to save lines, which my school’s rules sadly limit.

I think your suggestion is much more robust, though. I’m gonna go ahead with it.

Thanks.

Did you know there is an extension to GCC to automatically cleanup?

I wasn’t aware of that. It is amazing indeed!