// Copyright (c) 1998-2009 Nokia Corporation and/or its subsidiary(-ies).

// All rights reserved.

// This component and the accompanying materials are made available

// under the terms of the License "Symbian Foundation License v1.0"

// which accompanies this distribution, and is available

// at the URL "http://www.symbianfoundation.org/legal/sfl-v10.html".

//

// Initial Contributors:

// Nokia Corporation - initial contribution.

//

// Contributors:

//

// Description:

// e32\common\array.cpp

// 

//

#include "common.h"

#ifdef __KERNEL_MODE__

#include <kernel.h>

#endif

const TInt KDefaultPtrArrayGranularity		=8;

const TInt KPtrArrayMaxGranularity			=0x10000000;

const TInt KDefaultSimpleArrayGranularity	=8;

const TInt KSimpleArrayMaxGranularity		=0x10000000;

const TInt KSimpleArrayMaxEntrySize			=640;	// allow room for a unicode TFullName

const TInt KMaxArrayGrowBy					=65535;

const TInt KMinArrayFactor					=257;

const TInt KMaxArrayFactor					=32767;

EXPORT_C RPointerArrayBase::RPointerArrayBase()

	: iCount(0), iEntries(NULL), iAllocated(0), iGranularity(KDefaultPtrArrayGranularity), iSpare1(0), iSpare2(0)

	{}

EXPORT_C RPointerArrayBase::RPointerArrayBase(TInt aGranularity)

	: iCount(0), iEntries(NULL), iAllocated(0), iGranularity(aGranularity), iSpare1(0), iSpare2(0)

	{

	__ASSERT_ALWAYS(aGranularity>0 && aGranularity<=KPtrArrayMaxGranularity,

		Panic(EBadArrayGranularity));

	}

EXPORT_C RPointerArrayBase::RPointerArrayBase(TInt aMinGrowBy, TInt aFactor)

	: iCount(0), iEntries(NULL), iAllocated(0), iSpare1(0), iSpare2(0)

	{

	__ASSERT_ALWAYS(aMinGrowBy>0 && aMinGrowBy<=KMaxArrayGrowBy, Panic(EBadArrayMinGrowBy));

	__ASSERT_ALWAYS(aFactor>=KMinArrayFactor && aFactor<=KMaxArrayFactor, Panic(EBadArrayFactor));

	iGranularity = aMinGrowBy | (aFactor << 16) | 0x80000000;

	}

#ifndef __KERNEL_MODE__

EXPORT_C RPointerArrayBase::RPointerArrayBase(TAny** aEntries, TInt aCount)

	: iCount(aCount), iEntries(aEntries), iAllocated(aCount), iGranularity(aCount), iSpare1(0), iSpare2(0)

	{

	__ASSERT_ALWAYS(aCount>0,Panic(EBadArrayCount));

	}

#endif

EXPORT_C void RPointerArrayBase::Close()

	{

	iCount=0;

	STD_CLASS::Free(iEntries);

	iEntries=NULL;

	iAllocated=0;

	}

EXPORT_C TInt RPointerArrayBase::Count() const

	{

	return iCount;

	}

#ifndef __ARRAY_MACHINE_CODED__

EXPORT_C TAny*& RPointerArrayBase::At(TInt anIndex) const

	{

	__ASSERT_ALWAYS((anIndex>=0 && anIndex<iCount),Panic(EBadArrayIndex));

	return iEntries[anIndex];

	}

#else

GLDEF_C void PanicBadArrayIndex()

	{

	Panic(EBadArrayIndex);

	}

#endif

TInt CalculateArraySizeAfterGrow(TInt aOrigSize, TInt aGranularity, TInt aLimit)

	{

	if (aGranularity >= 0)

		{

		if (aOrigSize > aLimit - aGranularity)

			return KErrNoMemory;	// array can't be >2GB

		return aOrigSize + aGranularity;

		}

	TUint minStep = (TUint)(aGranularity & 65535);

	TUint factor = TUint(aGranularity & 0x7fff0000) >> 16;

	Uint64 na64 = aOrigSize;

	na64 *= (Uint64)factor;

	na64 += 128;

	na64 >>= 8;

	Uint64 min_na64 = (Uint64)aOrigSize + (Uint64)minStep;

	if (min_na64 > na64)

		na64 = min_na64;

	if (na64 > (Uint64)aLimit)

		return KErrNoMemory;	// array can't be >2GB

	return (TInt)na64;

	}

