Malloc 不应在此结构实例化上 return NULL

Malloc shouldn't return NULL on this struct instantiation

我正在研究一个以图为主题的挑战问题,所以我决定实现一个多重链表(这种数据结构可以表示有向图)。当我尝试为列表创建节点时,我 运行 遇到了问题。该程序编译正常,但是当它运行时,它只会运行到某个点并在没有警告的情况下退出。 运行 它在 VS2019 中处于调试模式,IDE 告诉我我正在尝试取消引用空指针。事实上,甚至在它编译之前,它就会在可疑行下划线并警告可能会发生这种情况。但我根本不明白为什么。下面是链表的实现(最小工作示例,意思是最小,我尽力了...):

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

typedef unsigned int uint;

typedef struct Node {
    uint id;
    uint data;
    size_t num_parents;
    size_t size_parents;
    struct Node * parents;
    size_t num_children;
    size_t size_children;
    struct Node * children;
} Node;

/*/ ORIGINAL PROBLEMATIC REALLOCATING FUNCTION
Node * reallocate_node_array(Node * array, size_t* size) {
    Node * new_array = new_array(Node, *size * 2);  // this doesn't seem to be working as I expected
    for (size_t i = 0; i < *size; i++) {
        new_array[i] = array[i];                    // FAULTY LINE
    }
    *size *= 2;
    return new_array;
}
/**/
//NEW VERSION EDITED TO REFLECT CRAIG ESTEY'S COMMENTS AND ANSWER
Node * reallocate_node_array(Node * array, size_t* size) {
    array = realloc(array, (*size) * 2);
    if (array == NULL) {
        perror("realloc");
        exit(1);
    }
    *size *= 2;
    return array;
}

void remove_node(Node * array, size_t * size, size_t index) {
    for (int i = index; i < *size - 1; i++) {
        array[i] = array[i + 1];
    }
    (*size)--;
}

void remove_parent (Node * node, uint id) {
    for (int i = 0; i < node->num_parents; i++) {
        if (node->parents[i].id == id) {
            remove_node(node->parents, &node->num_parents, i);
        }
    }
}

void remove_child(Node * node, uint id) {
    for (int i = 0; i < node->num_children; i++) {
        if (node->children[i].id == id) {
            remove_node(node->children, &node->num_children, i);
        }
    }
}

void add_child(Node * node, Node * child) {
    if (node->num_children >= node->size_children) {
        node->children = reallocate_node_array(node->children, &node->size_children);
    }
    node->children[++node->num_children] = *child;
}

void add_parent(Node * node, Node * parent) {
    if (node->num_parents >= node->size_parents) {
        node->parents = reallocate_node_array(node->parents, &node->size_parents);
    }
    node->parents[++node->num_parents] = *parent;
}

int main() {
    char * file_name = "input.txt";

    FILE * data_file = fopen(file_name, "r");
    if (data_file == NULL) {
        printf("Error: invalid file %s", file_name);
        return 1;
    }

    uint num_nodes, num_relationships;

    fscanf(data_file, "%u %u\n", &num_nodes, &num_relationships);

    // I'm sorry that I'm not checking for the result of malloc in this block.
    // I promise I'll be more responsible in the future.
    Node * nodes = (Node*)malloc((num_nodes + 1) * sizeof(Node));
    for (size_t i = 1; i <= num_nodes; i++) {
        nodes[i].id = i;
        fscanf(data_file, "%u ", &nodes[i].data);
        nodes[i].num_children = 0;
        nodes[i].size_children = 10;
        nodes[i].children = (Node*)malloc(10 * sizeof(Node)); // FAULTY LINE #1
        nodes[i].num_parents = 0;
        nodes[i].size_parents = 10;
        nodes[i].parents = (Node*)malloc(10 * sizeof(Node));  // FAULTY LINE #2 
    }

    for (uint i = 0; i < num_relationships; i++) {
        uint parent_id, child_id;
        fscanf(data_file, "%u %u\n", &parent_id, &child_id);

        add_child(&employees[parent_id], &employees[child_id]);
        add_parent(&employees[child_id], &employees[parent_id]);
    }
    
    return 0;
}

在显示“FAULTY LINE #1”和“#2”的地方,调试器告诉我程序已到达断点(抛出异常)。

main函数的重点是构建如下结构(图): A directed graph with small number of nodes。最简洁的方法是从文件中读取指令。这是input.txt的内容:

7 8
21 33 33 18 42 22 26
1 2
1 3
2 5
3 5
3 6
4 6
4 7
6 7

