Реализует API пула памяти - работа с союзами

Question

Реализует API пула памяти - работа с союзами

Я хотел бы реализовать API для структуры данных, которая заранее выделяет память для ряда объектов определенного размера, вместо того, чтобы каждый раз использовать malloc и free для каждого объекта, как это будет необходимо.

API должен включать следующие три функции:

pool* API_init(size_t sizeOfObj, int numOfObj)

Принимает два параметра, размер объекта и количество таких объектов, которые мы хотим сохранить, и возвращает указатель на пул - структуру данных, которая управляет памятью.

void* API_malloc(Pool* pool)

Принять пул и вернуть указатель для нового размещения отдельных объектов.

void API_free(Pool* pool, void* obj)

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

Требования к сложности по времени для методов «API_malloc» и «API_free» являются постоянными, а сложность памяти пула должна быть «sizeOfObj» * «numOfObj» + константа.

Чтобы иметь дело с фрагментами, я решил определить пул как связанный список фрагментов размером 'sizeOfObj' байтов, который, кроме того, содержит указатель на следующий неиспользуемый фрагмент. Чтобы сэкономить место в памяти, я решил определить блок с помощью UNION.

Это моя реализация:

#include <stdio.h>
#include <stdlib.h>

typedef struct Pool Pool;
typedef union Chunk Chunk;


union Chunk{

    char* padding;
    Chunk* next;
};

struct Pool{

    Chunk* nextFreeChunk;
};

Pool* API_init(int sizeOfObj, int numOfObj){

    Pool* res = (Pool*) malloc(sizeof(Pool));
    Chunk* next;
    Chunk* curr;

    for(int i = numOfObj -1; i >= 0; i--){

        curr = (Chunk*) malloc (sizeof(Chunk));
        curr->padding = (char*) malloc(sizeOfObj);

        if(i < numOfObj -1)
            curr->next = next;

        next = curr;
    }

    res->nextFreeChunk = curr;
    return res;
}

void* API_malloc(Pool* pool){

    void* res = pool->nextFreeChunk;
    pool->nextFreeChunk = (pool->nextFreeChunk)->next;
    return res;
}

void API_free(Pool* pool, void* obj){

    Chunk* ch = (Chunk*) obj;
    ch->next = pool->nextFreeChunk;
    pool->nextFreeChunk = ch;
}

Моя проблема в том, что чанки, как я определил, не обязательно имеют размер sizeOfObj, как указано, а указатели char тратят впустую память (более чем константу).

Я знаю, что объединение не может иметь в качестве члена гибкий массив символов, поэтому я не могу определить член 'char padding [sizeOfObj]' внутри 'API_init'.

Мы будем благодарны за любые предложения по решению моей проблемы или по новому подходу к реализации.

# c malloc memory free

MrSonic18 дек. 2019, в 13:39

Источник

0

Если все они имеют одинаковый размер, почему бы просто не использовать вместо этого массив и растровое изображение, чтобы вы могли воспользоваться кешированием. Vio Ariton 18 дек. 2019, в 17:40
0

Вы тестировали код? Объединение не имеет смысла, поскольку члены используют один и тот же кусок памяти, что означает, что заполнение и данные будут содержать один и тот же адрес. Vio Ariton 18 дек. 2019, в 17:59

Поделиться в социальных сетях:

Скопировать адрес страницы:

Ответы 1

Смежные вопросы

Если все они имеют одинаковый размер, почему бы просто не использовать вместо этого массив и растровое изображение, чтобы вы могли воспользоваться кешированием.
Вы тестировали код? Объединение не имеет смысла, поскольку члены используют один и тот же кусок памяти, что означает, что заполнение и данные будут содержать один и тот же адрес.

HAL9000 · Accepted Answer · 2019-12-18T15-23-36.000Z

У вас проблема в том, что с тех пор, какpadding а такжеnext использовать одну и ту же память (принадлежит объединению), когда вы назначаетеnext , какие бы данныеpadding баллы будут потеряны.

Ваше решение состоит в том, чтобы ваши фрагменты были либо вашими данными , либо указателем на следующий свободный фрагмент. Так что для каждогоmalloc() , нам нужно выделитьmax(sizeof(union Chunk), sizeOfObj)

union Chunk{
    char data[1]; /* `1` is a dummy value, the compiler doesn't actually really care 
                     if we allocate and use more than 1 char */ 
    union Chunk* next;
};


/* We return `struct Pool` by value to save a `malloc()`  (c is not java)*/ 
struct Pool API_init(size_t sizeOfObj, size_t numOfObj){

    union Chunk* prev = NULL;
    size_t chunksize = max(sizeof (union Chunk), sizeOfObj);

    /* counting upwards is easier than downwards */
    for(size_t i = 0; i < numOfObj; i++){

        /* We don't cast the return value from `malloc()`. This is c, not c++ */
        curr = malloc(chunksize);

        curr->next = prev;

        prev = curr;
    }

    struct Pool res;   
    res.nextFreeChunk = curr;
    return res;
}

ВашAPI_malloc() а такжеAPI_free() выглядит нормально, за исключением того, что они написаны на c ++, а не на c. Не используйте синтаксис c ++, когда пишете на c. И используйте c-компилятор, а не c ++.

Вы можете улучшить это, расправив весь пул за один раз, а не используя несколькоmalloc() :

struct Pool{
    char *buffer;
    Chunk* nextFreeChunk;
};

struct Pool API_init(size_t sizeOfObj, size_t numOfObj){

    size_t chunksize = max(sizeof (union Chunk), sizeOfObj);

    /* Checking for overflow is left as an exercise for the reader */
    size_t buffersize = numOfObj * chunksize;

    char *buffer = malloc(buffersize);


    for(size_t i = 0; i < numOfObj - 1; i++){

        union Chunk *curr = (union Chunk *)(buffer + i * chunksize);
        curr->next = (union Chunk *)(buffer + (i+1) * chunksize);

    }

    if (numOfObj)
    {
        union Chunk *last = (union Chunk *)(buffer + (numOfObj - 1) * chunksize);
        last->next = NULL;
    }


    struct Pool res;
    res.buffer = buffer;    
    res.nextFreeChunk = (union Chunk *)buffer;
    return res;
}

Естественно, любая проверка ошибок и мелкие исправления опущены для краткости.