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)
9 /* INCLUDES ******************************************************************/
15 #define SOMEONE_WAS_NICE_ENOUGH_TO_MAKE_OUR_CELLS_LEXICALLY_SORTED
17 /* GLOBALS *******************************************************************/
19 ULONG CmpMaxFastIndexPerHblock
=
20 (HBLOCK_SIZE
- (sizeof(HBIN
) +
22 FIELD_OFFSET(CM_KEY_FAST_INDEX
, List
))) / sizeof(CM_INDEX
);
24 ULONG CmpMaxIndexPerHblock
=
25 (HBLOCK_SIZE
- (sizeof(HBIN
) +
27 FIELD_OFFSET(CM_KEY_INDEX
, List
))) / sizeof(HCELL_INDEX
) - 1;
29 /* FUNCTIONS *****************************************************************/
33 CmpDoCompareKeyName(IN PHHIVE Hive
,
34 IN PCUNICODE_STRING SearchName
,
38 UNICODE_STRING KeyName
;
42 Node
= (PCM_KEY_NODE
)HvGetCell(Hive
, Cell
);
45 /* Check if it's compressed */
46 if (Node
->Flags
& KEY_COMP_NAME
)
48 /* Compare compressed names */
49 Result
= CmpCompareCompressedName(SearchName
,
55 /* Compare the Unicode name directly */
56 KeyName
.Buffer
= Node
->Name
;
57 KeyName
.Length
= Node
->NameLength
;
58 KeyName
.MaximumLength
= KeyName
.Length
;
59 Result
= RtlCompareUnicodeString(SearchName
, &KeyName
, TRUE
);
62 /* Release the cell and return the normalized result */
63 HvReleaseCell(Hive
, Cell
);
64 return (Result
== 0) ? Result
: ((Result
> 0) ? 1 : -1);
69 CmpCompareInIndex(IN PHHIVE Hive
,
70 IN PCUNICODE_STRING SearchName
,
72 IN PCM_KEY_INDEX Index
,
73 IN PHCELL_INDEX SubKey
)
75 PCM_KEY_FAST_INDEX FastIndex
;
79 ULONG ActualNameLength
= 4, CompareLength
, NameLength
;
85 /* Check if we are a fast or hashed leaf */
86 if ((Index
->Signature
== CM_KEY_FAST_LEAF
) ||
87 (Index
->Signature
== CM_KEY_HASH_LEAF
))
89 /* Get the Fast/Hash Index */
90 FastIndex
= (PCM_KEY_FAST_INDEX
)Index
;
91 FastEntry
= &FastIndex
->List
[Count
];
93 /* Check if we are a hash leaf, in which case we skip all this */
94 if (Index
->Signature
== CM_KEY_FAST_LEAF
)
96 /* Find out just how much of the name is there */
97 for (i
= 0; i
< 4; i
++)
99 /* Check if this entry is empty */
100 if (!FastEntry
->NameHint
[i
])
102 /* Only this much! */
103 ActualNameLength
= i
;
108 /* How large is the name and how many characters to compare */
109 NameLength
= SearchName
->Length
/ sizeof(WCHAR
);
110 CompareLength
= min(NameLength
, ActualNameLength
);
112 /* Loop all the chars we'll test */
113 for (i
= 0; i
< CompareLength
; i
++)
115 /* Get one char from each buffer */
116 p
= SearchName
->Buffer
[i
];
117 pp
= FastEntry
->NameHint
[i
];
119 /* See if they match and return result if they don't */
120 Result
= (LONG
)RtlUpcaseUnicodeChar(p
) -
121 (LONG
)RtlUpcaseUnicodeChar(pp
);
122 if (Result
) return (Result
> 0) ? 1 : -1;
126 /* If we got here then we have to do a full compare */
127 Result
= CmpDoCompareKeyName(Hive
, SearchName
, FastEntry
->Cell
);
128 if (Result
== 2) return Result
;
129 if (!Result
) *SubKey
= FastEntry
->Cell
;
133 /* We aren't, so do a name compare and return the subkey found */
134 Result
= CmpDoCompareKeyName(Hive
, SearchName
, Index
->List
[Count
]);
135 if (Result
== 2) return Result
;
136 if (!Result
) *SubKey
= Index
->List
[Count
];
139 /* Return the comparison result */
145 CmpFindSubKeyInRoot(IN PHHIVE Hive
,
146 IN PCM_KEY_INDEX Index
,
147 IN PCUNICODE_STRING SearchName
,
148 IN PHCELL_INDEX SubKey
)
150 ULONG High
, Low
= 0, i
= 0, ReturnIndex
;
151 HCELL_INDEX LeafCell
;
155 /* Verify Index for validity */
156 ASSERT(Index
->Count
!= 0);
157 ASSERT(Index
->Signature
== CM_KEY_INDEX_ROOT
);
159 /* Set high limit and loop */
160 High
= Index
->Count
- 1;
163 /* Choose next entry */
164 #ifdef SOMEONE_WAS_NICE_ENOUGH_TO_MAKE_OUR_CELLS_LEXICALLY_SORTED
165 i
= ((High
- Low
) / 2) + Low
;
168 /* Get the leaf cell and then the leaf itself */
169 LeafCell
= Index
->List
[i
];
170 Leaf
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
173 /* Make sure the leaf is valid */
174 ASSERT((Leaf
->Signature
== CM_KEY_INDEX_LEAF
) ||
175 (Leaf
->Signature
== CM_KEY_FAST_LEAF
) ||
176 (Leaf
->Signature
== CM_KEY_HASH_LEAF
));
177 ASSERT(Leaf
->Count
!= 0);
180 Result
= CmpCompareInIndex(Hive
,
185 if (Result
== 2) goto Big
;
187 /* Check if we found the leaf */
190 /* We found the leaf */
196 #ifdef SOMEONE_WAS_NICE_ENOUGH_TO_MAKE_OUR_CELLS_LEXICALLY_SORTED
197 /* Check for negative result */
200 /* If we got here, we should be at -1 */
201 ASSERT(Result
== -1);
203 /* Do another lookup, since we might still be in the right leaf */
204 Result
= CmpCompareInIndex(Hive
,
209 if (Result
== 2) goto Big
;
211 /* Check if it's not below */
215 * If the name was first below, and now it is above,
216 * then this means that it is somewhere in this leaf.
217 * Make sure we didn't get some weird result
219 ASSERT((Result
== 1) || (Result
== 0));
227 /* Update the limit to this index, since we know it's not higher. */
232 /* Update the base to this index, since we know it's not lower. */
240 /* This was some sort of special key */
241 ReturnIndex
= 0x80000000;
245 /* Check if there is only one entry left */
246 if ((High
- Low
) <= 1) break;
248 /* Release the leaf cell */
249 HvReleaseCell(Hive
, LeafCell
);
251 #ifndef SOMEONE_WAS_NICE_ENOUGH_TO_MAKE_OUR_CELLS_LEXICALLY_SORTED
252 /* Go to the next index, and return failure if we reach the end */
262 /* Make sure we got here for the right reasons */
263 ASSERT((High
- Low
== 1) || (High
== Low
));
265 /* Get the leaf cell and the leaf */
266 LeafCell
= Index
->List
[Low
];
267 Leaf
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
271 Result
= CmpCompareInIndex(Hive
,
276 if (Result
== 2) goto Big
;
278 /* Check if we found it */
281 /* We got lucky...return it */
287 /* It's below, so could still be in this leaf */
290 /* Make sure we're -1 */
291 ASSERT(Result
== -1);
293 /* Do a search from the bottom */
294 Result
= CmpCompareInIndex(Hive
, SearchName
, 0, Leaf
, SubKey
);
295 if (Result
== 2) goto Big
;
298 * Check if it's above, which means that it's within the ranges of our
299 * leaf (since we were below before).
304 ASSERT((Result
== 1) || (Result
== 0));
306 /* Yep, so we're in the right leaf; return it. */
312 /* It's still below us, so fail */
317 /* Release the leaf cell */
318 HvReleaseCell(Hive
, LeafCell
);
320 /* Well the low didn't work too well, so try the high. */
321 LeafCell
= Index
->List
[High
];
322 Leaf
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
326 Result
= CmpCompareInIndex(Hive
,
331 if (Result
== 2) goto Big
;
333 /* Check if we found it */
336 /* We got lucky... return it */
342 /* Check if we are too high */
345 /* Make sure we're -1 */
346 ASSERT(Result
== -1);
349 * Once again... since we were first too low and now too high, then
350 * this means we are within the range of this leaf... return it.
357 /* If we got here, then we are too low, again. */
364 /* Return path...check if we have a leaf to free */
366 if (Leaf
) HvReleaseCell(Hive
, LeafCell
);
368 /* Return the index */
374 CmpFindSubKeyInLeaf(IN PHHIVE Hive
,
375 IN PCM_KEY_INDEX Index
,
376 IN PCUNICODE_STRING SearchName
,
377 IN PHCELL_INDEX SubKey
)
379 ULONG High
, Low
= 0, i
;
382 /* Verify Index for validity */
383 ASSERT((Index
->Signature
== CM_KEY_INDEX_LEAF
) ||
384 (Index
->Signature
== CM_KEY_FAST_LEAF
) ||
385 (Index
->Signature
== CM_KEY_HASH_LEAF
));
387 /* Get the upper bound and middle entry */
388 High
= Index
->Count
- 1;
389 #ifdef SOMEONE_WAS_NICE_ENOUGH_TO_MAKE_OUR_CELLS_LEXICALLY_SORTED
395 /* Check if we don't actually have any entries */
403 /* Start compare loop */
406 /* Do the actual comparison and check the result */
407 Result
= CmpCompareInIndex(Hive
, SearchName
, i
, Index
, SubKey
);
410 /* Fail with special value */
415 /* Check if we got lucky and found it */
416 if (!Result
) return i
;
418 #ifdef SOMEONE_WAS_NICE_ENOUGH_TO_MAKE_OUR_CELLS_LEXICALLY_SORTED
419 /* Check if the result is below us */
422 /* Set the new bound; it can't be higher then where we are now. */
423 ASSERT(Result
== -1);
428 /* Set the new bound... it can't be lower then where we are now. */
433 /* Check if this is the last entry, if so, break out and handle it */
434 if ((High
- Low
) <= 1) break;
436 /* Set the new index */
437 i
= ((High
- Low
) / 2) + Low
;
449 * If we get here, High - Low = 1 or High == Low
450 * Simply look first at Low, then at High
452 Result
= CmpCompareInIndex(Hive
, SearchName
, Low
, Index
, SubKey
);
455 /* Fail with special value */
460 /* Check if we got lucky and found it */
461 if (!Result
) return Low
;
463 /* Check if the result is below us */
466 /* Return the low entry */
467 ASSERT(Result
== -1);
472 * If we got here, then just check the high and return it no matter what
473 * the result is (since we're a leaf, it has to be near there anyway).
475 Result
= CmpCompareInIndex(Hive
, SearchName
, High
, Index
, SubKey
);
478 /* Fail with special value */
483 /* Return the high */
489 CmpComputeHashKey(IN ULONG Hash
,
490 IN PCUNICODE_STRING Name
,
491 IN BOOLEAN AllowSeparators
)
496 /* Make some sanity checks on our parameters */
497 ASSERT((Name
->Length
== 0) ||
499 (Name
->Buffer
[0] != OBJ_NAME_PATH_SEPARATOR
));
501 /* If the name is empty, there is nothing to hash! */
502 if (!Name
->Length
) return Hash
;
504 /* Set the buffer and loop every character */
506 for (i
= 0; i
< Name
->Length
; i
+= sizeof(WCHAR
), Cp
++)
508 /* Make sure we don't have a separator when we shouldn't */
509 ASSERT(AllowSeparators
|| (*Cp
!= OBJ_NAME_PATH_SEPARATOR
));
511 /* Check what kind of char we have */
514 /* In the lower case region... is it truly lower case? */
517 /* Yes! Calculate it ourselves! */
518 Value
= *Cp
- L
'a' + L
'A';
522 /* No, use the API */
523 Value
= RtlUpcaseUnicodeChar(*Cp
);
528 /* Reuse the char, it's already upcased */
532 /* Multiply by a prime and add our value */
537 /* Return the hash */
543 CmpDoFindSubKeyByNumber(IN PHHIVE Hive
,
544 IN PCM_KEY_INDEX Index
,
548 HCELL_INDEX LeafCell
= 0;
549 PCM_KEY_INDEX Leaf
= NULL
;
550 PCM_KEY_FAST_INDEX FastIndex
;
553 /* Check if this is a root */
554 if (Index
->Signature
== CM_KEY_INDEX_ROOT
)
557 for (i
= 0; i
< Index
->Count
; i
++)
559 /* Check if this isn't the first iteration */
562 /* Make sure we had something valid, and release it */
563 ASSERT(Leaf
!= NULL
);
564 ASSERT(LeafCell
== Index
->List
[i
- 1]);
565 HvReleaseCell(Hive
, LeafCell
);
568 /* Get the leaf cell and the leaf for this index */
569 LeafCell
= Index
->List
[i
];
570 Leaf
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
571 if (!Leaf
) return HCELL_NIL
;
573 /* Check if the index may be inside it */
574 if (Number
< Leaf
->Count
)
576 /* Check if this is a fast or hash leaf */
577 if ((Leaf
->Signature
== CM_KEY_FAST_LEAF
) ||
578 (Leaf
->Signature
== CM_KEY_HASH_LEAF
))
580 /* Get the fast index */
581 FastIndex
= (PCM_KEY_FAST_INDEX
)Leaf
;
583 /* Look inside the list to get our actual cell */
584 Result
= FastIndex
->List
[Number
].Cell
;
585 HvReleaseCell(Hive
, LeafCell
);
590 /* Regular leaf, so just use the index directly */
591 Result
= Leaf
->List
[Number
];
593 /* Release and return it */
594 HvReleaseCell(Hive
,LeafCell
);
600 /* Otherwise, skip this leaf */
601 Number
= Number
- Leaf
->Count
;
605 /* Should never get here */
609 /* If we got here, then the cell is in this index */
610 ASSERT(Number
< Index
->Count
);
612 /* Check if we're a fast or hash leaf */
613 if ((Index
->Signature
== CM_KEY_FAST_LEAF
) ||
614 (Index
->Signature
== CM_KEY_HASH_LEAF
))
616 /* We are, get the fast index and get the cell from the list */
617 FastIndex
= (PCM_KEY_FAST_INDEX
)Index
;
618 return FastIndex
->List
[Number
].Cell
;
622 /* We aren't, so use the index directly to grab the cell */
623 return Index
->List
[Number
];
629 CmpFindSubKeyByNumber(IN PHHIVE Hive
,
630 IN PCM_KEY_NODE Node
,
634 HCELL_INDEX Result
= HCELL_NIL
;
636 /* Check if it's in the stable list */
637 if (Number
< Node
->SubKeyCounts
[Stable
])
639 /* Get the actual key index */
640 Index
= (PCM_KEY_INDEX
)HvGetCell(Hive
, Node
->SubKeyLists
[Stable
]);
641 if (!Index
) return HCELL_NIL
;
643 /* Do a search inside it */
644 Result
= CmpDoFindSubKeyByNumber(Hive
, Index
, Number
);
646 /* Release the cell and return the result */
647 HvReleaseCell(Hive
, Node
->SubKeyLists
[Stable
]);
650 else if (Hive
->StorageTypeCount
> Volatile
)
652 /* It's in the volatile list */
653 Number
= Number
- Node
->SubKeyCounts
[Stable
];
654 if (Number
< Node
->SubKeyCounts
[Volatile
])
656 /* Get the actual key index */
657 Index
= (PCM_KEY_INDEX
)HvGetCell(Hive
,
658 Node
->SubKeyLists
[Volatile
]);
659 if (!Index
) return HCELL_NIL
;
661 /* Do a search inside it */
662 Result
= CmpDoFindSubKeyByNumber(Hive
, Index
, Number
);
664 /* Release the cell and return the result */
665 HvReleaseCell(Hive
, Node
->SubKeyLists
[Volatile
]);
670 /* Nothing was found */
676 CmpFindSubKeyByHash(IN PHHIVE Hive
,
677 IN PCM_KEY_FAST_INDEX FastIndex
,
678 IN PCUNICODE_STRING SearchName
)
683 /* Make sure it's really a hash */
684 ASSERT(FastIndex
->Signature
== CM_KEY_HASH_LEAF
);
686 /* Compute the hash key for the name */
687 HashKey
= CmpComputeHashKey(0, SearchName
, FALSE
);
689 /* Loop all the entries */
690 for (i
= 0; i
< FastIndex
->Count
; i
++)
693 FastEntry
= &FastIndex
->List
[i
];
695 /* Compare the hash first */
696 if (FastEntry
->HashKey
== HashKey
)
698 /* Go ahead for a full compare */
699 if (!(CmpDoCompareKeyName(Hive
, SearchName
, FastEntry
->Cell
)))
701 /* It matched, return the cell */
702 return FastEntry
->Cell
;
707 /* If we got here then we failed */
713 CmpFindSubKeyByName(IN PHHIVE Hive
,
714 IN PCM_KEY_NODE Parent
,
715 IN PCUNICODE_STRING SearchName
)
718 PCM_KEY_INDEX IndexRoot
;
719 HCELL_INDEX SubKey
, CellToRelease
;
722 /* Loop each storage type */
723 for (i
= 0; i
< Hive
->StorageTypeCount
; i
++)
725 /* Make sure the parent node has subkeys */
726 if (Parent
->SubKeyCounts
[i
])
729 IndexRoot
= (PCM_KEY_INDEX
)HvGetCell(Hive
, Parent
->SubKeyLists
[i
]);
730 if (!IndexRoot
) return HCELL_NIL
;
732 /* Get the cell we'll need to release */
733 CellToRelease
= Parent
->SubKeyLists
[i
];
735 /* Check if this is another index root */
736 if (IndexRoot
->Signature
== CM_KEY_INDEX_ROOT
)
739 #ifndef SOMEONE_WAS_NICE_ENOUGH_TO_MAKE_OUR_CELLS_LEXICALLY_SORTED
740 /* CmpFindSubKeyInRoot is useless for actually finding the correct leaf when keys are not sorted */
743 /* Loop through each leaf in the index root */
744 for (ii
=0; ii
<IndexRoot
->Count
; ii
++)
746 Leaf
= HvGetCell(Hive
, IndexRoot
->List
[ii
]);
749 Found
= CmpFindSubKeyInLeaf(Hive
, Leaf
, SearchName
, &SubKey
);
750 HvReleaseCell(Hive
, IndexRoot
->List
[ii
]);
751 if (Found
& 0x80000000)
753 HvReleaseCell(Hive
, CellToRelease
);
757 if (SubKey
!= HCELL_NIL
)
759 HvReleaseCell(Hive
, CellToRelease
);
765 /* Lookup the name in the root */
766 Found
= CmpFindSubKeyInRoot(Hive
,
771 /* Release the previous cell */
772 ASSERT(CellToRelease
!= HCELL_NIL
);
773 HvReleaseCell(Hive
, CellToRelease
);
775 /* Make sure we found something valid */
776 if (Found
& 0x80000000) break;
778 /* Get the new Index Root and set the new cell to be released */
779 if (SubKey
== HCELL_NIL
) continue;
780 CellToRelease
= SubKey
;
781 IndexRoot
= (PCM_KEY_INDEX
)HvGetCell(Hive
, SubKey
);
784 /* Make sure the signature is what we expect it to be */
785 ASSERT((IndexRoot
->Signature
== CM_KEY_INDEX_LEAF
) ||
786 (IndexRoot
->Signature
== CM_KEY_FAST_LEAF
) ||
787 (IndexRoot
->Signature
== CM_KEY_HASH_LEAF
));
789 /* Check if this isn't a hashed leaf */
790 if (IndexRoot
->Signature
!= CM_KEY_HASH_LEAF
)
792 /* Find the subkey in the leaf */
793 Found
= CmpFindSubKeyInLeaf(Hive
,
798 /* Release the previous cell */
799 ASSERT(CellToRelease
!= HCELL_NIL
);
800 HvReleaseCell(Hive
, CellToRelease
);
802 /* Make sure we found a valid index */
803 if (Found
& 0x80000000) break;
807 /* Find the subkey in the hash */
808 SubKey
= CmpFindSubKeyByHash(Hive
,
809 (PCM_KEY_FAST_INDEX
)IndexRoot
,
812 /* Release the previous cell */
813 ASSERT(CellToRelease
!= HCELL_NIL
);
814 HvReleaseCell(Hive
, CellToRelease
);
817 /* Make sure we got a valid subkey and return it */
818 if (SubKey
!= HCELL_NIL
) return SubKey
;
822 /* If we got here, then we failed */
828 CmpMarkIndexDirty(IN PHHIVE Hive
,
829 IN HCELL_INDEX ParentKey
,
830 IN HCELL_INDEX TargetKey
)
833 UNICODE_STRING SearchName
;
834 BOOLEAN IsCompressed
;
837 HCELL_INDEX IndexCell
, Child
= HCELL_NIL
, CellToRelease
= HCELL_NIL
;
839 /* Get the target key node */
840 Node
= (PCM_KEY_NODE
)HvGetCell(Hive
, TargetKey
);
841 if (!Node
) return FALSE
;
843 /* Check if it's compressed */
844 if (Node
->Flags
& KEY_COMP_NAME
)
846 /* Remember this for later */
849 /* Build the search name */
850 SearchName
.Length
= CmpCompressedNameSize(Node
->Name
,
852 SearchName
.MaximumLength
= SearchName
.Length
;
853 SearchName
.Buffer
= CmpAllocate(SearchName
.Length
,
856 if (!SearchName
.Buffer
)
859 HvReleaseCell(Hive
, TargetKey
);
864 CmpCopyCompressedName(SearchName
.Buffer
,
865 SearchName
.MaximumLength
,
871 /* Name isn't compressed, build it directly from the node */
872 IsCompressed
= FALSE
;
873 SearchName
.Length
= Node
->NameLength
;
874 SearchName
.MaximumLength
= Node
->NameLength
;
875 SearchName
.Buffer
= Node
->Name
;
878 /* We can release the target key now */
879 HvReleaseCell(Hive
, TargetKey
);
881 /* Now get the parent key node */
882 Node
= (PCM_KEY_NODE
)HvGetCell(Hive
, ParentKey
);
883 if (!Node
) goto Quickie
;
885 /* Loop all hive storage */
886 for (i
= 0; i
< Hive
->StorageTypeCount
; i
++)
888 /* Check if any subkeys are in this index */
889 if (Node
->SubKeyCounts
[i
])
891 /* Get the cell index */
892 //ASSERT(HvIsCellAllocated(Hive, Node->SubKeyLists[i]));
893 IndexCell
= Node
->SubKeyLists
[i
];
895 /* Check if we had anything to release from before */
896 if (CellToRelease
!= HCELL_NIL
)
899 HvReleaseCell(Hive
, CellToRelease
);
900 CellToRelease
= HCELL_NIL
;
903 /* Get the key index for the cell */
904 Index
= (PCM_KEY_INDEX
)HvGetCell(Hive
, IndexCell
);
905 if (!Index
) goto Quickie
;
907 /* Release it at the next iteration or below */
908 CellToRelease
= IndexCell
;
910 /* Check if this is a root */
911 if (Index
->Signature
== CM_KEY_INDEX_ROOT
)
913 /* Get the child inside the root */
914 Result
= CmpFindSubKeyInRoot(Hive
, Index
, &SearchName
, &Child
);
915 if (Result
& 0x80000000) goto Quickie
;
916 if (Child
== HCELL_NIL
) continue;
918 /* We found it, mark the cell dirty */
919 HvMarkCellDirty(Hive
, IndexCell
, FALSE
);
921 /* Check if we had anything to release from before */
922 if (CellToRelease
!= HCELL_NIL
)
925 HvReleaseCell(Hive
, CellToRelease
);
926 CellToRelease
= HCELL_NIL
;
929 /* Now this child is the index, get the actual key index */
931 Index
= (PCM_KEY_INDEX
)HvGetCell(Hive
, Child
);
932 if (!Index
) goto Quickie
;
934 /* Release it later */
935 CellToRelease
= Child
;
938 /* Make sure this is a valid index */
939 ASSERT((Index
->Signature
== CM_KEY_INDEX_LEAF
) ||
940 (Index
->Signature
== CM_KEY_FAST_LEAF
) ||
941 (Index
->Signature
== CM_KEY_HASH_LEAF
));
943 /* Find the child in the leaf */
944 Result
= CmpFindSubKeyInLeaf(Hive
, Index
, &SearchName
, &Child
);
945 if (Result
& 0x80000000) goto Quickie
;
946 if (Child
!= HCELL_NIL
)
948 /* We found it, free the name now */
949 if (IsCompressed
) CmpFree(SearchName
.Buffer
, 0);
951 /* Release the parent key */
952 HvReleaseCell(Hive
, ParentKey
);
954 /* Check if we had a left over cell to release */
955 if (CellToRelease
!= HCELL_NIL
)
958 HvReleaseCell(Hive
, CellToRelease
);
961 /* And mark the index cell dirty */
962 HvMarkCellDirty(Hive
, IndexCell
, FALSE
);
969 /* Release any cells that we still hold */
970 if (Node
) HvReleaseCell(Hive
, ParentKey
);
971 if (CellToRelease
!= HCELL_NIL
) HvReleaseCell(Hive
, CellToRelease
);
973 /* Free the search name and return failure */
974 if (IsCompressed
) CmpFree(SearchName
.Buffer
, 0);
980 CmpAddToLeaf(IN PHHIVE Hive
,
981 IN HCELL_INDEX LeafCell
,
982 IN HCELL_INDEX NewKey
,
983 IN PUNICODE_STRING Name
)
986 PCM_KEY_FAST_INDEX FastLeaf
;
987 ULONG Size
, OldSize
, EntrySize
, i
, j
;
988 HCELL_INDEX NewCell
, Child
;
991 /* Mark the leaf dirty */
992 HvMarkCellDirty(Hive
, LeafCell
, FALSE
);
994 /* Get the leaf cell */
995 Leaf
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
998 /* Shouldn't happen */
1004 HvReleaseCell(Hive
, LeafCell
);
1006 /* Check if this is an index leaf */
1007 if (Leaf
->Signature
== CM_KEY_INDEX_LEAF
)
1009 /* This is an old-style leaf */
1011 EntrySize
= sizeof(HCELL_INDEX
);
1016 ASSERT((Leaf
->Signature
== CM_KEY_FAST_LEAF
) ||
1017 (Leaf
->Signature
== CM_KEY_HASH_LEAF
));
1019 /* This is a new-style optimized fast (or hash) leaf */
1020 FastLeaf
= (PCM_KEY_FAST_INDEX
)Leaf
;
1021 EntrySize
= sizeof(CM_INDEX
);
1024 /* Get the current size of the leaf */
1025 OldSize
= HvGetCellSize(Hive
, Leaf
);
1027 /* Calculate the size of the free entries */
1029 Size
-= EntrySize
* Leaf
->Count
+ FIELD_OFFSET(CM_KEY_INDEX
, List
);
1031 /* Assume we'll re-use the same leaf */
1034 /* Check if we're out of space */
1035 if ((Size
/ EntrySize
) < 1)
1037 /* Grow the leaf by 1.5x, making sure we can at least fit this entry */
1038 Size
= OldSize
+ OldSize
/ 2;
1039 if (Size
< (OldSize
+ EntrySize
)) Size
= OldSize
+ EntrySize
;
1041 /* Re-allocate the leaf */
1042 NewCell
= HvReallocateCell(Hive
, LeafCell
, Size
);
1043 if (NewCell
== HCELL_NIL
) return HCELL_NIL
;
1045 /* Get the leaf cell */
1046 Leaf
= (PCM_KEY_INDEX
)HvGetCell(Hive
, NewCell
);
1049 /* This shouldn't happen */
1054 /* Release the cell */
1055 HvReleaseCell(Hive
, NewCell
);
1057 /* Update the fast leaf pointer if we had one */
1058 if (FastLeaf
) FastLeaf
= (PCM_KEY_FAST_INDEX
)Leaf
;
1061 /* Find the insertion point for our entry */
1062 i
= CmpFindSubKeyInLeaf(Hive
, Leaf
, Name
, &Child
);
1063 if (i
& 0x80000000) return HCELL_NIL
;
1064 ASSERT(Child
== HCELL_NIL
);
1066 /* Check if we're not last */
1067 if (i
!= Leaf
->Count
)
1069 /* Find out where we should go */
1070 Result
= CmpCompareInIndex(Hive
,
1075 if (Result
== 2) return HCELL_NIL
;
1076 ASSERT(Result
!= 0);
1078 /* Check if we come after */
1081 /* We do, insert us after the key */
1082 ASSERT(Result
== 1);
1086 /* Check if we're still not last */
1087 if (i
!= Leaf
->Count
)
1089 /* Check if we had a fast leaf or not */
1092 /* Copy the fast indexes */
1093 RtlMoveMemory(&FastLeaf
->List
[i
+ 1],
1095 (FastLeaf
->Count
- i
) * sizeof(CM_INDEX
));
1099 /* Copy the indexes themselves */
1100 RtlMoveMemory(&Leaf
->List
[i
+ 1],
1102 (Leaf
->Count
- i
) * sizeof(HCELL_INDEX
));
1107 /* Check if this is a new-style leaf */
1111 FastLeaf
->List
[i
].Cell
= NewKey
;
1113 /* Check if this is a hash leaf */
1114 if( FastLeaf
->Signature
== CM_KEY_HASH_LEAF
)
1116 /* Set our hash key */
1117 FastLeaf
->List
[i
].HashKey
= CmpComputeHashKey(0, Name
, FALSE
);
1121 /* First, clear the name */
1122 FastLeaf
->List
[i
].NameHint
[0] = 0;
1123 FastLeaf
->List
[i
].NameHint
[1] = 0;
1124 FastLeaf
->List
[i
].NameHint
[2] = 0;
1125 FastLeaf
->List
[i
].NameHint
[3] = 0;
1127 /* Now, figure out if we can fit */
1128 if (Name
->Length
/ sizeof(WCHAR
) < 4)
1130 /* We can fit, use our length */
1131 j
= Name
->Length
/ sizeof(WCHAR
);
1135 /* We can't, use a maximum of 4 */
1139 /* Now fill out the name hint */
1142 /* Look for invalid characters and break out if we found one */
1143 if ((USHORT
)Name
->Buffer
[j
- 1] > (UCHAR
)-1) break;
1145 /* Otherwise, copy the a character */
1146 FastLeaf
->List
[i
].NameHint
[j
- 1] = (UCHAR
)Name
->Buffer
[j
- 1];
1152 /* This is an old-style leaf, just set our index directly */
1153 Leaf
->List
[i
] = NewKey
;
1156 /* Update the leaf count and return the new cell */
1163 CmpSplitLeaf(IN PHHIVE Hive
,
1164 IN HCELL_INDEX RootCell
,
1165 IN ULONG RootSelect
,
1166 IN HSTORAGE_TYPE Type
)
1168 PCM_KEY_INDEX IndexKey
, LeafKey
, NewKey
;
1169 PCM_KEY_FAST_INDEX FastLeaf
;
1170 HCELL_INDEX LeafCell
, NewCell
;
1171 USHORT FirstHalf
, LastHalf
;
1172 ULONG EntrySize
, TotalSize
;
1175 IndexKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, RootCell
);
1177 /* Check if we've got valid IndexKey */
1178 if (!IndexKey
) return HCELL_NIL
;
1180 /* Get the leaf cell and key */
1181 LeafCell
= IndexKey
->List
[RootSelect
];
1182 LeafKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
1184 /* Check if we've got valid LeafKey */
1185 if (!LeafKey
) return HCELL_NIL
;
1187 /* We are going to divide this leaf into two halves */
1188 FirstHalf
= (LeafKey
->Count
/ 2);
1189 LastHalf
= LeafKey
->Count
- FirstHalf
;
1191 /* Now check what kind of hive we're dealing with,
1192 * and compute entry size
1194 if (Hive
->Version
>= 5)
1196 /* XP Hive: Use hash leaf */
1197 ASSERT(LeafKey
->Signature
== CM_KEY_HASH_LEAF
);
1198 EntrySize
= sizeof(CM_INDEX
);
1202 /* Use index leaf */
1203 ASSERT(LeafKey
->Signature
== CM_KEY_INDEX_LEAF
);
1204 EntrySize
= sizeof(HCELL_INDEX
);
1207 /* Compute the total size */
1208 TotalSize
= (EntrySize
* LastHalf
) + FIELD_OFFSET(CM_KEY_INDEX
, List
) + 1;
1210 /* Mark the leaf cell dirty */
1211 HvMarkCellDirty(Hive
, LeafCell
, FALSE
);
1213 /* Make sure its type is the same */
1214 ASSERT(HvGetCellType(LeafCell
) == Type
);
1216 /* Allocate the cell, fail in case of error */
1217 NewCell
= HvAllocateCell(Hive
, TotalSize
, Type
, LeafCell
);
1218 if (NewCell
== HCELL_NIL
) return NewCell
;
1221 NewKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, NewCell
);
1224 /* Free the cell and exit - should not happen! */
1226 HvFreeCell(Hive
, NewCell
);
1230 /* Release the newly created cell */
1231 HvReleaseCell(Hive
, NewCell
);
1233 /* Set its signature according to the version of the hive */
1234 if (Hive
->Version
>= 5)
1236 /* XP Hive: Use hash leaf signature */
1237 NewKey
->Signature
= CM_KEY_HASH_LEAF
;
1241 /* Use index leaf signature */
1242 NewKey
->Signature
= CM_KEY_INDEX_LEAF
;
1245 /* Calculate the size of the free entries in the root key */
1246 TotalSize
= HvGetCellSize(Hive
, IndexKey
) -
1247 (IndexKey
->Count
* sizeof(HCELL_INDEX
)) -
1248 FIELD_OFFSET(CM_KEY_INDEX
, List
);
1250 /* Check if we're out of space */
1251 if (TotalSize
/ sizeof(HCELL_INDEX
) < 1)
1253 /* Grow the leaf by one more entry */
1254 TotalSize
= HvGetCellSize(Hive
, IndexKey
) + sizeof(HCELL_INDEX
);
1256 /* Re-allocate the root */
1257 RootCell
= HvReallocateCell(Hive
, RootCell
, TotalSize
);
1258 if (RootCell
== HCELL_NIL
)
1260 /* Free the cell and exit */
1261 HvFreeCell(Hive
, NewCell
);
1265 /* Get the leaf cell */
1266 IndexKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, RootCell
);
1269 /* This shouldn't happen */
1275 /* Splitting is done, now we need to copy the contents,
1276 * according to the hive version
1278 if (Hive
->Version
>= 5)
1280 /* Copy the fast indexes */
1281 FastLeaf
= (PCM_KEY_FAST_INDEX
)LeafKey
;
1282 RtlMoveMemory(&NewKey
->List
[0],
1283 &FastLeaf
->List
[FirstHalf
],
1284 LastHalf
* EntrySize
);
1288 /* Copy the indexes themselves */
1289 RtlMoveMemory(&NewKey
->List
[0],
1290 &LeafKey
->List
[FirstHalf
],
1291 LastHalf
* EntrySize
);
1294 /* Shift the data inside the root key */
1295 if ((RootSelect
+ 1) < IndexKey
->Count
)
1297 RtlMoveMemory(&IndexKey
->List
[RootSelect
+ 2],
1298 &IndexKey
->List
[RootSelect
+ 1],
1300 (RootSelect
+ 1)) * sizeof(HCELL_INDEX
));
1303 /* Make sure both old and new computed counts are valid */
1304 ASSERT(FirstHalf
!= 0);
1305 ASSERT(LastHalf
!= 0);
1307 /* Update the count value of old and new keys */
1308 LeafKey
->Count
= FirstHalf
;
1309 NewKey
->Count
= LastHalf
;
1311 /* Increase the count value of the root key */
1314 /* Set the new cell in root's list */
1315 IndexKey
->List
[RootSelect
+ 1] = NewCell
;
1317 /* Return the root cell */
1323 CmpSelectLeaf(IN PHHIVE Hive
,
1324 IN PCM_KEY_NODE KeyNode
,
1325 IN PUNICODE_STRING Name
,
1326 IN HSTORAGE_TYPE Type
,
1327 IN PHCELL_INDEX
*RootCell
)
1329 PCM_KEY_INDEX IndexKey
, LeafKey
;
1330 PCM_KEY_FAST_INDEX FastLeaf
;
1331 HCELL_INDEX LeafCell
, CurrentCell
;
1335 /* Mark it as dirty */
1336 HvMarkCellDirty(Hive
, KeyNode
->SubKeyLists
[Type
], FALSE
);
1339 IndexKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, KeyNode
->SubKeyLists
[Type
]);
1341 /* Check if we've got a valid key */
1344 /* Should not happen! */
1345 ASSERTMSG("IndexKey = NULL!, it should not happen!\n", FALSE
);
1350 ASSERT(IndexKey
->Signature
== CM_KEY_INDEX_ROOT
);
1355 SubKeyIndex
= CmpFindSubKeyInRoot(Hive
, IndexKey
, Name
, &LeafCell
);
1357 /* Make sure we found something valid */
1358 if (SubKeyIndex
& 0x80000000) return HCELL_NIL
;
1360 /* Try to fit it into the LeafCell, if it was found */
1361 if (LeafCell
!= HCELL_NIL
)
1363 /* Get the leaf key */
1364 LeafKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
1366 /* Check for failure */
1367 if (!LeafKey
) return HCELL_NIL
;
1369 /* Check if it fits into this leaf and break */
1370 if (LeafKey
->Count
< CmpMaxIndexPerHblock
)
1372 /* Fill in the result and return it */
1373 *RootCell
= &IndexKey
->List
[SubKeyIndex
];
1377 /* It didn't fit, so proceed to splitting */
1381 /* Get the leaf cell at the very end */
1382 LeafCell
= IndexKey
->List
[SubKeyIndex
];
1383 LeafKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
1385 /* Return an error in case of problems */
1386 if (!LeafKey
) return HCELL_NIL
;
1388 /* Choose the cell to search from depending on the key type */
1389 if ((LeafKey
->Signature
== CM_KEY_FAST_LEAF
) ||
1390 (LeafKey
->Signature
== CM_KEY_HASH_LEAF
))
1392 FastLeaf
= (PCM_KEY_FAST_INDEX
)LeafKey
;
1393 CurrentCell
= FastLeaf
->List
[0].Cell
;
1397 /* Make sure it's an index leaf */
1398 ASSERT(LeafKey
->Signature
== CM_KEY_INDEX_LEAF
);
1399 CurrentCell
= LeafKey
->List
[0];
1402 /* Do a name compare */
1403 Result
= CmpDoCompareKeyName(Hive
, Name
, CurrentCell
);
1405 /* Check for failure */
1406 if (Result
== 2) return HCELL_NIL
;
1408 /* Names can't be equal, ensure that */
1409 ASSERT(Result
!= 0);
1411 /* Check if it's above */
1414 /* Get the cell in the index */
1415 LeafCell
= IndexKey
->List
[SubKeyIndex
];
1416 LeafKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
1418 /* Return an error in case of problems */
1419 if (!LeafKey
) return HCELL_NIL
;
1421 /* Check if it fits into this leaf */
1422 if (LeafKey
->Count
< CmpMaxIndexPerHblock
)
1424 /* Fill in the result and return the cell */
1425 *RootCell
= &IndexKey
->List
[SubKeyIndex
];
1429 /* No, it doesn't fit, check the next adjacent leaf */
1430 if ((SubKeyIndex
+ 1) < IndexKey
->Count
)
1432 /* Yes, there is space */
1433 LeafCell
= IndexKey
->List
[SubKeyIndex
+ 1];
1434 LeafKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
1436 /* Return an error in case of problems */
1437 if (!LeafKey
) return HCELL_NIL
;
1439 /* Check if it fits and break */
1440 if (LeafKey
->Count
< CmpMaxIndexPerHblock
)
1442 /* Fill in the result and return the cell */
1443 *RootCell
= &IndexKey
->List
[SubKeyIndex
+ 1];
1448 /* It didn't fit, so proceed to splitting */
1452 /* No, it's below, check the subkey index */
1453 if (SubKeyIndex
> 0)
1455 /* There should be space at the leaf one before that */
1456 LeafCell
= IndexKey
->List
[SubKeyIndex
- 1];
1457 LeafKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
1459 /* Return an error in case of problems */
1460 if (!LeafKey
) return HCELL_NIL
;
1462 /* Check if it fits and break */
1463 if (LeafKey
->Count
< CmpMaxIndexPerHblock
)
1465 /* Fill in the result and return the cell */
1466 *RootCell
= &IndexKey
->List
[SubKeyIndex
- 1];
1472 /* Use the first leaf, if possible */
1473 LeafCell
= IndexKey
->List
[0];
1474 LeafKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
1476 /* Return an error in case of problems */
1477 if (!LeafKey
) return HCELL_NIL
;
1479 /* Check if it fits and break */
1480 if (LeafKey
->Count
< CmpMaxIndexPerHblock
)
1482 /* Fill in the result and return the cell */
1483 *RootCell
= &IndexKey
->List
[0];
1488 /* It didn't fit into either, so proceed to splitting */
1492 /* We need to split */
1493 CurrentCell
= CmpSplitLeaf(Hive
,
1494 KeyNode
->SubKeyLists
[Type
],
1498 /* Return failure in case splitting failed */
1499 if (CurrentCell
== HCELL_NIL
) return CurrentCell
;
1501 /* Set the SubKeyLists value with the new key */
1502 KeyNode
->SubKeyLists
[Type
] = CurrentCell
;
1504 /* Get the new cell */
1505 IndexKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, KeyNode
->SubKeyLists
[Type
]);
1507 /* Return in case of failure */
1508 if (!IndexKey
) return HCELL_NIL
;
1510 /* Make sure the new key became index root */
1511 ASSERT(IndexKey
->Signature
== CM_KEY_INDEX_ROOT
);
1513 /* Now loop over with the new IndexKey value, which definately
1518 /* Shouldn't come here */
1524 CmpAddSubKey(IN PHHIVE Hive
,
1525 IN HCELL_INDEX Parent
,
1526 IN HCELL_INDEX Child
)
1528 PCM_KEY_NODE KeyNode
;
1529 PCM_KEY_INDEX Index
;
1530 PCM_KEY_FAST_INDEX OldIndex
;
1531 UNICODE_STRING Name
;
1532 HCELL_INDEX IndexCell
= HCELL_NIL
, CellToRelease
= HCELL_NIL
, LeafCell
;
1533 PHCELL_INDEX RootPointer
= NULL
;
1535 BOOLEAN IsCompressed
;
1538 /* Get the key node */
1539 KeyNode
= (PCM_KEY_NODE
)HvGetCell(Hive
, Child
);
1542 /* Shouldn't happen */
1547 /* Check if the name is compressed */
1548 if (KeyNode
->Flags
& KEY_COMP_NAME
)
1550 /* Remember for later */
1551 IsCompressed
= TRUE
;
1553 /* Create the compressed name and allocate it */
1554 Name
.Length
= CmpCompressedNameSize(KeyNode
->Name
, KeyNode
->NameLength
);
1555 Name
.MaximumLength
= Name
.Length
;
1556 Name
.Buffer
= Hive
->Allocate(Name
.Length
, TRUE
, TAG_CM
);
1559 /* Release the cell and fail */
1560 HvReleaseCell(Hive
, Child
);
1565 /* Copy the compressed name */
1566 CmpCopyCompressedName(Name
.Buffer
,
1569 KeyNode
->NameLength
);
1573 /* Remember for later */
1574 IsCompressed
= FALSE
;
1576 /* Build the unicode string */
1577 Name
.Length
= KeyNode
->NameLength
;
1578 Name
.MaximumLength
= KeyNode
->NameLength
;
1579 Name
.Buffer
= &KeyNode
->Name
[0];
1582 /* Release the cell */
1583 HvReleaseCell(Hive
, Child
);
1585 /* Get the parent node */
1586 KeyNode
= (PCM_KEY_NODE
)HvGetCell(Hive
, Parent
);
1593 /* Find out the type of the cell, and check if this is the first subkey */
1594 Type
= HvGetCellType(Child
);
1595 if (!KeyNode
->SubKeyCounts
[Type
])
1597 /* Allocate a fast leaf */
1598 IndexCell
= HvAllocateCell(Hive
, sizeof(CM_KEY_FAST_INDEX
), Type
, HCELL_NIL
);
1599 if (IndexCell
== HCELL_NIL
)
1605 /* Get the leaf cell */
1606 Index
= (PCM_KEY_INDEX
)HvGetCell(Hive
, IndexCell
);
1609 /* Shouldn't happen */
1613 /* Now check what kind of hive we're dealing with */
1614 if (Hive
->Version
>= 5)
1616 /* XP Hive: Use hash leaf */
1617 Index
->Signature
= CM_KEY_HASH_LEAF
;
1619 else if (Hive
->Version
>= 3)
1621 /* Windows 2000 and ReactOS: Use fast leaf */
1622 Index
->Signature
= CM_KEY_FAST_LEAF
;
1626 /* NT 4: Use index leaf */
1627 Index
->Signature
= CM_KEY_INDEX_LEAF
;
1630 /* Setup the index list */
1632 KeyNode
->SubKeyLists
[Type
] = IndexCell
;
1636 /* We already have an index, get it */
1637 Index
= (PCM_KEY_INDEX
)HvGetCell(Hive
, KeyNode
->SubKeyLists
[Type
]);
1644 /* Remember to release the cell later */
1645 CellToRelease
= KeyNode
->SubKeyLists
[Type
];
1647 /* Check if this is a fast leaf that's gotten too full */
1648 if ((Index
->Signature
== CM_KEY_FAST_LEAF
) &&
1649 (Index
->Count
>= CmpMaxFastIndexPerHblock
))
1651 DPRINT("Doing Fast->Slow Leaf conversion\n");
1653 /* Mark this cell as dirty */
1654 HvMarkCellDirty(Hive
, CellToRelease
, FALSE
);
1657 OldIndex
= (PCM_KEY_FAST_INDEX
)Index
;
1659 for (i
= 0; i
< OldIndex
->Count
; i
++)
1661 Index
->List
[i
] = OldIndex
->List
[i
].Cell
;
1664 /* Set the new type value */
1665 Index
->Signature
= CM_KEY_INDEX_LEAF
;
1667 else if (((Index
->Signature
== CM_KEY_INDEX_LEAF
) ||
1668 (Index
->Signature
== CM_KEY_HASH_LEAF
)) &&
1669 (Index
->Count
>= CmpMaxIndexPerHblock
))
1671 /* This is an old/hashed leaf that's gotten too large, root it */
1672 IndexCell
= HvAllocateCell(Hive
,
1673 sizeof(CM_KEY_INDEX
) +
1674 sizeof(HCELL_INDEX
),
1677 if (IndexCell
== HCELL_NIL
)
1683 /* Get the index cell */
1684 Index
= (PCM_KEY_INDEX
)HvGetCell(Hive
, IndexCell
);
1687 /* Shouldn't happen */
1691 /* Mark the index as a root, and set the index cell */
1692 Index
->Signature
= CM_KEY_INDEX_ROOT
;
1694 Index
->List
[0] = KeyNode
->SubKeyLists
[Type
];
1695 KeyNode
->SubKeyLists
[Type
] = IndexCell
;
1699 /* Now we can choose the leaf cell */
1700 LeafCell
= KeyNode
->SubKeyLists
[Type
];
1702 /* Check if we turned the index into a root */
1703 if (Index
->Signature
== CM_KEY_INDEX_ROOT
)
1705 DPRINT("Leaf->Root Index Conversion\n");
1707 /* Get the leaf where to add the new entry (the routine will do
1708 * the splitting if necessary)
1710 LeafCell
= CmpSelectLeaf(Hive
, KeyNode
, &Name
, Type
, &RootPointer
);
1711 if (LeafCell
== HCELL_NIL
)
1718 /* Add our leaf cell */
1719 LeafCell
= CmpAddToLeaf(Hive
, LeafCell
, Child
, &Name
);
1720 if (LeafCell
== HCELL_NIL
)
1726 /* Update the key counts */
1727 KeyNode
->SubKeyCounts
[Type
]++;
1729 /* Check if caller wants us to return the leaf */
1733 *RootPointer
= LeafCell
;
1737 /* Otherwise, mark it as the list index for the cell */
1738 KeyNode
->SubKeyLists
[Type
] = LeafCell
;
1741 /* If the name was compressed, free our copy */
1742 if (IsCompressed
) Hive
->Free(Name
.Buffer
, 0);
1744 /* Release all our cells */
1745 if (IndexCell
!= HCELL_NIL
) HvReleaseCell(Hive
, IndexCell
);
1746 if (CellToRelease
!= HCELL_NIL
) HvReleaseCell(Hive
, CellToRelease
);
1747 HvReleaseCell(Hive
, Parent
);
1753 CmpRemoveSubKey(IN PHHIVE Hive
,
1754 IN HCELL_INDEX ParentKey
,
1755 IN HCELL_INDEX TargetKey
)
1758 UNICODE_STRING SearchName
;
1759 BOOLEAN IsCompressed
;
1761 HCELL_INDEX RootCell
= HCELL_NIL
, LeafCell
, ChildCell
;
1762 PCM_KEY_INDEX Root
= NULL
, Leaf
;
1763 PCM_KEY_FAST_INDEX Child
;
1764 ULONG Storage
, RootIndex
= 0x80000000, LeafIndex
;
1765 BOOLEAN Result
= FALSE
;
1766 HCELL_INDEX CellToRelease1
= HCELL_NIL
, CellToRelease2
= HCELL_NIL
;
1768 /* Get the target key node */
1769 Node
= (PCM_KEY_NODE
)HvGetCell(Hive
, TargetKey
);
1770 if (!Node
) return FALSE
;
1772 /* Make sure it's dirty, then release it */
1773 ASSERT(HvIsCellDirty(Hive
, TargetKey
));
1774 HvReleaseCell(Hive
, TargetKey
);
1776 /* Check if the name is compressed */
1777 if (Node
->Flags
& KEY_COMP_NAME
)
1779 /* Remember for later */
1780 IsCompressed
= TRUE
;
1782 /* Build the search name */
1783 SearchName
.Length
= CmpCompressedNameSize(Node
->Name
,
1785 SearchName
.MaximumLength
= SearchName
.Length
;
1787 /* Do we need an extra bufer? */
1788 if (SearchName
.MaximumLength
> sizeof(Buffer
))
1791 SearchName
.Buffer
= CmpAllocate(SearchName
.Length
,
1794 if (!SearchName
.Buffer
) return FALSE
;
1798 /* Otherwise, use our local stack buffer */
1799 SearchName
.Buffer
= Buffer
;
1802 /* Copy the compressed name */
1803 CmpCopyCompressedName(SearchName
.Buffer
,
1804 SearchName
.MaximumLength
,
1810 /* It's not compressed, build the name directly from the node */
1811 IsCompressed
= FALSE
;
1812 SearchName
.Length
= Node
->NameLength
;
1813 SearchName
.MaximumLength
= Node
->NameLength
;
1814 SearchName
.Buffer
= Node
->Name
;
1817 /* Now get the parent node */
1818 Node
= (PCM_KEY_NODE
)HvGetCell(Hive
, ParentKey
);
1819 if (!Node
) goto Exit
;
1821 /* Make sure it's dirty, then release it */
1822 ASSERT(HvIsCellDirty(Hive
, ParentKey
));
1823 HvReleaseCell(Hive
, ParentKey
);
1825 /* Get the storage type and make sure it's not empty */
1826 Storage
= HvGetCellType(TargetKey
);
1827 ASSERT(Node
->SubKeyCounts
[Storage
] != 0);
1828 //ASSERT(HvIsCellAllocated(Hive, Node->SubKeyLists[Storage]));
1830 /* Get the leaf cell now */
1831 LeafCell
= Node
->SubKeyLists
[Storage
];
1832 Leaf
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
1833 if (!Leaf
) goto Exit
;
1835 /* Remember to release it later */
1836 CellToRelease1
= LeafCell
;
1838 /* Check if the leaf is a root */
1839 if (Leaf
->Signature
== CM_KEY_INDEX_ROOT
)
1841 /* Find the child inside the root */
1842 RootIndex
= CmpFindSubKeyInRoot(Hive
, Leaf
, &SearchName
, &ChildCell
);
1843 if (RootIndex
& 0x80000000) goto Exit
;
1844 ASSERT(ChildCell
!= FALSE
);
1846 /* The root cell is now this leaf */
1848 RootCell
= LeafCell
;
1850 /* And the new leaf is now this child */
1851 LeafCell
= ChildCell
;
1852 Leaf
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
1853 if (!Leaf
) goto Exit
;
1855 /* Remember to release it later */
1856 CellToRelease2
= LeafCell
;
1859 /* Make sure the leaf is valid */
1860 ASSERT((Leaf
->Signature
== CM_KEY_INDEX_LEAF
) ||
1861 (Leaf
->Signature
== CM_KEY_FAST_LEAF
) ||
1862 (Leaf
->Signature
== CM_KEY_HASH_LEAF
));
1864 /* Now get the child in the leaf */
1865 LeafIndex
= CmpFindSubKeyInLeaf(Hive
, Leaf
, &SearchName
, &ChildCell
);
1866 if (LeafIndex
& 0x80000000) goto Exit
;
1867 ASSERT(ChildCell
!= HCELL_NIL
);
1869 /* Decrement key counts and check if this was the last leaf entry */
1870 Node
->SubKeyCounts
[Storage
]--;
1871 if (!(--Leaf
->Count
))
1874 HvFreeCell(Hive
, LeafCell
);
1876 /* Check if we were inside a root */
1879 /* Decrease the root count too, since the leaf is going away */
1880 if (!(--Root
->Count
))
1882 /* The root is gone too,n ow */
1883 HvFreeCell(Hive
, RootCell
);
1884 Node
->SubKeyLists
[Storage
] = HCELL_NIL
;
1886 else if (RootIndex
< Root
->Count
)
1888 /* Bring everything up by one */
1889 RtlMoveMemory(&Root
->List
[RootIndex
],
1890 &Root
->List
[RootIndex
+ 1],
1891 (Root
->Count
- RootIndex
) * sizeof(HCELL_INDEX
));
1896 /* Otherwise, just clear the cell */
1897 Node
->SubKeyLists
[Storage
] = HCELL_NIL
;
1900 else if (LeafIndex
< Leaf
->Count
)
1902 /* Was the leaf a normal index? */
1903 if (Leaf
->Signature
== CM_KEY_INDEX_LEAF
)
1905 /* Bring everything up by one */
1906 RtlMoveMemory(&Leaf
->List
[LeafIndex
],
1907 &Leaf
->List
[LeafIndex
+ 1],
1908 (Leaf
->Count
- LeafIndex
) * sizeof(HCELL_INDEX
));
1912 /* This is a fast index, bring everything up by one */
1913 Child
= (PCM_KEY_FAST_INDEX
)Leaf
;
1914 RtlMoveMemory(&Child
->List
[LeafIndex
],
1915 &Child
->List
[LeafIndex
+1],
1916 (Child
->Count
- LeafIndex
) * sizeof(CM_INDEX
));
1920 /* If we got here, now we're done */
1924 /* Release any cells we may have been holding */
1925 if (CellToRelease1
!= HCELL_NIL
) HvReleaseCell(Hive
, CellToRelease1
);
1926 if (CellToRelease2
!= HCELL_NIL
) HvReleaseCell(Hive
, CellToRelease2
);
1928 /* Check if the name was compressed and not inside our local buffer */
1929 if ((IsCompressed
) && (SearchName
.MaximumLength
> sizeof(Buffer
)))
1931 /* Free the buffer we allocated */
1932 CmpFree(SearchName
.Buffer
, 0);
1935 /* Return the result */