1. 题目

改造malloc和free函数，使C语言能自动发现泄漏的内存，在程序退出时打印中遗漏的内存地址和大小。

2. 思路

用一个链表来记录已经分配的内存地址。在malloc时，把分配的内存地址和大小插入链表；在free时，找到链表中相应结点，删除该结点。程序退出时，打印出链表中的结点。

上述思路有一个缺陷：删除结点时，需要遍历链表，如何才能变成常数时间能完成的操作？

方法是：在malloc时，多分配一块区域，用来记录链表结点的位置。

3. 代码

//Code 1

#include <stdlib.h>

typedef struct _PtrNode

{

    struct _PtrNode* prev;

    struct _PtrNode* next;

    void* locatedPtr;

    int size;

}PtrNode;

PtrNode* gRecordList;

void InitList()

{

    gRecordList = (PtrNode*)malloc(sizeof(PtrNode));

    gRecordList->prev = NULL;

    gRecordList->next = NULL;

}   

void InsertNode(PtrNode* pNode)

{

    if (NULL != gRecordList->next)

    {

        gRecordList->next->prev = pNode;

    }

    pNode->next = gRecordList->next;

    gRecordList->next = pNode;

    pNode->prev = gRecordList;

}   

void DeleteNode(PtrNode* pNode)

{

    if (NULL != pNode->next)

    {

        pNode->next->prev = pNode->prev;

    }

    pNode->prev->next = pNode->next;

    free(pNode);

}

void PrintLeek()

{

    PtrNode* pNode;

    for(pNode = gRecordList->next; pNode != NULL; pNode = pNode->next)

    {

        printf("leek:%x,%d\n", pNode->locatedPtr, pNode->size);

    }

}

void* MyMalloc(int size)

{

    void* ptr = malloc(size + sizeof(PtrNode*));

    PtrNode* pNode = (PtrNode*)malloc(sizeof(PtrNode));

    pNode->locatedPtr = ptr;

    pNode->size = size;

    *(PtrNode**)(ptr + size) = pNode;

    InsertNode(pNode);

    return ptr;

}

#define MyFree(pHandler) \

    do {\

        int size = sizeof(*pHandler); \

        PtrNode* pNode = *(PtrNode**)((void*)pHandler + size);\

        DeleteNode(pNode); \

        free(pHandler);\

    }while(0)

int main()

{

    InitList();

    int* p = (int*)MyMalloc(sizeof(int));

    p = (int*)MyMalloc(sizeof(int));

    PtrNode* p2 = (PtrNode*)MyMalloc(sizeof(PtrNode));

    MyFree(p);

    PrintLeek();

}