// CustomNew.p by François Pottier (pottier@clipper.ens.fr)
// December 1st, 1994

// --- WHAT IT IS - HOW TO USE IT ---------------------------------------------------------------------------------------

// This file redefines the standard new and delete operators.

// Advantages over MetroWerks's definition:
// 1. Memory is taken from the application heap or the temporary heap (preferrably the first) for greater flexibility.
// 2. Unused memory pools are released to the system.
// 3. Less fragmentation, because the MetroWerks delete operator doesn't always join adjacent free blocks.
// 4. If pool allocation fails, new doesn't revert to calling NewPtr for each block. It's a good thing, because otherwise the program
//	 would just slow down to a crawl (NewPtr is much slower than new) and die a horrible death, should the Toolbox run out of space.

// Finally, I keep a count of used blocks and free blocks, which can help assess the program's memory usage and fragmentation.

// How to use:
// - Add CustomNew.cp to your project.
// - Use CPlusPlusNoNew.Lib instead of CPlusPlus.Lib on 68k; use MWCRuntimeNoNew.Lib instead of MWCRuntime.Lib on PPC.
//	MWCRuntimeNoNew.Lib isn't provided by MetroWerks, you have to compile it yourself using MetroWerks' sources.

// --- LEGAL TERMS -----------------------------------------------------------------------------------------------------

// Although I wrote these routines entirely myself, they are loosely based on MetroWerks code.
// As far as I am concerned, you can use them freely in any of your programs. My only request is that you notify me if you find
// bugs or devise improvements. My email address is pottier@clipper.ens.fr

// Remember, this code has NOT been THOROUGHLY TESTED!

// --- OK FOLKS, LET'S HAVE THE CODE ------------------------------------------------------------------------------------

#include <stddef.h>
extern void (*new_handler)();


enum {
	kPoolSize = 65536L,										// Memory is allocated in 64K chunks
	kBigSize = 1024L										// Any allocations bigger than 1K go through the OS directly
};

typedef struct FreeMemList {									// Free blocks are linked together in a list
	struct FreeMemList	*next;								// Pointer to next free block
	long				size;									// Size of this block
} FreeMemList;

typedef struct MemPool {										// Memory is allocated from pools (locked handles)
	struct MemPool		*next;								// Pointer to next pool
	FreeMemList		*freeHead;							// Start of free blocks list
	long				usedBlocks, freeBlocks;					// Statistics
	Byte				data[];								// Blocks
} MemPool;

MemPool*				gPoolHead = NULL;						// List of pools

static Handle MakeLockedHandle (long size)						// Create a locked handle from the application heap
{														// or the temporary zone
	Handle			h;
	OSErr			e;

	h = NewHandle(size);
	if (h == NULL)
		h = TempNewHandle(size, &e);
	if (h)
		HLock(h);
	return h;
}

static Boolean NewPool (void)									// Add a new pool to the pool list
{
	Handle			h;
	MemPool*			pool;
	
	h = MakeLockedHandle(kPoolSize);
	if (h == NULL)
		return false;
	pool = (MemPool*) *h;
	
	pool->next = gPoolHead;
	pool->freeHead = (FreeMemList*) pool->data;
	pool->freeHead->next = NULL;
	pool->freeHead->size = (Ptr) pool + kPoolSize - (Ptr) pool->data;
	pool->usedBlocks = 0;
	pool->freeBlocks = 1;
	gPoolHead = pool;

	return true;
}

static void* AllocFromPool (MemPool* pool, long size)
{
	FreeMemList		*block;								// The block under consideration
	FreeMemList*		*link;								// The place which points to block in the free blocks list
	Ptr				result;
	
	for (link = &pool->freeHead; (block = *link); link = &block->next)	// Walk the free blocks list
		if (size <= block->size) {								// If a free block is big enough
			if (block->size >= size + sizeof(FreeMemList)) {		// If it's really big enough, we can split it
				block->size -= size;							// The low part remains a free block
				result = (Ptr) block + block->size;				// The high part becomes allocated
			}
			else {										// If it's just big enough, we can't split it
				*link = block->next;							// So we remove it from the free blocks list
				result = (Ptr) block;							// And we mark it all as allocated
				pool->freeBlocks--;
			}
			pool->usedBlocks++;
			* (long*) result = size;							// The first four bytes contain the new block's size
			return (result + 4);
		}
	
	return NULL;
}

