// BedrockHeap.h 
// Copyright © 1985-1992 by Apple Computer, Inc.  All rights fReserved.

#ifndef BRVMCHUN_H
#define BRVMCHUN_H

#ifndef BRVMBEST_H
#include "BRVMBest.h"
#endif


//----------------------------------------------------------------------------------------
// Forward class declarations
//----------------------------------------------------------------------------------------

class BR_CChunk;
class BR_CChunkyBlock;
class BR_CHeap;
class BR_CChunkyBlockStack;
 

//========================================================================================
// STRUCT BR_SChunkyBlockHeader
//========================================================================================

struct BR_SChunkyBlockHeader
{
	unsigned int fSizeIndex:4;
	unsigned int fBlockIndex:4;
	int fBlockType:4;
	unsigned int fMagicNumber:4;
};


//========================================================================================
// CLASS BR_CChunk
//========================================================================================

struct BR_SChunkHeader
{
	unsigned short fBlockBusyBits;
};


class BR_CChunk
{
public:
	BR_CChunk(short blocksPerChunk,
			  unsigned int sizeIndex,
			  BR_MemoryBlockSize blockSize);

	~BR_CChunk();

	inline void* operator new(size_t,
					   void* ptr);
	inline void* operator new(size_t);
	inline void operator delete(void*);

	BR_CChunkyBlock* GetBlock(unsigned int blkIndex,
							  BR_MemoryBlockSize blkSize);
	unsigned int GetSizeIndex();

	BR_Boolean IsBlockBusy(unsigned int whichBlock);
	BR_Boolean IsBusy();

	void SetBlockBusy(unsigned int whichBlock,
					  BR_Boolean busy);

private:
	BR_SChunkHeader fHeader;
};

//----------------------------------------------------------------------------------------
// INLINES BR_CChunk
//----------------------------------------------------------------------------------------

inline BR_CChunk::~BR_CChunk()
{
}

inline void* BR_CChunk::operator new(size_t,
				   void* ptr)
{
	return ptr;
}


inline void* BR_CChunk::operator new(size_t)
{
	return NULL;
}


inline void BR_CChunk::operator delete(void*)
{
}

inline BR_CChunkyBlock* BR_CChunk::GetBlock(unsigned int blkIndex,
											BR_MemoryBlockSize blkSize)
{
	BR_CChunkyBlock * blk = (BR_CChunkyBlock *)((BR_PointerDifference)this + sizeof(BR_SChunkHeader) + blkIndex * blkSize);
	return blk;
}


inline unsigned int BR_CChunk::GetSizeIndex()
{
	BR_SChunkyBlockHeader * header = (BR_SChunkyBlockHeader *)((BR_PointerDifference)this + sizeof(BR_SChunkHeader));
	return header->fSizeIndex;
}


inline BR_Boolean BR_CChunk::IsBusy()
{
	return fHeader.fBlockBusyBits != 0;
}


inline void BR_CChunk::SetBlockBusy(unsigned int whichBlock,
									BR_Boolean busy)
{
	unsigned short mask = 0x0001;

	for (short i = 0; i < whichBlock; i++)
		mask = mask << 1;

	if (busy)
		fHeader.fBlockBusyBits |= mask;
	else
		fHeader.fBlockBusyBits &= ~mask;
}


//========================================================================================
// CLASS BR_CChunkyBlock
//========================================================================================

class BR_CChunkyBlock
{
public:
	enum
	{
		kBusyOverhead = 2, 
		kChunkyBlockType = BR_CBestFitBlock::kBestFitBlockType + 1, 
		kMagicNumber = 0xA
	};


	void* operator new(size_t,
					   void* ptr);
	void* operator new(size_t);
	inline void operator delete(void*);

	BR_CChunkyBlock();
	BR_CChunkyBlock(unsigned int sizeIndex,
					unsigned int blockIndex);
	~BR_CChunkyBlock();

	BR_CChunk* GetChunk(BR_MemoryBlockSize blkSize);
	BR_CChunkyBlock* GetNext();
	unsigned int GetSizeIndex();

	BR_Boolean IsBusy(BR_MemoryBlockSize blockSize);

	void SetBusy(BR_MemoryBlockSize blockSize,
				 BR_Boolean busy);
	void SetNext(BR_CChunkyBlock* blk);

private:
	// Fields present in both free and busy blocks.

	BR_SChunkyBlockHeader fBusyHeader;

	// Fields present in only free blocks.

