test2.c

高效内存管理函数实现。VC＋＋实现

#include <stdio.h>
#include <stdlib.h>

#define TOTALMEMORY 1100
char MEMSpace[TOTALMEMORY];

void MEMInit(void);
char *MyAlloc(unsigned int size);
void  MyFree(char*p);

typedef struct list
{
  struct list * pre;//上一块空闲区或使用区指针，NULL表示为第一块空闲区或使用区
  unsigned int size;//空闲区或使用区大小
  struct list * next;//下一块空闲区或使用区指针，NULL表示为最后一块空闲区或使用区
}MCB;

struct memory
{
   char *memorybase;		//内存区首地址 
   long memorysize;			//内存区大小
   struct list * AllocList;	//使用链
   struct list * FreeList;	//空链
};
struct memory sMEM;
//****************************main()*************************//
void main()
{  
    char *ch[20];
	MEMInit();
    ch[1] = MyAlloc(300);	
    ch[2] = MyAlloc(300);
	ch[3] = MyAlloc(200);
	ch[4] = MyAlloc(200);
	MyFree(ch[1]);
	MyFree(ch[3]);
	ch[5] = MyAlloc(600);
	MyFree(ch[2]);
	ch[6] = MyAlloc(600);
}

void MEMInit(void)
{
    sMEM.memorybase = MEMSpace;
    sMEM.memorysize = TOTALMEMORY;
    sMEM.AllocList = NULL;
    sMEM.FreeList = (MCB *)MEMSpace;
    sMEM.FreeList->size = TOTALMEMORY - sizeof(MCB *);
    sMEM.FreeList->next = NULL;
    sMEM.FreeList->pre = NULL; 
    printf("Mem Inited success, test begin......管理1000字节空间\n");
}


char * MyAlloc(unsigned int size)
{
 struct list *CurList; 
 struct list *AllocMCB;
 struct list *NextList;//NextList ==>TmpList
 AllocMCB = sMEM.FreeList;//初始化AllocMCB
 NextList = sMEM.FreeList;//初始化NextList
 for(CurList = sMEM.FreeList; CurList!=NULL; CurList = CurList->next)
 {
          if (size<=(CurList->size)) //最先适应，找到就给它
          {   
			  if(size<=(CurList->size-sizeof(MCB)))//一分为二
              { 
                 AllocMCB = CurList;
			     CurList =(struct list*) (CurList+size+sizeof(struct list));
				 CurList->size = AllocMCB->size-size-sizeof(struct list);
				 CurList->next = AllocMCB->next;
                 CurList->pre = AllocMCB->pre;
				 if(AllocMCB->pre!=NULL)
					 (AllocMCB->pre)->next = CurList;
				 else sMEM.FreeList = CurList;
				 AllocMCB->size = size;
				 printf("分到%d字节的一块内存，余下的可划分为一块！\n",size);
              }
			  else
			  {     
					if(CurList->size==size) printf("刚好分到%d块内存！\n",size);
					else 
						printf("分到%d块内存,余下的不能划分为一块！\n",size);
					AllocMCB = CurList;
					NextList = CurList->pre;
					CurList = CurList->next;
					if(CurList!=NULL) 
						CurList->pre = NextList;
					if(NextList!=NULL) 
						NextList->next = CurList;
					else 
						sMEM.FreeList = CurList;
			  }              
              // 加入 sMEM.AllocList,直接放到头就可以
			  NextList = sMEM.AllocList;
              sMEM.AllocList = AllocMCB;
			  sMEM.AllocList->pre = NULL;
			  sMEM.AllocList->next = NextList;
			  if(NextList!=NULL) 
				  NextList->pre = sMEM.AllocList;
              return (char*) (AllocMCB + sizeof(MCB));//实际数据空间
          }
	 }
	 printf("内存不够，没有分到%d块内存！\n",size);
	 return NULL;
}

void MyFree(char*p)
{   int mark1 = 0;
    int mark2 = 0,size;
	struct list *NextList; 
	struct list *CurCtlList;
    struct list *PreList;
    CurCtlList = sMEM.FreeList;//初始化CurCtlList
    PreList = sMEM.FreeList;//初始化PreList 
	if(p==NULL) 
		printf("此变量内存已经释放了，不要再释放！\n");
	else
	{
		for(NextList = sMEM.AllocList;NextList!=NULL;NextList = NextList->next)
		{
			  if(p == (char *)(NextList+sizeof(MCB)))//在 sMEM.AllocList找到了
			  {		  
					CurCtlList = NextList;
					size = NextList->size;
					if(NextList->pre==NULL && NextList->next==NULL)
					{
						mark1 = 1;
						sMEM.AllocList=NULL;
						break;
					}
					else if(NextList->pre==NULL && NextList->next!=NULL)
					{
						sMEM.AllocList = (sMEM.AllocList)->next;
						(sMEM.AllocList)->pre =NULL;
						mark1 = 1;
						break;
					}
					else if(NextList->pre!=NULL && NextList->next==NULL)
					{
						(NextList->pre)->next=NULL;
						mark1 = 1;
						break;
					}
					else//中间的块
					{
						  PreList = NextList->pre;
						  NextList = NextList->next; 
						  if(NextList!=NULL) 
							  NextList->pre = PreList;
						  if(PreList!=NULL)
							  PreList->next = NextList;
						  mark1 = 1;
						  break;
					} 
			  }
		}
		if(mark1!=1) 
			printf("错误：要释放的内存块不是本函数分配的！\n");
		else
		{
		mark1 = 0;   
		if(sMEM.FreeList==NULL) 
			sMEM.FreeList = CurCtlList;
		else
		{
			for(NextList = sMEM.FreeList; NextList!=NULL; NextList = NextList->next)
			{
			   if(CurCtlList<NextList)//插在NextList的前面
			   {
				 PreList = NextList->pre;
				 if(PreList!=NULL)
					 PreList->next = CurCtlList;
				 else 
					 sMEM.FreeList = CurCtlList;
				 CurCtlList->pre = PreList;
				 CurCtlList->next = NextList;
				 NextList->pre = CurCtlList;
				 break;
			   }
			}
		}// 再检查相临的是否需要合并,先检查和前面的是否能合并
		if(PreList!=NULL)
		{
			if((PreList + PreList->size + sizeof(MCB))==CurCtlList)
			{		  //合并
				PreList->size = PreList->size + CurCtlList->size + sizeof(MCB);
				PreList->next = NextList;
				NextList->pre = PreList;
				CurCtlList = PreList;
				mark1 = 1;
			}
		} 	//再检查跟后面的是否能合并
		if(CurCtlList->next!=NULL)
		{
			if((CurCtlList + CurCtlList->size + sizeof(MCB)) == NextList)
			{            //合并
				CurCtlList->size = CurCtlList->size + NextList->size + sizeof(MCB) ;
				CurCtlList->next = NextList->next;
				if(NextList->next!=NULL)(NextList->next)->pre = CurCtlList;
				mark2 = 1;
			}
		}
		if(mark1==0 && mark2==0) 
			printf("释放%d块内存成功，没有合并\n",size);
		else if(mark1==0 && mark2==1) 
			printf("释放%d块内存成功，释放块与后面块合并\n",size);

		else if(mark1==1 && mark2==0) 
			printf("释放%d块内存成功，释放块与前面块合并\n",size);
		else 
			printf("释放%d块内存成功，释放块与前，后块合并\n",size);
		}
	}
}