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

#ifndef BRVMBEST_H
#define BRVMBEST_H

#ifndef BRSUPDEF_H
#include "BRSupDef.h"
#endif

#ifndef BRVMHEAP_H
#include "BRVMHeap.h"
#endif


//========================================================================================
// CLASS BR_CBestFitBlock
//========================================================================================

class BR_CBestFitBlock
{
public:
	enum
	{
		kBusyOverhead = 4, 
		kMinBlockSize = 20, 
		kBestFitBlockType = 1, 
		kMaxBlockSize = 0x00FFFFFF, 
		kMagicNumber = 0x3
	};


	BR_Boolean operator>(const BR_CBestFitBlock& blk);
	BR_Boolean operator<(const BR_CBestFitBlock& blk);
	BR_Boolean operator>=(const BR_CBestFitBlock& blk);
	BR_Boolean operator<=(const BR_CBestFitBlock& blk);
	BR_Boolean operator==(const BR_CBestFitBlock& blk);
	BR_Boolean operator!=(const BR_CBestFitBlock& blk);

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

	BR_CBestFitBlock();
	BR_CBestFitBlock(int busy,
					 int prevBusy,
					 long size);

	~BR_CBestFitBlock();

	BR_Boolean GetBusy();
	BR_CBestFitBlock* GetLeft();
	unsigned int GetMagicNumber();
	BR_CBestFitBlock* GetNext();
	BR_CBestFitBlock* GetParent();
	BR_Boolean GetPreviousBusy();
	BR_CBestFitBlock* GetRight();
	BR_MemoryBlockSize GetSize();

	void SetBusy(BR_Boolean busy);
	void SetLeft(BR_CBestFitBlock* left);
	void SetNext(BR_CBestFitBlock* fNext);
	void SetParent(BR_CBestFitBlock* parent);
	void SetPrevBusy(BR_Boolean busy);
	void SetRight(BR_CBestFitBlock* right);
	void SetSize(BR_MemoryBlockSize size);

	void StuffAddressAtEnd();

protected:

private:

	// The following four fields are present in both free blocks and busy blocks.
	// Block sizes are limited to sizes that can be represented in 24 bits (16 Meg).
	// The fBlockType field distiguishes chunky blocks from best fit blocks and
	// must be the first bit of the last byte in the header of both best fit and
	// chunky blocks.

	BR_MemoryBlockSize fSize:24;
	int fBlockType:4;
	BR_Boolean fBusy:1;
	BR_Boolean fPreviousBusy:1;

	unsigned int fMagicNumber:2;

	// The following fields are only present in free blocks. They are used to link
	// the free block into the free block tree. The address of a free block is also
	// stored at the fEnd of the block and must be accounted for in the minimum block
	// size.

	BR_CBestFitBlock* fParent;
	BR_CBestFitBlock* fLeft;
	BR_CBestFitBlock* fRight;
};

//----------------------------------------------------------------------------------------
// INLINES BR_CBestFitBlock
//----------------------------------------------------------------------------------------

//inline void BR_CBestFitBlock::operator delete(void*)
//{
//}


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


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


inline BR_Boolean BR_CBestFitBlock::operator>=(const BR_CBestFitBlock& blk)
{
	return *this > blk || *this == blk;
}


inline BR_Boolean BR_CBestFitBlock::operator<=(const BR_CBestFitBlock& blk)
{
	return *this < blk || *this == blk;
}


inline BR_Boolean BR_CBestFitBlock::operator!=(const BR_CBestFitBlock& blk)
{
	return !(*this == blk);
}


inline BR_CBestFitBlock::BR_CBestFitBlock(int busy,
										  int previousBusy,
										  long size)
{
	fParent = NULL;
	fRight = fLeft = NULL;
	fBlockType = kBestFitBlockType;
	fBusy = busy;
	fPreviousBusy = previousBusy;
	fSize = size;
	fMagicNumber = kMagicNumber;

	if (!busy)
		this->StuffAddressAtEnd();
}


inline BR_CBestFitBlock::BR_CBestFitBlock()
{
	fParent = NULL;
	fRight = fLeft = NULL;
	fBlockType = kBestFitBlockType;
	fBusy = FALSE;
	fPreviousBusy = FALSE;
	fSize = 0;
	fMagicNumber = kMagicNumber;

	this->StuffAddressAtEnd();
}


inline BR_CBestFitBlock::~BR_CBestFitBlock()
{
}


inline BR_Boolean BR_CBestFitBlock::GetBusy()
{
	return fBusy;
}


inline BR_CBestFitBlock* BR_CBestFitBlock::GetLeft()
{
	return fLeft;
}


inline unsigned int BR_CBestFitBlock::GetMagicNumber()
{
	return fMagicNumber;
}


inline BR_CBestFitBlock* BR_CBestFitBlock::GetNext()
{
	return fParent;
}


inline BR_CBestFitBlock* BR_CBestFitBlock::GetParent()
{
	return fParent;
}


inline BR_Boolean BR_CBestFitBlock::GetPreviousBusy()
{
	return fPreviousBusy;
}


inline BR_CBestFitBlock* BR_CBestFitBlock::GetRight()
{
	return fRight;
}


inline BR_MemoryBlockSize BR_CBestFitBlock::GetSize()
{
	return fSize;
}


inline void BR_CBestFitBlock::SetBusy(BR_Boolean busy)
{
	fBusy = busy;
}


