链表的替代品—内存池

约定不等于承诺〃 2022-07-14 04:37 254阅读 0赞

链表是大家非常熟悉的数据结构，使用频率也非常高，但是链表有几个缺点。首先，我们每创建一个节点，都要进行一下系统调用分配一块空间，这会浪费一点时间；其次，由于创建节点的时间不固定，会导致节点分配的空间不连续，容易形成离散的内存碎片；最后，由于内存不连续，所以链表的局部访问性较差，容易出现cache缺失。  
针对链表的上述问题，在实际工作中，我们很少直接用链表，而是采用链表的替代品—内存池。上过操作系统课程的同学对内存池应该不陌生，而且应该也知道设计一个好的内存池非常麻烦。但替换链表的内存池做了很大的简化：它是单线程的而且是只支持固定块大小的内存池。在具体实现过程中，我们先分配N块固定大小的连续内存，N块需要根据需求设定，之后每需要一个节点就从内存池中get一块空闲的块，用完之后再回收到内存池中。  
内存池可以解决链表三个问题中的前两个，不能解决后一个，但是如果内存池较小可以缓解cache缺失的问题，整体而言还是可以很好地代替链表。下面看一下具体实现。

## 1. 结构体 ##

内存池想象中比较简单，就是首先分配一块大内存，每次取一小块内存，用完再放回去即可，但是实现起来需要较多的辅助变量。我们不能仅仅通过一个指针来完成对内存池的访问，因为获取和释放的顺序是随机的。我们需要标记每一块的使用状况。内存池的结构体如下：

typedef struct _mem_pool_
    {
        char*  buffer_arr;
    
        char** index_arr;
        char** index_cur;
        char** index_end;
    }mem_pool_t;

buffer\_arr就是原始的整块大内存，除了这个变量之外还有三个二维指针：index\_arr是一个指针数组，分别指向每一块的首地址，index\_cur是一个遍历指针，用来指向当前可分配的块，index\_end表示可分配块的末尾。

## 2. 初始化 ##

初始化需要指定块大小和块个数，然后分配大块内存。但初始化的关键操作是初始化几个二维指针。看一下代码：

/**
     * @brief 创建内存池
     * @param capacity   容量
     * @param block_size 对象单元大小
     * @return 内存池对象指针，如果创建失败返回NULL
     */
    mem_pool_t* mem_pool_init(int capacity, int unit_size)
    {
        int i = 0;
        char *work = NULL;
        mem_pool_t* mem_pool = NULL;
    
        if(capacity <=0 || unit_size <=0)
        {
            printf("Illegal params, capacity[%d]"
                        " unit_size[%d]", capacity, unit_size);
            return NULL;
        }
    
        mem_pool = (mem_pool_t*)malloc(sizeof(mem_pool_t));
        if(NULL == mem_pool)
        {
            printf("init memery pool failed");
            return NULL;
        }
    
        mem_pool->buffer_arr = (char*)malloc(capacity*unit_size);
        if(NULL == mem_pool->buffer_arr)
        {
            printf("Failed to alloc mem_pool buffer");
            return NULL;
        }
    
        mem_pool->index_arr = (char**)malloc(sizeof(char*)*capacity);
        if(NULL == mem_pool->index_arr)
        {
            printf("Failed to alloc memory pool "
                        "index array");
            return NULL;
        }
        work = mem_pool->buffer_arr;
        for(i=0; i<capacity; i++, work+=unit_size)
        {
            mem_pool->index_arr[i] = work;
        }
        mem_pool->index_end = mem_pool->index_arr + capacity;
        mem_pool->index_cur = mem_pool->index_arr;
    
        return mem_pool;
    }

index\_arr是一个和内存池容量一样的二维指针，它被初始化为内存池每一块的首地址。index\_end指向index\_arr末尾的下一个位置，用来表示内存池的末尾。index\_cur只是简单地等于index\_arr的首地址。后面我们就可以通过加减index\_cur来分配或回收一块内存。

## 3. get函数 ##

get函数的目的是从内存池中取一块可用内存，它首先判断是否还有可用块，如果有就返回当前可用块。返回可用块的方法很简单，只需要将index\_cur对应位置的块返回即可。

/**
     * @brief 从内存池中分配一个单元
     * @param mem_pool 内存池指针
     * @return 新分配的对象指针，如果分配失败返回NULL
     */
    void* mem_pool_alloc(mem_pool_t* mem_pool)
    {
        void* ret;
    
        if(mem_pool->index_cur >= mem_pool->index_end)
        {
            printf("memory pool overflow");
            return NULL;
        }
        ret = *(mem_pool->index_cur++);
    
        return ret;
    }

## 4. free函数 ##

free函数的目的是回收一块用完的内存。和get相反，我们只需要把回收内存的地址赋给index\_cur-1即可。

/**
     * @brief 内存池回收一个对象单元
     * @param mem_pool 内存池
     * @param obj    待回收的对象单元
     * @return errno
     *         0  : OK
     *         -1 : ERROR
     */
    int mem_pool_free(mem_pool_t* mem_pool, void* obj)
    {
        if(NULL == mem_pool)
        {
            printf("try to free block in NULL pool");
            return MEM_POOL_ERR;
        }
        if(NULL == obj)
        {
            printf("try to free NULL object");
            return MEM_POOL_ERR;
        }
    
        *(--mem_pool->index_cur) = (char*)obj;
    
        return MEM_POOL_OK;
    }

这里需要注意的是，index\_arr一开始是顺序指向每一块内存的，但是在不停地get和free过程中index\_arr开始乱序指向每一块内存。  
可以看出，上面的get和free操作都非常简单，只是简单的加减操作，所以速度非常快，而且内存池是一整块内存，不存在内存碎片的问题。同时，如果内存池较小，也可以很大程度上缓解cache缺失问题。