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

     2 // All rights reserved.

     3 // This component and the accompanying materials are made available

     4 // under the terms of the License "Eclipse Public License v1.0"

     5 // which accompanies this distribution, and is available

     6 // at the URL "http://www.eclipse.org/legal/epl-v10.html".

     7 //

     8 // Initial Contributors:

     9 // Nokia Corporation - initial contribution.

    10 //

    11 // Contributors:

    12 //

    13 // Description:

    14 // e32\common\array.cpp

    15 // 

    16 //

    17 

    18 #include "common.h"

    19 #ifdef __KERNEL_MODE__

    20 #include <kernel/kernel.h>

    21 #endif

    22 

    23 const TInt KDefaultPtrArrayGranularity		=8;

    24 const TInt KPtrArrayMaxGranularity			=0x10000000;

    25 const TInt KDefaultSimpleArrayGranularity	=8;

    26 const TInt KSimpleArrayMaxGranularity		=0x10000000;

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

    28 const TInt KMaxArrayGrowBy					=65535;

    29 const TInt KMinArrayFactor					=257;

    30 const TInt KMaxArrayFactor					=32767;

    31 

    32 EXPORT_C RPointerArrayBase::RPointerArrayBase()

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

    34 	{}

    35 

    36 EXPORT_C RPointerArrayBase::RPointerArrayBase(TInt aGranularity)

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

    38 	{

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

    40 		Panic(EBadArrayGranularity));

    41 	}

    42 

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

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

    45 	{

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

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

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

    49 	}

    50 

    51 #ifndef __KERNEL_MODE__

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

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

    54 	{

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

    56 	}

    57 #endif

    58 

    59 EXPORT_C void RPointerArrayBase::Close()

    60 	{

    61 	iCount=0;

    62 	STD_CLASS::Free(iEntries);

    63 	iEntries=NULL;

    64 	iAllocated=0;

    65 	}

    66 

    67 EXPORT_C TInt RPointerArrayBase::Count() const

    68 	{

    69 	return iCount;

    70 	}

    71 

    72 #ifndef __ARRAY_MACHINE_CODED__

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

    74 	{

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

    76 	return iEntries[anIndex];

    77 	}

    78 #else

    79 GLDEF_C void PanicBadArrayIndex()

    80 	{

    81 	Panic(EBadArrayIndex);

    82 	}

    83 #endif

    84 

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

    86 	{

    87 	if (aGranularity >= 0)

    88 		{

    89 		if (aOrigSize > aLimit - aGranularity)

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

    91 		return aOrigSize + aGranularity;

    92 		}

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

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

    95 	Uint64 na64 = aOrigSize;

    96 	na64 *= (Uint64)factor;

    97 	na64 += 128;

    98 	na64 >>= 8;

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

   100 	if (min_na64 > na64)

   101 		na64 = min_na64;

   102 	if (na64 > (Uint64)aLimit)

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

   104 	return (TInt)na64;

   105 	}

   106 

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

   108 	{

   109 	TInt step = aGranularity;

   110 	if (step < 0)

   111 		step &= 65535;

   112 	if (aOrigSize - aUsed < step)

   113 		return aOrigSize;

   114 	aUsed += step - 1;

   115 	aUsed /= step;

   116 	aUsed *= step;

   117 	return aUsed;

   118 	}

   119 

   120 TInt RPointerArrayBase::Grow()

   121 	{

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

   123 	if (newAlloc < 0)

   124 		return newAlloc;

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

   126 	if (!pA)

   127 		return KErrNoMemory;

   128 	iEntries = pA;

   129 	iAllocated = newAlloc;

   130 	return KErrNone;

   131 	}

   132 

   133 #ifndef __ARRAY_MACHINE_CODED__

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

   135 	{

   136 	if (iCount==iAllocated)

   137 		{

   138 		TInt r=Grow();

   139 		if (r!=KErrNone)

   140 			return r;

   141 		}

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

   143 	return KErrNone;

   144 	}

   145 #endif

   146 

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

   148 	{

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

   150 	if (iCount==iAllocated)

   151 		{

   152 		TInt r=Grow();

   153 		if (r!=KErrNone)

   154 			return r;

   155 		}

   156 	TInt entries=iCount-aPos;

   157 	if (entries!=0)

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

   159 	iCount++;

   160 	iEntries[aPos]=(TAny*)anEntry;

   161 	return KErrNone;

   162 	}

   163 

   164 EXPORT_C void RPointerArrayBase::Remove(TInt anIndex)

   165 	{

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

   167 	TInt entries=iCount-anIndex-1;

   168 	if (entries!=0)

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

   170 	iCount--;

   171 	}

   172 

   173 EXPORT_C void RPointerArrayBase::Compress()

   174 	{

   175 	if (iCount)

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

   177 	else

   178 		{

   179 		STD_CLASS::Free(iEntries);

   180 		iEntries=NULL;

   181 		}

   182 	iAllocated=iCount;

   183 	}

   184 

   185 #ifndef __KERNEL_MODE__

   186 EXPORT_C void RPointerArrayBase::GranularCompress()

   187 	{

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

   189 	if (newAlloc == iAllocated)

   190 		return;

   191 	if (newAlloc)

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

   193 	else

   194 		{

   195 		STD_CLASS::Free(iEntries);

   196 		iEntries=NULL;

   197 		}

   198 	iAllocated=newAlloc;

   199 	}

   200 

   201 EXPORT_C TInt RPointerArrayBase::DoReserve(TInt aCount)

   202 	{

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

   204 	if (aCount <= iAllocated)

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

   206 

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

   208 	if (aCount >= KLimit)

   209 		return KErrNoMemory;

   210 

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

   212 	if (!pA)

   213 		return KErrNoMemory;

   214 	iEntries = pA;

   215 	iAllocated = aCount;

   216 	return KErrNone;

   217 	}

   218 #endif

   219 

   220 EXPORT_C void RPointerArrayBase::Reset()

   221 	{

   222 	iCount=0;

   223 	STD_CLASS::Free(iEntries);

   224 	iEntries=NULL;

   225 	iAllocated=0;

   226 	}

   227 

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

   229 	{

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

   231 	}

   232 

   233 #ifndef __ARRAY_MACHINE_CODED__

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

   235 	{

   236 	TInt i;

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

   238 		{

   239 		if (iEntries[i]==anEntry)

   240 			return i;

   241 		}

   242 	return KErrNotFound;

   243 	}

   244 

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

   246 	{

   247 	TInt i;

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

   249 		{

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

   251 			return i;

   252 		}

   253 	return KErrNotFound;

   254 	}

   255 

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

   257 	{

   258 	return BinarySearchSigned(anEntry, anIndex, EArrayFindMode_Any);

   259 	}

   260 

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

   262 	{

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

   264 	TInt l=0;

   265 	TInt r=iCount;

   266 	TInt ret = KErrNotFound;

   267 	while(r>l)

   268 		{

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

   270 		TInt h=(TInt)iEntries[m];

   271 		if (anEntry==h)

   272 			{

   273 			if (aMode == EArrayFindMode_Any)

   274 				{

   275 				anIndex=m;

   276 				return KErrNone;

   277 				}

   278 			ret = KErrNone;

   279 			if (aMode == EArrayFindMode_First)

   280 				r=m;

   281 			else

   282 				l=m+1;

   283 			}

   284 		else if (anEntry>h)

   285 			l=m+1;

   286 		else

   287 			r=m;

   288 		}

   289 	anIndex=r;

   290 	return ret;

   291 	}

   292 

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

   294 	{

   295 	return BinarySearchUnsigned(anEntry, anIndex, EArrayFindMode_Any);

   296 	}

   297 

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

   299 	{

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

   301 	TInt l=0;

   302 	TInt r=iCount;

   303 	TInt ret = KErrNotFound;

   304 	while(r>l)

   305 		{

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

   307 		TUint h=(TUint)iEntries[m];

   308 		if (anEntry==h)

   309 			{

   310 			if (aMode == EArrayFindMode_Any)

   311 				{

   312 				anIndex=m;

   313 				return KErrNone;

   314 				}

   315 			ret = KErrNone;

   316 			if (aMode == EArrayFindMode_First)

   317 				r=m;

   318 			else

   319 				l=m+1;

   320 			}

   321 		else if (anEntry>h)

   322 			l=m+1;

   323 		else

   324 			r=m;

   325 		}

   326 	anIndex=r;

   327 	return ret;

   328 	}

   329 

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

   331 	{

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

   333 	TInt l=0;

   334 	TInt r=iCount;

   335 	TInt ret = KErrNotFound;

   336 	while(r>l)

   337 		{

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

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

   340 		if (k==0)

   341 			{

   342 			if (aMode == EArrayFindMode_Any)

   343 				{

   344 				anIndex=m;

   345 				return KErrNone;

   346 				}

   347 			ret = KErrNone;

   348 			if (aMode == EArrayFindMode_First)

   349 				r=m;

   350 			else

   351 				l=m+1;

   352 			}

   353 		else if (k>0)

   354 			l=m+1;

   355 		else

   356 			r=m;

   357 		}

   358 	anIndex=r;

   359 	return ret;

   360 	}

   361 

   362 EXPORT_C TInt RPointerArrayBase::FindIsqSigned(TInt anEntry) const

   363 	{

   364 	return FindIsqSigned(anEntry, EArrayFindMode_Any);

   365 	}

   366 

   367 EXPORT_C TInt RPointerArrayBase::FindIsqUnsigned(TUint anEntry) const

   368 	{

   369 	return FindIsqUnsigned(anEntry, EArrayFindMode_Any);

   370 	}

   371 

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

   373 	{

   374 	return FindIsq(anEntry, anOrder, EArrayFindMode_Any);

   375 	}

   376 

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

   378 	{

   379 	TInt i;

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

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

   382 	}

   383 

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

   385 	{

   386 	TInt i;

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

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

   389 	}

   390 

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

   392 	{

   393 	TInt i;

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

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

   396 	}

   397 #else

   398 extern "C" void PanicBadArrayFindMode()

   399 	{

   400 	Panic(EBadArrayFindMode);

   401 	}

   402 #endif

   403 

   404 

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

   406 	{

   407 	TInt i=iCount;

   408 	while (i--)

   409 		{

   410 		if (iEntries[i]==anEntry)

   411 			return i;

   412 		}

   413 	return KErrNotFound;

   414 	}

   415 

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

   417 	{

   418 	TInt i=iCount;

   419 	while (i--)

   420 		{

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

   422 			return i;

   423 		}

   424 	return KErrNotFound;

   425 	}

   426 

   427 

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

   429 	{

   430 	TInt i;

   431 	TInt mode = aAllowRepeats ? EArrayFindMode_Last : EArrayFindMode_Any;

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

   433 	if (r==KErrNotFound || aAllowRepeats)

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

   435 	return KErrAlreadyExists;

   436 	}

   437 

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

   439 	{

   440 	TInt i;

   441 	TInt mode = aAllowRepeats ? EArrayFindMode_Last : EArrayFindMode_Any;

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

   443 	if (r==KErrNotFound || aAllowRepeats)

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

   445 	return KErrAlreadyExists;

   446 	}

   447 

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

   449 	{

   450 	TInt i;

   451 	TInt mode = aAllowRepeats ? EArrayFindMode_Last : EArrayFindMode_Any;

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

   453 	if (r==KErrNotFound || aAllowRepeats)

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

   455 	return KErrAlreadyExists;

   456 	}

   457 

   458 #ifndef __ARRAY_MACHINE_CODED__

   459 void HeapSortUnsigned(TUint* aEntries,TInt aCount)

   460 	{

   461 	TInt ss = aCount;

   462 	if (ss>1)

   463 		{

   464 		TInt sh = ss>>1;

   465 		FOREVER

   466 			{

   467 			TUint si;

   468 			if (sh!=0)

   469 				{

   470 				--sh;

   471 				si = aEntries[sh];

   472 				}

   473 			else

   474 				{

   475 				--ss;

   476 				si = aEntries[ss];

   477 				aEntries[ss]=aEntries[0];

   478 				if (ss==1)

   479 					{

   480 					aEntries[0]=si;

   481 					break;

   482 					}

   483 				}

   484 			TInt ii = sh;

   485 			TInt jj = sh;

   486 			FOREVER

   487 				{

   488 				jj = (jj+1)<<1;

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

   490 					--jj;

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

   492 					break;

   493 				aEntries[ii]=aEntries[jj];

   494 				ii = jj;

   495 				}

   496 			aEntries[ii]=si;

   497 			}

   498 		}

   499 	}

   500 #endif // !__ARRAY_MACHINE_CODED__

   501 

   502 

   503 #ifndef __KERNEL_MODE__

   504 #ifndef __ARRAY_MACHINE_CODED__

   505 EXPORT_C void RPointerArrayBase::HeapSortSigned()

   506 	{

   507 	TInt ss = iCount;

   508 	if (ss>1)

   509 		{

   510 		TInt sh = ss>>1;

   511 		FOREVER

   512 			{

   513 			TInt si;

   514 			if (sh!=0)

   515 				{

   516 				--sh;

   517 				si = (TInt)iEntries[sh];

   518 				}

   519 			else

   520 				{

   521 				--ss;

   522 				si = (TInt)iEntries[ss];

   523 				iEntries[ss]=iEntries[0];

   524 				if (ss==1)

   525 					{

   526 					iEntries[0]=(TAny*)si;

   527 					break;

   528 					}

   529 				}

   530 			TInt ii = sh;

   531 			TInt jj = sh;

   532 			FOREVER

   533 				{

   534 				jj = (jj+1)<<1;

   535 				if (jj>=ss || TInt(iEntries[jj-1])>TInt(iEntries[jj]) )

   536 					--jj;

   537 				if (jj>=ss || TInt(iEntries[jj])<=si)

   538 					break;

   539 				iEntries[ii]=iEntries[jj];

   540 				ii = jj;

   541 				}

   542 			iEntries[ii]=(TAny*)si;

   543 			}

   544 		}

   545 	}

   546 

   547 EXPORT_C void RPointerArrayBase::HeapSortUnsigned()

   548 	{

   549 	::HeapSortUnsigned((TUint*)iEntries,iCount);

   550 	}

   551 

   552 EXPORT_C void RPointerArrayBase::HeapSort(TGeneralLinearOrder anOrder)

   553 	{

   554 	TInt ss = iCount;

   555 	if (ss>1)

   556 		{

   557 		TInt sh = ss>>1;

   558 		FOREVER

   559 			{

   560 			TAny* si;

   561 			if (sh!=0)

   562 				{

   563 				--sh;

   564 				si = iEntries[sh];

   565 				}

   566 			else

   567 				{

   568 				--ss;

   569 				si = iEntries[ss];

   570 				iEntries[ss]=iEntries[0];

   571 				if (ss==1)

   572 					{

   573 					iEntries[0]=si;

   574 					break;

   575 					}

   576 				}

   577 			TInt ii = sh;

   578 			TInt jj = sh;

   579 			FOREVER

   580 				{

   581 				jj = (jj+1)<<1;

   582 				if (jj>=ss || (*anOrder)(iEntries[jj-1],iEntries[jj])>0 )

   583 					--jj;

   584 				if (jj>=ss || (*anOrder)(iEntries[jj],si)<=0 )

   585 					break;

   586 				iEntries[ii]=iEntries[jj];

   587 				ii = jj;

   588 				}

   589 			iEntries[ii]=si;

   590 			}

   591 		}

   592 	}

   593 #endif

   594 

   595 EXPORT_C TInt RPointerArrayBase::GetCount(const CBase* aPtr)

   596 	{

   597 	return ((RPointerArrayBase*)aPtr)->Count();

   598 	}

   599 

   600 EXPORT_C const TAny* RPointerArrayBase::GetElementPtr(const CBase* aPtr, TInt aIndex)

   601 	{

   602 	return &(((RPointerArrayBase*)aPtr)->At(aIndex));

   603 	}

   604 #endif	// __KERNEL_MODE__

   605 

   606 EXPORT_C RArrayBase::RArrayBase(TInt anEntrySize)

   607 	:	iCount(0), iEntries(NULL), iKeyOffset(0), iAllocated(0),

   608 		iGranularity(KDefaultSimpleArrayGranularity), iSpare1(0), iSpare2(0)

   609 	{

   610 	__ASSERT_ALWAYS(anEntrySize>0 && anEntrySize<=KSimpleArrayMaxEntrySize,Panic(EBadArrayEntrySize));

   611 	iEntrySize=(anEntrySize+(TInt)sizeof(TInt)-1)&~((TInt)sizeof(TInt)-1);

   612 	}

   613 

   614 EXPORT_C RArrayBase::RArrayBase(TInt anEntrySize, TInt aGranularity)

   615 	:	iCount(0), iEntries(NULL), iKeyOffset(0), iAllocated(0),

   616 		iGranularity(aGranularity), iSpare1(0), iSpare2(0)

   617 	{

   618 	__ASSERT_ALWAYS(anEntrySize>0 && anEntrySize<=KSimpleArrayMaxEntrySize,Panic(EBadArrayEntrySize));

   619 	__ASSERT_ALWAYS(aGranularity>0 && (aGranularity*anEntrySize)<=KSimpleArrayMaxGranularity, Panic(EBadArrayGranularity));

   620 	iEntrySize=(anEntrySize+(TInt)sizeof(TInt)-1)&~((TInt)sizeof(TInt)-1);

   621 	}

   622 

   623 EXPORT_C RArrayBase::RArrayBase(TInt aEntrySize,TAny* aEntries, TInt aCount)

   624 	:	iCount(aCount), iEntries(aEntries), iKeyOffset(0), iAllocated(aCount),

   625 		iGranularity(KDefaultSimpleArrayGranularity), iSpare1(0), iSpare2(0)

   626 	{

   627 	__ASSERT_ALWAYS(aEntrySize>0 && aEntrySize<=KSimpleArrayMaxEntrySize,Panic(EBadArrayEntrySize));

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

   629 	iEntrySize=(aEntrySize+(TInt)sizeof(TInt)-1)&~((TInt)sizeof(TInt)-1);

   630 	}

   631 

   632 EXPORT_C RArrayBase::RArrayBase(TInt anEntrySize, TInt aGranularity, TInt aKeyOffset)

   633 	:	 iCount(0), iEntries(NULL), iKeyOffset(aKeyOffset), iAllocated(0),

   634 		iGranularity(aGranularity), iSpare1(0), iSpare2(0)

   635 	{

   636 	__ASSERT_ALWAYS(anEntrySize>0 && anEntrySize<=KSimpleArrayMaxEntrySize,Panic(EBadArrayEntrySize));

   637 	__ASSERT_ALWAYS(aGranularity>0 && (aGranularity*anEntrySize)<=KSimpleArrayMaxGranularity, Panic(EBadArrayGranularity));

   638 	__ASSERT_ALWAYS(aKeyOffset>=0 && (aKeyOffset&3)==0 && aKeyOffset<anEntrySize, Panic(EBadArrayKeyOffset));

   639 	iEntrySize=(anEntrySize+(TInt)sizeof(TInt)-1)&~((TInt)sizeof(TInt)-1);

   640 	}

   641 

   642 EXPORT_C RArrayBase::RArrayBase(TInt aEntrySize, TInt aMinGrowBy, TInt aKeyOffset, TInt aFactor)

   643 	:	 iCount(0), iEntries(NULL), iKeyOffset(aKeyOffset), iAllocated(0), iSpare1(0), iSpare2(0)

   644 	{

   645 	__ASSERT_ALWAYS(aEntrySize>0 && aEntrySize<=KSimpleArrayMaxEntrySize, Panic(EBadArrayEntrySize));

   646 	__ASSERT_ALWAYS(aKeyOffset>=0 && (aKeyOffset&3)==0 && aKeyOffset<aEntrySize, Panic(EBadArrayKeyOffset));

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

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

   649 	iEntrySize=(aEntrySize+(TInt)sizeof(TInt)-1)&~((TInt)sizeof(TInt)-1);

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

   651 	}

   652 

   653 EXPORT_C void RArrayBase::Close()

   654 	{

   655 	iCount=0;

   656 	STD_CLASS::Free(iEntries);

   657 	iEntries=NULL;

   658 	iAllocated=0;

   659 	}

   660 

   661 EXPORT_C TInt RArrayBase::Count() const

   662 	{

   663 	return iCount;

   664 	}

   665 

   666 #ifndef __ARRAY_MACHINE_CODED__

   667 EXPORT_C TAny* RArrayBase::At(TInt anIndex) const

   668 	{

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

   670 	return (((TUint8*)iEntries)+anIndex*iEntrySize);

   671 	}

   672 #endif

   673 

   674 TInt RArrayBase::Grow()

   675 	{

   676 	TInt newAlloc = CalculateArraySizeAfterGrow(iAllocated, iGranularity, KMaxTInt/iEntrySize);

   677 	if (newAlloc < 0)

   678 		return newAlloc;

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

   680 	if (!pA)

   681 		return KErrNoMemory;

   682 	iEntries = pA;

   683 	iAllocated = newAlloc;

   684 	return KErrNone;

   685 	}

   686 

   687 #ifndef __ARRAY_MACHINE_CODED__

   688 EXPORT_C TInt RArrayBase::Append(const TAny* anEntry)

   689 	{

   690 	if (iCount==iAllocated)

   691 		{

   692 		TInt r=Grow();

   693 		if (r!=KErrNone)

   694 			return r;

   695 		}

   696 	wordmove((TUint8*)iEntries+iCount*iEntrySize, anEntry, iEntrySize);

   697 	iCount++;

   698 	return KErrNone;

   699 	}

   700 #endif

   701 

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

   703 	{

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

   705 	if (iCount==iAllocated)

   706 		{

   707 		TInt r=Grow();

   708 		if (r!=KErrNone)

   709 			return r;

   710 		}

   711 	TUint8 *pS=(TUint8*)iEntries+aPos*iEntrySize;

   712 	TUint8 *pD=pS+iEntrySize;

   713 	TInt entries=iCount-aPos;

   714 	if (entries!=0)

   715 		wordmove(pD,pS,entries*iEntrySize);

   716 	wordmove(pS,anEntry,iEntrySize);

   717 	iCount++;

   718 	return KErrNone;

   719 	}

   720 

   721 EXPORT_C void RArrayBase::Remove(TInt anIndex)

   722 	{

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

   724 	TUint8 *pD=(TUint8*)iEntries+anIndex*iEntrySize;

   725 	TUint8 *pS=pD+iEntrySize;

   726 	TInt entries=iCount-anIndex-1;

   727 	if (entries!=0)

   728 		wordmove(pD,pS,entries*iEntrySize);

   729 	iCount--;

   730 	}

   731 

   732 EXPORT_C void RArrayBase::Compress()

   733 	{

   734 	if (iCount)

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

   736 	else

   737 		{

   738 		STD_CLASS::Free(iEntries);

   739 		iEntries=NULL;

   740 		}

   741 	iAllocated=iCount;

   742 	}

   743 

   744 #ifndef __KERNEL_MODE__

   745 EXPORT_C void RArrayBase::GranularCompress()

   746 	{

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

   748 	if (newAlloc == iAllocated)

   749 		return;

   750 	if (newAlloc)

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

   752 	else

   753 		{

   754 		STD_CLASS::Free(iEntries);

   755 		iEntries=NULL;

   756 		}

   757 	iAllocated=newAlloc;

   758 	}

   759 

   760 EXPORT_C TInt RArrayBase::DoReserve(TInt aCount)

   761 	{

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

   763 	if (aCount <= iAllocated)

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

   765 

   766 	Int64 size = Int64(aCount) * Int64(iEntrySize);

   767 	if (size > Int64(KMaxTInt))

   768 		return KErrNoMemory;

   769 

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

   771 	if (!pA)

   772 		return KErrNoMemory;

   773 	iEntries = pA;

   774 	iAllocated = aCount;

   775 	return KErrNone;

   776 	}

   777 #endif

   778 

   779 EXPORT_C void RArrayBase::Reset()

   780 	{

   781 	iCount=0;

   782 	STD_CLASS::Free(iEntries);

   783 	iEntries=NULL;

   784 	iAllocated=0;

   785 	}

   786 

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

   788 	{

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

   790 	}

   791 

   792 #ifndef __ARRAY_MACHINE_CODED__

   793 EXPORT_C TInt RArrayBase::Find(const TAny* anEntry) const

   794 	{

   795 	TUint8 *pS=(TUint8*)iEntries+iKeyOffset;

   796 	TInt match=*(TInt*)((TUint8*)anEntry+iKeyOffset);

   797 	TInt i;

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

   799 		{

   800 		TInt key=*(TInt*)pS;

   801 		if (key==match)

   802 			return i;

   803 		pS+=iEntrySize;

   804 		}

   805 	return KErrNotFound;

   806 	}

   807 

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

   809 	{

   810 	TUint8 *pS=(TUint8*)iEntries;

   811 	TInt i;

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

   813 		{

   814 		if ((*anIdentity)(anEntry,pS))

   815 			return i;

   816 		pS+=iEntrySize;

   817 		}

   818 	return KErrNotFound;

   819 	}

   820 

   821 EXPORT_C TInt RArrayBase::BinarySearchSigned(const TAny* anEntry, TInt& anIndex) const

   822 	{

   823 	return BinarySearchSigned(anEntry, anIndex, EArrayFindMode_Any);

   824 	}

   825 

   826 EXPORT_C TInt RArrayBase::BinarySearchSigned(const TAny* anEntry, TInt& anIndex, TInt aMode) const

   827 	{

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

   829 	TInt match=*(TInt*)((TUint8*)anEntry+iKeyOffset);

   830 	TUint8* pK=(TUint8*)iEntries+iKeyOffset;

   831 	TInt l=0;

   832 	TInt r=iCount;

   833 	TInt ret = KErrNotFound;

   834 	while(r>l)

   835 		{

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

   837 		TInt h=*(TInt*)(pK+m*iEntrySize);

   838 		if (match==h)

   839 			{

   840 			if (aMode == EArrayFindMode_Any)

   841 				{

   842 				anIndex=m;

   843 				return KErrNone;

   844 				}

   845 			ret = KErrNone;

   846 			if (aMode == EArrayFindMode_First)

   847 				r=m;

   848 			else

   849 				l=m+1;

   850 			}

   851 		else if (match>h)

   852 			l=m+1;

   853 		else

   854 			r=m;

   855 		}

   856 	anIndex=r;

   857 	return ret;

   858 	}

   859 

   860 EXPORT_C TInt RArrayBase::BinarySearchUnsigned(const TAny* anEntry, TInt& anIndex) const

   861 	{

   862 	return BinarySearchUnsigned(anEntry, anIndex, EArrayFindMode_Any);

   863 	}

   864 

   865 EXPORT_C TInt RArrayBase::BinarySearchUnsigned(const TAny* anEntry, TInt& anIndex, TInt aMode) const

   866 	{

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

   868 	TUint match=*(TUint*)((TUint8*)anEntry+iKeyOffset);

   869 	TUint8* pK=(TUint8*)iEntries+iKeyOffset;

   870 	TInt l=0;

   871 	TInt r=iCount;

   872 	TInt ret = KErrNotFound;

   873 	while(r>l)

   874 		{

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

   876 		TUint h=*(TUint*)(pK+m*iEntrySize);

   877 		if (match==h)

   878 			{

   879 			if (aMode == EArrayFindMode_Any)

   880 				{

   881 				anIndex=m;

   882 				return KErrNone;

   883 				}

   884 			ret = KErrNone;

   885 			if (aMode == EArrayFindMode_First)

   886 				r=m;

   887 			else

   888 				l=m+1;

   889 			}

   890 		else if (match>h)

   891 			l=m+1;

   892 		else

   893 			r=m;

   894 		}

   895 	anIndex=r;

   896 	return ret;

   897 	}

   898 

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

   900 	{

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

   902 	TInt l=0;

   903 	TInt r=iCount;

   904 	TInt ret = KErrNotFound;

   905 	while(r>l)

   906 		{

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

   908 		TInt k=(*anOrder)(anEntry,(TUint8*)iEntries+m*iEntrySize);

   909 		if (k==0)

   910 			{

   911 			if (aMode == EArrayFindMode_Any)

   912 				{

   913 				anIndex=m;

   914 				return KErrNone;

   915 				}

   916 			ret = KErrNone;

   917 			if (aMode == EArrayFindMode_First)

   918 				r=m;

   919 			else

   920 				l=m+1;

   921 			}

   922 		else if (k>0)

   923 			l=m+1;

   924 		else

   925 			r=m;

   926 		}

   927 	anIndex=r;

   928 	return ret;

   929 	}

   930 

   931 EXPORT_C TInt RArrayBase::FindIsqSigned(const TAny* anEntry) const

   932 	{

   933 	return FindIsqSigned(anEntry, EArrayFindMode_Any);

   934 	}

   935 

   936 EXPORT_C TInt RArrayBase::FindIsqUnsigned(const TAny* anEntry) const

   937 	{

   938 	return FindIsqUnsigned(anEntry, EArrayFindMode_Any);

   939 	}

   940 

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

   942 	{

   943 	return FindIsq(anEntry, anOrder, EArrayFindMode_Any);

   944 	}

   945 

   946 EXPORT_C TInt RArrayBase::FindIsqSigned(const TAny* anEntry, TInt aMode) const

   947 	{

   948 	TInt i;

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

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

   951 	}

   952 

   953 EXPORT_C TInt RArrayBase::FindIsqUnsigned(const TAny* anEntry, TInt aMode) const

   954 	{

   955 	TInt i;

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

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

   958 	}

   959 

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

   961 	{

   962 	TInt i;

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

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

   965 	}

   966 #endif

   967 

   968 EXPORT_C TInt RArrayBase::FindReverse(const TAny* anEntry) const

   969 	{

   970 	TUint8 *pS=(TUint8*)iEntries+(iCount-1)*iEntrySize+iKeyOffset;

   971 	TInt match=*(TInt*)((TUint8*)anEntry+iKeyOffset);

   972 	TInt i=iCount;

   973 	while(i--)

   974 		{

   975 		TInt key=*(TInt*)pS;

   976 		if (key==match)

   977 			return i;

   978 		pS-=iEntrySize;

   979 		}

   980 	return KErrNotFound;

   981 	}

   982 

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

   984 	{

   985 	TUint8 *pS=(TUint8*)iEntries+(iCount-1)*iEntrySize;

   986 	TInt i=iCount;

   987 	while (i--)

   988 		{

   989 		if ((*anIdentity)(anEntry,pS))

   990 			return i;

   991 		pS-=iEntrySize;

   992 		}

   993 	return KErrNotFound;

   994 	}

   995 

   996 EXPORT_C TInt RArrayBase::InsertIsqSigned(const TAny* anEntry, TBool aAllowRepeats)

   997 	{

   998 	TInt i;

   999 	TInt mode = aAllowRepeats ? EArrayFindMode_Last : EArrayFindMode_Any;

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

  1001 	if (r==KErrNotFound || aAllowRepeats)

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

  1003 	return KErrAlreadyExists;

  1004 	}

  1005 

  1006 EXPORT_C TInt RArrayBase::InsertIsqUnsigned(const TAny* anEntry, TBool aAllowRepeats)

  1007 	{

  1008 	TInt i;

  1009 	TInt mode = aAllowRepeats ? EArrayFindMode_Last : EArrayFindMode_Any;

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

  1011 	if (r==KErrNotFound || aAllowRepeats)

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

  1013 	return KErrAlreadyExists;

  1014 	}

  1015 

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

  1017 	{

  1018 	TInt i;

  1019 	TInt mode = aAllowRepeats ? EArrayFindMode_Last : EArrayFindMode_Any;

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

  1021 	if (r==KErrNotFound || aAllowRepeats)

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

  1023 	return KErrAlreadyExists;

  1024 	}

  1025 

  1026 #ifndef __KERNEL_MODE__

  1027 #ifndef __ARRAY_MACHINE_CODED__

  1028 EXPORT_C void RArrayBase::HeapSortSigned()

  1029 	{

  1030 	TUint32 si[KSimpleArrayMaxEntrySize/4];

  1031 	TInt ss = iCount;

  1032 	if (ss>1)

  1033 		{

  1034 		TInt sh = ss>>1;

  1035 		FOREVER

  1036 			{

  1037 			if (sh!=0)

  1038 				{

  1039 				--sh;

  1040 				wordmove(si,(TUint8*)iEntries+sh*iEntrySize,iEntrySize);

  1041 				}

  1042 			else

  1043 				{

  1044 				--ss;

  1045 				wordmove(si,(TUint8*)iEntries+ss*iEntrySize,iEntrySize);

  1046 				wordmove((TUint8*)iEntries+ss*iEntrySize,iEntries,iEntrySize);

  1047 				if (ss==1)

  1048 					{

  1049 					wordmove(iEntries,si,iEntrySize);

  1050 					break;

  1051 					}

  1052 				}

  1053 			TInt ii = sh;

  1054 			TInt jj = sh;

  1055 			TInt sikey=*(TInt*)((TUint8*)si+iKeyOffset);

  1056 			FOREVER

  1057 				{

  1058 				jj = (jj+1)<<1;

  1059 				TUint8* pKey=((TUint8*)iEntries+jj*iEntrySize+iKeyOffset);

  1060 				if (jj>=ss || (*(TInt*)(pKey-iEntrySize))>*(TInt*)pKey )

  1061 					{

  1062 					--jj;

  1063 					pKey-=iEntrySize;

  1064 					}

  1065 				if (jj>=ss || *(TInt*)pKey<=sikey)

  1066 					break;

  1067 				wordmove((TUint8*)iEntries+ii*iEntrySize,(TUint8*)iEntries+jj*iEntrySize,iEntrySize);

  1068 				ii = jj;

  1069 				}

  1070 			wordmove((TUint8*)iEntries+ii*iEntrySize,si,iEntrySize);

  1071 			}

  1072 		}

  1073 	}

  1074 

  1075 EXPORT_C void RArrayBase::HeapSortUnsigned()

  1076 	{

  1077 	TUint32 si[KSimpleArrayMaxEntrySize/4];

  1078 	TInt ss = iCount;

  1079 	if (ss>1)

  1080 		{

  1081 		TInt sh = ss>>1;

  1082 		FOREVER

  1083 			{

  1084 			if (sh!=0)

  1085 				{

  1086 				--sh;

  1087 				wordmove(si,(TUint8*)iEntries+sh*iEntrySize,iEntrySize);

  1088 				}

  1089 			else

  1090 				{

  1091 				--ss;

  1092 				wordmove(si,(TUint8*)iEntries+ss*iEntrySize,iEntrySize);

  1093 				wordmove((TUint8*)iEntries+ss*iEntrySize,iEntries,iEntrySize);

  1094 				if (ss==1)

  1095 					{

  1096 					wordmove(iEntries,si,iEntrySize);

  1097 					break;

  1098 					}

  1099 				}

  1100 			TInt ii = sh;

  1101 			TInt jj = sh;

  1102 			TUint sikey=*(TUint*)((TUint8*)si+iKeyOffset);

  1103 			FOREVER

  1104 				{

  1105 				jj = (jj+1)<<1;

  1106 				TUint8* pKey=((TUint8*)iEntries+jj*iEntrySize+iKeyOffset);

  1107 				if (jj>=ss || (*(TUint*)(pKey-iEntrySize))>*(TUint*)pKey )

  1108 					{

  1109 					--jj;

  1110 					pKey-=iEntrySize;

  1111 					}

  1112 				if (jj>=ss || *(TUint*)pKey<=sikey)

  1113 					break;

  1114 				wordmove((TUint8*)iEntries+ii*iEntrySize,(TUint8*)iEntries+jj*iEntrySize,iEntrySize);

  1115 				ii = jj;

  1116 				}

  1117 			wordmove((TUint8*)iEntries+ii*iEntrySize,si,iEntrySize);

  1118 			}

  1119 		}

  1120 	}

  1121 

  1122 EXPORT_C void RArrayBase::HeapSort(TGeneralLinearOrder anOrder)

  1123 	{

  1124 	TUint32 si[KSimpleArrayMaxEntrySize/4];

  1125 	TInt ss = iCount;

  1126 	if (ss>1)

  1127 		{

  1128 		TInt sh = ss>>1;

  1129 		FOREVER

  1130 			{

  1131 			if (sh!=0)

  1132 				{

  1133 				--sh;

  1134 				wordmove(si,(TUint8*)iEntries+sh*iEntrySize,iEntrySize);