第一行:7为节点数; 8是连接数(关系)。
所有其他行:左边的数字是父节点;右边的数字是子节点。

所以,我的问题 我无法通过 reallocate_node_array 函数以及后来的“FAULTY LINE #1”和“#2”。

编辑


所以我在上面进行了很多编辑,以提供一个最小的工作示例并进一步阐明我的背景和困难。不管我做错了什么,如果你能告诉我,我将不胜感激。

然而,在我根据 Craig Estey 的批评编辑了我的 reallocate_node_array 函数之后,我能够在调试中更进一步,并在上面的实现中发现了一些可怕的错误。最重要的是我的结构 Node 的字段 parentschildren 需要是类型 Node** 而不是 Node*,因为它们应该是数组以表示 多重链表 。考虑到这一点,我重写了如下实现, 的行为符合预期。然而,我 运行 遇到了使用此代码的进一步任务的问题,这些问题不在本问题的范围内。如果我要提出一个新问题,我一定会牢记您的所有批评,并在下次尝试写出一个好问题。

感谢大家的反馈。

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

typedef unsigned int uint;

typedef struct Node {
    uint id;                // identifier of the node
    int data;               // actual data
    size_t num_parents;     // actual number of parent nodes
    size_t size_parents;    // current maximum capacity of array of parent nodes
    struct Node** parents;  // all nodes that connect from "upstream"
    size_t num_children;    // actual number of child nodes
    size_t size_children;   // current maximum capacity of array of children nodes
    struct Node** children; // all nodes that connect "downstream"
} Node;

void reallocate_node_array(Node** array, size_t* size) {
    array = realloc(array, sizeof(Node*) * (*size) * 2);
    if (array == NULL) {
        perror("realloc");
        exit(1);
    }
    *size *= 2;
}

// The intention is to pass `num_children` or `num_parents` as `size` in order to decrease them
void remove_node(Node** array, size_t* size, size_t index) {
    for (size_t i = index; i < *size - 1; i++) {
        array[i] = array[i + 1];
    }
    (*size)--; // the decrement to either `num_children` or `num_parents`
}

void remove_parent(Node* node, uint id) {
    for (size_t i = 0; i < node->num_parents; i++) {
        if (node->parents[i]->id == id) {
            remove_node(node->parents, &node->num_parents, i);
        }
    }
}

void remove_child(Node* node, uint id) {
    for (size_t i = 0; i < node->num_children; i++) {
        if (node->children[i]->id == id) {
            remove_node(node->children, &node->num_children, i);
        }
    }
}

void add_parent(Node* node, Node* parent) {
    if (node->num_parents >= node->size_parents) {
        reallocate_node_array(node->parents, &node->size_parents);
    }
    node->parents[node->num_parents++] = parent;
}

void add_child(Node* node, Node* child) {
    if (node->num_children >= node->size_children) {
        reallocate_node_array(node->children, &node->size_children);
    }
    node->children[node->num_children++] = child;
}

int main() {
    char* file_name = "input.txt";

    FILE* data_file = fopen(file_name, "r");
    if (data_file == NULL) {
        printf("Error: invalid file %s", file_name);
        return 1;
    }

    uint num_nodes, num_relationships;
    fscanf(data_file, "%u %u\n", &num_nodes, &num_relationships);

    Node* nodes = (Node*)malloc((num_nodes + 1) * sizeof(Node));
    for (size_t i = 1; i <= num_nodes; i++) {
        nodes[i].id = i;
        fscanf(data_file, "%u ", &nodes[i].data);
        nodes[i].num_children = 0;
        nodes[i].size_children = 10;
        nodes[i].children = (Node**)malloc(10 * sizeof(Node*));
        for (size_t j = 0; j < 10; j++) nodes[i].children[j] = (Node*)malloc(sizeof(Node));
        nodes[i].num_parents = 0;
        nodes[i].size_parents = 10;
        nodes[i].parents = (Node**)malloc(10 * sizeof(Node*));
        for (size_t j = 0; j < 10; j++) nodes[i].parents[j] = (Node*)malloc(sizeof(Node));
    }

    for (uint i = 0; i < num_relationships; i++) {
        uint parent_id, child_id;
        fscanf(data_file, "%u %u\n", &parent_id, &child_id);
        
        add_child(&nodes[parent_id], &nodes[child_id]);
        add_parent(&nodes[child_id], &nodes[parent_id]);
    }

    return 0;
}

来自我的最高评论:

