// 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

	}