memory_bitmap.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 TURE 1
#define FALSE 0
char memory[MEM_SIZE];
char bitmap[MEM_SIZE];

void* GetBlock(unsigned int size);
int FreeBlock(void* pBlock);
int IsFree(int unit);
void Init_Mem(void);
/**************************************************************************
 *Function name:Init_Mem               							      *
 *Return Type:  void                									  *
 *Definations:															  *
 * initializtion the link table ,it includes only one block-the total     *
 *************************************************************************/
void Init_Mem()
{
	int i;
	for(i=0;i<MEM_SIZE;i++)
	{
		bitmap[i]='N';
	}
}
/**************************************************************************
 *Function name:GetBlock                								*
 *Return Type:  Adrress Pionter             							*
 *Definations:                  										*
 *  在数组memory的分配size大小的内存块，把首地址返回。      			*
 *  如果分配失败，返回NULL              								*
**************************************************************************/
void* GetBlock(unsigned int size)
{
	/* first Fit*/
	int i,j,tag;
	tag=0;
	for(i=0;i<MEM_SIZE;i++)
	{
		//Judge the cell in Memory which is NUll
		//get the first cell count
		if(bitmap[i]=='N')
		{
			for(j=i;j<size;j++)
			{
			//Judge if the avilibal Memory size is Large enough to hold
			//if so ,come on.and get it ,else return Error
				if(bitmap[j]!='N')
					//case can't hold
				{
					tag=1;
					break;//here should be implement as function ,and turn i to i+size;
				}
			}
			if(tag==1)
			{
				tag=0;
				continue;
			}
			//Mark cells with char'A' as being allcated
			for(j=i;j<i+size;j++)
			{
				bitmap[j]='A';
				
			}
			bitmap[j-1]='E';
			return &memory[i];
		}
		//return Error code o as loop reach the end,cell can't be allocated.
		if(i>=MEM_SIZE-1&&size>1)
			return 0;

	}

	return memory;
}
/**************************************************************************
 *Function name:FreeBlock               								 *
 *Return Type:  int                 									 *
 *Definations:                  										 *
 * 释放首地址为pBlock的内存块。             							 *
   成功返回非0值，失败返回0                 							 *
**************************************************************************/
int FreeBlock(void* pBlock)
{
	char * pCell;
	while(((int)pCell-(int)bitmap)!=((int)pBlock-(int)memory))
		pCell++;
	(char *)pCell;
	for(;(*pCell)!='E';pCell++)
	{
		(*pCell)='N';
	}
	(*pCell)='N';
	return !0;
}
/***************************************************************************
*Function name: IsFree                      					          *
*Return Type:   int                 									  *
*Definations:                   										  *
* 判断数组memory中下标为unit的单元是否被占用。          				  *
*  空闲返回非0，否则返回0               								  *
***************************************************************************/

int IsFree(int unit)
{
	if(bitmap[unit]=='N')
		return !0;
	if(bitmap[unit]=='A'||bitmap[unit]=='E')
		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;
    Init_Mem();
    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;
}