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