/*

* Copyright (c) 2000-2009 Nokia Corporation and/or its subsidiary(-ies).

* All rights reserved.

* This component and the accompanying materials are made available

* under the terms of "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 "UniqueInstanceImpl.h"

#include "AssertFileAndLine.h"

#include <e32math.h>

using namespace UniqueInstance;

namespace UniqueInstance

{

_LIT(KUniqueInstance, "UniqInst");

void DestroyRUniqueInstance(void* aUniqueInstance)

	{

	reinterpret_cast<RInstanceImpl*>(aUniqueInstance)->Close();

	}

/**

 * Iterator that traverses an RSkipList's pointers.

 *

 * @internalComponent

 * @since App-frameworks6.1

 */

class TSkipListIterator

	{

public:

	TSkipListIterator(TCompareFn* aCompare, void* aMatch,

		RSkipList::TSection** aFirstLink, TInt aNumLinks);

	RSkipList::TSection& operator*();

	TInt Level();

	TBool DecrementLevel();		// returns true if aMatch found

	void SpliceIn(RSkipList::TSection* aSection) const;

	void SpliceOut() const;

private:

	TCompareFn*				iCompare;

	void*					iMatch;

	RSkipList::TSection**	iCurrentLink;

	TInt					iLevel;

	};

}

TSkipListIterator::TSkipListIterator(TCompareFn* aCompare, void* aMatch,

	RSkipList::TSection** aFirstLink, TInt aNumLinks)

	: iCompare(aCompare), iMatch(aMatch),

	iCurrentLink(aFirstLink - 1), iLevel(aNumLinks) {}

RSkipList::TSection& TSkipListIterator::operator*()

	{

	return **iCurrentLink;

	}

TInt TSkipListIterator::Level()

	{

	return iLevel;

	}

TBool TSkipListIterator::DecrementLevel()

	{

	--iLevel;

	++iCurrentLink;

	for(;;)

		{

		if (!*iCurrentLink)

			return EFalse;

		TInt compare = iCompare((*iCurrentLink)->iElement.iObject, iMatch);

		if (0 <= compare)

			return compare == 0;

		iCurrentLink = &(*iCurrentLink)->iLinks[-iLevel];

		}

	}

void TSkipListIterator::SpliceIn(RSkipList::TSection* aSection) const

	{

	aSection->iLinks[-iLevel] = *iCurrentLink;

	*iCurrentLink = aSection;

	}

void TSkipListIterator::SpliceOut() const

	{

	*iCurrentLink = (*iCurrentLink)->iLinks[-iLevel];

	}

///////////////////////

//					 //

//	CRepositoryImpl  //

//					 //

///////////////////////

CRepositoryImpl::CRepositoryImpl(TCompareFn* aCompare,

	TDeleteFn* aDelete, TCopyFnL* aCopyL, TInt aObjectSize)

	: iCompare(aCompare), iDelete(aDelete), iCopyL(aCopyL), iObjectSize(aObjectSize)

	{

	iNullElement.iObject = 0;

	ASSERT(iCompare);

	ASSERT(iDelete);

	ASSERT(iCopyL);

	}

CRepositoryImpl::~CRepositoryImpl()

	{

	iSkipList.Close();

	}

void CRepositoryImpl::ConstructL(TInt aMaxLinks)

	{

	iSkipList.Open(*iCompare, aMaxLinks);

	}

SElement* CRepositoryImpl::NullElement()

	{

	return &iNullElement;

	}

TBool CRepositoryImpl::IsNull(SElement* a) const

	{

	return a == &iNullElement;

	}

void CRepositoryImpl::Test() const

	{

	iSkipList.Test();

	}

SElement* CRepositoryImpl::InsertOrIncL(void* aElt)

	{

	SElement* r = iSkipList.AddExisting(aElt);

	if (!r)

		return iSkipList.AddNewL(aElt);

	iDelete(aElt);

	return r;

	}

SElement* CRepositoryImpl::IncOrCopyL(void* aElt)

	{

	SElement* r = iSkipList.AddExisting(aElt);

	if (r)

		return r;

	void* copy = iCopyL(aElt, iObjectSize);

	CleanupStack::PushL(TCleanupItem(iDelete, copy));

	r = iSkipList.AddNewL(copy);

	CleanupStack::Pop();

	return r;

	}

void CRepositoryImpl::DeleteOrDec(SElement* aNoLongerNeeded)

	{

	if (IsNull(aNoLongerNeeded))

		return;

	if (--(aNoLongerNeeded->iRefCount))

		return;

	void* object = aNoLongerNeeded->iObject;

	iSkipList.Remove(object);

	iDelete(object);

	}

void* CRepositoryImpl::DetatchOrCopyL(SElement* aWritableCopyNeeded)

	{

	void* retval = 0;

	if (!IsNull(aWritableCopyNeeded))

		{

		if (1 < aWritableCopyNeeded->iRefCount)

			{

			retval = iCopyL(aWritableCopyNeeded->iObject, iObjectSize);

			--(aWritableCopyNeeded->iRefCount);

			}

		else

			{

			retval = aWritableCopyNeeded->iObject;

			iSkipList.Remove(aWritableCopyNeeded->iObject);

			}

		}

	return retval;

	}

