memory.c

用链表实现的内存管理

/*================================================================================
 * 内存管理实验程序之双向链表实现完成版V3.0
 * VitulMemoryManagement.c
 * 原理：
 *		把一个数组模拟为内存，然后针对该块内存实现内存的分配和回收算法
 * 作者：Sunner Sun&&Mark
 * 最后修改时间：2005-4-3 20：00
 * 本程序已在GNU gdb 5.1.1 (mingw experimental)环境下测试通过
 ===============================================================================*/
#include <stdio.h>

#define MEM_SIZE 80
#define ALLOCATED 1
#define FREE 0

char memory[MEM_SIZE];//内存
typedef struct NODE
{
 int status;
 int size;
 int startid;
 struct NODE * next;
 struct NODE * prev;
};
/*双向链表，记录各块的信息，依次分别对应：
1：状态（空闲？占用）；2：大小；3：开始标记（数组的下标）；
4：指向后继的指针；5： 指向前驱的指针                    */

struct NODE * Header;

struct NODE *   AllocateNode (    void        );
void*           GetBlock    (unsigned int size);
int             FreeBlock   (  void*	pBlock);
int             IsFree      (   int		  unit);
void            Initlizer   (void			  );
void			PrintBlockLinks();

/**************************************************************************
 *Function name:Initlizer               							      *
 *Return Type:  void                									  *
 *Definations:															  *
 * initializtion the link table ,it includes only one block-the total     *
 *************************************************************************/
void Initlizer()
{
    Header=(struct NODE *)malloc(sizeof(Header));
    if(Header)
    {
        Header->status=FREE;
        Header->size=MEM_SIZE;
        Header->startid=0;
        Header->next=NULL;
        Header->prev=NULL;
    }
    else 
    {
        printf("A fatal error occur at Initlizer ,Code:%d Can't Create Node",Header);
        exit(0);
    }
}
/**************************************************************************
 *Function name:AllcateNode             								*
 *Return Type:  Pionter                 								*
 *Definations:   Allcate a new Node               						*
 **************************************************************************/
struct NODE * AllocateNode(void)
{
    struct NODE * lp;
    lp =(struct NODE *)malloc(sizeof(lp));
    if(lp)
    {
        lp->status=FREE;
        lp->size=0;
        lp->next=NULL;
        lp->prev=NULL;
        lp->startid=0;
        lp->next=NULL;
        lp->prev=NULL;

        return lp;
    }
    else 
        return NULL;
}
/**************************************************************************
 *Function name:PrintBlockLinks            								*
 *Return Type:  void				           							*
 *Definations:  print block list while debug							*
**************************************************************************/
void PrintBlockLinks()
{
	struct NODE * p;
	int count=-1;
	p=Header;
	printf("In Link table\n");
	while(1)
	{
		if(p==NULL)
			break;
		if(count!=-1)
		printf("%d:%dAdrress:%ld\n",count,p->size,&memory[p->startid]);
		count++;
		if(p->next==NULL)
			break;
		p=p->next;
	}
}
/**************************************************************************
 *Function name:GetBlock                								*
 *Return Type:  Adrress Pionter             							*
 *Definations:                  										*
 *  在数组memory的分配size大小的内存块，把首地址返回。      			*
 *  如果分配失败，返回NULL              								*
**************************************************************************/