inline void BR_CBestFitBlock::SetLeft(BR_CBestFitBlock* left)
{
	fLeft = left;
}


inline void BR_CBestFitBlock::SetNext(BR_CBestFitBlock* fNext)
{
	fParent = fNext;
}


inline void BR_CBestFitBlock::SetParent(BR_CBestFitBlock* parent)
{
	fParent = parent;
}


inline void BR_CBestFitBlock::SetPrevBusy(BR_Boolean busy)
{
	fPreviousBusy = busy;
}


inline void BR_CBestFitBlock::SetRight(BR_CBestFitBlock* right)
{
	fRight = right;
}


inline void BR_CBestFitBlock::SetSize(BR_MemoryBlockSize size)
{
	fSize = size;
}


//========================================================================================
// CLASS BestFitHeap
//
//		The BestFitHeap allocates fMemory from the system in segments. The segments are
//		linked together in a list so that When the heap is destroyed all segments can be
//		freed.
//
//========================================================================================

class BR_CBestFitSegment
{
public:

	friend BR_CBestFitHeap;

	enum
	{
		kSegmentPrefixSize = 12, kSegmentSuffixSize = 4, kSegmentOverhead = kSegmentPrefixSize + kSegmentSuffixSize
	};


	inline BR_Boolean AddressInSegment(void* ptr);

protected:

private:
	void* fSegmentSpace;
	BR_MemoryBlockSize fSegmentSize;
	BR_CBestFitSegment* fNextSegment;
};

//----------------------------------------------------------------------------------------
// INLINES BR_CBestFitSegment
//----------------------------------------------------------------------------------------

inline BR_Boolean BR_CBestFitSegment::AddressInSegment(void* ptr)
{
#ifdef BR_BUILD_MAC
	return ptr >= fSegmentSpace && ptr <= (void*)((BR_PointerDifference)fSegmentSpace + fSegmentSize);
#endif
#ifdef BR_BUILD_WIN
	return ptr >= fSegmentSpace && ptr <= (void*)((long)fSegmentSpace + fSegmentSize);
#endif

}


//========================================================================================
// CLASS BR_CFreeBlockTreeStats
//
//		Keep statistics on the min, max, and average size and depth of the
//		free block list.
//
//========================================================================================

class BR_CFreeBlockTreeStats
{
};

//========================================================================================
// CLASS BR_CFreeBlockTree
//
//		Binary tree for storing free blocks. Dependent on the structure and
//		implementation of BR_CBestFitBlock.
//
//========================================================================================

class BR_CFreeBlockTree
{
public:
	BR_CFreeBlockTree();

	void AddBlock(BR_CBestFitBlock* blk);
	void TreeInfo(BR_MemoryBlockSize& bytesFree,
				  BR_MemoryBlockSize& numberOfNodes) const;
	void CheckTree() const;
	void PrintTree() const;
	void RemoveBlock(BR_CBestFitBlock* blk);
	BR_CBestFitBlock* SearchForBlock(BR_MemoryBlockSize size,
									 void* blk,
									 BR_CBestFitBlock** insertLeaf = NULL);
	void TreeInfo(BR_MemoryBlockSize& bytesFree,
				  BR_MemoryBlockSize& numberOfNodes);

	~BR_CFreeBlockTree();

protected:
	void CheckTreeHelper(BR_CBestFitBlock* blk) const;
	BR_CBestFitBlock* GetSuccessorBlk(BR_CBestFitBlock* blk);
	void PrintTreeHelper(BR_CBestFitBlock* blk,
						 int level = 0) const;
	void TreeInfoHelper(BR_CBestFitBlock* blk,
						BR_MemoryBlockSize& bytesFree,
						BR_MemoryBlockSize& numberOfNodes) const;

private:
	BR_CBestFitBlock fRoot;

#ifdef BR_DEBUG
	BR_CFreeBlockTreeStats fStats;
#endif

};

//----------------------------------------------------------------------------------------
// INLINES BR_CFreeBlockTree
//----------------------------------------------------------------------------------------

inline BR_CFreeBlockTree::~BR_CFreeBlockTree()
{
}


//========================================================================================
// CLASS BR_CBestFitHeap
//
//		Memory allocation heap using the best fit allocation strategy.
//
//========================================================================================

class BR_CBestFitHeap : public BR_CMemoryHeap
{
public:

	virtual BR_MemoryBlockSize BytesFree() const;
	virtual void Check() const;
	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_MemoryBlockSize HeapSize() const;
	virtual BR_Boolean IsMyBlock(void* blk) const;
	virtual void Print(char* msg = "") const;

	BR_CBestFitHeap(BR_MemoryBlockSize sizeInitial,
					BR_MemoryBlockSize sizeIncrement = 0);
	virtual~ BR_CBestFitHeap();

protected:

	void AddToFreeBlocks(BR_CBestFitBlock* blk);
	BR_CBestFitBlock* Coalesce(BR_CBestFitBlock* blk);
	void CreateNewSegment(BR_MemoryBlockSize size);
	void DeleteSegments();
	void RemoveFromFreeBlocks(BR_CBestFitBlock* blk);
	BR_CBestFitBlock* SearchFreeBlocks(BR_MemoryBlockSize size);

private:

	BR_CBestFitSegment* fSegments;
	BR_MemoryBlockSize fSizeIncrement;
	BR_MemoryBlockSize fSizeInitial;
	BR_CFreeBlockTree fFreeTree;
};



#endif
