Added a binary tree implementation
[reactos.git] / 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 #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 * Insert a value in a hash table.
103 */
104 inline VOID STDCALL
105 ExpInsertHashTable(IN PHASH_TABLE HashTable,
106 IN PVOID Key,
107 IN ULONG KeyLength,
108 IN PVOID Value)
109 {
110 ULONG Index;
111
112 Index = (ExpHash(Key, KeyLength) & ExpHashTableMask(HashTable->HashTableSize));
113
114 ExInsertSplayTree(&HashTable->HashTrees[Index], Key, Value);
115 }
116
117
118 /*
119 * Search for a value associated with a given key in a hash table.
120 */
121 inline BOOLEAN STDCALL
122 ExpSearchHashTable(IN PHASH_TABLE HashTable,
123 IN PVOID Key,
124 IN ULONG KeyLength,
125 OUT PVOID * Value)
126 {
127 ULONG Index;
128
129 Index = (ExpHash(Key, KeyLength) & ExpHashTableMask(HashTable->HashTableSize));
130
131 return ExSearchSplayTree(&HashTable->HashTrees[Index], Key, Value);
132 }
133
134
135 /*
136 * Remove a value associated with a given key from a hash table.
137 */
138 BOOLEAN STDCALL
139 ExpRemoveHashTable(IN PHASH_TABLE HashTable,
140 IN PVOID Key,
141 IN ULONG KeyLength,
142 IN PVOID * Value)
143 {
144 ULONG Index;
145
146 Index = (ExpHash(Key, KeyLength) & ExpHashTableMask(HashTable->HashTableSize));
147
148 return ExRemoveSplayTree(&HashTable->HashTrees[Index], Key, Value);
149 }
150
151
152 /*
153 * Initializes a hash table.
154 */
155 BOOLEAN STDCALL
156 ExInitializeHashTable(IN PHASH_TABLE HashTable,
157 IN ULONG HashTableSize,
158 IN PKEY_COMPARATOR Compare OPTIONAL)
159 {
160 BOOLEAN Status;
161 LONG Index;
162
163 RtlZeroMemory(HashTable, sizeof(HASH_TABLE));
164
165 HashTable->HashTableSize = HashTableSize;
166
167 ExInitializeFastMutex(&HashTable->Lock);
168
169 HashTable->HashTrees = ExAllocatePool(PagedPool, ExpHashTableSize(HashTableSize) * sizeof(SPLAY_TREE));
170
171 if (HashTable->HashTrees == NULL)
172 {
173 return FALSE;
174 }
175
176 for (Index = 0; Index < ExpHashTableSize(HashTableSize); Index++)
177 {
178 Status = ExInitializeSplayTree(&HashTable->HashTrees[Index], Compare, FALSE);
179
180 if (!Status)
181 {
182 LONG i;
183
184 for (i = Index - 1; i >= 0; i--)
185 {
186 ExDeleteSplayTree(&HashTable->HashTrees[i]);
187 }
188
189 ExFreePool(HashTable->HashTrees);
190
191 return FALSE;
192 }
193 }
194
195 return TRUE;
196 }
197
198
199 /*
200 * Release resources used by a hash table.
201 */
202 VOID STDCALL
203 ExDeleteHashTable(IN PHASH_TABLE HashTable)
204 {
205 ULONG Index;
206
207 for (Index = 0; Index < ExpHashTableSize(HashTable->HashTableSize); Index++)
208 {
209 ExDeleteSplayTree(&HashTable->HashTrees[Index]);
210 }
211
212 ExFreePool(HashTable->HashTrees);
213 }
214
215
216 /*
217 * Insert a value in a hash table.
218 */
219 VOID STDCALL
220 ExInsertHashTable(IN PHASH_TABLE HashTable,
221 IN PVOID Key,
222 IN ULONG KeyLength,
223 IN PVOID Value)
224 {
225 /* FIXME: Use SEH for error reporting */
226
227 ExAcquireFastMutex(&HashTable->Lock);
228 ExpInsertHashTable(HashTable, Key, KeyLength, Value);
229 ExReleaseFastMutex(&HashTable->Lock);
230 }
231
232
233 /*
234 * Search for a value associated with a given key in a hash table.
235 */
236 BOOLEAN STDCALL
237 ExSearchHashTable(IN PHASH_TABLE HashTable,
238 IN PVOID Key,
239 IN ULONG KeyLength,
240 OUT PVOID * Value)
241 {
242 BOOLEAN Status;
243
244 ExAcquireFastMutex(&HashTable->Lock);
245 Status = ExpSearchHashTable(HashTable, Key, KeyLength, Value);
246 ExReleaseFastMutex(&HashTable->Lock);
247
248 return Status;
249 }
250
251
252 /*
253 * Remove a value associated with a given key from a hash table.
254 */
255 BOOLEAN STDCALL
256 ExRemoveHashTable(IN PHASH_TABLE HashTable,
257 IN PVOID Key,
258 IN ULONG KeyLength,
259 IN PVOID * Value)
260 {
261 BOOLEAN Status;
262
263 ExAcquireFastMutex(&HashTable->Lock);
264 Status = ExpRemoveHashTable(HashTable, Key, KeyLength, Value);
265 ExReleaseFastMutex(&HashTable->Lock);
266
267 return Status;
268 }
269
270 /* EOF */