//+-------------------------------------------------------------------------
//
//  Microsoft Windows
//  Copyright (C) Microsoft Corporation, 1995.
//
//  File:       psctbl2.hxx
//
//  Contents:   Trie-based IID to CLSID map
//
//  Classes:    CMapGuidToGuidBase
//                CPSClsidTbl
//                CScmPSClsidTbl
//
//  History:    06-Jun-95 t-stevan    Created
//
//--------------------------------------------------------------------------
#ifndef __GUIDMAP2_HXX__
#define __GUIDMAP2_HXX__

#include <smstack.hxx>
    
// *** Defines ***
// Size of GUID in bytes
const int GUID_BYTES =16;

// Number of GUIDs per GUIDBlock
const int cGuids = 16;
    
// *** Types ***
// handy types to pass around based pointers in, so that we don't have to
// use __based all the time, since the usage of __based is severely limited
typedef SmBasedPtr TrieNodeBasedPtr;
typedef SmBasedPtr CGUIDBlockBasedPtr;
typedef SmBasedPtr GUIDBasedPtr;

// We reference each CLSID by a 16 bit index, so therefore we have a maximum
// of 65,535 classids in the cache
typedef WORD GUIDIndex;

// an invalid GUIDIndex = 65535
const GUIDIndex INVALID_GUID_INDEX = 0xffff;

// Functors for allocationg memory
//+-------------------------------------------------------------------------
//
//  Class:      CAllocFunctor, CStackAlloc, CHeapAlloc
//
//  Purpose:    Used to isolate the exact memory allocator being used so that adding GUIDs to the map
//              works both when the map is in shared memory and in local memory
//
//  Interface:  appropriate constructors
//              Alloc
//              Free
//
//  History:    05-Jul-95 t-stevan    Created
//
//     Note:    These classes only represent an interface to a given allocator, they are not the allocators
//              themselves, so no resources are freed when these classes are destructed expect the room
//              used to hold the references to the other allocators
//
//--------------------------------------------------------------------------
class CAllocFunctor 
{
 public:
    virtual void *Alloc(ULONG cbSize)=0;
    virtual void Free(void *pvMem, ULONG cbSize)=0;
};

// CStackAlloc - functor for CSmStackAllocator
class CStackAlloc : public CAllocFunctor
{
 public:
    CStackAlloc(CSmStackAllocator &stack) : m_stack(stack)
        {}

    void *Alloc(ULONG cbSize)
        { return m_stack.Alloc(cbSize); }

    void Free(void *pvMem, ULONG cbSize)
        { m_stack.Free(pvMem, cbSize); }

 private:
    CSmStackAllocator &m_stack; // use a reference
};

// CHeapAlloc - functor for Heap* API calls
class CHeapAlloc : public CAllocFunctor
{
 public:
    CHeapAlloc(HANDLE hHeap)
        { m_hHeap = hHeap; }

    void *Alloc(ULONG cbSize)
        { return HeapAlloc(m_hHeap, 0, cbSize); }

    void Free(void *pvMem, ULONG)
        { HeapFree(m_hHeap, 0, pvMem); }

 private:
    HANDLE m_hHeap;
};

// *** Externs ***
// This string is used to hold the key name for IIDs in the registry
extern TCHAR tszInterface[];

// the following string is used in compapi.cxx
extern WCHAR wszProxyStubClsid[];
extern WCHAR wszProxyStubClsid16[];
//+-------------------------------------------------------------------------
//
//  Class:      CMapGuidToGuidBase
//
//  Purpose:    Trie-based GUID to GUID map, this is the base implementation
//              class for the two versions of the class - the DLL (client) version
//              and the EXE (server) version
//
//  Interface:  CGuidToGuidMapBase
//              ~CGuidToGuidMapBase
//              Initialize
//
//  History:    06-Jun-95 t-stevan    Created
//
//    Note:     This class is optimized for a IID->CLSID mapping, where there are many
//              IIDs and relatively few CLSIDs. So it represents a (usually) many-to-one mapping
//              Some efficiency would be lost in a one-to-one mapping.
//--------------------------------------------------------------------------
class CMapGuidToGuidBase
{
 public:
    inline CMapGuidToGuidBase();

    // Our initialization funciton.
    HRESULT Initialize(void *pBase);

