自定义malloc分配数组空间

申请栈空间，实现initMallocPoll、mAlloc、mRealloc、mFree动态分配。

使用blk结构体记录空间分配，返回申请空间的地址在紧跟在blk后，链表记录已分配或未分配的块，申请或释放时，改变链表指针的指向，合并相邻未分配块。

本篇文章参考自 https://blog.csdn.net/wxx258369/article/details/78949687，仅仅对其中的一部分做了修改

代码

mAlloc.h

#ifndef __mAlloc_h__
#define __mAlloc_h__

void initMallocPool(void *pool, unsigned size);

void* mAlloc(unsigned size);

void* mRealloc(void *ptr, unsigned size);

void mFree(void *ptr);

#endif

mAlloc.c

#include "mAlloc.h"
#include <string.h>

typedef struct _blk
{
	unsigned size;
    struct _blk *next;//指向下一个未分配块
}blk, *pblk;//指示每个已分配或未分配空间的大小和位置

static pblk phead = NULL;//链表记录未分配块的位置和大小

void initMallocPool(void *pool, unsigned size)
{
    phead = (pblk)pool;
    phead->next = NULL;
    phead->size = size - sizeof(blk);//可用空间
}

void* mAlloc(unsigned size)
{
    pblk pNext,pNode;
    void *result;
    pNext = phead;
    //地址从下往上增长
    
    //使分配的块为4字节的倍数，否则在某单片机上pNode->size访问错误
    if((size&3) != 0) 
        size = ((size >> 2) + 1) << 2;
    
    do
    {
    	if(pNext->size >= size + sizeof(blk))//找到可分配的块
        {
            pNext->size = pNext->size - size - sizeof(blk);//分配后剩余大小
            pNode = (pblk)((void*)pNext + pNext->size + sizeof(blk));//新节点
            pNode->size = size;
            
            result = (void*)(++pNode); //指针向上移动一个blk大小，为分配给用户的地址
            return result;
        }
        pNext = pNext->next;
    }while(pNext != NULL);
    
    return NULL; //找不到连续大小的块
}

void merge(pblk pPrior, pblk pNext)
{
    if(pNext == (pblk)((void*)pPrior + pPrior->size + sizeof(blk)))//相邻玩过
    {
        pPrior->size += pNext->size + sizeof(blk);
        pPrior->next = pNext->next;
    }
}

void mFree(void *ptr)
{
    pblk pFree = (pblk)(ptr - sizeof(blk));//指针向下移动一个blk大小，即位块信息
    pblk pNext = phead;
    pblk pPrior = phead;
    do
    {
        pPrior = pNext;
        pNext = pNext->next;
        //将待释放块插入未分配链表距离最近的两个未分配块的中间
        if(pNext == NULL || (pPrior <= pFree && pNext >= pFree))
        {
            pFree->next = pNext;
            pPrior->next = pFree;
            break;
        }
    }while(pNext != NULL);
    //合并相邻的两个未分配块
    merge(pPrior, pFree);
    merge(pFree, pNext);
    merge(pPrior, pNext);//如果三个块是连续的，则需要
}

void* mRealloc(void *ptr, unsigned size)
{
    if(ptr == NULL) return mAlloc(size);
    pblk pFree = (pblk)(ptr - sizeof(blk));//指针向下移动一个blk大小，即位块信息
    void *p = mAlloc(size);
    if(p != NULL)
    {
        memset(p, 0, size);
        if(pFree->size < size)  size的大小不总大于原空间的大小
            memcpy(p, ptr, pFree->size);
        else
            memcpy(p, ptr, size);
        mFree(ptr);
        return p;
    }
    return NULL;
}

测试

#include "mAlloc.h"

int main()
{
    char pool[1024*5];
    initMallocPool(pool, sizeof(pool));
    char *t = mAlloc(100);
    mFree(t);
    return 0;
}

改进

mAlloc可以进行优化，寻找所有未分配块中最接近需要size大小的块，避免剩余空间很多，但过于零碎，在需要分配一大块完整空间时找不到。

void* mAlloc(unsigned size)
{
    pblk pNext,pNode;
    void *result;
    pNext = phead;
    pblk pMin = phead;
    
    if((size&3) != 0) 
        size = ((size >> 2) + 1) << 2;
    do
    {
    	if(pNext->size >= size + sizeof(blk))//找到可分配的块
        {
            if(pMin->size > pNext->size)
                pMin = pNext;
        }
        pNext = pNext->next;
    }while(pNext != NULL);
    
    if(pMin->size >= size + sizeof(blk))
    {
        pMin->size = pMin->size - size - sizeof(blk);//分配后剩余大小
        pNode = (pblk)((void*)pMin + pMin->size + sizeof(blk));//新节点
        pNode->size = size;

        result = (void*)(++pNode); //指针向上移动一个blk大小，为分配给用户的地址
        return result;
    }
    
    return NULL; //找不到连续大小的块
}