graphicsdeviceinterface/gdi/inc/hextree.h
branchRCL_3
changeset 26 15986eb6c500
equal deleted inserted replaced
19:ac96196b945c 26:15986eb6c500
       
     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 - declaration
       
    15 //
       
    16 
       
    17 #ifndef HEXTREE_H
       
    18 #define HEXTREE_H
       
    19 
       
    20 #include <e32std.h>
       
    21 
       
    22 /**
       
    23 Base class that provides the implementation for RHexTree, which is just a thin
       
    24 template.
       
    25 
       
    26 An instance of this class can have up to eight 16-way prefix trees, with heights
       
    27 from 1 to 8. All the values are stored in the leaves. To find a value from a
       
    28 32-bit key, first the key is decomposed into 8 hexadecimal digits and then the
       
    29 prefix tree with height matching the number of digits in the key (ignoring zeros
       
    30 to the left) is traversed using the sequence of digits in the key as the
       
    31 indexing string. Offsets are internally used instead of pointers to allow
       
    32 instances to be placed in a heap shared between several processes.
       
    33 */
       
    34 class RHexTreeBase
       
    35     {
       
    36 public:
       
    37     IMPORT_C void ResetAndDestroy();
       
    38 protected:
       
    39     IMPORT_C RHexTreeBase(RHeap* aHeap);
       
    40     IMPORT_C TInt SetAt(TUint aKey, TAny* aValue);
       
    41     IMPORT_C TAny* At(TUint aKey) const;
       
    42 private:
       
    43     TInt SetAt(TUint aKey, TAny* aLeaf, TInt aHeight);
       
    44     TInt SetAt(TUint aKey, TAny* aLeaf, TInt aHeight, TAny* aNode, TInt aLevel);
       
    45     TAny* At(TUint aKey, TInt aHeight) const;
       
    46     void ResetAndDestroy(TInt aHeight, TAny* aNode, TInt aLevel);
       
    47 private:
       
    48     enum { EMaxNumHexDigits = 8 };
       
    49 private:
       
    50     RHeap* iHeap;
       
    51     TInt iRootOffsets[EMaxNumHexDigits];
       
    52     };
       
    53 
       
    54 /**
       
    55 An associative array implementation optimised for the case where the keys are
       
    56 32-bit codes with spatial locality of reference. The values can be of any
       
    57 self-contained data type (that is, without destructor or clean-up functions).
       
    58 It allows multiple-readers, single-writer concurrent access from different
       
    59 processes in an SMP-safe manner without locking, excluding deletion of
       
    60 individual key-value pairs.
       
    61 */
       
    62 template<class T>
       
    63 class RHexTree : public RHexTreeBase
       
    64     {
       
    65 public:
       
    66     inline RHexTree(RHeap* aHeap);
       
    67     inline TInt SetAt(TUint aKey, T* aValue);
       
    68     inline const T* At(TUint aKey) const;
       
    69     inline T* At(TUint aKey);
       
    70     };
       
    71 
       
    72 #include <hextree.inl>
       
    73 
       
    74 #endif // HEXTREE_H