#include <stdlib.h>
#include <string.h>
#include "xlmalloc.h"



static unsigned long Memfail=0L;	/* Count of allocation failures */
static unsigned long Allocs=0L;		/* Total allocations */
static unsigned long Frees=0L;		/* Total frees */
static unsigned long Invalid=0L;	/* Total calls to SysLfree with garbage arg */

/* The array is to record the number that 
 * the special sized memory block is used.
 * Sizes[0]  -----   memory block size: 2/0
 *           .....
 * Sizes[n]  -----   memory block size: 2/n 
* max block size is 2/19 = 128K */
static unsigned long Sizes[20]={ 0L, 0L, 0L, 0L, 0L,
				 0L, 0L, 0L, 0L, 0L,
				 0L, 0L, 0L, 0L, 0L,
				 0L, 0L, 0L, 0L, 0L };;

/* This debugging pattern MUST be exactly equal in size 
 * to the "header" union defined later */
static char Debugpat[] = { 0xfe,0xed, 0xfa, 0xce, 0xde, 0xad, 0xbe, 0xef };

static HEADER *Base=NULL;			//堆的基地址指針
static HEADER *First=NULL;			//第一個有效的分配塊
static HEADER *Allocp = NULL;		//FreeList的首指針


struct sheader heap[Heapsize/sizeof(struct sheader)];
//char	array_memory[Heapsize];

/* Heap memory, ABLKSIZE units */
static unsigned long Availmem = BTOU(Heapsize)-2;		

#ifdef HOT_RESET_DEBUG_CODE_ENABLE	//如果系統支持熱復位，需要我們手工將所有的全局變量重新置初值
void SysLmallocInit(void)
{
	int i;
	
#if ENABLE_SYSMEM_DEBUG_OUT
	MemUsed = 0L;
	MemUsedPeak = 0L;
#endif
	
	Memfail = 0L;
	Allocs = 0L;
	Frees = 0L;
	Invalid = 0L;

	for(i=0; i<20; i++)
		Sizes[i] = 0L;
	
	Base = NULL;	
	First = NULL;	
	Allocp = NULL;

	Availmem = BTOU(Heapsize)-2;
}
#endif

static char ilog2(int size)
{
	
	char	i;
	int     mask = 0x80000000;
	
	for( i = 0; i < 16; i++ )
	{
		if( size & mask )
			break;
		else
			mask = mask >> 1;
	}
	
	return ( 16 - i );
}


/* Allocate block of 'nb' bytes */
void *SysLmalloc( int nb )
{
#if Memdebug
	int i;
#endif
	
	register HEADER  *p,  *q;
	register unsigned long nu;

	if(nb == 0)
		return NULL;

	Allocs++;

#if Memdebug
	/* Record the size of this request */
	if((i = ilog2(nb)) >= 0)
		Sizes[i]++;
#endif

	
	/* Round up to full block, then add one for header */
	nu = BTOU(nb);
	
	//注意：我們在這里進入臨界區，我們將調用OS提供的API關閉任務調度
	//vDisableDispatch();
	 
	/* Initialize heap pointers if necessary */
	if((q = Allocp) == NULL){
		
		//創建一個空頭。目的：當所有空間分配完時，Lfree函數需要有一個表頭
		Base = (HEADER *)heap;			//array_memory;
		Base->s.ptr = Allocp = q = Base;
		Base->s.size = 1;
		
		
		First = Base + 1;
		Base->s.ptr = First;
		First->s.ptr = Base;
		First->s.size = BTOU(Heapsize)-2;	//注意BTOU要加一，所以這里要減二（BASE用了一塊）
		
		
	}
	/* Search heap list */
	for(p = q->s.ptr; ; q = p, p = p->s.ptr){
		if(p->s.size >= nu){
			/* This chunk is at least as large as we need */
			if(p->s.size <= nu + 1){
				/* This is either a perfect fit (size == nu)
				 * or the SysLfree chunk is just one unit larger.
				 * In either case, alloc the whole thing,
				 * because there's no point in keeping a SysLfree
				 * block only large enough to hold the header.
				 */
				q->s.ptr = p->s.ptr;
			} else {
				/* Carve out piece from end of entry */
				p->s.size -= nu;
				p += p->s.size;
				p->s.size = nu;
			}

			p->s.ptr = p;	/* for auditing */
			Availmem -= p->s.size;
			p++;
			
#if Memdebug
			// debug for memory test
			memset( p, 0xcc, nb );
#endif
			break;
		}

		/* We've searched all the way around the list without
		 * finding anything. 我們將返回空指針，內存分配失敗！
		 */
		
		if(p == Allocp){
			p = NULL;
			Memfail++;
			break;
		}
	}

	//注意：出臨界區，重新打開內核的調度
	//vEnableDispatch();
	
	return (void *)p;
}


