realloc()：数组列表和 "struct hack" 的下一个大小无效

Question

我正在尝试在 c 中实现数组列表。

typedef struct ArrayList {
    size_t len;
    size_t size;
    int arr[1];
} ArrayList;

我有一个函数可以在数组变满时重新分配它。

void array_list_push(ArrayList* list, int num) {
    if (list->len == list->size) {
        size_t size = list->size;
        size *= 2;
        printf("%ld\n", size); // It prints the size
        list = realloc(list, size * 2 + (sizeof(ArrayList) - 1 * sizeof(int)));
        list->size = size;
    }
    list->arr[list->len++] = num;
}

这里是“测试”功能。

#include <stdio.h>
#include "array_list.h"

int main() {
    ArrayList *list = array_list_create(2);
    unsigned i, j;
    for(i = 0; i < 32; i++)
    {
        array_list_push(list, i); // side-effect: prints the size. for ""debugging""
        printf("[");
        for(j=0; j < array_list_get_length(list); j++)
            printf("%d, ", array_list_get(list, j));
        printf("]\n");
    }
    return 0;
}

并且输出：

[0, ]
[0, 1, ]
4
[0, 1, 2, ]
[0, 1, 2, 3, ]
8
[0, 1, 2, 3, 4, ]
[0, 1, 2, 3, 4, 5, ]
[0, 1, 2, 3, 4, 5, 6, ]
[0, 1, 2, 3, 4, 5, 6, 7, ]
16
realloc(): invalid next size
Aborted (core dumped)

为什么我会收到此错误，为什么前 2 次重新分配没有失败？

这里是array_list_create

ArrayList* array_list_create(size_t initial_size) {
    ArrayList *list = malloc(sizeof(ArrayList) + sizeof(int) * (initial_size - 1));
    list->len = 0;
    list->size = initial_size;
    return list;
}

根据更改我的 realloc 函数后，我得到以下输出：

[0, ]
[0, 1, ]
4
[0, 1, 2, ]
[0, 1, 2, 3, ]
8
[]
[5, ]
[5, 6, ]
[5, 6, 7, ]
[5, 6, 7, 8, ]
[5, 6, 7, 8, 9, ]
[5, 6, 7, 8, 9, 10, ]
[5, 6, 7, 8, 9, 10, 11, ]
[5, 6, 7, 8, 9, 10, 11, 12, ]
[5, 6, 7, 8, 9, 10, 11, 12, 539768155, ]
[5, 6, 7, 8, 9, 10, 11, 12, 539768155, 924855350, ]
[5, 6, 7, 8, 9, 10, 11, 12, 539768155, 924855350, 741875756, ]
[5, 6, 7, 8, 9, 10, 11, 12, 539768155, 924855350, 741875756, 539769120, ]
[5, 6, 7, 8, 9, 10, 11, 12, 539768155, 924855350, 741875756, 539769120, 539766833, ]
[5, 6, 7, 8, 9, 10, 11, 12, 539768155, 924855350, 741875756, 539769120, 539766833, 539767089, ]
[5, 6, 7, 8, 9, 10, 11, 12, 539768155, 924855350, 741875756, 539769120, 539766833, 539767089, 539767345, ]
[5, 6, 7, 8, 9, 10, 11, 12, 539768155, 924855350, 741875756, 539769120, 539766833, 539767089, 539767345, 926495541, ]
[5, 6, 7, 8, 9, 10, 11, 12, 539768155, 924855350, 741875756, 539769120, 539766833, 539767089, 539767345, 926495541, 892418102, ]

以此类推。我尝试将它重定向到一个带有 ./main > output 的文件中，并且在编辑器中它显示了奇怪的 ?s。这是 cat output

的输出

?
[5, 6, 7, 8, 9, ]
[5, 6, 7, 8, 9, 10, ]
[5, 6, 7, 8, 9, 10, 11, ]
[5, 6, 7, 8, 9, 10, 11, 12, ]
[5, 6, 7, 8, 9, 10, 11, 12, 13, ]
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ]
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ]
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, ]
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, ]
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, ]
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, ]
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ]
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, ]
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, ]
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, ]
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, ]
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, ]
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, ]
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, ]
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, ]
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, ]
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, ]
[5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, ]

Answer 1

list = realloc(list, size * 2 + (sizeof(ArrayList) - 1 * sizeof(int)));

这个计算看起来不对。我不知道 2 是从哪里来的，但这没有任何意义；应该是sizeof(int)。我觉得写成

可能更清楚

list = realloc(list, sizeof(ArrayList) + (size - 1)*sizeof(int));

Answer 2

array_list_push中的realloc函数可以移动你的整个列表对象。您在 array_list_push 内部处理该问题，但 main 中的代码继续使用指向旧对象的指针。

Return 来自 array_list_push 的新指针：

ArrayList* array_list_push(ArrayList* list, int num) {
    if (list->len == list->size) {
        size_t size = list->size;
        size *= 2;
        printf("%ld\n", size); // It prints the size
        list = realloc(list, size * 2 + (sizeof(ArrayList) - 1 * sizeof(int)));
        list->size = size;
    }
    list->arr[list->len++] = num;
    return list;
}

并在 main 中使用新指针：

int main() {
    ArrayList *list = array_list_create(2);
    unsigned i, j;
    for(i = 0; i < 32; i++)
    {
        list = array_list_push(list, i); // side-effect: prints the size. for ""debugging""
        printf("[");
        for(j=0; j < array_list_get_length(list); j++)
            printf("%d, ", array_list_get(list, j));
        printf("]\n");
    }
    return 0;
}

提示：运行 valgrind 中的代码（如果在您的平台上可用）可以快速找到此类问题及其原因。

realloc()：数组列表和 "struct hack" 的下一个大小无效

realloc(): invalid next size with array lists and the "struct hack"

c89