--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/fontservices/textbase/sgdi/hextree.cpp	Mon Jul 12 14:38:26 2010 +0800
@@ -0,0 +1,195 @@
+// Copyright (c) 2010 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:
+// Hexadecimal trees - implementation
+//
+
+#include <hextree.h>
+#include <e32atomics.h>
+
+EXPORT_C RHexTreeBase::RHexTreeBase(RHeap* aHeap)
+    : iHeap(aHeap)
+    {
+    Mem::FillZ(iRootOffsets, sizeof(iRootOffsets));
+    }
+
+EXPORT_C TInt RHexTreeBase::SetAt(TUint aKey, TAny* aValue)
+    {
+    TUint mask = 0xF0000000;
+    for (TInt height = EMaxNumHexDigits; height > 1; --height)
+        {
+        if ((aKey & mask) != 0)
+            {
+            return SetAt(aKey, aValue, height);
+            }
+        mask >>= 4;
+        }
+    return SetAt(aKey, aValue, 1);
+    }
+
+EXPORT_C TAny* RHexTreeBase::At(TUint aKey) const
+    {
+    TUint mask = 0xF0000000;
+    for (TInt height = EMaxNumHexDigits; height > 1; --height)
+        {
+        if ((aKey & mask) != 0)
+            {
+            return At(aKey, height);
+            }
+        mask >>= 4;
+        }
+    return At(aKey, 1);
+    }
+
+/**
+Empties this associative array and frees all memory allocated both for the
+associative array implementation and for the values that have been added to
+this associative array.
+
+The internal state of this associative array is reset so that it can be reused
+or allowed to go out of scope after a call to this function.
+*/
+EXPORT_C void RHexTreeBase::ResetAndDestroy()
+    {
+    for (TInt height = 1; height <= EMaxNumHexDigits; ++height)
+        {
+        TInt offset = iRootOffsets[height - 1];
+        if (offset != 0)
+            {
+            TAny* root = PtrAdd(this, offset);
+            ResetAndDestroy(height, root, 1);
+            iRootOffsets[height - 1] = 0;
+            }
+        }
+    }
+
+TInt RHexTreeBase::SetAt(TUint aKey, TAny* aLeaf, TInt aHeight)
+    {
+    TInt err;
+    TInt offset = iRootOffsets[aHeight - 1];
+    if (offset == 0)
+        {
+        TAny* root = iHeap->AllocZ(aHeight > 1 ? sizeof(TInt) * 15 : sizeof(TInt) * 16);
+        if (!root)
+            {
+            return KErrNoMemory;
+            }
+        err = SetAt(aKey, aLeaf, aHeight, root, 1);
+        if (err == KErrNone)
+            {
+            __e32_atomic_store_rel32(&iRootOffsets[aHeight - 1], reinterpret_cast<TInt>(root) - reinterpret_cast<TInt>(this));
+            }
+        else
+            {
+            iHeap->Free(root);
+            }
+        }
+    else
+        {
+        TAny* root = PtrAdd(this, offset);
+        err = SetAt(aKey, aLeaf, aHeight, root, 1);
+        }
+    return err;
+    }
+
+TInt RHexTreeBase::SetAt(TUint aKey, TAny* aLeaf, TInt aHeight, TAny* aNode, TInt aLevel)
+    {
+    TInt err = KErrNone;
+    TInt branch = (aKey >> ((aHeight - aLevel) << 2)) & 0xF;
+    if (aLevel == 1 && aHeight > 1)
+        {
+        --branch;
+        }
+    TInt offset = static_cast<TInt*>(aNode)[branch];
+    if (aLevel == aHeight)
+        {
+        if (offset == 0)
+            {
+            __e32_atomic_store_rel32(&static_cast<TInt*>(aNode)[branch], reinterpret_cast<TInt>(aLeaf) - reinterpret_cast<TInt>(aNode));
+            }
+        else
+            {
+            err = KErrAlreadyExists;
+            }
+        }
+    else if (offset == 0)
+        {
+        TAny* newNode = iHeap->AllocZ(sizeof(TInt) * 16);
+        if (!newNode)
+            {
+            return KErrNoMemory;
+            }
+        err = SetAt(aKey, aLeaf, aHeight, newNode, aLevel + 1);
+        if (err == KErrNone)
+            {
+            __e32_atomic_store_rel32(&static_cast<TInt*>(aNode)[branch], reinterpret_cast<TInt>(newNode) - reinterpret_cast<TInt>(aNode));
+            }
+        else
+            {
+            iHeap->Free(newNode);
+            }
+        }
+    else
+        {
+        TAny* nextNode = PtrAdd(aNode, offset);
+        err = SetAt(aKey, aLeaf, aHeight, nextNode, aLevel + 1);
+        }
+    return err;
+    }
+
+TAny* RHexTreeBase::At(TUint aKey, TInt aHeight) const
+    {
+    TInt offset = __e32_atomic_load_acq32(&iRootOffsets[aHeight - 1]);
+    if (offset == 0)
+        {
+        return NULL;
+        }
+    const TAny* node = PtrAdd(this, offset);
+    for (TInt level = 1; level <= aHeight; ++level)
+        {
+        TInt branch = (aKey >> ((aHeight - level) << 2)) & 0xF;
+        if (level == 1 && aHeight > 1)
+            {
+            --branch;
+            }
+        offset = __e32_atomic_load_acq32(&static_cast<const TInt*>(node)[branch]);
+        if (offset == 0)
+            {
+            return NULL;
+            }
+        node = PtrAdd(node, offset);
+        }
+    return const_cast<TAny*>(node);
+    }
+
+void RHexTreeBase::ResetAndDestroy(TInt aHeight, TAny* aNode, TInt aLevel)
+    {
+    TInt maxNumBranches = (aLevel == 1 && aHeight > 1 ? 15 : 16);
+    for (TInt branch = 0; branch < maxNumBranches; ++branch)
+        {
+        TInt offset = static_cast<TInt*>(aNode)[branch];
+        if (offset != 0)
+            {
+            TAny* nextNode = PtrAdd(aNode, offset);
+            if (aLevel == aHeight)
+                {
+                iHeap->Free(nextNode);
+                }
+            else
+                {
+                ResetAndDestroy(aHeight, nextNode, aLevel + 1);
+                }
+            }
+        }
+    iHeap->Free(aNode);
+    }