NT4/private/ole32/com/inc/psctbl2.hxx

477 lines
17 KiB
C++
Raw Permalink Normal View History

2001-01-01 00:00:00 +01:00
//+-------------------------------------------------------------------------
//
// 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__