?? 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;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -