C, free sub-list element by element causes unexpected behavior

Question

I have a a linked list inside another linked list, typedefs are the following:

typedef struct struct_execution_queue {

    list_run_str *runstr;
    list_run_str *marker; //just a pointer to a specific element in runstr (it was not allocated with `malloc()`)

    int excount;

    struct struct_execution_queue *next;
}list_ex;

list_run_str is another linked list:

typedef struct struct_run_str { //run element
    char car;
    struct struct_run_str *next;
    struct struct_run_str *prev;
} list_run_str;

I implemented an insert() method that creates a new list_ex element and insert it in the head of the list. I tried to run a simple test code to see if memory management was ok:

int main(){
/*read data from input file and insert into lists (this part is ok)
I have all data I need: two rheads and two markers
*/
list_ex *exhead = NULL;

exhead = insert(exhead, rheadone, markerone, 10);
exhead = insert(exhead, rheadtwo, markertwo, 20);

free_ex_list(exhead);

}

To free all exhead elements I need to free the relative sublist first. Since rhead (sublist of exhead) is a linked list too (allocated with malloc()), I think it sould be freed element by element. This is the code I use:

void free_run_str_list(list_run_str *head) { //free a list_run_str list
    list_run_str *tmp;

    while (head != NULL) {
        tmp = head;
        head = head->next;
        free(tmp);
    } // <--------------------- breackpoint triggered here
}

void free_ex_list(list_ex *head) { //free a list_ex list
    list_ex *tmp;

    while (head != NULL) {
        tmp = head;
        free_run_str_list(tmp->runstr);
        head = head->next;
        free(tmp);
    }
}

The problem is when I compile this code, Visual Studio triggers a break point in the indicated line. When I debug step by step, the code runs until free_run_str_list(tmp->runstr); enters the call and does the first free(tmp). Now tmp has random values inside it (as it sould be) but also head has the same random values and, at the second iteration, the line free(temp) tries to free already freed memory causing (i guess) the error to occur.

So my questions are:

1. Why this happens?
2. Does it means an error while allocating memory? (if this is the case i leave the insert code below)
3. Is this the right way to free exhead?

I searched for similar solutions but I think I have a different issue.

• Here the issue was malloc() not allocating enough space for terminating character (not my case: i have a liked list of chars as sublist, not a string pointer).
• Not shure why but if I replace free_run_str_list(tmp->runstr); with free(tmp->runstr) in free_ex_list() no break points are triggered (but I am not shure this is the proper way: free only the head of the sub-linked list?).

Insert code:

list_ex *insert(list_ex *exhead, list_run_str *rhead, list_run_str *marker, int count) {
    list_ex *tmp;
    list_run_str *tmphead, *tmpmarker;

    if ((tmp = (list_ex *)malloc(sizeof(list_ex)))) {

        tmphead = duplicate(rhead, marker, &tmpmarker);
        tmp->runstr = tmphead;
        tmp->marker = tmpmarker;

        tmp->excount = count;

        tmp->next = exhead;
        exhead = tmp;
    }
    else
        printf("insert mem error\n");
    return tmp;
}



list_run_str *duplicate(list_run_str *head, list_run_str *marker, list_run_str **newmarker) { //duplicate a list_run_str_list and the relative marker
    list_run_str *newhead, *newtmphead, *tmphead;
    int markerpos, len, i;

    //find list length
    for (len = 0, tmphead = head; tmphead != NULL; len++, tmphead = tmphead->next);

    //find marker position in head
    markerpos = 0;
    if (marker != NULL)
        for (tmphead = marker; tmphead->prev != NULL; markerpos++, tmphead = tmphead->prev);

    //create new list_run_str list
    if ((newhead = (list_run_str *)malloc(sizeof(list_run_str) * len))) {
        i = 0;
        //load the new head
        newtmphead = newhead;
        tmphead = head;

        (newtmphead + i)->prev = NULL;
        (newtmphead + i)->next = (newtmphead + i + 1);
        (newtmphead + i)->car = tmphead->car;

        //load other elements
        for (i++, tmphead = tmphead->next; tmphead != NULL; i++, tmphead = tmphead->next) {
            (newtmphead + i)->car = tmphead->car;
            (newtmphead + i)->next = (newtmphead + i + 1);
            (newtmphead + i)->prev = (newtmphead + i - 1);
        }
        ((newtmphead)+len - 1)->next = NULL;

        //update the new marker
        for (i = 0, newtmphead = newhead; i < markerpos; i++, newtmphead = newtmphead->next);
        *newmarker = newtmphead;
    }
    else
        printf("duplicate mem error\n");
    return newhead;
}

Thanks for help.

EDIT

here is the exact code that causes the issue, i tried to simplify it as much as i could.

Code:

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

typedef struct struct_run_str {
    char car;
    struct struct_run_str *next;
    struct struct_run_str *prev;
} list_run_str;

typedef struct struct_execution_queue {
    list_run_str *runstr; //this will be allocated with malloc()
    list_run_str *marker; //this is only a pointer to a certain element in runstr

    int excount;

    struct struct_execution_queue *next;
}list_ex;

