嵌入式操作系统内核原理跟开发（基于链表节点的内存分配算法）

2012-06-30

嵌入式操作系统内核原理和开发（基于链表节点的内存分配算法）

链接节点的内存分配方法，其实就是一种按需分配的内存分配方法。简单一点说，就是你需要多少内存，我就给你多少内存。当然，为了把分配的内存都连起来，我们还需要对分配节点进行管理记录。就比如下面这个数据结构，

/**************************************************      malloc & free in link node algorithm**************************************************/#include <string.h>#include <malloc.h>/**************************************************           struct definition**************************************************/typedef struct _MNG_NODE{    struct _MNG_NODE* next;    unsigned int size;}MNG_NODE;/**************************************************           global variable declaration**************************************************/#define MEM_BUFFER_LENGTH   (0x1 << 24)static void* pGlbData;static MNG_NODE* pFreeList;static MNG_NODE* pAllocList;/************************************************** function: add node into headlist**************************************************/static void add_node_into_list_head(MNG_NODE* pNode, MNG_NODE** ppList){    pNode->next = *ppList;    *ppList = pNode;   }/************************************************** function: find best fit node**************************************************/static MNG_NODE* find_best_fit_node(unsigned int size){    MNG_NODE* pCur = pFreeList;    MNG_NODE* pPre = pCur;    while(pCur && pCur->size < (size + sizeof(MNG_NODE)))    {         pPre = pCur;        pCur = pCur->next;    }       if(NULL == pCur)        return NULL;    if(pFreeList == pCur)        pFreeList = pFreeList->next;    else        pPre->next = pCur->next;    return pCur;}/************************************************** function: implement memory allocation**************************************************/static void* _mem_malloc(unsigned int size){    MNG_NODE* pOld;    MNG_NODE* pNew;    pOld = find_best_fit_node(size);    if(NULL == pOld)        return NULL;    pNew = (MNG_NODE*)((char*)pOld + sizeof(MNG_NODE) + pOld->size - (sizeof(MNG_NODE) + size));    pNew->size = size;    pOld->size -= sizeof(MNG_NODE) + size;    add_node_into_list_head(pOld, &pFreeList);    add_node_into_list_head(pNew, &pAllocList);    return (void*)((char*)pNew + sizeof(MNG_NODE));}/************************************************** function: memory allocation**************************************************/void* mem_malloc(unsigned int size){    if(0 == size)        return NULL;    if(size > (MEM_BUFFER_LENGTH - sizeof(MNG_NODE)))        return NULL;    return _mem_malloc(size);}/************************************************** function: find previous node **************************************************/static MNG_NODE* find_previous_node(MNG_NODE* pNode){    MNG_NODE* pFind = pAllocList;    MNG_NODE* pPre = NULL;        while(pFind && pFind != pNode)    {        pPre = pFind;        pFind = pFind->next;    }    if(NULL == pFind)        return NULL;    return pPre;}/************************************************** function: implement memory free**************************************************/static void _mem_free(MNG_NODE* pNode){    MNG_NODE* pPreNode;    if(pNode == pAllocList)    {        pAllocList = pAllocList->next;        add_node_into_list_head(pNode, &pFreeList);        return;    }        pPreNode = find_previous_node(pNode);    if(NULL == pPreNode)        return;    pPreNode->next = pNode->next;    add_node_into_list_head(pNode, &pFreeList);    return;}/************************************************** function: free memory function**************************************************/void mem_free(void* pData){    if(NULL == pData)        return;    if(pData < pGlbData || pData >= (void*)((char*)pGlbData + MEM_BUFFER_LENGTH))        return;    _mem_free(pData - sizeof(MNG_NODE));}/************************************************** function: get memory buffer**************************************************/void mem_init(){    pGlbData = (void*)malloc(MEM_BUFFER_LENGTH);    if(NULL == pGlbData)        return;    memset(pGlbData, 0, MEM_BUFFER_LENGTH);    pFreeList = (MNG_NODE*)pGlbData;    pFreeList->size = MEM_BUFFER_LENGTH - sizeof(MNG_NODE);    pAllocList = NULL;}/************************************************** function: free memory buffer**************************************************/void mem_exit(){    if(NULL != pGlbData)        free(pGlbData);       pFreeList = NULL;    pAllocList = NULL;}/************************************************** function: file starts here**************************************************/int main(int argc, char* argv[]){    mem_init();    mem_exit();    return 1;}

1楼qinxiongxu15分钟前: 不错~~

热点排行