mirror of https://github.com/lianthony/NT4.0
503 lines
17 KiB
503 lines
17 KiB
// SegHash.h -- Class definition for a segmented hash table
|
|
|
|
#ifndef __SEGHASH_H__
|
|
|
|
#define __SEGHASH_H__
|
|
|
|
#include <Malloc.h>
|
|
#include "indicate.h"
|
|
#include "RWSync.h"
|
|
|
|
// How to use these class definitions...
|
|
//
|
|
// The important classes defined below are CAValRef and CSegHashTable.
|
|
// CSegHashTable objects encapsulate a segmented hash table which binds
|
|
// unique data values to fixed-size information tags. You define the size
|
|
// of those information tags when you create a CSegHashTable object. You
|
|
// manage the content of the tags as you add or look-up particular values.
|
|
//
|
|
// A CAValRef object ecapsulates a stream of references to values. This
|
|
// allows you to batch a collection of transactions against a CSegHashTable
|
|
// object and thereby reduce transaction overhead. All access to a
|
|
// CSegHashTable is mediated by a CAValRef object which lists the values
|
|
// of interest.
|
|
//
|
|
// The following public interfaces are provided:
|
|
//
|
|
// CAValRef Interfaces --
|
|
//
|
|
// CAValRef *NewValRef(UINT cSlots); // Allocates a CAValRef object
|
|
// // with space for cSlot value refs
|
|
//
|
|
// UINT CAValRef::AddValRef(PBYTE pbValue, USHORT cbValue);
|
|
// // Appends a value reference, returns
|
|
// // its index. Indices start at zero.
|
|
//
|
|
// void CAValRef::GetValRef(UINT iSlot, PBYTE *ppbValue, PUSHORT pcbValue);
|
|
// // Given an index, retrieves
|
|
// // a value reference.
|
|
//
|
|
// UINT CAValRef::CSlots (); // Number of allocated value slots.
|
|
// UINT CAValRef::CActiveSlots(); // Number of value slots in use.
|
|
//
|
|
// CAValRef *CAValRef::IndicatedSubset(CIndicatorSet *pis, UINT cSlots= 0);
|
|
// // Returns a subset of the values refs as
|
|
// // denoted by indicator set *pis.
|
|
//
|
|
// CAValRef *CAValRef:: IndexedSubset(UINT cIndices, PUINT pai, UINT cSlots= 0);
|
|
// // Returns a sbuset of the value refs as
|
|
// // denoted by index vector pai[0..cIndices-1]
|
|
//
|
|
// CSegHashTable Interfaces --
|
|
//
|
|
// CSegHashTable *NewSegHashTable(USHORT cbInfo, USHORT cbAlignment);
|
|
// // Creates a CSegHashTable object for tags
|
|
// // containing cbInfo bytes. Tags will be
|
|
// // aligned on cbAlignment byte boundaries.
|
|
// // cbInfo <= 256
|
|
// // cbAlignment can be 2, 4, or 8.
|
|
//
|
|
// CIndicatorSet *CSegHashTable::GetInfo(CAValRef *pavr, PVOID pvInfo);
|
|
// // Retrieves tags corresponding to value
|
|
// // refs. Indicator Set defines values
|
|
// // which were found.
|
|
//
|
|
// void CSegHashTable::SetInfo(CAValRef *pavr, PVOID pvInfo);
|
|
// // Sets tags for a collection of value refs.
|
|
// // Values must occur in CSegHashTable object.
|
|
//
|
|
// void CSegHashTable::AddValues(CAValRef *pavr, PVOID pvInfo);
|
|
// // Adds values and tags to a CSegHashTable
|
|
// // object. Values must not already exist in
|
|
// // CSegHashTable object.
|
|
//
|
|
// void CSegHashTable::Assimilate(CAValRef *pavr, PVOID pv, PFnHandleProc pfnMerge, PFnHandleProc pfnAdd);
|
|
// // Locates or adds values. Calls pfnMerge
|
|
// // for located values. Calls pfnAdd for
|
|
// // added values.
|
|
//
|
|
// void CSegHashTable::ForEach(PVOID pv, PFnPerTag pfnPerTag);
|
|
// // Applies function pfnPerTag to each tag in the
|
|
// // global hash table.
|
|
//
|
|
// UINT CSegHashTable::CbMemorySize(); // Space consumed by CSegHashTable object.
|
|
//
|
|
// The Assimilate function above is particularly useful for managing the tags for
|
|
// a collection of unique values. The PFnHandleProc functions must follow the form:
|
|
//
|
|
// typedef void (*PFnHandleProc)(UINT iValue, // Index of value ref in pavr
|
|
// PVOID pvTag, // Pointer to tag for value ref
|
|
// PVOID pvEnvironment // pv address passed to
|
|
// // Assimilate.
|
|
// );
|
|
//
|
|
// The PFnPerTag function has the form:
|
|
//
|
|
// typedef void (*PFnPerTag) (PVOID pvTag, // Pointer to tag for value ref
|
|
// PVOID pvEnvirionment // pv address passed to
|
|
// // ForEach.
|
|
// );
|
|
#ifndef NO_PRAGMAS
|
|
#pragma intrinsic(_alloca, memcmp, _rotl, memcpy, _rotr, memset, strcat, _strset, strcmp, _lrotl, abs, strcpy, _lrotr, strlen, labs)
|
|
#else
|
|
|
|
//
|
|
// REVIEW: HACK for Compiler bug on PPC
|
|
//
|
|
//
|
|
#pragma function(_rotl, _rotr)
|
|
#endif
|
|
|
|
typedef struct _EntryReference
|
|
{
|
|
PBYTE pbValue;
|
|
USHORT cbValue;
|
|
USHORT hvGlobal;
|
|
USHORT iHashClass;
|
|
USHORT offSegEntry;
|
|
struct _EntryReference *perNext;
|
|
|
|
} EntryReference;
|
|
|
|
class CSegHashTable;
|
|
class CSegHashSegment;
|
|
|
|
class CAValRef
|
|
{
|
|
friend class CSegHashTable;
|
|
friend class CSegHashSegment;
|
|
|
|
public:
|
|
|
|
// Creator --
|
|
|
|
static CAValRef *NewValRef(UINT cSlots);
|
|
|
|
// Destructor --
|
|
|
|
~CAValRef();
|
|
|
|
// Access Functions --
|
|
|
|
UINT AddWCRef (PWCHAR pwc, USHORT cw);
|
|
UINT AddValRef(PVOID pValue, USHORT cbValue); // returns iSlot //rmk, ronm
|
|
void GetValRef(UINT iSlot, const BYTE **ppbValue, PUSHORT pcbValue);
|
|
|
|
void DiscardRefs();
|
|
|
|
UINT CSlots ();
|
|
UINT CActiveSlots();
|
|
|
|
CAValRef *IndicatedSubset(CIndicatorSet *pis, UINT cSlots= 0);
|
|
CAValRef *IndexedSubset(UINT cIndices, PUINT pai, UINT cSlots= 0);
|
|
|
|
protected:
|
|
|
|
private:
|
|
|
|
enum { CLASSES_PER_SEGMENT= 0x2000 };
|
|
|
|
// Note: For speed we make GLOBAL_HASH_CLASSES a power of two. That allows
|
|
// us to convert a hash value to an index with a masking operation
|
|
// instead of a modulo operation.
|
|
//
|
|
// This value must match CSegHashTable::CLASSES_PER_SEGMENT!
|
|
|
|
BOOL m_fInitialed;
|
|
UINT m_cSlots;
|
|
UINT m_iSlotNext;
|
|
|
|
CSegHashTable *m_pseghash;
|
|
UINT m_cRevisions;
|
|
|
|
EntryReference *m_paRefSlots;
|
|
|
|
// Private Constructor --
|
|
|
|
CAValRef();
|
|
|
|
// Private access functions --
|
|
|
|
void ComputeHashValues(PBYTE pbValue, USHORT cbValue,
|
|
PUSHORT pushvGlobal, PUSHORT pusiHashClass
|
|
);
|
|
|
|
USHORT LocalHashMask();
|
|
};
|
|
|
|
inline UINT CAValRef::AddWCRef(PWCHAR pwc, USHORT cw)
|
|
{
|
|
return AddValRef(pwc, cw * sizeof(WCHAR));
|
|
}
|
|
|
|
typedef void (*PFnHandleProc)(UINT iValue, PVOID pvTag, PVOID pvEnvironment);
|
|
typedef void (*PFnPerTag )( PVOID pvTag, PVOID pvEnvironment);
|
|
typedef void (*PFnDumpAll )(const BYTE *pbValue, UINT cbValue, void *pvTag, PVOID pvEnvironment);
|
|
|
|
typedef struct _HashSlot
|
|
{
|
|
USHORT iClassLink;
|
|
USHORT ibImage;
|
|
USHORT hvGlobal;
|
|
USHORT iHashClass;
|
|
|
|
} HashSlot;
|
|
|
|
class CSegHashSegment
|
|
{
|
|
public:
|
|
|
|
// Constructor --
|
|
|
|
CSegHashSegment(USHORT fDepthMask, USHORT iGlobalClass, USHORT cbInfo, USHORT fAlign);
|
|
|
|
// Destructor --
|
|
|
|
inline ~CSegHashSegment() { }
|
|
|
|
// Access Functions --
|
|
|
|
USHORT DepthMask ();
|
|
USHORT GlobalClassIndex();
|
|
UINT CbAvailable ();
|
|
UINT EntryCount ();
|
|
|
|
EntryReference *Lookup(EntryReference *perValueList, EntryReference *perBase,
|
|
PVOID pv, PFnHandleProc pfnMerge, PFnHandleProc pfnAdd= NULL
|
|
);
|
|
|
|
void AddItems(EntryReference *pValueList);
|
|
|
|
CSegHashSegment *Split();
|
|
|
|
void ProcessEntryChain(EntryReference *perChain, EntryReference *perBase, PVOID pv, PFnHandleProc pfn);
|
|
|
|
void ForEach(PVOID pv, PFnPerTag pfnPerTag);
|
|
void DumpAll(PVOID pv, PFnDumpAll pfnDumpAll);
|
|
|
|
protected:
|
|
|
|
void ExportRefs(CAValRef ** ppavr, PVOID *pvInfo);
|
|
|
|
private:
|
|
|
|
enum {CLASSES_PER_SEGMENT= 0x2000, CB_BUFFER_SPACE= 0x10000 };
|
|
|
|
USHORT m_fDepthMask; // Number of hvGlobalBits used to select this hash table segmeent.
|
|
USHORT m_iGlobalClass; // Global index for this hash table segment.
|
|
USHORT m_offgheNext; // Index of next available HashSlot.
|
|
USHORT m_offImageLast; // Byte offset of last image.
|
|
USHORT m_cbInfo; // Size of info structure stored with an image.
|
|
USHORT m_fAlignment; // Mask denoting alignment requirements for info structure.
|
|
UINT m_cCollisions; // Count of hash collisions in this segment.
|
|
|
|
USHORT m_aiHashClasses[CLASSES_PER_SEGMENT]; // Headers for iHashClass chains.
|
|
BYTE m_abBuffer[CB_BUFFER_SPACE]; // Space for HashSlot, info, and image items.
|
|
|
|
// Within m_abBuffer we manage two stacks. The bottom stack grows upward from m_abBuffer[0].
|
|
// It contains a vector of HashSlot structures. The top stack grows downward from
|
|
// m_abBuffer[CB_BUFFER_SPACE-1]. It contains the value images associated with the HashSlot
|
|
// items. When a new value is added to a hash segment, we push the value on the top stack. Then we
|
|
// push a HashSlot and some additional data on the bottom stack.
|
|
//
|
|
// The size of the additional data is given by m_cbInfo. Its alignment requirements are given
|
|
// by m_fAlignment. We support alignment masks of 0x1, 0x3, and 0x7.
|
|
|
|
#ifdef _DEBUG
|
|
|
|
// Debugging code for Asserttion checking
|
|
|
|
BOOL ValidHashEntryPointer(HashSlot *pghe);
|
|
BOOL ValidImagePointer(PBYTE pbImage);
|
|
BOOL ValidHashEntryOffset(USHORT offEntry);
|
|
BOOL ValidImageOffset(USHORT offImage);
|
|
|
|
#endif // _DEBUG
|
|
|
|
HashSlot *PFirstEntry();
|
|
HashSlot *PEntry(USHORT offEntry);
|
|
HashSlot *PrevEntry(HashSlot *pghe);
|
|
HashSlot *NextEntry(HashSlot *pghe);
|
|
|
|
USHORT CbEntryImage(HashSlot *pghe );
|
|
USHORT CbEntryImage(USHORT offEntry);
|
|
|
|
PBYTE PbImage(USHORT offset);
|
|
PBYTE PbImage(HashSlot *pghe );
|
|
|
|
PBYTE PbEntryImage(USHORT offEntry);
|
|
|
|
PVOID PInfo(HashSlot *pghe );
|
|
PVOID PInfo(USHORT offEntry);
|
|
|
|
USHORT OffEntry(HashSlot *pghe);
|
|
USHORT OffImage(PBYTE pbImage);
|
|
};
|
|
|
|
typedef CSegHashSegment *PCSegHashSegment;
|
|
|
|
typedef void (CSegHashSegment::*PFnInfoAccess) (EntryReference *perChain,
|
|
EntryReference *perBase,
|
|
PVOID pvInfo
|
|
);
|
|
|
|
class CSegHashTable : CRWSync
|
|
{
|
|
// Note: Use NewSegHashTable to make new instances of this class. Don't attempt to use
|
|
// the constructor directly!
|
|
|
|
public:
|
|
|
|
// Destructor --
|
|
|
|
~CSegHashTable();
|
|
|
|
// Access Functions --
|
|
|
|
static CSegHashTable *NewSegHashTable(USHORT cbInfo, USHORT cbAlignment);
|
|
|
|
UINT EntryCount();
|
|
|
|
void Assimilate(CAValRef *pavr, PVOID pv, PFnHandleProc pfnMerge, PFnHandleProc pfnAdd);
|
|
|
|
void ForEach(PVOID pv, PFnPerTag pfnPerTag);
|
|
void DumpAll(PVOID pv, PFnDumpAll pfnDumpAll);
|
|
|
|
UINT CbMemorySize();
|
|
|
|
protected:
|
|
|
|
|
|
private:
|
|
|
|
enum { SEG_INCREMENT= 128, MAX_SEGS= 2048, MAX_LOGICAL_SEGS= 8192 };
|
|
|
|
BOOL m_fInitialed; // True if completely initialed, False otherwise.
|
|
UINT m_cChangeSets; // Count of transactions which wrote to the hash table.
|
|
USHORT m_fDepthMask; // Mask for bits in global hash value used to select a table segment.
|
|
USHORT m_cSegments; // Number of table segments currently allocated.
|
|
USHORT m_cSegSlots; // Number of slots in *m_papSegments.
|
|
USHORT m_cLogicalSlots; // Number of slots in *m_paiSegments.
|
|
USHORT m_cbInfo; // Size of info structure for each value.
|
|
USHORT m_fAlignment; // Alignment mask for info structures.
|
|
|
|
CSegHashSegment **m_papSegments; // Vector of pointers to table segments.
|
|
PUSHORT m_paiSegments; // Mapping table: hvGlobal & m_fDepthMask => iTableSegment
|
|
|
|
// Private Constructor --
|
|
|
|
CSegHashTable(USHORT cbInfo, USHORT cbAlignment);
|
|
|
|
// Private access functions --
|
|
|
|
USHORT LogicalSegCount();
|
|
|
|
void SplitAClass(EntryReference ***ppperFound, USHORT iClass);
|
|
};
|
|
|
|
// Definitions for inline functions:
|
|
|
|
inline UINT CAValRef::CSlots () { return m_cSlots; }
|
|
inline UINT CAValRef::CActiveSlots() { return m_iSlotNext; }
|
|
|
|
inline USHORT CAValRef::LocalHashMask() { return CLASSES_PER_SEGMENT - 1; }
|
|
|
|
inline void CAValRef::DiscardRefs()
|
|
{
|
|
m_iSlotNext = 0;
|
|
m_pseghash = NULL;
|
|
m_cRevisions = 0;
|
|
}
|
|
|
|
inline USHORT CSegHashSegment::DepthMask() { return m_fDepthMask ; }
|
|
inline USHORT CSegHashSegment::GlobalClassIndex() { return m_iGlobalClass; }
|
|
|
|
inline UINT CSegHashSegment::CbAvailable()
|
|
{
|
|
ASSERT(!m_offImageLast || ValidImageOffset(m_offImageLast));
|
|
ASSERT(CB_BUFFER_SPACE - m_offImageLast >= m_offgheNext);
|
|
|
|
return CB_BUFFER_SPACE - m_offImageLast - m_offgheNext;
|
|
}
|
|
|
|
inline UINT CSegHashSegment::EntryCount()
|
|
{
|
|
ASSERT(m_offgheNext / (m_cbInfo + sizeof(HashSlot)));
|
|
|
|
return (m_offgheNext / (m_cbInfo + sizeof(HashSlot)))-1;
|
|
}
|
|
|
|
inline HashSlot *CSegHashSegment::PEntry(USHORT offEntry)
|
|
{
|
|
ASSERT(ValidHashEntryOffset(offEntry)); // validate index value
|
|
|
|
return (HashSlot *) &m_abBuffer[offEntry];
|
|
}
|
|
|
|
inline HashSlot *CSegHashSegment::PFirstEntry()
|
|
{
|
|
return PEntry(sizeof(HashSlot) + m_cbInfo);
|
|
}
|
|
|
|
inline HashSlot *CSegHashSegment::PrevEntry(HashSlot *pghe)
|
|
{
|
|
ASSERT(&m_abBuffer[0] <= PBYTE(pghe) - sizeof(HashSlot) - m_cbInfo);
|
|
|
|
return (HashSlot *) (PBYTE(pghe) - sizeof(HashSlot) - m_cbInfo);
|
|
}
|
|
|
|
inline HashSlot *CSegHashSegment::NextEntry(HashSlot *pghe)
|
|
{
|
|
ASSERT(&m_abBuffer[m_offImageLast] > PBYTE(pghe) + 2*(sizeof(HashSlot) + m_cbInfo));
|
|
|
|
return (HashSlot *) (PBYTE(pghe) + sizeof(HashSlot) + m_cbInfo);
|
|
}
|
|
|
|
inline PBYTE CSegHashSegment::PbImage(USHORT offset)
|
|
{
|
|
ASSERT(ValidImageOffset(offset)); // validate offset value
|
|
|
|
return &m_abBuffer[CB_BUFFER_SPACE - offset];
|
|
}
|
|
|
|
inline PBYTE CSegHashSegment::PbImage(HashSlot *pghe)
|
|
{
|
|
ASSERT(ValidHashEntryPointer(pghe));
|
|
|
|
return PbImage(pghe->ibImage);
|
|
}
|
|
|
|
inline PBYTE CSegHashSegment::PbEntryImage(USHORT offEntry)
|
|
{
|
|
ASSERT(ValidHashEntryOffset(offEntry)); // validate index value
|
|
|
|
return PbImage(PEntry(offEntry));
|
|
}
|
|
|
|
inline USHORT CSegHashSegment::CbEntryImage(HashSlot *pghe)
|
|
{
|
|
ASSERT(ValidHashEntryPointer(pghe));
|
|
|
|
return pghe->ibImage - PrevEntry(pghe)->ibImage;
|
|
}
|
|
|
|
inline USHORT CSegHashSegment::CbEntryImage(USHORT offEntry)
|
|
{
|
|
ASSERT(ValidHashEntryOffset(offEntry)); // validate index value
|
|
|
|
return CbEntryImage(PEntry(offEntry));
|
|
}
|
|
|
|
inline PVOID CSegHashSegment::PInfo(HashSlot *pghe)
|
|
{
|
|
return (PVOID) PBYTE(pghe + 1);
|
|
}
|
|
|
|
inline PVOID CSegHashSegment::PInfo(USHORT offEntry )
|
|
{
|
|
return PInfo(PEntry(offEntry));
|
|
}
|
|
|
|
inline USHORT CSegHashSegment::OffEntry(HashSlot *pghe)
|
|
{
|
|
ASSERT(ValidHashEntryPointer(pghe)); // validate address value
|
|
|
|
return PBYTE(pghe) - m_abBuffer;
|
|
}
|
|
|
|
inline USHORT CSegHashSegment::OffImage(PBYTE pbImage)
|
|
{
|
|
ASSERT(ValidImagePointer(pbImage)); // validate address value
|
|
|
|
return (&m_abBuffer[CB_BUFFER_SPACE]) - pbImage;
|
|
}
|
|
|
|
inline USHORT CSegHashTable::LogicalSegCount()
|
|
{
|
|
ASSERT(m_fInitialed);
|
|
|
|
return m_fDepthMask + 1;
|
|
}
|
|
|
|
inline UINT CSegHashTable::CbMemorySize()
|
|
{
|
|
ASSERT(m_fInitialed);
|
|
|
|
return sizeof(*this )
|
|
+ m_cSegments * sizeof(CSegHashSegment )
|
|
+ m_cSegSlots * sizeof(CSegHashSegment *)
|
|
+ m_cLogicalSlots * sizeof(PUSHORT );
|
|
}
|
|
|
|
inline UINT CSegHashTable::EntryCount()
|
|
{
|
|
CSegHashSegment **pshs = m_papSegments;
|
|
UINT c = m_cSegments;
|
|
UINT cEntries = 0;
|
|
|
|
while (c--) cEntries += (*pshs++)->EntryCount();
|
|
|
|
return cEntries;
|
|
}
|
|
|
|
#endif // __SEGHASH_H__
|