Выделение непрерывной памяти для размещения нескольких структур с гибкими элементами массива

Question

Рассмотрим структуру, содержащую элемент гибкого массива, например:

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

У меня есть неизвестное количество Foos, каждый из которых имеет неизвестный размер, однако я могу быть уверен, что все мои Foosвместе составит ровно 1024 байта.Как я могу выделить 1024 байта для массива Foos, прежде чем узнавать длину каждого Foo, а затем заполнить члены массива позже?

Что-то вроде этого, хотя при этом возникает ошибка:

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

Причина, по которой вы хотите это сделать, состоит в том, чтобы все Foo оставались в непрерывной области памяти для удобства кэша ЦП.

Answer 1

Как уже отмечали другие, вы не можете иметь массив C Foo.Однако предположим, что вы хотите хранить их нерегулярно и просто должны знать, сколько места может потребоваться.Этот ответ показывает, что.

Пусть N будет количеством Foo объектов.

Пусть S будет sizeof(Foo), чтоэто размер Foo объекта с нулевыми байтами для data.

Пусть A будет _Alignof(Foo).

Каждый объект Foo должен быть запущенпо адресу, выровненному по A байт.Пусть это будет A .В худшем случае для заполнения является то, что массив data составляет один байт, что требует пропуска A -1 байтов до начала следующего Foo.

.1024 байта, потребляемых Foo объектами (включая их data), нам может понадобиться ( N -1) • ( A -1) байтов для этого заполнения.( N -1 объясняется тем, что после последнего Foo не требуется заполнять байты.)

Если каждый Foo имеет хотя бы один байт data, то большинство N может быть минимальным (1024 / ( S + 1)), потому что мы знаем, что все объекты Foo и их данные используют не более 1024 байтов.

Поэтому 1024 + пол (1024 / ( S + 1) -1) * ( A -1) байтов достаточно - 1024 байта для фактических данных и этажа (1024 / ( S + 1) -1) * ( A -1) для заполнения.

Обратите внимание, что в вышеприведенном предполагается, что каждый Foo имеет по крайней мере один байтdata.Если один или несколько Foo имеют нулевые байты data, N может быть больше пола (1024 / ( S + 1)).Однако после любого такого Foo заполнение не требуется, и N не может увеличиться более чем на один для каждого такого Foo (поскольку сокращение пространства, используемого одним байтом, не может привести к увеличению для более чем одногоFoo).Таким образом, такой Foo может дать нам еще один Foo в другом месте, который требует A -1 байт заполнения, но сам по себе не нуждается в заполнении, поэтому общее количество необходимых дополнений не может увеличиться.

Итак, план по выделению памяти для объектов Foo:

• Выделить 1024 + этаж (1024 / ( S + 1) -1)* ( A -1) байт.
• Поместите первый Foo в начало выделенной памяти.
• Поместите каждый последующий Foo в следующий A -центрированный адрес после конца предыдущего Foo (включая data).

Это, конечно, не приведет к массиву, просто масса Foo объекты в выделенном пространстве.Вам понадобятся указатели или другие средства их адресации.

Согласно C 2018 7.22.3.4 2:

Функция malloc выделяет пространство для объекта, для которого указана sizeпо размеру и значение которого не определено.

Таким образом, разбиение пространства, возвращаемого malloc нерегулярным способом для использования для нескольких объектов, не подходит для этой спецификации.Я оставлю это для обсуждения другими, но я не заметил, чтобы у реализации на С возникла проблема.

Answer 2

Вы не можете вообще иметь массив foos, потому что foo не имеет фиксированного размера, и определяющей характеристикой массива является то, что каждый объект имеет фиксированный размер и смещение от базывычисляется из его индекса.Для того, что вы хотите работать, индексирование array[n] должно знать полный размер foo[0], foo[1], ..., foo[n-1], что невозможно, поскольку язык не знает этих размеров;на практике элемент гибкого массива просто исключается из размера, поэтому foo[1] будет «перекрываться» с данными foo[0].

Если вам нужно иметь доступ к этим объектам как к массиву,вам нужно отказаться от помещения в каждый элемент гибкого массива.Вместо этого вы можете поместить все данные в конец и сохранить указатель или смещение для данных в каждом из них.Если вам не нужно иметь доступ к ним как к массиву, вы можете вместо этого создать своего рода связанный список в выделенной памяти, сохраняя смещение следующей записи в качестве члена каждой записи.(См., Например, как struct dirent работает с getdents в большинстве Unices.)