时间戳

首页 > 解决方案 > 实现池内存 API - 处理联合

c - 实现池内存 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 指针正在浪费内存（更多的是常量）。

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

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

标签： cmemorymallocfree

解决方案

你有一个问题，因为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()andAPI_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;
}

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

推荐阅读