void* GetBlock(unsigned int size)
{
   struct NODE * slp,* lp,* newlink;
   int count=0;
   slp=Header;
   while(1)
   {
	count++;
    if(slp==Header)
    {
        if(slp->next!=NULL)
    	{
            slp=slp->next;
		            continue;
        }/*如果节点为头节点且有后继，则转到第一个节点，继续查询*/
        else
    	{
            lp=AllocateNode();
            lp->status=ALLOCATED;
            lp->startid=0;
            lp->prev=slp;
            slp->next=lp;
            lp->size=size;

            newlink=AllocateNode();
			lp->next=newlink;
            newlink->status=FREE;
            newlink->prev=lp;
            newlink->next=NULL;
			newlink->startid=(lp->size);
            newlink->size=(slp->size)-(lp->size);
            return &memory[lp->startid];


        }/*列表为空，申请新建节点，链接*/
    }
    /* 若该块已被申请*/
    if(slp->status==ALLOCATED)
    {
        if(slp->next==NULL)
		{
			 /*若已到列表结尾，无法申请则返回0*/
			return 0;
		}
       
        slp=slp->next;
		printf("continue 131");
        continue;
    }
    else
	if(slp->status==FREE)
    {
        if(size==slp->size)
		{
			slp->status=ALLOCATED;
            return &memory[slp->startid];
		}
		if(size>(slp->size))
    	{
            if((slp->next)==NULL)
			{ /*若已到列表结尾，无法申请则返回0*/
				return 0;
			}
				slp=slp->next;
            continue;
    		
    	}
        if(size<(slp->size))
    	{
            newlink=AllocateNode();
            slp->status=ALLOCATED;			
            newlink->size    =( slp->size)	- size;
            newlink->startid =(slp->startid)+ size;
            newlink->prev    = slp;
            newlink->next    = slp->next;
            slp->next        = newlink;
			slp->size		 =size;
            
			return &memory[slp->startid];
    		
    	}
    }

   }
   printf("Fatal Error");
    return 0;
}
/**************************************************************************
 *Function name:FreeBlock               								 *
 *Return Type:  int                 									 *
 *Definations:                  										 *
 * 释放首地址为pBlock的内存块。             							 *
   成功返回非0值，失败返回0                 							 *
**************************************************************************/
int FreeBlock(void* pBlock)
{  
    struct NODE * lp,* lpprev,* lpnext;
    lp=Header->next;
    if(lp==NULL)
        return 0;
    /* 列表还未曾创建，无法释放*/
    while(1)
    {
		if((&memory[lp->startid])==pBlock)
			break;
        if(lp->next==NULL)
            return 0;
        lp=lp->next;
    }
    if(lp->status==FREE)
        return 0;
	/*找到首地址对应的块*/
	
    else
    {
        /*标记为空闲*/
		lp->status=FREE;
        lpprev=lp->prev;
        lpnext=lp->next;
        if(lpprev->status==FREE)
    	{
            if(lpprev->prev!=NULL)/*前驱不是头节点*/
    		{
                lp->startid=lpprev->startid;
				lp->size=lpprev->size+lp->size;
                if(lpprev->prev!=NULL)
				{
					lp->prev=lpprev->prev;
                    lpprev->prev->next=lp;

				}
				free(*lpprev);			
    		}
                /* 合并，释放*/

    	}
		else 
			if((lpnext!=NULL)&&(lpnext->status==FREE))
			{
                	lp->size=lp->size+lpnext->size;	
					lp->next=lpnext->next;
					if(lpnext->next!=NULL)
						lpnext->next->prev=lp;
					free(*lpnext);    		
				/* 合并，释放*/	
    		}
        return !0;
    }
	printf("Unkown Error!\n");
    return 0;
}
/***************************************************************************
*Function name: IsFree                      					          *
*Return Type:   int                 									  *
*Definations:                   										  *
* 判断数组memory中下标为unit的单元是否被占用。          				  *
*  空闲返回非0，否则返回0               								  *
***************************************************************************/

int IsFree(int unit)
{
    struct NODE * lp;
    lp=Header;
    if(lp->next==NULL)
        return !0;
    lp=lp->next;
    while(1)
    {
        if((lp->startid)<=unit)
        {   if(((lp->startid+lp->size)-1)>=unit)
    		{
                if(lp->status==ALLOCATED)
                	return 0;
                return !0;
    		}
        	else
    		{
				if(lp->next==NULL)
                return 0;
                lp=lp->next;
            	continue;
    		}
    	}
        else
    	{
            if(lp->next==NULL)
                return 0;
    	}
    }
   
}