 protected:
    // *** Implementation ***
    // CGUIDBlock is a block of 16 GUIDs  which hold the GUIDs which our key GUIDs are mapped TO
    // this is because there are a LOT of repeitions in a typical IID/CLSID mapping, so it's more
    // space economical to save a 2-byte index to one copy of a 16-byte GUID in each leaf, instead
    // of storing a 16 byte GUID. 
    // Insertion into this chained list of blocks in linear time. Retrieval is O(1) (a pointer dereference).
    class CGUIDBlock
    {
     public:
        // space is allocated for us, so we don't use a constructor
        inline void Initialize();

        GUIDIndex AddGuid(void *pBase, REFGUID guid, CAllocFunctor &alloc);

        HRESULT CopyToSharedMem(void *pNewBase, void *pOldBase, CGUIDBlock *pFirstBlock, CAllocFunctor &alloc);
        
        // returns the GUID a GUIDIndex maps to
        inline BOOL GetGuid(void *pBase, GUIDIndex guidIndex, GUID &guidOut) const;

     private:
        static GUIDIndex GuidInTable(void *pBase, CGUIDBlock *pBlock, REFGUID guid);

        int m_nGuids;                     // number of guids in this block
        CGUIDBlockBasedPtr m_bpNext;     // pointer to next block in chained list
        GUID m_guidArray[cGuids];         // array of guids
        
    };

    // Information that we keep in shared memory
    struct SharedMemHeader
    {
        CGUIDBlock m_GUIDs;                
        TrieNodeBasedPtr m_bpTrie;         // our dummy start node
        BOOL m_fFull;
    };

    // Internal node structure
    // Variable length structure
    // Properties of Trie:
    //
    //        (1) Each node in a trie is either an internal node (designated Node),
    //                or a leaf node (designated Leaf). IsLeaf() returns this status
    //        (2) Each Node has NumLinks() many links to other nodes
    //        (3) Each Node has x amount of links allocated, such that
    //                x = multiple of NODE_GROWBY greater than NumLinks()
    //                    unless # of links < NODE_LINKS, in this case x = NODE_LINKS
    //        (4) The total size in bytes of a Node is sizeof(WORD)+NumKeyBytes()+sizeof(TrieNodeBasedPtr)*x,
    //                where x is from (3) above
    //        (5) Each Leaf has 0 links allocated, and sizeo(GUIDIndex) bytes for a GUID index, 
    //                which holds what the IID maps to.    
    //        (6) The total size in bytes of a Leaf is sizeof(WORD)+NumKeyBytes()+sizeof(GUIDIndex)
    //        (7) Each Node and Leaf has NumKeyBytes() bytes allocated for storing parts of a key
    //                NumKeyBytes() can be zero.
    //        (8) Starting at the root of a trie, continuing down any path of links, will create a GUID
    //                  by taking the KeyBytes stored in each Node and the final Leaf in order. This is
    //                 the principle that Find is based on.
    //        (9) Insertion involves going down the trie until a difference between the key being inserted,
    //                 and the existing key paths are found. When this happens, the Node or Leaf where the 
    //                 difference occurred is split into three nodes : a prefix Node, holding the part of the
    //                 keys that were the same (garaunteed to be at least 1), a suffix Node or Leaf, holding the part
    //                 of the original key in the trie, and a new Leaf, holding the rest of the inserted key.
    //        (10) Only leaves can be deleted, and thus have the Deleted flag set to 1
    struct TrieNode 
    {
        // Node info word allocated as follows:
        //
        //      15  14             13-5               4-0
        //   | D | F | L L L L L L L L L |  K K K K K |             m_wInfo
        //       |   |            |                  ^---------- # of bytes of key stored at node (5 bits)
        //     |   |           ^--------------------------- # of links to other nodes (9 bits)
        //     |   ^---------------------------------------- 1 = Data stored at node (leaf)    (1 bit leaf flag)
        //     |                                             0 = No data stored at node (non-leaf)
        //     ^------------------------------------------- 1 = Node deleted (1 bit deleted flag)
        //                                                    0 = Node not deleted
        // Note that the number of allocated links is
        // NODE_LINKS if NumLinks() < NODE_LINKS, or the closest multiple of NODE_GROWBY to NodeLinks() 
        // these constants are defined in psctbl2.cxx
        WORD m_wInfo;
        
        BYTE m_bData[2];     // Placeholder for data 
        
        // We use static functions and explicit "this" pointers (pRoot)
        // so that we can remove recursion easily by changing pRoot on the fly
        
