sl@0: /*
sl@0: * Copyright (c) 2000-2009 Nokia Corporation and/or its subsidiary(-ies).
sl@0: * All rights reserved.
sl@0: * This component and the accompanying materials are made available
sl@0: * under the terms of "Eclipse Public License v1.0"
sl@0: * which accompanies this distribution, and is available
sl@0: * at the URL "http://www.eclipse.org/legal/epl-v10.html".
sl@0: *
sl@0: * Initial Contributors:
sl@0: * Nokia Corporation - initial contribution.
sl@0: *
sl@0: * Contributors:
sl@0: *
sl@0: * Description: 
sl@0: *
sl@0: */
sl@0: 
sl@0: 
sl@0: #include "UniqueInstanceImpl.h"
sl@0: #include "AssertFileAndLine.h"
sl@0: #include <e32math.h>
sl@0: 
sl@0: using namespace UniqueInstance;
sl@0: 
sl@0: namespace UniqueInstance
sl@0: {
sl@0: _LIT(KUniqueInstance, "UniqInst");
sl@0: 
sl@0: void DestroyRUniqueInstance(void* aUniqueInstance)
sl@0: 	{
sl@0: 	reinterpret_cast<RInstanceImpl*>(aUniqueInstance)->Close();
sl@0: 	}
sl@0: 
sl@0: /**
sl@0:  * Iterator that traverses an RSkipList's pointers.
sl@0:  *
sl@0:  * @internalComponent
sl@0:  * @since App-frameworks6.1
sl@0:  */
sl@0: class TSkipListIterator
sl@0: 	{
sl@0: public:
sl@0: 	TSkipListIterator(TCompareFn* aCompare, void* aMatch,
sl@0: 		RSkipList::TSection** aFirstLink, TInt aNumLinks);
sl@0: 	RSkipList::TSection& operator*();
sl@0: 	TInt Level();
sl@0: 	TBool DecrementLevel();		// returns true if aMatch found
sl@0: 	void SpliceIn(RSkipList::TSection* aSection) const;
sl@0: 	void SpliceOut() const;
sl@0: private:
sl@0: 	TCompareFn*				iCompare;
sl@0: 	void*					iMatch;
sl@0: 	RSkipList::TSection**	iCurrentLink;
sl@0: 	TInt					iLevel;
sl@0: 	};
sl@0: }
sl@0: 
sl@0: TSkipListIterator::TSkipListIterator(TCompareFn* aCompare, void* aMatch,
sl@0: 	RSkipList::TSection** aFirstLink, TInt aNumLinks)
sl@0: 	: iCompare(aCompare), iMatch(aMatch),
sl@0: 	iCurrentLink(aFirstLink - 1), iLevel(aNumLinks) {}
sl@0: 
sl@0: RSkipList::TSection& TSkipListIterator::operator*()
sl@0: 	{
sl@0: 	return **iCurrentLink;
sl@0: 	}
sl@0: 
sl@0: TInt TSkipListIterator::Level()
sl@0: 	{
sl@0: 	return iLevel;
sl@0: 	}
sl@0: 
sl@0: TBool TSkipListIterator::DecrementLevel()
sl@0: 	{
sl@0: 	--iLevel;
sl@0: 	++iCurrentLink;
sl@0: 	for(;;)
sl@0: 		{
sl@0: 		if (!*iCurrentLink)
sl@0: 			return EFalse;
sl@0: 		TInt compare = iCompare((*iCurrentLink)->iElement.iObject, iMatch);
sl@0: 		if (0 <= compare)
sl@0: 			return compare == 0;
sl@0: 		iCurrentLink = &(*iCurrentLink)->iLinks[-iLevel];
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: void TSkipListIterator::SpliceIn(RSkipList::TSection* aSection) const
sl@0: 	{
sl@0: 	aSection->iLinks[-iLevel] = *iCurrentLink;
sl@0: 	*iCurrentLink = aSection;
sl@0: 	}
sl@0: 
sl@0: void TSkipListIterator::SpliceOut() const
sl@0: 	{
sl@0: 	*iCurrentLink = (*iCurrentLink)->iLinks[-iLevel];
sl@0: 	}
sl@0: 
sl@0: 
sl@0: ///////////////////////
sl@0: //					 //
sl@0: //	CRepositoryImpl  //
sl@0: //					 //
sl@0: ///////////////////////
sl@0: 
sl@0: CRepositoryImpl::CRepositoryImpl(TCompareFn* aCompare,
sl@0: 	TDeleteFn* aDelete, TCopyFnL* aCopyL, TInt aObjectSize)
sl@0: 	: iCompare(aCompare), iDelete(aDelete), iCopyL(aCopyL), iObjectSize(aObjectSize)
sl@0: 	{
sl@0: 	iNullElement.iObject = 0;
sl@0: 	ASSERT(iCompare);
sl@0: 	ASSERT(iDelete);
sl@0: 	ASSERT(iCopyL);
sl@0: 	}
sl@0: 
sl@0: CRepositoryImpl::~CRepositoryImpl()
sl@0: 	{
sl@0: 	iSkipList.Close();
sl@0: 	}
sl@0: 
sl@0: void CRepositoryImpl::ConstructL(TInt aMaxLinks)
sl@0: 	{
sl@0: 	iSkipList.Open(*iCompare, aMaxLinks);
sl@0: 	}
sl@0: 
sl@0: SElement* CRepositoryImpl::NullElement()
sl@0: 	{
sl@0: 	return &iNullElement;
sl@0: 	}
sl@0: 
sl@0: TBool CRepositoryImpl::IsNull(SElement* a) const
sl@0: 	{
sl@0: 	return a == &iNullElement;
sl@0: 	}
sl@0: 
sl@0: void CRepositoryImpl::Test() const
sl@0: 	{
sl@0: 	iSkipList.Test();
sl@0: 	}
sl@0: 
sl@0: SElement* CRepositoryImpl::InsertOrIncL(void* aElt)
sl@0: 	{
sl@0: 	SElement* r = iSkipList.AddExisting(aElt);
sl@0: 	if (!r)
sl@0: 		return iSkipList.AddNewL(aElt);
sl@0: 	iDelete(aElt);
sl@0: 	return r;
sl@0: 	}
sl@0: 
sl@0: SElement* CRepositoryImpl::IncOrCopyL(void* aElt)
sl@0: 	{
sl@0: 	SElement* r = iSkipList.AddExisting(aElt);
sl@0: 	if (r)
sl@0: 		return r;
sl@0: 	void* copy = iCopyL(aElt, iObjectSize);
sl@0: 	CleanupStack::PushL(TCleanupItem(iDelete, copy));
sl@0: 	r = iSkipList.AddNewL(copy);
sl@0: 	CleanupStack::Pop();
sl@0: 	return r;
sl@0: 	}
sl@0: 
sl@0: void CRepositoryImpl::DeleteOrDec(SElement* aNoLongerNeeded)
sl@0: 	{
sl@0: 	if (IsNull(aNoLongerNeeded))
sl@0: 		return;
sl@0: 	if (--(aNoLongerNeeded->iRefCount))
sl@0: 		return;
sl@0: 	void* object = aNoLongerNeeded->iObject;
sl@0: 	iSkipList.Remove(object);
sl@0: 	iDelete(object);
sl@0: 	}
sl@0: 
sl@0: void* CRepositoryImpl::DetatchOrCopyL(SElement* aWritableCopyNeeded)
sl@0: 	{
sl@0: 	void* retval = 0;
sl@0: 	if (!IsNull(aWritableCopyNeeded))
sl@0: 		{
sl@0: 		if (1 < aWritableCopyNeeded->iRefCount)
sl@0: 			{
sl@0: 			retval = iCopyL(aWritableCopyNeeded->iObject, iObjectSize);
sl@0: 			--(aWritableCopyNeeded->iRefCount);
sl@0: 			}
sl@0: 		else
sl@0: 			{
sl@0: 			retval = aWritableCopyNeeded->iObject;
sl@0: 			iSkipList.Remove(aWritableCopyNeeded->iObject);
sl@0: 			}
sl@0: 		}
sl@0: 	return retval;
sl@0: 	}
sl@0: 
sl@0: 
sl@0: /////////////////
sl@0: //			   //
sl@0: //	RSkipList  //
sl@0: //			   //
sl@0: /////////////////
sl@0: 
sl@0: RSkipList::~RSkipList()
sl@0: 	{
sl@0: 	ASSERT(!iSentinel);
sl@0: 	}
sl@0: 
sl@0: void RSkipList::Open(TCompareFn* aCompare, TInt aMaxLinks)
sl@0: 	{
sl@0: 	ASSERT(0 < aMaxLinks);
sl@0: 	iLinkCount = aMaxLinks;
sl@0: 	TSection** sentinelBuffer = reinterpret_cast<TSection**>(
sl@0: 		operator new((aMaxLinks - 1) * sizeof(TSection*) + sizeof(TSection)));
sl@0: 	iSentinel = reinterpret_cast<TSection*>(sentinelBuffer + (iLinkCount - 1));
sl@0: 	iCompare = aCompare;
sl@0: 	for (TInt i = 0; i != iLinkCount; ++i)
sl@0: 		iSentinel->iLinks[-i] = 0;
sl@0: 	// iSentinel will be released in Close(). so,
sl@0: 	// coverity[memory_leak]
sl@0: 	}
sl@0: 
sl@0: void RSkipList::Close()
sl@0: 	{
sl@0: 	ASSERT(IsEmpty());
sl@0: 	if (iSentinel)
sl@0: 		operator delete(FirstLink());
sl@0: 	iSentinel = 0;
sl@0: 	}
sl@0: 
sl@0: SElement* RSkipList::AddExisting(void* aNewElt)
sl@0: 	{
sl@0: 	TSkipListIterator it(iCompare, aNewElt, FirstLink(), iLinkCount);
sl@0: 	while (it.Level())
sl@0: 		{
sl@0: 		if (it.DecrementLevel())
sl@0: 			{
sl@0: 			SElement* e = &(*it).iElement;
sl@0: 			++(e->iRefCount);
sl@0: 			return e;
sl@0: 			}
sl@0: 		}
sl@0: 	return 0;
sl@0: 	}
sl@0: 
sl@0: void* RSkipList::Remove(void* aNoLongerNeeded)
sl@0: 	{
sl@0: 	void* object = 0;
sl@0: 	TSection** toBeDeleted = 0;
sl@0: 
sl@0: 	TSkipListIterator it(iCompare, aNoLongerNeeded, FirstLink(), iLinkCount);
sl@0: 	while (it.Level())
sl@0: 		{
sl@0: 		if (it.DecrementLevel())
sl@0: 			{
sl@0: 			if (!toBeDeleted)
sl@0: 				{
sl@0: 				TSection& s = *it;
sl@0: 				toBeDeleted = s.iLinks - it.Level();
sl@0: 				object = s.iElement.iObject;
sl@0: 				}
sl@0: 			it.SpliceOut();
sl@0: 			}
sl@0: 		}
sl@0: 
sl@0: 	ASSERT(toBeDeleted);
sl@0: 	operator delete(toBeDeleted);
sl@0: 
sl@0: 	return object;
sl@0: 	}
sl@0: 
sl@0: SElement* RSkipList::AddNewL(void* aNewElt)
sl@0: 	{
sl@0: 	TInt numLinks = GenerateNumLinks();
sl@0: 	TSection** currentLink = reinterpret_cast<TSection**>
sl@0: 		( operator new((numLinks - 1) * sizeof(TSection*) + sizeof(TSection), ELeave) );
sl@0: 	TSection* newSection = reinterpret_cast<TSection*>(currentLink + (numLinks - 1));
sl@0: 	newSection->iElement.iObject = aNewElt;
sl@0: 	newSection->iElement.iRefCount = 1;
sl@0: 
sl@0: 	TSkipListIterator it(iCompare, aNewElt, FirstLink(), iLinkCount);
sl@0: #ifdef _DEBUG
sl@0: 	// to ensure allocated memory will be attached to the link list.
sl@0: 	TBool attachedToLinkList = EFalse;
sl@0: #endif
sl@0: 	while (it.Level())
sl@0: 		{
sl@0: 		it.DecrementLevel();
sl@0: 		if (it.Level() < numLinks)
sl@0: 			{
sl@0: 			it.SpliceIn(newSection);
sl@0: #ifdef _DEBUG
sl@0: 			attachedToLinkList = ETrue;
sl@0: #endif
sl@0: 			}
sl@0: 		}
sl@0: #ifdef _DEBUG
sl@0: 	ASSERT(attachedToLinkList);
sl@0: #endif
sl@0: 	// The memory currentLink will be attached to the link list,
sl@0: 	// and will be released in Remove(). so,
sl@0: 	// coverity[memory_leak]
sl@0: 	return &newSection->iElement;
sl@0: 	}
sl@0: 
sl@0: TBool RSkipList::IsEmpty() const
sl@0: 	{
sl@0: 	TSection** link = FirstLink();
sl@0: 	for (TInt i = iLinkCount; i; --i, ++link)
sl@0: 		{
sl@0: 		if (*link)
sl@0: 			return EFalse;
sl@0: 		}
sl@0: 	return ETrue;
sl@0: 	}
sl@0: 
sl@0: RSkipList::TSection** RSkipList::FirstLink() const
sl@0: 	{
sl@0: 	ASSERT(iSentinel);
sl@0: 	return &iSentinel->iLinks[ 1 - iLinkCount ];
sl@0: 	}
sl@0: 
sl@0: // 3/4 chance that 1 is returned
sl@0: // (1/4)^n * (3/4) chance that (n-1) is returned
sl@0: TInt RSkipList::GenerateNumLinks() const
sl@0: 	{
sl@0: 	TInt32 bits = 0;
sl@0: 	TInt r = 1;
sl@0: 
sl@0: 	for (;;)
sl@0: 		{
sl@0: 		if (r == iLinkCount)
sl@0: 			return r;
sl@0: 		if ((r & 7) == 0)
sl@0: 			bits = Math::Random();
sl@0: 		if ((bits & 3) != 0)
sl@0: 			return r;
sl@0: 		++r;
sl@0: 		bits >>= 2;
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: void RSkipList::TestLinks(TSection* aStart, TSection* aEnd, TInt aLink) const
sl@0: 	{
sl@0: 	while (aStart != aEnd)
sl@0: 		{
sl@0: 		__ASSERT_ALWAYS(aStart, User::Panic(KUniqueInstance, 0));
sl@0: 		TSection* aNext = aStart->iLinks[-aLink];
sl@0: 		if (aLink)
sl@0: 			TestLinks(aStart, aNext, aLink - 1);
sl@0: 		aStart = aNext;
sl@0: 		}
sl@0: 	}
sl@0: 
sl@0: TInt RSkipList::Test() const
sl@0: 	{
sl@0: 	TestLinks(iSentinel, 0, iLinkCount - 1);
sl@0: 
sl@0: 	TSection* last = iSentinel->iLinks[0];
sl@0: 	if (!last)
sl@0: 		return 0;
sl@0: 	TInt count = 1;
sl@0: 	for (TSection* p = last->iLinks[0]; p; last = p, p = p->iLinks[0])
sl@0: 		{
sl@0: 		++count;
sl@0: 		__ASSERT_ALWAYS(iCompare(last->iElement.iObject, p->iElement.iObject) < 0, User::Panic(KUniqueInstance, 0));
sl@0: 		}
sl@0: 	return count;
sl@0: 	}
sl@0: