ntoskrnl/ex/hashtab.c

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