内存池实现

2019-09-22

好久没写代码了，弄个内存池找下想法（没加锁，暂不支持多线程）

查找时间复杂度O(1)

核心思想：横列数组用于存放不同内存块大小的内存池（可以看做是一个内存桶），纵列采用单链表的方式存放同一类内存块，直接pop和push此链表，已实现malloc和free时间复杂度均为O(1)的效率（内存块间无序的特性，支撑了此思想）

查找时间复杂度O(n)

核心思想:横列数组用于存放不同内存块大小的内存池（可以看做是一个内存桶），纵列数组则用于存放相同内存块，及一类大小的内存池
mempool_array.h:

/*************************************************************************
    > File Name: mempool_array.h
    > Author:lizhong
    > Mail:423810942@qq.com
    > Instruction:
 ************************************************************************/
#ifndef _MEMPOOL_ARRAY_H
#define _MEMPOOL_ARRAY_H

typedef struct
{
    unsigned char used:1;
}mem_block_flag_t;

//定义了具体的内存块地址和该块内存是否被使用
typedef struct
{
    mem_block_flag_t *flag;
    void *addr;
}mem_block_t;

//定义了某种内存节点下有多少个内存块
typedef struct
{
    unsigned int mem_block_size;
    unsigned int mem_block_array_size;
    mem_block_t *mem_block_array;
}mem_pool_node_t;

//定义了有多少种内存节点
typedef struct
{
    unsigned int mem_pool_node_size;
    mem_pool_node_t* mem_pool_node;
}mem_pool_t;

mem_pool_t *mem_pool_init(unsigned int types, ...);
void *malloc_from_mp(mem_pool_t *mp, unsigned int mem_block_size);
void free_to_mp(void *addr);

#endif

mempool_array.c:

/*************************************************************************
    > File Name: mempool_array.c
    > Author:lizhong
    > Mail:423810942@qq.com
    > Instruction:
 ************************************************************************/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<stdarg.h>
#include"mempool_array.h"

mem_pool_t *mem_pool_init(unsigned int types, ...)
{
    int i = 0;
    int j = 0;
    mem_pool_t *mp = NULL;

    mp = (mem_pool_t *)malloc(sizeof(mem_pool_t));

    if(mp == NULL)
        return NULL;

    memset(mp, 0, sizeof(mem_pool_t));
    mp->mem_pool_node_size = types;

    mp->mem_pool_node = (mem_pool_node_t *)malloc(sizeof(mem_pool_node_t) * types);

    if(mp->mem_pool_node == NULL)
    {
        free(mp);
        return NULL;
    }
    memset(mp->mem_pool_node, 0, sizeof(mem_pool_node_t) * types);

    va_list val = {0};
    va_start(val, types);

    for(i = 0; i < types; ++i)
    {
        unsigned int mem_block_array_size = 0; 
        unsigned int mem_block_size = 0; 

        mem_block_array_size = va_arg(val, unsigned int); 
        mem_block_size = va_arg(val, unsigned int);

        mp->mem_pool_node[i].mem_block_array = (mem_block_t *)malloc(sizeof(mem_block_t) * mem_block_array_size); 

        if(mp->mem_pool_node[i].mem_block_array == NULL)
        {
            free(mp->mem_pool_node);
            free(mp);
            va_end(val);
            return NULL;
        }

        memset(mp->mem_pool_node[i].mem_block_array, 0, sizeof(mem_block_t) * mem_block_array_size);
        mp->mem_pool_node[i].mem_block_array_size = mem_block_array_size; 
        mp->mem_pool_node[i].mem_block_size = mem_block_size;

        mp->mem_pool_node[i].mem_block_array[0].flag = 
            malloc((sizeof(mem_block_flag_t) + mem_block_size) * mem_block_array_size); 
        memset(mp->mem_pool_node[i].mem_block_array[0].flag, 0, 
                (sizeof(mem_block_flag_t) + mem_block_size) * mem_block_array_size);

        mp->mem_pool_node[i].mem_block_array[0].addr = 
            mp->mem_pool_node[i].mem_block_array[0].flag + sizeof(mem_block_flag_t);

        for(j = 1; j < mem_block_array_size; ++j)
        {
            mp->mem_pool_node[i].mem_block_array[j].flag = 
                mp->mem_pool_node[i].mem_block_array[j - 1].flag + 
                sizeof(mem_block_flag_t) + mem_block_size;

            mp->mem_pool_node[i].mem_block_array[j].addr = 
                mp->mem_pool_node[i].mem_block_array[j - 1].addr + 
                sizeof(mem_block_flag_t) + mem_block_size;

            printf("FUNCTION:%s, i:%d, j:%d, addr:%ld, flag:%ld\n",
                    __FUNCTION__, i, j, mp->mem_pool_node[i].mem_block_array[j].addr, 
                    mp->mem_pool_node[i].mem_block_array[j].flag);
        }
    }

    va_end(val);
    return mp;
}

void *malloc_from_mp(mem_pool_t *mp, unsigned int mem_block_size)
{
    int i = 0;
    int j = 0;

    for(i = 0; i < mp->mem_pool_node_size; ++i)
    {
        if(mp->mem_pool_node[i].mem_block_size == mem_block_size)
        {
            for(j = 0; j < mp->mem_pool_node[i].mem_block_array_size; ++j)
            {
                if(mp->mem_pool_node[i].mem_block_array[j].flag->used == 0)
                {
                    mp->mem_pool_node[i].mem_block_array[j].flag->used = 1;
                    return mp->mem_pool_node[i].mem_block_array[j].addr;
                }
            }
        }
    }
    return NULL;
}

void free_to_mp(void *addr)
{
    mem_block_flag_t *flag = NULL;

    flag = addr - sizeof(mem_block_flag_t);
    flag->used = 0;
}

mempool_main.c:

/*************************************************************************
    > File Name: mempool_u.c
    > Author:lizhong
    > Mail:423810942@qq.com
    > Instruction:
 ************************************************************************/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include"mempool_array.h"


int main(int argc, char *argv[])
{
    void *addr = NULL;
    mem_pool_t *mp = NULL;
    mp = mem_pool_init(2, 3, 16, 5, sizeof(char));


    addr = malloc_from_mp(mp, 16);
    printf("%s addr:%ld\n", __FUNCTION__, addr);
    memset(addr, 5, 16);
    free_to_mp(addr);
    printf("%s addr:%ld\n", __FUNCTION__, addr);
    addr = malloc_from_mp(mp, 16);
    printf("%s addr:%ld\n", __FUNCTION__, addr);
    addr = malloc_from_mp(mp, 16);
    printf("%s addr:%ld\n", __FUNCTION__, addr);
    addr = malloc_from_mp(mp, 16);
    printf("%s addr:%ld\n", __FUNCTION__, addr);
    addr = malloc_from_mp(mp, 16);
    printf("%s addr:%ld\n", __FUNCTION__, addr);
    return 0;
}