0

考虑一个包含灵活数组成员的结构，如下所示：

typedef struct {
    size_t len;
    char data[];
} Foo;

我有一个未知数量的 Foo，每个都是未知大小，但是我可以确定我所有的 Foo 加起来正好是 1024 字节。如何在知道每个 Foo 的长度之前为一个 Foos 数组分配 1024 个字节，然后再填充该数组的成员？

像这样的东西，虽然它抛出了一个段错误：

Foo *array = malloc(1024);
int array_size = 0;

Foo foo1;
strcpy(foo1.data, "bar");
array[0] = foo1;
array_size++;

Foo foo2;
strcpy(foo2.data, "bar");
array[1] = foo2;
array_size++;

for (int i = 0; i < array_size; i++)
    puts(array[i].data);

想要这样做的原因是将所有 Foos 保持在一个连续的内存区域中，以便 CPU 缓存友好。

4

2 回答 2

1

你根本不能有一个 foos 数组，因为 foo 没有固定的大小，并且数组的定义特征是每个对象都有固定的大小和从其索引的基本可计算偏移量。对于您想要工作的内容，索引array[n]必须知道foo[0], foo[1], ...,的完整大小foo[n-1]，这是不可能的，因为语言不知道这些大小；在实践中，灵活的数组成员只是被排除在大小之外，因此将与's 的数据foo[1]“重叠” 。foo[0]

如果您需要能够以数组的形式访问这些对象，则需要放弃在每个对象中放置一个灵活的数组成员。相反，您可以将所有数据放在最后，并在每个数据中存储指向数据的指针或偏移量。如果您不需要能够将它们作为数组访问，则可以改为在分配的内存中构建一种链表，将下一个条目的偏移量存储为每个条目的成员。（例如，参见如何struct dirent在getdents大多数 Unices 上使用。）

于 2019-02-11T01:39:21.593 回答
1

正如其他人所指出的，您不能拥有一个 C 数组Foo。但是，假设您愿意不定期地存储它们，并且只需要知道可能需要多少空间。这个答案表明了这一点。

设N为Foo对象的数量。

令S为sizeof(Foo)，它是Foo0 字节的对象的大小data。

让A成为_Alignof(Foo)。

每个Foo对象都必须从与A字节对齐的地址开始。让它成为A。填充的最坏情况是data数组是一个字节，要求在下一个开始之前跳过AFoo -1 个字节。

因此，除了Foo对象（包括它们的data）消耗的 1024 个字节外，我们可能需要 ( N -1)•( A -1) 个字节来进行填充。（N -1 是因为在最后一个 之后不需要填充字节Foo。）

如果每个Foo都至少有一个字节data，则最多N可能是 floor(1024/( S +1))，因为我们知道所有Foo对象及其数据最多使用 1024 个字节。

因此 1024 + floor(1024/( S +1)−1)*( A −1) 字节就足够了——实际数据为 1024 字节，而 floor(1024/( S +1)−1)*( A −1) 为填充。

请注意，以上假设每个Foo都至少有一个字节data。如果一个或多个Foo有 0 个字节data，则N可能大于 floor(1024/( S +1))。但是，在任何这样的之后Foo，不需要填充，并且每个这样的N不能增加超过一Foo（因为减少一个字节使用的空间不能超过一个Foo）。因此，这样的 a可以在需要AFoo -1 字节填充的其他地方为我们提供更多，但它本身不需要填充，因此所需的填充总量不会增加。Foo

因此，为Foo对象分配内存的计划是：

  • 分配 1024 + floor(1024/( S +1)−1)*( A −1) 个字节。
  • 将第一个Foo放在分配内存的开头。
  • 将每个连续的地址放在前一个（包括其）结束之后Foo的下一个A对齐地址。Foodata

这不会产生数组，当然，只会产生Foo分配空间内的大量对象。您将需要指针或其他寻址方式。

根据 C 2018 7.22.3.4 2：

该函数为由大小指定且值不确定malloc的对象分配空间。size

因此，malloc以不规则的方式分割返回的空间以用于多个对象并不适合该规范。我将把它留给其他人讨论，但我没有观察到 C 实现有问题。

于 2019-02-11T01:43:30.130 回答