Memory leak in insert in sorted linked list

Question

I have used a function my professor provided that inserts data (ints) in a sorted linked list.

void sorted_insert(int x,node_t **list)
{
  node_t *q = NULL, *pq = NULL, *new_node = NULL;

  q = *list;

  while (q && x > q->data)
  {
    pq = q;
    q = q->next;
  }

  new_node = malloc(sizeof(node_t));
  new_node->data = x;
  new_node->next = q;

  if (!pq) { *list = new_node; }
  else { pq->next = new_node; }

}

Main calls:

node_t *list = NULL
sorted_insert(x,&list);

I have tested it by saving 100 random integers to and it is doing what is expected to , as the numbers are sorted. I later used a custom free function to free each node, like so:

void free_list(node_t *list)
{
  node_t *tmp = NULL;

  for (; list; list = list->next)
  {
    tmp = list;
    free(tmp);
  }
  return;
}

However, when I analyze the program with valgrind, it is showing that I am leaking memory in function sorted_insert , and to be precise, on this line: new_node = malloc(sizeof(node_t));

Valgrind output:

==9478== 160 (16 direct, 144 indirect) bytes in 1 blocks are definitely lost in loss record 2 of 2
==9478==    at 0x483C7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==9478==    by 0x109270: sorted_insert (list_insert_sorted.c:23)
==9478==    by 0x10938D: main (list_insert_sorted.c:55)

Why is this happening? Is there something wrong with my free function? Thank you in advance.

EDIT: I have changed the for loop, and even thoug im not skipping nodes, im still leaking memory.

Answer 1

Your free iterator is skipping nodes, your loop body has list=list->next, and so does the iterator, so it happens twice. you're lucky you had an even number of nodes, avoiding dereferencing a NULL pointer if you had had an odd number.

void free_list(node_t *list)
{
  node_t *tmp = list;

  while(tmp)
  {
    list = list->next;
    free(tmp);
    tmp = list;
  }
  return;
}

You then edited the code to removed the duplicate iterator, but in your edited code, after free(tmp), the memory list points to is no longer valid (same address as tmp after all), and your edited code dereferences the just freed memory that list points to in the iterator, so try what I wrote instead.