// Copyright (c) 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\kernel\smap.cpp

#include <kernel/kern_priv.h>
#include "smap.h"


/**
   SMap uses a binary search to perform quick lookups (finds) whilst Add and
   Remove and Iterating is happening concurrently. This container is optimised
   for fast lookups.

   Add, Remove and Iterator check that the caller has the heavyweight (slow) mutex lock
   held.

   Find methods take the fast lock whilst performing look ups.
 */

SMap::SMap(NFastMutex* aFastLock, DMutex* aSlowLock)
	:  iCount(0), iList(0), iFastLock(aFastLock), iSlowLock(aSlowLock)
	{}

SMap::~SMap()
	{
	Kern::Free(iList);
	}

/**
	Add checks that the caller has the heavyweight mutex held, determines the
	entry point in the array for the new entry and performs a copy and swap
	with a newly-allocated array.
*/
TInt SMap::Add(TUint aKey, TAny* aObject)
	{
	__NK_ASSERT_DEBUG(aObject);
	__ASSERT_MUTEX(iSlowLock);

	__ASSERT_CRITICAL;

#ifdef _DEBUG
	if (K::CheckForSimulatedAllocFail())
		{
		__KTRACE_OPT(KMMU,Kern::Printf("SMap::Add returns simulated OOM %d",KErrNoMemory));
		return KErrNoMemory;
		}
#endif
	TEntry* newlist = (TEntry*)Kern::Alloc(sizeof(TEntry)*(iCount + 1));

	if (!newlist)
		return KErrNoMemory;

	// find list insertion point...
	TUint i = FindIndex(aKey);
	TEntry* entry = newlist + i;

	// make room...
	if (i)
		{
		TUint moveSize = i * sizeof(TEntry);
		wordmove(newlist, iList, moveSize);
		}

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

#ifdef _DEBUG
	if (iList)
		K::Allocator->DebugFunction(RAllocator::ECopyDebugInfo, iList, newlist);
#endif

	// copy in new entry...
	entry->iKey = aKey;
	entry->iObj = aObject;
	TEntry* cleanup = iList;

	FastLock();
	// swap
	++iCount;
	iList = newlist;
	FastUnlock();

	Kern::Free(cleanup);
	return KErrNone;
	}

/**
   Remove checks that the caller has the heavyweight mutex held, determines the
   entry point in the array for the entry to be removed. It shuffles the entries
   left flashing the fast lock so as not to prevent 'finds' from being blocked.
*/
TAny* SMap::Remove(TUint aKey)
	{
	__ASSERT_CRITICAL;
	__ASSERT_MUTEX(iSlowLock);

	// search for it...
	TUint i = FindIndex(aKey);
	TEntry* entry = iList + i - 1;

	if (!i || entry->iKey != aKey)
		{
		// not found...
		return NULL;
		}

	// get objects...
	TAny* result = entry->iObj;
	__NK_ASSERT_DEBUG(result);

	FastLock();
	if (iCount > 1)
		{
		// the shuffle the entries a maximum of 4 at a time
		// in the existing memory flashing the lock, so as not to hold it too
		// long
		// Note Add and Remove cannot be performed while shuffling the
		// entries, but fast lookups can
		while (i < iCount)
			{
			TInt entries = Min((TInt)(iCount - i), 4);
			wordmove(&iList[i-1], &iList[i], entries * sizeof(TEntry));
			i += entries;
			NKern::FMFlash(iFastLock);
			}
		}

	--iCount;
	FastUnlock();
	return result;
	}

/**
   FindIndex returns the index into an array of entries for a given key, by
   performing a binary search.

   @returns    Zero if entry not found, otherwise returns 1 + index into
               the array of entries
*/
TUint SMap::FindIndex(TUint aKey)
	{
	TEntry* list = iList;

	TUint l = 0;
	TUint r = iCount;
	TUint m;

	while (l < r)
		{
		m = (l + r) >> 1;
		TUint32 x = list[m].iKey;
		if (x <= aKey)
			l = m + 1;
		else
			r = m;
		}

	return r;
	}

/**
   Find returns a pointer to the data (TAny) corresponding to the lookup key

   @returns    Returns NULL if entry not found, otherwise a pointer to the
               data corresponding to the key
*/
TAny* SMap::Find(TUint aKey)
	{
	__NK_ASSERT_DEBUG(iFastLock->HeldByCurrentThread());

	TUint i = FindIndex(aKey);

	if (i == 0)
		return NULL;

	TEntry* entry = iList + i;

	--entry;

	if (aKey != entry->iKey)
		return NULL;

	TAny* result = entry->iObj;
	__NK_ASSERT_DEBUG(result);
	return result;
	}

void SMap::TIterator::Reset()
	{
	iPos = 0;
	}

SMap::TEntry* SMap::TIterator::Next()
	{
	__ASSERT_MUTEX(iMap.iSlowLock);

	if (iPos < iMap.iCount)
		return &iMap.iList[iPos++];

	return NULL;
	}