kernel/eka/common/array.cpp
changeset 0 a41df078684a
child 148 31ea0f8e3c99
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/kernel/eka/common/array.cpp	Mon Oct 19 15:55:17 2009 +0100
@@ -0,0 +1,1179 @@
+// 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 "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:
+// e32\common\array.cpp
+// 
+//
+
+#include "common.h"
+#ifdef __KERNEL_MODE__
+#include <kernel/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;
+					}
+				}
+			TInt ii = sh;
+			TInt jj = sh;
+			FOREVER
+				{
+				jj = (jj+1)<<1;
+				if (jj>=ss || TInt(iEntries[jj-1])>TInt(iEntries[jj]) )
+					--jj;
+				if (jj>=ss || TInt(iEntries[jj])<=si)
+					break;
+				iEntries[ii]=iEntries[jj];
+				ii = jj;
+				}
+			iEntries[ii]=(TAny*)si;
+			}
+		}
+	}
+
+EXPORT_C void RPointerArrayBase::HeapSortUnsigned()
+	{
+	::HeapSortUnsigned((TUint*)iEntries,iCount);
+	}
+
+EXPORT_C void RPointerArrayBase::HeapSort(TGeneralLinearOrder anOrder)
+	{
+	TInt ss = iCount;
+	if (ss>1)
+		{
+		TInt sh = ss>>1;
+		FOREVER
+			{
+			TAny* si;
+			if (sh!=0)
+				{
+				--sh;
+				si = iEntries[sh];
+				}
+			else
+				{
+				--ss;
+				si = iEntries[ss];
+				iEntries[ss]=iEntries[0];
+				if (ss==1)
+					{
+					iEntries[0]=si;
+					break;
+					}
+				}
+			TInt ii = sh;
+			TInt jj = sh;
+			FOREVER
+				{
+				jj = (jj+1)<<1;
+				if (jj>=ss || (*anOrder)(iEntries[jj-1],iEntries[jj])>0 )
+					--jj;
+				if (jj>=ss || (*anOrder)(iEntries[jj],si)<=0 )
+					break;
+				iEntries[ii]=iEntries[jj];
+				ii = jj;
+				}
+			iEntries[ii]=si;
+			}
+		}
+	}
+#endif
+
+EXPORT_C TInt RPointerArrayBase::GetCount(const CBase* aPtr)
+	{
+	return ((RPointerArrayBase*)aPtr)->Count();
+	}
+
+EXPORT_C const TAny* RPointerArrayBase::GetElementPtr(const CBase* aPtr, TInt aIndex)
+	{
+	return &(((RPointerArrayBase*)aPtr)->At(aIndex));
+	}
+#endif	// __KERNEL_MODE__
+
+EXPORT_C RArrayBase::RArrayBase(TInt anEntrySize)
+	:	iCount(0), iEntries(NULL), iKeyOffset(0), iAllocated(0),
+		iGranularity(KDefaultSimpleArrayGranularity), iSpare1(0), iSpare2(0)
+	{
+	__ASSERT_ALWAYS(anEntrySize>0 && anEntrySize<=KSimpleArrayMaxEntrySize,Panic(EBadArrayEntrySize));
+	iEntrySize=(anEntrySize+(TInt)sizeof(TInt)-1)&~((TInt)sizeof(TInt)-1);
+	}
+
+EXPORT_C RArrayBase::RArrayBase(TInt anEntrySize, TInt aGranularity)
+	:	iCount(0), iEntries(NULL), iKeyOffset(0), iAllocated(0),
+		iGranularity(aGranularity), iSpare1(0), iSpare2(0)
+	{
+	__ASSERT_ALWAYS(anEntrySize>0 && anEntrySize<=KSimpleArrayMaxEntrySize,Panic(EBadArrayEntrySize));
+	__ASSERT_ALWAYS(aGranularity>0 && (aGranularity*anEntrySize)<=KSimpleArrayMaxGranularity, Panic(EBadArrayGranularity));
+	iEntrySize=(anEntrySize+(TInt)sizeof(TInt)-1)&~((TInt)sizeof(TInt)-1);
+	}
+
+EXPORT_C RArrayBase::RArrayBase(TInt aEntrySize,TAny* aEntries, TInt aCount)
+	:	iCount(aCount), iEntries(aEntries), iKeyOffset(0), iAllocated(aCount),
+		iGranularity(KDefaultSimpleArrayGranularity), iSpare1(0), iSpare2(0)
+	{
+	__ASSERT_ALWAYS(aEntrySize>0 && aEntrySize<=KSimpleArrayMaxEntrySize,Panic(EBadArrayEntrySize));
+	__ASSERT_ALWAYS(aCount>0,Panic(EBadArrayCount));
+	iEntrySize=(aEntrySize+(TInt)sizeof(TInt)-1)&~((TInt)sizeof(TInt)-1);
+	}
+
+EXPORT_C RArrayBase::RArrayBase(TInt anEntrySize, TInt aGranularity, TInt aKeyOffset)
+	:	 iCount(0), iEntries(NULL), iKeyOffset(aKeyOffset), iAllocated(0),
+		iGranularity(aGranularity), iSpare1(0), iSpare2(0)
+	{
+	__ASSERT_ALWAYS(anEntrySize>0 && anEntrySize<=KSimpleArrayMaxEntrySize,Panic(EBadArrayEntrySize));
+	__ASSERT_ALWAYS(aGranularity>0 && (aGranularity*anEntrySize)<=KSimpleArrayMaxGranularity, Panic(EBadArrayGranularity));
+	__ASSERT_ALWAYS(aKeyOffset>=0 && (aKeyOffset&3)==0 && aKeyOffset<anEntrySize, Panic(EBadArrayKeyOffset));
+	iEntrySize=(anEntrySize+(TInt)sizeof(TInt)-1)&~((TInt)sizeof(TInt)-1);
+	}
+
+EXPORT_C RArrayBase::RArrayBase(TInt aEntrySize, TInt aMinGrowBy, TInt aKeyOffset, TInt aFactor)
+	:	 iCount(0), iEntries(NULL), iKeyOffset(aKeyOffset), iAllocated(0), iSpare1(0), iSpare2(0)
+	{
+	__ASSERT_ALWAYS(aEntrySize>0 && aEntrySize<=KSimpleArrayMaxEntrySize, Panic(EBadArrayEntrySize));
+	__ASSERT_ALWAYS(aKeyOffset>=0 && (aKeyOffset&3)==0 && aKeyOffset<aEntrySize, Panic(EBadArrayKeyOffset));
+	__ASSERT_ALWAYS(aMinGrowBy>0 && aMinGrowBy<=KMaxArrayGrowBy, Panic(EBadArrayMinGrowBy));
+	__ASSERT_ALWAYS(aFactor>=KMinArrayFactor && aFactor<=KMaxArrayFactor, Panic(EBadArrayFactor));
+	iEntrySize=(aEntrySize+(TInt)sizeof(TInt)-1)&~((TInt)sizeof(TInt)-1);
+	iGranularity = aMinGrowBy | (aFactor << 16) | 0x80000000;
+	}
+
+EXPORT_C void RArrayBase::Close()
+	{
+	iCount=0;
+	STD_CLASS::Free(iEntries);
+	iEntries=NULL;
+	iAllocated=0;
+	}
+
+EXPORT_C TInt RArrayBase::Count() const
+	{
+	return iCount;
+	}
+
+#ifndef __ARRAY_MACHINE_CODED__
+EXPORT_C TAny* RArrayBase::At(TInt anIndex) const
+	{
+	__ASSERT_ALWAYS((anIndex>=0 && anIndex<iCount),Panic(EBadArrayIndex));
+	return (((TUint8*)iEntries)+anIndex*iEntrySize);
+	}
+#endif
+
+TInt RArrayBase::Grow()
+	{
+	TInt newAlloc = CalculateArraySizeAfterGrow(iAllocated, iGranularity, KMaxTInt/iEntrySize);
+	if (newAlloc < 0)
+		return newAlloc;
+	TAny** pA = (TAny**)STD_CLASS::ReAlloc(iEntries, newAlloc*iEntrySize);
+	if (!pA)
+		return KErrNoMemory;
+	iEntries = pA;
+	iAllocated = newAlloc;
+	return KErrNone;
+	}
+
+#ifndef __ARRAY_MACHINE_CODED__
+EXPORT_C TInt RArrayBase::Append(const TAny* anEntry)
+	{
+	if (iCount==iAllocated)
+		{
+		TInt r=Grow();
+		if (r!=KErrNone)
+			return r;
+		}
+	wordmove((TUint8*)iEntries+iCount*iEntrySize, anEntry, iEntrySize);
+	iCount++;
+	return KErrNone;
+	}
+#endif
+
+EXPORT_C TInt RArrayBase::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;
+		}
+	TUint8 *pS=(TUint8*)iEntries+aPos*iEntrySize;
+	TUint8 *pD=pS+iEntrySize;
+	TInt entries=iCount-aPos;
+	if (entries!=0)
+		wordmove(pD,pS,entries*iEntrySize);
+	wordmove(pS,anEntry,iEntrySize);
+	iCount++;
+	return KErrNone;
+	}
+
+EXPORT_C void RArrayBase::Remove(TInt anIndex)
+	{
+	__ASSERT_ALWAYS((anIndex>=0 && anIndex<iCount),Panic(EBadArrayIndex));
+	TUint8 *pD=(TUint8*)iEntries+anIndex*iEntrySize;
+	TUint8 *pS=pD+iEntrySize;
+	TInt entries=iCount-anIndex-1;
+	if (entries!=0)
+		wordmove(pD,pS,entries*iEntrySize);
+	iCount--;
+	}
+
+EXPORT_C void RArrayBase::Compress()
+	{
+	if (iCount)
+		iEntries=STD_CLASS::ReAlloc(iEntries,iCount*iEntrySize); // can't fail
+	else
+		{
+		STD_CLASS::Free(iEntries);
+		iEntries=NULL;
+		}
+	iAllocated=iCount;
+	}
+
+#ifndef __KERNEL_MODE__
+EXPORT_C void RArrayBase::GranularCompress()
+	{
+	TInt newAlloc = CalculateArraySizeAfterShrink(iAllocated, iGranularity, iCount);
+	if (newAlloc == iAllocated)
+		return;
+	if (newAlloc)
+		iEntries=STD_CLASS::ReAlloc(iEntries,newAlloc*iEntrySize); // can't fail
+	else
+		{
+		STD_CLASS::Free(iEntries);
+		iEntries=NULL;
+		}
+	iAllocated=newAlloc;
+	}
+
+EXPORT_C TInt RArrayBase::DoReserve(TInt aCount)
+	{
+	__ASSERT_ALWAYS(aCount>=0, Panic(EArrayBadReserveCount));
+	if (aCount <= iAllocated)
+		return KErrNone;	// if allocated space is already sufficient, nothing to do
+
+	Int64 size = Int64(aCount) * Int64(iEntrySize);
+	if (size > Int64(KMaxTInt))
+		return KErrNoMemory;
+
+	TAny** pA = (TAny**)STD_CLASS::ReAlloc(iEntries, aCount*iEntrySize);
+	if (!pA)
+		return KErrNoMemory;
+	iEntries = pA;
+	iAllocated = aCount;
+	return KErrNone;
+	}
+#endif
+
+EXPORT_C void RArrayBase::Reset()
+	{
+	iCount=0;
+	STD_CLASS::Free(iEntries);
+	iEntries=NULL;
+	iAllocated=0;
+	}
+
+EXPORT_C TInt RArrayBase::BinarySearch(const TAny* anEntry, TInt& anIndex, TGeneralLinearOrder anOrder) const
+	{
+	return BinarySearch(anEntry, anIndex, anOrder, EArrayFindMode_Any);
+	}
+
+#ifndef __ARRAY_MACHINE_CODED__
+EXPORT_C TInt RArrayBase::Find(const TAny* anEntry) const
+	{
+	TUint8 *pS=(TUint8*)iEntries+iKeyOffset;
+	TInt match=*(TInt*)((TUint8*)anEntry+iKeyOffset);
+	TInt i;
+	for (i=0; i<iCount; i++)
+		{
+		TInt key=*(TInt*)pS;
+		if (key==match)
+			return i;
+		pS+=iEntrySize;
+		}
+	return KErrNotFound;
+	}
+
+EXPORT_C TInt RArrayBase::Find(const TAny* anEntry, TGeneralIdentityRelation anIdentity) const
+	{
+	TUint8 *pS=(TUint8*)iEntries;
+	TInt i;
+	for (i=0; i<iCount; i++)
+		{
+		if ((*anIdentity)(anEntry,pS))
+			return i;
+		pS+=iEntrySize;
+		}
+	return KErrNotFound;
+	}
+
+EXPORT_C TInt RArrayBase::BinarySearchSigned(const TAny* anEntry, TInt& anIndex) const
+	{
+	return BinarySearchSigned(anEntry, anIndex, EArrayFindMode_Any);
+	}
+
+EXPORT_C TInt RArrayBase::BinarySearchSigned(const TAny* anEntry, TInt& anIndex, TInt aMode) const
+	{
+	__ASSERT_DEBUG(TUint(aMode)<TUint(EArrayFindMode_Limit), Panic(EBadArrayFindMode));
+	TInt match=*(TInt*)((TUint8*)anEntry+iKeyOffset);
+	TUint8* pK=(TUint8*)iEntries+iKeyOffset;
+	TInt l=0;
+	TInt r=iCount;
+	TInt ret = KErrNotFound;
+	while(r>l)
+		{
+		TInt m=(l+r)>>1;
+		TInt h=*(TInt*)(pK+m*iEntrySize);
+		if (match==h)
+			{
+			if (aMode == EArrayFindMode_Any)
+				{
+				anIndex=m;
+				return KErrNone;
+				}
+			ret = KErrNone;
+			if (aMode == EArrayFindMode_First)
+				r=m;
+			else
+				l=m+1;
+			}
+		else if (match>h)
+			l=m+1;
+		else
+			r=m;
+		}
+	anIndex=r;
+	return ret;
+	}
+
+EXPORT_C TInt RArrayBase::BinarySearchUnsigned(const TAny* anEntry, TInt& anIndex) const
+	{
+	return BinarySearchUnsigned(anEntry, anIndex, EArrayFindMode_Any);
+	}
+
+EXPORT_C TInt RArrayBase::BinarySearchUnsigned(const TAny* anEntry, TInt& anIndex, TInt aMode) const
+	{
+	__ASSERT_DEBUG(TUint(aMode)<TUint(EArrayFindMode_Limit), Panic(EBadArrayFindMode));
+	TUint match=*(TUint*)((TUint8*)anEntry+iKeyOffset);
+	TUint8* pK=(TUint8*)iEntries+iKeyOffset;
+	TInt l=0;
+	TInt r=iCount;
+	TInt ret = KErrNotFound;
+	while(r>l)
+		{
+		TInt m=(l+r)>>1;
+		TUint h=*(TUint*)(pK+m*iEntrySize);
+		if (match==h)
+			{
+			if (aMode == EArrayFindMode_Any)
+				{
+				anIndex=m;
+				return KErrNone;
+				}
+			ret = KErrNone;
+			if (aMode == EArrayFindMode_First)
+				r=m;
+			else
+				l=m+1;
+			}
+		else if (match>h)
+			l=m+1;
+		else
+			r=m;
+		}
+	anIndex=r;
+	return ret;
+	}
+
+EXPORT_C TInt RArrayBase::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,(TUint8*)iEntries+m*iEntrySize);
+		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 RArrayBase::FindIsqSigned(const TAny* anEntry) const
+	{
+	return FindIsqSigned(anEntry, EArrayFindMode_Any);
+	}
+
+EXPORT_C TInt RArrayBase::FindIsqUnsigned(const TAny* anEntry) const
+	{
+	return FindIsqUnsigned(anEntry, EArrayFindMode_Any);
+	}
+
+EXPORT_C TInt RArrayBase::FindIsq(const TAny* anEntry, TGeneralLinearOrder anOrder) const
+	{
+	return FindIsq(anEntry, anOrder, EArrayFindMode_Any);
+	}
+
+EXPORT_C TInt RArrayBase::FindIsqSigned(const TAny* anEntry, TInt aMode) const
+	{
+	TInt i;
+	TInt r=BinarySearchSigned(anEntry,i,aMode);
+	return (r==KErrNone)?i:r;
+	}
+
+EXPORT_C TInt RArrayBase::FindIsqUnsigned(const TAny* anEntry, TInt aMode) const
+	{
+	TInt i;
+	TInt r=BinarySearchUnsigned(anEntry,i,aMode);
+	return (r==KErrNone)?i:r;
+	}
+
+EXPORT_C TInt RArrayBase::FindIsq(const TAny* anEntry, TGeneralLinearOrder anOrder, TInt aMode) const
+	{
+	TInt i;
+	TInt r=BinarySearch(anEntry,i,anOrder,aMode);
+	return (r==KErrNone)?i:r;
+	}
+#endif
+
+EXPORT_C TInt RArrayBase::FindReverse(const TAny* anEntry) const
+	{
+	TUint8 *pS=(TUint8*)iEntries+(iCount-1)*iEntrySize+iKeyOffset;
+	TInt match=*(TInt*)((TUint8*)anEntry+iKeyOffset);
+	TInt i=iCount;
+	while(i--)
+		{
+		TInt key=*(TInt*)pS;
+		if (key==match)
+			return i;
+		pS-=iEntrySize;
+		}
+	return KErrNotFound;
+	}
+
+EXPORT_C TInt RArrayBase::FindReverse(const TAny* anEntry, TGeneralIdentityRelation anIdentity) const
+	{
+	TUint8 *pS=(TUint8*)iEntries+(iCount-1)*iEntrySize;
+	TInt i=iCount;
+	while (i--)
+		{
+		if ((*anIdentity)(anEntry,pS))
+			return i;
+		pS-=iEntrySize;
+		}
+	return KErrNotFound;
+	}
+
+EXPORT_C TInt RArrayBase::InsertIsqSigned(const TAny* 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 RArrayBase::InsertIsqUnsigned(const TAny* 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 RArrayBase::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 __KERNEL_MODE__
+#ifndef __ARRAY_MACHINE_CODED__
+EXPORT_C void RArrayBase::HeapSortSigned()
+	{
+	TUint32 si[KSimpleArrayMaxEntrySize/4];
+	TInt ss = iCount;
+	if (ss>1)
+		{
+		TInt sh = ss>>1;
+		FOREVER
+			{
+			if (sh!=0)
+				{
+				--sh;
+				wordmove(si,(TUint8*)iEntries+sh*iEntrySize,iEntrySize);
+				}
+			else
+				{
+				--ss;
+				wordmove(si,(TUint8*)iEntries+ss*iEntrySize,iEntrySize);
+				wordmove((TUint8*)iEntries+ss*iEntrySize,iEntries,iEntrySize);
+				if (ss==1)
+					{
+					wordmove(iEntries,si,iEntrySize);
+					break;
+					}
+				}
+			TInt ii = sh;
+			TInt jj = sh;
+			TInt sikey=*(TInt*)((TUint8*)si+iKeyOffset);
+			FOREVER
+				{
+				jj = (jj+1)<<1;
+				TUint8* pKey=((TUint8*)iEntries+jj*iEntrySize+iKeyOffset);
+				if (jj>=ss || (*(TInt*)(pKey-iEntrySize))>*(TInt*)pKey )
+					{
+					--jj;
+					pKey-=iEntrySize;
+					}
+				if (jj>=ss || *(TInt*)pKey<=sikey)
+					break;
+				wordmove((TUint8*)iEntries+ii*iEntrySize,(TUint8*)iEntries+jj*iEntrySize,iEntrySize);
+				ii = jj;
+				}
+			wordmove((TUint8*)iEntries+ii*iEntrySize,si,iEntrySize);
+			}
+		}
+	}
+
+EXPORT_C void RArrayBase::HeapSortUnsigned()
+	{
+	TUint32 si[KSimpleArrayMaxEntrySize/4];
+	TInt ss = iCount;
+	if (ss>1)
+		{
+		TInt sh = ss>>1;
+		FOREVER
+			{
+			if (sh!=0)
+				{
+				--sh;
+				wordmove(si,(TUint8*)iEntries+sh*iEntrySize,iEntrySize);
+				}
+			else
+				{
+				--ss;
+				wordmove(si,(TUint8*)iEntries+ss*iEntrySize,iEntrySize);
+				wordmove((TUint8*)iEntries+ss*iEntrySize,iEntries,iEntrySize);
+				if (ss==1)
+					{
+					wordmove(iEntries,si,iEntrySize);
+					break;
+					}
+				}
+			TInt ii = sh;
+			TInt jj = sh;
+			TUint sikey=*(TUint*)((TUint8*)si+iKeyOffset);
+			FOREVER
+				{
+				jj = (jj+1)<<1;
+				TUint8* pKey=((TUint8*)iEntries+jj*iEntrySize+iKeyOffset);
+				if (jj>=ss || (*(TUint*)(pKey-iEntrySize))>*(TUint*)pKey )
+					{
+					--jj;
+					pKey-=iEntrySize;
+					}
+				if (jj>=ss || *(TUint*)pKey<=sikey)
+					break;
+				wordmove((TUint8*)iEntries+ii*iEntrySize,(TUint8*)iEntries+jj*iEntrySize,iEntrySize);
+				ii = jj;
+				}
+			wordmove((TUint8*)iEntries+ii*iEntrySize,si,iEntrySize);
+			}
+		}
+	}
+
+EXPORT_C void RArrayBase::HeapSort(TGeneralLinearOrder anOrder)
+	{
+	TUint32 si[KSimpleArrayMaxEntrySize/4];
+	TInt ss = iCount;
+	if (ss>1)
+		{
+		TInt sh = ss>>1;
+		FOREVER
+			{
+			if (sh!=0)
+				{
+				--sh;
+				wordmove(si,(TUint8*)iEntries+sh*iEntrySize,iEntrySize);
+				}
+			else
+				{
+				--ss;
+				wordmove(si,(TUint8*)iEntries+ss*iEntrySize,iEntrySize);
+				wordmove((TUint8*)iEntries+ss*iEntrySize,iEntries,iEntrySize);
+				if (ss==1)
+					{
+					wordmove(iEntries,si,iEntrySize);
+					break;
+					}
+				}
+			TInt ii = sh;
+			TInt jj = sh;
+			FOREVER
+				{
+				jj = (jj+1)<<1;
+				TUint8* pJJ=((TUint8*)iEntries+jj*iEntrySize);
+				if (jj>=ss || (*anOrder)(pJJ-iEntrySize,pJJ)>0)
+					{
+					--jj;
+					pJJ-=iEntrySize;
+					}
+				if (jj>=ss || (*anOrder)(pJJ,si)<=0)
+					break;
+				wordmove((TUint8*)iEntries+ii*iEntrySize,(TUint8*)iEntries+jj*iEntrySize,iEntrySize);
+				ii = jj;
+				}
+			wordmove((TUint8*)iEntries+ii*iEntrySize,si,iEntrySize);
+			}
+		}
+	}
+#endif
+
+EXPORT_C TInt RArrayBase::GetCount(const CBase* aPtr)
+	{
+	return ((RArrayBase*)aPtr)->Count();
+	}
+
+EXPORT_C const TAny* RArrayBase::GetElementPtr(const CBase* aPtr, TInt aIndex)
+	{
+	return ((RArrayBase*)aPtr)->At(aIndex);
+	}
+#endif	// __KERNEL_MODE__
+