void free_run_str_list(list_run_str *head) { //free a "list_run_str" list
    list_run_str *tmp;

    while (head != NULL) {
        tmp = head;
        head = head->next;
        free(tmp);
    }
}

void free_ex_list(list_ex *head) { //free a "list_ex" list
    list_ex *tmp;

    while (head != NULL) {
        tmp = head;
        free_run_str_list(tmp->runstr);
        head = head->next;
        free(tmp);
    }
}

list_run_str *loadrunstr(list_run_str *head, char c) { //add an item at the ed of a "list_run_str" list
    list_run_str *tmp, *tmphead;

    if ((tmp = (list_run_str *)malloc(sizeof(list_run_str)))) {
        tmp->car = c;
        tmp->next = NULL;

        if (head == NULL) {
            tmp->prev = NULL;
            head = tmp;
        }
        else {
            for (tmphead = head; tmphead->next != NULL; tmphead = tmphead->next);
            tmphead->next = tmp;
            tmp->prev = tmphead;
        }
    }
    else
        printf("loadrunstr mem error\n");
    return head;
}

list_run_str *duplicate(list_run_str *head, list_run_str *marker, list_run_str **newmarker) { //duplicte head to newhed and adjust newmarker
    list_run_str *newhead, *newtmphead, *tmphead;
    int markerpos, len, i;

    //find list length
    for (len = 0, tmphead = head; tmphead != NULL; len++, tmphead = tmphead->next);

    //find marker position
    markerpos = 0;
    if (marker != NULL)
        for (tmphead = marker; tmphead->prev != NULL; markerpos++, tmphead = tmphead->prev);

    //create new "list_run_str" list
    if ((newhead = (list_run_str *)malloc(sizeof(list_run_str) * len))) {
        i = 0;
        //load the head
        newtmphead = newhead;
        tmphead = head;

        (newtmphead + i)->prev = NULL;
        (newtmphead + i)->next = (newtmphead + i + 1);
        (newtmphead + i)->car = tmphead->car;

        //load the other elements
        for (i++, tmphead = tmphead->next; tmphead != NULL; i++, tmphead = tmphead->next) {
            (newtmphead + i)->car = tmphead->car;
            (newtmphead + i)->next = (newtmphead + i + 1);
            (newtmphead + i)->prev = (newtmphead + i - 1);
        }
        ((newtmphead)+len - 1)->next = NULL;

        //update new marker position
        for (i = 0, newtmphead = newhead; i < markerpos; i++, newtmphead = newtmphead->next);
        *newmarker = newtmphead;
    }
    else
        printf("duplicate mem error\n");
    return newhead;
}

list_ex *insert(list_ex *exhead, list_run_str *rhead, list_run_str *marker, int count) { //insert new element in the head of a "list_ex" list
    list_ex *tmp;
    list_run_str *tmphead, *tmpmarker;

    if ((tmp = (list_ex *)malloc(sizeof(list_ex)))) {

        tmphead = duplicate(rhead, marker, &tmpmarker);
        tmp->runstr = tmphead;
        tmp->marker = tmpmarker;

        tmp->excount = count;

        tmp->next = exhead;
        exhead = tmp;
    }
    else
        printf("insert mem error\n");
    return tmp;
}

int main() {
    list_ex *exhead;
    list_run_str *rheadone, *markerone, *rheadtwo, *markertwo;

    exhead = NULL;
    rheadone = NULL;
    rheadtwo = NULL;

    //load some items in rheadone
    rheadone = loadrunstr(rheadone, 'a');
    rheadone = loadrunstr(rheadone, 'b');
    rheadone = loadrunstr(rheadone, 'c');

    //load some items in rheadtwo
    rheadtwo = loadrunstr(rheadtwo, 'd');
    rheadtwo = loadrunstr(rheadtwo, 'e');
    rheadtwo = loadrunstr(rheadtwo, 'f');

    //set markerone to point at some char in rheadone
    markerone = rheadone->next; //points to 'b'

    //set markertwho to point at some char in rheadtwo
    markertwo = rheadtwo; //points to 'd'

    //insert two new elements into exhead
    exhead = insert(exhead, rheadone, markerone, 10);
    exhead = insert(exhead, rheadone, markerone, 20);

    //try to free them
    free_ex_list(exhead);

    return 0;
}

Answer 1

From your posted code, the problem is in function duplicate. It sets variable len to the length of the list to be duplicated, and calls malloc to allocate a block of len elements of list_run_str. It then fills in those elements and joins them together into a linked list of list_run_str, does some other stuff and returns a pointer to the first element.

Presumably, the return value of function duplicate ends up in the runstr member of a list_ex.

Your free_run_str_list function called from free_list_ex calls free on each item of the linked list. If this linked list was constructed by function duplicate then the first call to free will free the entire block. However, you are freeing each item of the linked list individually even though they were all allocated from a single call to malloc.

To fix it, you should change your duplicate function to malloc each item of the linked list individually, since that is what the free_run_str_list function expects.