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

Question

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

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

У меня есть неизвестное количество Foos, каждый из которых имеет неизвестный размер, однако я могу быть уверен, что все мои Foos вместе составят ровно 1024 байта. Как я могу выделить 1024 байта для массива Foo, прежде чем знать длину каждого 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);

Причина желания сделать это состоит в том, чтобы держать все Foos в непрерывной области памяти, для удобства использования кеша процессора.

Answer 1

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

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

Answer 2

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

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

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

Пусть А будет _Alignof(Foo),

каждый Foo Объект должен начинаться с адреса, выровненного по байту. Пусть это будет А. В худшем случае для заполнения 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 по следующему адресу с А- выравниванием после окончания предыдущего Foo (включая его data).

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

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

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

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