I'd like to implement an API for a data structure that allocates memory in advance to a number of objects of a certain size, instead of each time using 'malloc' and 'free' for each object, as will be needed.
The API should include the following three functions:
pool* API_init(size_t sizeOfObj, int numOfObj)
Accepts two parameters, the object size and the number of such objects we wish to store, and returns pointer to a pool - a data structure that manage the memory.
void* API_malloc(Pool* pool)
Accept pool and return pointer for new allocation of a single objects.
void API_free(Pool* pool, void* obj)
Accepts two parameters, pool and the address which is need to be marked as unused.
The complexity time requirements for methods 'API_malloc' and 'API_free' is constant, and the memory complexity of pool should be 'sizeOfObj' * 'numOfObj' + constant.
In order to deal with fragments, I thought to defined a pool as linked list of chunks of size 'sizeOfObj' bytes, which in addition contains a pointer to the next unused chunk. In order to save memory space, I decide to defined chunk with UNION.
This is my implementaion:
#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;
}
My problem is that the chunks, as I defined, don't necessarily have size of 'sizeOfObj' as given, and the char pointers are wasting memory (more then constant).
I know that union can't have as member a flexible char array, so I can't defined member 'char padding[sizeOfObj]' inside 'API_init'.
Any suggestion for solving my problem or for new implementation approach will be gratefully appreciated.
You have the problem that since padding and next share the same memory (belongs to a union), when you assign to next, whatever data padding points to will be lost.
Your solution is for your chunks to either be your data, or be the pointer to your next free chunk. So for each malloc(), we need to allocate 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;
}
Your API_malloc() and API_free() looks OK, except that they are written in c++ rather than c. Don't use c++ syntax when you are writing in c. And use the c-compiler, not the c++ one.
You can improve on this by mallocing your whole pool in one go rather than using multiple 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;
}
Naturally, any error checking and minor bugfixing are left out for brevity