mem.cpp

内存管理系统

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

#define MEM_SIZE 64

static char memory[MEM_SIZE];       /*用字符数组来模拟内存 */


void* GetBlock(unsigned int size); /*分配 size 大小的内存 */
int FreeBlock(void* pBlock);        /*释放指针所指向的使用完毕的内存段 */

int IsFree(int unit);               /*判断这个内存单元是否正在被使用 */

/**************************结构体blockState及相关部分*************************************/
/* 此结构体用来记录内存的各个已被使用的和未被使用的模块
** 包括： 
**    int begin;         --> 此模块开始的点
      int end;           --> 此模块结束的点
      int state;         --> 表示是否为空闲(1表示已使用，0表示未使用)
      blockState * next; --> 指向下一个模块
*/
typedef struct blockState
{
int begin; 
int end;
int state;
struct blockState * previous;
struct blockState * next;
}blockState;
blockState * first;     //链表头指针,important!
int once = 0;

void init()             //初始化链表的函数，只被调用一次，因为不可以修改测试函数，所以放到这里
{
//printf( "Call init, Cause it need to initialize\n" );
first = ( blockState * )malloc( sizeof(blockState) );
if( !first )
{
   printf( "failed to create struct first!" );
   exit(0);
}
first->begin = 0;
first->end = MEM_SIZE -1;
first->state = 0;
first->previous = NULL;
first->next = NULL;
once = 1;
}
/***************************结构体blockState及相关部分结束*******************************/

/******************************GetBlock()函数开始**************************************/
/**
* 这个函数是这样工作的，首先是初始化一个链表，每一个节点由上面的结构体blockState来
* 组成，代表了申请的一个内存块。
* 当新申请一个新的内存块时，从链表头部开始查找没有被申请且大小满足大小的模块，
* 然后修改代表这个块的原链表节点，使其begin和end域符合要求，即代表了新申请的内存块了。
* 然后新建立一个链表节点，代表被破坏的原内存块的另一部分。
*/
void * GetBlock(unsigned int size) 
{   
blockState * tmp;   //循环链表的临时变量
blockState * tmp2;

    /**
* 循环检查链表，找到一个足够大的模块
* 因为是采用first fit算法，所以从开始一个一个寻找就好了
* 里面一些列的指针赋值就是最基本的双向链表的插入算法
* 数据结构课本上都有，没什么好解释的
*/ 
    tmp = first;
    while( tmp != NULL ) 
    { 
	   //printf( "tmp.state=%d | tmp.end = %d| tmp.begin=%d | size=%d\n", tmp->state, tmp->end, tmp->begin, size );
	   if ( (tmp->state == 0) && ((tmp->end - tmp->begin + 1) > size) )
	   {
			blockState * newBlock = (blockState *)malloc( sizeof(blockState) );
			newBlock->previous = tmp;
			newBlock->next = tmp->next;
			tmp2 = tmp->next;
			if ( tmp2 != NULL )
			{
				tmp2->previous = newBlock;
			}
			tmp->next = newBlock;
			newBlock->end = tmp->end;
			tmp->end = ( tmp->begin + size - 1 );//比如说，申请四个，是从0-3
			tmp->state = 1;  
			newBlock->begin = (tmp->end+1);
			newBlock->state = 0; 
			return &memory[tmp->begin];          //找到了，返回
	   }
	   else if ( (tmp->state == 0) && ((tmp->end - tmp->begin+ 1) == size) )
	   {
			//printf( "恰好\n" );
			tmp->state = 1;                      //如果是正好的大小，直接修改并返回
			return &memory[tmp->begin];
	   }
	   else
			tmp = tmp->next;

    } 
}
/***************************GetBlock()函数结束**************************************/

