/*	XGCollection.cpp
 *
 *		This is used to store a collection of objects in a compact manner.
 */

/**********************************************************************

  YAAF is Copyright 1997-1999 by William Woody.

  Redistribution and use in source and binary forms, with or without 
  modification, are permitted provided that the following conditions 
  are met:

  Redistributions of source code must retain the above copyright notice, 
  this list of conditions and the following disclaimer.

  Neither the name of the copyright holder or other contributors may
  be used to promote products derived from this software without
  specific written prior permission.

  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES 
  OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 
  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS 
  BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN 
  ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 
  CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 
  SOFTWARE.
  
  Contact:   woody@alumni.caltech.edu
  Web page:  http://www.pandawave.com/yaaf/

**********************************************************************/

#include <XCollection.h>
#include <XError.h>
#include <string.h>


void XGCollection::Validate()
{
	fData.Validate();
	fTOC.Validate();
	Assert( fWastedSpace >= 0 && fWastedSpace <= fAllocMark );
	Assert( fAllocMark <= fData.GetSize() );
	int maxtoc = fTOC.GetSize() / sizeof(XGCollected);
	XGCollected *toc = (XGCollected *)(*fTOC);
	int index;
	int next, prev;
	for (index = fUsedChain; index != -1; index = toc[index].used.next) {
		Assert( index >= 0 && index <= maxtoc );
		Assert( toc[index].used.offset >= 0 && toc[index].used.offset <= fAllocMark - toc[index].used.size );
		Assert( toc[index].used.size >= 0 && toc[index].used.size <= fAllocMark );
		next = toc[index].used.next;
		prev = toc[index].used.prev;
		if (next != -1) {
			Assert( next >= 0 && next < maxtoc );
			Assert( toc[next].used.prev == index );
		}
		if (prev == -1) {
			Assert( fUsedChain == index );
		} else {
			Assert( prev >= 0 && prev < maxtoc );
			Assert( toc[prev].used.next == index );
		}
	}
	for (index = fAvailChain; index != -1; index = toc[index].avail.next) {
		Assert( index >= 0 && index <= maxtoc );
		next = toc[index].avail.next;
		prev = toc[index].avail.prev;
		if (next != -1) {
			Assert( next >= 0 && next < maxtoc );
			Assert( toc[next].avail.prev == index );
		}
		if (prev == -1) {
			Assert( fAvailChain == index );
		} else {
			Assert( prev >= 0 && prev < maxtoc );
			Assert( toc[prev].avail.next == index );
		}
	}
}

#define Validate() ((void)0)


/************************************************************************/
/*																		*/
/*	Constructor/Destructor												*/
/*																		*/
/************************************************************************/

/*$	XGCollection::XGCollection
 *
 *		Construct an empty collection object
 */

XGCollection::XGCollection()
{
	fAvailChain = -1;
	fUsedChain = -1;
	fWastedSpace = 0;
	fAllocMark = 0;
}

/*$	XGCollection::~XGCollection
 *
 *		Free a collection object and all of it's contained objects
 */

XGCollection::~XGCollection()
{
}

/************************************************************************/
/*																		*/
/*	Allocation/Deallocation												*/
/*																		*/
/************************************************************************/

/*$	XGCollection::New
 *
 *		Allocate an object in a collection of the specified size in
 *	bytes and return a collection handle which refers to that object.
 */

uint32 XGCollection::New(uint32 size)
{
	XGCollected *toc;
	
	Validate();
	
	if (fAvailChain == -1) {
		int oldtoc = fTOC.GetSize() / sizeof(XGCollected);
		int newtoc = 100 + oldtoc * 2;
		fTOC.SetSize(newtoc * sizeof(XGCollected));
		toc = (XGCollected *)*fTOC;
		for (int i = oldtoc; i < newtoc; ++i) {
			toc[i].avail.next = i+1;
			toc[i].avail.prev = i-1;
		}
		toc[oldtoc].avail.prev = -1;
		toc[newtoc-1].avail.next = -1;
		fAvailChain = oldtoc;
		
		Validate();
		
	}
	
	int index = fAvailChain;
	long offset = GetDataSpace( size );
	
	Validate();
	
	toc = (XGCollected *)*fTOC;
	fAvailChain = toc[fAvailChain].avail.next;
	Validate();
	if (fAvailChain >= 0) {
		toc[fAvailChain].avail.prev = -1;
	}
	Validate();
	toc[index].used.offset = offset;
	Validate();
	toc[index].used.size = size;
	Validate();
	toc[index].used.next = fUsedChain;
	Validate();
	toc[index].used.prev = -1;
	Validate();
	if (fUsedChain >= 0) {
		toc[fUsedChain].used.prev = index;
	}
	Validate();
	fUsedChain = index;
	
	Validate();
	
	return index + 1;
}

/*$	XGCollection::Free
 *
 *		Free the specified collection handle.
 */

