3 * Copyright (C) 1998-2002 ReactOS Team
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.
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.
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.
20 * PROJECT: ReactOS kernel
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
28 * 15-03-2002 CSH Created
30 #include <ddk/ntddk.h>
31 #include <internal/ex.h>
34 #include <internal/debug.h>
36 /* FUNCTIONS ****************************************************************/
38 #define ExpHashTableSize(n) ((ULONG)1 << (n))
39 #define ExpHashTableMask(n) (ExpHashTableSize(n) - 1)
41 #define ExpHashMix(a, b, c) \
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); \
59 register ULONG a
, b
, c
, len
;
61 /* Set up the internal state */
63 a
= b
= 0x9e3779b9; /* The golden ratio; an arbitrary value */
66 /* Handle most of the key */
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));
76 /* Handle the last 11 bytes */
78 switch(len
) /* All the case statements fall through */
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);
88 case 4 : a
+= ((ULONG
)Key
[3] << 24);
89 case 3 : a
+= ((ULONG
)Key
[2] << 16);
90 case 2 : a
+= ((ULONG
)Key
[1] << 8);
92 /* case 0: nothing left to add */
102 * Lock the hash table
105 ExpLockHashTable(PHASH_TABLE HashTable
,
108 if (HashTable
->UseNonPagedPool
)
110 KeAcquireSpinLock(&HashTable
->Lock
.NonPaged
, OldIrql
);
114 ExAcquireFastMutex(&HashTable
->Lock
.Paged
);
120 * Unlock the hash table
123 ExpUnlockHashTable(PHASH_TABLE HashTable
,
126 if (HashTable
->UseNonPagedPool
)
128 KeReleaseSpinLock(&HashTable
->Lock
.NonPaged
, *OldIrql
);
132 ExReleaseFastMutex(&HashTable
->Lock
.Paged
);
138 * Insert a value in a hash table.
141 ExpInsertHashTable(IN PHASH_TABLE HashTable
,
148 Index
= (ExpHash(Key
, KeyLength
) & ExpHashTableMask(HashTable
->HashTableSize
));
150 ExInsertSplayTree(&HashTable
->HashTrees
[Index
], Key
, Value
);
155 * Search for a value associated with a given key in a hash table.
157 inline BOOLEAN STDCALL
158 ExpSearchHashTable(IN PHASH_TABLE HashTable
,
165 Index
= (ExpHash(Key
, KeyLength
) & ExpHashTableMask(HashTable
->HashTableSize
));
167 return ExSearchSplayTree(&HashTable
->HashTrees
[Index
], Key
, Value
);
172 * Remove a value associated with a given key from a hash table.
175 ExpRemoveHashTable(IN PHASH_TABLE HashTable
,
182 Index
= (ExpHash(Key
, KeyLength
) & ExpHashTableMask(HashTable
->HashTableSize
));
184 return ExRemoveSplayTree(&HashTable
->HashTrees
[Index
], Key
, Value
);
189 * Initializes a hash table.
192 ExInitializeHashTable(IN PHASH_TABLE HashTable
,
193 IN ULONG HashTableSize
,
194 IN PKEY_COMPARATOR Compare OPTIONAL
,
195 IN BOOLEAN UseNonPagedPool
)
200 RtlZeroMemory(HashTable
, sizeof(HASH_TABLE
));
202 HashTable
->HashTableSize
= HashTableSize
;
204 HashTable
->UseNonPagedPool
= UseNonPagedPool
;
208 KeInitializeSpinLock(&HashTable
->Lock
.NonPaged
);
209 HashTable
->HashTrees
= ExAllocatePool(NonPagedPool
, ExpHashTableSize(HashTableSize
) * sizeof(SPLAY_TREE
));
213 ExInitializeFastMutex(&HashTable
->Lock
.Paged
);
214 HashTable
->HashTrees
= ExAllocatePool(PagedPool
, ExpHashTableSize(HashTableSize
) * sizeof(SPLAY_TREE
));
217 if (HashTable
->HashTrees
== NULL
)
222 for (Index
= 0; Index
< ExpHashTableSize(HashTableSize
); Index
++)
224 Status
= ExInitializeSplayTree(&HashTable
->HashTrees
[Index
], Compare
, FALSE
, UseNonPagedPool
);
230 for (i
= Index
- 1; i
>= 0; i
--)
232 ExDeleteSplayTree(&HashTable
->HashTrees
[i
]);
235 ExFreePool(HashTable
->HashTrees
);
246 * Release resources used by a hash table.
249 ExDeleteHashTable(IN PHASH_TABLE HashTable
)
253 for (Index
= 0; Index
< ExpHashTableSize(HashTable
->HashTableSize
); Index
++)
255 ExDeleteSplayTree(&HashTable
->HashTrees
[Index
]);
258 ExFreePool(HashTable
->HashTrees
);
263 * Insert a value in a hash table.
266 ExInsertHashTable(IN PHASH_TABLE HashTable
,
273 /* FIXME: Use SEH for error reporting */
275 ExpLockHashTable(HashTable
, &OldIrql
);
276 ExpInsertHashTable(HashTable
, Key
, KeyLength
, Value
);
277 ExpUnlockHashTable(HashTable
, &OldIrql
);
282 * Search for a value associated with a given key in a hash table.
285 ExSearchHashTable(IN PHASH_TABLE HashTable
,
293 ExpLockHashTable(HashTable
, &OldIrql
);
294 Status
= ExpSearchHashTable(HashTable
, Key
, KeyLength
, Value
);
295 ExpUnlockHashTable(HashTable
, &OldIrql
);
302 * Remove a value associated with a given key from a hash table.
305 ExRemoveHashTable(IN PHASH_TABLE HashTable
,
313 ExpLockHashTable(HashTable
, &OldIrql
);
314 Status
= ExpRemoveHashTable(HashTable
, Key
, KeyLength
, Value
);
315 ExpUnlockHashTable(HashTable
, &OldIrql
);