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