TInt CalculateArraySizeAfterShrink(TInt aOrigSize, TInt aGranularity, TInt aUsed)

	{

	TInt step = aGranularity;

	if (step < 0)

		step &= 65535;

	if (aOrigSize - aUsed < step)

		return aOrigSize;

	aUsed += step - 1;

	aUsed /= step;

	aUsed *= step;

	return aUsed;

	}

TInt RPointerArrayBase::Grow()

	{

	TInt newAlloc = CalculateArraySizeAfterGrow(iAllocated, iGranularity, KMaxTInt >> 2);

	if (newAlloc < 0)

		return newAlloc;

	TAny** pA = (TAny**)STD_CLASS::ReAlloc(iEntries, newAlloc*sizeof(TAny*));

	if (!pA)

		return KErrNoMemory;

	iEntries = pA;

	iAllocated = newAlloc;

	return KErrNone;

	}

#ifndef __ARRAY_MACHINE_CODED__

EXPORT_C TInt RPointerArrayBase::Append(const TAny* anEntry)

	{

	if (iCount==iAllocated)

		{

		TInt r=Grow();

		if (r!=KErrNone)

			return r;

		}

	iEntries[iCount++]=(TAny*)anEntry;

	return KErrNone;

	}

#endif

EXPORT_C TInt RPointerArrayBase::Insert(const TAny* anEntry, TInt aPos)

	{

	__ASSERT_ALWAYS((aPos>=0 && aPos<=iCount),Panic(EBadArrayPosition));

	if (iCount==iAllocated)

		{

		TInt r=Grow();

		if (r!=KErrNone)

			return r;

		}

	TInt entries=iCount-aPos;

	if (entries!=0)

		wordmove(iEntries+aPos+1,iEntries+aPos,entries*sizeof(TAny*));

	iCount++;

	iEntries[aPos]=(TAny*)anEntry;

	return KErrNone;

	}

EXPORT_C void RPointerArrayBase::Remove(TInt anIndex)

	{

	__ASSERT_ALWAYS((anIndex>=0 && anIndex<iCount),Panic(EBadArrayIndex));

	TInt entries=iCount-anIndex-1;

	if (entries!=0)

		wordmove(iEntries+anIndex,iEntries+anIndex+1,entries*sizeof(TAny*));

	iCount--;

	}

EXPORT_C void RPointerArrayBase::Compress()

	{

	if (iCount)

		iEntries=(TAny**)STD_CLASS::ReAlloc(iEntries,iCount*sizeof(TAny*)); // can't fail

	else

		{

		STD_CLASS::Free(iEntries);

		iEntries=NULL;

		}

	iAllocated=iCount;

	}

#ifndef __KERNEL_MODE__

EXPORT_C void RPointerArrayBase::GranularCompress()

	{

	TInt newAlloc = CalculateArraySizeAfterShrink(iAllocated, iGranularity, iCount);

	if (newAlloc == iAllocated)

		return;

	if (newAlloc)

		iEntries=(TAny**)STD_CLASS::ReAlloc(iEntries,newAlloc*sizeof(TAny*)); // can't fail

	else

		{

		STD_CLASS::Free(iEntries);

		iEntries=NULL;

		}

	iAllocated=newAlloc;

	}

EXPORT_C TInt RPointerArrayBase::DoReserve(TInt aCount)

	{

	__ASSERT_ALWAYS(aCount>=0, Panic(EArrayBadReserveCount));

	if (aCount <= iAllocated)

		return KErrNone;	// if allocated space is already sufficient, nothing to do

	const TInt KLimit = TInt(0x80000000u / sizeof(TAny*));

	if (aCount >= KLimit)

		return KErrNoMemory;

	TAny** pA = (TAny**)STD_CLASS::ReAlloc(iEntries, aCount*sizeof(TAny*));

	if (!pA)

		return KErrNoMemory;

	iEntries = pA;

	iAllocated = aCount;

	return KErrNone;

	}

#endif

EXPORT_C void RPointerArrayBase::Reset()

	{

	iCount=0;

	STD_CLASS::Free(iEntries);

	iEntries=NULL;

	iAllocated=0;

	}

EXPORT_C TInt RPointerArrayBase::BinarySearch(const TAny* anEntry, TInt& anIndex, TGeneralLinearOrder anOrder) const

	{

	return BinarySearch(anEntry, anIndex, anOrder, EArrayFindMode_Any);

	}

#ifndef __ARRAY_MACHINE_CODED__