/************************************************
 * 下面为测试代码，不需要修改，也不许使用其定义 *
 * 的各种变量、宏、结构等                       *
 ************************************************/

#define MAX_BLOCK_SIZE  16
#define BLOCK_COUNT     80
struct BLOCK
{
    void* p;
    int size;
};

void PrintMemoryUsage(void);
int New(struct BLOCK *pBlocks);
int Delete(struct BLOCK *pBlocks);
void ShowBlock(struct BLOCK *pBlocks);

int main(void)
{
    struct BLOCK blocks[BLOCK_COUNT] = {0,0};
    int ch = 0;
    int rtn = 1;
    int i;
    Initlizer();
    do
    {
        switch (ch)
        {
        case 'n':
            rtn = New(blocks);
            break;
        case 'd':
            rtn = Delete(blocks);
            break;
		
        case '\n':
            continue;

            break;
        }
        if (!rtn)
            printf("\nError!!!!\n");
        PrintMemoryUsage();
		//ShowBlock(blocks);
		//PrintBlockLinks();
        printf("Input \'n\' to new, \'d\' to delete and \'q\' to quit:");

    } while ((ch=getchar()) != 'q');

    /* 删除所有已申请的block */
    for (i=0; i<BLOCK_COUNT; i++)
    {
        if (blocks[i].p != NULL)
        {
            FreeBlock(blocks[i].p);
        }
    }
    
    return 0;
}
/***************************************************************************
*Function name: ShowBlock                    					          *
*Return Type:   int                 									  *
*Definations:    打印当前的分块情况               										  *
***************************************************************************/
void ShowBlock(struct BLOCK *pBlocks)
{
	int i;
	for (i=0; i<BLOCK_COUNT; i++)
	{
		if (pBlocks[i].p != NULL)
		{
			printf("%d: %d :Adrress:%ld\n", i, pBlocks[i].size,pBlocks[i].p);
		}
	}
}
/***************************************************************************
*Function name: PrintMemoryUsag                    					      *
*Return Type:   int                 									  *
*Definations:打印memory分配情况    										  *
***************************************************************************/
void PrintMemoryUsage(void)
{
    int i;

    putchar('\n');
    
    for (i=0; i<MEM_SIZE; i++)
    {
        if (i%10 == 0)
            putchar('|');
        else
            putchar(' ');
    }
    
    putchar('\n');

    for (i=0; i<MEM_SIZE; i++)
    {
        if (IsFree(i))
            putchar('-');
        else
            putchar('*');
    }
    putchar('\n');
                    
}

/***************************************************************************
*Function name: New                             					      *
*Return Type:   int                 									  *
*Definations: 新申请block  												  *
***************************************************************************/

int New(struct BLOCK *pBlocks)
{
    int size = 0;

    while (size < 1 || size > MAX_BLOCK_SIZE)
    {
        printf("Size?[1-%d]", MAX_BLOCK_SIZE);
        scanf("%d", &size);
    }

    while (pBlocks->p != NULL)
        pBlocks++;

    pBlocks->p = GetBlock(size);
    pBlocks->size = size;

    return (pBlocks->p != NULL);
}
/***************************************************************************
*Function name: Delete                            					      *
*Return Type:   int                 									  *
*Definations: 删除已经申请的block 										  *
***************************************************************************/
int Delete(struct BLOCK *pBlocks)
{
    int i;

    for (i=0; i<BLOCK_COUNT; i++)
    {
        if (pBlocks[i].p != NULL)
        {
            printf("%d:%d\t", i, pBlocks[i].size);
        }
    }
    printf("\nWhich to delete:");
    scanf("%d", &i);
    if (FreeBlock(pBlocks[i].p))
    {
        pBlocks[i].p = NULL;
        return !0;
    }
    else
        return 0;
}