Я хотел бы реализовать 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'.
Мы будем благодарны за любые предложения по решению моей проблемы или по новому подходу к реализации.
У вас проблема в том, что с тех пор, как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;
}
Естественно, любая проверка ошибок и мелкие исправления опущены для краткости.