// We assume the free blocks list to be always ordered from bottom to top, and it is because we insert new free blocks in the right
// place. This allows us to easily join adjacent free blocks into a single one when deleting a block, thus reducing stupid fragmentation.

static void DeleteFromPool (MemPool* pool, Ptr pointer, long size)
{
	FreeMemList		*block, *previous, *next;
	FreeMemList*		*link;
	
	previous = next = NULL;									// Look for any adjacent free blocks
	for (link = &pool->freeHead; (block = *link); link = &block->next)	// Walk the free blocks list
		if (pointer == (Ptr) block + block->size)					// We have found a free block just before ours
			previous = block;
		else if (pointer + size == (Ptr) block) {					// We have found a free block just after ours
			next = block;
			goto Coalesce;									// Stop searching now, there's nothing more up there and we will need the value of link
		}
		else if (pointer + size < (Ptr) block)						// We have found no adjacent block
			goto Coalesce;									// The current value of link tells us where to insert the new free block
	
Coalesce:
	pool->usedBlocks--;
	if (previous != NULL && next != NULL) {						// We now have 3 free blocks, join them
		previous->size += size + next->size;
		previous->next = next->next;
		pool->freeBlocks--;
	}
	else if (previous)										// Expand the free block below
		previous->size += size;
	else if (next) {											// Expand the free block above
		((FreeMemList*) pointer)->next = next->next;
		((FreeMemList*) pointer)->size = next->size + size;
		*link = (FreeMemList*) pointer;
	}
	else {												// Add a free block to the list
		((FreeMemList*) pointer)->next = *link;
		((FreeMemList*) pointer)->size = size;
		*link = (FreeMemList*) pointer;
		pool->freeBlocks++;
	}	
}

void *operator new (size_t size)
{
	MemPool*			pool;
	void*			result;

	size = (size & 0xFFFFFFFC) + 8;							// Make sure size is a multiple of 4, and add 4 bytes to store the block size

	while(1) {
	  	if (size >= kBigSize) {									// If the requested size is big
			Handle h = MakeLockedHandle(size);						// Use the Memory Manager directly
			if (h == NULL)
				if (new_handler) new_handler(); else return(NULL);
			* (long*) *h = -1L;									// This special value serves to recognize standalone blocks
			return (*h + 4);
		}
		
		pool = gPoolHead;										// Try to find a pool with enough room
		while (pool) {
			if (result = AllocFromPool(pool, size))
				return result;
			pool = pool->next;
		}
		
		if (NewPool())											// If no pool has enough space, create a new pool
			return AllocFromPool(gPoolHead, size);
		if (new_handler) new_handler(); else return(NULL);			       // If we can't create a new pool, fail - *don't* revert to NewPtr, it's too damn slow and would hopelessly fill up the heap
	}
}

void operator delete (void *pointer)
{
	long				size;
	MemPool*			pool;
	MemPool*			*link;

	if (pointer) {
		pointer = (Ptr) pointer - 4;							// Retrieve the block size, which is stored 4 bytes below
		size = * (long*) pointer;

		if (size == -1L)										// If the size tag is -1, the block is a handle
			DisposeHandle(RecoverHandle((Ptr) pointer));
		else {
			link = &gPoolHead;								// Find which pools the block belongs to
			while ((pool = *link) && ((Ptr) pointer < (Ptr) pool || (Ptr) pointer > (Ptr) pool + kPoolSize))
				link = &pool->next;

			DeleteFromPool(pool, (Ptr) pointer, size);				// Delete the block from this pool
			
			if (pool->usedBlocks == 0) {						// If this pool isn't used any more
				*link = pool->next;							// Remove it from the pool queue
				DisposeHandle(RecoverHandle((Ptr) pool));		// And release it
			}
		}
	}
}

long BytesTakenFromTempZone (void)							// For informational purposes, returns the number of
{														// bytes taken from the Multifinder zone. Note that this
	MemPool*			pool;									// figure takes only pools into accounts, not stand-alone
	Handle			h;									// blocks.
	long				size;
	
	size = 0;
	for (pool = gPoolHead; pool; pool = pool->next) {
		h = RecoverHandle((Ptr) pool);
		if (HandleZone(h) != ApplicZone())
			size += GetHandleSize(h);
	}
	return size;
}

// THAT'S ALL FOLKS. HOPE YOU ENJOYED THE SHOW -----------------------------------------------------------------------