|
|
/*++
Copyright (c) 1997-2002 Microsoft Corporation
Module Name : LKRhash.h
Abstract: Declares LKRhash: a fast, scalable, cache- and MP-friendly hash table
Author: Paul (Per-Ake) Larson, PALarson@microsoft.com, July 1997 Murali R. Krishnan (MuraliK) George V. Reilly (GeorgeRe) 06-Jan-1998
Environment: Win32 - User Mode
Project: LKRhash
Revision History: 10/01/1998 - Change name from LKhash to LKRhash 10/2000 - Port to kernel mode
--*/
#ifndef __LKRHASH_H__
#define __LKRHASH_H__
#ifndef __LKR_HASH_H__
// external definitions
# include <LKR-hash.h>
#endif // !__LKR_HASH_H__
#ifndef __IRTLDBG_H__
# include <IrtlDbg.h>
#endif // !__IRTLDBG_H__
#ifndef LKR_NO_GLOBAL_LIST
# ifndef __LSTENTRY_H__
# include <LstEntry.h>
# endif // !__LSTENTRY_H__
#else // LKR_NO_GLOBAL_LIST
# ifndef __LOCKS_H__
# include <Locks.h>
# endif // !__LOCKS_H__
#endif // LKR_NO_GLOBAL_LIST
#ifndef __HASHFN_H__
# include <HashFn.h>
#endif // !__HASHFN_H__
// Disable old-style deprecated iterators, by default
#ifndef LKR_DEPRECATED_ITERATORS
# define LKR_NO_DEPRECATED_ITERATORS
#endif // !LKR_DEPRECATED_ITERATORS
#ifndef LKR_NO_DEPRECATED_ITERATORS
# undef LKR_DEPRECATED_ITERATORS
# define LKR_DEPRECATED_ITERATORS 1
#endif // !LKR_NO_DEPRECATED_ITERATORS
#undef LKR_COUNTDOWN
// Is bucket locking enabled? If not, then the table lock must be held
// for longer, but that may be cheaper
#define LKR_USE_BUCKET_LOCKS
#define LKR_ALLOW_NULL_RECORDS
// #define __LKRHASH_NO_NAMESPACE__
// #define __HASHFN_NO_NAMESPACE__
// #define LKR_TABLE_LOCK CReaderWriterLock3
// #define LKR_BUCKET_LOCK CSmallSpinLock
#ifndef LKR_TABLE_LOCK
# if defined(LKR_EXPOSED_TABLE_LOCK) || defined(LKR_DEPRECATED_ITERATORS)
// need recursive writelocks
# define LKR_TABLE_LOCK CReaderWriterLock4
# else
// use non-recursive writelocks
# define LKR_TABLE_LOCK CReaderWriterLock2
# endif
#endif // !LKR_TABLE_LOCK
#ifndef LKR_BUCKET_LOCK
# ifndef LKR_USE_BUCKET_LOCKS
# define LKR_BUCKET_LOCK CFakeLock
# elif defined(LKR_DEPRECATED_ITERATORS)
# define LKR_BUCKET_LOCK CReaderWriterLock3
# else // !LKR_DEPRECATED_ITERATORS
# define LKR_BUCKET_LOCK CSmallSpinLock
# endif // !LKR_DEPRECATED_ITERATORS
#endif // !LKR_BUCKET_LOCK
#ifdef IRTLDEBUG
# define LKR_ALLOC_STATS
# define LKR_OPS_STATS
#endif // IRTLDEBUG
//=====================================================================
// The class CLKRLinearHashTable defined in this file provides dynamic hash
// tables, i.e. tables that grow and shrink dynamically with
// the number of records in the table.
// The basic method used is linear hashing, as explained in:
//
// P.-A. Larson, Dynamic Hash Tables, Comm. of the ACM, 31, 4 (1988)
//
// This version has the following characteristics:
// - It is thread-safe and uses spin locks for synchronization.
// - It was designed to support very high rates of concurrent
// operations (inserts/deletes/lookups). It achieves this by
// (a) partitioning a CLKRHashTable into a collection of
// CLKRLinearHashTables to reduce contention on the global table lock.
// (b) minimizing the hold time on a table lock, preferring to lock
// down a bucket chain instead.
// - The design is L1 cache-conscious. See CNodeClump.
// - It is designed for sets varying in size from a dozen
// elements to several million.
//
// Main classes:
// CLKRLinearHashTable: thread-safe linear hash table
// CLKRHashTable: collection of CLKRLinearHashTables
// CTypedHashTable: typesafe wrapper for CLKRHashTable
//
//
// Paul Larson, [email protected], July 1997
// Original implementation with input from Murali R. Krishnan,
// [email protected].
//
// George V. Reilly, [email protected], Dec 1997-Jan 1998
// Massive cleanup and rewrite. Added templates.
//=====================================================================
// 1) Linear Hashing
// ------------------
//
// Linear hash tables grow and shrink dynamically with the number of
// records in the table. The growth or shrinkage is smooth: logically,
// one bucket at a time but physically in larger increments
// (64 buckets). An insertion (deletion) may cause an expansion
// (contraction) of the table. This causes relocation of a small number
// of records (at most one bucket worth). All operations (insert,
// delete, lookup) take constant expected time, regardless of the
// current size or the growth of the table.
//
// 2) LKR extensions to Linear hash table
// --------------------------------------
//
// Larson-Krishnan-Reilly extensions to Linear hash tables for multiprocessor
// scalability and improved cache performance.
//
// Traditional implementations of linear hash tables use one global lock
// to prevent interference between concurrent operations
// (insert/delete/lookup) on the table. The single lock easily becomes
// the bottleneck in SMP scenarios when multiple threads are used.
//
// Traditionally, a (hash) bucket is implemented as a chain of
// single-item nodes. Every operation results in chasing down a chain
// looking for an item. However, pointer chasing is very slow on modern
// systems because almost every jump results in a cache miss. L2 (or L3)
// cache misses are very expensive in missed CPU cycles and the cost is
// increasing (going to 100s of cycles in the future).
//
// LKR extensions offer
// 1) Partitioning (by hashing) of records among multiple subtables.
// Each subtable has locks but there is no global lock. Each
// subtable receives a much lower rate of operations, resulting in
// fewer conflicts.
//
// 2) Improved cache locality by grouping keys and their hash values
// into contigous chunks that fit exactly into one (or a few)
// cache lines.
//
// Specifically the implementation that exists here achieves this using
// the following techniques.
//
// Class CLKRHashTable is the top-level data structure that dynamically
// creates m_cSubTables linear hash subtables. The CLKRLinearHashTables act as
// the subtables to which items and accesses are fanned out. A good
// hash function multiplexes requests uniformly to various subtables,
// thus minimizing traffic to any single subtable. The implemenation
// uses a home-grown version of bounded spinlocks, that is, a thread
// does not spin on a lock indefinitely, instead yielding after a
// predetermined number of loops.
//
// Each CLKRLinearHashTable consists of a directory (growable array) of
// segments, each holding m_nSegSize CBuckets. Each CBucket in turn consists
// of a chain of CNodeClumps. Each CNodeClump contains a group of
// NODES_PER_CLUMP hash values (aka hash keys or signatures) and
// pointers to the associated data items. Keeping the signatures
// together increases the cache locality in scans for lookup.
//
// Traditionally, people store a link-list element right inside the
// object that is hashed and use this link-list for the chaining of data
// blocks. However, keeping just the pointers to the data object and
// not chaining through them limits the need for bringing in the data
// object to the cache. We need to access the data object only if the
// hash values match. This limits the cache-thrashing behaviour
// exhibited by conventional implementations. It has the additional
// benefit that the objects themselves do not need to be modified
// in order to be collected in the hash subtable (i.e., it's non-invasive).
#ifdef LKR_STL_ITERATORS
// needed for std::forward_iterator_tag, etc
# include <iterator>
// The iterators have very verbose tracing. Don't want it on all the time
// in debug builds.
# if defined(IRTLDEBUG) && (LKR_STL_ITERATORS >= 2)
# define LKR_ITER_TRACE IrtlTrace
# else // !defined(IRTLDEBUG) || LKR_STL_ITERATORS < 2
# define LKR_ITER_TRACE 1 ? (void)0 : IrtlTrace
# endif // !defined(IRTLDEBUG) || LKR_STL_ITERATORS < 2
#endif // LKR_STL_ITERATORS
//--------------------------------------------------------------------
// Default values for the hashtable constructors
enum {#ifdef _WIN64
LK_DFLT_MAXLOAD= 4, // 64-byte nodes => NODES_PER_CLUMP = 4
#else
LK_DFLT_MAXLOAD= 7, // Default upperbound on average chain length.
#endif
LK_DFLT_INITSIZE=LK_MEDIUM_TABLESIZE, // Default initial size of hash table
LK_DFLT_NUM_SUBTBLS= 0, // Use a heuristic to choose #subtables
};
/*--------------------------------------------------------------------
* Undocumented additional creation flag parameters to LKR_CreateTable */
enum { LK_CREATE_NON_PAGED_ALLOCS = 0x1000, // Use paged or NP pool in kernel
};
//--------------------------------------------------------------------
// Custom memory allocators (optional)
//--------------------------------------------------------------------
#if !defined(LKR_NO_ALLOCATORS) && !defined(LKRHASH_KERNEL_MODE)
// # define LKRHASH_ACACHE 1
// # define LKRHASH_ROCKALL_FAST 1
#endif // !LKR_NO_ALLOCATORS && !LKRHASH_KERNEL_MODE
#if defined(LKRHASH_ACACHE)
# include <acache.hxx>
class ACache : public ALLOC_CACHE_HANDLER{private: SIZE_T m_cb;
public: ACache(IN LPCSTR pszName, IN const ALLOC_CACHE_CONFIGURATION* pacConfig) : ALLOC_CACHE_HANDLER(pszName, pacConfig), m_cb(m_acConfig.cbSize) {}
SIZE_T ByteSize() const { return m_cb; }
static const TCHAR* ClassName() {return _TEXT("ACache");}}; // class ACache
typedef ACache CLKRhashAllocator;# define LKRHASH_ALLOCATOR_NEW(_C, N, Tag) \
const ALLOC_CACHE_CONFIGURATION acc = { 1, N, sizeof(_C) }; \ _C::sm_palloc = new ACache("LKRhash:" #_C, &acc);
#elif defined(LKRHASH_ROCKALL_FAST)
# include <FastHeap.hpp>
class FastHeap : public FAST_HEAP{private: SIZE_T m_cb;
public: FastHeap(SIZE_T cb) : m_cb(cb) {}
LPVOID Alloc() { return New(m_cb, NULL, false); }
BOOL Free(LPVOID pvMem) { return Delete(pvMem); }
SIZE_T ByteSize() const { return m_cb; }
static const TCHAR* ClassName() {return _TEXT("FastHeap");}}; // class FastHeap
typedef FastHeap CLKRhashAllocator;# define LKRHASH_ALLOCATOR_NEW(_C, N, Tag) \
_C::sm_palloc = new FastHeap(sizeof(_C))
#endif // LKRHASH_ROCKALL_FAST
#ifdef LKRHASH_ALLOCATOR_NEW
// placed inline in the declaration of class _C
# define LKRHASH_ALLOCATOR_DEFINITIONS(_C) \
protected: \ static CLKRhashAllocator* sm_palloc; \ public: \ friend class CLKRLinearHashTable; \ \ static void* operator new(size_t s) \ { \ UNREFERENCED_PARAMETER(s); \ IRTLASSERT(s == sizeof(_C)); \ IRTLASSERT(sm_palloc != NULL); \ return sm_palloc->Alloc(); \ } \ static void operator delete(void* pv) \ { \ IRTLASSERT(pv != NULL); \ IRTLASSERT(sm_palloc != NULL); \ sm_palloc->Free(pv); \ }
// used in LKR_Initialize()
# define LKRHASH_ALLOCATOR_INIT(_C, N, Tag, f) \
{ \ if (f) \ { \ IRTLASSERT(_C::sm_palloc == NULL); \ LKRHASH_ALLOCATOR_NEW(_C, N, Tag); \ f = (_C::sm_palloc != NULL); \ } \ }
// used in LKR_Terminate()
# define LKRHASH_ALLOCATOR_UNINIT(_C) \
{ \ if (_C::sm_palloc != NULL) \ { \ delete _C::sm_palloc; \ _C::sm_palloc = NULL; \ } \ }
#else // !LKRHASH_ALLOCATOR_NEW
# define LKRHASH_ALLOCATOR_DEFINITIONS(_C)
# define LKRHASH_ALLOCATOR_INIT(_C, N, Tag, f)
# define LKRHASH_ALLOCATOR_UNINIT(_C)
class CLKRhashAllocator{public: static const TCHAR* ClassName() {return _TEXT("global new");}};
#endif // !LKRHASH_ALLOCATOR_NEW
#define LKRHASH_CLASS_INIT_DECLS(_C) \
private: \ /* class-wide initialization and termination */ \ static int _Initialize(DWORD dwFlags); \ static void _Terminate(); \ \ friend int ::LKR_Initialize(DWORD dwInitFlags); \ friend void ::LKR_Terminate()
#ifndef __LKRHASH_NO_NAMESPACE__
namespace LKRhash {#endif // !__LKRHASH_NO_NAMESPACE__
//--------------------------------------------------------------------
// forward declarations
class IRTL_DLLEXP CLKRLinearHashTable;
class IRTL_DLLEXP CLKRHashTable;
template <class _Der, class _Rcd, class _Ky, bool _fDRC, class _HT#ifdef LKR_DEPRECATED_ITERATORS
, class _Iter#endif // LKR_DEPRECATED_ITERATORS
>class CTypedHashTable;
class CNodeClump;typedef CNodeClump* PNodeClump;
class CBucket;typedef CBucket* PBucket;
class CSegment;typedef CSegment* PSegment;
class IRTL_DLLEXP CLKRHashTableStats;
//--------------------------------------------------------------------
// Statistical information returned by GetStatistics
//--------------------------------------------------------------------
#ifdef LOCK_INSTRUMENTATION
class IRTL_DLLEXP CAveragedLockStats : public CLockStatistics{public: int m_nItems;
CAveragedLockStats();}; // class CAveragedLockStats
#endif // LOCK_INSTRUMENTATION
#ifndef LKRHASH_KERNEL_MODE
class IRTL_DLLEXP CLKRHashTableStats{public: int RecordCount; // number of records in the table
int TableSize; // table size in number of slots
int DirectorySize; // number of entries in directory
int LongestChain; // longest hash chain in the table
int EmptySlots; // number of unused hash slots
double SplitFactor; // fraction of buckets split
double AvgSearchLength; // average length of a successful search
double ExpSearchLength; // theoretically expected length
double AvgUSearchLength; // average length of an unsuccessful search
double ExpUSearchLength; // theoretically expected length
int NodeClumpSize; // number of slots in a node clump
int CBucketSize; // sizeof(CBucket)
#ifdef LOCK_INSTRUMENTATION
CAveragedLockStats m_alsTable; // stats for table lock
CAveragedLockStats m_alsBucketsAvg; // avg of stats for bucket locks
CGlobalLockStatistics m_gls; // global statistics for all locks
#endif // LOCK_INSTRUMENTATION
enum { MAX_BUCKETS = 40, };
// histogram of bucket lengths
LONG m_aBucketLenHistogram[MAX_BUCKETS];
CLKRHashTableStats();
static const LONG* BucketSizes();
static LONG BucketSize( LONG nBucketIndex);
static LONG BucketIndex( LONG nBucketLength);}; // class CLKRHashTableStats
#endif // !LKRHASH_KERNEL_MODE
//--------------------------------------------------------------------
// Keep some statistics about allocations/frees and about various operations
#ifdef LKR_ALLOC_STATS
# define DECLARE_ALLOC_STAT(Type) \
mutable LONG m_c##Type##Allocs; \ mutable LONG m_c##Type##Frees; \ static LONG sm_c##Type##Allocs; \ static LONG sm_c##Type##Frees
# define DECLARE_CLASS_ALLOC_STAT_STORAGE(Class, Type) \
LONG LKRHASH_NS::Class::sm_c##Type##Allocs; \ LONG LKRHASH_NS::Class::sm_c##Type##Frees
# define INIT_ALLOC_STAT(Type) \
m_c##Type##Allocs = m_c##Type##Frees = 0
# define INIT_CLASS_ALLOC_STAT(Class, Type) \
LKRHASH_NS::Class::sm_c##Type##Allocs = 0; \ LKRHASH_NS::Class::sm_c##Type##Frees = 0
# define INCREMENT_ALLOC_STAT(Type) \
InterlockedIncrement(&m_c##Type##Allocs); \ InterlockedIncrement(&sm_c##Type##Allocs)
# define INCREMENT_FREE_STAT(Type) \
InterlockedIncrement(&m_c##Type##Frees); \ InterlockedIncrement(&sm_c##Type##Frees)
# define VALIDATE_DUMP_ALLOC_STAT(Type) \
IRTLASSERT(m_c##Type##Allocs == m_c##Type##Frees); \ IRTLTRACE(_TEXT(#Type) _TEXT(": Allocs=%ld, Frees=%ld\n"), \ m_c##Type##Allocs, m_c##Type##Frees)
# define VALIDATE_DUMP_CLASS_ALLOC_STAT(Class, Type) \
IRTLASSERT(LKRHASH_NS::Class::sm_c##Type##Allocs \ == LKRHASH_NS::Class::sm_c##Type##Frees); \ IRTLTRACE(_TEXT("Global ") _TEXT(#Type) \ _TEXT(": Allocs=%ld, Frees=%ld\n"), \ LKRHASH_NS::Class::sm_c##Type##Allocs, \ LKRHASH_NS::Class::sm_c##Type##Frees)
#else // !LKR_ALLOC_STATS
# define DECLARE_ALLOC_STAT(Type)
# define DECLARE_CLASS_ALLOC_STAT_STORAGE(Class, Type)
# define INIT_ALLOC_STAT(Type) ((void) 0)
# define INIT_CLASS_ALLOC_STAT(Class, Type) ((void) 0)
# define INCREMENT_ALLOC_STAT(Type) ((void) 0)
# define INCREMENT_FREE_STAT(Type) ((void) 0)
# define VALIDATE_DUMP_ALLOC_STAT(Type) ((void) 0)
# define VALIDATE_DUMP_CLASS_ALLOC_STAT(Class, Type) ((void) 0)
#endif // !LKR_ALLOC_STATS
// Statistics on different kinds of operations
#ifdef LKR_OPS_STATS
# define DECLARE_OP_STAT(Type) \
mutable LONG m_c##Type##Ops; \ static LONG sm_c##Type##Ops
# define DECLARE_CLASS_OP_STAT_STORAGE(Class, Type) \
LONG LKRHASH_NS::Class::sm_c##Type##Ops
# define INIT_OP_STAT(Type) \
m_c##Type##Ops = 0
# define INIT_CLASS_OP_STAT(Class, Type) \
LKRHASH_NS::Class::sm_c##Type##Ops = 0
# define INCREMENT_OP_STAT(Type) \
InterlockedIncrement(&m_c##Type##Ops); \ InterlockedIncrement(&sm_c##Type##Ops)
# define DUMP_OP_STAT(Type) \
IRTLTRACE(_TEXT(#Type) _TEXT(": Ops=%ld\n"), m_c##Type##Ops)
# define DUMP_CLASS_OP_STAT(Class, Type) \
IRTLTRACE(_TEXT("Global ") _TEXT(#Type) _TEXT(": Ops=%ld\n"), \ LKRHASH_NS::Class::sm_c##Type##Ops)
#else // !LKR_OPS_STATS
# define DECLARE_OP_STAT(Type)
# define DECLARE_CLASS_OP_STAT_STORAGE(Class, Type)
# define INIT_OP_STAT(Type) ((void) 0)
# define INIT_CLASS_OP_STAT(Class,Type) ((void) 0)
# define INCREMENT_OP_STAT(Type) ((void) 0)
# define DUMP_OP_STAT(Type) ((void) 0)
# define DUMP_CLASS_OP_STAT(Class,Type) ((void) 0)
#endif // !LKR_OPS_STATS
//--------------------------------------------------------------------
// Global table lock code. This is only used to measure how much of a
// slowdown having a global lock on the CLKRHashTable causes. It is
// *never* used in production code.
// #define LKRHASH_GLOBAL_LOCK CCritSec
#ifdef LKRHASH_GLOBAL_LOCK
# define LKRHASH_GLOBAL_LOCK_DECLARATIONS() \
typedef LKRHASH_GLOBAL_LOCK GlobalLock; \ mutable GlobalLock m_lkGlobal;
# define LKRHASH_GLOBAL_READ_LOCK() m_lkGlobal.ReadLock()
# define LKRHASH_GLOBAL_WRITE_LOCK() m_lkGlobal.WriteLock()
# define LKRHASH_GLOBAL_READ_UNLOCK() m_lkGlobal.ReadUnlock()
# define LKRHASH_GLOBAL_WRITE_UNLOCK() m_lkGlobal.WriteUnlock()
#else // !LKRHASH_GLOBAL_LOCK
# define LKRHASH_GLOBAL_LOCK_DECLARATIONS()
// These ones will be optimized away by the compiler
# define LKRHASH_GLOBAL_READ_LOCK() ((void)0)
# define LKRHASH_GLOBAL_WRITE_LOCK() ((void)0)
# define LKRHASH_GLOBAL_READ_UNLOCK() ((void)0)
# define LKRHASH_GLOBAL_WRITE_UNLOCK() ((void)0)
#endif // !LKRHASH_GLOBAL_LOCK
// Class for nodes on a bucket chain. Instead of a node containing
// one (signature, record-pointer, next-tuple-pointer) tuple, it
// contains _N_ such tuples. (N-1 next-tuple-pointers are omitted.)
// This improves locality of reference greatly; i.e., it's L1
// cache-friendly. It also reduces memory fragmentation and memory
// allocator overhead. It does complicate the chain traversal code
// slightly, admittedly.
//
// This theory is beautiful. In practice, however, CNodeClumps
// are *not* perfectly aligned on 32-byte boundaries by the memory
// allocators. Experimental results indicate that we get a 2-3%
// speed improvement by using 32-byte-aligned blocks, but this must
// be considered against the average of 16 bytes wasted per block.
class CNodeClump{public: // Record slots per chunk - set so a chunk matches (one or two)
// cache lines. 3 ==> 32 bytes, 7 ==> 64 bytes, on 32-bit system.
// Note: the default max load factor is 7, which implies that
// there will seldom be more than one node clump in a chain.
enum {#if defined(LOCK_INSTRUMENTATION)
BUCKET_BYTE_SIZE = 96,#else
BUCKET_BYTE_SIZE = 64,#endif
// overhead = m_Lock + m_pncNext
BUCKET_OVERHEAD = sizeof(LKR_BUCKET_LOCK) + sizeof(PNodeClump), // node size = dwKeySignature + pvRecord
NODE_SIZE = sizeof(const void*) + sizeof(DWORD), NODES_PER_CLUMP = (BUCKET_BYTE_SIZE - BUCKET_OVERHEAD) / NODE_SIZE,#ifdef _WIN64
NODE_CLUMP_BITS = 2,#else
NODE_CLUMP_BITS = 3,#endif
_NODES_PER_CLUMP = 15, // <<---
_NODE_CLUMP_BITS = 4, };
typedef int NodeIndex; // for iterating through a CNodeClump
enum { // See if countdown loops are faster than countup loops for
// traversing a CNodeClump. In practice, countup loops are faster.
// These constants allow us to write direction-agnostic loops,
// such as
// for (NodeIndex x = NODE_BEGIN; x != NODE_END; x += NODE_STEP)
#ifndef LKR_COUNTDOWN
// for (NodeIndex x = 0; x < NODES_PER_CLUMP; ++x) ...
NODE_BEGIN = 0, NODE_END = NODES_PER_CLUMP, NODE_STEP = +1,#else // LKR_COUNTDOWN
// for (NodeIndex x = NODES_PER_CLUMP; --x >= 0; ) ...
NODE_BEGIN = NODES_PER_CLUMP - 1, NODE_END = -1, NODE_STEP = -1,#endif // LKR_COUNTDOWN
};
// If m_dwKeySigs[iNode] == HASH_INVALID_SIGNATURE then the node is
// empty, as are all nodes in the range [iNode+NODE_STEP, NODE_END).
enum {#ifndef __HASHFN_NO_NAMESPACE__
HASH_INVALID_SIGNATURE = HashFn::HASH_INVALID_SIGNATURE,#else // !__HASHFN_NO_NAMESPACE__
HASH_INVALID_SIGNATURE = ::HASH_INVALID_SIGNATURE,#endif // !__HASHFN_NO_NAMESPACE__
};
DWORD m_dwKeySigs[NODES_PER_CLUMP];// hash values computed from keys
PNodeClump m_pncNext; // next node clump on the chain
const void* m_pvNode[NODES_PER_CLUMP]; // pointers to records
CNodeClump() { STATIC_ASSERT((1 << (NODE_CLUMP_BITS - 1)) < NODES_PER_CLUMP); STATIC_ASSERT(NODES_PER_CLUMP <= (1 << NODE_CLUMP_BITS)); STATIC_ASSERT(NODES_PER_CLUMP * NODE_SIZE + BUCKET_OVERHEAD <= BUCKET_BYTE_SIZE); Clear(); }
void Clear() { m_pncNext = NULL; // no dangling pointers
IRTLASSERT(IsLastClump());
for (NodeIndex iNode = NODES_PER_CLUMP; --iNode >= 0; ) { m_dwKeySigs[iNode] = HASH_INVALID_SIGNATURE; m_pvNode[iNode] = NULL; IRTLASSERT(IsEmptyAndInvalid(iNode)); } }
DWORD Signature( NodeIndex iNode) const { IRTLASSERT(0 <= iNode && iNode < NODES_PER_CLUMP); return m_dwKeySigs[iNode]; }
const void* Node( NodeIndex iNode) const { IRTLASSERT(0 <= iNode && iNode < NODES_PER_CLUMP); return m_pvNode[iNode]; }
PNodeClump const NextClump() const { return m_pncNext; }
bool InvalidSignature( NodeIndex iNode) const { IRTLASSERT(0 <= iNode && iNode < NODES_PER_CLUMP); return (m_dwKeySigs[iNode] == HASH_INVALID_SIGNATURE); }
bool IsEmptyNode( NodeIndex iNode) const { IRTLASSERT(0 <= iNode && iNode < NODES_PER_CLUMP);#ifndef LKR_ALLOW_NULL_RECORDS
return (m_pvNode[iNode] == NULL);#else
return InvalidSignature(iNode);#endif
}
bool IsEmptyAndInvalid( NodeIndex iNode) const { return#ifndef LKR_ALLOW_NULL_RECORDS
IsEmptyNode(iNode) &&#endif
InvalidSignature(iNode); }
bool IsEmptySlot( NodeIndex iNode) const { return InvalidSignature(iNode); }
bool IsLastClump() const { return (m_pncNext == NULL); }
#ifdef IRTLDEBUG
bool NoMoreValidSlots( NodeIndex iNode) const { IRTLASSERT(0 <= iNode && iNode < NODES_PER_CLUMP); bool f = IsLastClump(); // last nodeclump in chain
for ( ; iNode != NODE_END; iNode += NODE_STEP) f = f && IsEmptyAndInvalid(iNode); return f; }
bool NoValidSlots() const { return NoMoreValidSlots(NODE_BEGIN); }
// Don't want overhead of calls to dtor in retail build, since it
// doesn't do anything useful
~CNodeClump() { IRTLASSERT(IsLastClump()); // no dangling pointers
for (NodeIndex iNode = NODES_PER_CLUMP; --iNode >= 0; ) IRTLASSERT(InvalidSignature(iNode) && IsEmptyNode(iNode)); }#endif // IRTLDEBUG
private: // We rely on the compiler to generate an efficient copy constructor
// and operator= that make shallow (bitwise) copies of CNodeClumps.
LKRHASH_ALLOCATOR_DEFINITIONS(CNodeClump);
LKRHASH_CLASS_INIT_DECLS(CNodeClump);}; // class CNodeClump
#ifdef LKR_STL_ITERATORS
class IRTL_DLLEXP CLKRLinearHashTable_Iterator;class IRTL_DLLEXP CLKRHashTable_Iterator;
class IRTL_DLLEXP CLKRLinearHashTable_Iterator{ friend class CLKRLinearHashTable; friend class CLKRHashTable; friend class CLKRHashTable_Iterator;
protected: typedef short NodeIndex;
CLKRLinearHashTable* m_plht; // which linear hash subtable?
PNodeClump m_pnc; // a CNodeClump in bucket
DWORD m_dwBucketAddr;// bucket index
NodeIndex m_iNode; // offset within m_pnc
enum { NODES_PER_CLUMP = CNodeClump::NODES_PER_CLUMP, NODE_BEGIN = CNodeClump::NODE_BEGIN, NODE_END = CNodeClump::NODE_END, NODE_STEP = CNodeClump::NODE_STEP, HASH_INVALID_SIGNATURE = CNodeClump::HASH_INVALID_SIGNATURE, };
CLKRLinearHashTable_Iterator( CLKRLinearHashTable* plht, PNodeClump pnc, DWORD dwBucketAddr, NodeIndex iNode) : m_plht(plht), m_pnc(pnc), m_dwBucketAddr(dwBucketAddr), m_iNode(iNode) { LKR_ITER_TRACE(_TEXT(" LKLH::prot ctor, this=%p, plht=%p, ") _TEXT("pnc=%p, ba=%d, in=%d\n"), this, plht, pnc, dwBucketAddr, iNode); }
inline void _AddRef( LK_ADDREF_REASON lkar) const;
bool _Increment( bool fDecrementOldValue=true);
NodeIndex _NodesPerClump() const { return NODES_PER_CLUMP; } NodeIndex _NodeBegin() const { return NODE_BEGIN; } NodeIndex _NodeEnd() const { return NODE_END; } NodeIndex _NodeStep() const { return NODE_STEP; }
public: CLKRLinearHashTable_Iterator() : m_plht(NULL), m_pnc(NULL), m_dwBucketAddr(0), m_iNode(0) { LKR_ITER_TRACE(_TEXT(" LKLH::default ctor, this=%p\n"), this); }
CLKRLinearHashTable_Iterator( const CLKRLinearHashTable_Iterator& rhs) : m_plht(rhs.m_plht), m_pnc(rhs.m_pnc), m_dwBucketAddr(rhs.m_dwBucketAddr), m_iNode(rhs.m_iNode) { LKR_ITER_TRACE(_TEXT(" LKLH::copy ctor, this=%p, rhs=%p\n"), this, &rhs); _AddRef(LKAR_ITER_COPY_CTOR); }
CLKRLinearHashTable_Iterator& operator=( const CLKRLinearHashTable_Iterator& rhs) { LKR_ITER_TRACE(_TEXT(" LKLH::operator=, this=%p, rhs=%p\n"), this, &rhs); rhs._AddRef(LKAR_ITER_ASSIGN_ACQUIRE); this->_AddRef(LKAR_ITER_ASSIGN_RELEASE);
m_plht = rhs.m_plht; m_pnc = rhs.m_pnc; m_dwBucketAddr = rhs.m_dwBucketAddr; m_iNode = rhs.m_iNode;
return *this; }
~CLKRLinearHashTable_Iterator() { LKR_ITER_TRACE(_TEXT(" LKLH::dtor, this=%p, plht=%p\n"), this, m_plht); _AddRef(LKAR_ITER_DTOR); }
bool Increment() { return IsValid() ? _Increment() : false;
}
bool IsValid() const { bool fValid = (m_plht != NULL && m_pnc != NULL && 0 <= m_iNode && m_iNode < NODES_PER_CLUMP); if (fValid) fValid = (m_pnc->m_dwKeySigs[m_iNode] != HASH_INVALID_SIGNATURE); IRTLASSERT(fValid); return fValid; }
const void* Record() const { IRTLASSERT(IsValid()); return m_pnc->m_pvNode[m_iNode]; }
inline const DWORD_PTR Key() const;
bool operator==( const CLKRLinearHashTable_Iterator& rhs) const { LKR_ITER_TRACE(_TEXT(" LKLH::operator==, this=%p, rhs=%p\n"), this, &rhs); // m_pnc and m_iNode uniquely identify an iterator
bool fEQ = ((m_pnc == rhs.m_pnc) // most unique field
&& (m_iNode == rhs.m_iNode)); IRTLASSERT(!fEQ || ((m_plht == rhs.m_plht) && (m_dwBucketAddr == rhs.m_dwBucketAddr))); return fEQ; }
bool operator!=( const CLKRLinearHashTable_Iterator& rhs) const { LKR_ITER_TRACE(_TEXT(" LKLH::operator!=, this=%p, rhs=%p\n"), this, &rhs); bool fNE = ((m_pnc != rhs.m_pnc) || (m_iNode != rhs.m_iNode)); //// IRTLASSERT(fNE == !this->operator==(rhs));
return fNE; }}; // class CLKRLinearHashTable_Iterator
class IRTL_DLLEXP CLKRHashTable_Iterator{ friend class CLKRHashTable;
protected: typedef short SubTableIndex;
// order important to minimize size
CLKRHashTable* m_pht; // which hash table?
CLKRLinearHashTable_Iterator m_subiter; // iterator into subtable
SubTableIndex m_ist; // index of subtable
CLKRHashTable_Iterator( CLKRHashTable* pht, SubTableIndex ist) : m_pht(pht), m_subiter(CLKRLinearHashTable_Iterator()), // zero
m_ist(ist) { LKR_ITER_TRACE(_TEXT(" LKHT::prot ctor, this=%p, pht=%p, ist=%d\n"), this, pht, ist); }
bool _Increment( bool fDecrementOldValue=true);
public: CLKRHashTable_Iterator() : m_pht(NULL), m_subiter(CLKRLinearHashTable_Iterator()), // zero
m_ist(0) { LKR_ITER_TRACE(_TEXT(" LKHT::default ctor, this=%p\n"), this); }
#ifdef IRTLDEBUG
// Compiler does a perfectly adequate job of synthesizing these methods.
CLKRHashTable_Iterator( const CLKRHashTable_Iterator& rhs) : m_pht(rhs.m_pht), m_subiter(rhs.m_subiter), m_ist(rhs.m_ist) { LKR_ITER_TRACE(_TEXT(" LKHT::copy ctor, this=%p, rhs=%p\n"), this, &rhs); }
CLKRHashTable_Iterator& operator=( const CLKRHashTable_Iterator& rhs) { LKR_ITER_TRACE(_TEXT(" LKHT::operator=, this=%p, rhs=%p\n"), this, &rhs);
m_ist = rhs.m_ist; m_subiter = rhs.m_subiter; m_pht = rhs.m_pht;
return *this; }
~CLKRHashTable_Iterator() { LKR_ITER_TRACE(_TEXT(" LKHT::dtor, this=%p, pht=%p\n"), this, m_pht); }#endif // IRTLDEBUG
bool Increment() { return IsValid() ? _Increment() : false; }
bool IsValid() const { bool fValid = (m_pht != NULL && m_ist >= 0); IRTLASSERT(fValid); fValid = fValid && (m_subiter.m_plht != NULL); IRTLASSERT(fValid); fValid = fValid && (m_subiter.m_pnc != NULL); IRTLASSERT(fValid); fValid = fValid && (0 <= m_subiter.m_iNode); IRTLASSERT(fValid); fValid = fValid && (m_subiter.m_iNode < CNodeClump::NODES_PER_CLUMP); IRTLASSERT(fValid);
if (fValid) { fValid = (m_subiter.m_pnc->m_dwKeySigs[m_subiter.m_iNode] != CNodeClump::HASH_INVALID_SIGNATURE); } IRTLASSERT(fValid); return fValid; }
const void* Record() const { IRTLASSERT(IsValid()); return m_subiter.Record(); }
const DWORD_PTR Key() const { IRTLASSERT(IsValid()); return m_subiter.Key(); }
bool operator==( const CLKRHashTable_Iterator& rhs) const { LKR_ITER_TRACE(_TEXT(" LKHT::operator==, this=%p, rhs=%p\n"), this, &rhs); // m_pnc and m_iNode uniquely identify an iterator
bool fEQ = ((m_subiter.m_pnc == rhs.m_subiter.m_pnc) // most unique field
&& (m_subiter.m_iNode == rhs.m_subiter.m_iNode)); IRTLASSERT(!fEQ || ((m_ist == rhs.m_ist) && (m_pht == rhs.m_pht) && (m_subiter.m_plht == rhs.m_subiter.m_plht) && (m_subiter.m_dwBucketAddr == rhs.m_subiter.m_dwBucketAddr))); return fEQ; }
bool operator!=( const CLKRHashTable_Iterator& rhs) const { LKR_ITER_TRACE(_TEXT(" LKHT::operator!=, this=%p, rhs=%p\n"), this, &rhs); bool fNE = ((m_subiter.m_pnc != rhs.m_subiter.m_pnc) || (m_subiter.m_iNode != rhs.m_subiter.m_iNode)); //// IRTLASSERT(fNE == !this->operator==(rhs));
return fNE; }}; // class CLKRHashTable_Iterator
#endif // LKR_STL_ITERATORS
//--------------------------------------------------------------------
// CLKRLinearHashTable
//
// A thread-safe linear hash (sub)table.
//--------------------------------------------------------------------
class IRTL_DLLEXP CLKRLinearHashTable{public: typedef LKR_TABLE_LOCK TableLock; typedef LKR_BUCKET_LOCK BucketLock;
#ifdef LKR_DEPRECATED_ITERATORS
class CIterator; friend class CLKRLinearHashTable::CIterator;#endif // LKR_DEPRECATED_ITERATORS
#ifdef LKR_STL_ITERATORS
friend class CLKRLinearHashTable_Iterator; typedef CLKRLinearHashTable_Iterator Iterator;#endif // LKR_STL_ITERATORS
private: friend class CNodeClump; friend class CLKRHashTable;
#ifdef LKRHASH_INSTRUMENTATION
// TODO
#endif // LKRHASH_INSTRUMENTATION
public:
// aliases for convenience
enum { MIN_DIRSIZE_BITS = 2, // min size for directory of segments
MIN_DIRSIZE = 1u << MIN_DIRSIZE_BITS, MAX_DIRSIZE_BITS = 20, // max size for directory of segments
MAX_DIRSIZE = 1u << MAX_DIRSIZE_BITS, NODES_PER_CLUMP = CNodeClump::NODES_PER_CLUMP, NODE_BEGIN = CNodeClump::NODE_BEGIN, NODE_END = CNodeClump::NODE_END, NODE_STEP = CNodeClump::NODE_STEP, HASH_INVALID_SIGNATURE = CNodeClump::HASH_INVALID_SIGNATURE, NAME_SIZE = 24, // CHARs, includes trailing '\0'
MAX_LKR_SUBTABLES = MAXIMUM_PROCESSORS, // 64 on Win64, 32 on W32
INVALID_PARENT_INDEX = 128, };
typedef CNodeClump::NodeIndex NodeIndex;
private:
//
// Miscellaneous helper functions
//
LKRHASH_CLASS_INIT_DECLS(CLKRLinearHashTable);
// Convert a hash signature to a bucket address
inline DWORD _BucketAddress(DWORD dwSignature) const;
// See the Linear Hashing paper
inline static DWORD _H0(DWORD dwSignature, DWORD dwBktAddrMask);
inline DWORD _H0(DWORD dwSignature) const;
// See the Linear Hashing paper. Preserves one bit more than _H0.
inline static DWORD _H1(DWORD dwSignature, DWORD dwBktAddrMask);
inline DWORD _H1(DWORD dwSignature) const;
// In which segment within the directory does the bucketaddress lie?
// (Return type must be lvalue so that it can be assigned to.)
inline PSegment& _Segment(DWORD dwBucketAddr) const;
// Offset within the segment of the bucketaddress
inline DWORD _SegIndex(DWORD dwBucketAddr) const;
// Convert a bucketaddress to a PBucket
inline PBucket _BucketFromAddress(DWORD dwBucketAddr) const;
// Number of nodes in a CNodeClump
inline NodeIndex _NodesPerClump() const;
// Index of first node in a CNodeClump
inline NodeIndex _NodeBegin() const;
// Index of last node in a CNodeClump
inline NodeIndex _NodeEnd() const;
// Advance from _NodeBegin() to _NodeEnd() by this increment
inline NodeIndex _NodeStep() const;
// Use bucket locks or not?
inline bool _UseBucketLocking() const;
// Move the expansion index forward by one.
inline void _IncrementExpansionIndex();
// Move the expansion index back by one.
inline void _DecrementExpansionIndex();
// Extract the key from a record
inline const DWORD_PTR _ExtractKey(const void* pvRecord) const;
// Hash the key
inline DWORD _CalcKeyHash(const DWORD_PTR pnKey) const;
// Compare two keys for equality
inline int _CompareKeys(const DWORD_PTR pnKey1, const DWORD_PTR pnKey2) const;
// AddRef or Release a record.
inline LONG _AddRefRecord(const void* pvRecord, LK_ADDREF_REASON lkar) const;
// Used by _FindKey so that the thread won't deadlock if the user has
// already explicitly called subtable->WriteLock().
inline bool _ReadOrWriteLock() const;
inline void _ReadOrWriteUnlock(bool fReadLocked) const;
// Memory allocation wrappers to allow us to simulate allocation
// failures during testing
PSegment* const _AllocateSegmentDirectory( size_t n);
bool _FreeSegmentDirectory();
PNodeClump const _AllocateNodeClump() const;
bool _FreeNodeClump( PNodeClump pnc) const;
CSegment* const _AllocateSegment() const;
bool _FreeSegment( CSegment* pseg) const;
#ifdef LOCK_INSTRUMENTATION
static LONG sm_cTables;
static const TCHAR* _LockName() { LONG l = ++sm_cTables; // possible race condition but we don't care, as this is never
// used in production code
static TCHAR s_tszName[CLockStatistics::L_NAMELEN]; wsprintf(s_tszName, _TEXT("LH%05x"), 0xFFFFF & l); return s_tszName; }
// Statistics for the subtable lock
CLockStatistics _LockStats() const { return m_Lock.Statistics(); }#endif // LOCK_INSTRUMENTATION
private: // Fields are ordered so as to minimize number of cache lines touched
DWORD m_dwSignature; // debugging: id & corruption check
// Put the table lock in the first cache line, far away from the other
// volatile fields.
mutable TableLock m_Lock; // Lock on entire linear hash subtable
const bool m_fUseLocks; // Must use locks to protect data
bool m_fSealed; // no further updates allowed
mutable LK_RETCODE m_lkrcState; // Internal state of subtable
CHAR m_szName[NAME_SIZE];// an identifier for debugging
// type-specific function pointers
LKR_PFnExtractKey m_pfnExtractKey; // Extract key from record
LKR_PFnCalcKeyHash m_pfnCalcKeyHash; // Calculate hash signature of key
LKR_PFnCompareKeys m_pfnCompareKeys; // Compare two keys
LKR_PFnAddRefRecord m_pfnAddRefRecord; // AddRef a record
BYTE m_MaxLoad; // max load factor (average chain length)
BYTE m_nLevel; // number of subtable doublings performed
BYTE m_lkts; // "size" of subtable: small/medium/large
BYTE m_nSegBits; // C{Small,Medium,Large}Segment::SEGBITS
WORD m_nSegSize; // C{Small,Medium,Large}Segment::SEGSIZE
WORD m_nSegMask; // C{Small,Medium,Large}Segment::SEGMASK
DWORD m_dwBktAddrMask0; // mask used for address calculation
DWORD m_dwBktAddrMask1; // used in _H1 calculation
DWORD m_cDirSegs; // segment directory size: varies between
// MIN_DIRSIZE and MAX_DIRSIZE
PSegment* m_paDirSegs; // directory of subtable segments
PSegment m_aDirSegs[MIN_DIRSIZE]; // inlined directory, adequate
// for many subtables
// These three fields are fairly volatile, but tend to be adjusted
// at the same time. Keep them well away from the TableLock.
DWORD m_iExpansionIdx; // address of next bucket to be expanded
DWORD m_cRecords; // number of records in the subtable
DWORD m_cActiveBuckets; // number of buckets in use (subtable size)
const BYTE m_nTableLockType; // for debugging: LOCK_READERWRITERLOCK4
const BYTE m_nBucketLockType;// for debugging: e.g., LOCK_SPINLOCK
WORD m_wBucketLockSpins;// default spin count for bucket locks
const CLKRHashTable* const m_phtParent;// Owning table. NULL => standalone
const BYTE m_iParentIndex; // index within parent table
const bool m_fMultiKeys; // Allow multiple identical keys?
const bool m_fNonPagedAllocs;// Use paged or NP pool in kernel
BYTE m_Dummy1;
// Reserve some space for future debugging needs
DWORD_PTR m_pvReserved1; DWORD_PTR m_pvReserved2; DWORD_PTR m_pvReserved3; DWORD_PTR m_pvReserved4;
#ifndef LKR_NO_GLOBAL_LIST
CListEntry m_leGlobalList;
static CLockedDoubleList sm_llGlobalList;// All active CLKRLinearHashTables
#endif // !LKR_NO_GLOBAL_LIST
DECLARE_ALLOC_STAT(SegDir); DECLARE_ALLOC_STAT(Segment); DECLARE_ALLOC_STAT(NodeClump);
DECLARE_OP_STAT(InsertRecord); DECLARE_OP_STAT(FindKey); DECLARE_OP_STAT(FindRecord); DECLARE_OP_STAT(DeleteKey); DECLARE_OP_STAT(DeleteRecord); DECLARE_OP_STAT(FindKeyMultiRec); DECLARE_OP_STAT(DeleteKeyMultiRec); DECLARE_OP_STAT(Expand); DECLARE_OP_STAT(Contract); DECLARE_OP_STAT(LevelExpansion); DECLARE_OP_STAT(LevelContraction); DECLARE_OP_STAT(ApplyIf); DECLARE_OP_STAT(DeleteIf);
// Non-trivial implementation functions
void _InsertThisIntoGlobalList(); void _RemoveThisFromGlobalList();
LK_RETCODE _InsertRecord( const void* pvRecord, const DWORD_PTR pnKey, const DWORD dwSignature, bool fOverwrite#ifdef LKR_STL_ITERATORS
, Iterator* piterResult=NULL#endif // LKR_STL_ITERATORS
); LK_RETCODE _DeleteKey( const DWORD_PTR pnKey, const DWORD dwSignature, const void** ppvRecord, bool fDeleteAllSame); LK_RETCODE _DeleteRecord( const void* pvRecord, const DWORD dwSignature); void _DeleteNode( PBucket const pbkt, PNodeClump& rpnc, PNodeClump& rpncPrev, NodeIndex& riNode, LK_ADDREF_REASON lkar); LK_RETCODE _FindKey( const DWORD_PTR pnKey, const DWORD dwSignature, const void** ppvRecord#ifdef LKR_STL_ITERATORS
, Iterator* piterResult=NULL#endif // LKR_STL_ITERATORS
) const; LK_RETCODE _FindRecord( const void* pvRecord, const DWORD dwSignature) const; LK_RETCODE _FindKeyMultipleRecords( const DWORD_PTR pnKey, const DWORD dwSignature, size_t* pcRecords, LKR_MULTIPLE_RECORDS** pplmr) const; LK_RETCODE _DeleteKeyMultipleRecords( const DWORD_PTR pnKey, const DWORD dwSignature, size_t* pcRecords, LKR_MULTIPLE_RECORDS** pplmr);
#ifdef LKR_APPLY_IF
// Predicate functions
static LK_PREDICATE WINAPI _PredTrue(const void* /*pvRecord*/, void* /*pvState*/) { return LKP_PERFORM; }
DWORD _ApplyIf( LKR_PFnRecordPred pfnPredicate, LKR_PFnRecordAction pfnAction, void* pvState, LK_LOCKTYPE lkl, LK_PREDICATE& rlkp); DWORD _DeleteIf( LKR_PFnRecordPred pfnPredicate, void* pvState, LK_PREDICATE& rlkp);#endif // LKR_APPLY_IF
// returns count of errors in compacted state => 0 is good
int _IsBucketChainCompact(PBucket const pbkt) const; int _IsBucketChainMultiKeySorted(PBucket const pbkt) const;
// helper functions
void _Clear(bool fShrinkDirectory); LK_RETCODE _SetSegVars(LK_TABLESIZE lkts, DWORD cInitialBuckets); LK_RETCODE _Expand(); LK_RETCODE _Contract(); LK_RETCODE _SplitBucketChain( PNodeClump pncOldTarget, PNodeClump pncNewTarget, const DWORD dwBktAddrMask, const DWORD dwNewBkt, PNodeClump pncFreeList); LK_RETCODE _AppendBucketChain( PBucket const pbktNewTarget, CNodeClump& rncOldFirst, PNodeClump pncFreeList); LK_RETCODE _MergeSortBucketChains( PBucket const pbktNewTarget, CNodeClump& rncOldFirst, PNodeClump pncFreeList);
// Private copy ctor and op= to prevent compiler synthesizing them.
// TODO: implement these properly; they could be useful.
CLKRLinearHashTable(const CLKRLinearHashTable&); CLKRLinearHashTable& operator=(const CLKRLinearHashTable&);
private: // This ctor is used by CLKRHashTable, the parent table
CLKRLinearHashTable( LPCSTR pszClassName, // Identifies subtable for debugging
LKR_PFnExtractKey pfnExtractKey, // Extract key from record
LKR_PFnCalcKeyHash pfnCalcKeyHash, // Calculate hash signature of key
LKR_PFnCompareKeys pfnCompareKeys, // Compare two keys
LKR_PFnAddRefRecord pfnAddRefRecord,// AddRef in FindKey, etc
unsigned maxload, // Upperbound on avg chain length
DWORD initsize, // Initial size of hash subtable
CLKRHashTable* phtParent, // Owning table.
int iParentIndex, // index within parent table
bool fMultiKeys, // Allow multiple identical keys?
bool fUseLocks, // Must use locks
bool fNonPagedAllocs // use paged or NP pool in kernel
);
// Does all the common work of the constructors
LK_RETCODE _Initialize( LKR_PFnExtractKey pfnExtractKey, LKR_PFnCalcKeyHash pfnCalcKeyHash, LKR_PFnCompareKeys pfnCompareKeys, LKR_PFnAddRefRecord pfnAddRefRecord, LPCSTR pszClassName, unsigned maxload, DWORD initsize);
public: CLKRLinearHashTable( LPCSTR pszClassName, // Identifies subtable for debugging
LKR_PFnExtractKey pfnExtractKey, // Extract key from record
LKR_PFnCalcKeyHash pfnCalcKeyHash, // Calculate hash signature of key
LKR_PFnCompareKeys pfnCompareKeys, // Compare two keys
LKR_PFnAddRefRecord pfnAddRefRecord,// AddRef in FindKey, etc
unsigned maxload=LK_DFLT_MAXLOAD,// Upperbound on average chain length
DWORD initsize=LK_DFLT_INITSIZE, // Initial size of hash subtable.
DWORD num_subtbls=LK_DFLT_NUM_SUBTBLS, // for signature compatiblity
// with CLKRHashTable
bool fMultiKeys=false,// Allow multiple identical keys?
bool fUseLocks=true // Must use locks
#ifdef LKRHASH_KERNEL_MODE
, bool fNonPagedAllocs=true // use paged or NP pool
#endif
);
~CLKRLinearHashTable();
static const TCHAR* ClassName() {return _TEXT("CLKRLinearHashTable");}
unsigned NumSubTables() const {return 1;}
bool MultiKeys() const { return m_fMultiKeys; }
bool UsingLocks() const { return m_fUseLocks; }
#ifdef LKRHASH_KERNEL_MODE
bool NonPagedAllocs() const { return m_fNonPagedAllocs; }#endif
static LK_TABLESIZE NumSubTables(DWORD& rinitsize, DWORD& rnum_subtbls);
// Insert a new record into hash subtable.
// Returns LK_SUCCESS if all OK, LK_KEY_EXISTS if same key already
// exists (unless fOverwrite), LK_ALLOC_FAIL if out of space,
// or LK_BAD_RECORD for a bad record.
LK_RETCODE InsertRecord( const void* pvRecord, bool fOverwrite=false) { if (!IsUsable()) return m_lkrcState;
#ifndef LKR_ALLOW_NULL_RECORDS
if (pvRecord == NULL) return LK_BAD_RECORD;#endif
const DWORD_PTR pnKey = _ExtractKey(pvRecord);
return _InsertRecord(pvRecord, pnKey, _CalcKeyHash(pnKey), fOverwrite); }
// Delete record with the given key.
// Returns LK_SUCCESS if all OK, or LK_NO_SUCH_KEY if not found
LK_RETCODE DeleteKey( const DWORD_PTR pnKey, const void** ppvRecord=NULL, bool fDeleteAllSame=false) { if (!IsUsable()) return m_lkrcState;
if (ppvRecord != NULL) *ppvRecord = NULL;
return _DeleteKey(pnKey, _CalcKeyHash(pnKey), ppvRecord, fDeleteAllSame); }
// Delete a record from the subtable, if present.
// Returns LK_SUCCESS if all OK, or LK_NO_SUCH_KEY if not found
LK_RETCODE DeleteRecord( const void* pvRecord) { if (!IsUsable()) return m_lkrcState;
#ifndef LKR_ALLOW_NULL_RECORDS
if (pvRecord == NULL) return LK_BAD_RECORD;#endif
return _DeleteRecord(pvRecord, _CalcKeyHash(_ExtractKey(pvRecord))); }
// Find record with given key.
// Returns: LK_SUCCESS, if record found (record is returned in *ppvRecord)
// LK_BAD_RECORD, if ppvRecord is invalid
// LK_NO_SUCH_KEY, if no record with given key value was found
// LK_UNUSABLE, if hash subtable not in usable state
// Note: the record is AddRef'd. You must decrement the reference
// count when you are finished with the record (if you're implementing
// refcounting semantics).
LK_RETCODE FindKey( const DWORD_PTR pnKey, const void** ppvRecord) const { if (!IsUsable()) return m_lkrcState;
if (ppvRecord == NULL) return LK_BAD_RECORD;
return _FindKey(pnKey, _CalcKeyHash(pnKey), ppvRecord); }
// Sees if the record is contained in the subtable
// Returns: LK_SUCCESS, if record found
// LK_BAD_RECORD, if pvRecord is invalid
// LK_NO_SUCH_KEY, if record is not in the subtable
// LK_UNUSABLE, if hash subtable not in usable state
// Note: the record is *not* AddRef'd.
LK_RETCODE FindRecord( const void* pvRecord) const { if (!IsUsable()) return m_lkrcState;
#ifndef LKR_ALLOW_NULL_RECORDS
if (pvRecord == NULL) return LK_BAD_RECORD;#endif
return _FindRecord(pvRecord, _CalcKeyHash(_ExtractKey(pvRecord))); }
LK_RETCODE FindKeyMultipleRecords( const DWORD_PTR pnKey, size_t* pcRecords, LKR_MULTIPLE_RECORDS** pplmr=NULL) const { if (!IsUsable()) return m_lkrcState;
if (pcRecords == NULL) return LK_BAD_PARAMETERS;
return _FindKeyMultipleRecords(pnKey, _CalcKeyHash(pnKey), pcRecords, pplmr); }
LK_RETCODE DeleteKeyMultipleRecords( const DWORD_PTR pnKey, size_t* pcRecords, LKR_MULTIPLE_RECORDS** pplmr=NULL) { if (!IsUsable()) return m_lkrcState;
if (pcRecords == NULL) return LK_BAD_PARAMETERS;
return _DeleteKeyMultipleRecords(pnKey, _CalcKeyHash(pnKey), pcRecords, pplmr); }
static LK_RETCODE FreeMultipleRecords(LKR_MULTIPLE_RECORDS* plmr);
#ifdef LKR_APPLY_IF
// Walk the hash subtable, applying pfnAction to all records.
// Locks the whole subtable for the duration with either a (possibly
// shared) readlock or a writelock, according to lkl.
// Loop is aborted if pfnAction returns LKA_ABORT.
// Returns the number of successful applications.
DWORD Apply( LKR_PFnRecordAction pfnAction, void* pvState=NULL, LK_LOCKTYPE lkl=LKL_READLOCK);
// Walk the hash subtable, applying pfnAction to any records that match
// pfnPredicate. Locks the whole subtable for the duration with either
// a (possibly shared) readlock or a writelock, according to lkl.
// Loop is aborted if pfnAction returns LKA_ABORT.
// Returns the number of successful applications.
DWORD ApplyIf( LKR_PFnRecordPred pfnPredicate, LKR_PFnRecordAction pfnAction, void* pvState=NULL, LK_LOCKTYPE lkl=LKL_READLOCK);
// Delete any records that match pfnPredicate.
// Locks the subtable for the duration with a writelock.
// Returns the number of deletions.
//
// Do *not* walk the hash table by hand with an iterator and call
// DeleteKey. The iterator will end up pointing to garbage.
DWORD DeleteIf( LKR_PFnRecordPred pfnPredicate, void* pvState=NULL);#endif // LKR_APPLY_IF
// Check subtable for consistency. Returns 0 if okay, or the number of
// errors otherwise.
int CheckTable() const;
// Remove all data from the subtable
void Clear() { WriteLock(); _Clear(true); WriteUnlock(); }
// Number of elements in the subtable
DWORD Size() const { return m_cRecords; }
// Maximum possible number of elements in the subtable
DWORD MaxSize() const { return static_cast<DWORD>(m_MaxLoad * MAX_DIRSIZE * m_nSegSize); }
// Get hash subtable statistics
CLKRHashTableStats GetStatistics() const;
// Is the hash subtable usable?
bool IsUsable() const { return (m_lkrcState == LK_SUCCESS); }
// Is the hash subtable consistent and correct?
bool IsValid() const { STATIC_ASSERT(((MIN_DIRSIZE & (MIN_DIRSIZE-1)) == 0) // == (1 << N)
&& ((1 << 2) <= MIN_DIRSIZE) && (MIN_DIRSIZE < MAX_DIRSIZE) && ((MAX_DIRSIZE & (MAX_DIRSIZE-1)) == 0) && (MAX_DIRSIZE <= (1 << 30)));
bool f = (m_lkrcState == LK_SUCCESS // serious internal failure?
&& m_paDirSegs != NULL && MIN_DIRSIZE <= m_cDirSegs && m_cDirSegs <= MAX_DIRSIZE && (m_cDirSegs & (m_cDirSegs-1)) == 0 && m_pfnExtractKey != NULL && m_pfnCalcKeyHash != NULL && m_pfnCompareKeys != NULL && m_pfnAddRefRecord != NULL && m_cActiveBuckets > 0 && ValidSignature() ); if (!f) m_lkrcState = LK_UNUSABLE; return f; }
// Set the spin count on the subtable lock
void SetTableLockSpinCount(WORD wSpins);
// Get the spin count on the subtable lock
WORD GetTableLockSpinCount() const;
// Set/Get the spin count on the bucket locks
void SetBucketLockSpinCount(WORD wSpins); WORD GetBucketLockSpinCount() const;
enum { SIGNATURE = (('L') | ('K' << 8) | ('L' << 16) | ('H' << 24)), SIGNATURE_FREE = (('L') | ('K' << 8) | ('L' << 16) | ('x' << 24)), };
bool ValidSignature() const { return m_dwSignature == SIGNATURE;}
#ifdef LKR_EXPOSED_TABLE_LOCK
public:#else // !LKR_EXPOSED_TABLE_LOCK
protected:#endif // !LKR_EXPOSED_TABLE_LOCK
//
// Lock manipulators
//
// Lock the subtable (exclusively) for writing
void WriteLock() { m_Lock.WriteLock(); }
// Lock the subtable (possibly shared) for reading
void ReadLock() const { m_Lock.ReadLock(); }
// Unlock the subtable for writing
void WriteUnlock() { m_Lock.WriteUnlock(); }
// Unlock the subtable for reading
void ReadUnlock() const { m_Lock.ReadUnlock(); }
// Is the subtable already locked for writing?
bool IsWriteLocked() const { return m_Lock.IsWriteLocked(); }
// Is the subtable already locked for reading?
bool IsReadLocked() const { return m_Lock.IsReadLocked(); }
// Is the subtable unlocked for writing?
bool IsWriteUnlocked() const { return m_Lock.IsWriteUnlocked(); }
// Is the subtable unlocked for reading?
bool IsReadUnlocked() const { return m_Lock.IsReadUnlocked(); }
// Convert the read lock to a write lock
void ConvertSharedToExclusive() { m_Lock.ConvertSharedToExclusive(); }
// Convert the write lock to a read lock
void ConvertExclusiveToShared() const { m_Lock.ConvertExclusiveToShared(); }
#ifdef LKRHASH_KERNEL_MODE
LKRHASH_ALLOCATOR_DEFINITIONS(CLKRLinearHashTable);#endif // LKRHASH_KERNEL_MODE
#ifdef LKR_DEPRECATED_ITERATORS
// These iterators are deprecated. Use the STL-style iterators instead.
public:
// Iterators can be used to walk the subtable. To ensure a consistent
// view of the data, the iterator locks the whole subtable. This can
// have a negative effect upon performance, because no other thread
// can do anything with the subtable. Use with care.
//
// You should not use an iterator to walk the subtable, calling DeleteKey,
// as the iterator will end up pointing to garbage.
//
// Use Apply, ApplyIf, or DeleteIf instead of iterators to safely
// walk the tree. Or use the STL-style iterators.
//
// Note that iterators acquire a reference to the record pointed to
// and release that reference as soon as the iterator is incremented.
// In other words, this code is safe:
// lkrc = ht.IncrementIterator(&iter);
// // assume lkrc == LK_SUCCESS for the sake of this example
// CMyHashTable::Record* pRec = iter.Record();
// Foo(pRec); // uses pRec but doesn't hang on to it
// lkrc = ht.IncrementIterator(&iter);
//
// But this code is not safe because pRec is used out of the scope of
// the iterator that provided it:
// lkrc = ht.IncrementIterator(&iter);
// CMyHashTable::Record* pRec = iter.Record();
// // Broken code: Should have called
// // ht.AddRefRecord(pRec, LKAR_EXPLICIT_ACQUIRE) here
// lkrc = ht.IncrementIterator(&iter);
// Foo(pRec); // Unsafe: because no longer have a valid reference
//
// If the record has no reference-counting semantics, then you can
// ignore the above remarks about scope.
class CIterator { protected: friend class CLKRLinearHashTable;
CLKRLinearHashTable* m_plht; // which linear hash subtable?
DWORD m_dwBucketAddr; // bucket index
PNodeClump m_pnc; // a CNodeClump in bucket
NodeIndex m_iNode; // offset within m_pnc
LK_LOCKTYPE m_lkl; // readlock or writelock?
private: // Private copy ctor and op= to prevent compiler synthesizing them.
// TODO: implement these properly; they could be useful.
CIterator(const CIterator&); CIterator& operator=(const CIterator&);
public: CIterator( LK_LOCKTYPE lkl=LKL_WRITELOCK) : m_plht(NULL), m_dwBucketAddr(0), m_pnc(NULL), m_iNode(-1), m_lkl(lkl) {}
// Return the record associated with this iterator
const void* Record() const { IRTLASSERT(IsValid());
return ((m_pnc != NULL && m_iNode >= 0 && m_iNode < CLKRLinearHashTable::NODES_PER_CLUMP) ? m_pnc->m_pvNode[m_iNode] : NULL); }
// Return the key associated with this iterator
const DWORD_PTR Key() const { IRTLASSERT(m_plht != NULL); const void* pRec = Record(); return ((m_plht != NULL) ? m_plht->_ExtractKey(pRec) : NULL); }
bool IsValid() const { return ((m_plht != NULL) && (m_pnc != NULL) && (0 <= m_iNode && m_iNode < CLKRLinearHashTable::NODES_PER_CLUMP) && (!m_pnc->IsEmptyNode(m_iNode))); }
// Delete the record that the iterator points to. Does an implicit
// IncrementIterator after deletion.
LK_RETCODE DeleteRecord();
// Change the record that the iterator points to. The new record
// must have the same key as the old one.
LK_RETCODE ChangeRecord(const void* pNewRec); }; // class CIterator
// Const iterators for readonly access. You must use these with
// const CLKRLinearHashTables.
class CConstIterator : public CIterator { private: // Private, unimplemented copy ctor and op= to prevent
// compiler synthesizing them.
CConstIterator(const CConstIterator&); CConstIterator& operator=(const CConstIterator&);
public: CConstIterator() : CIterator(LKL_READLOCK) {} }; // class CConstIterator
private: // The public APIs lock the subtable. The private ones, which are used
// directly by CLKRHashTable, don't.
LK_RETCODE _InitializeIterator(CIterator* piter); LK_RETCODE _CloseIterator(CIterator* piter);
public: // Initialize the iterator to point to the first item in the hash subtable
// Returns LK_SUCCESS, LK_NO_MORE_ELEMENTS, or LK_BAD_ITERATOR.
LK_RETCODE InitializeIterator(CIterator* piter) { IRTLASSERT(piter != NULL && piter->m_plht == NULL); if (piter == NULL || piter->m_plht != NULL) return LK_BAD_ITERATOR;
if (piter->m_lkl == LKL_WRITELOCK) WriteLock(); else ReadLock();
return _InitializeIterator(piter); }
// The const iterator version
LK_RETCODE InitializeIterator(CConstIterator* piter) const { IRTLASSERT(piter != NULL && piter->m_plht == NULL); IRTLASSERT(piter->m_lkl != LKL_WRITELOCK);
if (piter == NULL || piter->m_plht != NULL || piter->m_lkl == LKL_WRITELOCK) return LK_BAD_ITERATOR;
ReadLock(); return const_cast<CLKRLinearHashTable*>(this) ->_InitializeIterator(static_cast<CIterator*>(piter)); }
// Move the iterator on to the next item in the subtable.
// Returns LK_SUCCESS, LK_NO_MORE_ELEMENTS, or LK_BAD_ITERATOR.
LK_RETCODE IncrementIterator(CIterator* piter);
LK_RETCODE IncrementIterator(CConstIterator* piter) const { IRTLASSERT(piter != NULL && piter->m_plht == this); IRTLASSERT(piter->m_lkl != LKL_WRITELOCK);
if (piter == NULL || piter->m_plht != this || piter->m_lkl == LKL_WRITELOCK) return LK_BAD_ITERATOR;
return const_cast<CLKRLinearHashTable*>(this) ->IncrementIterator(static_cast<CIterator*>(piter)); }
// Close the iterator.
LK_RETCODE CloseIterator(CIterator* piter) { IRTLASSERT(piter != NULL && piter->m_plht == this); if (piter == NULL || piter->m_plht != this) return LK_BAD_ITERATOR; _CloseIterator(piter);
if (piter->m_lkl == LKL_WRITELOCK) WriteUnlock(); else ReadUnlock();
return LK_SUCCESS; };
// Close the CConstIterator
LK_RETCODE CloseIterator(CConstIterator* piter) const { IRTLASSERT(piter != NULL && piter->m_plht == this); IRTLASSERT(piter->m_lkl != LKL_WRITELOCK);
if (piter == NULL || piter->m_plht != this || piter->m_lkl == LKL_WRITELOCK) return LK_BAD_ITERATOR;
const_cast<CLKRLinearHashTable*>(this) ->_CloseIterator(static_cast<CIterator*>(piter));
ReadUnlock(); return LK_SUCCESS; };
#endif // LKR_DEPRECATED_ITERATORS
#ifdef LKR_STL_ITERATORS
private: bool _Erase(Iterator& riter, DWORD dwSignature); bool _Find(DWORD_PTR pnKey, DWORD dwSignature, Iterator& riterResult);
bool _IsValidIterator(const Iterator& riter) const { LKR_ITER_TRACE(_TEXT(" LKLH:_IsValidIterator(%p)\n"), &riter); bool fValid = ((riter.m_plht == this) && (riter.m_dwBucketAddr < m_cActiveBuckets) && riter.IsValid()); IRTLASSERT(fValid); return fValid; }
public: // Return iterator pointing to first item in subtable
Iterator Begin();
// Return a one-past-the-end iterator. Always empty.
Iterator End() const { LKR_ITER_TRACE(_TEXT(" LKLH::End\n")); return Iterator(); }
// Insert a record
// Returns `true' if successful; iterResult points to that record
// Returns `false' otherwise; iterResult == End()
bool Insert( /* in */ const void* pvRecord, /* out */ Iterator& riterResult, /* in */ bool fOverwrite=false);
// Erase the record pointed to by the iterator; adjust the iterator
// to point to the next record. Returns `true' if successful.
bool Erase( /* in,out */ Iterator& riter);
// Erase the records in the range [riterFirst, riterLast).
// Returns `true' if successful. riterFirst points to riterLast on return.
bool Erase( /*in*/ Iterator& riterFirst, /*in*/ Iterator& riterLast);
// Find the (first) record that has its key == pnKey.
// If successful, returns `true' and iterator points to (first) record.
// If fails, returns `false' and iterator == End()
bool Find( /* in */ DWORD_PTR pnKey, /* out */ Iterator& riterResult);
// Find the range of records that have their keys == pnKey.
// If successful, returns `true', iterFirst points to first record,
// and iterLast points to one-beyond-the last such record.
// If fails, returns `false' and both iterators == End().
// Primarily useful when m_fMultiKey == true
bool EqualRange( /* in */ DWORD_PTR pnKey, /* out */ Iterator& riterFirst, // inclusive
/* out */ Iterator& riterLast); // exclusive
#endif // LKR_STL_ITERATORS
}; // class CLKRLinearHashTable
#ifdef LKR_STL_ITERATORS
// These functions have to be defined after CLKRLinearHashTable
inline voidCLKRLinearHashTable_Iterator::_AddRef( LK_ADDREF_REASON lkar) const{ // TODO: should iterator call _AddRefRecord at all
if (m_plht != NULL && m_iNode != NODE_BEGIN - NODE_STEP) { IRTLASSERT((0 <= m_iNode && m_iNode < NODES_PER_CLUMP) && (unsigned) m_iNode < NODES_PER_CLUMP && m_pnc != NULL && (lkar < 0 || lkar > 0) ); const void* pvRecord = m_pnc->m_pvNode[m_iNode];#ifndef LKR_ALLOW_NULL_RECORDS
IRTLASSERT(pvRecord != NULL);#endif
LKR_ITER_TRACE(_TEXT(" LKLH::AddRef, this=%p, Rec=%p\n"), this, pvRecord); LONG cRefs = m_plht->_AddRefRecord(pvRecord, lkar); UNREFERENCED_PARAMETER(cRefs); IRTLASSERT(cRefs > 0); }} // CLKRLinearHashTable_Iterator::_AddRef
inline const DWORD_PTRCLKRLinearHashTable_Iterator::Key() const{ IRTLASSERT(IsValid()); return m_plht->_ExtractKey(m_pnc->m_pvNode[m_iNode]);} // CLKRLinearHashTable_Iterator::Key
#endif // LKR_STL_ITERATORS
//--------------------------------------------------------------------
// CLKRHashTable
//
// To improve concurrency, a hash table is divided into a number of
// (independent) subtables. Each subtable is a linear hash table. The
// number of subtables is defined when the outer table is created and remains
// fixed thereafter. Records are assigned to subtables based on their
// hashed key.
//
// For small or low-contention hashtables, you can bypass this
// thin wrapper and use CLKRLinearHashTable directly. The methods are
// documented in the declarations for CLKRHashTable (above).
//--------------------------------------------------------------------
class IRTL_DLLEXP CLKRHashTable{private: typedef CLKRLinearHashTable SubTable;
public: typedef SubTable::TableLock TableLock; typedef SubTable::BucketLock BucketLock;
#ifdef LKR_DEPRECATED_ITERATORS
class CIterator; friend class CLKRHashTable::CIterator;#endif // LKR_DEPRECATED_ITERATORS
#ifdef LKR_STL_ITERATORS
friend class CLKRHashTable_Iterator; typedef CLKRHashTable_Iterator Iterator;#endif // LKR_STL_ITERATORS
friend class CLKRLinearHashTable; friend int ::LKR_Initialize(DWORD dwInitFlags); friend void ::LKR_Terminate();
// aliases for convenience
enum { NAME_SIZE = SubTable::NAME_SIZE, HASH_INVALID_SIGNATURE = SubTable::HASH_INVALID_SIGNATURE, NODES_PER_CLUMP = SubTable::NODES_PER_CLUMP, MAX_LKR_SUBTABLES = SubTable::MAX_LKR_SUBTABLES, INVALID_PARENT_INDEX = SubTable::INVALID_PARENT_INDEX, };
private: // Hash table parameters
DWORD m_dwSignature; // debugging: id & corruption check
CHAR m_szName[NAME_SIZE]; // an identifier for debugging
mutable LK_RETCODE m_lkrcState; // Internal state of table
LKR_PFnExtractKey m_pfnExtractKey; LKR_PFnCalcKeyHash m_pfnCalcKeyHash; DWORD m_cSubTables; // number of subtables
int m_nSubTableMask; SubTable* m_palhtDir[MAX_LKR_SUBTABLES]; // array of subtables
#ifndef LKR_NO_GLOBAL_LIST
CListEntry m_leGlobalList;
static CLockedDoubleList sm_llGlobalList; // All active CLKRHashTables
#endif // !LKR_NO_GLOBAL_LIST
DECLARE_ALLOC_STAT(SubTable);
LKRHASH_GLOBAL_LOCK_DECLARATIONS();
LKRHASH_CLASS_INIT_DECLS(CLKRHashTable);
private: inline void _InsertThisIntoGlobalList(); inline void _RemoveThisFromGlobalList();
// Private copy ctor and op= to prevent compiler synthesizing them.
// TODO: implement these properly; they could be useful.
CLKRHashTable(const CLKRHashTable&); CLKRHashTable& operator=(const CLKRHashTable&);
// Extract the key from the record
inline const DWORD_PTR _ExtractKey(const void* pvRecord) const;
// Hash the key
inline DWORD _CalcKeyHash(const DWORD_PTR pnKey) const;
// Use the key's hash signature to multiplex into a subtable
inline SubTable* const _SubTable(DWORD dwSignature) const;
// Find the index of pst within the subtable array
inline int _SubTableIndex(SubTable* pst) const;
// Memory allocation wrappers to allow us to simulate allocation
// failures during testing
SubTable* const _AllocateSubTable( LPCSTR pszClassName, // Identifies table for debugging
LKR_PFnExtractKey pfnExtractKey, // Extract key from record
LKR_PFnCalcKeyHash pfnCalcKeyHash, // Calculate hash signature of key
LKR_PFnCompareKeys pfnCompareKeys, // Compare two keys
LKR_PFnAddRefRecord pfnAddRefRecord,// AddRef in FindKey, etc
unsigned maxload, // Upperbound on avg chain length
DWORD initsize, // Initial size of hash table.
CLKRHashTable* phtParent, // Owning table.
int iParentIndex, // index within parent table
bool fMultiKeys, // Allow multiple identical keys?
bool fUseLocks, // Must use locks
bool fNonPagedAllocs // use paged or NP pool in kernel
) const;
bool _FreeSubTable( SubTable* plht) const;
public: CLKRHashTable( LPCSTR pszClassName, // Identifies table for debugging
LKR_PFnExtractKey pfnExtractKey, // Extract key from record
LKR_PFnCalcKeyHash pfnCalcKeyHash, // Calculate hash signature of key
LKR_PFnCompareKeys pfnCompareKeys, // Compare two keys
LKR_PFnAddRefRecord pfnAddRefRecord,// AddRef in FindKey, etc
unsigned maxload=LK_DFLT_MAXLOAD, // bound on avg chain length
DWORD initsize=LK_DFLT_INITSIZE,// Initial size of hash table.
DWORD num_subtbls=LK_DFLT_NUM_SUBTBLS, // #subordinate hash tables.
bool fMultiKeys=false,// Allow multiple identical keys?
bool fUseLocks=true // Must use locks
#ifdef LKRHASH_KERNEL_MODE
, bool fNonPagedAllocs=true // use paged or NP pool
#endif
);
~CLKRHashTable();
static const TCHAR* ClassName() {return _TEXT("CLKRHashTable");}
unsigned NumSubTables() const {return m_cSubTables;}
bool MultiKeys() const;
#ifdef LKRHASH_KERNEL_MODE
bool NonPagedAllocs() const;#endif
static LK_TABLESIZE NumSubTables(DWORD& rinitsize, DWORD& rnum_subtbls);
// Thin wrappers for the corresponding methods in CLKRLinearHashTable
LK_RETCODE InsertRecord( const void* pvRecord, bool fOverwrite=false); LK_RETCODE DeleteKey( const DWORD_PTR pnKey, const void** ppvRecord=NULL, bool fDeleteAllSame=false); LK_RETCODE DeleteRecord( const void* pvRecord); LK_RETCODE FindKey( const DWORD_PTR pnKey, const void** ppvRecord) const; LK_RETCODE FindRecord( const void* pvRecord) const; LK_RETCODE FindKeyMultipleRecords( const DWORD_PTR pnKey, size_t* pcRecords, LKR_MULTIPLE_RECORDS** pplmr=NULL) const; LK_RETCODE DeleteKeyMultipleRecords( const DWORD_PTR pnKey, size_t* pcRecords, LKR_MULTIPLE_RECORDS** pplmr=NULL); static LK_RETCODE FreeMultipleRecords( LKR_MULTIPLE_RECORDS* plmr);
#ifdef LKR_APPLY_IF
DWORD Apply( LKR_PFnRecordAction pfnAction, void* pvState=NULL, LK_LOCKTYPE lkl=LKL_READLOCK); DWORD ApplyIf( LKR_PFnRecordPred pfnPredicate, LKR_PFnRecordAction pfnAction, void* pvState=NULL, LK_LOCKTYPE lkl=LKL_READLOCK); DWORD DeleteIf( LKR_PFnRecordPred pfnPredicate, void* pvState=NULL);#endif // LKR_APPLY_IF
void Clear(); int CheckTable() const; DWORD Size() const; DWORD MaxSize() const; CLKRHashTableStats GetStatistics() const; bool IsValid() const;
void SetTableLockSpinCount(WORD wSpins); WORD GetTableLockSpinCount() const; void SetBucketLockSpinCount(WORD wSpins); WORD GetBucketLockSpinCount() const;
enum { SIGNATURE = (('L') | ('K' << 8) | ('H' << 16) | ('T' << 24)), SIGNATURE_FREE = (('L') | ('K' << 8) | ('H' << 16) | ('x' << 24)), };
bool ValidSignature() const { return m_dwSignature == SIGNATURE;}
// Is the hash table usable?
bool IsUsable() const { return (m_lkrcState == LK_SUCCESS); }
#ifdef LKR_EXPOSED_TABLE_LOCK
public:#else // !LKR_EXPOSED_TABLE_LOCK
protected:#endif // !LKR_EXPOSED_TABLE_LOCK
void WriteLock(); void ReadLock() const; void WriteUnlock(); void ReadUnlock() const; bool IsWriteLocked() const; bool IsReadLocked() const; bool IsWriteUnlocked() const; bool IsReadUnlocked() const; void ConvertSharedToExclusive(); void ConvertExclusiveToShared() const;
#ifdef LKRHASH_KERNEL_MODE
LKRHASH_ALLOCATOR_DEFINITIONS(CLKRHashTable);#endif // LKRHASH_KERNEL_MODE
#ifdef LKR_DEPRECATED_ITERATORS
public:
typedef SubTable::CIterator CLHTIterator;
class CIterator : public CLHTIterator { protected: friend class CLKRHashTable;
CLKRHashTable* m_pht; // which hash table?
int m_ist; // which subtable
private: // Private copy ctor and op= to prevent compiler synthesizing them.
CIterator(const CIterator&); CIterator& operator=(const CIterator&);
public: CIterator( LK_LOCKTYPE lkl=LKL_WRITELOCK) : CLHTIterator(lkl), m_pht(NULL), m_ist(-1) {}
const void* Record() const { IRTLASSERT(IsValid());
// This is a hack to work around a compiler bug. Calling
// CLHTIterator::Record calls this function recursively until
// the stack overflows.
const CLHTIterator* pBase = static_cast<const CLHTIterator*>(this); return pBase->Record(); }
const DWORD_PTR Key() const { IRTLASSERT(IsValid()); const CLHTIterator* pBase = static_cast<const CLHTIterator*>(this); return pBase->Key(); }
bool IsValid() const { const CLHTIterator* pBase = static_cast<const CLHTIterator*>(this); return (m_pht != NULL && m_ist >= 0 && pBase->IsValid()); } };
// Const iterators for readonly access
class CConstIterator : public CIterator { private: // Private, unimplemented copy ctor and op= to prevent
// compiler synthesizing them.
CConstIterator(const CConstIterator&); CConstIterator& operator=(const CConstIterator&);
public: CConstIterator() : CIterator(LKL_READLOCK) {} };
public: LK_RETCODE InitializeIterator(CIterator* piter); LK_RETCODE IncrementIterator(CIterator* piter); LK_RETCODE CloseIterator(CIterator* piter);
LK_RETCODE InitializeIterator(CConstIterator* piter) const { IRTLASSERT(piter != NULL && piter->m_pht == NULL); IRTLASSERT(piter->m_lkl != LKL_WRITELOCK);
if (piter == NULL || piter->m_pht != NULL || piter->m_lkl == LKL_WRITELOCK) return LK_BAD_ITERATOR;
return const_cast<CLKRHashTable*>(this) ->InitializeIterator(static_cast<CIterator*>(piter)); }
LK_RETCODE IncrementIterator(CConstIterator* piter) const { IRTLASSERT(piter != NULL && piter->m_pht == this); IRTLASSERT(piter->m_lkl != LKL_WRITELOCK);
if (piter == NULL || piter->m_pht != this || piter->m_lkl == LKL_WRITELOCK) return LK_BAD_ITERATOR;
return const_cast<CLKRHashTable*>(this) ->IncrementIterator(static_cast<CIterator*>(piter)); }
LK_RETCODE CloseIterator(CConstIterator* piter) const { IRTLASSERT(piter != NULL && piter->m_pht == this); IRTLASSERT(piter->m_lkl != LKL_WRITELOCK);
if (piter == NULL || piter->m_pht != this || piter->m_lkl == LKL_WRITELOCK) return LK_BAD_ITERATOR;
return const_cast<CLKRHashTable*>(this) ->CloseIterator(static_cast<CIterator*>(piter)); };
#endif // LKR_DEPRECATED_ITERATORS
#ifdef LKR_STL_ITERATORS
private: bool _IsValidIterator(const Iterator& riter) const { LKR_ITER_TRACE(_TEXT(" LKHT:_IsValidIterator(%p)\n"), &riter); bool fValid = (riter.m_pht == this); IRTLASSERT(fValid); fValid = fValid && (0 <= riter.m_ist && riter.m_ist < (int) m_cSubTables); IRTLASSERT(fValid); IRTLASSERT(_SubTableIndex(riter.m_subiter.m_plht) == riter.m_ist); fValid = fValid && riter.IsValid(); IRTLASSERT(fValid); return fValid; }
public: Iterator Begin();
Iterator End() const { LKR_ITER_TRACE(_TEXT(" LKHT::End\n")); return Iterator(); }
bool Insert( /* in */ const void* pvRecord, /* out */ Iterator& riterResult, /* in */ bool fOverwrite=false);
bool Erase( /* in,out */ Iterator& riter);
bool Erase( /*in*/ Iterator& riterFirst, /*in*/ Iterator& riterLast);
bool Find( /* in */ DWORD_PTR pnKey, /* out */ Iterator& riterResult);
bool EqualRange( /* in */ DWORD_PTR pnKey, /* out */ Iterator& riterFirst, // inclusive
/* out */ Iterator& riterLast); // exclusive
#endif // LKR_STL_ITERATORS
}; // class CLKRHashTable
//--------------------------------------------------------------------
// A typesafe wrapper for CLKRHashTable (or CLKRLinearHashTable).
//
// * _Derived must derive from CTypedHashTable and provide certain member
// functions (ExtractKey, CalcKeyHash, CompareKeys, AddRefRecord). It's
// needed so that the method wrappers can downcast to the typesafe
// implementations that you provide.
// * _Record is the type of the record. C{Linear}HashTable will store
// >pointers< to _Record; i.e., stores _Records by reference, not by value.
// * _Key is the type of the key. _Key is used directly---it is not
// assumed to be a pointer type. _Key can be an integer or a pointer.
// C{Linear}HashTable assumes that the key is stored in the associated
// record. See the comments at the declaration of LKR_PFnExtractKey
// for more details.
// (optional parameters):
// * _BaseHashTable is the base hash table: CLKRHashTable or
/// CLKRLinearHashTable
// * _BaseIterator is the iterator type, _BaseHashTable::CIterator
//
// Some associative containers allow you to store key-value (aka
// name-value) pairs. LKRhash doesn't allow you to do this directly, but
// it's straightforward to build a simple wrapper class (or to use
// std::pair<key,value>).
//
// CTypedHashTable could derive directly from CLKRLinearHashTable, if you
// don't need the extra overhead of CLKRHashTable (which is quite low).
// If you expect to be using the table a lot on multiprocessor machines,
// you should use the default of CLKRHashTable, as it will scale better.
//
// You may need to add the following line to your code to disable
// warning messages about truncating extremly long identifiers.
// #pragma warning (disable : 4786)
//
// The _Derived class should look something like this:
// class CDerived : public CTypedHashTable<CDerived, RecordType, KeyType>
// {
// public:
// CDerived()
// : CTypedHashTable<CDerived, RecordType, KeyType>("DerivedTable")
// { /* other ctor actions, if needed */ }
// static KeyType ExtractKey(const RecordType* pTest);
// static DWORD CalcKeyHash(const KeyType Key);
// static int CompareKeys(const KeyType Key1, const KeyType Key2);
// static LONG AddRefRecord(RecordType* pRecord,LK_ADDREF_REASON lkar);
// // You probably want to declare the copy ctor and operator=
// // as private, so that the compiler won't synthesize them.
// // You don't need to provide a dtor, unless you have custom
// // member data to clean up.
//
// // Optional: other functions
// };
//
//--------------------------------------------------------------------
template < class _Derived, class _Record, class _Key, bool _fDoRefCounting=false, class _BaseHashTable=CLKRHashTable#ifdef LKR_DEPRECATED_ITERATORS
, class _BaseIterator=_BaseHashTable::CIterator#endif // LKR_DEPRECATED_ITERATORS
>class CTypedHashTable : public _BaseHashTable{public: // convenient aliases
typedef _Derived Derived; typedef _Record Record; typedef _Key Key; enum { REF_COUNTED = _fDoRefCounting }; typedef _BaseHashTable BaseHashTable;
typedef CTypedHashTable<_Derived, _Record, _Key, _fDoRefCounting, _BaseHashTable#ifdef LKR_DEPRECATED_ITERATORS
, _BaseIterator#endif // LKR_DEPRECATED_ITERATORS
> HashTable;
#ifdef LKR_DEPRECATED_ITERATORS
typedef _BaseIterator BaseIterator;#endif // LKR_DEPRECATED_ITERATORS
private: // Wrappers for the typesafe methods exposed by the derived class
static const DWORD_PTR WINAPI _ExtractKey(const void* pvRecord) { const _Record* pRec = static_cast<const _Record*>(pvRecord);
// I would prefer to use reinterpret_cast here and in _CalcKeyHash
// and _CompareKeys, but the stupid Win64 compiler thinks it knows
// better than I do.
const _Key key = _Derived::ExtractKey(pRec);
// const void* pvKey = reinterpret_cast<const void*>(key);
// const DWORD_PTR pnKey = reinterpret_cast<const DWORD_PTR>(pvKey);
const DWORD_PTR pnKey = (DWORD_PTR) key;
return pnKey; }
static DWORD WINAPI _CalcKeyHash(const DWORD_PTR pnKey1) { const void* pvKey1 = reinterpret_cast<const void*>(pnKey1); const DWORD_PTR pnKey1a = reinterpret_cast<const DWORD_PTR>(pvKey1);// const _Key key1 = reinterpret_cast<const _Key>(pnKey1a);
const _Key key1 = (const _Key) pnKey1a;
return _Derived::CalcKeyHash(key1); }
static int WINAPI _CompareKeys(const DWORD_PTR pnKey1, const DWORD_PTR pnKey2) { const void* pvKey1 = reinterpret_cast<const void*>(pnKey1); const DWORD_PTR pnKey1a = reinterpret_cast<const DWORD_PTR>(pvKey1);// const _Key key1 = reinterpret_cast<const _Key>(pnKey1a);
const _Key key1 = (const _Key) pnKey1a;
const void* pvKey2 = reinterpret_cast<const void*>(pnKey2); const DWORD_PTR pnKey2a = reinterpret_cast<const DWORD_PTR>(pvKey2);// const _Key key2 = reinterpret_cast<const _Key>(pnKey2a);
const _Key key2 = (const _Key) pnKey2a;
return _Derived::CompareKeys(key1, key2); }
static LONG WINAPI _AddRefRecord(void* pvRecord, LK_ADDREF_REASON lkar) { _Record* pRec = static_cast<_Record*>(pvRecord); return _Derived::AddRefRecord(pRec, lkar); }
#ifdef LKR_APPLY_IF
// Typesafe wrappers for Apply, ApplyIf, and DeleteIf.
public: // ApplyIf() and DeleteIf(): Does the record match the predicate?
// Note: takes a Record*, not a const Record*. You can modify the
// record in Pred() or Action(), if you like, but if you do, you
// should use LKL_WRITELOCK to lock the table. Also, you need to
// exercise care that you don't modify the key of the record.
typedef LK_PREDICATE (WINAPI *PFnRecordPred) (Record* pRec, void* pvState);
// Apply() et al: Perform action on record.
typedef LK_ACTION (WINAPI *PFnRecordAction)(Record* pRec, void* pvState);
protected: class CState { protected: friend class CTypedHashTable<_Derived, _Record, _Key, _fDoRefCounting, _BaseHashTable #ifdef LKR_DEPRECATED_ITERATORS
, _BaseIterator #endif // LKR_DEPRECATED_ITERATORS
>;
PFnRecordPred m_pfnPred; PFnRecordAction m_pfnAction; void* m_pvState;
public: CState( PFnRecordPred pfnPred, PFnRecordAction pfnAction, void* pvState) : m_pfnPred(pfnPred), m_pfnAction(pfnAction), m_pvState(pvState) {} };
static LK_PREDICATE WINAPI _Pred(const void* pvRecord, void* pvState) { _Record* pRec = static_cast<_Record*>(const_cast<void*>(pvRecord)); CState* pState = static_cast<CState*>(pvState);
return (*pState->m_pfnPred)(pRec, pState->m_pvState); }
static LK_ACTION WINAPI _Action(const void* pvRecord, void* pvState) { _Record* pRec = static_cast<_Record*>(const_cast<void*>(pvRecord)); CState* pState = static_cast<CState*>(pvState);
return (*pState->m_pfnAction)(pRec, pState->m_pvState); }#endif // LKR_APPLY_IF
protected: ~CTypedHashTable() { IRTLTRACE1("~CTypedHashTable(%p)\n", this); }
CTypedHashTable(const HashTable&); HashTable& operator=(const HashTable&);
private: template <bool> class CRefCount;
// Dummy, no-op specialization
template <> class CRefCount<false> { public: LONG Increment() { return 1; } LONG Decrement() { return 0; } };
// Real, threadsafe specialization
template <> class CRefCount<true> { public: CRefCount<true>() : m_cRefs(1) {} ~CRefCount<true>() { IRTLASSERT(0 == m_cRefs); } LONG Increment() { return ::InterlockedIncrement(&m_cRefs); } LONG Decrement() { return ::InterlockedDecrement(&m_cRefs); } private: LONG m_cRefs; };
mutable CRefCount<_fDoRefCounting> m_rc;
LONG _AddRef() const { return m_rc.Increment(); }
LONG _Release() const { const LONG cRefs = m_rc.Decrement();
if (0 == cRefs) { _Derived* pThis = static_cast<_Derived*>( const_cast<HashTable*>(this)); delete pThis; }
return cRefs; }
template <bool> class CAutoRefCountImpl;
typedef CAutoRefCountImpl<_fDoRefCounting> CAutoRefCount; friend typename CAutoRefCountImpl<_fDoRefCounting>; // friend typename CAutoRefCount;
// no-op specialization
template <> class CAutoRefCountImpl<false> { public: CAutoRefCountImpl<false>(const HashTable* const) {} };
// threadsafe specialization
template <> class CAutoRefCountImpl<true> { private: const HashTable* const m_pCont;
// At /W4, compiler complains that it can't generate operator=
CAutoRefCountImpl<true>& operator=(const CAutoRefCountImpl<true>&);
public: CAutoRefCountImpl<true>( const HashTable* const pCont) : m_pCont(pCont) { m_pCont->_AddRef(); }
~CAutoRefCountImpl<true>() { m_pCont->_Release(); } };
// Now at the top of an operation, we place a statement like this:
// CAutoRefCount arc(this);
//
// If we're using CAutoRefCountImpl<false>, the compiler optimizes it away.
//
// If we're using CAutoRefCountImpl<true>, we increment m_rc at this
// point. At the end of the function, the destructor calls _Release(),
// which will `delete this' if the last reference was released.
public: CTypedHashTable( LPCSTR pszClassName, // Identifies table for debugging
unsigned maxload=LK_DFLT_MAXLOAD, // Upperbound on avg chain len
DWORD initsize=LK_DFLT_INITSIZE, // Initial size of table: S/M/L
DWORD num_subtbls=LK_DFLT_NUM_SUBTBLS,// #subordinate hash tables.
bool fMultiKeys=false, // Allow multiple identical keys?
bool fUseLocks=true // Must use locks
#ifdef LKRHASH_KERNEL_MODE
, bool fNonPagedAllocs=true // use paged or NP pool in kernel
#endif
) : _BaseHashTable(pszClassName, _ExtractKey, _CalcKeyHash, _CompareKeys, _AddRefRecord, maxload, initsize, num_subtbls, fMultiKeys, fUseLocks#ifdef LKRHASH_KERNEL_MODE
, fNonPagedAllocs#endif
) { // Ensure that _Key is no bigger than a pointer. Because we
// support both numeric and pointer keys, the various casts
// in the member functions unfortunately silently truncate if
// _Key is an unacceptable numeric type, such as __int64 on x86.
STATIC_ASSERT(sizeof(_Key) <= sizeof(DWORD_PTR)); }
LK_RETCODE InsertRecord(const _Record* pRec, bool fOverwrite=false) { CAutoRefCount arc(this);
return _BaseHashTable::InsertRecord(pRec, fOverwrite); }
LK_RETCODE DeleteKey(const _Key key, _Record** ppRec=NULL, bool fDeleteAllSame=false) { CAutoRefCount arc(this);
// const void* pvKey = reinterpret_cast<const void*>(key);
// DWORD_PTR pnKey = reinterpret_cast<DWORD_PTR>(pvKey);
DWORD_PTR pnKey = (DWORD_PTR) key; const void** ppvRec = (const void**) ppRec;
return _BaseHashTable::DeleteKey(pnKey, ppvRec, fDeleteAllSame); }
LK_RETCODE DeleteRecord(const _Record* pRec) { CAutoRefCount arc(this);
return _BaseHashTable::DeleteRecord(pRec); }
// Note: returns a _Record**, not a const Record**. Note that you
// can use a const type for the template parameter to ensure constness.
LK_RETCODE FindKey(const _Key key, _Record** ppRec) const { if (ppRec == NULL) return LK_BAD_RECORD;
*ppRec = NULL;
CAutoRefCount arc(this); const void* pvRec = NULL;
// const void* pvKey = reinterpret_cast<const void*>(key);
// DWORD_PTR pnKey = reinterpret_cast<DWORD_PTR>(pvKey);
DWORD_PTR pnKey = (DWORD_PTR) key;
LK_RETCODE lkrc = _BaseHashTable::FindKey(pnKey, &pvRec);
*ppRec = static_cast<_Record*>(const_cast<void*>(pvRec));
return lkrc; }
LK_RETCODE FindRecord(const _Record* pRec) const { CAutoRefCount arc(this);
return _BaseHashTable::FindRecord(pRec); }
void Destroy() { _Release(); }
LK_RETCODE FindKeyMultipleRecords( const _Key key, size_t* pcRecords, LKR_MULTIPLE_RECORDS** pplmr=NULL ) const { CAutoRefCount arc(this);// const void* pvKey = reinterpret_cast<const void*>(key);
// DWORD_PTR pnKey = reinterpret_cast<DWORD_PTR>(pvKey);
DWORD_PTR pnKey = (DWORD_PTR) key;
return _BaseHashTable::FindKeyMultipleRecords(pnKey, pcRecords, pplmr); }
LK_RETCODE DeleteKeyMultipleRecords( const _Key key, size_t* pcRecords, LKR_MULTIPLE_RECORDS** pplmr=NULL) { CAutoRefCount arc(this);// const void* pvKey = reinterpret_cast<const void*>(key);
// DWORD_PTR pnKey = reinterpret_cast<DWORD_PTR>(pvKey);
DWORD_PTR pnKey = (DWORD_PTR) key;
return _BaseHashTable::DeleteKeyMultipleRecords(pnKey, pcRecords, pplmr); }
static LK_RETCODE FreeMultipleRecords(LKR_MULTIPLE_RECORDS* plmr) { return _BaseHashTable::FreeMultipleRecords(LKR_MULTIPLE_RECORDS* plmr) }
// Other C{Linear}HashTable methods can be exposed without change
// CODEWORK: refcount iterators
#ifdef LKR_APPLY_IF
public:
// Typesafe wrappers for Apply et al
DWORD Apply(PFnRecordAction pfnAction, void* pvState=NULL, LK_LOCKTYPE lkl=LKL_READLOCK) { IRTLASSERT(pfnAction != NULL); if (pfnAction == NULL) return 0;
CAutoRefCount arc(this); CState state(NULL, pfnAction, pvState);
return _BaseHashTable::Apply(_Action, &state, lkl); }
DWORD ApplyIf(PFnRecordPred pfnPredicate, PFnRecordAction pfnAction, void* pvState=NULL, LK_LOCKTYPE lkl=LKL_READLOCK) { IRTLASSERT(pfnPredicate != NULL && pfnAction != NULL); if (pfnPredicate == NULL || pfnAction == NULL) return 0;
CAutoRefCount arc(this); CState state(pfnPredicate, pfnAction, pvState);
return _BaseHashTable::ApplyIf(_Pred, _Action, &state, lkl); }
DWORD DeleteIf(PFnRecordPred pfnPredicate, void* pvState=NULL) { IRTLASSERT(pfnPredicate != NULL); if (pfnPredicate == NULL) return 0;
CAutoRefCount arc(this); CState state(pfnPredicate, NULL, pvState);
return _BaseHashTable::DeleteIf(_Pred, &state); }#endif // LKR_APPLY_IF
#ifdef LKR_DEPRECATED_ITERATORS
// Typesafe wrappers for iterators
class CIterator : public _BaseIterator { private: // Private, unimplemented copy ctor and op= to prevent
// compiler synthesizing them.
CIterator(const CIterator&); CIterator& operator=(const CIterator&);
public: CIterator( LK_LOCKTYPE lkl=LKL_WRITELOCK) : _BaseIterator(lkl) {}
_Record* Record() const { const _BaseIterator* pBase = static_cast<const _BaseIterator*>(this); return reinterpret_cast<_Record*>(const_cast<void*>( pBase->Record())); }
_Key Key() const { const _BaseIterator* pBase = static_cast<const _BaseIterator*>(this); return reinterpret_cast<_Key>(reinterpret_cast<void*>(pBase->Key())); } };
// readonly iterator
class CConstIterator : public CIterator { private: // Private, unimplemented copy ctor and op= to prevent
// compiler synthesizing them.
CConstIterator(const CConstIterator&); CConstIterator& operator=(const CConstIterator&);
public: CConstIterator() : CIterator(LKL_READLOCK) {}
const _Record* Record() const { return CIterator::Record(); }
const _Key Key() const { return CIterator::Key(); } };
public: LK_RETCODE InitializeIterator(CIterator* piter) { return _BaseHashTable::InitializeIterator(piter); }
LK_RETCODE IncrementIterator(CIterator* piter) { return _BaseHashTable::IncrementIterator(piter); }
LK_RETCODE CloseIterator(CIterator* piter) { return _BaseHashTable::CloseIterator(piter); }
LK_RETCODE InitializeIterator(CConstIterator* piter) const { return const_cast<HashTable*>(this) ->InitializeIterator(static_cast<CIterator*>(piter)); }
LK_RETCODE IncrementIterator(CConstIterator* piter) const { return const_cast<HashTable*>(this) ->IncrementIterator(static_cast<CIterator*>(piter)); }
LK_RETCODE CloseIterator(CConstIterator* piter) const { return const_cast<HashTable*>(this) ->CloseIterator(static_cast<CIterator*>(piter)); }
#endif // LKR_DEPRECATED_ITERATORS
#ifdef LKR_STL_ITERATORS
// TODO: const_iterator
public:
class iterator { friend class CTypedHashTable<_Derived, _Record, _Key, _fDoRefCounting, _BaseHashTable #ifdef LKR_DEPRECATED_ITERATORS
, _BaseIterator #endif // LKR_DEPRECATED_ITERATORS
>;
protected: typename _BaseHashTable::Iterator m_iter;
iterator( const typename _BaseHashTable::Iterator& rhs) : m_iter(rhs) { LKR_ITER_TRACE(_TEXT("Typed::prot ctor, this=%p, rhs=%p\n"), this, &rhs); }
public: typedef std::forward_iterator_tag iterator_category; typedef _Record value_type; typedef ptrdiff_t difference_type; typedef size_t size_type; typedef value_type& reference; typedef value_type* pointer;
iterator() : m_iter() { LKR_ITER_TRACE(_TEXT("Typed::default ctor, this=%p\n"), this); }
iterator( const iterator& rhs) : m_iter(rhs.m_iter) { LKR_ITER_TRACE(_TEXT("Typed::copy ctor, this=%p, rhs=%p\n"), this, &rhs); }
iterator& operator=( const iterator& rhs) { LKR_ITER_TRACE(_TEXT("Typed::operator=, this=%p, rhs=%p\n"), this, &rhs); m_iter = rhs.m_iter; return *this; }
~iterator() { LKR_ITER_TRACE(_TEXT("Typed::dtor, this=%p\n"), this); }
pointer operator->() const { return (reinterpret_cast<_Record*>( const_cast<void*>(m_iter.Record()))); }
reference operator*() const { return * (operator->()); }
// pre-increment
iterator& operator++() { LKR_ITER_TRACE(_TEXT("Typed::pre-increment, this=%p\n"), this); m_iter.Increment(); return *this; }
// post-increment
iterator operator++(int) { LKR_ITER_TRACE(_TEXT("Typed::post-increment, this=%p\n"), this); iterator iterPrev = *this; m_iter.Increment(); return iterPrev; }
bool operator==( const iterator& rhs) const { LKR_ITER_TRACE(_TEXT("Typed::operator==, this=%p, rhs=%p\n"), this, &rhs); return m_iter == rhs.m_iter; }
bool operator!=( const iterator& rhs) const { LKR_ITER_TRACE(_TEXT("Typed::operator!=, this=%p, rhs=%p\n"), this, &rhs); return m_iter != rhs.m_iter; }
_Record* Record() const { LKR_ITER_TRACE(_TEXT("Typed::Record, this=%p\n"), this); return reinterpret_cast<_Record*>( const_cast<void*>(m_iter.Record())); }
_Key Key() const { LKR_ITER_TRACE(_TEXT("Typed::Key, this=%p\n"), this); return reinterpret_cast<_Key>( reinterpret_cast<void*>(m_iter.Key())); } }; // class iterator
// Return iterator pointing to first item in table
iterator begin() { LKR_ITER_TRACE(_TEXT("Typed::begin()\n")); return iterator(_BaseHashTable::Begin()); }
// Return a one-past-the-end iterator. Always empty.
iterator end() const { LKR_ITER_TRACE(_TEXT("Typed::end()\n")); return iterator(_BaseHashTable::End()); }
template <class _InputIterator> CTypedHashTable( _InputIterator f, // first element in range
_InputIterator l, // one-beyond-last element
LPCSTR pszClassName, // Identifies table for debugging
unsigned maxload=LK_DFLT_MAXLOAD, // Upperbound on avg chain len
DWORD initsize=LK_DFLT_INITSIZE, // Initial size of table: S/M/L
DWORD num_subtbls=LK_DFLT_NUM_SUBTBLS,// #subordinate hash tables.
bool fMultiKeys=false, // Allow multiple identical keys?
bool fUseLocks=true // Must use locks
#ifdef LKRHASH_KERNEL_MODE
, bool fNonPagedAllocs=true // use paged or NP pool in kernel
#endif
) : _BaseHashTable(pszClassName, _ExtractKey, _CalcKeyHash, _CompareKeys, _AddRefRecord, maxload, initsize, num_subtbls, fMultiKeys, fUseLocks#ifdef LKRHASH_KERNEL_MODE
, fNonPagedAllocs#endif
) { insert(f, l); }
template <class _InputIterator> void insert(_InputIterator f, _InputIterator l) { for ( ; f != l; ++f) InsertRecord(&(*f)); }
bool Insert( const _Record* pRecord, iterator& riterResult, bool fOverwrite=false) { LKR_ITER_TRACE(_TEXT("Typed::Insert\n")); return _BaseHashTable::Insert(pRecord, riterResult.m_iter, fOverwrite); }
bool Erase( iterator& riter) { LKR_ITER_TRACE(_TEXT("Typed::Erase\n")); return _BaseHashTable::Erase(riter.m_iter); }
bool Erase( iterator& riterFirst, iterator& riterLast) { LKR_ITER_TRACE(_TEXT("Typed::Erase2\n")); return _BaseHashTable::Erase(riterFirst.m_iter, riterLast.m_iter); }
bool Find( const _Key key, iterator& riterResult) { LKR_ITER_TRACE(_TEXT("Typed::Find\n")); const void* pvKey = reinterpret_cast<const void*>(key); DWORD_PTR pnKey = reinterpret_cast<DWORD_PTR>(pvKey); return _BaseHashTable::Find(pnKey, riterResult.m_iter); }
bool EqualRange( const _Key key, iterator& riterFirst, iterator& riterLast) { LKR_ITER_TRACE(_TEXT("Typed::EqualRange\n")); const void* pvKey = reinterpret_cast<const void*>(key); DWORD_PTR pnKey = reinterpret_cast<DWORD_PTR>(pvKey); return _BaseHashTable::EqualRange(pnKey, riterFirst.m_iter, riterLast.m_iter); }
// The iterator functions for an STL hash_(|multi)_(set|map)
//
// Value type of a Pair-Associative Container is
// pair<const key_type, mapped_type>
//
// pair<iterator,bool> insert(const value_type& x);
//
// void erase(iterator pos);
// void erase(iterator f, iterator l);
//
// iterator find(const key_type& k) [const];
// const_iterator find(const key_type& k) const;
//
// pair<iterator,iterator> equal_range(const key_type& k) [const];
// pair<const_iterator,const_iterator> equal_range(const key_type& k) const
#endif // LKR_STL_ITERATORS
}; // class CTypedHashTable
#ifndef __LKRHASH_NO_NAMESPACE__
};#endif // !__LKRHASH_NO_NAMESPACE__
#endif // __LKRHASH_H__
|