/* Put memory block back on heap */
void SysLfree( void *blk )
{
	register HEADER  *p,  *q;
	unsigned int i;

	if(blk == NULL)
		return;		/* Required by ANSI */
	Frees++;
	
	p = ((HEADER  *)blk) - 1;	//p 指向該內存塊的頭部
	/* Audit check，檢查該塊內存是否是合法分配的 */
	if(p->s.ptr != p){
		Invalid++;
		return;
	}
	Availmem += p->s.size;

#if Memdebug
	/* Fill data area with pattern to detect later overwrites */
	for(i=1;i<p->s.size;i++)
		memcpy(p[i].c,Debugpat,sizeof(Debugpat));
#endif

	//注意：我們在這里進入臨界區，我們將調用OS提供的API關閉任務調度
	//vDisableDispatch();

	
 	/* Search the SysLfree list looking for the right place to insert */
	//從Allocp FreeList的頭部開始搜索
	for(q = Allocp; !(p > q && p < q->s.ptr); q = q->s.ptr){
		/* Highest address on circular list? */
		if(q >= q->s.ptr && (p > q || p < q->s.ptr))
			break;
	}
	if(p + p->s.size == q->s.ptr){
		/* Combine with front of this entry */
		//與下一個Free塊的頭部合并
		p->s.size += q->s.ptr->s.size;
		p->s.ptr = q->s.ptr->s.ptr;
		#if Memdebug 
			memcpy(q->s.ptr->c,Debugpat,sizeof(Debugpat));
		#endif
	} else {
		/* Link to front of this entry */
		//將P塊加入到FreeList（p塊的next指針指向下一塊）
		p->s.ptr = q->s.ptr;
	}
	
	//看看P塊是否可能與前一個Free塊（q塊）的尾部合并？當然如果q塊是BASE的話，我們就不合并
	if((q + q->s.size == p) && (q != Base)){
		/* Combine with end of this entry */
		q->s.size += p->s.size;
		q->s.ptr = p->s.ptr;
		#if Memdebug
			memcpy(p->c,Debugpat,sizeof(Debugpat));
		#endif
	} else {
		/* Link to end of this entry */
		//將P塊加入到FreeList（q塊的next指針指向p）
		q->s.ptr = p;
	}

	//注意：出臨界區，重新打開內核的調度
	//vEnableDispatch();
	
	return;
}

/* Move existing block to new area */
void *SysLrealloc( void *area, int size )
{
	unsigned osize;
	HEADER  *hp;
	void *pnew;
	
	if(size == 0)
		return NULL;
		
	hp = ((HEADER *)area) - 1;
	if(hp->s.ptr != hp)
		return NULL;
	
	osize = (hp->s.size -1) * ABLKSIZE;

	/* We must copy the block since freeing it may cause the heap
	 * debugging code to scribble over it.
	 */
	if((pnew = SysLmalloc(size)) != NULL)
		memcpy(pnew,area,size>osize? osize : size);
	SysLfree(area);
	return pnew;
}

/* Allocate block of cleared memory */
void *SysLcalloc( int size )
{
	register char *cp;
	
	if(size == 0)
		return NULL;
		
	if((cp = SysLmalloc(size)) != NULL)
		memset(cp,0,size);
	return cp;
}


/* Version of SysLmalloc() that waits if necessary for memory to become available */
/*
void *
SysLmallocw(nb)
WORD nb;
{
	register void *p;

	if(nb == 0)
		return NULL;
		
	while((p = SysLmalloc(nb)) == NULL){
		Memwait++;
		twai_sem(Memsem, TMO_FEVR);
    	Memwait--;
	}
	return p;
}
*/

/* Version of calloc that waits if necessary for memory to become available */
/*
void *
Lcallocw(size)
unsigned size;	// Size of each element 
{
	register char *cp;
	
	if(size == 0)
		return NULL;
		
	cp = SysLmallocw(size);
	memset(cp,0,size);
	return cp;
}
*/
/* Print heap stats : only for debug */
/*
int
dostat(void)
{
	int i;

	printf("heap size %lu avail %lu (%lu%%) \n",
	 Heapsize,Availmem * ABLKSIZE,100L*Availmem*ABLKSIZE/Heapsize);
	
	printf("allocs %lu frees %lu (diff %lu) alloc fails %lu invalid frees %lu\n",
		Allocs,Frees,Allocs-Frees,Memfail,Invalid);
	printf("\n");
	return 0;
}
*/

/* Print heap Lfree list */
/*
int
dofreelist(void)
{
	HEADER  *p;
	int i = 0;
	int j;
	unsigned corrupt;
	int i_state;

	for(p = Base->s.ptr;p != (HEADER  *)Base;p = p->s.ptr){
		corrupt = 0;
		if(Memdebug){
			//i_state = dirps();
			for(j=1;j<p->s.size;j++){
				if(memcmp(p[j].c,Debugpat,sizeof(Debugpat)) != 0){
					corrupt = j;
					break;
				}
			}
			//restore(i_state);
		}
		if(corrupt)
			printf("%p %6lu C: %u",p,(p->s.size - 1) * ABLKSIZE,corrupt);
		else
			printf("%p %6lu",p,(p->s.size - 1) * ABLKSIZE);

		if(++i == 4){
			i = 0;
			if(printf("\n") == EOF)
				return 0;
		} else
			printf(" | ");
	}
	if(i != 0)
		printf("\n");
	return 0;
}


int
dosizes(void)

{
	int i;

	for(i=0;i<16;i += 4){
		printf("N>=%5u:%7ld| N>=%5u:%7ld| N>=%5u:%7ld| N>=%5u:%7ld\n",
		 1<<i,Sizes[i],	2<<i,Sizes[i+1],
		 4<<i,Sizes[i+2],8<<i,Sizes[i+3]);
	}
	return 0;
}

*/