Thread: Free List?

  1. #1
    Registered User
    Join Date
    May 2016
    Posts
    104

    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?
    printf("I'm a %s.\n", strrev("Dren"));

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,172
    It's basically a kind of garbage collection mechanism.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,859
    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.
    Fact - Beethoven wrote his first symphony in C

  4. #4
    Registered User
    Join Date
    Feb 2019
    Posts
    533
    Did you know there is an extension to GCC to automatically cleanup?
    Code:
    static void clearup_ptr( void **ptr ) { if ( *ptr ) free( *ptr ); }
    
    void doSomething( void )
    {
      __attribute__((cleanup(cleanup_ptr))) char *p;
    
      p = malloc(size);  //...
    
      // ... do a lot of stuff...
    
      // don't need to free here.
      // exiting the function will do...
    }

  5. #5
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,859
    That's fairly awesome - Just check what OS you are using, as flp said it is not a standard function

  6. #6
    Registered User
    Join Date
    May 2016
    Posts
    104
    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!
    Last edited by Dren; 05-21-2019 at 01:06 AM. Reason: derp spacing
    printf("I'm a %s.\n", strrev("Dren"));

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Free linked list in 2D list
    By deathmetal in forum C Programming
    Replies: 17
    Last Post: 08-13-2015, 09:27 PM
  2. need help in free() of linked list
    By iHateSicsic in forum C Programming
    Replies: 7
    Last Post: 11-14-2010, 02:36 PM
  3. free list
    By rabers in forum C Programming
    Replies: 32
    Last Post: 02-18-2009, 08:53 AM
  4. how to check list is free
    By ok_good in forum C Programming
    Replies: 5
    Last Post: 09-15-2007, 02:00 PM
  5. free()ing a list
    By viaxd in forum C Programming
    Replies: 3
    Last Post: 06-19-2004, 08:11 AM

Tags for this Thread