Malloc and free in double recursion

Question

I was playing with C code when i encountered the following problem. I have a code that looks like this:

#include <stdio.h>
#include <stdlib.h>

typedef struct a {
  int n1;
  int n2;
} el;

typedef struct list {
  el *elements;
  int nElements;
} list;

void copyList(list in, list *out) {
    int i;
    for(i = 0; i < in.nElements; i++) {
        out->elements = realloc(out->elements,sizeof(el)*(out->nElements + 1));
        out->elements[i] = in.elements[i];
        out->nElements = out->nElements + 1;
    }
}

void initList(list *l) {
    l->nElements = 0;
    l->elements = NULL;
}

void freeList(list *l) {
    l->nElements = 0;
    if(l->elements != NULL) {
        free(l->elements);
        l->elements = NULL;
    }
}

void testRecur(int i, list l) {
    list l1;

    if(i > 0) {
        initList(&l1);
        copyList(l,&l1);
        // freeList(&l);
        testRecur(i-1,l1);
        testRecur(i-2,l1);
        // freeList(&l1);
    }
    else {
        // freeList(&l);
    }

}

int main(void) {
  list l1;
  list l2;
  el element;

  initList(&l1);
  initList(&l2);

  l1.elements = malloc(sizeof(el)*2);
  l1.nElements = 2;

  element.n1 = 1;
  element.n2 = 2;
  l1.elements[0] = element;

  element.n1 = 3;
  element.n2 = 4;
  l1.elements[1] = element;

  testRecur(10,l1);

  // freeList(&l1);

  return 0;
}

It is a simple code that copies recursively a list a certain number of times. It has no sense but it is easy enough to explain the concept. The problem is: where should i place the free calls? I've tried all the combinations of the commented spots but i end up having a double free error (*** Error in ./a.out: double free or corruption (fasttop): 0x0000000001ecd010 ***) or a memory leak detection with valgrind (with the following arguments: valgrind --tool=memcheck --leak-check=yes --show-reachable=yes --num-callers=20 --track-fds=yes ./a.out). Is there a way to not leak memory (at least according to valgrind)?

Answer 1

The solution is to remove all occurences of freeList(&l); from testRecur() function.

Explanation:

A good practice while using alloc(and its variants) and free is to try to do both in same scope. In your example, the functions which are allocating memories to list are in main() and copyList().

1.main() function allocation and de-allocation can be done in same scope easily:

int main(void) {
  /*
   Initialization code
  */
  // Allocation
  l1.elements = malloc(sizeof(el)*2);
  l1.nElements = 2;
  /*
   Process list l1, but dont play with its memory.
   A thumb rule can be to pass l1(by reference) as const
  */

  // De-allocation
  freeList(&l1);

  return 0;
}

2.copyList(): As per code, we cant free list in copyList itself as we need it later. So we do the next best thing - de-allocate in the function which called copyList. Think of copyList having two parts - allocation and copying.

void testRecur(int i, list l) {
    list l1;

    if(i > 0) {
        initList(&l1);
        /* memory will be allocated in copyList. 
           So, allocation scope starts here */
        copyList(l, &l1);
        /* Process list l1, but again, dont play with its memory */
        testRecur(i-1,l1);
        testRecur(i-2,l1);
        /* Now l1 is no more required, its scope is finished.
           We can free l1. */
        freeList(&l1);
    }
}

Note: This is not related to allocate and free, but passing structure(list) as value is of no significance in your example, so its better to pass list by reference in function testRecur().