追踪内存泄漏，释放不正确？

Question

下午，我收到一个奇怪的 valgrind 错误报告。请参阅所附图片。我有一个释放堆的函数，或者我虽然做了。需要帮助追踪这个错误。欢迎修复，但也欢迎解释。

我对 valgrind 的分析跟踪到第 67 行，当我创建节点时，所以我知道我很可能忘记用我的 free 函数释放它。

#include "stdio.h"
#include "stdlib.h"
#include "limits.h"

struct adj_list_node
{
    int vertex;
    int weight;
    struct adj_list_node *next;
};

struct adj_list
{
    struct adj_list_node *head;
};

struct graph
{
    int vertices;
    struct adj_list *array;
};

struct adj_list_node* create_node(int vertex, int weight);
struct graph *create_graph(int vertices);
void add_edge(struct graph *graph, int src_vertex, int dst_vertex, int weight);
void free_nodes(struct adj_list_node *node);
void free_graph(struct graph *graph);

struct min_heap_node
{
    int vertex;
    int distance;
};

struct min_heap
{
    int size;
    int capacity;
    int *position;
    struct min_heap_node **array;
};

struct min_heap_node *create_heap_node(int vertex, int distance);
struct min_heap *create_heap(int capacity);

void swap_node(struct min_heap_node** a, struct min_heap_node** b);
int is_empty(struct min_heap* heap);
void min_heapify(struct min_heap *heap, int parent);
struct min_heap_node *extract_min_node(struct min_heap* heap);
int is_in_min_heap(struct min_heap *heap, int index);

void decrease_key(struct min_heap *heap, int index, int distance);
void dijkstra(struct graph* graph, int src_vertex);
void delete_heap(struct min_heap *heap);
void print_path(int parent[], int vertex);
void print_array(int dist[], int n,int parent[]);

#include "dikjkstra.h"

struct adj_list_node* create_adj_node(int vertex, int weight)
{
    struct adj_list_node *new_node = malloc(sizeof(struct adj_list_node));
    new_node->vertex = vertex;
    new_node->weight = weight;
    new_node->next = NULL;
    return new_node;
}

struct graph *create_graph(int vertices)
{
    struct graph *new_graph = malloc(sizeof(struct graph));
    new_graph->vertices = vertices;
    new_graph->array = malloc(sizeof(struct adj_list) * vertices);

    for (int i = 0;i < vertices; ++i) {
        new_graph->array[i].head = NULL;
    }

    return new_graph;
}

void add_edge(struct graph *graph, int src_vertex, int dst_vertex, int weight)
{
    struct adj_list_node *new_node = create_adj_node(dst_vertex, weight);
    new_node->next = graph->array[src_vertex].head;
    graph->array[src_vertex].head = new_node;

    new_node = create_adj_node(src_vertex, weight);
    new_node->next = graph->array[dst_vertex].head;
    graph->array[dst_vertex].head = new_node;
}

void free_nodes(struct adj_list_node *node)
{
    if (node == NULL) {
        return;
    }

    struct adj_list_node *temp_node = node;

    while (temp_node) {
        struct adj_list_node *removed_node = temp_node;
        temp_node = removed_node->next;
        removed_node->next = NULL;
        free(removed_node);
    }
}

void free_graph(struct graph *graph)
{
    if(graph->array == NULL) {
        return;
    }

    for (int i = 0; i < graph->vertices; ++i) {
        free_nodes(graph->array[i].head);
    }
    free(graph->array);
}


struct min_heap_node *create_heap_node(int vertex, int distance)
{
    struct min_heap_node *new_node = malloc(sizeof(struct min_heap_node));
    new_node->vertex = vertex;
    new_node->distance = distance;
    return new_node;
}

