实现池内存 API - 处理联合

Question

我想为一个数据结构实现一个API，它预先为一定大小的多个对象分配内存，而不是每次都使用'malloc'和'free' 为每个对象，根据需要。

API应该包括以下三个功能：

pool* API_init(size_t sizeOfObj, int numOfObj)

接受两个参数，对象大小和我们希望存储的此类对象的数量，以及 return指向池的指针 - 管理内存的数据结构。

void* API_malloc(Pool* pool)

接受池和 return 用于新分配单个对象的指针。

void API_free(Pool* pool, void* obj)

接受两个参数，池和需要标记为未使用的地址。

方法'API_malloc'和'API_free'的复杂度时间要求是常数，pool的内存复杂度应该是'sizeOfObj' * 'numOfObj' +常数。

为了处理碎片，我想将池定义为大小为 'sizeOfObj' 字节的块的链表，其中还包含指向下一个未使用块的指针。为了节省内存space，我决定用UNION来定义chunk。

这是我的实现：

#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 指针正在浪费内存（比常量更多）。

我知道 union 不能有一个灵活的 char 数组作为成员，所以我不能在 'API_init' 中定义成员 'char padding[sizeOfObj]'。

对于解决我的问题或新的实施方法的任何建议将不胜感激。

Answer 1

你遇到的问题是，由于 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;
}

当然，为简洁起见，任何错误检查和小错误修复都被省略了

实现池内存 API - 处理联合

Implements pool memory API - dealing with unions

c

memory

malloc

free