- Oops.. fix a bug in RtlRemoveUnicodePrefix: edit the parent, not the entry itself.
[reactos.git] / reactos / lib / rtl / unicodeprefix.c
1 /*
2 * COPYRIGHT: See COPYING in the top level directory
3 * PROJECT: ReactOS system libraries
4 * PURPOSE: Unicode Prefix implementation
5 * FILE: lib/rtl/unicodeprefix.c
6 * PROGRAMMER: Alex Ionescu (alex@relsoft.net)
7 */
8
9 /* INCLUDES *****************************************************************/
10
11 #include <rtl.h>
12
13 #define NDEBUG
14 #include <debug.h>
15
16 /*
17 * FIXME: Try to find the official names and add to NDK
18 * Definitions come from fastfat driver.
19 */
20 typedef USHORT NODE_TYPE_CODE;
21 #define PFX_NTC_TABLE ((NODE_TYPE_CODE)0x0800)
22 #define PFX_NTC_ROOT ((NODE_TYPE_CODE)0x0801)
23 #define PFX_NTC_CHILD ((NODE_TYPE_CODE)0x0802)
24 #define PFX_NTC_CASE_MATCH ((NODE_TYPE_CODE)0x0803)
25
26 /* FUNCTIONS ***************************************************************/
27
28 STATIC
29 ULONG
30 NTAPI
31 ComputeUnicodeNameLength(IN PUNICODE_STRING UnicodeName)
32 {
33 ULONG Chars = UnicodeName->Length / sizeof(WCHAR);
34 ULONG i, NamesFound = 1;
35
36 /* Loop the string */
37 for (i = 0; i < (Chars - 1); i++)
38 {
39 /* Check if we found a backslash, meaning another name */
40 if (UnicodeName->Buffer[i] == '\\') NamesFound++;
41 }
42
43 /* Return the number of names found */
44 return NamesFound;
45 }
46
47
48 STATIC
49 RTL_GENERIC_COMPARE_RESULTS
50 NTAPI
51 CompareUnicodeStrings(IN PUNICODE_STRING String,
52 IN PUNICODE_STRING Prefix,
53 IN ULONG CaseCheckChar)
54 {
55 ULONG StringLength = String->Length / sizeof(WCHAR);
56 ULONG PrefixLength = Prefix->Length / sizeof(WCHAR);
57 ULONG ScanLength = min(StringLength, PrefixLength);
58 ULONG i;
59 WCHAR FoundPrefix, FoundString;
60
61 /* Validate the Case Check Character Position */
62 if (CaseCheckChar > ScanLength) CaseCheckChar = ScanLength;
63
64 /* Do the case sensitive comparison first */
65 for (i = 0; i < CaseCheckChar; i++)
66 {
67 /* Compare the two characters */
68 if (Prefix->Buffer[i] != String->Buffer[i]) break;
69 }
70
71 /* Save the characters we found */
72 FoundPrefix = Prefix->Buffer[i];
73 FoundString = String->Buffer[i];
74
75 /* Check if we exausted the search above */
76 if (i == CaseCheckChar)
77 {
78 /* FIXME: Do a case-insensitive search */
79 }
80
81 /* Check if we weren't able to find a match in the loops */
82 if (i < ScanLength)
83 {
84 /* If the prefix character found was a backslash, this is a less */
85 if (FoundPrefix == '\\') return GenericLessThan;
86
87 /* If the string character found was a backslack, then this is a more */
88 if (FoundString == '\\') return GenericGreaterThan;
89
90 /* None of those two special cases, do a normal check */
91 if (FoundPrefix < FoundString) return GenericLessThan;
92
93 /* The only choice left is that Prefix > String */
94 return GenericGreaterThan;
95 }
96
97 /* If we got here, a match was found. Check if the prefix is smaller */
98 if (PrefixLength < StringLength)
99 {
100 /* Check if the string is actually a prefix */
101 if (String->Buffer[PrefixLength] == '\\') return -1;
102
103 /* It's not a prefix, and it's shorter, so it's a less */
104 return GenericLessThan;
105 }
106
107 /* Check if the prefix is longer */
108 if (PrefixLength > StringLength) return GenericGreaterThan;
109
110 /* If we got here, then they are 100% equal */
111 return GenericEqual;
112 }
113
114 /*
115 * @unimplemented
116 */
117 PUNICODE_PREFIX_TABLE_ENTRY
118 NTAPI
119 RtlFindUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
120 PUNICODE_STRING FullName,
121 ULONG CaseInsensitiveIndex)
122 {
123 UNIMPLEMENTED;
124 return 0;
125 }
126
127 /*
128 * @implemented
129 */
130 VOID
131 NTAPI
132 RtlInitializeUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable)
133 {
134 /* Setup the table */
135 PrefixTable->NameLength = 0;
136 PrefixTable->LastNextEntry = NULL;
137 PrefixTable->NodeTypeCode = PFX_NTC_TABLE;
138 PrefixTable->NextPrefixTree = (PUNICODE_PREFIX_TABLE_ENTRY)PrefixTable;
139 }
140
141 /*
142 * @implemented
143 */
144 BOOLEAN
145 NTAPI
146 RtlInsertUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
147 PUNICODE_STRING Prefix,
148 PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry)
149 {
150 PUNICODE_PREFIX_TABLE_ENTRY CurrentEntry, PreviousEntry, Entry, NextEntry;
151 ULONG NameCount;
152 RTL_GENERIC_COMPARE_RESULTS Result;
153 PRTL_SPLAY_LINKS SplayLinks;
154
155 /* Find out how many names there are */
156 NameCount = ComputeUnicodeNameLength(Prefix);
157
158 /* Set up the initial entry data */
159 PrefixTableEntry->NameLength = NameCount;
160 PrefixTableEntry->Prefix = Prefix;
161 RtlInitializeSplayLinks(&PrefixTableEntry->Links);
162
163 /* Find the right spot where to insert this entry */
164 PreviousEntry = (PUNICODE_PREFIX_TABLE_ENTRY)PrefixTable;
165 CurrentEntry = PreviousEntry->NextPrefixTree;
166 while (CurrentEntry->NameLength > NameCount)
167 {
168 /* Not a match, move to the next entry */
169 PreviousEntry = CurrentEntry;
170 CurrentEntry = CurrentEntry->NextPrefixTree;
171 }
172
173 /* Check if we did find a tree by now */
174 if (CurrentEntry->NameLength != NameCount)
175 {
176 /* We didn't, so insert a new entry in the list */
177 PreviousEntry->NextPrefixTree = PrefixTableEntry;
178 PrefixTableEntry->NextPrefixTree = CurrentEntry;
179
180 /* This is now a root entry with case match */
181 PrefixTableEntry->NodeTypeCode = PFX_NTC_ROOT;
182 PrefixTableEntry->CaseMatch = PrefixTableEntry;
183
184 /* Quick return */
185 return TRUE;
186 }
187
188 /* We found a tree, so star thte search loop */
189 Entry = CurrentEntry;
190 while (TRUE)
191 {
192 /* Do a case-insensitive comparison to find out the match level */
193 Result = CompareUnicodeStrings(Entry->Prefix, Prefix, 0);
194 if (Result == GenericEqual)
195 {
196 /* We have a match, start doing a case-sensitive search */
197 NextEntry = Entry;
198
199 /* Search the circular case-match list */
200 do
201 {
202 /* Check if we found a match */
203 if (CompareUnicodeStrings(NextEntry->Prefix, Prefix, -1) ==
204 (GenericEqual))
205 {
206 /* We must fail the insert: it already exists */
207 return FALSE;
208 }
209
210 /* Move to the next entry in the circular list */
211 NextEntry = NextEntry->CaseMatch;
212 }
213 while (NextEntry != Entry);
214
215 /*
216 * No match found, so we can safely insert it. Remember that a
217 * case insensitive match was found, so this is not a ROOT NTC
218 * but a Case Match NTC instead.
219 */
220 PrefixTableEntry->NodeTypeCode = PFX_NTC_CASE_MATCH;
221 PrefixTableEntry->NextPrefixTree = NULL;
222
223 /* Insert it into the circular list */
224 PrefixTableEntry->CaseMatch = Entry->CaseMatch;
225 Entry->CaseMatch = PrefixTableEntry;
226 }
227 else if (Result == GenericGreaterThan)
228 {
229 /* Check out if we have a left child */
230 if (RtlLeftChild(&Entry->Links))
231 {
232 /* We do, enter it and restart the loop */
233 SplayLinks = RtlLeftChild(&Entry->Links);
234 Entry = CONTAINING_RECORD(SplayLinks,
235 UNICODE_PREFIX_TABLE_ENTRY,
236 Links);
237 }
238 else
239 {
240 /* We don't, set this entry as a child */
241 PrefixTableEntry->NodeTypeCode = PFX_NTC_CHILD;
242 PrefixTableEntry->NextPrefixTree = NULL;
243 PrefixTableEntry->CaseMatch = PrefixTableEntry;
244
245 /* Insert us into the tree */
246 RtlInsertAsLeftChild(&Entry->Links, &PrefixTableEntry->Links);
247 break;
248 }
249 }
250 else
251 {
252 /* Check out if we have a right child */
253 if (RtlRightChild(&Entry->Links))
254 {
255 /* We do, enter it and restart the loop */
256 SplayLinks = RtlLeftChild(&Entry->Links);
257 Entry = CONTAINING_RECORD(SplayLinks,
258 UNICODE_PREFIX_TABLE_ENTRY,
259 Links);
260 }
261 else
262 {
263 /* We don't, set this entry as a child */
264 PrefixTableEntry->NodeTypeCode = PFX_NTC_CHILD;
265 PrefixTableEntry->NextPrefixTree = NULL;
266 PrefixTableEntry->CaseMatch = PrefixTableEntry;
267
268 /* Insert us into the tree */
269 RtlInsertAsRightChild(&Entry->Links, &PrefixTableEntry->Links);
270 break;
271 }
272 }
273 }
274
275 /* Get the next tree entry */
276 NextEntry = CurrentEntry->NextPrefixTree;
277
278 /* Set what was the current entry to a child entry */
279 CurrentEntry->NodeTypeCode = PFX_NTC_CHILD;
280 CurrentEntry->NextPrefixTree = NULL;
281
282 /* Splay the tree */
283 SplayLinks = RtlSplay(&Entry->Links);
284
285 /* The link points to the root, get it */
286 Entry = CONTAINING_RECORD(SplayLinks, UNICODE_PREFIX_TABLE_ENTRY, Links);
287
288 /* Mark the root as a root entry */
289 Entry->NodeTypeCode = PFX_NTC_ROOT;
290
291 /* Add it to the tree list */
292 PreviousEntry->NextPrefixTree = Entry;
293 Entry->NextPrefixTree = NextEntry;
294
295 /* Return success */
296 return TRUE;
297 }
298
299 /*
300 * @implemented
301 */
302 PUNICODE_PREFIX_TABLE_ENTRY
303 NTAPI
304 RtlNextUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
305 BOOLEAN Restart)
306 {
307 PRTL_SPLAY_LINKS SplayLinks;
308 PUNICODE_PREFIX_TABLE_ENTRY Entry, CaseMatchEntry;
309
310 /* We might need this entry 2/3rd of the time, so cache it now */
311 CaseMatchEntry = PrefixTable->LastNextEntry->CaseMatch;
312
313 /* Check if this is a restart or if we don't have a last entry */
314 if ((Restart) || !(PrefixTable->LastNextEntry))
315 {
316 /* Get the next entry and validate it */
317 Entry = PrefixTable->NextPrefixTree;
318 if (Entry->NodeTypeCode == PFX_NTC_TABLE) return NULL;
319
320 /* Now get the Splay Tree Links */
321 SplayLinks = &Entry->Links;
322
323 /* Loop until we get the first node in the tree */
324 while (RtlLeftChild(SplayLinks)) SplayLinks = RtlLeftChild(SplayLinks);
325
326 /* Get the entry from it */
327 Entry = CONTAINING_RECORD(SplayLinks,
328 UNICODE_PREFIX_TABLE_ENTRY,
329 Links);
330 }
331 else if (CaseMatchEntry->NodeTypeCode == PFX_NTC_CASE_MATCH)
332 {
333 /* If the last entry was a Case Match, then return it */
334 Entry = CaseMatchEntry;
335 }
336 else
337 {
338 /* Find the successor */
339 SplayLinks = RtlRealSuccessor(&CaseMatchEntry->Links);
340 if (!SplayLinks)
341 {
342 /* Didn't find one, we'll have to search the tree */
343 SplayLinks = &PrefixTable->LastNextEntry->Links;
344
345 /* Get the topmost node (root) */
346 while (!RtlIsRoot(SplayLinks)) SplayLinks = RtlParent(SplayLinks);
347 Entry = CONTAINING_RECORD(SplayLinks,
348 UNICODE_PREFIX_TABLE_ENTRY,
349 Links);
350
351 /* Get its tree and make sure somethign is in it */
352 Entry = Entry->NextPrefixTree;
353 if (Entry->NameLength <= 0) return NULL;
354
355 /* Select these new links and find the first node */
356 while (RtlLeftChild(SplayLinks)) SplayLinks = RtlLeftChild(SplayLinks);
357 }
358
359 /* Get the entry from it */
360 Entry = CONTAINING_RECORD(SplayLinks,
361 UNICODE_PREFIX_TABLE_ENTRY,
362 Links);
363 }
364
365 /* Save this entry as the last one returned, and return it */
366 PrefixTable->LastNextEntry = Entry;
367 return Entry;
368 }
369
370 /*
371 * @implemented
372 */
373 VOID
374 NTAPI
375 RtlRemoveUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
376 PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry)
377 {
378 PUNICODE_PREFIX_TABLE_ENTRY Entry, RefEntry, NewEntry;
379 PRTL_SPLAY_LINKS SplayLinks;
380
381 /* Erase the last entry */
382 PrefixTable->LastNextEntry = NULL;
383
384 /* Check if this was a Case Match Entry */
385 if (PrefixTableEntry->NodeTypeCode == PFX_NTC_CASE_MATCH)
386 {
387 /* Get the case match entry */
388 Entry = PrefixTableEntry->CaseMatch;
389
390 /* Now loop until we find one referencing what the caller sent */
391 while (Entry->CaseMatch != PrefixTableEntry) Entry = Entry->CaseMatch;
392
393 /* We found the entry that was sent, link them to delete this entry */
394 Entry->CaseMatch = PrefixTableEntry->CaseMatch;
395 }
396 else if ((PrefixTableEntry->NodeTypeCode == PFX_NTC_ROOT) ||
397 (PrefixTableEntry->NodeTypeCode == PFX_NTC_CHILD))
398 {
399 /* Check if this entry is a case match */
400 if (PrefixTableEntry->CaseMatch != PrefixTableEntry)
401 {
402 /* Get the case match entry */
403 Entry = PrefixTableEntry->CaseMatch;
404
405 /* Now loop until we find one referencing what the caller sent */
406 while (Entry->CaseMatch != PrefixTableEntry) Entry = Entry->CaseMatch;
407
408 /* We found the entry that was sent, link them to delete this entry */
409 Entry->CaseMatch = PrefixTableEntry->CaseMatch;
410
411 /* Copy the data */
412 Entry->NodeTypeCode = PrefixTableEntry->NodeTypeCode;
413 Entry->NextPrefixTree = PrefixTableEntry->NextPrefixTree;
414 Entry->Links = PrefixTableEntry->Links;
415
416 /* Now check if we are a root entry */
417 if (RtlIsRoot(&PrefixTableEntry->Links))
418 {
419 /* We are, so make this entry root as well */
420 Entry->Links.Parent = &Entry->Links;
421
422 /* Find the entry referencing us */
423 RefEntry = Entry->NextPrefixTree;
424 while (RefEntry->NextPrefixTree != Entry)
425 {
426 /* Not this one, move to the next entry */
427 RefEntry = RefEntry->NextPrefixTree;
428 }
429
430 /* Link them to us now */
431 RefEntry->NextPrefixTree = Entry;
432 }
433 else if (RtlIsLeftChild(&PrefixTableEntry->Links))
434 {
435 /* We were the left child, so make us as well */
436 RtlParent(&PrefixTableEntry->Links)->LeftChild = &Entry->Links;
437 }
438 else
439 {
440 /* We were the right child, so make us as well */
441 RtlParent(&PrefixTableEntry->Links)->RightChild = &Entry->Links;
442 }
443
444 /* Check if we have a left child */
445 if (RtlLeftChild(&Entry->Links))
446 {
447 /* Update its parent link */
448 RtlLeftChild(&Entry->Links)->Parent = &Entry->Links;
449 }
450 /* Check if we have a right child */
451 if (RtlRightChild(&Entry->Links))
452 {
453 /* Update its parent link */
454 RtlRightChild(&Entry->Links)->Parent = &Entry->Links;
455 }
456 }
457 else
458 {
459 /* It's not a case match, so we'll delete the actual entry */
460 SplayLinks = &PrefixTableEntry->Links;
461
462 /* Find the root entry */
463 while (!RtlIsRoot(SplayLinks)) SplayLinks = RtlParent(SplayLinks);
464 Entry = CONTAINING_RECORD(SplayLinks,
465 UNICODE_PREFIX_TABLE_ENTRY,
466 Links);
467
468 /* Delete the entry and check if the whole tree is gone */
469 SplayLinks = RtlDelete(&PrefixTableEntry->Links);
470 if (!SplayLinks)
471 {
472 /* The tree is also gone now, find the entry referencing us */
473 RefEntry = Entry->NextPrefixTree;
474 while (RefEntry->NextPrefixTree != Entry)
475 {
476 /* Not this one, move to the next entry */
477 RefEntry = RefEntry->NextPrefixTree;
478 }
479
480 /* Link them so this entry stops being referenced */
481 RefEntry->NextPrefixTree = Entry->NextPrefixTree;
482 }
483 else if (&Entry->Links != SplayLinks)
484 {
485 /* The tree is still here, but we got moved to a new one */
486 NewEntry = CONTAINING_RECORD(SplayLinks,
487 UNICODE_PREFIX_TABLE_ENTRY,
488 Links);
489
490 /* Find the entry referencing us */
491 RefEntry = Entry->NextPrefixTree;
492 while (RefEntry->NextPrefixTree != Entry)
493 {
494 /* Not this one, move to the next entry */
495 RefEntry = RefEntry->NextPrefixTree;
496 }
497
498 /* Since we got moved, make us the new root entry */
499 NewEntry->NodeTypeCode = PFX_NTC_ROOT;
500
501 /* Link us with the entry referencing the old root */
502 RefEntry->NextPrefixTree = NewEntry;
503
504 /* And link us with the old tree */
505 NewEntry->NextPrefixTree = Entry->NextPrefixTree;
506
507 /* Set the old tree as a child */
508 Entry->NodeTypeCode = PFX_NTC_CHILD;
509 Entry->NextPrefixTree = NULL;
510 }
511 }
512 }
513 }
514
515 /* EOF */