diff -r 000000000000 -r 1fb32624e06b textrendering/textformatting/undo/UniqueInstanceImpl.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/textrendering/textformatting/undo/UniqueInstanceImpl.cpp Tue Feb 02 02:02:46 2010 +0200 @@ -0,0 +1,365 @@ +/* +* 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 + +using namespace UniqueInstance; + +namespace UniqueInstance +{ +_LIT(KUniqueInstance, "UniqInst"); + +void DestroyRUniqueInstance(void* aUniqueInstance) + { + reinterpret_cast(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( + operator new((aMaxLinks - 1) * sizeof(TSection*) + sizeof(TSection))); + iSentinel = reinterpret_cast(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 + ( operator new((numLinks - 1) * sizeof(TSection*) + sizeof(TSection), ELeave) ); + TSection* newSection = reinterpret_cast(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; + } +