/***************************FreeBlock()函数开始************************************/
/** 函数传入的是
*    struct BLOCK
*     {
*    void * p;
*    int size;
*     }; 
* 的那个p域，不是传入的BLOCK结构体!!
*
* 该函数需要执行的操作是将这个块的内存释放
* 成功返回非0不成功返回0
* 注意，删除的时候不能简单的把原来的模块的state设置为0，你要知道
* 删除以后，内存的结构已经发生改变了，所以链表要相应的改变，
* 否则在以后重新申请的时候就会出错了，很显然
* 里面那一系列的指针赋值是双向链表的最基本的，最常规的算法，所以
* 没什么好解释的。数据结构书上都有
*/
int FreeBlock( void * pBlock_p )
{
    blockState * tmp = first;
    blockState * tmp2; //用于得到tmp前面的那个节点
blockState * tmp3; //只是用做暂存一下而已，无奈之举

while ( tmp != NULL )
{
   if ( (tmp->state == 1) && ( &memory[tmp->begin] == pBlock_p) )
   {
    /*****
    * 下面这块判断将要删除的这个块的前面是不是空的，如果是，先删除，然后将两个空白块合并
    * 这是很朴素、很自然的
    */
      tmp2 = tmp->previous; 
    if ( (tmp2 != NULL) && (tmp2->state == 0) )
    {   
     tmp2->next = tmp->next;
     tmp3 = tmp->next;
     tmp3->previous = tmp2;
     tmp2->end = tmp->end;
     free( tmp );      //现在tmp里面已经不存放东西了，应该释放内存
     tmp = tmp2;       //tmp2只是个临时变量，tmp是不能没有的，因为它全局的东东，如果它没了，其他地方便不能调用了  
    }

    /******
    * 下面这部分判断要删除的当前块的后面是不是空
    * 如果是空，把两者做合并处理
    **/
    tmp3 = tmp->next;     //因为tmp->next->state的方式不能编译通过，所以折中了一下
    if ( (tmp3 != NULL) && (tmp3->state == 0) )
    {
     tmp->next = tmp3->next;
     tmp->end = tmp3->end;
     free( tmp3 );     //这个tmp3(也就是要删除的tmp的下一个)里面已经不存东西了，释放之
    }

        
    tmp->state = 0;
    return 1;
   }
   else
    tmp = tmp->next;
}

   return 0;

}
/***************************FreeBlock()函数结束************************************/


/***************************IsFree()函数开始************************************/
/****
* 此函数判断内存的unit单元是否被使用。如果不是free（已经被申请使用）则返回0
* 是free则返回非0
* 感觉这个算法效率特低，如果内核这么写那肯定废了
* 正在改进ing...
*/
int IsFree( int unit )
{
blockState * tmp;

/****
* 下面这部分第一次初始化链表.
* 因为不允许修改测试函数，而链表的初始化必须在所有工作
* 之前调用，所以放在这里，IsFree()函数是在main函数里第一
* 次调用的一个函数，这样就保证了链表被正确初始化
* 而且这个函数由于试用了once变量，保证了只调用一次
* init函数，即只初始化一次链表
*/
if ( once == 0 )   
{
   init(); 
}

    tmp = first;
    while ( tmp != NULL )
    {
   if ( ( tmp->state == 1 ) && ( unit >= tmp->begin ) && ( unit <= tmp->end ) )
   {
    return 0;   //此内存块已经被申请，返回0
   }
   else
   {
    tmp = tmp->next;
   }
    }
return 1;           //链表循环完毕，未找到
}
/***************************IsFree()函数结束************************************/


/********************************************************************************/
/*以下为测试程序*/
#define MAX_BLOCK_SIZE 16
#define BLOCK_COUNT   MEM_SIZE

struct BLOCK
{
void * p;
int size;
};

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

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

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

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();
   printf("Input \'n\' to new, \'d\' to delete and \'q\' to quit:");

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


for (i=0; i<BLOCK_COUNT; i++)
{
   if (blocks[i].p != NULL)
   {
    FreeBlock( blocks[i].p );            
   }
}

return 0;
}


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('*');
}
printf("\n"); 
putchar('\n');
}


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);
}


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;
}