linked lists and free()

Discussion in 'C Programming' started by Hans Vlems, Aug 30, 2013.

  1. Hans Vlems

    Hans Vlems Guest

    Linked lists of structures can grow considerably and use a lot of memory.
    Calling free() is necessary. What I do now is to descend the list to the pointer
    that points to the last node in the list and call free(structptr->nextnode), and travel backwards to free each preceeding node.
    Would just freeing the pointer to the top of the list work just as well?

    Hans
     
    Hans Vlems, Aug 30, 2013
    #1
    1. Advertisements

  2. Once you free memory, it becomes invalid and you can't access it again.
    Often implementations don't "shred" memory on free, so using it will
    appear to work, but eventually things will become unstuck.
    So if you free the preceding node, the following node becomes orphaned.
    But you can take a pointer to it, free the preceding node, then use that
    pointer to free the rest of the list.
    Try to write some code and post it here. I knock up little routines to
    free linked lists all the time, so it wouldn't take me a minute. But
    it's important to learn the technique.
     
    Malcolm McLean, Aug 30, 2013
    #2
    1. Advertisements

  3. Hans Vlems

    Paul N Guest

    Normally, in a linked list, each item in the list has its own separate "chunk" of memory. Each item holds a pointer to the next item, so that it knowswhere it is, but it does not "control" it in any way.

    To take a simple example, suppose there are only two items in the list. To clear the list completely and (try to) give the memory used back to the system, you would ask the first item where the second is stored; free that; then free the first item. You would normally also set the pointer that tells you where the first item is to NULL. If you just free the first item, the second item is still occupying memory - and worse still, you probably have no way of finding where in memory it is so you can't free it later even if you wanted to.
     
    Paul N, Aug 30, 2013
    #3
  4. You have to free memory in a manner that corresponds to the way in
    which the memory was allocated. If, as appears to be your practice,
    memory for each node was allocated individually, each must be freed
    individually. If you free the memory occupied by the first node
    without saving the address in the nextnode member, the memory occupied
    by the remaining members becomes inaccessible and constitutes n-1
    memory leaks.
     
    Barry Schwarz, Aug 30, 2013
    #4
  5. Hans Vlems

    Hans Vlems Guest

    Op vrijdag 30 augustus 2013 13:06:41 UTC+2 schreef Paul N:

    OK, that's what I thought would happen. So my method to travel all the linking pointers but the last (which is NULL) and start freeing first its contents (e.g. char *) and then itself, step one node back (recursively) and repeat the process until the master pointer is reached (which I termed points to the head of the list) and set that to NULL as the last step.
    Just freeing the master pointer isn't enough.
    Thanks,
    Hans
     
    Hans Vlems, Aug 30, 2013
    #5
  6. Hans Vlems

    James Kuyper Guest

    If you allocate a block of memory by calling malloc(), calloc() or
    realloc(), and you don't call free() to deallocate that same block of
    memory, then you have a memory leak. This applies separately to each
    block - the memory allocation system doesn't know anything about the
    fact that you've linked them together to form a list. If you allocated
    each element of the list separately, then you have to free() each one
    separately.

    If you allocated a single block containing many different nodes, and
    then linked them together to form a list, then you can deallocate that
    entire block at one time - but calling free() on the head node will do
    that only if the head node is also the first node in that block.

    There's something called "garbage collection", which periodically checks
    your entire memory to see if it contains anything that might be a
    pointer into an allocated block of memory; if it finds no such pointers,
    it automatically deallocates that block. A collector cannot, in general,
    know the details of what memory means, so it can sometimes detect false
    positives when a piece of memory that doesn't actually contain a pointer
    happens to have the same bit pattern as a pointer to the allocated memory.

    In effect, a garbage collection system DOES know about the fact that
    your nodes are linked together. If you free the head node, sooner or
    later it will notice that there's no pointers in memory pointing at the
    second node of the list, and will collect it, too. Eventually, the
    entire list will be collected. Note that this approach will not work on,
    for instance, a doubly-linked list, because there are two pointers to
    every node, and it cannot be deallocated until both have been collected
    - therefore, none of them will be collected.

    The malloc() family cannot use garbage collection, because the C
    standard specifies that the life time of an allocated object continues
    right up until it is explicitly free()d. There's no exception from this
    requirement just because there are no pointers to that memory currently
    in memory. Those pointers could be stored in an encrypted form not
    recognized by the collector, or on disk, or they could even be displayed
    for a user who writes them down and then types them back in later. If
    there are no unencrypted copies of the pointer currently in memory,
    garbage collection could collect the memory prematurely.

    However, implementations can support garbage collection of memory
    allocated by means other than the malloc() family. It's up to the user
    of such memory to make sure that at least one pointer remains in memory
    at all times, that points into any block of garbage-collectible memory
    that the user doesn't want collected.
     
    James Kuyper, Aug 30, 2013
    #6
  7. Hans Vlems

    James Kuyper Guest

    It would be simpler to deallocate it in the forward direction:

    node * nextnode;
    for(node *node=head; node; node=nextnode)
    {
    nextnode = node->nextnode;
    free(node->data);
    free(node);
    }
    head = NULL; // only needed if head is used farther down.
     
    James Kuyper, Aug 30, 2013
    #7
  8. Hans Vlems

    Eric Sosman Guest

    To the direct question, "No, not if each node was allocated
    with its own malloc() call." One free() call releases the memory
    obtained from one malloc() call (or realloc(), calloc(), etc.),
    but does not affect memory obtained from other calls.

    Freeing the nodes last-to-first is probably not the best way,
    especially if (as you suggest) the list may be long. First-to-last
    is usually better, if you'll exercise just a tiny bit of care:

    void freeList(struct node *head) {
    while (head != NULL) {
    struct node *next = head->link;
    free(head);
    head = next;
    }
    }

    The important bit is to retrieve each node's link field *before*
    releasing the node's memory, not after the memory's gone:

    void freeListINCORRECTLY(struct node *head) {
    while (head != NULL) {
    free(head);
    head = head->link; // NO! NO! NO!
    }
    }
     
    Eric Sosman, Aug 30, 2013
    #8
  9. Hans Vlems

    Nobody Guest

    If you use linked lists heavily, you may be better off implementing your
    own allocator, using malloc() (or something lower level, e.g. sbrk()) to
    supply larger blocks. E.g.

    struct node {
    void *data;
    struct node *next;
    };

    static struct node *free_list;

    static void more_nodes(void)
    {
    struct node *p = malloc(NUM_NODES * sizeof(struct node));
    if (!p)
    return p;
    for (int i = 0; i < NUM_NODES-1; i++)
    p.next = &p[i+1];
    p[NUM_NODES-1].next = free_list;
    free_list = p;
    }

    struct node* alloc_node(void)
    {
    if (!free_list)
    more_nodes();
    struct node *p = free_list;
    if (p)
    free_list = p->next;
    return p;
    }

    void free_node(struct node* p)
    {
    p->next = free_list;
    free_list = p;
    }
     
    Nobody, Aug 30, 2013
    #9
  10. You have to have a free() call for each malloc() call, but the free()
    calls don't have to be in any particular order. (I know you didn't say
    otherwise; I'm just clarifying.)
     
    Keith Thompson, Aug 30, 2013
    #10
  11. Hans Vlems

    Eric Sosman Guest

    Nobody didn't explain why "you may be better off," so I'll
    try to explain the reasoning. If malloc() adds a fixed overhead
    to each allocation (this is common, but not universal), and if
    the node is small so the overhead inflates its size significantly,
    and if the nodes are very numerous, then the overhead may become
    bothersomely large. For example, if malloc() adds an extra eight
    bytes to each allocation and the nodes are only eight bytes long,
    the overhead essentially doubles the memory use.

    In such a case it may be helpful to malloc() big batches of
    nodes and sub-allocate them as Nobody describes. If you ask
    malloc() for 8000 bytes (intending to use them for 1000 eight-
    byte nodes) and malloc() adds eight bytes of its own, the extra
    eight bytes inflate memory use by only 0.1% instead of by 100%.
    (There may also be a benefit in making one one-thousandth as many
    malloc() and free() calls; the sub-allocator has a simpler job
    to do, and may be able to do it faster.)

    However, this is not a strategy to be used indiscriminately.
    Remember, you can only free() what you malloc() -- *exactly*
    what you malloc(). You can return an unused node to the pool
    as Nobody shows, but you can't free() it; you can only free()
    the entire 8000-byte block along with all the nodes it holds.
    If you'd like to discard the block but it still holds one in-use
    node, that single eight-byte node "pins" the entire block so
    you cannot free() it.

    There are circumstances where these tradeoffs can actually
    be advantageous. I'm not saying "Don't Do That," just "Be Aware"
    that Nobody's approach is not a drop-in replacement for using
    malloc() and free() on individual nodes.
     
    Eric Sosman, Aug 30, 2013
    #11
  12. While what you say is technically true in the "C standards documents"
    sense, it is, like most of the things you post, nonsensical in context.

    Or, to put it another way, you didn't understand what the previous poster
    wrote.
     
    Kenny McCormack, Aug 30, 2013
    #12
  13. The other factor is speed.

    If you look at my book Basic Algorithms you'll find a fixed block allocator.
    It's simple to write, and each allocation is just a few machine instructions.
    (It's a linked list in its own right).

    See Basic Algorithms and much more:
    http://www.malcolmmclean.site11.com/www
     
    Malcolm McLean, Aug 30, 2013
    #13
  14. Hans Vlems

    Nobody Guest

    It's not just memory usage, but speed as well.
     
    Nobody, Sep 1, 2013
    #14
  15. Hans Vlems

    Eric Sosman Guest

    From the part you snipped:
     
    Eric Sosman, Sep 1, 2013
    #15
  16. Hans Vlems

    Hans Vlems Guest

    Op vrijdag 30 augustus 2013 16:37:35 UTC+2 schreef Nobody:


    I considered doing that but the data stored in the various kinds of linked lists comes from Excel sheets in the guise of csv files. The contents differ widely, from as little as 2500 records to nearly 200.000.
    The overhead in elapsed (which the user notices) is negligible. Memory usage my be different, I have no easy way to observe that on a Windows system without access to task manager or top.
    Hans
     
    Hans Vlems, Sep 2, 2013
    #16
  17. Hans Vlems

    Hans Vlems Guest

    Op vrijdag 30 augustus 2013 14:51:50 UTC+2 schreef Eric Sosman:
    That's a classic tradeoff, right :). The algorithm is either head-to-tail,as you do and you need to declare temporary storage or recursively, in which case the no additional declaration is needed at the expense of a growingstack. In both cases memory is used.
    Hans
     
    Hans Vlems, Sep 2, 2013
    #17
  18. Hans Vlems

    Hans Vlems Guest

    Op vrijdag 30 augustus 2013 18:00:55 UTC+2 schreef Eric Sosman:
    Eric, thank you for your comments. I must admit that the overhead possibly incurred by malloc() never even crossed my mind. The program is interactive, the user must select input files and select one option on how to manipulate them.
    All I cared for were fast response times... And even in the case where 149000 records are loaded, 48 fileds per record doesn't seem to slow down the system.
    That is the advantage of systems with cpu's that run in GHz's and memory available in GB's.
    Using "classical" programming techniques properly, the underlying processing system is hardly worth considering. Not like it was on a PDP 11/40 with 32 kB memory or a B7700 with "just" three processors and 1 MW main storage.Recursion with little overhead runs real fast on modern Intel gear!
    Hans
     
    Hans Vlems, Sep 2, 2013
    #18
  19. Hans Vlems

    Eric Sosman Guest

    Yes, memory is used -- but how much? For a list of N nodes,
    last-to-first uses memory proportional to N to keep track of its
    recursion[*], while first-to-last uses the same constant amount
    of memory (two pointers' worth) no matter how long the list is.

    [*] A different last-to-first algorithm also uses constant
    memory, but running time proportional to the *square* of N.
     
    Eric Sosman, Sep 2, 2013
    #19
  20. I don't think you can say that without qualification, even in the
    context of C. gcc can do tail-call optimisation and I've just checked
    that I can write a recursive reverse-order freeing function that uses
    constant extra space.
    And yet another (very similar to the code you'd write to reverse a list
    in-place) has linear running time and uses constant space. You've be
    within your rights to call this a front-to back freeing of a reversed
    list (slightly optimised), but it does free the nodes in reverse order.
    Another way to look at it is that since a C linked-list can be reversed
    in place in linear time with constant storage, there's no significant
    difference between freeing the nodes in either order.
     
    Ben Bacarisse, Sep 2, 2013
    #20
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.