0

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;
}
mcalabresi
  • 37
  • 6
  • 3
    Please try to create a [Minimal, Complete, and Verifiable Example](http://stackoverflow.com/help/mcve) to show us. Preferably as a single block of code. And that should include all variables and also all input data you feed to the program. If possible, make a simplified input handlinmg, using some static compile-time fixed input that leads to the problem (also [read about finding a simpler problem](https://ericlippert.com/2014/03/21/find-a-simpler-problem/)). And of course [learn how to debug your programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). – Some programmer dude Aug 14 '18 at 15:27
  • 2
    "Visual Studio triggers a break point". I dont think you mean that. I think you mean that you get an error message.Cam you please include the message – pm100 Aug 14 '18 at 15:28
  • @pm100 Visual Studio does break (as in, interrupt execution) when it detects certain kinds of problems via assertions or fences, so I suspect this is what he's referring to. Knowing the message that appears in Visual Studio would still be helpful though. – TypeIA Aug 14 '18 at 15:44
  • @Some programmer dude, ok working on it – mcalabresi Aug 14 '18 at 15:46
  • @pm 100, thanks for reply, this is all i get from VS, sorry the language is italian: https://ibb.co/jKfL39 – mcalabresi Aug 14 '18 at 15:48
  • @TypeIA 'break point' in an IDE has a very specific meaning. This is not it – pm100 Aug 14 '18 at 15:52
  • What is `rheadone` (and the other three variables in `main`) ? – Support Ukraine Aug 14 '18 at 16:02
  • edited my question, hope my code is clear enough – mcalabresi Aug 14 '18 at 16:24
  • 3
    In `duplicate()`, you allocated an array with a single `malloc` and you are trying to `free` the elements individually in `free_run_str_list()`. You should only `free` exactly what you `malloc`ed. – Ian Abbott Aug 14 '18 at 16:25
  • @IanAbbott, so I need to change the whole code of free_sun_str_list() with free(head) because I allocated all the memory at once? (my questions could soud stupid but I'm a student and I'm trying to understand how memory managment works...thanks.) – mcalabresi Aug 14 '18 at 16:35
  • 1
    You cannot allocate a list element-by-element and then "duplicate" it by allocating an entire array of elements and then pretend you have a well defined data type. If you want to define a linked list or any other data type, decide on *one* way to allocate it and *one* way to free it. – n. m. could be an AI Aug 14 '18 at 16:41
  • 1
    Basically, you cannot `free` the middle of a block allocated by `malloc`. You can only `free` the start of the block, and it frees the whole block that was allocated by `malloc`. – Ian Abbott Aug 14 '18 at 16:46
  • 1
    You are writing out of bounds in the `duplicate` function. That destroys the value of `newmarker` – Support Ukraine Aug 14 '18 at 16:48
  • @pm100 I understood perfectly what the OP meant and I don't think anything is to be gained by terminological pedantry in this case. – TypeIA Aug 14 '18 at 23:50

1 Answers1

2

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.

Ian Abbott
  • 15,083
  • 19
  • 33