void XGCollection::Free(uint32 index)
{
	
	Validate();
	
	--index;
	if (index < 0) return;
	XGCollected *toc = (XGCollected *)(*fTOC);
	fWastedSpace += (toc[index].used.size + 3) & ~3;
	
	if (toc[index].used.next >= 0) {
		toc[toc[index].used.next].used.prev = toc[index].used.prev;
	}
	if (toc[index].used.prev >= 0) {
		toc[toc[index].used.prev].used.next = toc[index].used.next;
	} else {
		fUsedChain = toc[index].used.next;
	}
	
	toc[index].avail.next = fAvailChain;
	toc[index].avail.prev = -1;
	if (fAvailChain >= 0) {
		toc[fAvailChain].avail.prev = index;
	}
	fAvailChain = index;
	
	
	Validate();
	
}

/*$	XGCollection::DeleteAll
 *
 *		Delete all of the memory objects which are allocated in this
 *	particular collection.
 */

void XGCollection::DeleteAll()
{
	
	Validate();
	
	fTOC.SetSize(0);
	fData.SetSize(0);
	fUsedChain = -1;
	fAvailChain = -1;
	fWastedSpace = 0;
	fAllocMark = 0;
	
	Validate();
	
}

/*$	XGCollection::GetSize
 *
 *		Get the size of this object in bytes.
 */

uint32 XGCollection::GetSize(uint32 index)
{
	
	Validate();
	
	--index;
	XGCollected *toc = (XGCollected *)(*fTOC);
	return toc[index].used.size;
}

/*$	XGCollection::SetSize
 *
 *		This adjusts the allocated size of this collection object
 *	to the size specified.
 */

void XGCollection::SetSize(uint32 index, uint32 size)
{
	
	Validate();
	
	--index;
	long oldsize = ((XGCollected *)(*fTOC))[index].used.size;
	if (oldsize < size) {
		int newoffset = GetDataSpace( size );
		int oldoffset = ((XGCollected *)(*fTOC))[index].used.offset;
		fWastedSpace += (oldsize + 3) & ~3;
		memcpy( (newoffset + (char *)*fData), (oldoffset + (char *)*fData), oldsize );
		((XGCollected *)(*fTOC))[index].used.offset = newoffset;
	} else {
		fWastedSpace += ((oldsize + 3) & ~3) - ((size + 3) & ~3);
	}
	((XGCollected *)(*fTOC))[index].used.size = size;
	
	Validate();
	
}

/*$	XGCollection::GetDataPtr
 *
 *		Get a pointer to my data. This simply derefs the handle,
 *	and should be used with caution, as any calls which may adjust
 *	the size of this handle or move it will invalidate this pointer.
 */

void *XGCollection::GetDataPtr(uint32 index)
{
	
	Validate();
	
	--index;
	XGCollected *toc = (XGCollected *)(*fTOC);
	int offset = toc[index].used.offset;
	
	Validate();
	
	return (void *)(offset + (char *)*fData);
}

/*$	XGCollection::GetData
 *
 *		Copy the data refered to by this handle to the pointer
 *	provided. This is a safer (but slower) way to access the
 *	data in a collection object. This returns the amount of
 *	data that was copied.
 */

uint32 XGCollection::GetData(uint32 index, uint32 maxsize, void *data)
{
	
	Validate();
	
	--index;
	XGCollected *toc = (XGCollected *)(*fTOC);
	int offset = toc[index].used.offset;
	int size = toc[index].used.size;
	if (maxsize > size) maxsize = size;
	memcpy( data, (offset + (char *)*fData), maxsize );
	
	Validate();
	
	return maxsize;
}

/*$	XGCollection::SetData
 *
 *		Set the data associated with this collection handle to
 *	the data provided. This adjusts the size of the handle if
 *	needed. This returns the size of the data copied.
 */

uint32 XGCollection::SetData(uint32 index, uint32 size, const void *data)
{
	
	Validate();
	
	SetSize( index, size );
	memcpy( GetDataPtr( index ), data, size );
	Validate();
	
	return size;
	
}

/************************************************************************/
/*																		*/
/*	Internal Routines													*/
/*																		*/
/************************************************************************/


uint32 XGCollection::GetDataSpace( uint32 size )
{
	
	Validate();
	
	if ((fWastedSpace << 1) > (fAllocMark + size)) {
		CompactDataSpace();
	}
	size = (size + 3) & ~3;
	int oldsize = fData.GetSize();
	if (size + fAllocMark > oldsize) {
		fData.SetSize( size + oldsize * 2 );
	}
	long oldmark = fAllocMark;
	fAllocMark += size;
	
	Validate();
	
	return oldmark;
}


void XGCollection::CompactDataSpace()
{
	
	Validate();
	
	XGHandle temp( (fAllocMark - fWastedSpace) * 2 );
	
	fWastedSpace = 0;
	fAllocMark = 0;
	XGCollected *toc = (XGCollected *)(*fTOC);
	for (long index = fUsedChain; index >= 0; index = toc[index].used.next) {
		memcpy( fAllocMark + (char *)*temp, toc[index].used.offset + (char *)*fData, toc[index].used.size );
		toc[index].used.offset = fAllocMark;
		fAllocMark += toc[index].used.size;
	}
	XGHandle::SwapContents( temp, fData );
	
	Validate();
	
}

