graphicsdeviceinterface/gdi/sgdi/hextree.cpp
changeset 183 6a1564a2f3e6
parent 168 2bd88482bfe5
child 194 18f84489a694
equal deleted inserted replaced
168:2bd88482bfe5 183:6a1564a2f3e6
     1 // Copyright (c) 2010 Nokia Corporation and/or its subsidiary(-ies).
       
     2 // All rights reserved.
       
     3 // This component and the accompanying materials are made available
       
     4 // under the terms of "Eclipse Public License v1.0"
       
     5 // which accompanies this distribution, and is available
       
     6 // at the URL "http://www.eclipse.org/legal/epl-v10.html".
       
     7 //
       
     8 // Initial Contributors:
       
     9 // Nokia Corporation - initial contribution.
       
    10 //
       
    11 // Contributors:
       
    12 //
       
    13 // Description:
       
    14 // Hexadecimal trees - implementation
       
    15 //
       
    16 
       
    17 #include <hextree.h>
       
    18 #include <e32atomics.h>
       
    19 
       
    20 EXPORT_C RHexTreeBase::RHexTreeBase(RHeap* aHeap)
       
    21     : iHeap(aHeap)
       
    22     {
       
    23     Mem::FillZ(iRootOffsets, sizeof(iRootOffsets));
       
    24     }
       
    25 
       
    26 EXPORT_C TInt RHexTreeBase::SetAt(TUint aKey, TAny* aValue)
       
    27     {
       
    28     TUint mask = 0xF0000000;
       
    29     for (TInt height = EMaxNumHexDigits; height > 1; --height)
       
    30         {
       
    31         if ((aKey & mask) != 0)
       
    32             {
       
    33             return SetAt(aKey, aValue, height);
       
    34             }
       
    35         mask >>= 4;
       
    36         }
       
    37     return SetAt(aKey, aValue, 1);
       
    38     }
       
    39 
       
    40 EXPORT_C TAny* RHexTreeBase::At(TUint aKey) const
       
    41     {
       
    42     TUint mask = 0xF0000000;
       
    43     for (TInt height = EMaxNumHexDigits; height > 1; --height)
       
    44         {
       
    45         if ((aKey & mask) != 0)
       
    46             {
       
    47             return At(aKey, height);
       
    48             }
       
    49         mask >>= 4;
       
    50         }
       
    51     return At(aKey, 1);
       
    52     }
       
    53 
       
    54 /**
       
    55 Empties this associative array and frees all memory allocated both for the
       
    56 associative array implementation and for the values that have been added to
       
    57 this associative array.
       
    58 
       
    59 The internal state of this associative array is reset so that it can be reused
       
    60 or allowed to go out of scope after a call to this function.
       
    61 */
       
    62 EXPORT_C void RHexTreeBase::ResetAndDestroy()
       
    63     {
       
    64     for (TInt height = 1; height <= EMaxNumHexDigits; ++height)
       
    65         {
       
    66         TInt offset = iRootOffsets[height - 1];
       
    67         if (offset != 0)
       
    68             {
       
    69             TAny* root = PtrAdd(this, offset);
       
    70             ResetAndDestroy(height, root, 1);
       
    71             iRootOffsets[height - 1] = 0;
       
    72             }
       
    73         }
       
    74     }
       
    75 
       
    76 TInt RHexTreeBase::SetAt(TUint aKey, TAny* aLeaf, TInt aHeight)
       
    77     {
       
    78     TInt err;
       
    79     TInt offset = iRootOffsets[aHeight - 1];
       
    80     if (offset == 0)
       
    81         {
       
    82         TAny* root = iHeap->AllocZ(aHeight > 1 ? sizeof(TInt) * 15 : sizeof(TInt) * 16);
       
    83         if (!root)
       
    84             {
       
    85             return KErrNoMemory;
       
    86             }
       
    87         err = SetAt(aKey, aLeaf, aHeight, root, 1);
       
    88         if (err == KErrNone)
       
    89             {
       
    90             __e32_atomic_store_rel32(&iRootOffsets[aHeight - 1], reinterpret_cast<TInt>(root) - reinterpret_cast<TInt>(this));
       
    91             }
       
    92         else
       
    93             {
       
    94             iHeap->Free(root);
       
    95             }
       
    96         }
       
    97     else
       
    98         {
       
    99         TAny* root = PtrAdd(this, offset);
       
   100         err = SetAt(aKey, aLeaf, aHeight, root, 1);
       
   101         }
       
   102     return err;
       
   103     }
       
   104 
       
   105 TInt RHexTreeBase::SetAt(TUint aKey, TAny* aLeaf, TInt aHeight, TAny* aNode, TInt aLevel)
       
   106     {
       
   107     TInt err = KErrNone;
       
   108     TInt branch = (aKey >> ((aHeight - aLevel) << 2)) & 0xF;
       
   109     if (aLevel == 1 && aHeight > 1)
       
   110         {
       
   111         --branch;
       
   112         }
       
   113     TInt offset = static_cast<TInt*>(aNode)[branch];
       
   114     if (aLevel == aHeight)
       
   115         {
       
   116         if (offset == 0)
       
   117             {
       
   118             __e32_atomic_store_rel32(&static_cast<TInt*>(aNode)[branch], reinterpret_cast<TInt>(aLeaf) - reinterpret_cast<TInt>(aNode));
       
   119             }
       
   120         else
       
   121             {
       
   122             err = KErrAlreadyExists;
       
   123             }
       
   124         }
       
   125     else if (offset == 0)
       
   126         {
       
   127         TAny* newNode = iHeap->AllocZ(sizeof(TInt) * 16);
       
   128         if (!newNode)
       
   129             {
       
   130             return KErrNoMemory;
       
   131             }
       
   132         err = SetAt(aKey, aLeaf, aHeight, newNode, aLevel + 1);
       
   133         if (err == KErrNone)
       
   134             {
       
   135             __e32_atomic_store_rel32(&static_cast<TInt*>(aNode)[branch], reinterpret_cast<TInt>(newNode) - reinterpret_cast<TInt>(aNode));
       
   136             }
       
   137         else
       
   138             {
       
   139             iHeap->Free(newNode);
       
   140             }
       
   141         }
       
   142     else
       
   143         {
       
   144         TAny* nextNode = PtrAdd(aNode, offset);
       
   145         err = SetAt(aKey, aLeaf, aHeight, nextNode, aLevel + 1);
       
   146         }
       
   147     return err;
       
   148     }
       
   149 
       
   150 TAny* RHexTreeBase::At(TUint aKey, TInt aHeight) const
       
   151     {
       
   152     TInt offset = __e32_atomic_load_acq32(&iRootOffsets[aHeight - 1]);
       
   153     if (offset == 0)
       
   154         {
       
   155         return NULL;
       
   156         }
       
   157     const TAny* node = PtrAdd(this, offset);
       
   158     for (TInt level = 1; level <= aHeight; ++level)
       
   159         {
       
   160         TInt branch = (aKey >> ((aHeight - level) << 2)) & 0xF;
       
   161         if (level == 1 && aHeight > 1)
       
   162             {
       
   163             --branch;
       
   164             }
       
   165         offset = __e32_atomic_load_acq32(&static_cast<const TInt*>(node)[branch]);
       
   166         if (offset == 0)
       
   167             {
       
   168             return NULL;
       
   169             }
       
   170         node = PtrAdd(node, offset);
       
   171         }
       
   172     return const_cast<TAny*>(node);
       
   173     }
       
   174 
       
   175 void RHexTreeBase::ResetAndDestroy(TInt aHeight, TAny* aNode, TInt aLevel)
       
   176     {
       
   177     TInt maxNumBranches = (aLevel == 1 && aHeight > 1 ? 15 : 16);
       
   178     for (TInt branch = 0; branch < maxNumBranches; ++branch)
       
   179         {
       
   180         TInt offset = static_cast<TInt*>(aNode)[branch];
       
   181         if (offset != 0)
       
   182             {
       
   183             TAny* nextNode = PtrAdd(aNode, offset);
       
   184             if (aLevel == aHeight)
       
   185                 {
       
   186                 iHeap->Free(nextNode);
       
   187                 }
       
   188             else
       
   189                 {
       
   190                 ResetAndDestroy(aHeight, nextNode, aLevel + 1);
       
   191                 }
       
   192             }
       
   193         }
       
   194     iHeap->Free(aNode);
       
   195     }