Leaked source code of windows server 2003
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

273 lines
6.1 KiB

  1. //
  2. // Copyright (C) 2000, Microsoft Corporation
  3. //
  4. // File: shash.h
  5. //
  6. // Contents: Generic hashtable
  7. // Classes:
  8. //
  9. // History: April. 9 2001, Author: Rohanp
  10. //
  11. //-----------------------------------------------------------------------------
  12. #ifndef __SHASHTABLE_H__
  13. #define __SHASHTABLE_H__
  14. #pragma warning(disable: 4200)
  15. #ifdef __cplusplus
  16. extern "C" {
  17. #endif
  18. //forward declaration
  19. struct _SHASH_TABLE;
  20. struct _SHASH_HEADER;
  21. // This function computes the hash value
  22. //
  23. typedef ULONG (*PFNHASH)( void* pvKey ) ;
  24. //
  25. // This function compares the keys
  26. //
  27. typedef int (*PFNMATCHKEY)( void* key1, void* key2 ) ;
  28. //
  29. // This function gets called when the keys get removed
  30. //
  31. typedef int (*PFNREMOVEKEY)(struct _SHASH_HEADER * pHeader) ;
  32. //
  33. // This function gets called when the keys get removed
  34. //
  35. typedef DWORD (*PFNENUMERATEKEY)(struct _SHASH_HEADER * pHeader, void * pContext ) ;
  36. // memory allocations function
  37. typedef void* (*PFNALLOC)( ULONG cb ) ;
  38. // memory free function
  39. typedef void (*PFNFREE)( void* lpv ) ;
  40. //
  41. // This function allocs memory for the tables lock
  42. //
  43. typedef void * (*PFNALLOCLOCK)( void ) ;
  44. //
  45. // This function releases the lock memory
  46. //
  47. typedef void (*PFNFREELOCK)( void * ) ;
  48. typedef BOOLEAN (*PFNAQUIREWRITELOCK)( struct _SHASH_TABLE * pTable ) ;
  49. typedef BOOLEAN (*PFNAQUIREREADLOCK)( struct _SHASH_TABLE * pTable ) ;
  50. typedef BOOLEAN (*PFNRELEASEWRITELOCK)( struct _SHASH_TABLE * pTable ) ;
  51. typedef BOOLEAN (*PFNRELEASEREADLOCK)( struct _SHASH_TABLE * pTable ) ;
  52. #define SHASH_DEFAULT_HASH_SIZE 512
  53. #define SHASH_CRIT_SPIN_COUNT 4000
  54. //
  55. // There are flags that are not used by shash, they can be used by
  56. // the caller.
  57. //
  58. #define SHASH_USER_FLAGS 0xFFFF0000
  59. typedef struct _SHASH_HEADER
  60. {
  61. ULONG Signature;
  62. ULONG Flags;
  63. PVOID pvKey;
  64. PVOID pData;
  65. LONG RefCount;
  66. ULONG dwHash;
  67. FILETIME Time;
  68. LIST_ENTRY ListEntry;
  69. }SHASH_HEADER, *PSHASH_HEADER;
  70. #define SHASH_FLAG_DELETE_PENDING 0x00000001
  71. typedef struct _SHASHFUNCTABLE
  72. {
  73. PFNHASH HashFunc;
  74. PFNMATCHKEY CompareFunc;
  75. PFNALLOC AllocFunc;
  76. PFNFREE FreeFunc;
  77. PFNALLOC AllocHashEntryFunc;
  78. PFNFREE FreeHashEntryFunc;
  79. PFNALLOCLOCK AllocLockFunc;
  80. PFNFREELOCK FreeLockFunc;
  81. PFNAQUIREWRITELOCK WriteLockFunc;
  82. PFNAQUIREREADLOCK ReadLockFunc;
  83. PFNRELEASEWRITELOCK ReleaseWriteLockFunc;
  84. PFNRELEASEREADLOCK ReleaseReadLockFunc;
  85. ULONG Flags;
  86. ULONG NumBuckets;
  87. } SHASH_FUNCTABLE, *PSHASH_FUNCTABLE;
  88. typedef struct _SHASH_BUCKET
  89. {
  90. ULONG Count;
  91. LIST_ENTRY ListHead;
  92. } SHASH_BUCKET, *PHASH_SBUCKET;
  93. typedef struct _SHASH_ENTRY
  94. {
  95. PVOID pvKey;
  96. LONG RefCount;
  97. ULONG Flags;
  98. PVOID pData;
  99. LARGE_INTEGER EntryTime;
  100. LARGE_INTEGER ExpireTime;
  101. LIST_ENTRY ListEntry;
  102. } SHASH_ENTRY, *PSHASH_ENTRY;
  103. typedef struct _SHASH_TABLE
  104. {
  105. PFNHASH HashFunc;
  106. PFNMATCHKEY CompareFunc;
  107. PFNALLOC AllocFunc;
  108. PFNFREE FreeFunc;
  109. PFNALLOC AllocHashEntryFunc;
  110. PFNFREE FreeHashEntryFunc;
  111. PFNALLOCLOCK AllocLockFunc;
  112. PFNFREELOCK FreeLockFunc;
  113. PFNAQUIREWRITELOCK WriteLockFunc;
  114. PFNAQUIREREADLOCK ReadLockFunc;
  115. PFNRELEASEWRITELOCK ReleaseWriteLockFunc;
  116. PFNRELEASEREADLOCK ReleaseReadLockFunc;
  117. LONG Version;
  118. ULONG Flags;
  119. ULONG NumBuckets;
  120. ULONG TotalItems;
  121. PVOID pLock;
  122. SHASH_BUCKET HashBuckets[0];
  123. } SHASH_TABLE, *PSHASH_TABLE;
  124. #define SHASH_CAP_POWER_OF2 0x000001
  125. #define SHASH_CAP_TABLE_LOCKED 0x000002
  126. #define SHASH_CAP_NOSEARCH_INSERT 0x000004
  127. #define SHASH_DEFAULT_HASHTIMEOUT (15 * 60) //timeout entries in 15 minutes
  128. #define SHASH_REPLACE_IFFOUND 1
  129. #define SHASH_FAIL_IFFOUND 2
  130. #ifdef KERNEL_MODE
  131. #define SHASH_GET_TIME(Time) KeQuerySystemTime(Time)
  132. #else
  133. #define SHASH_GET_TIME(Time) NtQuerySystemTime(Time)
  134. #endif
  135. typedef struct _SHASH_ITERATOR {
  136. //
  137. // index
  138. //
  139. ULONG index;
  140. LIST_ENTRY* pListHead;
  141. //
  142. //
  143. LIST_ENTRY* ple;
  144. PSHASH_HEADER pEntry;
  145. } SHASH_ITERATOR,*PSHASH_ITERATOR;
  146. NTSTATUS
  147. ShashInitHashTable(
  148. PSHASH_TABLE *ppHashTable,
  149. PSHASH_FUNCTABLE pFuncTable);
  150. void
  151. ShashTerminateHashTable(
  152. PSHASH_TABLE pHashTable
  153. );
  154. NTSTATUS
  155. SHashInsertKey(IN PSHASH_TABLE pTable,
  156. IN void * pData,
  157. IN void * pvKeyIn,
  158. IN DWORD InsertFlag
  159. );
  160. NTSTATUS
  161. SHashRemoveKey( IN PSHASH_TABLE pTable,
  162. IN void * pvKeyIn,
  163. IN PFNREMOVEKEY pRemoveFunc
  164. );
  165. PSHASH_HEADER
  166. SHashLookupKeyEx( IN PSHASH_TABLE pTable,
  167. IN void* pvKeyIn
  168. );
  169. NTSTATUS
  170. SHashIsKeyInTable( IN PSHASH_TABLE pTable,
  171. IN void* pvKeyIn
  172. );
  173. NTSTATUS
  174. SHashGetDataFromTable( IN PSHASH_TABLE pTable,
  175. IN void* pvKeyIn,
  176. IN void ** ppData
  177. );
  178. NTSTATUS
  179. ShashEnumerateItems(IN PSHASH_TABLE pTable,
  180. IN PFNENUMERATEKEY pfnCallback,
  181. IN LPVOID lpvClientContext
  182. );
  183. NTSTATUS
  184. SHashReleaseReference( IN PSHASH_TABLE pTable,
  185. IN PSHASH_HEADER pData
  186. );
  187. PSHASH_HEADER
  188. SHashStartEnumerate(
  189. IN PSHASH_ITERATOR pIterator,
  190. IN PSHASH_TABLE pTable
  191. );
  192. PSHASH_HEADER
  193. SHashNextEnumerate(
  194. IN PSHASH_ITERATOR pIterator,
  195. IN PSHASH_TABLE pTable);
  196. VOID
  197. SHashFinishEnumerate(
  198. IN PSHASH_ITERATOR pIterator,
  199. IN PSHASH_TABLE pTable
  200. );
  201. NTSTATUS
  202. SHashMarkForDeletion( IN PSHASH_TABLE pTable,
  203. IN PSHASH_HEADER pData
  204. );
  205. #ifdef __cplusplus
  206. }
  207. #endif
  208. #pragma warning(default: 4200)
  209. #endif