EXPORT_C TInt RPointerArrayBase::Find(const TAny* anEntry) const

	{

	TInt i;

	for (i=0; i<iCount; i++)

		{

		if (iEntries[i]==anEntry)

			return i;

		}

	return KErrNotFound;

	}

EXPORT_C TInt RPointerArrayBase::Find(const TAny* anEntry, TGeneralIdentityRelation anIdentity) const

	{

	TInt i;

	for (i=0; i<iCount; i++)

		{

		if ((*anIdentity)(anEntry,iEntries[i]))

			return i;

		}

	return KErrNotFound;

	}

EXPORT_C TInt RPointerArrayBase::BinarySearchSigned(TInt anEntry, TInt& anIndex) const

	{

	return BinarySearchSigned(anEntry, anIndex, EArrayFindMode_Any);

	}

EXPORT_C TInt RPointerArrayBase::BinarySearchSigned(TInt anEntry, TInt& anIndex, TInt aMode) const

	{

	__ASSERT_DEBUG(TUint(aMode)<TUint(EArrayFindMode_Limit), Panic(EBadArrayFindMode));

	TInt l=0;

	TInt r=iCount;

	TInt ret = KErrNotFound;

	while(r>l)

		{

		TInt m=(l+r)>>1;

		TInt h=(TInt)iEntries[m];

		if (anEntry==h)

			{

			if (aMode == EArrayFindMode_Any)

				{

				anIndex=m;

				return KErrNone;

				}

			ret = KErrNone;

			if (aMode == EArrayFindMode_First)

				r=m;

			else

				l=m+1;

			}

		else if (anEntry>h)

			l=m+1;

		else

			r=m;

		}

	anIndex=r;

	return ret;

	}

EXPORT_C TInt RPointerArrayBase::BinarySearchUnsigned(TUint anEntry, TInt& anIndex) const

	{

	return BinarySearchUnsigned(anEntry, anIndex, EArrayFindMode_Any);

	}

EXPORT_C TInt RPointerArrayBase::BinarySearchUnsigned(TUint anEntry, TInt& anIndex, TInt aMode) const

	{

	__ASSERT_DEBUG(TUint(aMode)<TUint(EArrayFindMode_Limit), Panic(EBadArrayFindMode));

	TInt l=0;

	TInt r=iCount;

	TInt ret = KErrNotFound;

	while(r>l)

		{

		TUint m=(l+r)>>1;

		TUint h=(TUint)iEntries[m];

		if (anEntry==h)

			{

			if (aMode == EArrayFindMode_Any)

				{

				anIndex=m;

				return KErrNone;

				}

			ret = KErrNone;

			if (aMode == EArrayFindMode_First)

				r=m;

			else

				l=m+1;

			}

		else if (anEntry>h)

			l=m+1;

		else

			r=m;

		}

	anIndex=r;

	return ret;

	}

EXPORT_C TInt RPointerArrayBase::BinarySearch(const TAny* anEntry, TInt& anIndex, TGeneralLinearOrder anOrder, TInt aMode) const

	{

	__ASSERT_DEBUG(TUint(aMode)<TUint(EArrayFindMode_Limit), Panic(EBadArrayFindMode));

	TInt l=0;

	TInt r=iCount;

	TInt ret = KErrNotFound;

	while(r>l)

		{

		TInt m=(l+r)>>1;

		TInt k=(*anOrder)(anEntry,iEntries[m]);

		if (k==0)

			{

			if (aMode == EArrayFindMode_Any)

				{

				anIndex=m;

				return KErrNone;

				}

			ret = KErrNone;

			if (aMode == EArrayFindMode_First)

				r=m;

			else

				l=m+1;

			}

		else if (k>0)

			l=m+1;

		else

			r=m;

		}

	anIndex=r;

	return ret;

	}

EXPORT_C TInt RPointerArrayBase::FindIsqSigned(TInt anEntry) const

	{

	return FindIsqSigned(anEntry, EArrayFindMode_Any);

	}

EXPORT_C TInt RPointerArrayBase::FindIsqUnsigned(TUint anEntry) const

	{

	return FindIsqUnsigned(anEntry, EArrayFindMode_Any);

	}

EXPORT_C TInt RPointerArrayBase::FindIsq(const TAny* anEntry, TGeneralLinearOrder anOrder) const

	{

	return FindIsq(anEntry, anOrder, EArrayFindMode_Any);

	}

EXPORT_C TInt RPointerArrayBase::FindIsqSigned(TInt anEntry, TInt aMode) const

	{

	TInt i;

	TInt r=BinarySearchSigned(anEntry,i,aMode);

	return (r==KErrNone)?i:r;

	}

