memory.cpp

使用双向循环链表实现的动态内存管理

// F0603036 林毅  5060309900
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
              
struct map {           
   unsigned m_size;
   char *m_addr;
   struct map *prior,*next;
};
struct map *coremap,*start;


void output()  //输出表函数
{
	int j=0;
	struct map *p;
	if(coremap==NULL)    //无空闲区
		printf("now all the free memories have been assigned.\n");
	else{
		printf("now the free memory list is as following:\n");
		printf("%s\t%s\n","address","size");
		for(p=coremap;(p!=coremap)||(j==0);p=p->next){  //用p进行遍历，j作为标记，防止重复输出
			if(p->next==coremap)j+=1;
			printf("%d\t%d\n",p->m_addr,p->m_size);  //打印空闲区起始地址和大小
		}
	}
}



char *  lmalloc(unsigned size)  //内存分配函数
{
	struct map *p;
	char *a;
	int g=0;
	if(coremap==NULL)return(0); //无空闲供分配
	else{
		for(p=start;(p!=start)||(g==0);p=p->next){ //用p进行遍历，g作标记
			if(p->next==start)g+=1;
			if(p->m_size>=size){   //首次搜索到合适的空闲区
				a=p->m_addr;       
				p->m_addr+=size;
				p->m_size-=size;
				start=p;           //修改起始查询指针
				if(p->m_size==0){    //整块空闲区被利用,删除该项,并使start指向下块空闲区
					if(p->next==p)   //如果链表中原来只有一空闲区，则设coremap和start为空
						start=coremap=NULL;
					else{
						p->next->prior=p->prior;
						p->prior->next=p->next;
						start=p->next;
						if(p==coremap)coremap=p->next; //如果删除的是链表第一项，则使coremap指向下一项
					}
                    free(p); //释放被删除项
				}
					
				return(a);  
			}
		}
	return(0);   //分配失败
	}
}



void lfree(unsigned size,char *addr)  //内存释放函数
{
	int h=0,g=0;
    struct map *p,*q;
	if(coremap==NULL){  //表中原无空闲区,则新建空闲区,并初始化表格
		coremap=(struct map*)malloc(sizeof(struct map));
		coremap->m_addr=addr;
		coremap->m_size=size;
		coremap->prior=coremap;
		coremap->next=coremap;
		start=coremap;
		output();
	}

	else{
		for(p=coremap;(p!=coremap)||(g==0);p=p->next){ //用p遍历，g作标记
			if(p->next==coremap)g+=1;  
			if(p->m_addr>addr){   //找到第一个首地址大于所需释放起始地址的内存块
				if(p==coremap){    //在链表的开头添加新的空闲区
					if((addr+size)==p->m_addr){  //释放内存区的下界刚好和原链表首项所指地址相接
						coremap->m_size+=size;
						coremap->m_addr-=size;
						h=1;
					}
					else if((addr+size)<p->m_addr){  //释放内存区的下界在原链表首项所指地址的上端
						q=(struct map*)malloc(sizeof(struct map));
						q->m_addr=addr;
						q->m_size=size;
						q->prior=coremap->prior;
						q->next=coremap;
                        coremap->prior->next=q;
						coremap->prior=q;
						coremap=q;
						h=1;
					}
				}
				else if((addr+size)==p->m_addr){   //释放内存区在原链表中间的某两项所指空闲块之间且下界刚好和后一项首地址相接
					if(addr==(p->prior->m_addr)+(p->prior->m_size)){   //上界刚好和前一项尾地址相接
						p->prior->next=p->next;
						p->next->prior=p->prior;
						p->prior->m_size=p->prior->m_size+size+p->m_size;
                        if(start==p)start=p->prior;
						free(p);
						h=1;
					}
					else if(addr>(p->prior->m_addr)+(p->prior->m_size)){ //上界在前一项尾地址下方
					p->m_size+=size;
					p->m_addr-=size;
					h=1;
					}
				}
				else if((addr+size)<p->m_addr){    //释放内存区在原链表中间的某两项所指空闲块之间且下界在后一项首地址前面
					if(addr==(p->prior->m_addr)+(p->prior->m_size)){ //上界刚好和前一项尾地址相接
						p->prior->m_size+=size;
						h=1;
					}
					else if(addr>(p->prior->m_addr)+(p->prior->m_size)){ //上界在前一项尾地址下方
						q=(struct map*)malloc(sizeof(struct map));  
						q->m_addr=addr;
						q->m_size=size;
						q->prior=p->prior;
						q->next=p;
						p->prior->next=q;
						p->prior=q;
						h=1;
					}
				}
				break;     
			}
		}
		if(h==1)output(); 
		else   
		{  
			if((p==coremap) && p->prior->m_addr<addr){    //考虑释放区在原链表尾项所指空闲块后面
				if(p->prior->m_addr+p->prior->m_size==addr){  //上界刚好和该项尾地址相接
					p->prior->m_size+=size;
					output();
				}
				else if(p->prior->m_addr+p->prior->m_size<addr){   //上界在该项尾地址后面
					p->prior->next=(struct map*)malloc(sizeof(struct map));
					p->prior->next->m_addr=addr;
                    p->prior->next->m_size=size;
                    p->prior->next->prior=p->prior;
                    p->prior->next->next=coremap;
					p->prior=p->prior->next;
					output();
				}
				else
					printf("Invalid command!\n");   
			}
			else
				printf("Invalid command!\n");
		}
	}
}


