--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/fbs/fontandbitmapserver/sfbs/PILE.CPP	Tue Feb 02 01:47:50 2010 +0200
@@ -0,0 +1,315 @@
+// Copyright (c) 1995-2009 Nokia Corporation and/or its subsidiary(-ies).
+// All rights reserved.
+// This component and the accompanying materials are made available
+// under the terms of "Eclipse Public License v1.0"
+// which accompanies this distribution, and is available
+// at the URL "http://www.eclipse.org/legal/epl-v10.html".
+//
+// Initial Contributors:
+// Nokia Corporation - initial contribution.
+//
+// Contributors:
+//
+// Description:
+//
+
+#include <hal.h>
+#include <fbs.h>
+#include <bitmap.h>
+#include "UTILS.H"
+
+
+GLREF_C void Panic(TFbsPanic aPanic);
+
+LOCAL_C TInt GranularRoundUp(TInt aCount)
+	{
+	return (aCount + 7) & ~7;
+	}
+
+CChunkPile::CChunkPile(const RChunk& aChunk)
+:	iChunk(aChunk)
+	{}
+
+EXPORT_C CChunkPile::~CChunkPile()
+	{
+	iChunk.Close();
+	iSmallCells.Close();
+	iFreeSmallCellLinks.Close();
+	iLargeCells.Close();
+	iFreeLargeCellLinks.Close();
+	iLock.Close();
+	}
+
+EXPORT_C CChunkPile* CChunkPile::NewL(const RChunk& aChunk)
+	{
+	CChunkPile* thisptr=new(ELeave) CChunkPile(aChunk);
+	CleanupStack::PushL(thisptr);
+	thisptr->ConstructL();
+	CleanupStack::Pop();
+	return(thisptr);
+	}
+
+void CChunkPile::ConstructL()
+	{
+	TInt ret = iChunk.Duplicate(RThread());
+	__ASSERT_ALWAYS(ret == KErrNone, Panic(EFbsPanicChunkError));
+	HAL::Get(HAL::EMemoryPageSize, iPageSize);
+	__ASSERT_ALWAYS(iPageSize > 4, Panic(EFbsPanicChunkError));
+	iPageMask = iPageSize - 1; // assume page size is a power of 2
+	__ASSERT_ALWAYS(KFbServLargeChunkMinPhysicalSize > 0, Panic(EFbsPanicChunkError));
+	User::LeaveIfError(iChunk.Commit(iPageSize, KFbServLargeChunkMinPhysicalSize));
+	iSmallCells.AppendL(iChunk.Base() + iPageSize); // prevent a data offset of 0 from chunk base
+	iSmallCells.AppendL(iChunk.Base() + iPageSize + KFbServLargeChunkMinPhysicalSize);
+	iFreeSmallCellLinks.AppendL(0);
+	iLargeSectionBottom = iChunk.MaxSize() >> KFbServLargeChunkSizeShifter;
+	iLargeCells.AppendL(iChunk.Base() + iLargeSectionBottom);
+	iLargeCells.AppendL(iChunk.Base() + iChunk.MaxSize());
+	iFreeLargeCellLinks.AppendL(0);
+	User::LeaveIfError(iLock.CreateLocal());
+	}
+
+EXPORT_C TUint8* CChunkPile::ChunkBase() const
+	{
+	return(iChunk.Base());
+	}
+
+EXPORT_C TInt CChunkPile::VirtualSize()
+	{
+	TInt maxmem = 0;
+	HAL::Get(HALData::EMemoryRAM, maxmem);
+	ASSERT(maxmem > 0);
+	return Min(Max(KFbServLargeChunkMinVirtualSize, maxmem << KFbServLargeChunkSizeShifter), KFbServLargeChunkMaxVirtualSize);
+	}
+
+EXPORT_C TUint8* CChunkPile::Alloc(TInt aSize)
+	{
+	__ASSERT_ALWAYS(aSize > 0 && aSize < KMaxTInt / 2, Panic(EFbsPanicChunkError));
+	TUint8* cell;
+	iLock.Wait();
+	if (aSize < KMaxLargeBitmapAlloc)
+		{
+		aSize = Align4(aSize); // round size up to nearest four bytes
+		TInt err = DoAlloc(cell, aSize, iSmallCells, iFreeSmallCellLinks, EFalse);
+		if (err != KErrNone && cell != NULL)
+			{
+			// OOM after the small section grew? if so decommit as much physical memory as possible
+			TInt topIndex = iSmallCells.Count() - 1;
+			if (cell == iSmallCells[topIndex - 1])
+				ShrinkSmallSection((iSmallCells[topIndex] - cell) & ~iPageMask);
+			cell = NULL;
+			}
+		}
+	else
+		{
+		aSize = (aSize + iPageMask) & ~iPageMask; // round size up to nearest page boundary
+		TInt err = DoAlloc(cell, aSize, iLargeCells, iFreeLargeCellLinks, ETrue);
+		if (err != KErrNone && cell != NULL)
+			{
+			iChunk.Decommit(cell - iChunk.Base(), aSize);
+			cell = NULL;
+			}
+		}
+	iLock.Signal();
+	return cell;
+	}
+
+EXPORT_C void CChunkPile::Free(TAny* aCell)
+	{
+	iLock.Wait();
+	if (static_cast<TUint8*>(aCell) < iChunk.Base() + iLargeSectionBottom)
+		DoFree(static_cast<TUint8*>(aCell), iSmallCells, iFreeSmallCellLinks, EFalse);
+	else
+		DoFree(static_cast<TUint8*>(aCell), iLargeCells, iFreeLargeCellLinks, ETrue);
+	iLock.Signal();
+	}
+
+TInt CChunkPile::DoAlloc(TUint8*& aCell, TInt aSize, RPointerArray<TUint8>& aCells, RArray<TInt>& aFreeCellLinks, TBool aLarge)
+/*
+This function tries to allocate a cell of aSize bytes and returns its address in aCell if successful.
+In case of failure aCell is either NULL, if there is not enough memory for a cell of that size,
+or it contains the address of a free cell of at least aSize bytes,
+if there is not enough memory for the internal structures used by CChunkPile.
+*/
+	{
+	__ASSERT_DEBUG(aCells.Count() >= 2, Panic(EFbsPanicChunkError));
+	aCell = NULL;
+	TInt cellIndex = 0;
+	TInt freeCount = aFreeCellLinks.Count();
+	for (TInt freeIndex = 0; freeIndex < freeCount; ++freeIndex)
+		{
+		TInt freeCellLink = aFreeCellLinks[freeIndex];
+		cellIndex += freeCellLink;
+		TInt size = aCells[cellIndex + 1] - aCells[cellIndex];
+		if (size >= aSize)
+			{
+			if (aLarge)
+				{
+				TInt err = iChunk.Commit(aCells[cellIndex] - iChunk.Base(), aSize);
+				if (err != KErrNone)
+					return err;
+				}
+			aCell = aCells[cellIndex];
+			if (size == aSize) // exact fit?
+				{
+				aFreeCellLinks.Remove(freeIndex);
+				if (freeIndex < aFreeCellLinks.Count())
+					aFreeCellLinks[freeIndex] += freeCellLink;
+				}
+			else
+				{
+				// make sure there are always enough empty slots in aFreeCellLinks
+				TInt err = aFreeCellLinks.Reserve(GranularRoundUp((aCells.Count() + 1) >> 1));
+				if (err != KErrNone)
+					return err;
+				err = aCells.Insert(aCell + aSize, cellIndex + 1);
+				if (err != KErrNone)
+					return err;
+				++aFreeCellLinks[freeIndex];
+				}
+			return KErrNone;
+			}
+		}
+	if (aLarge)
+		return KErrNoMemory;
+	TInt err = GrowSmallSection(aSize, cellIndex);
+	if (err != KErrNone)
+		return err;
+	TInt topIndex = iSmallCells.Count() - 1;
+	aCell = iSmallCells[topIndex - 1];
+	if (iSmallCells[topIndex] - aCell == aSize) // exact fit?
+		{
+		iFreeSmallCellLinks.Remove(iFreeSmallCellLinks.Count() - 1);
+		}
+	else
+		{
+		// make sure there are always enough empty slots in aFreeCellLinks
+		err = iFreeSmallCellLinks.Reserve(GranularRoundUp((iSmallCells.Count() + 1) >> 1));
+		if (err != KErrNone)
+			return err;
+		err = iSmallCells.Insert(aCell + aSize, topIndex);
+		if (err != KErrNone)
+			return err;
+		++iFreeSmallCellLinks[iFreeSmallCellLinks.Count() - 1];
+		}
+	return KErrNone;
+	}
+
+void CChunkPile::DoFree(TUint8* aCell, RPointerArray<TUint8>& aCells, RArray<TInt>& aFreeCellLinks, TBool aLarge)
+	{
+	TInt cellIndex = aCells.FindInAddressOrder(aCell);
+	__ASSERT_DEBUG(cellIndex >= 0 && cellIndex < aCells.Count() - 1, Panic(EFbsPanicChunkError));
+	if (cellIndex < 0 || cellIndex == aCells.Count() - 1)
+		return;
+	TInt prevIndex = KMaxTInt;
+	TInt nextIndex = 0;
+	TInt freeCount = aFreeCellLinks.Count();
+	TInt freeIndex;
+	for (freeIndex = 0; freeIndex < freeCount; ++freeIndex)
+		{
+		nextIndex += aFreeCellLinks[freeIndex];
+		if (nextIndex >= cellIndex)
+			{
+			__ASSERT_DEBUG(nextIndex > cellIndex, Panic(EFbsPanicChunkError));
+			if (nextIndex == cellIndex)
+				return;
+			break;
+			}
+		prevIndex = nextIndex;
+		}
+	if (aLarge)
+		iChunk.Decommit(aCell - iChunk.Base(), aCells[cellIndex + 1] - aCell);
+	if (prevIndex == cellIndex - 1 && nextIndex == cellIndex + 1)
+		{
+		aFreeCellLinks.Remove(freeIndex);
+		aCells.Remove(cellIndex + 1);
+		aCells.Remove(cellIndex--);
+		}
+	else if (prevIndex == cellIndex - 1)
+		{
+		if (freeIndex < freeCount)
+			--aFreeCellLinks[freeIndex];
+		aCells.Remove(cellIndex--);
+		}
+	else if (nextIndex == cellIndex + 1)
+		{
+		--aFreeCellLinks[freeIndex];
+		aCells.Remove(cellIndex + 1);
+		}
+	else
+		{
+		if (freeIndex < freeCount)
+			aFreeCellLinks[freeIndex] = nextIndex - cellIndex;
+		aFreeCellLinks.Insert(freeIndex > 0 ? cellIndex - prevIndex : cellIndex, freeIndex); // can't fail
+		}
+	if (aLarge)
+		return;
+	TInt topIndex = aCells.Count() - 1;
+	if (cellIndex == topIndex - 1)
+		{
+		// last cell is free and has just grown, shrink with granularity iPageSize << KFbServLargeChunkGrowByShifter
+		TInt roundMask = (iPageSize << KFbServLargeChunkGrowByShifter) - 1;
+		ShrinkSmallSection((aCells[topIndex] - aCells[cellIndex]) & ~roundMask);
+		}
+	}
+
+TInt CChunkPile::GrowSmallSection(TInt aSize, TInt aLastFreeCell)
+/*
+This function tries to grow the section for small cells with granularity iPageSize << KFbServLargeChunkGrowByShifter.
+It appends or expands the last free cell so that it has at least aSize bytes if successful.
+aLastFreeCell must be the index of the last free cell in the small section or 0 if there is none.
+*/
+	{
+	TInt roundMask = (iPageSize << KFbServLargeChunkGrowByShifter) - 1;
+	TInt topIndex = iSmallCells.Count() - 1;
+	TInt maxGrowBy = (iChunk.Base() + iLargeSectionBottom) - iSmallCells[topIndex];
+	__ASSERT_DEBUG(maxGrowBy >= 0, Panic(EFbsPanicChunkError));
+	if (iFreeSmallCellLinks.Count() > 0 && aLastFreeCell == topIndex - 1)
+		{
+		// last cell is free
+		TInt growBy = (iSmallCells[aLastFreeCell] + aSize) - iSmallCells[topIndex];
+		__ASSERT_DEBUG(growBy > 0, Panic(EFbsPanicChunkError));
+		if (growBy > maxGrowBy)
+			return KErrNoMemory;
+		growBy = Min((growBy + roundMask) & ~roundMask, maxGrowBy);
+		TInt err = iChunk.Commit(iSmallCells[topIndex] - iChunk.Base(), growBy);
+		if (err != KErrNone)
+			return err;
+		iSmallCells[topIndex] += growBy;
+		}
+	else
+		{
+		// last cell is not free
+		if (aSize > maxGrowBy)
+			return KErrNoMemory;
+		TInt growBy = Min((aSize + roundMask) & ~roundMask, maxGrowBy);
+		TInt err = iSmallCells.Reserve(GranularRoundUp(iSmallCells.Count() + 1));
+		if (err != KErrNone)
+			return err;
+		err = iFreeSmallCellLinks.Reserve(GranularRoundUp((iSmallCells.Count() + 1) >> 1));
+		if (err != KErrNone)
+			return err;
+		err = iChunk.Commit(iSmallCells[topIndex] - iChunk.Base(), growBy);
+		if (err != KErrNone)
+			return err;
+		iSmallCells.Append(iSmallCells[topIndex] + growBy); // can't fail
+		iFreeSmallCellLinks.Append(topIndex - aLastFreeCell); // can't fail
+		}
+	return KErrNone;
+	}
+
+void CChunkPile::ShrinkSmallSection(TInt aShrinkBy)
+	{
+	TInt topIndex = iSmallCells.Count() - 1;
+	TInt maxShrinkBy = (iSmallCells[topIndex] - iChunk.Base()) - (KFbServLargeChunkMinPhysicalSize + iPageSize);
+	__ASSERT_DEBUG(maxShrinkBy >= 0, Panic(EFbsPanicChunkError));
+	aShrinkBy = Min(aShrinkBy, maxShrinkBy);
+	if (aShrinkBy > 0)
+		{
+		iChunk.Decommit((iSmallCells[topIndex] -= aShrinkBy) - iChunk.Base(), aShrinkBy);
+		if (iSmallCells[topIndex] == iSmallCells[topIndex - 1])
+			{
+			iSmallCells.Remove(topIndex);
+			iFreeSmallCellLinks.Remove(iFreeSmallCellLinks.Count() - 1);
+			}
+		}
+	}