Алгоритм поиска наиболее выгодного количества двух частей разных размеров
Предположим, у меня есть блок памяти, который нужно разбить на наиболее выгодное количество двух структур разных размеров. Структуры выглядят так:
// макрос для выравнивания значения вверх
#define ALIGN_UP(__value, __alignment2) (((__value) + (__alignment2) - 1) & ~((__alignment2) - 1))
#define MEMORY_BLOCK_LENGTH 4096 // 4КБ
typedef struct __attribute__((packed)) {
unsigned int caller_id; // идентификатор потока
unsigned int data_offset; // смещение данных
unsigned int flags; // флаги данных
unsigned int reserved_count; // количество зарезервированных структур данных после текущей (нужно для правильного высвобождения страниц памяти, занятых потоком)
} memory_descriptor_t;
typedef struct __attribute__((packed)) {
unsigned char data[MEMORY_BLOCK_LENGTH]; // данные памяти
} memory_block_t;
Данные структуры хранятся в двух разных массивах. Эти массивы структур memory_block_t
находятся на выровненном по границе MEMORY_BLOCK_LENGTH
адресе.
Наиболее выгодное количество структур определяется размером структуры. Проще говоря, нужно разместить в регионе памяти как можно больше структур memory_block_t
.
Как это должно выглядеть в памяти:
-------------------------------
0x100100| ------------------- |
-------------------------------
0x101000| memory_descriptor_t |>-->
------------------------------- |
0x101020| memory_descriptor_t |>----->
------------------------------- | |
0x101040| memory_descriptor_t |--------->
------------------------------- | | |
... | | |
------------------------------- | | |
0x102000| memory_block_t |<--< | |
------------------------------- | |
0x103000| memory_block_t |<-----< |
------------------------------- |
0x104000| memory_block_t |<--------<
-------------------------------
...
Придумал пока только такой вариант(пока одна структура не пересечётся с другой), но хотелось бы узнать, есть ли более лучший способ:
unsigned int get_memory_region_blocks_count(
unsigned int region_address, // выровненный адрес
unsigned int region_size // выровненный размер региона памяти
) {
unsigned int region_end = region_address + region_size;
// если размер региона меньше, чем выровненный размер дескриптора и блока, то возвратить 0
if (region_end < ALIGN_UP(sizeof(memory_descriptor_t), MEMORY_BLOCK_LENGTH) + sizeof(memory_block_t)) return 0;
unsigned int count = 0;
unsigned int offset_descriptor = 0, offset_block = region_end - sizeof(memory_block_t);
while (offset_descriptor < offset_block) {
++count;
offset_descriptor += sizeof(memory_descriptor_t);
offset_block -= sizeof(memory_block_t);
}
return count;
}