Алгоритм поиска наиболее выгодного количества двух частей разных размеров

Рейтинг: 0Ответов: 1Опубликовано: 21.04.2023

Предположим, у меня есть блок памяти, который нужно разбить на наиболее выгодное количество двух структур разных размеров. Структуры выглядят так:

// макрос для выравнивания значения вверх
#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;
}

Ответы

▲ 1
  1. Объединить эти структуры в одну или просто писать поочередно

  2. Если нужно, чтобы описатели шли подряд, то блоки писать с конца выделенного региона, пока не встретятся

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