int main()
{
    char * lmalloc(unsigned size);
    void lfree( unsigned size,char *addr);
	char str1[10];unsigned int a1;char *a2;
	char *x,*y;
	coremap=(struct map*)malloc(sizeof(struct map)); 
	y=coremap->m_addr=(char *)malloc(1000);   //申请内存区
	if(coremap->m_addr==0)   //若申请失败,则程序结束   
	{
		printf("out of memory\n");
		return 1;
	}
	start=coremap;           //链表初始化
	coremap->m_size=1000;
	coremap->prior=coremap;
	coremap->next=coremap;
	printf("The initial free memory is as following:\n");
    printf("%s\t%s\n","address","size");
	printf("%d\t%d\n",coremap->m_addr,coremap->m_size);
	do{                  
		printf("Please enter your command(malloc/free):\n"); //读取命令
		do{
			scanf("%s",str1);
		}while(strcmp(str1,"malloc")!=0 && strcmp(str1,"free")!=0);
		if(strcmp(str1,"malloc")==0){         //分配内存并输出结果
			scanf("%u",&a1);
			printf("%s\t%u\n",str1,a1);
			if(a1<=0)printf("Invalid command!\n");
			else{
				x=lmalloc(a1);               //调用lmalloc函数
				if(!x)printf("No available memory!\n");
				else{
					printf("The assigned memory start from address:%u\n",x);
					output();
				} 
			}
		}
		else if(strcmp(str1,"free")==0){   //释放内存并输出结果
			scanf("%u %u",&a1,&a2);
			printf("%s\t%u\t%u\n",str1,a1,a2);
			if(a1<=0 || a2<y || (a2+a1)>(y+1000))  //考虑超出申请内存范围的情况
				printf("Invalid command!\n");
			else
				lfree(a1,a2);  //调用lfree函数
		}
		else
			printf("Invalid command!\n");
		printf("Continue?\n");
		do{
			printf("'y' for yes and 'n' to exit:\n");   //读取命令决定是继续进行内存操作或退出程序
			scanf("%s",str1);
			printf("%s\n",str1);
		}while(strcmp(str1,"y")!=0 && strcmp(str1,"n")!=0);

	}while(strcmp(str1,"y")==0);
	free(y);  //释放申请内存
	return 0;
}