1 /*

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

     3 * All rights reserved.

     4 * This component and the accompanying materials are made available

     5 * under the terms of "Eclipse Public License v1.0"

     6 * which accompanies this distribution, and is available

     7 * at the URL "http://www.eclipse.org/legal/epl-v10.html".

     8 *

     9 * Initial Contributors:

    10 * Nokia Corporation - initial contribution.

    11 *

    12 * Contributors:

    13 *

    14 * Description: 

    15 *

    16 */

    17 

    18 

    19 #include "UniqueInstanceImpl.h"

    20 #include "AssertFileAndLine.h"

    21 #include <e32math.h>

    22 

    23 using namespace UniqueInstance;

    24 

    25 namespace UniqueInstance

    26 {

    27 _LIT(KUniqueInstance, "UniqInst");

    28 

    29 void DestroyRUniqueInstance(void* aUniqueInstance)

    30 	{

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

    32 	}

    33 

    34 /**

    35  * Iterator that traverses an RSkipList's pointers.

    36  *

    37  * @internalComponent

    38  * @since App-frameworks6.1

    39  */

    40 class TSkipListIterator

    41 	{

    42 public:

    43 	TSkipListIterator(TCompareFn* aCompare, void* aMatch,

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

    45 	RSkipList::TSection& operator*();

    46 	TInt Level();

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

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

    49 	void SpliceOut() const;

    50 private:

    51 	TCompareFn*				iCompare;

    52 	void*					iMatch;

    53 	RSkipList::TSection**	iCurrentLink;

    54 	TInt					iLevel;

    55 	};

    56 }

    57 

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

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

    60 	: iCompare(aCompare), iMatch(aMatch),

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

    62 

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

    64 	{

    65 	return **iCurrentLink;

    66 	}

    67 

    68 TInt TSkipListIterator::Level()

    69 	{

    70 	return iLevel;

    71 	}

    72 

    73 TBool TSkipListIterator::DecrementLevel()

    74 	{

    75 	--iLevel;

    76 	++iCurrentLink;

    77 	for(;;)

    78 		{

    79 		if (!*iCurrentLink)

    80 			return EFalse;

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

    82 		if (0 <= compare)

    83 			return compare == 0;

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

    85 		}

    86 	}

    87 

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

    89 	{

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

    91 	*iCurrentLink = aSection;

    92 	}

    93 

    94 void TSkipListIterator::SpliceOut() const

    95 	{

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

    97 	}

    98 

    99 

   100 ///////////////////////

   101 //					 //

   102 //	CRepositoryImpl  //

   103 //					 //

   104 ///////////////////////

   105 

   106 CRepositoryImpl::CRepositoryImpl(TCompareFn* aCompare,

   107 	TDeleteFn* aDelete, TCopyFnL* aCopyL, TInt aObjectSize)

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

   109 	{

   110 	iNullElement.iObject = 0;

   111 	ASSERT(iCompare);

   112 	ASSERT(iDelete);

   113 	ASSERT(iCopyL);

   114 	}

   115 

   116 CRepositoryImpl::~CRepositoryImpl()

   117 	{

   118 	iSkipList.Close();

   119 	}

   120 

   121 void CRepositoryImpl::ConstructL(TInt aMaxLinks)

   122 	{

   123 	iSkipList.Open(*iCompare, aMaxLinks);

   124 	}

   125 

   126 SElement* CRepositoryImpl::NullElement()

   127 	{

   128 	return &iNullElement;

   129 	}

   130 

   131 TBool CRepositoryImpl::IsNull(SElement* a) const

   132 	{

   133 	return a == &iNullElement;

   134 	}

   135 

   136 void CRepositoryImpl::Test() const

   137 	{

   138 	iSkipList.Test();

   139 	}

   140 

   141 SElement* CRepositoryImpl::InsertOrIncL(void* aElt)

   142 	{

   143 	SElement* r = iSkipList.AddExisting(aElt);

   144 	if (!r)

   145 		return iSkipList.AddNewL(aElt);

   146 	iDelete(aElt);

   147 	return r;

   148 	}

   149 

   150 SElement* CRepositoryImpl::IncOrCopyL(void* aElt)

   151 	{

   152 	SElement* r = iSkipList.AddExisting(aElt);

   153 	if (r)

   154 		return r;

   155 	void* copy = iCopyL(aElt, iObjectSize);

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

   157 	r = iSkipList.AddNewL(copy);

   158 	CleanupStack::Pop();

   159 	return r;

   160 	}

   161 

   162 void CRepositoryImpl::DeleteOrDec(SElement* aNoLongerNeeded)

   163 	{

   164 	if (IsNull(aNoLongerNeeded))

   165 		return;

   166 	if (--(aNoLongerNeeded->iRefCount))

   167 		return;

   168 	void* object = aNoLongerNeeded->iObject;

   169 	iSkipList.Remove(object);

   170 	iDelete(object);

   171 	}

   172 

   173 void* CRepositoryImpl::DetatchOrCopyL(SElement* aWritableCopyNeeded)

   174 	{

   175 	void* retval = 0;

   176 	if (!IsNull(aWritableCopyNeeded))

   177 		{

   178 		if (1 < aWritableCopyNeeded->iRefCount)

   179 			{

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

   181 			--(aWritableCopyNeeded->iRefCount);

   182 			}

   183 		else

   184 			{

   185 			retval = aWritableCopyNeeded->iObject;

   186 			iSkipList.Remove(aWritableCopyNeeded->iObject);

   187 			}

   188 		}

   189 	return retval;

   190 	}

   191 

   192 

   193 /////////////////

   194 //			   //

   195 //	RSkipList  //

   196 //			   //

   197 /////////////////

   198 

   199 RSkipList::~RSkipList()

   200 	{

   201 	ASSERT(!iSentinel);

   202 	}

   203 

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

   205 	{

   206 	ASSERT(0 < aMaxLinks);

   207 	iLinkCount = aMaxLinks;

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

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

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

   211 	iCompare = aCompare;

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

   213 		iSentinel->iLinks[-i] = 0;

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

   215 	// coverity[memory_leak]

   216 	}

   217 

   218 void RSkipList::Close()

   219 	{

   220 	ASSERT(IsEmpty());

   221 	if (iSentinel)

   222 		operator delete(FirstLink());

   223 	iSentinel = 0;

   224 	}

   225 

   226 SElement* RSkipList::AddExisting(void* aNewElt)

   227 	{

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

   229 	while (it.Level())

   230 		{

   231 		if (it.DecrementLevel())

   232 			{

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

   234 			++(e->iRefCount);

   235 			return e;

   236 			}

   237 		}

   238 	return 0;

   239 	}

   240 

   241 void* RSkipList::Remove(void* aNoLongerNeeded)

   242 	{

   243 	void* object = 0;

   244 	TSection** toBeDeleted = 0;

   245 

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

   247 	while (it.Level())

   248 		{

   249 		if (it.DecrementLevel())

   250 			{

   251 			if (!toBeDeleted)

   252 				{

   253 				TSection& s = *it;

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

   255 				object = s.iElement.iObject;

   256 				}

   257 			it.SpliceOut();

   258 			}

   259 		}

   260 

   261 	ASSERT(toBeDeleted);

   262 	operator delete(toBeDeleted);

   263 

   264 	return object;

   265 	}

   266 

   267 SElement* RSkipList::AddNewL(void* aNewElt)

   268 	{

   269 	TInt numLinks = GenerateNumLinks();

   270 	TSection** currentLink = reinterpret_cast<TSection**>

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

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

   273 	newSection->iElement.iObject = aNewElt;

   274 	newSection->iElement.iRefCount = 1;

   275 

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

   277 #ifdef _DEBUG

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

   279 	TBool attachedToLinkList = EFalse;

   280 #endif

   281 	while (it.Level())

   282 		{

   283 		it.DecrementLevel();

   284 		if (it.Level() < numLinks)

   285 			{

   286 			it.SpliceIn(newSection);

   287 #ifdef _DEBUG

   288 			attachedToLinkList = ETrue;

   289 #endif

   290 			}

   291 		}

   292 #ifdef _DEBUG

   293 	ASSERT(attachedToLinkList);

   294 #endif

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

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

   297 	// coverity[memory_leak]

   298 	return &newSection->iElement;

   299 	}

   300 

   301 TBool RSkipList::IsEmpty() const

   302 	{

   303 	TSection** link = FirstLink();

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

   305 		{

   306 		if (*link)

   307 			return EFalse;

   308 		}

   309 	return ETrue;

   310 	}

   311 

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

   313 	{

   314 	ASSERT(iSentinel);

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

   316 	}

   317 

   318 // 3/4 chance that 1 is returned

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

   320 TInt RSkipList::GenerateNumLinks() const

   321 	{

   322 	TInt32 bits = 0;

   323 	TInt r = 1;

   324 

   325 	for (;;)

   326 		{

   327 		if (r == iLinkCount)

   328 			return r;

   329 		if ((r & 7) == 0)

   330 			bits = Math::Random();

   331 		if ((bits & 3) != 0)

   332 			return r;

   333 		++r;

   334 		bits >>= 2;

   335 		}

   336 	}

   337 

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

   339 	{

   340 	while (aStart != aEnd)

   341 		{

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

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

   344 		if (aLink)

   345 			TestLinks(aStart, aNext, aLink - 1);

   346 		aStart = aNext;

   347 		}

   348 	}

   349 

   350 TInt RSkipList::Test() const

   351 	{

   352 	TestLinks(iSentinel, 0, iLinkCount - 1);

   353 

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

   355 	if (!last)

   356 		return 0;

   357 	TInt count = 1;

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

   359 		{

   360 		++count;

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

   362 		}

   363 	return count;

   364 	}

   365