--- /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 <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;
+ }
+