SIGABRT while attempting to free a linked list

Question

I was working on some older texts our professor gave us to prepare for the upcoming exam, and I ran into this problem.

My task is to read information from a text file which is structured as follows:

[decimal number],[roman number (string)],[o or u (optimized or unoptimized roman number)]

for a few thousand lines and store that information in a binary search tree, using the decimal number as key. Each branch must also contain the number of occurences of that number and a list of the various roman versions encountered, with the optimized one at the top of the list. Then free everything.

My code (in c):

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

struct list //list node
{
  char *rom;
  struct list *next;
};

struct branch //main tree branch
{
  int count, dec;
  struct list *list;
  struct branch *right, *left;
};

struct list *insertnode(struct list *head, char *rom, char opt) //creates a head or creates and adds a new node to the end
{
  struct list *new;
  if(!head) //if !head, make one
    {
      new = malloc(sizeof(new));
      new->rom = malloc(sizeof(char)*(strlen(rom)+1));
      strcpy(new->rom, rom);
      new->next = NULL;
      return new;
    }
  if(opt == 'o') //if the roman form is optimized, put it in front of all the others
    {
      new = malloc(sizeof(new));
      new->rom = malloc(sizeof(char)*(strlen(rom)+1));
      strcpy(new->rom, rom);
      new->next = head;
      return new;
    }
  head->next = insertnode(head->next, rom, opt); //recursive insertions
  return head;
}

struct branch *insertbranch(struct branch *root, int dec, char *rom, char opt) //creates a root or creates and adds a new branch
{
  struct branch *new;
  if(!root) //if !root, make a root...
    {
      new = malloc(sizeof(new));
      new->list = insertnode(new->list, rom, opt);
      new->dec = dec;
      new->count = 1;
      new->right=new->left=NULL;
      return new;
    }
  if(dec<root->dec) root->left = insertbranch(root->left, dec, rom, opt); //branch on the left, recursive
  else if(dec>root->dec) root->right = insertbranch(root->right, dec, rom, opt); //branch on the right, recursive
  else //if there already is such a branch, increase its count
    {
      root->count += 1;
      root->list = insertnode(root->list, rom, opt);
    }
  return root;
}

void freelist(struct list *head) //frees list 'head'
{
  struct list *tmp;
  while(head)
    {
      tmp = head;
      head = head->next;
      free(tmp->rom);
      free(tmp); // <- OFFENDING LINE
    }
  return;
}

void freetree(struct branch *root) //frees tree 'root'
{
  if(!root) return;
  freetree(root->left); //recursive!
  freetree(root->right); //and on the right
  free(root->right);
  free(root->left);
  freelist(root->list);
  free(root);
  return;
}

int main()
{
  struct branch *root;
  struct list *list;
  int dec, i=1, n;
  char rom[30], opt;
  FILE *file = fopen("rom.csv", "r");
  if(!file) //is the file even there?
    return 1;

  while(fscanf(file, "%d,%[^,],%c\n", &dec, rom, &opt)==3) //go through the file and fill tree
    root = insertbranch(root, dec, rom, opt);

  freetree(root);
  printf("Goodbye!\n");
  return 0;
}

After debugging I isolated the problem: in function "freelist", when it reaches the command "free(tmp)" the program aborts. I have no idea what the cause could be. I even check to make sure that the node head exists.

Thanks for any help!

Answer 1

You aren't allocating the correct amount of memory in insertnode() and insertbranch().

You need to replace this:

new = malloc(sizeof(new));

With:

new = malloc(sizeof(*new));

This is because new is a pointer. With malloc(sizeof(new)), you're only allocating space to store a pointer, rather than the necessary space to store the contents of your struct.

Here's the correct version of these functions:

struct list *insertnode(struct list *head, char *rom, char opt) //creates a head or creates and adds a new node to the end
{
    struct list *new;
    if(!head) //if !head, make one
    {
        new = malloc(sizeof(*new));
        new->rom = malloc(sizeof(char)*(strlen(rom)+1));
        strcpy(new->rom, rom);
        new->next = NULL;
        return new;
    }
    if(opt == 'o') //if the roman form is optimized, put it in front of all the others
    {
        new = malloc(sizeof(*new));
        new->rom = malloc(sizeof(char)*(strlen(rom)+1));
        strcpy(new->rom, rom);
        new->next = head;
        return new;
    }
    head->next = insertnode(head->next, rom, opt); //recursive insertions
    return head;
}

struct branch *insertbranch(struct branch *root, int dec, char *rom, char opt) //creates a root or creates and adds a new branch
{
    struct branch *new;
    if(!root) //if !root, make a root...
    {
        new = malloc(sizeof(*new));
        new->list = insertnode(new->list, rom, opt);
        new->dec = dec;
        new->count = 1;
        new->right=new->left=NULL;
        return new;
    }
    if(dec<root->dec) root->left = insertbranch(root->left, dec, rom, opt); //branch on the left, recursive
    else if(dec>root->dec) root->right = insertbranch(root->right, dec, rom, opt); //branch on the right, recursive
    else //if there already is such a branch, increase its count
    {
        root->count += 1;
        root->list = insertnode(root->list, rom, opt);
    }
    return root;
}

I didn't thoroughly look at every line of code, but it looks mostly right. From the quick look I had, your only mistake is to allocate less memory than you use. The results of writing past allocated memory are unpredictable and can manifest much later in the program (such as when freeing memory). This is why undefined behavior is so hard to debug :)

Answer 2

I found the problem. After the recursive call to freetree I attempt to free the same memory again in the form of free(root->left) and free(root->right). I feel a bit silly now.