/////////////////

//			   //

//	RSkipList  //

//			   //

/////////////////

RSkipList::~RSkipList()

	{

	ASSERT(!iSentinel);

	}

void RSkipList::Open(TCompareFn* aCompare, TInt aMaxLinks)

	{

	ASSERT(0 < aMaxLinks);

	iLinkCount = aMaxLinks;

	TSection** sentinelBuffer = reinterpret_cast<TSection**>(

		operator new((aMaxLinks - 1) * sizeof(TSection*) + sizeof(TSection)));

	iSentinel = reinterpret_cast<TSection*>(sentinelBuffer + (iLinkCount - 1));

	iCompare = aCompare;

	for (TInt i = 0; i != iLinkCount; ++i)

		iSentinel->iLinks[-i] = 0;

	// iSentinel will be released in Close(). so,

	// coverity[memory_leak]

	}

void RSkipList::Close()

	{

	ASSERT(IsEmpty());

	if (iSentinel)

		operator delete(FirstLink());

	iSentinel = 0;

	}

SElement* RSkipList::AddExisting(void* aNewElt)

	{

	TSkipListIterator it(iCompare, aNewElt, FirstLink(), iLinkCount);

	while (it.Level())

		{

		if (it.DecrementLevel())

			{

			SElement* e = &(*it).iElement;

			++(e->iRefCount);

			return e;

			}

		}

	return 0;

	}

void* RSkipList::Remove(void* aNoLongerNeeded)

	{

	void* object = 0;

	TSection** toBeDeleted = 0;

	TSkipListIterator it(iCompare, aNoLongerNeeded, FirstLink(), iLinkCount);

	while (it.Level())

		{

		if (it.DecrementLevel())

			{

			if (!toBeDeleted)

				{

				TSection& s = *it;

				toBeDeleted = s.iLinks - it.Level();

				object = s.iElement.iObject;

				}

			it.SpliceOut();

			}

		}

	ASSERT(toBeDeleted);

	operator delete(toBeDeleted);

	return object;

	}

SElement* RSkipList::AddNewL(void* aNewElt)

	{

	TInt numLinks = GenerateNumLinks();

	TSection** currentLink = reinterpret_cast<TSection**>

		( operator new((numLinks - 1) * sizeof(TSection*) + sizeof(TSection), ELeave) );

	TSection* newSection = reinterpret_cast<TSection*>(currentLink + (numLinks - 1));

	newSection->iElement.iObject = aNewElt;

	newSection->iElement.iRefCount = 1;

	TSkipListIterator it(iCompare, aNewElt, FirstLink(), iLinkCount);

#ifdef _DEBUG

	// to ensure allocated memory will be attached to the link list.

	TBool attachedToLinkList = EFalse;

#endif

	while (it.Level())

		{

		it.DecrementLevel();

		if (it.Level() < numLinks)

			{

			it.SpliceIn(newSection);

#ifdef _DEBUG

			attachedToLinkList = ETrue;

#endif

			}

		}

#ifdef _DEBUG

	ASSERT(attachedToLinkList);

#endif

	// The memory currentLink will be attached to the link list,

	// and will be released in Remove(). so,

	// coverity[memory_leak]

	return &newSection->iElement;

	}

TBool RSkipList::IsEmpty() const

	{

	TSection** link = FirstLink();

	for (TInt i = iLinkCount; i; --i, ++link)

		{

		if (*link)

			return EFalse;

		}

	return ETrue;

	}

RSkipList::TSection** RSkipList::FirstLink() const

	{

	ASSERT(iSentinel);

	return &iSentinel->iLinks[ 1 - iLinkCount ];

	}

// 3/4 chance that 1 is returned

// (1/4)^n * (3/4) chance that (n-1) is returned

TInt RSkipList::GenerateNumLinks() const

	{

	TInt32 bits = 0;

	TInt r = 1;

	for (;;)

		{

		if (r == iLinkCount)

			return r;

		if ((r & 7) == 0)

			bits = Math::Random();

		if ((bits & 3) != 0)

			return r;

		++r;

		bits >>= 2;

		}

	}

void RSkipList::TestLinks(TSection* aStart, TSection* aEnd, TInt aLink) const

	{

	while (aStart != aEnd)

		{

		__ASSERT_ALWAYS(aStart, User::Panic(KUniqueInstance, 0));

		TSection* aNext = aStart->iLinks[-aLink];

		if (aLink)

			TestLinks(aStart, aNext, aLink - 1);

		aStart = aNext;

		}

	}

TInt RSkipList::Test() const

	{

	TestLinks(iSentinel, 0, iLinkCount - 1);

	TSection* last = iSentinel->iLinks[0];

	if (!last)

		return 0;

	TInt count = 1;

	for (TSection* p = last->iLinks[0]; p; last = p, p = p->iLinks[0])

		{

		++count;

		__ASSERT_ALWAYS(iCompare(last->iElement.iObject, p->iElement.iObject) < 0, User::Panic(KUniqueInstance, 0));

		}

	return count;

	}