C、free sub-list element by element导致意外行为

Question

我在另一个链表中有一个链表，类型定义如下：

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是另一个链表：

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

我实现了一个 insert() 方法来创建一个新的 list_ex 元素并将其插入列表的头部。我尝试运行一个简单的测试代码来查看内存管理是否正常：

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);

}

要释放所有 exhead 元素，我需要先释放相关子列表。由于 rhead（exhead 的子列表）也是一个链表（使用 malloc() 分配），我认为它应该逐个元素地释放。这是我使用的代码：

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);
    }
}

问题是 当我编译这段代码时，Visual Studio 在指示的行中触发一个断点。当我逐步调试时，代码运行s 直到 free_run_str_list(tmp->runstr); 进入调用并执行第一个 free(tmp)。现在 tmp 里面有随机值（因为它应该是）而且 head 也有相同的随机值，并且在第二次迭代时，行 free(temp) 试图释放已经释放的内存导致（我猜）发生的错误。

所以我的问题是：

为什么会这样？
是不是分配内存的时候出错了？（如果是这种情况，我会在下面留下插入代码）
这是释放 exhead 的正确方法吗？

我搜索了类似的解决方案，但我认为我遇到了不同的问题。

Here 问题是 malloc() 没有为终止字符分配足够的 space （不是我的情况：我有一个喜欢的字符列表作为子列表，而不是字符串指针）。
不知道为什么，但是如果我在 free_ex_list() 中用 free(tmp->runstr) 替换 free_run_str_list(tmp->runstr); 则不会触发断点（但我不确定这是正确的方法：只释放头部子链表的？）。

插入代码：

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;
}

感谢您的帮助。

编辑

这是导致问题的确切代码，我尽可能地简化了它。

代码：

#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

从您发布的代码来看，问题出在函数 duplicate 中。它将变量 len 设置为要复制的列表的长度，并调用 malloc 分配 list_run_str 的 len 个元素块。然后它填充这些元素并将它们连接到一个 list_run_str 的链表中，做一些其他的事情并且 return 是指向第一个元素的指针。

据推测，函数 duplicate 的 return 值最终出现在 list_ex 的 runstr 成员中。

从 free_list_ex 调用的 free_run_str_list 函数对链表的每个项目调用 free。如果这个链表是由函数 duplicate 构造的，那么第一次调用 free 将释放整个块。但是，您正在单独释放链接列表的每个项目，即使它们都是通过对 malloc.

的一次调用分配的

要修复它，您应该将 duplicate 函数更改为单独 malloc 链表的每个项目，因为这是 free_run_str_list 函数所期望的。

C、free sub-list element by element导致意外行为

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

c

free