CODEWITHSUNDEEP
cvalgrindfreesingly-linked-list
i-need-pointers
i-need-pointers

Reputation: 63

Invalid free() error when freeing memory of a singly-linked list

In C, I am trying to free all memory in a singly-linked list, the structure of which is:

typedef struct node {
  char *data;
  int weight;
  struct node *next;
} Node;

The last element has a next field of NULL. Every node as well as its data field is dynamically allocated. My function so far is:

void free_list(Node *const list) {
  Node *current = list;
  Node *temp;

  while (current != NULL) {
    temp = current;
    current = current->next;

    free(temp->data);
    free(temp);
  }
}

When I run one of my tests on valgrind, I can see that all heap blocks were freed, so certainly no memory is leaked, which is the goal. However, valgrind throws me an Invalid free() error, and I cannot figure out why. Curiously, when I remove the line free(temp) this error goes away, but I am now leaking memory. So that line is both essential and problematic. Where have I gone wrong?

Adding more code to make a reproducible example.

Nodes are added to the list using:

unsigned int add(Node *const head, const char new_data[], unsigned int weight) {
  Node *current = head;
  Node *new_node = malloc(sizeof(Node));
  char *new_data_copy = malloc(strlen(new_data) + 1);

  strcpy(new_data_copy, new_data);

  /* this loop moves the current pointer to the point where the new element
  should be inserted, since this is a sorted list. */
  while (current->next != NULL && current->next->weight < weight) {
    current = current->next;
  }

  new_node->data = new_data_copy;
  new_node->weight = weight;
  new_node->next = current->next
  current->next = new_node;

  return 1;
}

The list is always initialized before I invoke anything, with the values NULL, -1, and NULL for the data, weight, and next fields.

As you can see the list is order lowest weight to highest weight. There may be more bugs I have to work out which is why I tried to cut down the problem to isolate my specific problem with valgrind.

Edit: valgrind is showing me 12 allocs and 13 frees, so there is a stray free somewhere...

Edit 2: how is the head created? In the main, Node head is declared and then initialize(&head) is called.

void initialize(Node *const head) {
  head->data = NULL
  head->weight = -1;
  head->next = NULL
}

A main

#include "structure.h"
int main(void) {
  Node head;
  char *data[] = {"A","B","C","D","E","F"};
  int weight[] = {1, 2, 3, 4, 5, 6};
  int i;

  initialize(&head);

  for (i = 0; i< 6; i++) {
    add(&head, data[i], weight[i]);
  }

  free_list(&head);
  return 0;
}

Upvotes: 0

Views: 479

Answers (1)

Schwern
Schwern

Reputation: 164659

free is only for things allocated on the heap with malloc. If you allocate something on the stack its memory is managed for you.

Probably something like this happened.

// The first Node is allocated on the stack
Node list = { .data="test", .weight=23 };

// The rest are heap allocated.
add(list, "new", 42);

// free_list calls free() on all of them
free_list(list);

You can avoid this by extracting the code to create a new node from add.

Node *new_node( const char *data, int weight ) {
    Node *node = malloc(sizeof(Node));
    node->data = strdup(data);
    node->weight = weight;
    return node;
}

Then this can be used to initialize the list, and also to pass into add. This makes it easier to ensure every Node is allocated on the heap. And it makes add more useful, it can add any existing node.

Node *add(Node *current, Node *new_node) {
  while (current->next != NULL && current->next->weight < weight) {
    current = current->next;
  }

  new_node->next = current->next;
  current->next = new_node;

  // Might be useful to know where the node was added.
  return current;
}

Node *list = new_node("test", 23);
add(list, new_node("new", 42));
free_list(list);

(I'm on a phone, apologies for any mistakes.)

Upvotes: 3

Related Questions