/* 
 * 內存管理實驗程序殘缺版 1.2.2
 * 把一個數組模擬為內存，然后針對該塊內存實現內存的分配和回收算法
 * 作者：Sunner Sun
 * 最后修改時間：2005-3-25 16:53
 */

#include <stdio.h>

#define MEM_SIZE 64
#define TURE 1
#define FALSE 0
char memory[MEM_SIZE];

void* GetBlock(unsigned int size);
int FreeBlock(void* pBlock);
int IsFree(int unit);
void Init_Mem(void);


void Init_Mem()
{
    int i;
    for(i=0;i<MEM_SIZE;i++)
    {
        memory[i]='N';
    }
}
/* 在數組memory的分配size大小的內存塊，把首地址返回。
   如果分配失敗，返回NULL */

void* GetBlock(unsigned int size)
{
    int i,j;
    for(i=0;i<MEM_SIZE;i++)
    {
        if(memory[i]=='N')
        {
            for(j=i;j<size;j++)
        	{
                if(memory[j]!='N')
            	{
                    break;
            	}
        	}
            for(j=i;j<i+size;j++)
        	{
                memory[j]='A';
        		
        	}
            memory[j-1]='E';
            return &memory[i];
        }
        if(i>=MEM_SIZE-1&&size>1)
            return 0;

    }

    return memory;
}

/* 釋放首地址為pBlock的內存塊。
   成功返回非0值，失敗返回0 */
int FreeBlock(void* pBlock)
{
    char * pCell;
    for(pCell=(char *)pBlock;(*pCell)!='E';pCell++)
    {
        (*pCell)='N';
    }
    (*pCell)='N';
    return !0;
}

/* 判斷數組memory中下標為unit的單元是否被占用。
   空閑返回非0，否則返回0 */
int IsFree(int unit)
{
    if(memory[unit]=='N')
        return !0;
    if(memory[unit]=='A'||memory[unit]=='E')
        return 0;
}


/************************************************
 * 下面為測試代碼，不需要修改，也不許使用其定義 *
 * 的各種變量、宏、結構等                       *
 ************************************************/

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

/* 打印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');
}

/* 新申請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);
}

/* 刪除已經申請的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;
}