        // Adds a key to a Trie starting at pRoot
        static HRESULT AddKey(void *pBase, TrieNode *pRoot, TrieNodeBasedPtr UNALIGNED *ppPrev, const BYTE *pbKey, 
                                       GUIDIndex data, BOOL fReplace, CAllocFunctor &alloc);
        
        // copies a trie to shared memory and returns a based pointer to it
        static TrieNodeBasedPtr CopyToSharedMem(void *pNewBase, void *pOldBase, TrieNode *pRoot, CAllocFunctor &alloc);

        // skeleton code as to how to go about key removal is included, but
        // commented out. 
        //static BOOL RemoveKey(TrieNode *pRoot, const BYTE *pbKey);
        
        // finds the data mapped to a key
        static BOOL TraverseKey(void *pBase, TrieNode *pRoot, const BYTE *pbKey, GUIDIndex &data);

        // public because members of CMapGuidToGuidBase and derived classes need to create leaves and nodes
        static TrieNode *CreateTrieLeaf(const BYTE *pbKey, BYTE bKeyBytes, GUIDIndex data, CAllocFunctor &alloc);
        static TrieNode *CreateTrieNode(const BYTE *pbKey, BYTE bKeyBytes, BYTE bLinks, 
                                                CAllocFunctor &alloc);
         
     private:
        // *** Internal Functions ***
        // NOTE: All private inline TrieNode functions are implemented in psctbl2.cxx
        // and therefore only accessable from there
        inline int NumLinks() const;
        inline int NumKeyBytes() const;
        inline BOOL IsLeaf() const;
        inline BOOL IsDeleted() const;
        inline void SetLeaf(BOOL fLeaf);
        inline void SetDeleted(BOOL fDeleted);
        inline void SetKeyBytes(int nKeyBytes);
        inline void SetLinks(int nLinks);
        inline void IncrementLinks();
        inline BYTE *GetKey(); 
        inline GUIDIndex *GetData(); 
        inline static int FindLinkSize(int nLinks);
        
        // Returns the computed size of a node given the information about the node
        inline static DWORD GetNodeSize(BYTE bKeyBytes, BOOL fLeaf, int bLinks);
        
        // return the start of the link array
        inline TrieNodeBasedPtr UNALIGNED *GetLinkStart() const;
        
        // Function which inserts a pointer into the link array
        // shifts nAfter nodes back one spot to make room
        inline static void InsertIntoLinkArray(TrieNodeBasedPtr UNALIGNED *pArray, TrieNodeBasedPtr pNode, int nAfter);
        
        // Returns S_OK if the node was added successfully
        // returns S_FALSE if the a new block of links had to be allocated
        // if this happens, a new TrieNode structure will be passed
        // in ppNewNode, and the old TrieNode structure will be invalid
        // This means any links to pRoot must be updated!!!!
        static HRESULT AddLink(void *pBase, TrieNode *pRoot, TrieNode *pNode, 
                                    TrieNodeBasedPtr UNALIGNED *ppNewNode, CAllocFunctor &alloc);
        
        // Returns the TrieNode associated with the next byte in the key (bKey),
        // and also returns a pointer to where this link is stored.
        // This pointer (ppLink) is necessary so that if AddLink requires us to update
        // links to this retrieved node, we can do that.
        TrieNode *GetLink(void *pBase, BYTE bKey, TrieNodeBasedPtr UNALIGNED*&ppLink);
        
        
        // Creates a suffix node from an existing node, used for splitting tries up
        TrieNode *CreateSuffixNode(BYTE bBytesDifferent, CAllocFunctor &alloc);
        
    };

    // *** Actual data for class ***
    void *m_pMemBase; // the base address for all our memory needs
    SharedMemHeader *m_pHeader; // our shared memory header
};

//+-------------------------------------------------------------------------
//
//  Class:      CPSClsidTbl
//
//  Purpose:    Trie-based GUID to GUID map, this is the DLL (client) side 
//              implementation, which only allows read-only operations
//
//  Interface:  Initialize
//              Find
//
//  History:    22-Jun-95 t-stevan    Created
//
//    Note:     Again, optimized for IID->CLSID maps
//--------------------------------------------------------------------------
class CPSClsidTbl : public CMapGuidToGuidBase
{
 public:
    HRESULT Initialize(void *pBase);

