reactos/ntoskrnl/ex/hashtab.c

   1 /* $Id:$
   2  *
   3  * COPYRIGHT:       See COPYING in the top level directory
   4  * PROJECT:         ReactOS kernel
   5  * FILE:            ntoskrnl/ex/hashtab.c
   6  * PURPOSE:         Hash table support
   7  *
   8  * PROGRAMMERS:     Casper S. Hornstrup (chorns@users.sourceforge.net)
   9  */
  10
  11 /*
  12  * NOTES:           The hash function is from:
  13  *                  Bob Jenkins <bob_jenkins@burtleburtle.net>
  14  *                  http://burtleburtle.net/bob/hash/doobs.html
  15  */
  16
  17 #include <ntoskrnl.h>
  18
  19 #define NDEBUG
  20 #include <internal/debug.h>
  21
  22 /* FUNCTIONS ****************************************************************/
  23
  24 #define ExpHashTableSize(n) ((ULONG)1 << (n))
  25 #define ExpHashTableMask(n) (ExpHashTableSize(n) - 1)
  26
  27 #define ExpHashMix(a, b, c) \
  28 { \
  29   a -= b; a -= c; a ^= (c >> 13); \
  30   b -= c; b -= a; b ^= (a << 8);  \
  31   c -= a; c -= b; c ^= (b >> 13); \
  32   a -= b; a -= c; a ^= (c >> 12); \
  33   b -= c; b -= a; b ^= (a << 16); \
  34   c -= a; c -= b; c ^= (b >> 5);  \
  35   a -= b; a -= c; a ^= (c >> 3);  \
  36   b -= c; b -= a; b ^= (a << 10); \
  37   c -= a; c -= b; c ^= (b >> 15); \
  38 }
  39
  40
  41 ULONG
  42 ExpHash(PUCHAR Key,
  43   ULONG KeyLength)
  44 {
  45   register ULONG a, b, c, len;
  46
  47         /* Set up the internal state */
  48         len = KeyLength;
  49         a = b = 0x9e3779b9;    /* The golden ratio; an arbitrary value */
  50         c = 0;
  51
  52         /* Handle most of the key */
  53         while (len >= 12)
  54                 {
  55                   a += (Key[0] + ((ULONG)Key[1]<<8) + ((ULONG)Key[2]<<16) + ((ULONG)Key[3]<<24));
  56                   b += (Key[4] + ((ULONG)Key[5]<<8) + ((ULONG)Key[6]<<16) + ((ULONG)Key[7]<<24));
  57                   c += (Key[8] + ((ULONG)Key[9]<<8) + ((ULONG)Key[10]<<16)+ ((ULONG)Key[11]<<24));
  58                   ExpHashMix(a, b, c);
  59                   Key += 12; len -= 12;
  60                 }
  61
  62         /* Handle the last 11 bytes */
  63         c += KeyLength;
  64         switch(len)       /* All the case statements fall through */
  65                 {
  66                         case 11: c += ((ULONG)Key[10] << 24);
  67                         case 10: c += ((ULONG)Key[9] << 16);
  68                         case 9 : c += ((ULONG)Key[8] << 8);
  69                           /* The first byte of c is reserved for the length */
  70                         case 8 : b += ((ULONG)Key[7] << 24);
  71                         case 7 : b += ((ULONG)Key[6] << 16);
  72                         case 6 : b += ((ULONG)Key[5] << 8);
  73                         case 5 : b += Key[4];
  74                         case 4 : a += ((ULONG)Key[3] << 24);
  75                         case 3 : a += ((ULONG)Key[2] << 16);
  76                         case 2 : a += ((ULONG)Key[1] << 8);
  77                         case 1 : a += Key[0];
  78                         /* case 0: nothing left to add */
  79                 }
  80
  81         ExpHashMix(a, b, c);
  82
  83         return c;
  84 }
  85
  86
  87 /*
  88  * Lock the hash table
  89  */
  90 inline VOID
  91 ExpLockHashTable(PHASH_TABLE HashTable,
  92   PKIRQL OldIrql)
  93 {
  94         if (HashTable->UseNonPagedPool)
  95           {
  96       KeAcquireSpinLock(&HashTable->Lock.NonPaged, OldIrql);
  97           }
  98         else
  99                 {
 100       ExAcquireFastMutex(&HashTable->Lock.Paged);
 101                 }
 102 }
 103
 104
 105 /*
 106  * Unlock the hash table
 107  */
 108 inline VOID
 109 ExpUnlockHashTable(PHASH_TABLE HashTable,
 110   PKIRQL OldIrql)
 111 {
 112         if (HashTable->UseNonPagedPool)
 113           {
 114       KeReleaseSpinLock(&HashTable->Lock.NonPaged, *OldIrql);
 115           }
 116         else
 117                 {
 118       ExReleaseFastMutex(&HashTable->Lock.Paged);
 119                 }
 120 }
 121
 122
 123 /*
 124  * Insert a value in a hash table.
 125  */
 126 inline VOID STDCALL
 127 ExpInsertHashTable(IN PHASH_TABLE  HashTable,
 128   IN PVOID  Key,
 129   IN ULONG  KeyLength,
 130   IN PVOID  Value)
 131 {
 132   ULONG Index;
 133
 134   Index = (ExpHash(Key, KeyLength) & ExpHashTableMask(HashTable->HashTableSize));
 135
 136   ExInsertSplayTree(&HashTable->HashTrees[Index], Key, Value);
 137 }
 138
 139
 140 /*
 141  * Search for a value associated with a given key in a hash table.
 142  */
 143 inline BOOLEAN STDCALL
 144 ExpSearchHashTable(IN PHASH_TABLE  HashTable,
 145   IN PVOID  Key,
 146   IN ULONG  KeyLength,
 147   OUT PVOID  * Value)
 148 {
 149   ULONG Index;
 150
 151   Index = (ExpHash(Key, KeyLength) & ExpHashTableMask(HashTable->HashTableSize));
 152
 153   return ExSearchSplayTree(&HashTable->HashTrees[Index], Key, Value);
 154 }
 155
 156
 157 /*
 158  * Remove a value associated with a given key from a hash table.
 159  */
 160 BOOLEAN STDCALL
 161 ExpRemoveHashTable(IN PHASH_TABLE  HashTable,
 162   IN PVOID  Key,
 163   IN ULONG  KeyLength,
 164   IN PVOID  * Value)
 165 {
 166   ULONG Index;
 167
 168   Index = (ExpHash(Key, KeyLength) & ExpHashTableMask(HashTable->HashTableSize));
 169
 170   return ExRemoveSplayTree(&HashTable->HashTrees[Index], Key, Value);
 171 }
 172
 173
 174 /*
 175  * Initializes a hash table.
 176  */
 177 BOOLEAN STDCALL
 178 ExInitializeHashTable(IN PHASH_TABLE  HashTable,
 179   IN ULONG  HashTableSize,
 180   IN PKEY_COMPARATOR  Compare  OPTIONAL,
 181   IN BOOLEAN  UseNonPagedPool)
 182 {
 183   BOOLEAN Status;
 184   ULONG Index;
 185
 186   RtlZeroMemory(HashTable, sizeof(HASH_TABLE));
 187
 188   HashTable->HashTableSize = HashTableSize;
 189
 190   HashTable->UseNonPagedPool = UseNonPagedPool;
 191
 192   if (UseNonPagedPool)
 193     {
 194       KeInitializeSpinLock(&HashTable->Lock.NonPaged);
 195       HashTable->HashTrees = ExAllocatePool(NonPagedPool, ExpHashTableSize(HashTableSize) * sizeof(SPLAY_TREE));
 196                 }
 197                 else
 198                 {
 199       ExInitializeFastMutex(&HashTable->Lock.Paged);
 200       HashTable->HashTrees = ExAllocatePool(PagedPool, ExpHashTableSize(HashTableSize) * sizeof(SPLAY_TREE));
 201                 }
 202
 203   if (HashTable->HashTrees == NULL)
 204                 {
 205       return FALSE;
 206                 }
 207
 208   for (Index = 0; Index < ExpHashTableSize(HashTableSize); Index++)
 209     {
 210       Status = ExInitializeSplayTree(&HashTable->HashTrees[Index], Compare, FALSE, UseNonPagedPool);
 211
 212       if (!Status)
 213                                 {
 214           LONG i;
 215
 216           for (i = Index - 1; i >= 0; i--)
 217                                                 {
 218               ExDeleteSplayTree(&HashTable->HashTrees[i]);
 219                                                 }
 220
 221           ExFreePool(HashTable->HashTrees);
 222
 223           return FALSE;
 224                                 }
 225     }
 226
 227   return TRUE;
 228 }
 229
 230
 231 /*
 232  * Release resources used by a hash table.
 233  */
 234 VOID STDCALL
 235 ExDeleteHashTable(IN PHASH_TABLE  HashTable)
 236 {
 237   ULONG Index;
 238
 239   for (Index = 0; Index < ExpHashTableSize(HashTable->HashTableSize); Index++)
 240                 {
 241       ExDeleteSplayTree(&HashTable->HashTrees[Index]);
 242                 }
 243
 244   ExFreePool(HashTable->HashTrees);
 245 }
 246
 247
 248 /*
 249  * Insert a value in a hash table.
 250  */
 251 VOID STDCALL
 252 ExInsertHashTable(IN PHASH_TABLE  HashTable,
 253   IN PVOID  Key,
 254   IN ULONG  KeyLength,
 255   IN PVOID  Value)
 256 {
 257   KIRQL OldIrql;
 258
 259   /* FIXME: Use SEH for error reporting */
 260
 261   ExpLockHashTable(HashTable, &OldIrql);
 262   ExpInsertHashTable(HashTable, Key, KeyLength, Value);
 263   ExpUnlockHashTable(HashTable, &OldIrql);
 264 }
 265
 266
 267 /*
 268  * Search for a value associated with a given key in a hash table.
 269  */
 270 BOOLEAN STDCALL
 271 ExSearchHashTable(IN PHASH_TABLE  HashTable,
 272   IN PVOID  Key,
 273   IN ULONG  KeyLength,
 274   OUT PVOID  * Value)
 275 {
 276   BOOLEAN Status;
 277   KIRQL OldIrql;
 278
 279   ExpLockHashTable(HashTable, &OldIrql);
 280   Status = ExpSearchHashTable(HashTable, Key, KeyLength, Value);
 281   ExpUnlockHashTable(HashTable, &OldIrql);
 282
 283   return Status;
 284 }
 285
 286
 287 /*
 288  * Remove a value associated with a given key from a hash table.
 289  */
 290 BOOLEAN STDCALL
 291 ExRemoveHashTable(IN PHASH_TABLE  HashTable,
 292   IN PVOID  Key,
 293   IN ULONG  KeyLength,
 294   IN PVOID  * Value)
 295 {
 296   BOOLEAN Status;
 297   KIRQL OldIrql;
 298
 299   ExpLockHashTable(HashTable, &OldIrql);
 300   Status = ExpRemoveHashTable(HashTable, Key, KeyLength, Value);
 301   ExpUnlockHashTable(HashTable, &OldIrql);
 302
 303   return Status;
 304 }
 305
 306 /* EOF */