struct min_heap *create_heap(int capacity)
{
    struct min_heap *new_heap = malloc(sizeof(struct min_heap));
    new_heap->size = 0;
    new_heap->capacity = capacity;
    new_heap->position = malloc(capacity * sizeof(int));
    new_heap->array = malloc(sizeof(struct min_heap_node *) * capacity);
    return new_heap;
}

void swap_node(struct min_heap_node** a, struct min_heap_node** b)
{
    struct min_heap_node *temp_node;
    temp_node = *a;
    *a = *b;
    *b = temp_node;
}

int is_empty(struct min_heap* heap)
{
    return heap->size == 0;
}

void min_heapify(struct min_heap *heap, int parent)
{
    int left_child = 2 * parent + 1;
    int right_child = 2 * parent + 2;

    int smallest = parent;

    if (left_child < heap->size && heap->array[left_child]->distance < heap->array[smallest]->distance) {
        smallest = left_child;
    }

    if ( right_child < heap->size && heap->array[right_child]->distance < heap->array[smallest]->distance) {
        smallest = right_child;
    }

    if (smallest != parent) {
        struct min_heap_node *smallest_node = heap->array[smallest];
        struct min_heap_node *temp_node = heap->array[parent];

        heap->position[smallest_node->vertex] = parent;
        heap->position[temp_node->vertex] = smallest;

        swap_node(&heap->array[smallest], &heap->array[parent]);
        min_heapify(heap, smallest);
    }
}

struct min_heap_node *extract_min_node(struct min_heap *heap)
{
    if (is_empty(heap)) {
        return NULL;
    }

    struct min_heap_node *root_node = heap->array[0];

    struct min_heap_node *last_node = heap->array[heap->size - 1];
    heap->array[0] = last_node;

    heap->position[root_node->vertex] = heap->size - 1;
    heap->position[last_node->vertex] = 0;

    --(heap)->size;
    min_heapify(heap, 0);

    return root_node;
}

int is_in_min_heap(struct min_heap *heap, int index)
{
    if (heap->position[index] < heap->size) {
        return 1;
    } else {
        return 0;
    }
}

void delete_heap(struct min_heap *heap)
{
    free(heap->array);
    free(heap->position);
    free(heap);
}

void decrease_key(struct min_heap *heap, int index, int distance)
{
    int key = heap->position[index];

    heap->array[key]->distance = distance;

    while(key && heap->array[key]->distance < heap->array[(key - 1) / 2]->distance) {
        heap->position[heap->array[key]->vertex] = (key - 1) / 2;
        heap->position[heap->array[(key - 1) / 2]->vertex] = key;
        swap_node(&heap->array[key], &heap->array[(key - 1) / 2]);

        key = (key - 1) / 2;
    }
}

void dijkstra(struct graph* graph, int src_vertex)
{
    int vertices = graph->vertices;
    struct min_heap *heap = create_heap(vertices);
    int distance[vertices];
    heap->size = vertices;
    int parent[vertices];
    parent[src_vertex] = src_vertex;

    for(int i = 0; i < vertices; ++i) {
        distance[i] = INT_MAX;
        heap->array[i] = create_heap_node(i, INT_MAX);
        heap->position[i] = i;
    }

    distance[src_vertex] = 0;
    decrease_key(heap, src_vertex, distance[src_vertex]);

    while(!is_empty(heap)) {
        struct min_heap_node *min_node = extract_min_node(heap);
        int u = min_node->vertex;

        for (struct adj_list_node *cursor = graph->array[u].head; cursor; cursor = cursor->next) {
            int v = cursor->vertex;

            if(is_in_min_heap(heap,v) && distance[u]!=INT_MAX && distance[u] + cursor->weight < distance[v]) {
                distance[v] = cursor->weight + distance[u];
                parent[v] = u;
                decrease_key(heap, v, distance[v]);
            }
        }
    }
    print_array(distance, vertices, parent);
    delete_heap(heap);
}

void print_path(int parent[], int vertex)
{
    if (parent[vertex]==vertex) {
        return;
    }
    print_path(parent, parent[vertex]);
    printf("%d->", parent[vertex]);
}