EXPORT_C TInt RPointerArrayBase::FindIsqUnsigned(TUint anEntry, TInt aMode) const

	{

	TInt i;

	TInt r=BinarySearchUnsigned(anEntry,i,aMode);

	return (r==KErrNone)?i:r;

	}

EXPORT_C TInt RPointerArrayBase::FindIsq(const TAny* anEntry, TGeneralLinearOrder anOrder, TInt aMode) const

	{

	TInt i;

	TInt r=BinarySearch(anEntry,i,anOrder,aMode);

	return (r==KErrNone)?i:r;

	}

#else

extern "C" void PanicBadArrayFindMode()

	{

	Panic(EBadArrayFindMode);

	}

#endif

EXPORT_C TInt RPointerArrayBase::FindReverse(const TAny* anEntry) const

	{

	TInt i=iCount;

	while (i--)

		{

		if (iEntries[i]==anEntry)

			return i;

		}

	return KErrNotFound;

	}

EXPORT_C TInt RPointerArrayBase::FindReverse(const TAny* anEntry, TGeneralIdentityRelation anIdentity) const

	{

	TInt i=iCount;

	while (i--)

		{

		if ((*anIdentity)(anEntry,iEntries[i]))

			return i;

		}

	return KErrNotFound;

	}

EXPORT_C TInt RPointerArrayBase::InsertIsqSigned(TInt anEntry, TBool aAllowRepeats)

	{

	TInt i;

	TInt mode = aAllowRepeats ? EArrayFindMode_Last : EArrayFindMode_Any;

	TInt r=BinarySearchSigned(anEntry,i,mode);

	if (r==KErrNotFound || aAllowRepeats)

		return Insert((const TAny*)anEntry,i);

	return KErrAlreadyExists;

	}

EXPORT_C TInt RPointerArrayBase::InsertIsqUnsigned(TUint anEntry, TBool aAllowRepeats)

	{

	TInt i;

	TInt mode = aAllowRepeats ? EArrayFindMode_Last : EArrayFindMode_Any;

	TInt r=BinarySearchUnsigned(anEntry,i,mode);

	if (r==KErrNotFound || aAllowRepeats)

		return Insert((const TAny*)anEntry,i);

	return KErrAlreadyExists;

	}

EXPORT_C TInt RPointerArrayBase::InsertIsq(const TAny* anEntry, TGeneralLinearOrder anOrder, TBool aAllowRepeats)

	{

	TInt i;

	TInt mode = aAllowRepeats ? EArrayFindMode_Last : EArrayFindMode_Any;

	TInt r=BinarySearch(anEntry,i,anOrder,mode);

	if (r==KErrNotFound || aAllowRepeats)

		return Insert((const TAny*)anEntry,i);

	return KErrAlreadyExists;

	}

#ifndef __ARRAY_MACHINE_CODED__

void HeapSortUnsigned(TUint* aEntries,TInt aCount)

	{

	TInt ss = aCount;

	if (ss>1)

		{

		TInt sh = ss>>1;

		FOREVER

			{

			TUint si;

			if (sh!=0)

				{

				--sh;

				si = aEntries[sh];

				}

			else

				{

				--ss;

				si = aEntries[ss];

				aEntries[ss]=aEntries[0];

				if (ss==1)

					{

					aEntries[0]=si;

					break;

					}

				}

			TInt ii = sh;

			TInt jj = sh;

			FOREVER

				{

				jj = (jj+1)<<1;

				if (jj>=ss || TUint(aEntries[jj-1])>TUint(aEntries[jj]) )

					--jj;

				if (jj>=ss || TUint(aEntries[jj])<=si)

					break;

				aEntries[ii]=aEntries[jj];

				ii = jj;

				}

			aEntries[ii]=si;

			}

		}

	}

#endif // !__ARRAY_MACHINE_CODED__

#ifndef __KERNEL_MODE__

#ifndef __ARRAY_MACHINE_CODED__

EXPORT_C void RPointerArrayBase::HeapSortSigned()

	{

	TInt ss = iCount;

	if (ss>1)

		{

		TInt sh = ss>>1;

		FOREVER

			{

			TInt si;

			if (sh!=0)

				{

				--sh;

				si = (TInt)iEntries[sh];

				}

			else

				{

				--ss;

				si = (TInt)iEntries[ss];

				iEntries[ss]=iEntries[0];

				if (ss==1)

					{

					iEntries[0]=(TAny*)si;

					break;

					}