projects / reactos.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
- Implement NtDeleteKey as a simpler wrapper around CmDeleteKey.
[reactos.git] / reactos / ntoskrnl / config / cmindex.c
1 /*
2 * PROJECT: ReactOS Kernel
3 * LICENSE: GPL - See COPYING in the top level directory
4 * FILE: ntoskrnl/config/cmindex.c
5 * PURPOSE: Configuration Manager - Cell Indexes
6 * PROGRAMMERS: Alex Ionescu (alex.ionescu@reactos.org)
7 */
8
9 /* INCLUDES ******************************************************************/
10
11 #include "ntoskrnl.h"
12 #include "cm.h"
13 #define NDEBUG
14 #include "debug.h"
15
16 /* GLOBALS *******************************************************************/
17
18 /* FUNCTIONS *****************************************************************/
19
20 LONG
21 NTAPI
22 CmpDoCompareKeyName(IN PHHIVE Hive,
23 IN PUNICODE_STRING SearchName,
24 IN HCELL_INDEX Cell)
25 {
26 PCM_KEY_NODE Node;
27 UNICODE_STRING KeyName;
28 LONG Result;
29
30 /* Get the node */
31 Node = (PCM_KEY_NODE)HvGetCell(Hive, Cell);
32 if (!Node) return 2;
33
34 /* Check if it's compressed */
35 if (Node->Flags & KEY_COMP_NAME)
36 {
37 /* Compare compressed names */
38 Result = CmpCompareCompressedName(SearchName,
39 Node->Name,
40 Node->NameLength);
41 }
42 else
43 {
44 /* Compare the Unicode name directly */
45 KeyName.Buffer = Node->Name;
46 KeyName.Length = Node->NameLength;
47 KeyName.MaximumLength = KeyName.Length;
48 Result = RtlCompareUnicodeString(SearchName, &KeyName, TRUE);
49 }
50
51 /* Release the cell and return the normalized result */
52 HvReleaseCell(Hive, Cell);
53 return (Result == 0) ? Result : ((Result > 0) ? 1 : -1);
54 }
55
56 LONG
57 NTAPI
58 CmpCompareInIndex(IN PHHIVE Hive,
59 IN PUNICODE_STRING SearchName,
60 IN ULONG Count,
61 IN PCM_KEY_INDEX Index,
62 IN PHCELL_INDEX SubKey)
63 {
64 PCM_KEY_FAST_INDEX FastIndex;
65 PCM_INDEX FastEntry;
66 LONG Result;
67 ULONG i;
68 ULONG ActualNameLength = 4, CompareLength, NameLength;
69 WCHAR p, pp;
70
71 /* Assume failure */
72 *SubKey = HCELL_NIL;
73
74 /* Check if we are a fast or hashed leaf */
75 if ((Index->Signature == CM_KEY_FAST_LEAF) ||
76 (Index->Signature == CM_KEY_HASH_LEAF))
77 {
78 /* Get the Fast/Hash Index */
79 FastIndex = (PCM_KEY_FAST_INDEX)Index;
80 FastEntry = &FastIndex->List[Count];
81
82 /* Check if we are a hash leaf, in which case we skip all this */
83 if (Index->Signature == CM_KEY_FAST_LEAF)
84 {
85 /* Find out just how much of the name is there */
86 for (i = 0; i < 4; i++)
87 {
88 /* Check if this entry is empty */
89 if (!FastEntry->NameHint[i])
90 {
91 /* Only this much! */
92 ActualNameLength = i;
93 break;
94 }
95 }
96
97 /* How large is the name and how many characters to compare */
98 NameLength = SearchName->Length / sizeof(WCHAR);
99 CompareLength = min(NameLength, ActualNameLength);
100
101 /* Loop all the chars we'll test */
102 for (i = 0; i < CompareLength; i++)
103 {
104 /* Get one char from each buffer */
105 p = SearchName->Buffer[i];
106 pp = FastEntry->NameHint[i];
107
108 /* See if they match and return result if they don't */
109 Result = (LONG)RtlUpcaseUnicodeChar(p) -
110 (LONG)RtlUpcaseUnicodeChar(pp);
111 if (Result) return (Result > 0) ? 1 : -1;
112 }
113 }
114
115 /* If we got here then we have to do a full compare */
116 Result = CmpDoCompareKeyName(Hive, SearchName, FastEntry->Cell);
117 if (Result == 2) return Result;
118 if (!Result) *SubKey = FastEntry->Cell;
119 }
120 else
121 {
122 /* We aren't, so do a name compare and return the subkey found */
123 Result = CmpDoCompareKeyName(Hive, SearchName, Index->List[Count]);
124 if (Result == 2) return Result;
125 if (!Result) *SubKey = Index->List[Count];
126 }
127
128 /* Return the comparison result */
129 return Result;
130 }
131
132 ULONG
133 NTAPI
134 CmpFindSubKeyInRoot(IN PHHIVE Hive,
135 IN PCM_KEY_INDEX Index,
136 IN PUNICODE_STRING SearchName,
137 IN PHCELL_INDEX SubKey)
138 {
139 ULONG High, Low = 0, i, ReturnIndex;
140 HCELL_INDEX LeafCell;
141 PCM_KEY_INDEX Leaf;
142 LONG Result;
143
144 /* Verify Index for validity */
145 ASSERTMSG("We don't do a linear search yet!\n", FALSE);
146 ASSERT(Index->Count != 0);
147 ASSERT(Index->Signature == CM_KEY_INDEX_ROOT);
148
149 /* Set high limit and loop */
150 High = Index->Count - 1;
151 while (TRUE)
152 {
153 /* Choose next entry */
154 i = ((High - Low) / 2) + Low;
155
156 /* Get the leaf cell and then the leaf itself */
157 LeafCell = Index->List[i];
158 Leaf = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
159 if (Leaf)
160 {
161 /* Make sure the leaf is valid */
162 ASSERT((Leaf->Signature == CM_KEY_INDEX_LEAF) ||
163 (Leaf->Signature == CM_KEY_FAST_LEAF) ||
164 (Leaf->Signature == CM_KEY_HASH_LEAF));
165 ASSERT(Leaf->Count != 0);
166
167 /* Do the compare */
168 Result = CmpCompareInIndex(Hive,
169 SearchName,
170 Leaf->Count - 1,
171 Leaf,
172 SubKey);
173 if (Result == 2) goto Big;
174
175 /* Check if we found the leaf */
176 if (!Result)
177 {
178 /* We found the leaf */
179 *SubKey = LeafCell;
180 ReturnIndex = i;
181 goto Return;
182 }
183
184 /* Check for negative result */
185 if (Result < 0)
186 {
187 /* If we got here, we should be at -1 */
188 ASSERT(Result == -1);
189
190 /* Do another lookup, since we might still be in the right leaf */
191 Result = CmpCompareInIndex(Hive,
192 SearchName,
193 0,
194 Leaf,
195 SubKey);
196 if (Result == 2) goto Big;
197
198 /* Check if it's not below */
199 if (Result >= 0)
200 {
201 /*
202 * If the name was first below, and now it is above,
203 * then this means that it is somewhere in this leaf.
204 * Make sure we didn't get some weird result
205 */
206 ASSERT((Result == 1) || (Result == 0));
207
208 /* Return it */
209 *SubKey = LeafCell;
210 ReturnIndex = Low;
211 goto Return;
212 }
213
214 /* Update the limit to this index, since we know it's not higher. */
215 High = i;
216 }
217 else
218 {
219 /* Update the base to this index, since we know it's not lower. */
220 Low = i;
221 }
222 }
223 else
224 {
225 Big:
226 /* This was some sort of special key */
227 ReturnIndex = 0x80000000;
228 goto ReturnFailure;
229 }
230
231 /* Check if there is only one entry left */
232 if ((High - Low) <= 1) break;
233
234 /* Release the leaf cell */
235 HvReleaseCell(Hive, LeafCell);
236 }
237
238 /* Make sure we got here for the right reasons */
239 ASSERT((High - Low == 1) || (High == Low));
240
241 /* Get the leaf cell and the leaf */
242 LeafCell = Index->List[Low];
243 Leaf = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
244 if (!Leaf) goto Big;
245
246 /* Do the compare */
247 Result = CmpCompareInIndex(Hive,
248 SearchName,
249 Leaf->Count-1,
250 Leaf,
251 SubKey);
252 if (Result == 2) goto Big;
253
254 /* Check if we found it */
255 if (!Result)
256 {
257 /* We got lucky...return it */
258 *SubKey = LeafCell;
259 ReturnIndex = Low;
260 goto Return;
261 }
262
263 /* It's below, so could still be in this leaf */
264 if (Result < 0)
265 {
266 /* Make sure we're -1 */
267 ASSERT(Result == -1);
268
269 /* Do a search from the bottom */
270 Result = CmpCompareInIndex(Hive, SearchName, 0, Leaf, SubKey);
271 if (Result == 2) goto Big;
272
273 /*
274 * Check if it's above, which means that it's within the ranges of our
275 * leaf (since we were below before).
276 */
277 if (Result >= 0)
278 {
279 /* Sanity check */
280 ASSERT((Result == 1) || (Result == 0));
281
282 /* Yep, so we're in the right leaf; return it. */
283 *SubKey = LeafCell;
284 ReturnIndex = Low;
285 goto Return;
286 }
287
288 /* It's still below us, so fail */
289 ReturnIndex = Low;
290 goto ReturnFailure;
291 }
292
293 /* Release the leaf cell */
294 HvReleaseCell(Hive, LeafCell);
295
296 /* Well the low didn't work too well, so try the high. */
297 LeafCell = Index->List[High];
298 Leaf = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
299 if (!Leaf) goto Big;
300
301 /* Do the compare */
302 Result = CmpCompareInIndex(Hive,
303 SearchName,
304 Leaf->Count - 1,
305 Leaf,
306 SubKey);
307 if (Result == 2) goto Big;
308
309 /* Check if we found it */
310 if (Result == 0)
311 {
312 /* We got lucky... return it */
313 *SubKey = LeafCell;
314 ReturnIndex = High;
315 goto Return;
316 }
317
318 /* Check if we are too high */
319 if (Result < 0)
320 {
321 /* Make sure we're -1 */
322 ASSERT(Result == -1);
323
324 /*
325 * Once again... since we were first too low and now too high, then
326 * this means we are within the range of this leaf... return it.
327 */
328 *SubKey = LeafCell;
329 ReturnIndex = High;
330 goto Return;
331 }
332
333 /* If we got here, then we are too low, again. */
334 ReturnIndex = High;
335
336 /* Failure path */
337 ReturnFailure:
338 *SubKey = HCELL_NIL;
339
340 /* Return path...check if we have a leaf to free */
341 Return:
342 if (Leaf) HvReleaseCell(Hive, LeafCell);
343
344 /* Return the index */
345 return ReturnIndex;
346 }
347
348 ULONG
349 NTAPI
350 CmpFindSubKeyInLeaf(IN PHHIVE Hive,
351 IN PCM_KEY_INDEX Index,
352 IN PUNICODE_STRING SearchName,
353 IN PHCELL_INDEX SubKey)
354 {
355 ULONG High, Low = 0, i;
356 LONG Result;
357
358 /* Verify Index for validity */
359 ASSERT((Index->Signature == CM_KEY_INDEX_LEAF) ||
360 (Index->Signature == CM_KEY_FAST_LEAF) ||
361 (Index->Signature == CM_KEY_HASH_LEAF));
362
363 /* Get the upper bound and middle entry */
364 High = Index->Count - 1;
365 #ifdef SOMEONE_WAS_NICE_ENOUGH_TO_MAKE_OUR_CELLS_LEXICALLY_SORTED
366 i = High / 2;
367 #else
368 i = 0;
369 #endif
370
371 /* Check if we don't actually have any entries */
372 if (!Index->Count)
373 {
374 /* Return failure */
375 *SubKey = HCELL_NIL;
376 return 0;
377 }
378
379 /* Start compare loop */
380 while (TRUE)
381 {
382 /* Do the actual comparison and check the result */
383 Result = CmpCompareInIndex(Hive, SearchName, i, Index, SubKey);
384 if (Result == 2)
385 {
386 /* Fail with special value */
387 *SubKey = HCELL_NIL;
388 return 0x80000000;
389 }
390
391 /* Check if we got lucky and found it */
392 if (!Result) return i;
393
394 #ifdef SOMEONE_WAS_NICE_ENOUGH_TO_MAKE_OUR_CELLS_LEXICALLY_SORTED
395 /* Check if the result is below us */
396 if (Result < 0)
397 {
398 /* Set the new bound; it can't be higher then where we are now. */
399 ASSERT(Result == -1);
400 High = i;
401 }
402 else
403 {
404 /* Set the new bound... it can't be lower then where we are now. */
405 ASSERT(Result == 1);
406 Low = i;
407 }
408
409 /* Check if this is the last entry, if so, break out and handle it */
410 if ((High - Low) <= 1) break;
411
412 /* Set the new index */
413 i = ((High - Low) / 2) + Low;
414 #else
415 if (++i > High)
416 {
417 /* Return failure */
418 *SubKey = HCELL_NIL;
419 return 0;
420 }
421 #endif
422 }
423
424 /*
425 * If we get here, High - Low = 1 or High == Low
426 * Simply look first at Low, then at High
427 */
428 Result = CmpCompareInIndex(Hive, SearchName, Low, Index, SubKey);
429 if (Result == 2)
430 {
431 /* Fail with special value */
432 *SubKey = HCELL_NIL;
433 return 0x80000000;
434 }
435
436 /* Check if we got lucky and found it */
437 if (!Result) return Low;
438
439 /* Check if the result is below us */
440 if (Result < 0)
441 {
442 /* Return the low entry */
443 ASSERT(Result == -1);
444 return Low;
445 }
446
447 /*
448 * If we got here, then just check the high and return it no matter what
449 * the result is (since we're a leaf, it has to be near there anyway).
450 */
451 Result = CmpCompareInIndex(Hive, SearchName, High, Index, SubKey);
452 if (Result == 2)
453 {
454 /* Fail with special value */
455 *SubKey = HCELL_NIL;
456 return 0x80000000;
457 }
458
459 /* Return the high */
460 return High;
461 }
462
463 ULONG
464 NTAPI
465 CmpComputeHashKey(IN ULONG Hash,
466 IN PUNICODE_STRING Name,
467 IN BOOLEAN AllowSeparators)
468 {
469 LPWSTR Cp;
470 ULONG Value, i;
471
472 /* Make some sanity checks on our parameters */
473 ASSERT((Name->Length == 0) ||
474 (AllowSeparators) ||
475 (Name->Buffer[0] != OBJ_NAME_PATH_SEPARATOR));
476
477 /* If the name is empty, there is nothing to hash! */
478 if (!Name->Length) return Hash;
479
480 /* Set the buffer and loop every character */
481 Cp = Name->Buffer;
482 for (i = 0; i < Name->Length; i += sizeof(WCHAR), Cp++)
483 {
484 /* Make sure we don't have a separator when we shouldn't */
485 ASSERT(AllowSeparators || (*Cp != OBJ_NAME_PATH_SEPARATOR));
486
487 /* Check what kind of char we have */
488 if (*Cp >= L'a')
489 {
490 /* In the lower case region... is it truly lower case? */
491 if (*Cp < L'z')
492 {
493 /* Yes! Calculate it ourselves! */
494 Value = *Cp - L'a' + L'A';
495 }
496 else
497 {
498 /* No, use the API */
499 Value = RtlUpcaseUnicodeChar(*Cp);
500 }
501 }
502 else
503 {
504 /* Reuse the char, it's already upcased */
505 Value = *Cp;
506 }
507
508 /* Multiply by a prime and add our value */
509 Hash *= 37;
510 Hash += Value;
511 }
512
513 /* Return the hash */
514 return Hash;
515 }
516
517 HCELL_INDEX
518 NTAPI
519 CmpDoFindSubKeyByNumber(IN PHHIVE Hive,
520 IN PCM_KEY_INDEX Index,
521 IN ULONG Number)
522 {
523 ULONG i;
524 HCELL_INDEX LeafCell = 0;
525 PCM_KEY_INDEX Leaf = NULL;
526 PCM_KEY_FAST_INDEX FastIndex;
527 HCELL_INDEX Result;
528
529 /* Check if this is a root */
530 if (Index->Signature == CM_KEY_INDEX_ROOT)
531 {
532 /* Loop the index */
533 for (i = 0; i < Index->Count; i++)
534 {
535 /* Check if this isn't the first iteration */
536 if (i)
537 {
538 /* Make sure we had something valid, and release it */
539 ASSERT(Leaf != NULL );
540 ASSERT(LeafCell == Index->List[i - 1]);
541 HvReleaseCell(Hive, LeafCell);
542 }
543
544 /* Get the leaf cell and the leaf for this index */
545 LeafCell = Index->List[i];
546 Leaf = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
547 if (!Leaf) return HCELL_NIL;
548
549 /* Check if the index may be inside it */
550 if (Number < Leaf->Count)
551 {
552 /* Check if this is a fast or hash leaf */
553 if ((Leaf->Signature == CM_KEY_FAST_LEAF) ||
554 (Leaf->Signature == CM_KEY_HASH_LEAF))
555 {
556 /* Get the fast index */
557 FastIndex = (PCM_KEY_FAST_INDEX)Leaf;
558
559 /* Look inside the list to get our actual cell */
560 Result = FastIndex->List[Number].Cell;
561 HvReleaseCell(Hive, LeafCell);
562 return Result;
563 }
564 else
565 {
566 /* Regular leaf, so just use the index directly */
567 Result = Leaf->List[Number];
568
569 /* Release and return it */
570 HvReleaseCell(Hive,LeafCell);
571 return Result;
572 }
573 }
574 else
575 {
576 /* Otherwise, skip this leaf */
577 Number = Number - Leaf->Count;
578 }
579 }
580
581 /* Should never get here */
582 ASSERT(FALSE);
583 }
584
585 /* If we got here, then the cell is in this index */
586 ASSERT(Number < Index->Count);
587
588 /* Check if we're a fast or hash leaf */
589 if ((Index->Signature == CM_KEY_FAST_LEAF) ||
590 (Index->Signature == CM_KEY_HASH_LEAF))
591 {
592 /* We are, get the fast index and get the cell from the list */
593 FastIndex = (PCM_KEY_FAST_INDEX)Index;
594 return FastIndex->List[Number].Cell;
595 }
596 else
597 {
598 /* We aren't, so use the index directly to grab the cell */
599 return Index->List[Number];
600 }
601 }
602
603 HCELL_INDEX
604 NTAPI
605 CmpFindSubKeyByNumber(IN PHHIVE Hive,
606 IN PCM_KEY_NODE Node,
607 IN ULONG Number)
608 {
609 PCM_KEY_INDEX Index;
610 HCELL_INDEX Result = HCELL_NIL;
611
612 /* Check if it's in the stable list */
613 if (Number < Node->SubKeyCounts[HvStable])
614 {
615 /* Get the actual key index */
616 Index = (PCM_KEY_INDEX)HvGetCell(Hive, Node->SubKeyLists[HvStable]);
617 if (!Index) return HCELL_NIL;
618
619 /* Do a search inside it */
620 Result = CmpDoFindSubKeyByNumber(Hive, Index, Number);
621
622 /* Release the cell and return the result */
623 HvReleaseCell(Hive, Node->SubKeyLists[HvStable]);
624 return Result;
625 }
626 else if (Hive->StorageTypeCount > HvVolatile)
627 {
628 /* It's in the volatile list */
629 Number = Number - Node->SubKeyCounts[HvStable];
630 if (Number < Node->SubKeyCounts[HvVolatile])
631 {
632 /* Get the actual key index */
633 Index = (PCM_KEY_INDEX)HvGetCell(Hive,
634 Node->SubKeyLists[HvVolatile]);
635 if (!Index) return HCELL_NIL;
636
637 /* Do a search inside it */
638 Result = CmpDoFindSubKeyByNumber(Hive, Index, Number);
639
640 /* Release the cell and return the result */
641 HvReleaseCell(Hive, Node->SubKeyLists[HvVolatile]);
642 return Result;
643 }
644 }
645
646 /* Nothing was found */
647 return HCELL_NIL;
648 }
649
650 HCELL_INDEX
651 NTAPI
652 CmpFindSubKeyByHash(IN PHHIVE Hive,
653 IN PCM_KEY_FAST_INDEX FastIndex,
654 IN PUNICODE_STRING SearchName)
655 {
656 ULONG HashKey, i;
657 PCM_INDEX FastEntry;
658
659 /* Make sure it's really a hash */
660 ASSERT(FastIndex->Signature == CM_KEY_HASH_LEAF);
661
662 /* Compute the hash key for the name */
663 HashKey = CmpComputeHashKey(0, SearchName, FALSE);
664
665 /* Loop all the entries */
666 for (i = 0; i < FastIndex->Count; i++)
667 {
668 /* Get the entry */
669 FastEntry = &FastIndex->List[i];
670
671 /* Compare the hash first */
672 if (FastEntry->HashKey == HashKey)
673 {
674 /* Go ahead for a full compare */
675 if (!(CmpDoCompareKeyName(Hive, SearchName, FastEntry->Cell)))
676 {
677 /* It matched, return the cell */
678 return FastEntry->Cell;
679 }
680 }
681 }
682
683 /* If we got here then we failed */
684 return HCELL_NIL;
685 }
686
687 HCELL_INDEX
688 NTAPI
689 CmpFindSubKeyByName(IN PHHIVE Hive,
690 IN PCM_KEY_NODE Parent,
691 IN PUNICODE_STRING SearchName)
692 {
693 ULONG i;
694 PCM_KEY_INDEX IndexRoot;
695 HCELL_INDEX SubKey, CellToRelease;
696 ULONG Found;
697
698 /* Loop each storage type */
699 for (i = 0; i < Hive->StorageTypeCount; i++)
700 {
701 /* Make sure the parent node has subkeys */
702 if (Parent->SubKeyCounts[i])
703 {
704 /* Get the Index */
705 IndexRoot = (PCM_KEY_INDEX)HvGetCell(Hive, Parent->SubKeyLists[i]);
706 if (!IndexRoot) return HCELL_NIL;
707
708 /* Get the cell we'll need to release */
709 CellToRelease = Parent->SubKeyLists[i];
710
711 /* Check if this is another index root */
712 if (IndexRoot->Signature == CM_KEY_INDEX_ROOT)
713 {
714 /* Lookup the name in the root */
715 Found = CmpFindSubKeyInRoot(Hive,
716 IndexRoot,
717 SearchName,
718 &SubKey);
719
720 /* Release the previous cell */
721 ASSERT(CellToRelease != HCELL_NIL);
722 HvReleaseCell(Hive, CellToRelease);
723
724 /* Make sure we found something valid */
725 if (Found < 0) break;
726
727 /* Get the new Index Root and set the new cell to be released */
728 if (SubKey == HCELL_NIL) continue;
729 CellToRelease = SubKey;
730 IndexRoot = (PCM_KEY_INDEX)HvGetCell(Hive, SubKey);
731 }
732
733 /* Make sure the signature is what we expect it to be */
734 ASSERT((IndexRoot->Signature == CM_KEY_INDEX_LEAF) ||
735 (IndexRoot->Signature == CM_KEY_FAST_LEAF) ||
736 (IndexRoot->Signature == CM_KEY_HASH_LEAF));
737
738 /* Check if this isn't a hashed leaf */
739 if (IndexRoot->Signature != CM_KEY_HASH_LEAF)
740 {
741 /* Find the subkey in the leaf */
742 Found = CmpFindSubKeyInLeaf(Hive,
743 IndexRoot,
744 SearchName,
745 &SubKey);
746
747 /* Release the previous cell */
748 ASSERT(CellToRelease != HCELL_NIL);
749 HvReleaseCell(Hive, CellToRelease);
750
751 /* Make sure we found a valid index */
752 if (Found < 0) break;
753 }
754 else
755 {
756 /* Find the subkey in the hash */
757 SubKey = CmpFindSubKeyByHash(Hive,
758 (PCM_KEY_FAST_INDEX)IndexRoot,
759 SearchName);
760
761 /* Release the previous cell */
762 ASSERT(CellToRelease != HCELL_NIL);
763 HvReleaseCell(Hive, CellToRelease);
764 }
765
766 /* Make sure we got a valid subkey and return it */
767 if (SubKey != HCELL_NIL) return SubKey;
768 }
769 }
770
771 /* If we got here, then we failed */
772 return HCELL_NIL;
773 }
774
775 BOOLEAN
776 NTAPI
777 CmpMarkIndexDirty(IN PHHIVE Hive,
778 IN HCELL_INDEX ParentKey,
779 IN HCELL_INDEX TargetKey)
780 {
781 PCM_KEY_NODE Node;
782 UNICODE_STRING SearchName;
783 BOOLEAN IsCompressed;
784 ULONG i, Result;
785 PCM_KEY_INDEX Index;
786 HCELL_INDEX IndexCell, Child = HCELL_NIL, CellToRelease = HCELL_NIL;
787
788 /* Get the target key node */
789 Node = (PCM_KEY_NODE)HvGetCell(Hive, TargetKey);
790 if (!Node) return FALSE;
791
792 /* Check if it's compressed */
793 if (Node->Flags & KEY_COMP_NAME)
794 {
795 /* Remember this for later */
796 IsCompressed = TRUE;
797
798 /* Build the search name */
799 SearchName.Length = CmpCompressedNameSize(Node->Name,
800 Node->NameLength);
801 SearchName.MaximumLength = SearchName.Length;
802 SearchName.Buffer = ExAllocatePoolWithTag(PagedPool,
803 SearchName.Length,
804 TAG_CM);
805 if (!SearchName.Buffer)
806 {
807 /* Fail */
808 HvReleaseCell(Hive, TargetKey);
809 return FALSE;
810 }
811
812 /* Copy it */
813 CmpCopyCompressedName(SearchName.Buffer,
814 SearchName.MaximumLength,
815 Node->Name,
816 Node->NameLength);
817 }
818 else
819 {
820 /* Name isn't compressed, build it directly from the node */
821 IsCompressed = FALSE;
822 SearchName.Length = Node->NameLength;
823 SearchName.MaximumLength = Node->NameLength;
824 SearchName.Buffer = Node->Name;
825 }
826
827 /* We can release the target key now */
828 HvReleaseCell(Hive, TargetKey);
829
830 /* Now get the parent key node */
831 Node = (PCM_KEY_NODE)HvGetCell(Hive, ParentKey);
832 if (!Node) goto Quickie;
833
834 /* Loop all hive storage */
835 for (i = 0; i < Hive->StorageTypeCount; i++)
836 {
837 /* Check if any subkeys are in this index */
838 if (Node->SubKeyCounts[i])
839 {
840 /* Get the cell index */
841 //ASSERT(HvIsCellAllocated(Hive, Node->SubKeyLists[i]));
842 IndexCell = Node->SubKeyLists[i];
843
844 /* Check if we had anything to release from before */
845 if (CellToRelease != HCELL_NIL)
846 {
847 /* Release it now */
848 HvReleaseCell(Hive, CellToRelease);
849 CellToRelease = HCELL_NIL;
850 }
851
852 /* Get the key index for the cell */
853 Index = (PCM_KEY_INDEX)HvGetCell(Hive, IndexCell);
854 if (!Index) goto Quickie;
855
856 /* Release it at the next iteration or below */
857 CellToRelease = IndexCell;
858
859 /* Check if this is a root */
860 if (Index->Signature == CM_KEY_INDEX_ROOT)
861 {
862 /* Get the child inside the root */
863 Result = CmpFindSubKeyInRoot(Hive, Index, &SearchName, &Child);
864 if (Result & 0x80000000) goto Quickie;
865 if (Child == HCELL_NIL) continue;
866
867 /* We found it, mark the cell dirty */
868 HvMarkCellDirty(Hive, IndexCell);
869
870 /* Check if we had anything to release from before */
871 if (CellToRelease != HCELL_NIL)
872 {
873 /* Release it now */
874 HvReleaseCell(Hive, CellToRelease);
875 CellToRelease = HCELL_NIL;
876 }
877
878 /* Now this child is the index, get the actual key index */
879 IndexCell = Child;
880 Index = (PCM_KEY_INDEX)HvGetCell(Hive, Child);
881 if (!Index) goto Quickie;
882
883 /* Release it later */
884 CellToRelease = Child;
885 }
886
887 /* Make sure this is a valid index */
888 ASSERT((Index->Signature == CM_KEY_INDEX_LEAF) ||
889 (Index->Signature == CM_KEY_FAST_LEAF) ||
890 (Index->Signature == CM_KEY_HASH_LEAF));
891
892 /* Find the child in the leaf */
893 Result = CmpFindSubKeyInLeaf(Hive, Index, &SearchName, &Child);
894 if (Result & 0x80000000) goto Quickie;
895 if (Child != HCELL_NIL)
896 {
897 /* We found it, free the name now */
898 if (IsCompressed) ExFreePool(SearchName.Buffer);
899
900 /* Release the parent key */
901 HvReleaseCell(Hive, ParentKey);
902
903 /* Check if we had a left over cell to release */
904 if (CellToRelease != HCELL_NIL)
905 {
906 /* Release it */
907 HvReleaseCell(Hive, CellToRelease);
908 }
909
910 /* And mark the index cell dirty */
911 HvMarkCellDirty(Hive, IndexCell);
912 return TRUE;
913 }
914 }
915 }
916
917 Quickie:
918 /* Release any cells that we still hold */
919 if (Node) HvReleaseCell(Hive, ParentKey);
920 if (CellToRelease != HCELL_NIL) HvReleaseCell(Hive, CellToRelease);
921
922 /* Free the search name and return failure */
923 if (IsCompressed) ExFreePool(SearchName.Buffer);
924 return FALSE;
925 }
926
927 BOOLEAN
928 NTAPI
929 CmpRemoveSubKey(IN PHHIVE Hive,
930 IN HCELL_INDEX ParentKey,
931 IN HCELL_INDEX TargetKey)
932 {
933 PCM_KEY_NODE Node;
934 UNICODE_STRING SearchName;
935 BOOLEAN IsCompressed;
936 WCHAR Buffer[50];
937 HCELL_INDEX RootCell = HCELL_NIL, LeafCell, ChildCell;
938 PCM_KEY_INDEX Root = NULL, Leaf;
939 PCM_KEY_FAST_INDEX Child;
940 ULONG Storage, RootIndex = 0x80000000, LeafIndex;
941 BOOLEAN Result = FALSE;
942 HCELL_INDEX CellToRelease1 = HCELL_NIL, CellToRelease2 = HCELL_NIL;
943
944 /* Get the target key node */
945 Node = (PCM_KEY_NODE)HvGetCell(Hive, TargetKey);
946 if (!Node) return FALSE;
947
948 /* Make sure it's dirty, then release it */
949 ASSERT(HvIsCellDirty(Hive, TargetKey));
950 HvReleaseCell(Hive, TargetKey);
951
952 /* Check if the name is compressed */
953 if (Node->Flags & KEY_COMP_NAME)
954 {
955 /* Remember for later */
956 IsCompressed = TRUE;
957
958 /* Build the search name */
959 SearchName.Length = CmpCompressedNameSize(Node->Name,
960 Node->NameLength);
961 SearchName.MaximumLength = SearchName.Length;
962
963 /* Do we need an extra bufer? */
964 if (SearchName.MaximumLength > sizeof(Buffer))
965 {
966 /* Allocate one */
967 SearchName.Buffer = ExAllocatePoolWithTag(PagedPool,
968 SearchName.Length,
969 TAG_CM);
970 if (!SearchName.Buffer) return FALSE;
971 }
972 else
973 {
974 /* Otherwise, use our local stack buffer */
975 SearchName.Buffer = Buffer;
976 }
977
978 /* Copy the compressed name */
979 CmpCopyCompressedName(SearchName.Buffer,
980 SearchName.MaximumLength,
981 Node->Name,
982 Node->NameLength);
983 }
984 else
985 {
986 /* It's not compressed, build the name directly from the node */
987 IsCompressed = FALSE;
988 SearchName.Length = Node->NameLength;
989 SearchName.MaximumLength = Node->NameLength;
990 SearchName.Buffer = Node->Name;
991 }
992
993 /* Now get the parent node */
994 Node = (PCM_KEY_NODE)HvGetCell(Hive, ParentKey);
995 if (!Node) goto Exit;
996
997 /* Make sure it's dirty, then release it */
998 ASSERT(HvIsCellDirty(Hive, ParentKey));
999 HvReleaseCell(Hive, ParentKey);
1000
1001 /* Get the storage type and make sure it's not empty */
1002 Storage = HvGetCellType(TargetKey);
1003 ASSERT(Node->SubKeyCounts[Storage] != 0);
1004 //ASSERT(HvIsCellAllocated(Hive, Node->SubKeyLists[Storage]));
1005
1006 /* Get the leaf cell now */
1007 LeafCell = Node->SubKeyLists[Storage];
1008 Leaf = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1009 if (!Leaf) goto Exit;
1010
1011 /* Remember to release it later */
1012 CellToRelease1 = LeafCell;
1013
1014 /* Check if the leaf is a root */
1015 if (Leaf->Signature == CM_KEY_INDEX_ROOT)
1016 {
1017 /* Find the child inside the root */
1018 RootIndex = CmpFindSubKeyInRoot(Hive, Leaf, &SearchName, &ChildCell);
1019 if (RootIndex & 0x80000000) goto Exit;
1020 ASSERT(ChildCell != FALSE);
1021
1022 /* The root cell is now this leaf */
1023 Root = Leaf;
1024 RootCell = LeafCell;
1025
1026 /* And the new leaf is now this child */
1027 LeafCell = ChildCell;
1028 Leaf = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1029 if (!Leaf) goto Exit;
1030
1031 /* Remember to release it later */
1032 CellToRelease2 = LeafCell;
1033 }
1034
1035 /* Make sure the leaf is valid */
1036 ASSERT((Leaf->Signature == CM_KEY_INDEX_LEAF) ||
1037 (Leaf->Signature == CM_KEY_FAST_LEAF) ||
1038 (Leaf->Signature == CM_KEY_HASH_LEAF));
1039
1040 /* Now get the child in the leaf */
1041 LeafIndex = CmpFindSubKeyInLeaf(Hive, Leaf, &SearchName, &ChildCell);
1042 if (LeafIndex & 0x80000000) goto Exit;
1043 ASSERT(ChildCell != HCELL_NIL);
1044
1045 /* Decrement key counts and check if this was the last leaf entry */
1046 Node->SubKeyCounts[Storage]--;
1047 if (!(--Leaf->Count))
1048 {
1049 /* Free the leaf */
1050 HvFreeCell(Hive, LeafCell);
1051
1052 /* Check if we were inside a root */
1053 if (Root)
1054 {
1055 /* Decrease the root count too, since the leaf is going away */
1056 if (!(--Root->Count))
1057 {
1058 /* The root is gone too,n ow */
1059 HvFreeCell(Hive, RootCell);
1060 Node->SubKeyLists[Storage] = HCELL_NIL;
1061 }
1062 else if (RootIndex < Root->Count)
1063 {
1064 /* Bring everything up by one */
1065 RtlMoveMemory(&Root->List[RootIndex],
1066 &Root->List[RootIndex + 1],
1067 (Root->Count - RootIndex) * sizeof(HCELL_INDEX));
1068 }
1069 }
1070 else
1071 {
1072 /* Otherwise, just clear the cell */
1073 Node->SubKeyLists[Storage] = HCELL_NIL;
1074 }
1075 }
1076 else if (LeafIndex < Leaf->Count)
1077 {
1078 /* Was the leaf a normal index? */
1079 if (Leaf->Signature == CM_KEY_INDEX_LEAF)
1080 {
1081 /* Bring everything up by one */
1082 RtlMoveMemory(&Leaf->List[LeafIndex],
1083 &Leaf->List[LeafIndex + 1],
1084 (Leaf->Count - LeafIndex) * sizeof(HCELL_INDEX));
1085 }
1086 else
1087 {
1088 /* This is a fast index, bring everything up by one */
1089 Child = (PCM_KEY_FAST_INDEX)Leaf;
1090 RtlMoveMemory(&Child->List[LeafIndex],
1091 &Child->List[LeafIndex+1],
1092 (Child->Count - LeafIndex) * sizeof(CM_INDEX));
1093 }
1094 }
1095
1096 /* If we got here, now we're done */
1097 Result = TRUE;
1098
1099 Exit:
1100 /* Release any cells we may have been holding */
1101 if (CellToRelease1 != HCELL_NIL) HvReleaseCell(Hive, CellToRelease1);
1102 if (CellToRelease2 != HCELL_NIL) HvReleaseCell(Hive, CellToRelease2);
1103
1104 /* Check if the name was compressed and not inside our local buffer */
1105 if ((IsCompressed) && (SearchName.MaximumLength > sizeof(Buffer)))
1106 {
1107 /* Free the buffer we allocated */
1108 ExFreePool(SearchName.Buffer);
1109 }
1110
1111 /* Return the result */
1112 return Result;
1113 }
A free Windows-compatible Operating System