- Don't use STATIC
[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 static
48 RTL_GENERIC_COMPARE_RESULTS
49 NTAPI
50 CompareUnicodeStrings(IN PUNICODE_STRING Prefix,
51 IN PUNICODE_STRING String,
52 IN ULONG CaseCheckChar)
53 {
54 ULONG StringLength = String->Length / sizeof(WCHAR);
55 ULONG PrefixLength = Prefix->Length / sizeof(WCHAR);
56 ULONG ScanLength = min(StringLength, PrefixLength);
57 ULONG i;
58 WCHAR FoundPrefix, FoundString;
59 PWCHAR p, p1;
60 DPRINT("CompareUnicodeStrings: %wZ %wZ\n", String, Prefix);
61
62 /* Handle case noticed in npfs when Prefix = '\' and name starts with '\' */
63 if ((PrefixLength == 1) &&
64 (Prefix->Buffer[0] == '\\') &&
65 (StringLength > 1) &&
66 (String->Buffer[0] == '\\'))
67 {
68 /* The string is actually a prefix */
69 return -1;
70 }
71
72 /* Validate the Case Check Character Position */
73 if (CaseCheckChar > ScanLength) CaseCheckChar = ScanLength;
74
75 /* Do the case sensitive comparison first */
76 for (i = 0; i < CaseCheckChar; i++)
77 {
78 /* Compare the two characters */
79 if (Prefix->Buffer[i] != String->Buffer[i]) break;
80 }
81
82 /* Save the characters we found */
83 FoundPrefix = Prefix->Buffer[i];
84 FoundString = String->Buffer[i];
85
86 /* Check if we exausted the search above */
87 if (i == CaseCheckChar)
88 {
89 /* Do a case-insensitive search */
90 p = &Prefix->Buffer[i];
91 p1 = &String->Buffer[i];
92 do
93 {
94 /* Move to the next character */
95 FoundPrefix = *p++;
96 FoundString = *p1++;
97
98 /* Compare it */
99 if (FoundPrefix != FoundString)
100 {
101 /* Upcase the characters */
102 FoundPrefix = RtlUpcaseUnicodeChar(FoundPrefix);
103 FoundString = RtlUpcaseUnicodeChar(FoundString);
104
105 /* Compare them again */
106 if (FoundPrefix != FoundString) break;
107 }
108
109 /* Move to the next char */
110 i++;
111 } while (i < ScanLength);
112 }
113
114 /* Check if we weren't able to find a match in the loops */
115 if (i < ScanLength)
116 {
117 /* If the prefix character found was a backslash, this is a less */
118 if (FoundPrefix == '\\') return GenericLessThan;
119
120 /* If the string character found was a backslack, then this is a more */
121 if (FoundString == '\\') return GenericGreaterThan;
122
123 /* None of those two special cases, do a normal check */
124 if (FoundPrefix < FoundString) return GenericLessThan;
125
126 /* The only choice left is that Prefix > String */
127 return GenericGreaterThan;
128 }
129
130 /* If we got here, a match was found. Check if the prefix is smaller */
131 if (PrefixLength < StringLength)
132 {
133 /* Check if the string is actually a prefix */
134 if (String->Buffer[PrefixLength] == '\\') return -1;
135
136 /* It's not a prefix, and it's shorter, so it's a less */
137 return GenericLessThan;
138 }
139
140 /* Check if the prefix is longer */
141 if (PrefixLength > StringLength) return GenericGreaterThan;
142
143 /* If we got here, then they are 100% equal */
144 return GenericEqual;
145 }
146
147 /*
148 * @implemented
149 */
150 PUNICODE_PREFIX_TABLE_ENTRY
151 NTAPI
152 RtlFindUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
153 PUNICODE_STRING FullName,
154 ULONG CaseInsensitiveIndex)
155 {
156 ULONG NameCount;
157 PUNICODE_PREFIX_TABLE_ENTRY CurrentEntry, PreviousEntry, Entry, NextEntry;
158 PRTL_SPLAY_LINKS SplayLinks;
159 RTL_GENERIC_COMPARE_RESULTS Result;
160 DPRINT("RtlFindUnicodePrefix\n");
161
162 /* Find out how many names there are */
163 NameCount = ComputeUnicodeNameLength(FullName);
164
165 /* Find the right spot where to start looking for this entry */
166 PreviousEntry = (PUNICODE_PREFIX_TABLE_ENTRY)PrefixTable;
167 CurrentEntry = PreviousEntry->NextPrefixTree;
168 while (CurrentEntry->NameLength > NameCount)
169 {
170 /* Not a match, move to the next entry */
171 PreviousEntry = CurrentEntry;
172 CurrentEntry = CurrentEntry->NextPrefixTree;
173 }
174
175 /* Loop every entry which has valid entries */
176 while (CurrentEntry->NameLength)
177 {
178 DPRINT("CurrentEntry->NameLength %lx\n", CurrentEntry->NameLength);
179
180 /* Get the splay links and loop */
181 SplayLinks = &CurrentEntry->Links;
182 while (SplayLinks)
183 {
184 /* Get the entry */
185 DPRINT("SplayLinks %p\n", SplayLinks);
186 Entry = CONTAINING_RECORD(SplayLinks,
187 UNICODE_PREFIX_TABLE_ENTRY,
188 Links);
189
190 /* Do the comparison */
191 Result = CompareUnicodeStrings(Entry->Prefix, FullName, 0);
192 DPRINT("Result %lx\n", Result);
193 if (Result == GenericGreaterThan)
194 {
195 /* Prefix is greater, so restart on the left child */
196 SplayLinks = RtlLeftChild(SplayLinks);
197 continue;
198 }
199 else if (Result == GenericLessThan)
200 {
201 /* Prefix is smaller, so restart on the right child */
202 SplayLinks = RtlRightChild(SplayLinks);
203 continue;
204 }
205
206 /*
207 * We have a match, check if this was a case-sensitive search
208 * NOTE: An index of 0 means case-insensitive(ie, we'll be case
209 * insensitive since index 0, ie, all the time)
210 */
211 DPRINT("CaseInsensitiveIndex %lx\n", CaseInsensitiveIndex);
212 if (!CaseInsensitiveIndex)
213 {
214 /*
215 * Check if this entry was a child. We need to return the root,
216 * so if this entry was a child, we'll splay the tree and get
217 * the root, and set the current entry as a child.
218 */
219 if (Entry->NodeTypeCode == PFX_NTC_CHILD)
220 {
221 /* Get the next entry */
222 NextEntry = CurrentEntry->NextPrefixTree;
223
224 /* Make the current entry become a child */
225 CurrentEntry->NodeTypeCode = PFX_NTC_CHILD;
226 CurrentEntry->NextPrefixTree = NULL;
227
228 /* Splay the tree */
229 SplayLinks = RtlSplay(&Entry->Links);
230
231 /* Get the new root entry */
232 Entry = CONTAINING_RECORD(SplayLinks,
233 UNICODE_PREFIX_TABLE_ENTRY,
234 Links);
235
236 /* Set it as a root entry */
237 Entry->NodeTypeCode = PFX_NTC_ROOT;
238
239 /* Add it to the root entries list */
240 PreviousEntry->NextPrefixTree = Entry;
241 Entry->NextPrefixTree = NextEntry;
242 }
243
244 /* Return the entry */
245 DPRINT("RtlFindUnicodePrefix: %p\n", Entry);
246 return Entry;
247 }
248
249 /* We'll do a case-sensitive search if we've reached this point */
250 NextEntry = Entry;
251 do
252 {
253 /* Do the case-sensitive search */
254 Result = CompareUnicodeStrings(NextEntry->Prefix,
255 FullName,
256 CaseInsensitiveIndex);
257 if ((Result != GenericLessThan) &&
258 (Result != GenericGreaterThan))
259 {
260 /* This is a positive match, return it */
261 DPRINT("RtlFindUnicodePrefix: %p\n", NextEntry);
262 return NextEntry;
263 }
264
265 /* No match yet, continue looping the circular list */
266 NextEntry = NextEntry->CaseMatch;
267 DPRINT("NextEntry %p\n", NextEntry);
268 } while (NextEntry != Entry);
269
270 /*
271 * If we got here, then we found a non-case-sensitive match, but
272 * we need to find a case-sensitive match, so we'll just keep
273 * searching the next tree (NOTE: we need to break out for this).
274 */
275 break;
276 }
277
278 /* Splay links exausted, move to next entry */
279 PreviousEntry = CurrentEntry;
280 CurrentEntry = CurrentEntry->NextPrefixTree;
281 DPRINT("CurrentEntry %p\n", CurrentEntry);
282 }
283
284 /* If we got here, nothing was found */
285 DPRINT("RtlFindUnicodePrefix: %p\n", NULL);
286 return NULL;
287 }
288
289 /*
290 * @implemented
291 */
292 VOID
293 NTAPI
294 RtlInitializeUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable)
295 {
296 /* Setup the table */
297 PrefixTable->NameLength = 0;
298 PrefixTable->LastNextEntry = NULL;
299 PrefixTable->NodeTypeCode = PFX_NTC_TABLE;
300 PrefixTable->NextPrefixTree = (PUNICODE_PREFIX_TABLE_ENTRY)PrefixTable;
301 }
302
303 /*
304 * @implemented
305 */
306 BOOLEAN
307 NTAPI
308 RtlInsertUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
309 PUNICODE_STRING Prefix,
310 PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry)
311 {
312 PUNICODE_PREFIX_TABLE_ENTRY CurrentEntry, PreviousEntry, Entry, NextEntry;
313 ULONG NameCount;
314 RTL_GENERIC_COMPARE_RESULTS Result;
315 PRTL_SPLAY_LINKS SplayLinks;
316 DPRINT("RtlInsertUnicodePrefix\n");
317
318 /* Find out how many names there are */
319 NameCount = ComputeUnicodeNameLength(Prefix);
320
321 /* Set up the initial entry data */
322 PrefixTableEntry->NameLength = NameCount;
323 PrefixTableEntry->Prefix = Prefix;
324 RtlInitializeSplayLinks(&PrefixTableEntry->Links);
325
326 /* Find the right spot where to insert this entry */
327 PreviousEntry = (PUNICODE_PREFIX_TABLE_ENTRY)PrefixTable;
328 CurrentEntry = PreviousEntry->NextPrefixTree;
329 while (CurrentEntry->NameLength > NameCount)
330 {
331 /* Not a match, move to the next entry */
332 PreviousEntry = CurrentEntry;
333 CurrentEntry = CurrentEntry->NextPrefixTree;
334 }
335
336 /* Check if we did find a tree by now */
337 if (CurrentEntry->NameLength != NameCount)
338 {
339 /* We didn't, so insert a new entry in the list */
340 PreviousEntry->NextPrefixTree = PrefixTableEntry;
341 PrefixTableEntry->NextPrefixTree = CurrentEntry;
342
343 /* This is now a root entry with case match */
344 PrefixTableEntry->NodeTypeCode = PFX_NTC_ROOT;
345 PrefixTableEntry->CaseMatch = PrefixTableEntry;
346
347 /* Quick return */
348 DPRINT("RtlInsertUnicodePrefix TRUE\n");
349 return TRUE;
350 }
351
352 /* We found a tree, so star thte search loop */
353 Entry = CurrentEntry;
354 while (TRUE)
355 {
356 /* Do a case-insensitive comparison to find out the match level */
357 Result = CompareUnicodeStrings(Entry->Prefix, Prefix, 0);
358 if (Result == GenericEqual)
359 {
360 /* We have a match, start doing a case-sensitive search */
361 NextEntry = Entry;
362
363 /* Search the circular case-match list */
364 do
365 {
366 /* Check if we found a match */
367 if (CompareUnicodeStrings(NextEntry->Prefix, Prefix, -1) ==
368 (GenericEqual))
369 {
370 /* We must fail the insert: it already exists */
371 DPRINT("RtlInsertUnicodePrefix FALSE\n");
372 return FALSE;
373 }
374
375 /* Move to the next entry in the circular list */
376 NextEntry = NextEntry->CaseMatch;
377 }
378 while (NextEntry != Entry);
379
380 /*
381 * No match found, so we can safely insert it. Remember that a
382 * case insensitive match was found, so this is not a ROOT NTC
383 * but a Case Match NTC instead.
384 */
385 PrefixTableEntry->NodeTypeCode = PFX_NTC_CASE_MATCH;
386 PrefixTableEntry->NextPrefixTree = NULL;
387
388 /* Insert it into the circular list */
389 PrefixTableEntry->CaseMatch = Entry->CaseMatch;
390 Entry->CaseMatch = PrefixTableEntry;
391 break;
392 }
393
394 /* Check if the result was greater or lesser than */
395 if (Result == GenericGreaterThan)
396 {
397 /* Check out if we have a left child */
398 if (RtlLeftChild(&Entry->Links))
399 {
400 /* We do, enter it and restart the loop */
401 SplayLinks = RtlLeftChild(&Entry->Links);
402 Entry = CONTAINING_RECORD(SplayLinks,
403 UNICODE_PREFIX_TABLE_ENTRY,
404 Links);
405 }
406 else
407 {
408 /* We don't, set this entry as a child */
409 PrefixTableEntry->NodeTypeCode = PFX_NTC_CHILD;
410 PrefixTableEntry->NextPrefixTree = NULL;
411 PrefixTableEntry->CaseMatch = PrefixTableEntry;
412
413 /* Insert us into the tree */
414 RtlInsertAsLeftChild(&Entry->Links, &PrefixTableEntry->Links);
415 break;
416 }
417 }
418 else
419 {
420 /* Check out if we have a right child */
421 if (RtlRightChild(&Entry->Links))
422 {
423 /* We do, enter it and restart the loop */
424 SplayLinks = RtlLeftChild(&Entry->Links);
425 Entry = CONTAINING_RECORD(SplayLinks,
426 UNICODE_PREFIX_TABLE_ENTRY,
427 Links);
428 }
429 else
430 {
431 /* We don't, set this entry as a child */
432 PrefixTableEntry->NodeTypeCode = PFX_NTC_CHILD;
433 PrefixTableEntry->NextPrefixTree = NULL;
434 PrefixTableEntry->CaseMatch = PrefixTableEntry;
435
436 /* Insert us into the tree */
437 RtlInsertAsRightChild(&Entry->Links, &PrefixTableEntry->Links);
438 break;
439 }
440 }
441 }
442
443 /* Get the next tree entry */
444 NextEntry = CurrentEntry->NextPrefixTree;
445
446 /* Set what was the current entry to a child entry */
447 CurrentEntry->NodeTypeCode = PFX_NTC_CHILD;
448 CurrentEntry->NextPrefixTree = NULL;
449
450 /* Splay the tree */
451 SplayLinks = RtlSplay(&Entry->Links);
452
453 /* The link points to the root, get it */
454 Entry = CONTAINING_RECORD(SplayLinks, UNICODE_PREFIX_TABLE_ENTRY, Links);
455
456 /* Mark the root as a root entry */
457 Entry->NodeTypeCode = PFX_NTC_ROOT;
458
459 /* Add it to the tree list */
460 PreviousEntry->NextPrefixTree = Entry;
461 Entry->NextPrefixTree = NextEntry;
462
463 /* Return success */
464 DPRINT("RtlInsertUnicodePrefix TRUE\n");
465 return TRUE;
466 }
467
468 /*
469 * @implemented
470 */
471 PUNICODE_PREFIX_TABLE_ENTRY
472 NTAPI
473 RtlNextUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
474 BOOLEAN Restart)
475 {
476 PRTL_SPLAY_LINKS SplayLinks;
477 PUNICODE_PREFIX_TABLE_ENTRY Entry, CaseMatchEntry;
478 DPRINT("RtlNextUnicodePrefix\n");
479
480 /* We might need this entry 2/3rd of the time, so cache it now */
481 CaseMatchEntry = PrefixTable->LastNextEntry->CaseMatch;
482
483 /* Check if this is a restart or if we don't have a last entry */
484 if ((Restart) || !(PrefixTable->LastNextEntry))
485 {
486 /* Get the next entry and validate it */
487 Entry = PrefixTable->NextPrefixTree;
488 if (Entry->NodeTypeCode == PFX_NTC_TABLE) return NULL;
489
490 /* Now get the Splay Tree Links */
491 SplayLinks = &Entry->Links;
492
493 /* Loop until we get the first node in the tree */
494 while (RtlLeftChild(SplayLinks)) SplayLinks = RtlLeftChild(SplayLinks);
495
496 /* Get the entry from it */
497 Entry = CONTAINING_RECORD(SplayLinks,
498 UNICODE_PREFIX_TABLE_ENTRY,
499 Links);
500 }
501 else if (CaseMatchEntry->NodeTypeCode == PFX_NTC_CASE_MATCH)
502 {
503 /* If the last entry was a Case Match, then return it */
504 Entry = CaseMatchEntry;
505 }
506 else
507 {
508 /* Find the successor */
509 SplayLinks = RtlRealSuccessor(&CaseMatchEntry->Links);
510 if (!SplayLinks)
511 {
512 /* Didn't find one, we'll have to search the tree */
513 SplayLinks = &PrefixTable->LastNextEntry->Links;
514
515 /* Get the topmost node (root) */
516 while (!RtlIsRoot(SplayLinks)) SplayLinks = RtlParent(SplayLinks);
517 Entry = CONTAINING_RECORD(SplayLinks,
518 UNICODE_PREFIX_TABLE_ENTRY,
519 Links);
520
521 /* Get its tree and make sure somethign is in it */
522 Entry = Entry->NextPrefixTree;
523 if (Entry->NameLength <= 0) return NULL;
524
525 /* Select these new links and find the first node */
526 while (RtlLeftChild(SplayLinks)) SplayLinks = RtlLeftChild(SplayLinks);
527 }
528
529 /* Get the entry from it */
530 Entry = CONTAINING_RECORD(SplayLinks,
531 UNICODE_PREFIX_TABLE_ENTRY,
532 Links);
533 }
534
535 /* Save this entry as the last one returned, and return it */
536 PrefixTable->LastNextEntry = Entry;
537 DPRINT("RtlNextUnicodePrefix: %p\n", Entry);
538 return Entry;
539 }
540
541 /*
542 * @implemented
543 */
544 VOID
545 NTAPI
546 RtlRemoveUnicodePrefix(PUNICODE_PREFIX_TABLE PrefixTable,
547 PUNICODE_PREFIX_TABLE_ENTRY PrefixTableEntry)
548 {
549 PUNICODE_PREFIX_TABLE_ENTRY Entry, RefEntry, NewEntry;
550 PRTL_SPLAY_LINKS SplayLinks;
551 DPRINT("RtlRemoveUnicodePrefix\n");
552
553 /* Erase the last entry */
554 PrefixTable->LastNextEntry = NULL;
555
556 /* Check if this was a Case Match Entry */
557 if (PrefixTableEntry->NodeTypeCode == PFX_NTC_CASE_MATCH)
558 {
559 /* Get the case match entry */
560 Entry = PrefixTableEntry->CaseMatch;
561
562 /* Now loop until we find one referencing what the caller sent */
563 while (Entry->CaseMatch != PrefixTableEntry) Entry = Entry->CaseMatch;
564
565 /* We found the entry that was sent, link them to delete this entry */
566 Entry->CaseMatch = PrefixTableEntry->CaseMatch;
567 }
568 else if ((PrefixTableEntry->NodeTypeCode == PFX_NTC_ROOT) ||
569 (PrefixTableEntry->NodeTypeCode == PFX_NTC_CHILD))
570 {
571 /* Check if this entry is a case match */
572 if (PrefixTableEntry->CaseMatch != PrefixTableEntry)
573 {
574 /* Get the case match entry */
575 Entry = PrefixTableEntry->CaseMatch;
576
577 /* Now loop until we find one referencing what the caller sent */
578 while (Entry->CaseMatch != PrefixTableEntry) Entry = Entry->CaseMatch;
579
580 /* We found the entry that was sent, link them to delete this entry */
581 Entry->CaseMatch = PrefixTableEntry->CaseMatch;
582
583 /* Copy the data */
584 Entry->NodeTypeCode = PrefixTableEntry->NodeTypeCode;
585 Entry->NextPrefixTree = PrefixTableEntry->NextPrefixTree;
586 Entry->Links = PrefixTableEntry->Links;
587
588 /* Now check if we are a root entry */
589 if (RtlIsRoot(&PrefixTableEntry->Links))
590 {
591 /* We are, so make this entry root as well */
592 Entry->Links.Parent = &Entry->Links;
593
594 /* Find the entry referencing us */
595 RefEntry = Entry->NextPrefixTree;
596 while (RefEntry->NextPrefixTree != Entry)
597 {
598 /* Not this one, move to the next entry */
599 RefEntry = RefEntry->NextPrefixTree;
600 }
601
602 /* Link them to us now */
603 RefEntry->NextPrefixTree = Entry;
604 }
605 else if (RtlIsLeftChild(&PrefixTableEntry->Links))
606 {
607 /* We were the left child, so make us as well */
608 RtlParent(&PrefixTableEntry->Links)->LeftChild = &Entry->Links;
609 }
610 else
611 {
612 /* We were the right child, so make us as well */
613 RtlParent(&PrefixTableEntry->Links)->RightChild = &Entry->Links;
614 }
615
616 /* Check if we have a left child */
617 if (RtlLeftChild(&Entry->Links))
618 {
619 /* Update its parent link */
620 RtlLeftChild(&Entry->Links)->Parent = &Entry->Links;
621 }
622 /* Check if we have a right child */
623 if (RtlRightChild(&Entry->Links))
624 {
625 /* Update its parent link */
626 RtlRightChild(&Entry->Links)->Parent = &Entry->Links;
627 }
628 }
629 else
630 {
631 /* It's not a case match, so we'll delete the actual entry */
632 SplayLinks = &PrefixTableEntry->Links;
633
634 /* Find the root entry */
635 while (!RtlIsRoot(SplayLinks)) SplayLinks = RtlParent(SplayLinks);
636 Entry = CONTAINING_RECORD(SplayLinks,
637 UNICODE_PREFIX_TABLE_ENTRY,
638 Links);
639
640 /* Delete the entry and check if the whole tree is gone */
641 SplayLinks = RtlDelete(&PrefixTableEntry->Links);
642 if (!SplayLinks)
643 {
644 /* The tree is also gone now, find the entry referencing us */
645 RefEntry = Entry->NextPrefixTree;
646 while (RefEntry->NextPrefixTree != Entry)
647 {
648 /* Not this one, move to the next entry */
649 RefEntry = RefEntry->NextPrefixTree;
650 }
651
652 /* Link them so this entry stops being referenced */
653 RefEntry->NextPrefixTree = Entry->NextPrefixTree;
654 }
655 else if (&Entry->Links != SplayLinks)
656 {
657 /* The tree is still here, but we got moved to a new one */
658 NewEntry = CONTAINING_RECORD(SplayLinks,
659 UNICODE_PREFIX_TABLE_ENTRY,
660 Links);
661
662 /* Find the entry referencing us */
663 RefEntry = Entry->NextPrefixTree;
664 while (RefEntry->NextPrefixTree != Entry)
665 {
666 /* Not this one, move to the next entry */
667 RefEntry = RefEntry->NextPrefixTree;
668 }
669
670 /* Since we got moved, make us the new root entry */
671 NewEntry->NodeTypeCode = PFX_NTC_ROOT;
672
673 /* Link us with the entry referencing the old root */
674 RefEntry->NextPrefixTree = NewEntry;
675
676 /* And link us with the old tree */
677 NewEntry->NextPrefixTree = Entry->NextPrefixTree;
678
679 /* Set the old tree as a child */
680 Entry->NodeTypeCode = PFX_NTC_CHILD;
681 Entry->NextPrefixTree = NULL;
682 }
683 }
684 }
685 }
686
687 /* EOF */