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