	BR_CChunkyBlock* fNext;
};

//----------------------------------------------------------------------------------------
// INLINES BR_CChunkyBlock
//----------------------------------------------------------------------------------------

inline void* BR_CChunkyBlock::operator new(size_t,
				   void* ptr)
{
	return ptr;
}


inline void* BR_CChunkyBlock::operator new(size_t)
{
	return NULL;
}


inline void BR_CChunkyBlock::operator delete(void*)
{
}

inline BR_CChunkyBlock::BR_CChunkyBlock()
{
	fBusyHeader.fBlockType = kChunkyBlockType;
	fBusyHeader.fMagicNumber = kMagicNumber;
	fNext = NULL;
}


inline BR_CChunkyBlock::~BR_CChunkyBlock()
{
}


inline BR_CChunkyBlock::BR_CChunkyBlock(unsigned int sizeIndex,
										unsigned int blockIndex)
{
	fBusyHeader.fSizeIndex = sizeIndex;
	fBusyHeader.fBlockIndex = blockIndex;
	fBusyHeader.fBlockType = kChunkyBlockType;
	fBusyHeader.fMagicNumber = kMagicNumber;
	fNext = NULL;
}


inline BR_CChunk* BR_CChunkyBlock::GetChunk(BR_MemoryBlockSize blkSize)
{
	BR_CChunk * chk = (BR_CChunk *)((BR_PointerDifference)this - sizeof(BR_SChunkHeader) - blkSize * fBusyHeader.fBlockIndex);
	return chk;
}


inline BR_CChunkyBlock* BR_CChunkyBlock::GetNext()
{
	return fNext;
}


inline unsigned int BR_CChunkyBlock::GetSizeIndex()
{
	return fBusyHeader.fSizeIndex;
}


inline BR_Boolean BR_CChunkyBlock::IsBusy(BR_MemoryBlockSize blockSize)
{
	return this->GetChunk(blockSize)->IsBlockBusy(fBusyHeader.fBlockIndex);
}


inline void BR_CChunkyBlock::SetBusy(BR_MemoryBlockSize blockSize,
									 BR_Boolean busy)
{
	this->GetChunk(blockSize)->SetBlockBusy(fBusyHeader.fBlockIndex, busy);
}


inline void BR_CChunkyBlock::SetNext(BR_CChunkyBlock* blk)
{
	fNext = blk;
}


//========================================================================================
// CLASS BR_CChunkyBlockStack
//========================================================================================

class BR_CChunkyBlockStack
{
public:
	BR_CChunkyBlockStack();
	~BR_CChunkyBlockStack();

	BR_CChunkyBlock* Pop();
	void Push(BR_CChunkyBlock* blk);
	void RemoveRange(BR_PointerDifference begAddr,
					 BR_PointerDifference endAddr);
	BR_CChunkyBlock* Top();

private:
	BR_CChunkyBlock fHead;
};


//========================================================================================
// CLASS BR_CHeap
//========================================================================================

class BR_CHeap : public BR_CBestFitHeap
{
private:
	static const BR_MemoryBlockSize kDefaultBlockSizes[];

public:
	enum
	{
		kMaxNumberOfBlockSizes = 16, kDefaultBlocksPerChunk = 4
	};


	BR_CHeap(BR_MemoryBlockSize initialSize,
			 BR_MemoryBlockSize incrementSize = 0,
			 short blocksPerChunk = kDefaultBlocksPerChunk,
			 const BR_MemoryBlockSize* blockSizes = kDefaultBlockSizes);

	virtual void* DoAllocate(BR_MemoryBlockSize size,
							 BR_MemoryBlockSize& allocatedSize);
	virtual BR_MemoryBlockSize DoBlockSize(const void* block) const;
	virtual void DoFree(void*);
	virtual BR_Boolean DoIsValidBlock(void* blk) const;
	virtual void DoReset();

	virtual~ BR_CHeap();

protected:
	void* AllocateBlock(unsigned int sizeIndex);
	void CreateNewChunk(unsigned int sizeIndex);
	void FreeBlock(BR_CChunkyBlock* blk);
	unsigned int SizeIndex(BR_MemoryBlockSize size);

private:
	short fNumberOfBlockSizes;
	const BR_MemoryBlockSize* fBlockSizes;
	BR_CChunkyBlockStack fFreeLists[kMaxNumberOfBlockSizes];
	short fBlocksPerChunk;
};



#endif
