diff -r c55016431358 -r 0a7b44b10206 symport/e32/common/array.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/symport/e32/common/array.cpp Thu Jun 25 15:59:54 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 "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 +#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= 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=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; il) + { + 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)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)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 && aKeyOffset0 && aEntrySize<=KSimpleArrayMaxEntrySize, Panic(EBadArrayEntrySize)); + __ASSERT_ALWAYS(aKeyOffset>=0 && (aKeyOffset&3)==0 && aKeyOffset0 && 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=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=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; il) + { + 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)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)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__ +