    HRESULT Find(REFGUID keyGuid, GUID *pGuidOut) const;

    inline BOOL IsFull() const;
};

//+-------------------------------------------------------------------------
//
//  Class:      CScmPSClsidTbl
//
//  Purpose:    Trie-based GUID to GUID map, this is the EXE (server) side 
//              implementation, which only allows write ops
//
//  Interface:  CScmPSClsidTbl
//              Initialize
//              InitTbl
//              FreeTbl
//              CopyToSharedMem
//              Add
//              IsFull
//
//  History:    22-Jun-95 t-stevan    Created
//
//--------------------------------------------------------------------------
class CScmPSClsidTbl : public CMapGuidToGuidBase
{
 public:
    inline CScmPSClsidTbl();

    // This initializes the object itself
    HRESULT Initialize();

    // This loads in the entries to the table from the registry
    HRESULT InitTbl();

    inline void FreeTbl();

    // copies the locally built map to shared memory
    HRESULT CopyToSharedMem(void *pBase, CSmStackAllocator &alloc);

    // adds a key to the locally build map
    HRESULT AddLocal(REFGUID keyGuid, REFGUID dataGuid, BOOL fReplace=FALSE);
    
    //BOOL Delete(REFGUID keyGuid);

    inline BOOL IsFull() const;

 private:
     // Information we use to create the trie
    struct LocalMemHeader
    {
        CGUIDBlock m_GUIDs;
        TrieNodeBasedPtr m_bpTrie;
        BOOL m_fFull;
    };

    LocalMemHeader *m_pLocalHeader;        // local tree information
    HANDLE m_hHeap;                     // local heap used to construct the table 

};

// *** Inline Functions ***
//+-------------------------------------------------------------------------
//
//  Function:   CMapGuidToGuidBase::CMapGuidToGuidBase
//
//  Synopsis:   Constructor of GUID->GUID map
//
//  Arguments:  none
//
//  Returns:    nothing
//
//--------------------------------------------------------------------------
CMapGuidToGuidBase::CMapGuidToGuidBase() : m_pMemBase(NULL), m_pHeader(NULL)
{
}

//+-------------------------------------------------------------------------
//
//  Member:     CPSClsidTbl::IsFull
//
//  Synopsis:   Returns if the map is full
//
//  Arguments:  (none)
//
//  Returns:    TRUE if the map is full, FALSE is not
//
//--------------------------------------------------------------------------
inline BOOL CPSClsidTbl::IsFull() const
{
    if(m_pHeader != NULL)
    {
        return m_pHeader->m_fFull;
    }
    else
    {
        Win4Assert(0 && "CPSClsidTbl::IsFull() called with no valid header!");
    
        return TRUE;
    }
}

//+-------------------------------------------------------------------------
//
//  Function:   CScmPSClsidTbl::CScmPSClsidTbl
//
//  Synopsis:   Constructor of GUID->GUID map, server side
//
//  Arguments:  none
//
//  Returns:    nothing
//
//--------------------------------------------------------------------------
CScmPSClsidTbl::CScmPSClsidTbl() : m_pLocalHeader(NULL), m_hHeap(NULL)
{
}

//+-------------------------------------------------------------------------
//
//  Member:     CScmPSClsidTbl::IsFull
//
//  Synopsis:   Returns if the map is full
//
//  Arguments:  (none)
//
//  Returns:    TRUE if the map is full, FALSE is not
//
//--------------------------------------------------------------------------
inline BOOL CScmPSClsidTbl::IsFull() const
{
    if(m_pLocalHeader != NULL)
    {
        return m_pLocalHeader->m_fFull;
    }
    else if(m_pHeader != NULL)
    {
        return m_pHeader->m_fFull;
    }
    else
    {
        Win4Assert(0 && "CScmPSClsidTbl::IsFull() called with no valid header!");
    
        return TRUE;
    }
}

//+-------------------------------------------------------------------------
//
//  Function:   CScmPSClsidTbl::FreeTbl
//
//  Synopsis:   Frees up the locally allocated table
//
//  Arguments:  none
//
//  Returns:    nothing
//
//--------------------------------------------------------------------------
void CScmPSClsidTbl::FreeTbl()
{
    Win4Assert(m_hHeap != NULL);

    HeapDestroy(m_hHeap);

    m_hHeap = NULL;
}

#endif // __GUIDMAP2_HXX__