neicun.c

我所采用的内存管理思想是链表管理思想

/* 内存管理实验程序
 * 作者：朱睿
 * 把一个数组模拟为内存，然后针对该块内存实现内存的分配和回收算法
*/

#include <stdio.h>

#define MEM_SIZE 80
char mm[MEM_SIZE];

void* mm_request(unsigned int size);
int mm_release(void* pBlock);
int IsFree(int unit);

/*********************************************************************************************/
struct node
{
    char* p;
    int memosize;
    int flag;
    struct node* next;
};
typedef struct node* NODE;
NODE list = NULL;

/*********************************************************************************************/
//初始化链表，产生空闲内存

void mm_init()
{
    list = (NODE)malloc( sizeof( struct node ) );
    list->p = mm;
    list->memosize = MEM_SIZE;
    list->flag = 0;
    list->next = NULL;
}

/*****************链表按空闲区由小到大排序***************************************************/
void sort()        
{
    struct node *ptr1 = list;
    struct node *ptr2 = ptr1->next;
    int temp;
   
	while(ptr1!=NULL)
    {
		ptr2 = ptr1->next;
        
		while(ptr2!=NULL)
        {
            if(ptr1->memosize>ptr2->memosize)
            {
                //交换空闲区大小
				temp = ptr1->memosize;
                ptr1->memosize = ptr2->memosize;
                ptr2->memosize = temp;

				//交换首地址
                temp = ptr1->p;
                ptr1->p = ptr2->p;
                ptr2->p = temp;


            }
            ptr2 = ptr2->next;
            
        }//while ptr2
        ptr1 = ptr1->next;

            
    }//while ptr1

	
}//End sort
/*********************************************************************************************/
// 在数组mm的分配size大小的内存块，把首地址返回，如果分配失败，返回NULL 

void* mm_request(unsigned int size)
{
    NODE comp ,listnode;
    comp = list;
   
    //找到大于或等于所需内存大小的内存空间块
    while( ( comp != NULL )&&( ( comp->flag == 1 )||( comp->memosize < size ) ) )
            comp = comp->next;

     if( comp==NULL )
        return NULL;

    //从中划分一块出来供它用之
    else if( comp->memosize > size  )
    {
        listnode = (NODE)malloc(sizeof( struct node ) );
        listnode->p = comp->p + size;
        listnode->memosize = comp->memosize - size;
        listnode->flag = 0;
        listnode->next = comp->next;
        comp->memosize = size;
        comp->flag = 1;
        comp->next = listnode;
        return comp->p;
    }
    return NULL;
}
/*********************************************************************************************/
// 释放首地址为p的内存块，成功返回非0值，失败返回0 

int mm_release(void* p)
{
    NODE comp,temp;
    comp = list;
    /*若释放的内存为第一块内存，则直接将其标志为0*/
    if( comp->p == (char*)p )
    {
        comp->flag = 0;
        /*若它的下一个结点可以与它合并，则将其合并*/
        if( comp->next->flag == 0 )
        {
            comp->memosize = comp->memosize + comp->next->memosize;
            temp = comp->next;
            comp->next = temp->next;
            free( temp );
        }
        return 1;
    }
    /*若内存块为其他结点所指的内存块，则循环去找到合符要求的内存块*/
    else
    {
        while ( ( comp->next != NULL )&&( comp->next->p != (char *)p ) )
            comp = comp->next;
        if( comp->next == NULL )
            return 0;
        else if( comp->next->p == (char*)p )
        {
            comp->next->flag = 0;
            /*需要合并下一个结点则并之，需要合并上一个结点则并之*/
            if( ( comp->next->next != NULL )&&( comp->next->next->flag == 0 ) )
            {
                comp->next->memosize = comp->next->memosize + comp->next->next->memosize;
                temp = comp->next->next;
                comp->next->next = temp->next;
                free( temp );
            }
            if( comp->flag == 0 )
            {
                comp ->memosize = comp->memosize + comp->next->memosize;
                temp = comp->next;
                comp->next = temp->next;
                free ( temp );
            }
            return 1;
        }
    }
    return 0;
}

/*********************************************************************************************/
// 判断数组mm中下标为unit的单元是否被占用， 空闲返回非0，否则返回0 

int IsFree(int unit)
{
    NODE comp;
    char* B;
    comp = list;
    B =   mm + unit ;
    /*循环找到单元内存所在结点结点，若结点标志为1则返回0，否则返回1*/
    while( comp != NULL )
    {
        if( ( (comp->p ) <= B )&&( ( comp->p ) + comp->memosize -1 >=  B  ) )
        {
            if( comp->flag == 0 )
                return 1;
            else
                return 0;
        }
        comp = comp->next;
    }
    return  0;
}


/*********************************************************************************************/
// 测试代码

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

void PrintMemoryUsage(void);
int New(struct BLOCK *pBlocks);
int Delete(struct BLOCK *pBlocks);
int ranReq();
int ranRel();
int total = 0;

int main(void)
{
    struct BLOCK blocks[BLOCK_COUNT] = {0,0};

    int ch = 0;
    int rtn = 1;
    int i;


    mm_init();

    do
    {  switch (ch)
        {
        case 'n':
			//do{
				rtn = New(blocks);
			//}while(rtn==1);          //去掉此处注释可以实现自动分配
            break;
        case 'd':
            rtn = Delete(blocks);
            break;
        case '\n':
            continue;
            break;
        }
	if(rtn!=-1)
	{
		printf("The rate of memory use is: %f \n",((float)(total))/((float)MEM_SIZE));

        PrintMemoryUsage();
        printf("Input \'n\' to new, \'d\' to delete and \'q\' to quit:");
	}
	else  {printf("\nError!!!!\n"); printf("The rate of memory use is: %f \n",((float)(total))/((float)MEM_SIZE));break;}
    } while ((ch=getchar()) != 'q'&&rtn == 1);

    /* 删除所有已申请的block */
    for (i=0; i<BLOCK_COUNT; i++)
    {
        if (blocks[i].p != NULL)
        {
            mm_release(blocks[i].p);
        }
    }
    
    return 0;
}

/* 打印memory分配情况 */
void PrintMemoryUsage(void)
{
    int i;
    putchar('\n');

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

    putchar('\n');
}

/* 新申请block */
int New(struct BLOCK *pBlocks)
{
    int size=ranReq();
    while (pBlocks->p != NULL)
        pBlocks++;
    pBlocks->p = mm_request(size);
    pBlocks->size = size;
	if(total+size<MEM_SIZE)
    {
		total+=size;
		return (pBlocks->p != NULL);}
	else return(-1);
    

}

/* 删除已经申请的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 (mm_release(pBlocks[i].p))
    {
        pBlocks[i].p = NULL;
        return !0;
	
    }
    else
        return 0;
}

//**********************产生1—50之间的随机数*************************************************
int ranReq()
{  
	int i; 
     
	do{i = rand()%20;}while(i==0);
     //printf("%d\n", rand()%100); 
      
	return i;
}//End random

int ranRel()
{  
	int i; 
     
	do{i = rand();}while(i<0||i>=MAX_BLOCK_SIZE);
     
	printf("%d\n", i); 
      
	return i;
}//End random*/