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 /* GLOBALS *******************************************************************/
17 ULONG CmpMaxFastIndexPerHblock
=
18 (HBLOCK_SIZE
- (sizeof(HBIN
) +
20 FIELD_OFFSET(CM_KEY_FAST_INDEX
, List
))) / sizeof(CM_INDEX
);
22 ULONG CmpMaxIndexPerHblock
=
23 (HBLOCK_SIZE
- (sizeof(HBIN
) +
25 FIELD_OFFSET(CM_KEY_INDEX
, List
))) / sizeof(HCELL_INDEX
) - 1;
27 /* FUNCTIONS *****************************************************************/
31 CmpDoCompareKeyName(IN PHHIVE Hive
,
32 IN PCUNICODE_STRING SearchName
,
36 UNICODE_STRING KeyName
;
40 Node
= (PCM_KEY_NODE
)HvGetCell(Hive
, Cell
);
43 /* Check if it's compressed */
44 if (Node
->Flags
& KEY_COMP_NAME
)
46 /* Compare compressed names */
47 Result
= CmpCompareCompressedName(SearchName
,
53 /* Compare the Unicode name directly */
54 KeyName
.Buffer
= Node
->Name
;
55 KeyName
.Length
= Node
->NameLength
;
56 KeyName
.MaximumLength
= KeyName
.Length
;
57 Result
= RtlCompareUnicodeString(SearchName
, &KeyName
, TRUE
);
60 /* Release the cell and return the normalized result */
61 HvReleaseCell(Hive
, Cell
);
62 return (Result
== 0) ? Result
: ((Result
> 0) ? 1 : -1);
67 CmpCompareInIndex(IN PHHIVE Hive
,
68 IN PCUNICODE_STRING SearchName
,
70 IN PCM_KEY_INDEX Index
,
71 IN PHCELL_INDEX SubKey
)
73 PCM_KEY_FAST_INDEX FastIndex
;
77 ULONG ActualNameLength
= 4, CompareLength
, NameLength
;
83 /* Check if we are a fast or hashed leaf */
84 if ((Index
->Signature
== CM_KEY_FAST_LEAF
) ||
85 (Index
->Signature
== CM_KEY_HASH_LEAF
))
87 /* Get the Fast/Hash Index */
88 FastIndex
= (PCM_KEY_FAST_INDEX
)Index
;
89 FastEntry
= &FastIndex
->List
[Count
];
91 /* Check if we are a hash leaf, in which case we skip all this */
92 if (Index
->Signature
== CM_KEY_FAST_LEAF
)
94 /* Find out just how much of the name is there */
95 for (i
= 0; i
< 4; i
++)
97 /* Check if this entry is empty */
98 if (!FastEntry
->NameHint
[i
])
100 /* Only this much! */
101 ActualNameLength
= i
;
106 /* How large is the name and how many characters to compare */
107 NameLength
= SearchName
->Length
/ sizeof(WCHAR
);
108 CompareLength
= min(NameLength
, ActualNameLength
);
110 /* Loop all the chars we'll test */
111 for (i
= 0; i
< CompareLength
; i
++)
113 /* Get one char from each buffer */
114 p
= SearchName
->Buffer
[i
];
115 pp
= FastEntry
->NameHint
[i
];
117 /* See if they match and return result if they don't */
118 Result
= (LONG
)RtlUpcaseUnicodeChar(p
) -
119 (LONG
)RtlUpcaseUnicodeChar(pp
);
120 if (Result
) return (Result
> 0) ? 1 : -1;
124 /* If we got here then we have to do a full compare */
125 Result
= CmpDoCompareKeyName(Hive
, SearchName
, FastEntry
->Cell
);
126 if (Result
== 2) return Result
;
127 if (!Result
) *SubKey
= FastEntry
->Cell
;
131 /* We aren't, so do a name compare and return the subkey found */
132 Result
= CmpDoCompareKeyName(Hive
, SearchName
, Index
->List
[Count
]);
133 if (Result
== 2) return Result
;
134 if (!Result
) *SubKey
= Index
->List
[Count
];
137 /* Return the comparison result */
143 CmpFindSubKeyInRoot(IN PHHIVE Hive
,
144 IN PCM_KEY_INDEX Index
,
145 IN PCUNICODE_STRING SearchName
,
146 IN PHCELL_INDEX SubKey
)
148 ULONG High
, Low
= 0, i
= 0, ReturnIndex
;
149 HCELL_INDEX LeafCell
;
153 /* Verify Index for validity */
154 ASSERT(Index
->Count
!= 0);
155 ASSERT(Index
->Signature
== CM_KEY_INDEX_ROOT
);
157 /* Set high limit and loop */
158 High
= Index
->Count
- 1;
161 /* Choose next entry */
162 #ifdef SOMEONE_WAS_NICE_ENOUGH_TO_MAKE_OUR_CELLS_LEXICALLY_SORTED
163 i
= ((High
- Low
) / 2) + Low
;
166 /* Get the leaf cell and then the leaf itself */
167 LeafCell
= Index
->List
[i
];
168 Leaf
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
171 /* Make sure the leaf is valid */
172 ASSERT((Leaf
->Signature
== CM_KEY_INDEX_LEAF
) ||
173 (Leaf
->Signature
== CM_KEY_FAST_LEAF
) ||
174 (Leaf
->Signature
== CM_KEY_HASH_LEAF
));
175 ASSERT(Leaf
->Count
!= 0);
178 Result
= CmpCompareInIndex(Hive
,
183 if (Result
== 2) goto Big
;
185 /* Check if we found the leaf */
188 /* We found the leaf */
194 #ifdef SOMEONE_WAS_NICE_ENOUGH_TO_MAKE_OUR_CELLS_LEXICALLY_SORTED
195 /* Check for negative result */
198 /* If we got here, we should be at -1 */
199 ASSERT(Result
== -1);
201 /* Do another lookup, since we might still be in the right leaf */
202 Result
= CmpCompareInIndex(Hive
,
207 if (Result
== 2) goto Big
;
209 /* Check if it's not below */
213 * If the name was first below, and now it is above,
214 * then this means that it is somewhere in this leaf.
215 * Make sure we didn't get some weird result
217 ASSERT((Result
== 1) || (Result
== 0));
225 /* Update the limit to this index, since we know it's not higher. */
230 /* Update the base to this index, since we know it's not lower. */
238 /* This was some sort of special key */
239 ReturnIndex
= 0x80000000;
243 /* Check if there is only one entry left */
244 if ((High
- Low
) <= 1) break;
246 /* Release the leaf cell */
247 HvReleaseCell(Hive
, LeafCell
);
249 #ifndef SOMEONE_WAS_NICE_ENOUGH_TO_MAKE_OUR_CELLS_LEXICALLY_SORTED
250 /* Go to the next index, and return failure if we reach the end */
260 /* Make sure we got here for the right reasons */
261 ASSERT((High
- Low
== 1) || (High
== Low
));
263 /* Get the leaf cell and the leaf */
264 LeafCell
= Index
->List
[Low
];
265 Leaf
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
269 Result
= CmpCompareInIndex(Hive
,
274 if (Result
== 2) goto Big
;
276 /* Check if we found it */
279 /* We got lucky...return it */
285 /* It's below, so could still be in this leaf */
288 /* Make sure we're -1 */
289 ASSERT(Result
== -1);
291 /* Do a search from the bottom */
292 Result
= CmpCompareInIndex(Hive
, SearchName
, 0, Leaf
, SubKey
);
293 if (Result
== 2) goto Big
;
296 * Check if it's above, which means that it's within the ranges of our
297 * leaf (since we were below before).
302 ASSERT((Result
== 1) || (Result
== 0));
304 /* Yep, so we're in the right leaf; return it. */
310 /* It's still below us, so fail */
315 /* Release the leaf cell */
316 HvReleaseCell(Hive
, LeafCell
);
318 /* Well the low didn't work too well, so try the high. */
319 LeafCell
= Index
->List
[High
];
320 Leaf
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
324 Result
= CmpCompareInIndex(Hive
,
329 if (Result
== 2) goto Big
;
331 /* Check if we found it */
334 /* We got lucky... return it */
340 /* Check if we are too high */
343 /* Make sure we're -1 */
344 ASSERT(Result
== -1);
347 * Once again... since we were first too low and now too high, then
348 * this means we are within the range of this leaf... return it.
355 /* If we got here, then we are too low, again. */
362 /* Return path...check if we have a leaf to free */
364 if (Leaf
) HvReleaseCell(Hive
, LeafCell
);
366 /* Return the index */
372 CmpFindSubKeyInLeaf(IN PHHIVE Hive
,
373 IN PCM_KEY_INDEX Index
,
374 IN PCUNICODE_STRING SearchName
,
375 IN PHCELL_INDEX SubKey
)
377 ULONG High
, Low
= 0, i
;
380 /* Verify Index for validity */
381 ASSERT((Index
->Signature
== CM_KEY_INDEX_LEAF
) ||
382 (Index
->Signature
== CM_KEY_FAST_LEAF
) ||
383 (Index
->Signature
== CM_KEY_HASH_LEAF
));
385 /* Get the upper bound and middle entry */
386 High
= Index
->Count
- 1;
387 #ifdef SOMEONE_WAS_NICE_ENOUGH_TO_MAKE_OUR_CELLS_LEXICALLY_SORTED
393 /* Check if we don't actually have any entries */
401 /* Start compare loop */
404 /* Do the actual comparison and check the result */
405 Result
= CmpCompareInIndex(Hive
, SearchName
, i
, Index
, SubKey
);
408 /* Fail with special value */
413 /* Check if we got lucky and found it */
414 if (!Result
) return i
;
416 #ifdef SOMEONE_WAS_NICE_ENOUGH_TO_MAKE_OUR_CELLS_LEXICALLY_SORTED
417 /* Check if the result is below us */
420 /* Set the new bound; it can't be higher then where we are now. */
421 ASSERT(Result
== -1);
426 /* Set the new bound... it can't be lower then where we are now. */
431 /* Check if this is the last entry, if so, break out and handle it */
432 if ((High
- Low
) <= 1) break;
434 /* Set the new index */
435 i
= ((High
- Low
) / 2) + Low
;
447 * If we get here, High - Low = 1 or High == Low
448 * Simply look first at Low, then at High
450 Result
= CmpCompareInIndex(Hive
, SearchName
, Low
, Index
, SubKey
);
453 /* Fail with special value */
458 /* Check if we got lucky and found it */
459 if (!Result
) return Low
;
461 /* Check if the result is below us */
464 /* Return the low entry */
465 ASSERT(Result
== -1);
470 * If we got here, then just check the high and return it no matter what
471 * the result is (since we're a leaf, it has to be near there anyway).
473 Result
= CmpCompareInIndex(Hive
, SearchName
, High
, Index
, SubKey
);
476 /* Fail with special value */
481 /* Return the high */
487 CmpComputeHashKey(IN ULONG Hash
,
488 IN PCUNICODE_STRING Name
,
489 IN BOOLEAN AllowSeparators
)
494 /* Make some sanity checks on our parameters */
495 ASSERT((Name
->Length
== 0) ||
497 (Name
->Buffer
[0] != OBJ_NAME_PATH_SEPARATOR
));
499 /* If the name is empty, there is nothing to hash! */
500 if (!Name
->Length
) return Hash
;
502 /* Set the buffer and loop every character */
504 for (i
= 0; i
< Name
->Length
; i
+= sizeof(WCHAR
), Cp
++)
506 /* Make sure we don't have a separator when we shouldn't */
507 ASSERT(AllowSeparators
|| (*Cp
!= OBJ_NAME_PATH_SEPARATOR
));
509 /* Check what kind of char we have */
512 /* In the lower case region... is it truly lower case? */
515 /* Yes! Calculate it ourselves! */
516 Value
= *Cp
- L
'a' + L
'A';
520 /* No, use the API */
521 Value
= RtlUpcaseUnicodeChar(*Cp
);
526 /* Reuse the char, it's already upcased */
530 /* Multiply by a prime and add our value */
535 /* Return the hash */
541 CmpDoFindSubKeyByNumber(IN PHHIVE Hive
,
542 IN PCM_KEY_INDEX Index
,
546 HCELL_INDEX LeafCell
= 0;
547 PCM_KEY_INDEX Leaf
= NULL
;
548 PCM_KEY_FAST_INDEX FastIndex
;
551 /* Check if this is a root */
552 if (Index
->Signature
== CM_KEY_INDEX_ROOT
)
555 for (i
= 0; i
< Index
->Count
; i
++)
557 /* Check if this isn't the first iteration */
560 /* Make sure we had something valid, and release it */
561 ASSERT(Leaf
!= NULL
);
562 ASSERT(LeafCell
== Index
->List
[i
- 1]);
563 HvReleaseCell(Hive
, LeafCell
);
566 /* Get the leaf cell and the leaf for this index */
567 LeafCell
= Index
->List
[i
];
568 Leaf
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
569 if (!Leaf
) return HCELL_NIL
;
571 /* Check if the index may be inside it */
572 if (Number
< Leaf
->Count
)
574 /* Check if this is a fast or hash leaf */
575 if ((Leaf
->Signature
== CM_KEY_FAST_LEAF
) ||
576 (Leaf
->Signature
== CM_KEY_HASH_LEAF
))
578 /* Get the fast index */
579 FastIndex
= (PCM_KEY_FAST_INDEX
)Leaf
;
581 /* Look inside the list to get our actual cell */
582 Result
= FastIndex
->List
[Number
].Cell
;
583 HvReleaseCell(Hive
, LeafCell
);
588 /* Regular leaf, so just use the index directly */
589 Result
= Leaf
->List
[Number
];
591 /* Release and return it */
592 HvReleaseCell(Hive
,LeafCell
);
598 /* Otherwise, skip this leaf */
599 Number
= Number
- Leaf
->Count
;
603 /* Should never get here */
607 /* If we got here, then the cell is in this index */
608 ASSERT(Number
< Index
->Count
);
610 /* Check if we're a fast or hash leaf */
611 if ((Index
->Signature
== CM_KEY_FAST_LEAF
) ||
612 (Index
->Signature
== CM_KEY_HASH_LEAF
))
614 /* We are, get the fast index and get the cell from the list */
615 FastIndex
= (PCM_KEY_FAST_INDEX
)Index
;
616 return FastIndex
->List
[Number
].Cell
;
620 /* We aren't, so use the index directly to grab the cell */
621 return Index
->List
[Number
];
627 CmpFindSubKeyByNumber(IN PHHIVE Hive
,
628 IN PCM_KEY_NODE Node
,
632 HCELL_INDEX Result
= HCELL_NIL
;
634 /* Check if it's in the stable list */
635 if (Number
< Node
->SubKeyCounts
[Stable
])
637 /* Get the actual key index */
638 Index
= (PCM_KEY_INDEX
)HvGetCell(Hive
, Node
->SubKeyLists
[Stable
]);
639 if (!Index
) return HCELL_NIL
;
641 /* Do a search inside it */
642 Result
= CmpDoFindSubKeyByNumber(Hive
, Index
, Number
);
644 /* Release the cell and return the result */
645 HvReleaseCell(Hive
, Node
->SubKeyLists
[Stable
]);
648 else if (Hive
->StorageTypeCount
> Volatile
)
650 /* It's in the volatile list */
651 Number
= Number
- Node
->SubKeyCounts
[Stable
];
652 if (Number
< Node
->SubKeyCounts
[Volatile
])
654 /* Get the actual key index */
655 Index
= (PCM_KEY_INDEX
)HvGetCell(Hive
,
656 Node
->SubKeyLists
[Volatile
]);
657 if (!Index
) return HCELL_NIL
;
659 /* Do a search inside it */
660 Result
= CmpDoFindSubKeyByNumber(Hive
, Index
, Number
);
662 /* Release the cell and return the result */
663 HvReleaseCell(Hive
, Node
->SubKeyLists
[Volatile
]);
668 /* Nothing was found */
674 CmpFindSubKeyByHash(IN PHHIVE Hive
,
675 IN PCM_KEY_FAST_INDEX FastIndex
,
676 IN PCUNICODE_STRING SearchName
)
681 /* Make sure it's really a hash */
682 ASSERT(FastIndex
->Signature
== CM_KEY_HASH_LEAF
);
684 /* Compute the hash key for the name */
685 HashKey
= CmpComputeHashKey(0, SearchName
, FALSE
);
687 /* Loop all the entries */
688 for (i
= 0; i
< FastIndex
->Count
; i
++)
691 FastEntry
= &FastIndex
->List
[i
];
693 /* Compare the hash first */
694 if (FastEntry
->HashKey
== HashKey
)
696 /* Go ahead for a full compare */
697 if (!(CmpDoCompareKeyName(Hive
, SearchName
, FastEntry
->Cell
)))
699 /* It matched, return the cell */
700 return FastEntry
->Cell
;
705 /* If we got here then we failed */
711 CmpFindSubKeyByName(IN PHHIVE Hive
,
712 IN PCM_KEY_NODE Parent
,
713 IN PCUNICODE_STRING SearchName
)
716 PCM_KEY_INDEX IndexRoot
;
717 HCELL_INDEX SubKey
, CellToRelease
;
720 /* Loop each storage type */
721 for (i
= 0; i
< Hive
->StorageTypeCount
; i
++)
723 /* Make sure the parent node has subkeys */
724 if (Parent
->SubKeyCounts
[i
])
727 IndexRoot
= (PCM_KEY_INDEX
)HvGetCell(Hive
, Parent
->SubKeyLists
[i
]);
728 if (!IndexRoot
) return HCELL_NIL
;
730 /* Get the cell we'll need to release */
731 CellToRelease
= Parent
->SubKeyLists
[i
];
733 /* Check if this is another index root */
734 if (IndexRoot
->Signature
== CM_KEY_INDEX_ROOT
)
737 #ifndef SOMEONE_WAS_NICE_ENOUGH_TO_MAKE_OUR_CELLS_LEXICALLY_SORTED
738 /* CmpFindSubKeyInRoot is useless for actually finding the correct leaf when keys are not sorted */
741 /* Loop through each leaf in the index root */
742 for (ii
=0; ii
<IndexRoot
->Count
; ii
++)
744 Leaf
= HvGetCell(Hive
, IndexRoot
->List
[ii
]);
747 Found
= CmpFindSubKeyInLeaf(Hive
, Leaf
, SearchName
, &SubKey
);
748 HvReleaseCell(Hive
, IndexRoot
->List
[ii
]);
749 if (Found
& 0x80000000)
751 HvReleaseCell(Hive
, CellToRelease
);
755 if (SubKey
!= HCELL_NIL
)
757 HvReleaseCell(Hive
, CellToRelease
);
763 /* Lookup the name in the root */
764 Found
= CmpFindSubKeyInRoot(Hive
,
769 /* Release the previous cell */
770 ASSERT(CellToRelease
!= HCELL_NIL
);
771 HvReleaseCell(Hive
, CellToRelease
);
773 /* Make sure we found something valid */
774 if (Found
& 0x80000000) break;
776 /* Get the new Index Root and set the new cell to be released */
777 if (SubKey
== HCELL_NIL
) continue;
778 CellToRelease
= SubKey
;
779 IndexRoot
= (PCM_KEY_INDEX
)HvGetCell(Hive
, SubKey
);
782 /* Make sure the signature is what we expect it to be */
783 ASSERT((IndexRoot
->Signature
== CM_KEY_INDEX_LEAF
) ||
784 (IndexRoot
->Signature
== CM_KEY_FAST_LEAF
) ||
785 (IndexRoot
->Signature
== CM_KEY_HASH_LEAF
));
787 /* Check if this isn't a hashed leaf */
788 if (IndexRoot
->Signature
!= CM_KEY_HASH_LEAF
)
790 /* Find the subkey in the leaf */
791 Found
= CmpFindSubKeyInLeaf(Hive
,
796 /* Release the previous cell */
797 ASSERT(CellToRelease
!= HCELL_NIL
);
798 HvReleaseCell(Hive
, CellToRelease
);
800 /* Make sure we found a valid index */
801 if (Found
& 0x80000000) break;
805 /* Find the subkey in the hash */
806 SubKey
= CmpFindSubKeyByHash(Hive
,
807 (PCM_KEY_FAST_INDEX
)IndexRoot
,
810 /* Release the previous cell */
811 ASSERT(CellToRelease
!= HCELL_NIL
);
812 HvReleaseCell(Hive
, CellToRelease
);
815 /* Make sure we got a valid subkey and return it */
816 if (SubKey
!= HCELL_NIL
) return SubKey
;
820 /* If we got here, then we failed */
826 CmpMarkIndexDirty(IN PHHIVE Hive
,
827 IN HCELL_INDEX ParentKey
,
828 IN HCELL_INDEX TargetKey
)
831 UNICODE_STRING SearchName
;
832 BOOLEAN IsCompressed
;
835 HCELL_INDEX IndexCell
, Child
= HCELL_NIL
, CellToRelease
= HCELL_NIL
;
837 /* Get the target key node */
838 Node
= (PCM_KEY_NODE
)HvGetCell(Hive
, TargetKey
);
839 if (!Node
) return FALSE
;
841 /* Check if it's compressed */
842 if (Node
->Flags
& KEY_COMP_NAME
)
844 /* Remember this for later */
847 /* Build the search name */
848 SearchName
.Length
= CmpCompressedNameSize(Node
->Name
,
850 SearchName
.MaximumLength
= SearchName
.Length
;
851 SearchName
.Buffer
= CmpAllocate(SearchName
.Length
,
854 if (!SearchName
.Buffer
)
857 HvReleaseCell(Hive
, TargetKey
);
862 CmpCopyCompressedName(SearchName
.Buffer
,
863 SearchName
.MaximumLength
,
869 /* Name isn't compressed, build it directly from the node */
870 IsCompressed
= FALSE
;
871 SearchName
.Length
= Node
->NameLength
;
872 SearchName
.MaximumLength
= Node
->NameLength
;
873 SearchName
.Buffer
= Node
->Name
;
876 /* We can release the target key now */
877 HvReleaseCell(Hive
, TargetKey
);
879 /* Now get the parent key node */
880 Node
= (PCM_KEY_NODE
)HvGetCell(Hive
, ParentKey
);
881 if (!Node
) goto Quickie
;
883 /* Loop all hive storage */
884 for (i
= 0; i
< Hive
->StorageTypeCount
; i
++)
886 /* Check if any subkeys are in this index */
887 if (Node
->SubKeyCounts
[i
])
889 /* Get the cell index */
890 //ASSERT(HvIsCellAllocated(Hive, Node->SubKeyLists[i]));
891 IndexCell
= Node
->SubKeyLists
[i
];
893 /* Check if we had anything to release from before */
894 if (CellToRelease
!= HCELL_NIL
)
897 HvReleaseCell(Hive
, CellToRelease
);
898 CellToRelease
= HCELL_NIL
;
901 /* Get the key index for the cell */
902 Index
= (PCM_KEY_INDEX
)HvGetCell(Hive
, IndexCell
);
903 if (!Index
) goto Quickie
;
905 /* Release it at the next iteration or below */
906 CellToRelease
= IndexCell
;
908 /* Check if this is a root */
909 if (Index
->Signature
== CM_KEY_INDEX_ROOT
)
911 /* Get the child inside the root */
912 Result
= CmpFindSubKeyInRoot(Hive
, Index
, &SearchName
, &Child
);
913 if (Result
& 0x80000000) goto Quickie
;
914 if (Child
== HCELL_NIL
) continue;
916 /* We found it, mark the cell dirty */
917 HvMarkCellDirty(Hive
, IndexCell
, FALSE
);
919 /* Check if we had anything to release from before */
920 if (CellToRelease
!= HCELL_NIL
)
923 HvReleaseCell(Hive
, CellToRelease
);
924 CellToRelease
= HCELL_NIL
;
927 /* Now this child is the index, get the actual key index */
929 Index
= (PCM_KEY_INDEX
)HvGetCell(Hive
, Child
);
930 if (!Index
) goto Quickie
;
932 /* Release it later */
933 CellToRelease
= Child
;
936 /* Make sure this is a valid index */
937 ASSERT((Index
->Signature
== CM_KEY_INDEX_LEAF
) ||
938 (Index
->Signature
== CM_KEY_FAST_LEAF
) ||
939 (Index
->Signature
== CM_KEY_HASH_LEAF
));
941 /* Find the child in the leaf */
942 Result
= CmpFindSubKeyInLeaf(Hive
, Index
, &SearchName
, &Child
);
943 if (Result
& 0x80000000) goto Quickie
;
944 if (Child
!= HCELL_NIL
)
946 /* We found it, free the name now */
947 if (IsCompressed
) CmpFree(SearchName
.Buffer
, 0);
949 /* Release the parent key */
950 HvReleaseCell(Hive
, ParentKey
);
952 /* Check if we had a left over cell to release */
953 if (CellToRelease
!= HCELL_NIL
)
956 HvReleaseCell(Hive
, CellToRelease
);
959 /* And mark the index cell dirty */
960 HvMarkCellDirty(Hive
, IndexCell
, FALSE
);
967 /* Release any cells that we still hold */
968 if (Node
) HvReleaseCell(Hive
, ParentKey
);
969 if (CellToRelease
!= HCELL_NIL
) HvReleaseCell(Hive
, CellToRelease
);
971 /* Free the search name and return failure */
972 if (IsCompressed
) CmpFree(SearchName
.Buffer
, 0);
978 CmpAddToLeaf(IN PHHIVE Hive
,
979 IN HCELL_INDEX LeafCell
,
980 IN HCELL_INDEX NewKey
,
981 IN PUNICODE_STRING Name
)
984 PCM_KEY_FAST_INDEX FastLeaf
;
985 ULONG Size
, OldSize
, EntrySize
, i
, j
;
986 HCELL_INDEX NewCell
, Child
;
989 /* Mark the leaf dirty */
990 HvMarkCellDirty(Hive
, LeafCell
, FALSE
);
992 /* Get the leaf cell */
993 Leaf
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
996 /* Shouldn't happen */
1002 HvReleaseCell(Hive
, LeafCell
);
1004 /* Check if this is an index leaf */
1005 if (Leaf
->Signature
== CM_KEY_INDEX_LEAF
)
1007 /* This is an old-style leaf */
1009 EntrySize
= sizeof(HCELL_INDEX
);
1014 ASSERT((Leaf
->Signature
== CM_KEY_FAST_LEAF
) ||
1015 (Leaf
->Signature
== CM_KEY_HASH_LEAF
));
1017 /* This is a new-style optimized fast (or hash) leaf */
1018 FastLeaf
= (PCM_KEY_FAST_INDEX
)Leaf
;
1019 EntrySize
= sizeof(CM_INDEX
);
1022 /* Get the current size of the leaf */
1023 OldSize
= HvGetCellSize(Hive
, Leaf
);
1025 /* Calculate the size of the free entries */
1027 Size
-= EntrySize
* Leaf
->Count
+ FIELD_OFFSET(CM_KEY_INDEX
, List
);
1029 /* Assume we'll re-use the same leaf */
1032 /* Check if we're out of space */
1033 if ((Size
/ EntrySize
) < 1)
1035 /* Grow the leaf by 1.5x, making sure we can at least fit this entry */
1036 Size
= OldSize
+ OldSize
/ 2;
1037 if (Size
< (OldSize
+ EntrySize
)) Size
= OldSize
+ EntrySize
;
1039 /* Re-allocate the leaf */
1040 NewCell
= HvReallocateCell(Hive
, LeafCell
, Size
);
1041 if (NewCell
== HCELL_NIL
) return HCELL_NIL
;
1043 /* Get the leaf cell */
1044 Leaf
= (PCM_KEY_INDEX
)HvGetCell(Hive
, NewCell
);
1047 /* This shouldn't happen */
1052 /* Release the cell */
1053 HvReleaseCell(Hive
, NewCell
);
1055 /* Update the fast leaf pointer if we had one */
1056 if (FastLeaf
) FastLeaf
= (PCM_KEY_FAST_INDEX
)Leaf
;
1059 /* Find the insertion point for our entry */
1060 i
= CmpFindSubKeyInLeaf(Hive
, Leaf
, Name
, &Child
);
1061 if (i
& 0x80000000) return HCELL_NIL
;
1062 ASSERT(Child
== HCELL_NIL
);
1064 /* Check if we're not last */
1065 if (i
!= Leaf
->Count
)
1067 /* Find out where we should go */
1068 Result
= CmpCompareInIndex(Hive
,
1073 if (Result
== 2) return HCELL_NIL
;
1074 ASSERT(Result
!= 0);
1076 /* Check if we come after */
1079 /* We do, insert us after the key */
1080 ASSERT(Result
== 1);
1084 /* Check if we're still not last */
1085 if (i
!= Leaf
->Count
)
1087 /* Check if we had a fast leaf or not */
1090 /* Copy the fast indexes */
1091 RtlMoveMemory(&FastLeaf
->List
[i
+ 1],
1093 (FastLeaf
->Count
- i
) * sizeof(CM_INDEX
));
1097 /* Copy the indexes themselves */
1098 RtlMoveMemory(&Leaf
->List
[i
+ 1],
1100 (Leaf
->Count
- i
) * sizeof(HCELL_INDEX
));
1105 /* Check if this is a new-style leaf */
1109 FastLeaf
->List
[i
].Cell
= NewKey
;
1111 /* Check if this is a hash leaf */
1112 if( FastLeaf
->Signature
== CM_KEY_HASH_LEAF
)
1114 /* Set our hash key */
1115 FastLeaf
->List
[i
].HashKey
= CmpComputeHashKey(0, Name
, FALSE
);
1119 /* First, clear the name */
1120 FastLeaf
->List
[i
].NameHint
[0] = 0;
1121 FastLeaf
->List
[i
].NameHint
[1] = 0;
1122 FastLeaf
->List
[i
].NameHint
[2] = 0;
1123 FastLeaf
->List
[i
].NameHint
[3] = 0;
1125 /* Now, figure out if we can fit */
1126 if (Name
->Length
/ sizeof(WCHAR
) < 4)
1128 /* We can fit, use our length */
1129 j
= Name
->Length
/ sizeof(WCHAR
);
1133 /* We can't, use a maximum of 4 */
1137 /* Now fill out the name hint */
1140 /* Look for invalid characters and break out if we found one */
1141 if ((USHORT
)Name
->Buffer
[j
- 1] > (UCHAR
)-1) break;
1143 /* Otherwise, copy the a character */
1144 FastLeaf
->List
[i
].NameHint
[j
- 1] = (UCHAR
)Name
->Buffer
[j
- 1];
1150 /* This is an old-style leaf, just set our index directly */
1151 Leaf
->List
[i
] = NewKey
;
1154 /* Update the leaf count and return the new cell */
1161 CmpSplitLeaf(IN PHHIVE Hive
,
1162 IN HCELL_INDEX RootCell
,
1163 IN ULONG RootSelect
,
1164 IN HSTORAGE_TYPE Type
)
1166 PCM_KEY_INDEX IndexKey
, LeafKey
, NewKey
;
1167 PCM_KEY_FAST_INDEX FastLeaf
;
1168 HCELL_INDEX LeafCell
, NewCell
;
1169 ULONG FirstHalf
, LastHalf
;
1170 ULONG EntrySize
, TotalSize
;
1173 IndexKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, RootCell
);
1175 /* Check if we've got valid IndexKey */
1176 if (!IndexKey
) return HCELL_NIL
;
1178 /* Get the leaf cell and key */
1179 LeafCell
= IndexKey
->List
[RootSelect
];
1180 LeafKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
1182 /* Check if we've got valid LeafKey */
1183 if (!LeafKey
) return HCELL_NIL
;
1185 /* We are going to divide this leaf into two halves */
1186 FirstHalf
= (LeafKey
->Count
/ 2);
1187 LastHalf
= LeafKey
->Count
- FirstHalf
;
1189 /* Now check what kind of hive we're dealing with,
1190 * and compute entry size
1192 if (Hive
->Version
>= 5)
1194 /* XP Hive: Use hash leaf */
1195 ASSERT(LeafKey
->Signature
== CM_KEY_HASH_LEAF
);
1196 EntrySize
= sizeof(CM_INDEX
);
1200 /* Use index leaf */
1201 ASSERT(LeafKey
->Signature
== CM_KEY_INDEX_LEAF
);
1202 EntrySize
= sizeof(HCELL_INDEX
);
1205 /* Compute the total size */
1206 TotalSize
= (EntrySize
* LastHalf
) + FIELD_OFFSET(CM_KEY_INDEX
, List
) + 1;
1208 /* Mark the leaf cell dirty */
1209 HvMarkCellDirty(Hive
, LeafCell
, FALSE
);
1211 /* Make sure its type is the same */
1212 ASSERT(HvGetCellType(LeafCell
) == Type
);
1214 /* Allocate the cell, fail in case of error */
1215 NewCell
= HvAllocateCell(Hive
, TotalSize
, Type
, LeafCell
);
1216 if (NewCell
== HCELL_NIL
) return NewCell
;
1219 NewKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, NewCell
);
1222 /* Free the cell and exit - should not happen! */
1224 HvFreeCell(Hive
, NewCell
);
1228 /* Release the newly created cell */
1229 HvReleaseCell(Hive
, NewCell
);
1231 /* Set its signature according to the version of the hive */
1232 if (Hive
->Version
>= 5)
1234 /* XP Hive: Use hash leaf signature */
1235 NewKey
->Signature
= CM_KEY_HASH_LEAF
;
1239 /* Use index leaf signature */
1240 NewKey
->Signature
= CM_KEY_INDEX_LEAF
;
1243 /* Calculate the size of the free entries in the root key */
1244 TotalSize
= HvGetCellSize(Hive
, IndexKey
) -
1245 (IndexKey
->Count
* sizeof(HCELL_INDEX
)) -
1246 FIELD_OFFSET(CM_KEY_INDEX
, List
);
1248 /* Check if we're out of space */
1249 if (TotalSize
/ sizeof(HCELL_INDEX
) < 1)
1251 /* Grow the leaf by one more entry */
1252 TotalSize
= HvGetCellSize(Hive
, IndexKey
) + sizeof(HCELL_INDEX
);
1254 /* Re-allocate the root */
1255 RootCell
= HvReallocateCell(Hive
, RootCell
, TotalSize
);
1256 if (RootCell
== HCELL_NIL
)
1258 /* Free the cell and exit */
1259 HvFreeCell(Hive
, NewCell
);
1263 /* Get the leaf cell */
1264 IndexKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, RootCell
);
1267 /* This shouldn't happen */
1273 /* Splitting is done, now we need to copy the contents,
1274 * according to the hive version
1276 if (Hive
->Version
>= 5)
1278 /* Copy the fast indexes */
1279 FastLeaf
= (PCM_KEY_FAST_INDEX
)LeafKey
;
1280 RtlMoveMemory(&NewKey
->List
[0],
1281 &FastLeaf
->List
[FirstHalf
],
1282 LastHalf
* EntrySize
);
1286 /* Copy the indexes themselves */
1287 RtlMoveMemory(&NewKey
->List
[0],
1288 &LeafKey
->List
[FirstHalf
],
1289 LastHalf
* EntrySize
);
1292 /* Shift the data inside the root key */
1293 if (RootSelect
< (IndexKey
->Count
- 1))
1295 RtlMoveMemory(&IndexKey
->List
[RootSelect
+ 2],
1296 &IndexKey
->List
[RootSelect
+ 1],
1298 (RootSelect
+ 1)) * sizeof(HCELL_INDEX
));
1301 /* Make sure both old and new computed counts are valid */
1302 ASSERT(FirstHalf
!= 0);
1303 ASSERT(LastHalf
!= 0);
1305 /* Update the count value of old and new keys */
1306 LeafKey
->Count
= FirstHalf
;
1307 NewKey
->Count
= LastHalf
;
1309 /* Increase the count value of the root key */
1312 /* Set the new cell in root's list */
1313 IndexKey
->List
[RootSelect
+ 1] = NewCell
;
1315 /* Return the root cell */
1321 CmpSelectLeaf(IN PHHIVE Hive
,
1322 IN PCM_KEY_NODE KeyNode
,
1323 IN PUNICODE_STRING Name
,
1324 IN HSTORAGE_TYPE Type
,
1325 IN PHCELL_INDEX
*RootCell
)
1327 PCM_KEY_INDEX IndexKey
, LeafKey
;
1328 PCM_KEY_FAST_INDEX FastLeaf
;
1329 HCELL_INDEX LeafCell
, CurrentCell
;
1333 /* Mark it as dirty */
1334 HvMarkCellDirty(Hive
, KeyNode
->SubKeyLists
[Type
], FALSE
);
1337 IndexKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, KeyNode
->SubKeyLists
[Type
]);
1339 /* Check if we've got a valid key */
1342 /* Should not happen! */
1343 ASSERTMSG("IndexKey = NULL!, it should not happen!\n", FALSE
);
1348 ASSERT(IndexKey
->Signature
== CM_KEY_INDEX_ROOT
);
1353 SubKeyIndex
= CmpFindSubKeyInRoot(Hive
, IndexKey
, Name
, &LeafCell
);
1355 /* Make sure we found something valid */
1356 if (SubKeyIndex
& 0x80000000) return HCELL_NIL
;
1358 /* Try to fit it into the LeafCell, if it was found */
1359 if (LeafCell
!= HCELL_NIL
)
1361 /* Get the leaf key */
1362 LeafKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
1364 /* Check for failure */
1365 if (!LeafKey
) return HCELL_NIL
;
1367 /* Check if it fits into this leaf and break */
1368 if (LeafKey
->Count
< CmpMaxIndexPerHblock
)
1370 /* Fill in the result and return it */
1371 *RootCell
= &IndexKey
->List
[SubKeyIndex
];
1375 /* It didn't fit, so proceed to splitting */
1379 /* Get the leaf cell at the very end */
1380 LeafCell
= IndexKey
->List
[SubKeyIndex
];
1381 LeafKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
1383 /* Return an error in case of problems */
1384 if (!LeafKey
) return HCELL_NIL
;
1386 /* Choose the cell to search from depending on the key type */
1387 if ((LeafKey
->Signature
== CM_KEY_FAST_LEAF
) ||
1388 (LeafKey
->Signature
== CM_KEY_HASH_LEAF
))
1390 FastLeaf
= (PCM_KEY_FAST_INDEX
)LeafKey
;
1391 CurrentCell
= FastLeaf
->List
[0].Cell
;
1395 /* Make sure it's an index leaf */
1396 ASSERT(LeafKey
->Signature
== CM_KEY_INDEX_LEAF
);
1397 CurrentCell
= LeafKey
->List
[0];
1400 /* Do a name compare */
1401 Result
= CmpDoCompareKeyName(Hive
, Name
, CurrentCell
);
1403 /* Check for failure */
1404 if (Result
== 2) return HCELL_NIL
;
1406 /* Names can't be equal, ensure that */
1407 ASSERT(Result
!= 0);
1409 /* Check if it's above */
1412 /* Get the cell in the index */
1413 LeafCell
= IndexKey
->List
[SubKeyIndex
];
1414 LeafKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
1416 /* Return an error in case of problems */
1417 if (!LeafKey
) return HCELL_NIL
;
1419 /* Check if it fits into this leaf */
1420 if (LeafKey
->Count
< CmpMaxIndexPerHblock
)
1422 /* Fill in the result and return the cell */
1423 *RootCell
= &IndexKey
->List
[SubKeyIndex
];
1427 /* No, it doesn't fit, check the next adjacent leaf */
1428 if (SubKeyIndex
< (IndexKey
->Count
- 1))
1430 /* Yes, there is space */
1431 LeafCell
= IndexKey
->List
[SubKeyIndex
+ 1];
1432 LeafKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
1434 /* Return an error in case of problems */
1435 if (!LeafKey
) return HCELL_NIL
;
1437 /* Check if it fits and break */
1438 if (LeafKey
->Count
< CmpMaxIndexPerHblock
)
1440 /* Fill in the result and return the cell */
1441 *RootCell
= &IndexKey
->List
[SubKeyIndex
+ 1];
1446 /* It didn't fit, so proceed to splitting */
1450 /* No, it's below, check the subkey index */
1451 if (SubKeyIndex
> 0)
1453 /* There should be space at the leaf one before that */
1454 LeafCell
= IndexKey
->List
[SubKeyIndex
- 1];
1455 LeafKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
1457 /* Return an error in case of problems */
1458 if (!LeafKey
) return HCELL_NIL
;
1460 /* Check if it fits and break */
1461 if (LeafKey
->Count
< CmpMaxIndexPerHblock
)
1463 /* Fill in the result and return the cell */
1464 *RootCell
= &IndexKey
->List
[SubKeyIndex
- 1];
1470 /* Use the first leaf, if possible */
1471 LeafCell
= IndexKey
->List
[0];
1472 LeafKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
1474 /* Return an error in case of problems */
1475 if (!LeafKey
) return HCELL_NIL
;
1477 /* Check if it fits and break */
1478 if (LeafKey
->Count
< CmpMaxIndexPerHblock
)
1480 /* Fill in the result and return the cell */
1481 *RootCell
= &IndexKey
->List
[0];
1486 /* It didn't fit into either, so proceed to splitting */
1490 /* We need to split */
1491 CurrentCell
= CmpSplitLeaf(Hive
,
1492 KeyNode
->SubKeyLists
[Type
],
1496 /* Return failure in case splitting failed */
1497 if (CurrentCell
== HCELL_NIL
) return CurrentCell
;
1499 /* Set the SubKeyLists value with the new key */
1500 KeyNode
->SubKeyLists
[Type
] = CurrentCell
;
1502 /* Get the new cell */
1503 IndexKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, KeyNode
->SubKeyLists
[Type
]);
1505 /* Return in case of failure */
1506 if (!IndexKey
) return HCELL_NIL
;
1508 /* Make sure the new key became index root */
1509 ASSERT(IndexKey
->Signature
== CM_KEY_INDEX_ROOT
);
1511 /* Now loop over with the new IndexKey value, which definately
1516 /* Shouldn't come here */
1522 CmpAddSubKey(IN PHHIVE Hive
,
1523 IN HCELL_INDEX Parent
,
1524 IN HCELL_INDEX Child
)
1526 PCM_KEY_NODE KeyNode
;
1527 PCM_KEY_INDEX Index
;
1528 PCM_KEY_FAST_INDEX OldIndex
;
1529 UNICODE_STRING Name
;
1530 HCELL_INDEX IndexCell
= HCELL_NIL
, CellToRelease
= HCELL_NIL
, LeafCell
;
1531 PHCELL_INDEX RootPointer
= NULL
;
1533 BOOLEAN IsCompressed
;
1536 /* Get the key node */
1537 KeyNode
= (PCM_KEY_NODE
)HvGetCell(Hive
, Child
);
1540 /* Shouldn't happen */
1545 /* Check if the name is compressed */
1546 if (KeyNode
->Flags
& KEY_COMP_NAME
)
1548 /* Remember for later */
1549 IsCompressed
= TRUE
;
1551 /* Create the compressed name and allocate it */
1552 Name
.Length
= CmpCompressedNameSize(KeyNode
->Name
, KeyNode
->NameLength
);
1553 Name
.MaximumLength
= Name
.Length
;
1554 Name
.Buffer
= Hive
->Allocate(Name
.Length
, TRUE
, TAG_CM
);
1557 /* Release the cell and fail */
1558 HvReleaseCell(Hive
, Child
);
1563 /* Copy the compressed name */
1564 CmpCopyCompressedName(Name
.Buffer
,
1567 KeyNode
->NameLength
);
1571 /* Remember for later */
1572 IsCompressed
= FALSE
;
1574 /* Build the unicode string */
1575 Name
.Length
= KeyNode
->NameLength
;
1576 Name
.MaximumLength
= KeyNode
->NameLength
;
1577 Name
.Buffer
= &KeyNode
->Name
[0];
1580 /* Release the cell */
1581 HvReleaseCell(Hive
, Child
);
1583 /* Get the parent node */
1584 KeyNode
= (PCM_KEY_NODE
)HvGetCell(Hive
, Parent
);
1591 /* Find out the type of the cell, and check if this is the first subkey */
1592 Type
= HvGetCellType(Child
);
1593 if (!KeyNode
->SubKeyCounts
[Type
])
1595 /* Allocate a fast leaf */
1596 IndexCell
= HvAllocateCell(Hive
, sizeof(CM_KEY_FAST_INDEX
), Type
, HCELL_NIL
);
1597 if (IndexCell
== HCELL_NIL
)
1603 /* Get the leaf cell */
1604 Index
= (PCM_KEY_INDEX
)HvGetCell(Hive
, IndexCell
);
1607 /* Shouldn't happen */
1611 /* Now check what kind of hive we're dealing with */
1612 if (Hive
->Version
>= 5)
1614 /* XP Hive: Use hash leaf */
1615 Index
->Signature
= CM_KEY_HASH_LEAF
;
1617 else if (Hive
->Version
>= 3)
1619 /* Windows 2000 and ReactOS: Use fast leaf */
1620 Index
->Signature
= CM_KEY_FAST_LEAF
;
1624 /* NT 4: Use index leaf */
1625 Index
->Signature
= CM_KEY_INDEX_LEAF
;
1628 /* Setup the index list */
1630 KeyNode
->SubKeyLists
[Type
] = IndexCell
;
1634 /* We already have an index, get it */
1635 Index
= (PCM_KEY_INDEX
)HvGetCell(Hive
, KeyNode
->SubKeyLists
[Type
]);
1642 /* Remember to release the cell later */
1643 CellToRelease
= KeyNode
->SubKeyLists
[Type
];
1645 /* Check if this is a fast leaf that's gotten too full */
1646 if ((Index
->Signature
== CM_KEY_FAST_LEAF
) &&
1647 (Index
->Count
>= CmpMaxFastIndexPerHblock
))
1649 DPRINT("Doing Fast->Slow Leaf conversion\n");
1651 /* Mark this cell as dirty */
1652 HvMarkCellDirty(Hive
, CellToRelease
, FALSE
);
1655 OldIndex
= (PCM_KEY_FAST_INDEX
)Index
;
1657 for (i
= 0; i
< OldIndex
->Count
; i
++)
1659 Index
->List
[i
] = OldIndex
->List
[i
].Cell
;
1662 /* Set the new type value */
1663 Index
->Signature
= CM_KEY_INDEX_LEAF
;
1665 else if (((Index
->Signature
== CM_KEY_INDEX_LEAF
) ||
1666 (Index
->Signature
== CM_KEY_HASH_LEAF
)) &&
1667 (Index
->Count
>= CmpMaxIndexPerHblock
))
1669 /* This is an old/hashed leaf that's gotten too large, root it */
1670 IndexCell
= HvAllocateCell(Hive
,
1671 sizeof(CM_KEY_INDEX
) +
1672 sizeof(HCELL_INDEX
),
1675 if (IndexCell
== HCELL_NIL
)
1681 /* Get the index cell */
1682 Index
= (PCM_KEY_INDEX
)HvGetCell(Hive
, IndexCell
);
1685 /* Shouldn't happen */
1689 /* Mark the index as a root, and set the index cell */
1690 Index
->Signature
= CM_KEY_INDEX_ROOT
;
1692 Index
->List
[0] = KeyNode
->SubKeyLists
[Type
];
1693 KeyNode
->SubKeyLists
[Type
] = IndexCell
;
1697 /* Now we can choose the leaf cell */
1698 LeafCell
= KeyNode
->SubKeyLists
[Type
];
1700 /* Check if we turned the index into a root */
1701 if (Index
->Signature
== CM_KEY_INDEX_ROOT
)
1703 DPRINT("Leaf->Root Index Conversion\n");
1705 /* Get the leaf where to add the new entry (the routine will do
1706 * the splitting if necessary)
1708 LeafCell
= CmpSelectLeaf(Hive
, KeyNode
, &Name
, Type
, &RootPointer
);
1709 if (LeafCell
== HCELL_NIL
)
1716 /* Add our leaf cell */
1717 LeafCell
= CmpAddToLeaf(Hive
, LeafCell
, Child
, &Name
);
1718 if (LeafCell
== HCELL_NIL
)
1724 /* Update the key counts */
1725 KeyNode
->SubKeyCounts
[Type
]++;
1727 /* Check if caller wants us to return the leaf */
1731 *RootPointer
= LeafCell
;
1735 /* Otherwise, mark it as the list index for the cell */
1736 KeyNode
->SubKeyLists
[Type
] = LeafCell
;
1739 /* If the name was compressed, free our copy */
1740 if (IsCompressed
) Hive
->Free(Name
.Buffer
, 0);
1742 /* Release all our cells */
1743 if (IndexCell
!= HCELL_NIL
) HvReleaseCell(Hive
, IndexCell
);
1744 if (CellToRelease
!= HCELL_NIL
) HvReleaseCell(Hive
, CellToRelease
);
1745 HvReleaseCell(Hive
, Parent
);
1751 CmpRemoveSubKey(IN PHHIVE Hive
,
1752 IN HCELL_INDEX ParentKey
,
1753 IN HCELL_INDEX TargetKey
)
1756 UNICODE_STRING SearchName
;
1757 BOOLEAN IsCompressed
;
1759 HCELL_INDEX RootCell
= HCELL_NIL
, LeafCell
, ChildCell
;
1760 PCM_KEY_INDEX Root
= NULL
, Leaf
;
1761 PCM_KEY_FAST_INDEX Child
;
1762 ULONG Storage
, RootIndex
= 0x80000000, LeafIndex
;
1763 BOOLEAN Result
= FALSE
;
1764 HCELL_INDEX CellToRelease1
= HCELL_NIL
, CellToRelease2
= HCELL_NIL
;
1766 /* Get the target key node */
1767 Node
= (PCM_KEY_NODE
)HvGetCell(Hive
, TargetKey
);
1768 if (!Node
) return FALSE
;
1770 /* Make sure it's dirty, then release it */
1771 ASSERT(HvIsCellDirty(Hive
, TargetKey
));
1772 HvReleaseCell(Hive
, TargetKey
);
1774 /* Check if the name is compressed */
1775 if (Node
->Flags
& KEY_COMP_NAME
)
1777 /* Remember for later */
1778 IsCompressed
= TRUE
;
1780 /* Build the search name */
1781 SearchName
.Length
= CmpCompressedNameSize(Node
->Name
,
1783 SearchName
.MaximumLength
= SearchName
.Length
;
1785 /* Do we need an extra bufer? */
1786 if (SearchName
.MaximumLength
> sizeof(Buffer
))
1789 SearchName
.Buffer
= CmpAllocate(SearchName
.Length
,
1792 if (!SearchName
.Buffer
) return FALSE
;
1796 /* Otherwise, use our local stack buffer */
1797 SearchName
.Buffer
= Buffer
;
1800 /* Copy the compressed name */
1801 CmpCopyCompressedName(SearchName
.Buffer
,
1802 SearchName
.MaximumLength
,
1808 /* It's not compressed, build the name directly from the node */
1809 IsCompressed
= FALSE
;
1810 SearchName
.Length
= Node
->NameLength
;
1811 SearchName
.MaximumLength
= Node
->NameLength
;
1812 SearchName
.Buffer
= Node
->Name
;
1815 /* Now get the parent node */
1816 Node
= (PCM_KEY_NODE
)HvGetCell(Hive
, ParentKey
);
1817 if (!Node
) goto Exit
;
1819 /* Make sure it's dirty, then release it */
1820 ASSERT(HvIsCellDirty(Hive
, ParentKey
));
1821 HvReleaseCell(Hive
, ParentKey
);
1823 /* Get the storage type and make sure it's not empty */
1824 Storage
= HvGetCellType(TargetKey
);
1825 ASSERT(Node
->SubKeyCounts
[Storage
] != 0);
1826 //ASSERT(HvIsCellAllocated(Hive, Node->SubKeyLists[Storage]));
1828 /* Get the leaf cell now */
1829 LeafCell
= Node
->SubKeyLists
[Storage
];
1830 Leaf
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
1831 if (!Leaf
) goto Exit
;
1833 /* Remember to release it later */
1834 CellToRelease1
= LeafCell
;
1836 /* Check if the leaf is a root */
1837 if (Leaf
->Signature
== CM_KEY_INDEX_ROOT
)
1839 /* Find the child inside the root */
1840 RootIndex
= CmpFindSubKeyInRoot(Hive
, Leaf
, &SearchName
, &ChildCell
);
1841 if (RootIndex
& 0x80000000) goto Exit
;
1842 ASSERT(ChildCell
!= FALSE
);
1844 /* The root cell is now this leaf */
1846 RootCell
= LeafCell
;
1848 /* And the new leaf is now this child */
1849 LeafCell
= ChildCell
;
1850 Leaf
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
1851 if (!Leaf
) goto Exit
;
1853 /* Remember to release it later */
1854 CellToRelease2
= LeafCell
;
1857 /* Make sure the leaf is valid */
1858 ASSERT((Leaf
->Signature
== CM_KEY_INDEX_LEAF
) ||
1859 (Leaf
->Signature
== CM_KEY_FAST_LEAF
) ||
1860 (Leaf
->Signature
== CM_KEY_HASH_LEAF
));
1862 /* Now get the child in the leaf */
1863 LeafIndex
= CmpFindSubKeyInLeaf(Hive
, Leaf
, &SearchName
, &ChildCell
);
1864 if (LeafIndex
& 0x80000000) goto Exit
;
1865 ASSERT(ChildCell
!= HCELL_NIL
);
1867 /* Decrement key counts and check if this was the last leaf entry */
1868 Node
->SubKeyCounts
[Storage
]--;
1869 if (!(--Leaf
->Count
))
1872 HvFreeCell(Hive
, LeafCell
);
1874 /* Check if we were inside a root */
1877 /* Decrease the root count too, since the leaf is going away */
1878 if (!(--Root
->Count
))
1880 /* The root is gone too,n ow */
1881 HvFreeCell(Hive
, RootCell
);
1882 Node
->SubKeyLists
[Storage
] = HCELL_NIL
;
1884 else if (RootIndex
< Root
->Count
)
1886 /* Bring everything up by one */
1887 RtlMoveMemory(&Root
->List
[RootIndex
],
1888 &Root
->List
[RootIndex
+ 1],
1889 (Root
->Count
- RootIndex
) * sizeof(HCELL_INDEX
));
1894 /* Otherwise, just clear the cell */
1895 Node
->SubKeyLists
[Storage
] = HCELL_NIL
;
1898 else if (LeafIndex
< Leaf
->Count
)
1900 /* Was the leaf a normal index? */
1901 if (Leaf
->Signature
== CM_KEY_INDEX_LEAF
)
1903 /* Bring everything up by one */
1904 RtlMoveMemory(&Leaf
->List
[LeafIndex
],
1905 &Leaf
->List
[LeafIndex
+ 1],
1906 (Leaf
->Count
- LeafIndex
) * sizeof(HCELL_INDEX
));
1910 /* This is a fast index, bring everything up by one */
1911 Child
= (PCM_KEY_FAST_INDEX
)Leaf
;
1912 RtlMoveMemory(&Child
->List
[LeafIndex
],
1913 &Child
->List
[LeafIndex
+1],
1914 (Child
->Count
- LeafIndex
) * sizeof(CM_INDEX
));
1918 /* If we got here, now we're done */
1922 /* Release any cells we may have been holding */
1923 if (CellToRelease1
!= HCELL_NIL
) HvReleaseCell(Hive
, CellToRelease1
);
1924 if (CellToRelease2
!= HCELL_NIL
) HvReleaseCell(Hive
, CellToRelease2
);
1926 /* Check if the name was compressed and not inside our local buffer */
1927 if ((IsCompressed
) && (SearchName
.MaximumLength
> sizeof(Buffer
)))
1929 /* Free the buffer we allocated */
1930 CmpFree(SearchName
.Buffer
, 0);
1933 /* Return the result */