1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/graphics/graphicsdeviceinterface/gdi/sgdi/hextree.cpp Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,195 @@
1.4 +// Copyright (c) 2010 Nokia Corporation and/or its subsidiary(-ies).
1.5 +// All rights reserved.
1.6 +// This component and the accompanying materials are made available
1.7 +// under the terms of "Eclipse Public License v1.0"
1.8 +// which accompanies this distribution, and is available
1.9 +// at the URL "http://www.eclipse.org/legal/epl-v10.html".
1.10 +//
1.11 +// Initial Contributors:
1.12 +// Nokia Corporation - initial contribution.
1.13 +//
1.14 +// Contributors:
1.15 +//
1.16 +// Description:
1.17 +// Hexadecimal trees - implementation
1.18 +//
1.19 +
1.20 +#include <hextree.h>
1.21 +#include <e32atomics.h>
1.22 +
1.23 +EXPORT_C RHexTreeBase::RHexTreeBase(RHeap* aHeap)
1.24 + : iHeap(aHeap)
1.25 + {
1.26 + Mem::FillZ(iRootOffsets, sizeof(iRootOffsets));
1.27 + }
1.28 +
1.29 +EXPORT_C TInt RHexTreeBase::SetAt(TUint aKey, TAny* aValue)
1.30 + {
1.31 + TUint mask = 0xF0000000;
1.32 + for (TInt height = EMaxNumHexDigits; height > 1; --height)
1.33 + {
1.34 + if ((aKey & mask) != 0)
1.35 + {
1.36 + return SetAt(aKey, aValue, height);
1.37 + }
1.38 + mask >>= 4;
1.39 + }
1.40 + return SetAt(aKey, aValue, 1);
1.41 + }
1.42 +
1.43 +EXPORT_C TAny* RHexTreeBase::At(TUint aKey) const
1.44 + {
1.45 + TUint mask = 0xF0000000;
1.46 + for (TInt height = EMaxNumHexDigits; height > 1; --height)
1.47 + {
1.48 + if ((aKey & mask) != 0)
1.49 + {
1.50 + return At(aKey, height);
1.51 + }
1.52 + mask >>= 4;
1.53 + }
1.54 + return At(aKey, 1);
1.55 + }
1.56 +
1.57 +/**
1.58 +Empties this associative array and frees all memory allocated both for the
1.59 +associative array implementation and for the values that have been added to
1.60 +this associative array.
1.61 +
1.62 +The internal state of this associative array is reset so that it can be reused
1.63 +or allowed to go out of scope after a call to this function.
1.64 +*/
1.65 +EXPORT_C void RHexTreeBase::ResetAndDestroy()
1.66 + {
1.67 + for (TInt height = 1; height <= EMaxNumHexDigits; ++height)
1.68 + {
1.69 + TInt offset = iRootOffsets[height - 1];
1.70 + if (offset != 0)
1.71 + {
1.72 + TAny* root = PtrAdd(this, offset);
1.73 + ResetAndDestroy(height, root, 1);
1.74 + iRootOffsets[height - 1] = 0;
1.75 + }
1.76 + }
1.77 + }
1.78 +
1.79 +TInt RHexTreeBase::SetAt(TUint aKey, TAny* aLeaf, TInt aHeight)
1.80 + {
1.81 + TInt err;
1.82 + TInt offset = iRootOffsets[aHeight - 1];
1.83 + if (offset == 0)
1.84 + {
1.85 + TAny* root = iHeap->AllocZ(aHeight > 1 ? sizeof(TInt) * 15 : sizeof(TInt) * 16);
1.86 + if (!root)
1.87 + {
1.88 + return KErrNoMemory;
1.89 + }
1.90 + err = SetAt(aKey, aLeaf, aHeight, root, 1);
1.91 + if (err == KErrNone)
1.92 + {
1.93 + __e32_atomic_store_rel32(&iRootOffsets[aHeight - 1], reinterpret_cast<TInt>(root) - reinterpret_cast<TInt>(this));
1.94 + }
1.95 + else
1.96 + {
1.97 + iHeap->Free(root);
1.98 + }
1.99 + }
1.100 + else
1.101 + {
1.102 + TAny* root = PtrAdd(this, offset);
1.103 + err = SetAt(aKey, aLeaf, aHeight, root, 1);
1.104 + }
1.105 + return err;
1.106 + }
1.107 +
1.108 +TInt RHexTreeBase::SetAt(TUint aKey, TAny* aLeaf, TInt aHeight, TAny* aNode, TInt aLevel)
1.109 + {
1.110 + TInt err = KErrNone;
1.111 + TInt branch = (aKey >> ((aHeight - aLevel) << 2)) & 0xF;
1.112 + if (aLevel == 1 && aHeight > 1)
1.113 + {
1.114 + --branch;
1.115 + }
1.116 + TInt offset = static_cast<TInt*>(aNode)[branch];
1.117 + if (aLevel == aHeight)
1.118 + {
1.119 + if (offset == 0)
1.120 + {
1.121 + __e32_atomic_store_rel32(&static_cast<TInt*>(aNode)[branch], reinterpret_cast<TInt>(aLeaf) - reinterpret_cast<TInt>(aNode));
1.122 + }
1.123 + else
1.124 + {
1.125 + err = KErrAlreadyExists;
1.126 + }
1.127 + }
1.128 + else if (offset == 0)
1.129 + {
1.130 + TAny* newNode = iHeap->AllocZ(sizeof(TInt) * 16);
1.131 + if (!newNode)
1.132 + {
1.133 + return KErrNoMemory;
1.134 + }
1.135 + err = SetAt(aKey, aLeaf, aHeight, newNode, aLevel + 1);
1.136 + if (err == KErrNone)
1.137 + {
1.138 + __e32_atomic_store_rel32(&static_cast<TInt*>(aNode)[branch], reinterpret_cast<TInt>(newNode) - reinterpret_cast<TInt>(aNode));
1.139 + }
1.140 + else
1.141 + {
1.142 + iHeap->Free(newNode);
1.143 + }
1.144 + }
1.145 + else
1.146 + {
1.147 + TAny* nextNode = PtrAdd(aNode, offset);
1.148 + err = SetAt(aKey, aLeaf, aHeight, nextNode, aLevel + 1);
1.149 + }
1.150 + return err;
1.151 + }
1.152 +
1.153 +TAny* RHexTreeBase::At(TUint aKey, TInt aHeight) const
1.154 + {
1.155 + TInt offset = __e32_atomic_load_acq32(&iRootOffsets[aHeight - 1]);
1.156 + if (offset == 0)
1.157 + {
1.158 + return NULL;
1.159 + }
1.160 + const TAny* node = PtrAdd(this, offset);
1.161 + for (TInt level = 1; level <= aHeight; ++level)
1.162 + {
1.163 + TInt branch = (aKey >> ((aHeight - level) << 2)) & 0xF;
1.164 + if (level == 1 && aHeight > 1)
1.165 + {
1.166 + --branch;
1.167 + }
1.168 + offset = __e32_atomic_load_acq32(&static_cast<const TInt*>(node)[branch]);
1.169 + if (offset == 0)
1.170 + {
1.171 + return NULL;
1.172 + }
1.173 + node = PtrAdd(node, offset);
1.174 + }
1.175 + return const_cast<TAny*>(node);
1.176 + }
1.177 +
1.178 +void RHexTreeBase::ResetAndDestroy(TInt aHeight, TAny* aNode, TInt aLevel)
1.179 + {
1.180 + TInt maxNumBranches = (aLevel == 1 && aHeight > 1 ? 15 : 16);
1.181 + for (TInt branch = 0; branch < maxNumBranches; ++branch)
1.182 + {
1.183 + TInt offset = static_cast<TInt*>(aNode)[branch];
1.184 + if (offset != 0)
1.185 + {
1.186 + TAny* nextNode = PtrAdd(aNode, offset);
1.187 + if (aLevel == aHeight)
1.188 + {
1.189 + iHeap->Free(nextNode);
1.190 + }
1.191 + else
1.192 + {
1.193 + ResetAndDestroy(aHeight, nextNode, aLevel + 1);
1.194 + }
1.195 + }
1.196 + }
1.197 + iHeap->Free(aNode);
1.198 + }