void print_array(int cost[], int vertices,int parent[])
{
    printf("\nvertex\t\tcost\t\tpath\n");
    for(int i = 0; i < vertices ; ++i) {
        printf("%d\t\t\t%d\t\t\t", i, cost[i]);
        print_path(parent, i);
        printf("%d\n", i);
    }
}

/**
 *            6
 *     0-------------1
 *     |            /|\
 *     |           / | \
 *     |          /  |  
 *     |         /   |   \
 *     |        /    |    \
 *     |       /     |     \
 *    1|     2/     2|      2
 *     |     /       |     /
 *     |    /        |    /
 *     |   /         |   /5
 *     |  /          |  /
 *     | /           | /
 *     |/            |/
 *     3-------------4
 *            1
 */

int main()
{
    int total_vertex = 5;

    struct graph* graph = create_graph(total_vertex);

    add_edge(graph, 0, 1, 6);
    add_edge(graph, 0, 3, 1);

    add_edge(graph, 1, 0, 6);
    add_edge(graph, 1, 3, 2);
    add_edge(graph, 1, 4, 2);
    add_edge(graph, 1, 2, 5);

    add_edge(graph, 2, 1, 5);
    add_edge(graph, 2, 4, 5);

    add_edge(graph, 3, 0, 1);
    add_edge(graph, 3, 1, 2);
    add_edge(graph, 3, 4, 1);

    add_edge(graph, 4, 3, 1);
    add_edge(graph, 4, 1, 2);
    add_edge(graph, 4, 2, 5);

    dijkstra(graph,0);

    free_graph(graph);
    free(graph);
    return 0;
}

/**
* Output
* vertex    cost        path
* 0     0       0
* 1     3       0->3->1
* 2     7       0->3->4->2
* 3     1       0->3
* 4     2       0->3->4
*/

Answer 1

Valgrind 说泄漏的内存是由 create_heap_node 分配的，这意味着您没有释放一些堆节点。我们如何找到它？

每个malloc 都需要一个free。如果每个创建函数都有匹配的自由函数（并使用一致的命名方案），则更容易检查这一点。

create_heap_node
- 缺失
create_heap
- delete_heap（应该是free_heap）
create_adj_node
- free_nodes（应该是free_adj_nodes）
create_graph
- free_graph
  - 调用 free_nodes
  - does not free the graph（您手动释放它，但这是等待发生的内存泄漏）

乍一看，您缺少 free_heap_node。

void delete_heap(struct min_heap *heap)
{
    free(heap->array);  // potential memory leak
    free(heap->position);
    free(heap);
}

也许其他东西正在释放这些节点，但 delete_heap 不应该这样假设。可能存在内存泄漏。

dijkstra 是唯一使用 delete_heap 的函数。 dijkstra 在调用 delete heap 时假定堆为空，而事实确实如此。然而，dijkstra 提取节点但它从不释放它们。

    while(!is_empty(heap)) {
        struct min_heap_node *min_node = extract_min_node(heap);

        // min_node is removed from heap but never freed.
        // memory leak.
        // needs free_heap_node(min_node)
    }
    
    delete_heap(heap);

free_nodes 应该是 free_adj_nodes。您可以添加 free_adj_node 以获得完整性，这将使 free_nodes 更简单。

// free itself, return the next node
struct adj_list_node *free_adj_node(struct adj_list_node *node) {
    struct adj_list_node *next = node->next;
    free(node);
    return next;
}

void free_adj_nodes(struct adj_list_node *node)
{
    // No need to check if node is null.
    // If it is, the loop will simply not run.

    // Free nodes until the next node is null.
    while (node) {
        node = free_adj_node(node);
    }
}

追踪内存泄漏，释放不正确？

Tracking down memory leak, free incorrectly?

c

arrays

malloc

valgrind