1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/os/graphics/graphicsdeviceinterface/gdi/inc/hextree.h	Fri Jun 15 03:10:57 2012 +0200
     1.3 @@ -0,0 +1,74 @@
     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 - declaration
    1.18 +//
    1.19 +
    1.20 +#ifndef HEXTREE_H
    1.21 +#define HEXTREE_H
    1.22 +
    1.23 +#include <e32std.h>
    1.24 +
    1.25 +/**
    1.26 +Base class that provides the implementation for RHexTree, which is just a thin
    1.27 +template.
    1.28 +
    1.29 +An instance of this class can have up to eight 16-way prefix trees, with heights
    1.30 +from 1 to 8. All the values are stored in the leaves. To find a value from a
    1.31 +32-bit key, first the key is decomposed into 8 hexadecimal digits and then the
    1.32 +prefix tree with height matching the number of digits in the key (ignoring zeros
    1.33 +to the left) is traversed using the sequence of digits in the key as the
    1.34 +indexing string. Offsets are internally used instead of pointers to allow
    1.35 +instances to be placed in a heap shared between several processes.
    1.36 +*/
    1.37 +class RHexTreeBase
    1.38 +    {
    1.39 +public:
    1.40 +    IMPORT_C void ResetAndDestroy();
    1.41 +protected:
    1.42 +    IMPORT_C RHexTreeBase(RHeap* aHeap);
    1.43 +    IMPORT_C TInt SetAt(TUint aKey, TAny* aValue);
    1.44 +    IMPORT_C TAny* At(TUint aKey) const;
    1.45 +private:
    1.46 +    TInt SetAt(TUint aKey, TAny* aLeaf, TInt aHeight);
    1.47 +    TInt SetAt(TUint aKey, TAny* aLeaf, TInt aHeight, TAny* aNode, TInt aLevel);
    1.48 +    TAny* At(TUint aKey, TInt aHeight) const;
    1.49 +    void ResetAndDestroy(TInt aHeight, TAny* aNode, TInt aLevel);
    1.50 +private:
    1.51 +    enum { EMaxNumHexDigits = 8 };
    1.52 +private:
    1.53 +    RHeap* iHeap;
    1.54 +    TInt iRootOffsets[EMaxNumHexDigits];
    1.55 +    };
    1.56 +
    1.57 +/**
    1.58 +An associative array implementation optimised for the case where the keys are
    1.59 +32-bit codes with spatial locality of reference. The values can be of any
    1.60 +self-contained data type (that is, without destructor or clean-up functions).
    1.61 +It allows multiple-readers, single-writer concurrent access from different
    1.62 +processes in an SMP-safe manner without locking, excluding deletion of
    1.63 +individual key-value pairs.
    1.64 +*/
    1.65 +template<class T>
    1.66 +class RHexTree : public RHexTreeBase
    1.67 +    {
    1.68 +public:
    1.69 +    inline RHexTree(RHeap* aHeap);
    1.70 +    inline TInt SetAt(TUint aKey, T* aValue);
    1.71 +    inline const T* At(TUint aKey) const;
    1.72 +    inline T* At(TUint aKey);
    1.73 +    };
    1.74 +
    1.75 +#include <hextree.inl>
    1.76 +
    1.77 +#endif // HEXTREE_H