// Copyright (c) 2007-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:

 //

 #include <kernel/kern_priv.h>

 #include "maddrcont.h"

 RAddressedContainer::RAddressedContainer(NFastMutex* aReadLock, DMutex*& aWriteLock)

 	: iMaxCount(0), iCount(0), iList(0), iReadLock(aReadLock), iWriteLock(aWriteLock)

 	{}

 RAddressedContainer::~RAddressedContainer()

 	{

 	Kern::Free(iList);

 	}

 const TUint MinCount = 8; // must be power of two

 FORCE_INLINE TUint RAddressedContainer::CalculateGrow()

 	{

 	TUint newMax = iMaxCount;

 	if(newMax<MinCount)

 		newMax = MinCount;

 	else

 		newMax <<= 1;

 	return newMax;

 	}

 TUint RAddressedContainer::CalculateShrink(TUint aCount)

 	{

 	TUint newMax = iMaxCount;

 	if(!aCount)

 		return 0; // empty container should have zero max size

 #ifndef _DEBUG

 	// we want at least 'MinCount' free slots after shrinking for hysteresis,

 	// but not in UDEB builds because OOM testing will barf...

 	aCount += MinCount;

 #endif

 	TUint tryMax = newMax;

 	do

 		{

 		newMax = tryMax;

 		tryMax >>= 1;

 		}

 	while(tryMax>=aCount);

 	if(newMax<MinCount)

 		newMax = MinCount;

 	return newMax;

 	}

 TBool RAddressedContainer::CheckWriteLock()

 	{

 	if(K::Initialising)

 		return true; // check disabled during boot as we are single threaded at that point

 	if(!iWriteLock)

 		return false;

 	if((((TLinAddr)iWriteLock)&1))

 		return true; // its a lock from DMutexPool, we can't check that, assume it's OK

 	return iWriteLock->iCleanup.iThread==&Kern::CurrentThread();

 	}

 #ifdef _DEBUG

 const TUint KMaxEntriesInOneGo = 4; // small number to improve test coverage

 #else

 const TUint KMaxEntriesInOneGo = 32; // to produce a similar worst case number of cache line accesses to the binary search

 #endif

 TInt RAddressedContainer::Add(TLinAddr aAddress, TAny* aObject)

 	{

 	__NK_ASSERT_DEBUG(aObject);

 	__ASSERT_CRITICAL;

 	__NK_ASSERT_DEBUG(CheckWriteLock());

 #ifdef _DEBUG

 	if(K::CheckForSimulatedAllocFail())

 		{

 		__KTRACE_OPT(KMMU,Kern::Printf("RAddressedContainer::Add returns simulated OOM %d",KErrNoMemory));

 		return KErrNoMemory;

 		}

 #endif

 	// find list insertion point...

 	TUint i = FindIndex(aAddress);

 	if(iCount<iMaxCount)

 		{

 		// insert new entry...

 		ReadLock();

 		// make room by shuffling entries up in the array KMaxEntriesInOneGo at a time...

 		TEntry* entry = iList+i;

 		TEntry* prev = iList+iCount;

 		++iCount; // must do this before releasing read lock for the first time

 		for(;;)

 			{

 			TEntry* next = prev-KMaxEntriesInOneGo;

 			if(next<=entry)

 				{

 				// move the final remaining entries...

 				wordmove(entry+1,entry,(TUintPtr)prev-(TUintPtr)entry);

 				break;

 				}

 			wordmove(next+1,next,(TUintPtr)prev-(TUintPtr)next);

 			prev = next;

 			// flash the read lock to give readers a chance to look at the list...

 			ReadFlash();

 			// Note, readers may see a duplicate entry in the list at 'prev' but this

 			// is OK as the Find functions will still work.

 			}

 		// copy in new entry...

 		entry->iAddress = aAddress;

 		entry->iObject = aObject;

 		ReadUnlock();

 		}

 	else

 		{

 		// list memory needs expanding...

 		TUint newMaxCount = CalculateGrow();

 		// allocate new memory...

 		TEntry* newList = (TEntry*)Kern::Alloc(sizeof(TEntry)*newMaxCount);

 		if(!newList)

 			return KErrNoMemory;

 		#ifdef _DEBUG

 			if(iList)

 				K::Allocator->DebugFunction(RAllocator::ECopyDebugInfo, iList, newList);

 		#endif

 		iMaxCount = newMaxCount;

 		// copy list to new memory, and insert new entry...

 		wordmove(newList,iList,sizeof(TEntry)*i);

 		TEntry* entry = newList+i;

 		entry->iAddress = aAddress;

 		entry->iObject = aObject;

 		wordmove(entry+1,iList+i,sizeof(TEntry)*(iCount-i));

 		// start using new list...

 		TEntry* oldList = iList;

 		ReadLock();

 		iList = newList;

 		++iCount;

 		ReadUnlock();

 		// free memory used for old list...

 		Kern::Free(oldList);

 		}

 	return KErrNone;

 	}

 TAny* RAddressedContainer::Remove(TLinAddr aAddress)

 	{

 	__ASSERT_CRITICAL;

 	__NK_ASSERT_DEBUG(CheckWriteLock());

 	// search for it...

 	TUint i = FindIndex(aAddress);

 	TEntry* entry = iList+i-1;

 	if(!i || entry->iAddress!=aAddress)

 		{

 		// not found...

 		return 0;

 		}

 	--i; // make 'i' the index of entry to remove

 	// get object...

 	TAny* result = entry->iObject;

 	__NK_ASSERT_DEBUG(result);

 	TUint newMaxCount = CalculateShrink(iCount-1);

 	if(newMaxCount>=iMaxCount)

 		{

 remove_without_resize:

 		// remove old entry...

 		ReadLock();

 		// shuffling entries down in the array KMaxEntriesInOneGo at a time...

 		TEntry* prev = iList+i+1;

 		TEntry* end = iList+iCount;

 		for(;;)

 			{

 			TEntry* next = prev+KMaxEntriesInOneGo;

 			if(next>=end)

 				{

 				// move the final remaining entries...

 				wordmove(prev-1,prev,(TUintPtr)end-(TUintPtr)prev);

 				break;

 				}

 			wordmove(prev-1,prev,(TUintPtr)next-(TUintPtr)prev);

 			prev = next;

 			// flash the read lock to give readers a chance to look at the list...

 			ReadFlash();

 			// Note, readers may see a duplicate entry at the end of the list but this

 			// is OK as the Find functions will still work.

 			}

 		--iCount; // must do this after moving all the entries

 		ReadUnlock();		

 		}

 	else

 		{

 		// list memory needs shrinking...

 		// allocate new memory...

 		TEntry* newList = 0;

 		if(newMaxCount)

 			{

 			newList = (TEntry*)Kern::Alloc(sizeof(TEntry)*newMaxCount);

 			if(!newList)

 				goto remove_without_resize; // have no memory to shrink array

 			#ifdef _DEBUG

 				if(iList)

 					K::Allocator->DebugFunction(RAllocator::ECopyDebugInfo, iList, newList);

 			#endif

 			}

 		iMaxCount = newMaxCount;

 		// copy list to new memory, deleting removed entry...

 		wordmove(newList,iList,sizeof(TEntry)*i);

 		wordmove(newList+i,iList+i+1,sizeof(TEntry)*(iCount-i-1));

 		// start using new list...

 		TEntry* oldList = iList;

 		ReadLock();

 		iList = newList;

 		--iCount;

 		ReadUnlock();

 		// free memory used for old list...

 		Kern::Free(oldList);

 		}

 	return result;

 	}

 TAny* RAddressedContainer::Find(TLinAddr aAddress)

 	{

 	if(iReadLock)

 		__NK_ASSERT_DEBUG(iReadLock->HeldByCurrentThread());

 	else

 		__NK_ASSERT_DEBUG(CheckWriteLock());

 	TUint i = FindIndex(aAddress);

 	TEntry* entry = iList+i;

 	if(i==0)

 		return 0;

 	--entry;

 	if(aAddress!=entry->iAddress)

 		return 0;

 	TAny* result = entry->iObject;

 	__NK_ASSERT_DEBUG(result);

 	return result;

 	}

 TAny* RAddressedContainer::Find(TLinAddr aAddress, TUint& aOffset)

 	{

 	if(iReadLock)

 		__NK_ASSERT_DEBUG(iReadLock->HeldByCurrentThread());

 	else

 		__NK_ASSERT_DEBUG(CheckWriteLock());

 	TUint i = FindIndex(aAddress);

 	TEntry* entry = iList+i;

 	if(i==0)

 		return 0;

 	--entry;

 	aOffset = aAddress-entry->iAddress;

 	TAny* result = entry->iObject;

 	__NK_ASSERT_DEBUG(result);

 	return result;

 	}

 TUint RAddressedContainer::FindIndex(TLinAddr aAddress)

 	{

 	TEntry* list = iList;

 #if 0

 	// linear search from end...

 	TUint count = iCount;

 	while(count)

 		{

 		if(list[count-1].iAddress<=aAddress)

 			break;

 		--count;

 		}

 	return count;

 #else

 	// binary search...

 	TUint l = 0;

 	TUint r = iCount;

 	TUint m;

 	while(l<r)

 		{

 		m = (l+r)>>1;

 		TUint32 x = list[m].iAddress;

 		if(x<=aAddress)

 			l = m+1;

 		else

 			r = m;

 		}

 	return r;

 #endif

 	}