Where is the call to reallocate_node_array? Please edit your question and post it. If it's (e.g.): myarray = reallocate_node_array(myarray,&myarray_size), then the original value of myarray is leaked (because the function does not free the old/original array pointer). Unless you're trying to create a separate duplicate copy, why not just use realloc? – Craig Estey

您的回复表明这确实是问题所在。

所以,这是简单的修复:

Node *
reallocate_node_array(Node *array, size_t *size)
{

    array = realloc(array,sizeof(*array) * *size * 2);

    if (array == NULL) {
        perror("realloc");
        exit(1);
    }

    *size *= 2;

    return array;
}

但是,当我看到数组大小作为 单独的 参数传递时,我想创建一个新的“数组”结构,其中包含 size/length。这类似于 c++ 向量的作用:

typedef struct {
    Node *data;
    size_t size;
} NodeArray;

void
reallocate_node_array(NodeArray *array)
{

    array->data = realloc(array->data,sizeof(*array->data) * array->size * 2);

    if (array->data == NULL) {
        perror("realloc");
        exit(1);
    }

    array->size *= 2;
}

这有点过分,因为 调用者 仍然需要跟踪事情。

这通常是初级 C 程序员的练习。

这是一个增强功能:

typedef struct {
    Node *data;                         // pointer to data
    size_t size;                        // number of elements currently in use
    size_t capacity;                    // number of elements available
} NodeArray;

void
reallocate_node_array(NodeArray *array,size_t need)
// array -- pointer to node array
// need -- number of elements to grow by
{
    size_t size = array->size + need;

    if (size >= array->capacity) {
        array->capacity = size + 100;
        array->data = realloc(array->data,
            sizeof(*array->data) * array->capacity);

        if (array->data == NULL) {
            perror("realloc");
            exit(1);
        }
    }
}

更新:

You should always assign the result of realloc to a temporary variable - if realloc cannot extend the buffer, it returns NULL but leaves the original buffer in place. If you assign the result back to array->data and it's NULL, then you will have a memory leak. [redacted] – John Bode

JohnBode I know this trick but checking for NULL and exiting is fine too. On most programs/systems, running out of memory is/should be fatal. No way to recover meaningfully. You can handle the error but how does the program progress? – Craig Estey

I think the same way. I never wrote anything where allocating an array was optional. – Coral Bleaching

是的。正如我所说,对于大多数程序来说,这是致命的。 TL;DR 不用担心——开心点,因为这是我的“肥皂盒”之一 issues/nits ;-)

对于那些基于某些外部操作(例如,许多客户端连接到服务器)进行分配的程序,程序should/must以另一种方式限制事情并且 等到 malloc/realloc returns NULL 在这个过程中“太晚了”。

例如,它应该限制可以同时处理的传入请求的数量。如果我们限制为 N 个请求,每个请求需要分配 M 个字节,我们必须事先知道 N * M 可以 安全地分配。

对于关键任务,实时应用程序通常 所有 [可能] 分配是在程序初始化期间完成的,并且具有各种预分配的子池 structs/buffers。这是我过去为商业产品级所做的 apps/systems。

对于实时应用程序,有一个 notion/specification 的“实时安全”。也就是说,程序将具有“确定性执行”。还有其他的,但其原则之一要求所有分配都在初始化期间完成,以使内存不足的情况成为不可能[by design]。

此外,当分配失败时,程序现在处于不确定和 不安全 状态。 其他在之前发生了什么让我们进入这种状态?

是否分配失败只是因为它要求太多内存?也就是说,我们是否没有进行足够的资源限制检查。这将是一个设计缺陷。

或者,是因为 [其他地方] 存在错误并且堆已损坏?或者,程序的其他部分 data/state 现在已损坏?

我们无法确定。

为了安全起见,唯一要做的就是尽快中止。否则,当我们不再知道后果会是什么时,允许它继续存在的风险是什么?

(例如)它会[进一步]损坏数据库或删除错误的文件等吗?分配失败可能表示 UB(未定义行为),其后果是继续操作向实时控制设备发送 错误 值,导致 危险 行为的设备。思考:机器人控制、心脏起搏器控制等

简而言之,在现代系统上,通常有足够多的内存(例如千兆字节)来满足所有正常请求。因此,内存不足表示 错误(例如,失控循环执行分配)。

[真正]内存有限的实时嵌入式系统必须事先精心设计(遵循“实时安全”rules/guidelines)以prevent/avoid从一开始就不会发生的情况.