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
)
736 /* Lookup the name in the root */
737 Found
= CmpFindSubKeyInRoot(Hive
,
742 /* Release the previous cell */
743 ASSERT(CellToRelease
!= HCELL_NIL
);
744 HvReleaseCell(Hive
, CellToRelease
);
746 /* Make sure we found something valid */
747 if (Found
& 0x80000000) break;
749 /* Get the new Index Root and set the new cell to be released */
750 if (SubKey
== HCELL_NIL
) continue;
751 CellToRelease
= SubKey
;
752 IndexRoot
= (PCM_KEY_INDEX
)HvGetCell(Hive
, SubKey
);
755 /* Make sure the signature is what we expect it to be */
756 ASSERT((IndexRoot
->Signature
== CM_KEY_INDEX_LEAF
) ||
757 (IndexRoot
->Signature
== CM_KEY_FAST_LEAF
) ||
758 (IndexRoot
->Signature
== CM_KEY_HASH_LEAF
));
760 /* Check if this isn't a hashed leaf */
761 if (IndexRoot
->Signature
!= CM_KEY_HASH_LEAF
)
763 /* Find the subkey in the leaf */
764 Found
= CmpFindSubKeyInLeaf(Hive
,
769 /* Release the previous cell */
770 ASSERT(CellToRelease
!= HCELL_NIL
);
771 HvReleaseCell(Hive
, CellToRelease
);
773 /* Make sure we found a valid index */
774 if (Found
& 0x80000000) break;
778 /* Find the subkey in the hash */
779 SubKey
= CmpFindSubKeyByHash(Hive
,
780 (PCM_KEY_FAST_INDEX
)IndexRoot
,
783 /* Release the previous cell */
784 ASSERT(CellToRelease
!= HCELL_NIL
);
785 HvReleaseCell(Hive
, CellToRelease
);
788 /* Make sure we got a valid subkey and return it */
789 if (SubKey
!= HCELL_NIL
) return SubKey
;
793 /* If we got here, then we failed */
799 CmpMarkIndexDirty(IN PHHIVE Hive
,
800 IN HCELL_INDEX ParentKey
,
801 IN HCELL_INDEX TargetKey
)
804 UNICODE_STRING SearchName
;
805 BOOLEAN IsCompressed
;
808 HCELL_INDEX IndexCell
, Child
= HCELL_NIL
, CellToRelease
= HCELL_NIL
;
810 /* Get the target key node */
811 Node
= (PCM_KEY_NODE
)HvGetCell(Hive
, TargetKey
);
812 if (!Node
) return FALSE
;
814 /* Check if it's compressed */
815 if (Node
->Flags
& KEY_COMP_NAME
)
817 /* Remember this for later */
820 /* Build the search name */
821 SearchName
.Length
= CmpCompressedNameSize(Node
->Name
,
823 SearchName
.MaximumLength
= SearchName
.Length
;
824 SearchName
.Buffer
= CmpAllocate(SearchName
.Length
,
827 if (!SearchName
.Buffer
)
830 HvReleaseCell(Hive
, TargetKey
);
835 CmpCopyCompressedName(SearchName
.Buffer
,
836 SearchName
.MaximumLength
,
842 /* Name isn't compressed, build it directly from the node */
843 IsCompressed
= FALSE
;
844 SearchName
.Length
= Node
->NameLength
;
845 SearchName
.MaximumLength
= Node
->NameLength
;
846 SearchName
.Buffer
= Node
->Name
;
849 /* We can release the target key now */
850 HvReleaseCell(Hive
, TargetKey
);
852 /* Now get the parent key node */
853 Node
= (PCM_KEY_NODE
)HvGetCell(Hive
, ParentKey
);
854 if (!Node
) goto Quickie
;
856 /* Loop all hive storage */
857 for (i
= 0; i
< Hive
->StorageTypeCount
; i
++)
859 /* Check if any subkeys are in this index */
860 if (Node
->SubKeyCounts
[i
])
862 /* Get the cell index */
863 //ASSERT(HvIsCellAllocated(Hive, Node->SubKeyLists[i]));
864 IndexCell
= Node
->SubKeyLists
[i
];
866 /* Check if we had anything to release from before */
867 if (CellToRelease
!= HCELL_NIL
)
870 HvReleaseCell(Hive
, CellToRelease
);
871 CellToRelease
= HCELL_NIL
;
874 /* Get the key index for the cell */
875 Index
= (PCM_KEY_INDEX
)HvGetCell(Hive
, IndexCell
);
876 if (!Index
) goto Quickie
;
878 /* Release it at the next iteration or below */
879 CellToRelease
= IndexCell
;
881 /* Check if this is a root */
882 if (Index
->Signature
== CM_KEY_INDEX_ROOT
)
884 /* Get the child inside the root */
885 Result
= CmpFindSubKeyInRoot(Hive
, Index
, &SearchName
, &Child
);
886 if (Result
& 0x80000000) goto Quickie
;
887 if (Child
== HCELL_NIL
) continue;
889 /* We found it, mark the cell dirty */
890 HvMarkCellDirty(Hive
, IndexCell
, FALSE
);
892 /* Check if we had anything to release from before */
893 if (CellToRelease
!= HCELL_NIL
)
896 HvReleaseCell(Hive
, CellToRelease
);
897 CellToRelease
= HCELL_NIL
;
900 /* Now this child is the index, get the actual key index */
902 Index
= (PCM_KEY_INDEX
)HvGetCell(Hive
, Child
);
903 if (!Index
) goto Quickie
;
905 /* Release it later */
906 CellToRelease
= Child
;
909 /* Make sure this is a valid index */
910 ASSERT((Index
->Signature
== CM_KEY_INDEX_LEAF
) ||
911 (Index
->Signature
== CM_KEY_FAST_LEAF
) ||
912 (Index
->Signature
== CM_KEY_HASH_LEAF
));
914 /* Find the child in the leaf */
915 Result
= CmpFindSubKeyInLeaf(Hive
, Index
, &SearchName
, &Child
);
916 if (Result
& 0x80000000) goto Quickie
;
917 if (Child
!= HCELL_NIL
)
919 /* We found it, free the name now */
920 if (IsCompressed
) CmpFree(SearchName
.Buffer
, 0);
922 /* Release the parent key */
923 HvReleaseCell(Hive
, ParentKey
);
925 /* Check if we had a left over cell to release */
926 if (CellToRelease
!= HCELL_NIL
)
929 HvReleaseCell(Hive
, CellToRelease
);
932 /* And mark the index cell dirty */
933 HvMarkCellDirty(Hive
, IndexCell
, FALSE
);
940 /* Release any cells that we still hold */
941 if (Node
) HvReleaseCell(Hive
, ParentKey
);
942 if (CellToRelease
!= HCELL_NIL
) HvReleaseCell(Hive
, CellToRelease
);
944 /* Free the search name and return failure */
945 if (IsCompressed
) CmpFree(SearchName
.Buffer
, 0);
951 CmpAddToLeaf(IN PHHIVE Hive
,
952 IN HCELL_INDEX LeafCell
,
953 IN HCELL_INDEX NewKey
,
954 IN PUNICODE_STRING Name
)
957 PCM_KEY_FAST_INDEX FastLeaf
;
958 ULONG Size
, OldSize
, EntrySize
, i
, j
;
959 HCELL_INDEX NewCell
, Child
;
962 /* Mark the leaf dirty */
963 HvMarkCellDirty(Hive
, LeafCell
, FALSE
);
965 /* Get the leaf cell */
966 Leaf
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
969 /* Shouldn't happen */
975 HvReleaseCell(Hive
, LeafCell
);
977 /* Check if this is an index leaf */
978 if (Leaf
->Signature
== CM_KEY_INDEX_LEAF
)
980 /* This is an old-style leaf */
982 EntrySize
= sizeof(HCELL_INDEX
);
987 ASSERT((Leaf
->Signature
== CM_KEY_FAST_LEAF
) ||
988 (Leaf
->Signature
== CM_KEY_HASH_LEAF
));
990 /* This is a new-style optimized fast (or hash) leaf */
991 FastLeaf
= (PCM_KEY_FAST_INDEX
)Leaf
;
992 EntrySize
= sizeof(CM_INDEX
);
995 /* Get the current size of the leaf */
996 OldSize
= HvGetCellSize(Hive
, Leaf
);
998 /* Calculate the size of the free entries */
1000 Size
-= EntrySize
* Leaf
->Count
+ FIELD_OFFSET(CM_KEY_INDEX
, List
);
1002 /* Assume we'll re-use the same leaf */
1005 /* Check if we're out of space */
1006 if ((Size
/ EntrySize
) < 1)
1008 /* Grow the leaf by 1.5x, making sure we can at least fit this entry */
1009 Size
= OldSize
+ OldSize
/ 2;
1010 if (Size
< (OldSize
+ EntrySize
)) Size
= OldSize
+ EntrySize
;
1012 /* Re-allocate the leaf */
1013 NewCell
= HvReallocateCell(Hive
, LeafCell
, Size
);
1014 if (NewCell
== HCELL_NIL
) return HCELL_NIL
;
1016 /* Get the leaf cell */
1017 Leaf
= (PCM_KEY_INDEX
)HvGetCell(Hive
, NewCell
);
1020 /* This shouldn't happen */
1025 /* Release the cell */
1026 HvReleaseCell(Hive
, NewCell
);
1028 /* Update the fast leaf pointer if we had one */
1029 if (FastLeaf
) FastLeaf
= (PCM_KEY_FAST_INDEX
)Leaf
;
1032 /* Find the insertion point for our entry */
1033 i
= CmpFindSubKeyInLeaf(Hive
, Leaf
, Name
, &Child
);
1034 if (i
& 0x80000000) return HCELL_NIL
;
1035 ASSERT(Child
== HCELL_NIL
);
1037 /* Check if we're not last */
1038 if (i
!= Leaf
->Count
)
1040 /* Find out where we should go */
1041 Result
= CmpCompareInIndex(Hive
,
1046 if (Result
== 2) return HCELL_NIL
;
1047 ASSERT(Result
!= 0);
1049 /* Check if we come after */
1052 /* We do, insert us after the key */
1053 ASSERT(Result
== 1);
1057 /* Check if we're still not last */
1058 if (i
!= Leaf
->Count
)
1060 /* Check if we had a fast leaf or not */
1063 /* Copy the fast indexes */
1064 RtlMoveMemory(&FastLeaf
->List
[i
+ 1],
1066 (FastLeaf
->Count
- i
) * sizeof(CM_INDEX
));
1070 /* Copy the indexes themselves */
1071 RtlMoveMemory(&Leaf
->List
[i
+ 1],
1073 (Leaf
->Count
- i
) * sizeof(HCELL_INDEX
));
1078 /* Check if this is a new-style leaf */
1082 FastLeaf
->List
[i
].Cell
= NewKey
;
1084 /* Check if this is a hash leaf */
1085 if( FastLeaf
->Signature
== CM_KEY_HASH_LEAF
)
1087 /* Set our hash key */
1088 FastLeaf
->List
[i
].HashKey
= CmpComputeHashKey(0, Name
, FALSE
);
1092 /* First, clear the name */
1093 FastLeaf
->List
[i
].NameHint
[0] = 0;
1094 FastLeaf
->List
[i
].NameHint
[1] = 0;
1095 FastLeaf
->List
[i
].NameHint
[2] = 0;
1096 FastLeaf
->List
[i
].NameHint
[3] = 0;
1098 /* Now, figure out if we can fit */
1099 if (Name
->Length
/ sizeof(WCHAR
) < 4)
1101 /* We can fit, use our length */
1102 j
= Name
->Length
/ sizeof(WCHAR
);
1106 /* We can't, use a maximum of 4 */
1110 /* Now fill out the name hint */
1113 /* Look for invalid characters and break out if we found one */
1114 if ((USHORT
)Name
->Buffer
[j
- 1] > (UCHAR
)-1) break;
1116 /* Otherwise, copy the a character */
1117 FastLeaf
->List
[i
].NameHint
[j
- 1] = (UCHAR
)Name
->Buffer
[j
- 1];
1123 /* This is an old-style leaf, just set our index directly */
1124 Leaf
->List
[i
] = NewKey
;
1127 /* Update the leaf count and return the new cell */
1134 CmpSplitLeaf(IN PHHIVE Hive
,
1135 IN HCELL_INDEX RootCell
,
1136 IN ULONG RootSelect
,
1137 IN HSTORAGE_TYPE Type
)
1139 PCM_KEY_INDEX IndexKey
, LeafKey
, NewKey
;
1140 PCM_KEY_FAST_INDEX FastLeaf
;
1141 HCELL_INDEX LeafCell
, NewCell
;
1142 ULONG FirstHalf
, LastHalf
;
1143 ULONG EntrySize
, TotalSize
;
1146 IndexKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, RootCell
);
1148 /* Check if we've got valid IndexKey */
1149 if (!IndexKey
) return HCELL_NIL
;
1151 /* Get the leaf cell and key */
1152 LeafCell
= IndexKey
->List
[RootSelect
];
1153 LeafKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
1155 /* Check if we've got valid LeafKey */
1156 if (!LeafKey
) return HCELL_NIL
;
1158 /* We are going to divide this leaf into two halves */
1159 FirstHalf
= (LeafKey
->Count
/ 2);
1160 LastHalf
= LeafKey
->Count
- FirstHalf
;
1162 /* Now check what kind of hive we're dealing with,
1163 * and compute entry size
1165 if (Hive
->Version
>= 5)
1167 /* XP Hive: Use hash leaf */
1168 ASSERT(LeafKey
->Signature
== CM_KEY_HASH_LEAF
);
1169 EntrySize
= sizeof(CM_INDEX
);
1173 /* Use index leaf */
1174 ASSERT(LeafKey
->Signature
== CM_KEY_INDEX_LEAF
);
1175 EntrySize
= sizeof(HCELL_INDEX
);
1178 /* Compute the total size */
1179 TotalSize
= (EntrySize
* LastHalf
) + FIELD_OFFSET(CM_KEY_INDEX
, List
) + 1;
1181 /* Mark the leaf cell dirty */
1182 HvMarkCellDirty(Hive
, LeafCell
, FALSE
);
1184 /* Make sure its type is the same */
1185 ASSERT(HvGetCellType(LeafCell
) == Type
);
1187 /* Allocate the cell, fail in case of error */
1188 NewCell
= HvAllocateCell(Hive
, TotalSize
, Type
, LeafCell
);
1189 if (NewCell
== HCELL_NIL
) return NewCell
;
1192 NewKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, NewCell
);
1195 /* Free the cell and exit - should not happen! */
1197 HvFreeCell(Hive
, NewCell
);
1201 /* Release the newly created cell */
1202 HvReleaseCell(Hive
, NewCell
);
1204 /* Set its signature according to the version of the hive */
1205 if (Hive
->Version
>= 5)
1207 /* XP Hive: Use hash leaf signature */
1208 NewKey
->Signature
= CM_KEY_HASH_LEAF
;
1212 /* Use index leaf signature */
1213 NewKey
->Signature
= CM_KEY_INDEX_LEAF
;
1216 /* Calculate the size of the free entries in the root key */
1217 TotalSize
= HvGetCellSize(Hive
, IndexKey
) -
1218 (IndexKey
->Count
* sizeof(HCELL_INDEX
)) -
1219 FIELD_OFFSET(CM_KEY_INDEX
, List
);
1221 /* Check if we're out of space */
1222 if (TotalSize
/ sizeof(HCELL_INDEX
) < 1)
1224 /* Grow the leaf by one more entry */
1225 TotalSize
= HvGetCellSize(Hive
, IndexKey
) + sizeof(HCELL_INDEX
);
1227 /* Re-allocate the root */
1228 RootCell
= HvReallocateCell(Hive
, RootCell
, TotalSize
);
1229 if (RootCell
== HCELL_NIL
)
1231 /* Free the cell and exit */
1232 HvFreeCell(Hive
, NewCell
);
1236 /* Get the leaf cell */
1237 IndexKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, RootCell
);
1240 /* This shouldn't happen */
1246 /* Splitting is done, now we need to copy the contents,
1247 * according to the hive version
1249 if (Hive
->Version
>= 5)
1251 /* Copy the fast indexes */
1252 FastLeaf
= (PCM_KEY_FAST_INDEX
)LeafKey
;
1253 RtlMoveMemory(&NewKey
->List
[0],
1254 &FastLeaf
->List
[FirstHalf
],
1255 LastHalf
* EntrySize
);
1259 /* Copy the indexes themselves */
1260 RtlMoveMemory(&NewKey
->List
[0],
1261 &LeafKey
->List
[FirstHalf
],
1262 LastHalf
* EntrySize
);
1265 /* Shift the data inside the root key */
1266 if (RootSelect
< (IndexKey
->Count
- 1))
1268 RtlMoveMemory(&IndexKey
->List
[RootSelect
+ 2],
1269 &IndexKey
->List
[RootSelect
+ 1],
1271 (RootSelect
+ 1) * sizeof(HCELL_INDEX
));
1274 /* Make sure both old and new computed counts are valid */
1275 ASSERT(FirstHalf
!= 0);
1276 ASSERT(LastHalf
!= 0);
1278 /* Update the count value of old and new keys */
1279 LeafKey
->Count
= FirstHalf
;
1280 NewKey
->Count
= LastHalf
;
1282 /* Increase the count value of the root key */
1285 /* Set the new cell in root's list */
1286 IndexKey
->List
[RootSelect
+ 1] = NewCell
;
1288 /* Return the root cell */
1294 CmpSelectLeaf(IN PHHIVE Hive
,
1295 IN PCM_KEY_NODE KeyNode
,
1296 IN PUNICODE_STRING Name
,
1297 IN HSTORAGE_TYPE Type
,
1298 IN PHCELL_INDEX
*RootCell
)
1300 PCM_KEY_INDEX IndexKey
, LeafKey
;
1301 PCM_KEY_FAST_INDEX FastLeaf
;
1302 HCELL_INDEX LeafCell
, CurrentCell
;
1306 /* Mark it as dirty */
1307 HvMarkCellDirty(Hive
, KeyNode
->SubKeyLists
[Type
], FALSE
);
1310 IndexKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, KeyNode
->SubKeyLists
[Type
]);
1312 /* Check if we've got a valid key */
1315 /* Should not happen! */
1316 ASSERTMSG("IndexKey = NULL!, it should not happen!\n", FALSE
);
1321 ASSERT(IndexKey
->Signature
== CM_KEY_INDEX_ROOT
);
1326 SubKeyIndex
= CmpFindSubKeyInRoot(Hive
, IndexKey
, Name
, &LeafCell
);
1328 /* Make sure we found something valid */
1329 if (SubKeyIndex
& 0x80000000) return HCELL_NIL
;
1331 /* Try to fit it into the LeafCell, if it was found */
1332 if (LeafCell
!= HCELL_NIL
)
1334 /* Get the leaf key */
1335 LeafKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
1337 /* Check for failure */
1338 if (!LeafKey
) return HCELL_NIL
;
1340 /* Check if it fits into this leaf and break */
1341 if (LeafKey
->Count
< CmpMaxIndexPerHblock
)
1343 /* Fill in the result and return it */
1344 *RootCell
= &IndexKey
->List
[SubKeyIndex
];
1350 /* Get the leaf cell at the very end */
1351 LeafCell
= IndexKey
->List
[SubKeyIndex
];
1352 LeafKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
1354 /* Return an error in case of problems */
1355 if (!LeafKey
) return HCELL_NIL
;
1357 /* Choose the cell to search from depending on the key type */
1358 if ((LeafKey
->Signature
== CM_KEY_FAST_LEAF
) ||
1359 (LeafKey
->Signature
== CM_KEY_HASH_LEAF
))
1361 FastLeaf
= (PCM_KEY_FAST_INDEX
)LeafKey
;
1362 CurrentCell
= FastLeaf
->List
[0].Cell
;
1366 /* Make sure it's an index leaf */
1367 ASSERT(LeafKey
->Signature
== CM_KEY_INDEX_LEAF
);
1368 CurrentCell
= LeafKey
->List
[0];
1371 /* Do a name compare */
1372 Result
= CmpDoCompareKeyName(Hive
, Name
, CurrentCell
);
1374 /* Check for failure */
1375 if (Result
== 2) return HCELL_NIL
;
1377 /* Names can't be equal, ensure that */
1378 ASSERT(Result
!= 0);
1380 /* Check if it's above */
1383 /* Get the first cell in the index */
1384 LeafCell
= IndexKey
->List
[0];
1385 LeafKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
1387 /* Return an error in case of problems */
1388 if (!LeafKey
) return HCELL_NIL
;
1390 /* Check if it fits into this leaf and break */
1391 if (LeafKey
->Count
< CmpMaxIndexPerHblock
)
1393 /* Fill in the result and return the cell */
1394 *RootCell
= &IndexKey
->List
[SubKeyIndex
+ 1];
1398 /* No, it doesn't fit, check the other leaf */
1399 if (SubKeyIndex
< (IndexKey
->Count
- 1))
1401 /* Yes, there is space */
1402 LeafCell
= IndexKey
->List
[SubKeyIndex
+ 1];
1403 LeafKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
1405 /* Return an error in case of problems */
1406 if (!LeafKey
) return HCELL_NIL
;
1408 /* Check if it fits and break */
1409 if (LeafKey
->Count
< CmpMaxIndexPerHblock
)
1411 /* Fill in the result and return the cell */
1412 *RootCell
= &IndexKey
->List
[SubKeyIndex
+ 1];
1419 /* No, it's below, check the subkey index */
1420 if (SubKeyIndex
> 0)
1422 /* There should be space at the leaf one before that */
1423 LeafCell
= IndexKey
->List
[SubKeyIndex
- 1];
1424 LeafKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
1426 /* Return an error in case of problems */
1427 if (!LeafKey
) return HCELL_NIL
;
1429 /* Check if it fits and break */
1430 if (LeafKey
->Count
< CmpMaxIndexPerHblock
)
1432 /* Decrement the subkey index */
1435 /* Fill in the result and return the cell */
1436 *RootCell
= &IndexKey
->List
[SubKeyIndex
];
1442 /* Use the first leaf, if possible */
1443 LeafCell
= IndexKey
->List
[0];
1444 LeafKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
1446 /* Return an error in case of problems */
1447 if (!LeafKey
) return HCELL_NIL
;
1449 /* Check if it fits and break */
1450 if (LeafKey
->Count
< CmpMaxIndexPerHblock
)
1452 /* Fill in the result and return the cell */
1453 *RootCell
= &IndexKey
->List
[0];
1458 /* It didn't fit into either, so proceed to splitting */
1462 /* We need to split */
1463 CurrentCell
= CmpSplitLeaf(Hive
,
1464 KeyNode
->SubKeyLists
[Type
],
1468 /* Return failure in case splitting failed */
1469 if (CurrentCell
== HCELL_NIL
) return CurrentCell
;
1471 /* Set the SubKeyLists value with the new key */
1472 KeyNode
->SubKeyLists
[Type
] = CurrentCell
;
1474 /* Get the new cell */
1475 IndexKey
= (PCM_KEY_INDEX
)HvGetCell(Hive
, KeyNode
->SubKeyLists
[Type
]);
1477 /* Return in case of failure */
1478 if (!IndexKey
) return HCELL_NIL
;
1480 /* Make sure the new key became index root */
1481 ASSERT(IndexKey
->Signature
== CM_KEY_INDEX_ROOT
);
1483 /* Now loop over with the new IndexKey value, which definately
1488 /* Shouldn't come here */
1494 CmpAddSubKey(IN PHHIVE Hive
,
1495 IN HCELL_INDEX Parent
,
1496 IN HCELL_INDEX Child
)
1498 PCM_KEY_NODE KeyNode
;
1499 PCM_KEY_INDEX Index
;
1500 PCM_KEY_FAST_INDEX OldIndex
;
1501 UNICODE_STRING Name
;
1502 HCELL_INDEX IndexCell
= HCELL_NIL
, CellToRelease
= HCELL_NIL
, LeafCell
;
1503 PHCELL_INDEX RootPointer
= NULL
;
1505 BOOLEAN IsCompressed
;
1508 /* Get the key node */
1509 KeyNode
= (PCM_KEY_NODE
)HvGetCell(Hive
, Child
);
1512 /* Shouldn't happen */
1517 /* Check if the name is compressed */
1518 if (KeyNode
->Flags
& KEY_COMP_NAME
)
1520 /* Remember for later */
1521 IsCompressed
= TRUE
;
1523 /* Create the compressed name and allocate it */
1524 Name
.Length
= CmpCompressedNameSize(KeyNode
->Name
, KeyNode
->NameLength
);
1525 Name
.MaximumLength
= Name
.Length
;
1526 Name
.Buffer
= Hive
->Allocate(Name
.Length
, TRUE
, TAG_CM
);
1529 /* Release the cell and fail */
1530 HvReleaseCell(Hive
, Child
);
1535 /* Copy the compressed name */
1536 CmpCopyCompressedName(Name
.Buffer
,
1539 KeyNode
->NameLength
);
1543 /* Remember for later */
1544 IsCompressed
= FALSE
;
1546 /* Build the unicode string */
1547 Name
.Length
= KeyNode
->NameLength
;
1548 Name
.MaximumLength
= KeyNode
->NameLength
;
1549 Name
.Buffer
= &KeyNode
->Name
[0];
1552 /* Release the cell */
1553 HvReleaseCell(Hive
, Child
);
1555 /* Get the parent node */
1556 KeyNode
= (PCM_KEY_NODE
)HvGetCell(Hive
, Parent
);
1563 /* Find out the type of the cell, and check if this is the first subkey */
1564 Type
= HvGetCellType(Child
);
1565 if (!KeyNode
->SubKeyCounts
[Type
])
1567 /* Allocate a fast leaf */
1568 IndexCell
= HvAllocateCell(Hive
, sizeof(CM_KEY_FAST_INDEX
), Type
, HCELL_NIL
);
1569 if (IndexCell
== HCELL_NIL
)
1575 /* Get the leaf cell */
1576 Index
= (PCM_KEY_INDEX
)HvGetCell(Hive
, IndexCell
);
1579 /* Shouldn't happen */
1583 /* Now check what kind of hive we're dealing with */
1584 if (Hive
->Version
>= 5)
1586 /* XP Hive: Use hash leaf */
1587 Index
->Signature
= CM_KEY_HASH_LEAF
;
1589 else if (Hive
->Version
>= 3)
1591 /* Windows 2000 and ReactOS: Use fast leaf */
1592 Index
->Signature
= CM_KEY_FAST_LEAF
;
1596 /* NT 4: Use index leaf */
1597 Index
->Signature
= CM_KEY_INDEX_LEAF
;
1600 /* Setup the index list */
1602 KeyNode
->SubKeyLists
[Type
] = IndexCell
;
1606 /* We already have an index, get it */
1607 Index
= (PCM_KEY_INDEX
)HvGetCell(Hive
, KeyNode
->SubKeyLists
[Type
]);
1614 /* Remember to release the cell later */
1615 CellToRelease
= KeyNode
->SubKeyLists
[Type
];
1617 /* Check if this is a fast leaf that's gotten too full */
1618 if ((Index
->Signature
== CM_KEY_FAST_LEAF
) &&
1619 (Index
->Count
>= CmpMaxFastIndexPerHblock
))
1621 DPRINT("Doing Fast->Slow Leaf conversion\n");
1623 /* Mark this cell as dirty */
1624 HvMarkCellDirty(Hive
, CellToRelease
, FALSE
);
1627 OldIndex
= (PCM_KEY_FAST_INDEX
)Index
;
1629 for (i
= 0; i
< OldIndex
->Count
; i
++)
1631 Index
->List
[i
] = OldIndex
->List
[i
].Cell
;
1634 /* Set the new type value */
1635 Index
->Signature
= CM_KEY_INDEX_LEAF
;
1637 else if (((Index
->Signature
== CM_KEY_INDEX_LEAF
) ||
1638 (Index
->Signature
== CM_KEY_HASH_LEAF
)) &&
1639 (Index
->Count
>= CmpMaxIndexPerHblock
))
1641 /* This is an old/hashed leaf that's gotten too large, root it */
1642 IndexCell
= HvAllocateCell(Hive
,
1643 sizeof(CM_KEY_INDEX
) +
1644 sizeof(HCELL_INDEX
),
1647 if (IndexCell
== HCELL_NIL
)
1653 /* Get the index cell */
1654 Index
= (PCM_KEY_INDEX
)HvGetCell(Hive
, IndexCell
);
1657 /* Shouldn't happen */
1661 /* Mark the index as a root, and set the index cell */
1662 Index
->Signature
= CM_KEY_INDEX_ROOT
;
1664 Index
->List
[0] = KeyNode
->SubKeyLists
[Type
];
1665 KeyNode
->SubKeyLists
[Type
] = IndexCell
;
1669 /* Now we can choose the leaf cell */
1670 LeafCell
= KeyNode
->SubKeyLists
[Type
];
1672 /* Check if we turned the index into a root */
1673 if (Index
->Signature
== CM_KEY_INDEX_ROOT
)
1675 DPRINT("Leaf->Root Index Conversion\n");
1677 /* Get the leaf where to add the new entry (the routine will do
1678 * the splitting if necessary)
1680 LeafCell
= CmpSelectLeaf(Hive
, KeyNode
, &Name
, Type
, &RootPointer
);
1681 if (LeafCell
== HCELL_NIL
)
1688 /* Add our leaf cell */
1689 LeafCell
= CmpAddToLeaf(Hive
, LeafCell
, Child
, &Name
);
1690 if (LeafCell
== HCELL_NIL
)
1696 /* Update the key counts */
1697 KeyNode
->SubKeyCounts
[Type
]++;
1699 /* Check if caller wants us to return the leaf */
1703 *RootPointer
= LeafCell
;
1707 /* Otherwise, mark it as the list index for the cell */
1708 KeyNode
->SubKeyLists
[Type
] = LeafCell
;
1711 /* If the name was compressed, free our copy */
1712 if (IsCompressed
) Hive
->Free(Name
.Buffer
, 0);
1714 /* Release all our cells */
1715 if (IndexCell
!= HCELL_NIL
) HvReleaseCell(Hive
, IndexCell
);
1716 if (CellToRelease
!= HCELL_NIL
) HvReleaseCell(Hive
, CellToRelease
);
1717 HvReleaseCell(Hive
, Parent
);
1723 CmpRemoveSubKey(IN PHHIVE Hive
,
1724 IN HCELL_INDEX ParentKey
,
1725 IN HCELL_INDEX TargetKey
)
1728 UNICODE_STRING SearchName
;
1729 BOOLEAN IsCompressed
;
1731 HCELL_INDEX RootCell
= HCELL_NIL
, LeafCell
, ChildCell
;
1732 PCM_KEY_INDEX Root
= NULL
, Leaf
;
1733 PCM_KEY_FAST_INDEX Child
;
1734 ULONG Storage
, RootIndex
= 0x80000000, LeafIndex
;
1735 BOOLEAN Result
= FALSE
;
1736 HCELL_INDEX CellToRelease1
= HCELL_NIL
, CellToRelease2
= HCELL_NIL
;
1738 /* Get the target key node */
1739 Node
= (PCM_KEY_NODE
)HvGetCell(Hive
, TargetKey
);
1740 if (!Node
) return FALSE
;
1742 /* Make sure it's dirty, then release it */
1743 ASSERT(HvIsCellDirty(Hive
, TargetKey
));
1744 HvReleaseCell(Hive
, TargetKey
);
1746 /* Check if the name is compressed */
1747 if (Node
->Flags
& KEY_COMP_NAME
)
1749 /* Remember for later */
1750 IsCompressed
= TRUE
;
1752 /* Build the search name */
1753 SearchName
.Length
= CmpCompressedNameSize(Node
->Name
,
1755 SearchName
.MaximumLength
= SearchName
.Length
;
1757 /* Do we need an extra bufer? */
1758 if (SearchName
.MaximumLength
> sizeof(Buffer
))
1761 SearchName
.Buffer
= CmpAllocate(SearchName
.Length
,
1764 if (!SearchName
.Buffer
) return FALSE
;
1768 /* Otherwise, use our local stack buffer */
1769 SearchName
.Buffer
= Buffer
;
1772 /* Copy the compressed name */
1773 CmpCopyCompressedName(SearchName
.Buffer
,
1774 SearchName
.MaximumLength
,
1780 /* It's not compressed, build the name directly from the node */
1781 IsCompressed
= FALSE
;
1782 SearchName
.Length
= Node
->NameLength
;
1783 SearchName
.MaximumLength
= Node
->NameLength
;
1784 SearchName
.Buffer
= Node
->Name
;
1787 /* Now get the parent node */
1788 Node
= (PCM_KEY_NODE
)HvGetCell(Hive
, ParentKey
);
1789 if (!Node
) goto Exit
;
1791 /* Make sure it's dirty, then release it */
1792 ASSERT(HvIsCellDirty(Hive
, ParentKey
));
1793 HvReleaseCell(Hive
, ParentKey
);
1795 /* Get the storage type and make sure it's not empty */
1796 Storage
= HvGetCellType(TargetKey
);
1797 ASSERT(Node
->SubKeyCounts
[Storage
] != 0);
1798 //ASSERT(HvIsCellAllocated(Hive, Node->SubKeyLists[Storage]));
1800 /* Get the leaf cell now */
1801 LeafCell
= Node
->SubKeyLists
[Storage
];
1802 Leaf
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
1803 if (!Leaf
) goto Exit
;
1805 /* Remember to release it later */
1806 CellToRelease1
= LeafCell
;
1808 /* Check if the leaf is a root */
1809 if (Leaf
->Signature
== CM_KEY_INDEX_ROOT
)
1811 /* Find the child inside the root */
1812 RootIndex
= CmpFindSubKeyInRoot(Hive
, Leaf
, &SearchName
, &ChildCell
);
1813 if (RootIndex
& 0x80000000) goto Exit
;
1814 ASSERT(ChildCell
!= FALSE
);
1816 /* The root cell is now this leaf */
1818 RootCell
= LeafCell
;
1820 /* And the new leaf is now this child */
1821 LeafCell
= ChildCell
;
1822 Leaf
= (PCM_KEY_INDEX
)HvGetCell(Hive
, LeafCell
);
1823 if (!Leaf
) goto Exit
;
1825 /* Remember to release it later */
1826 CellToRelease2
= LeafCell
;
1829 /* Make sure the leaf is valid */
1830 ASSERT((Leaf
->Signature
== CM_KEY_INDEX_LEAF
) ||
1831 (Leaf
->Signature
== CM_KEY_FAST_LEAF
) ||
1832 (Leaf
->Signature
== CM_KEY_HASH_LEAF
));
1834 /* Now get the child in the leaf */
1835 LeafIndex
= CmpFindSubKeyInLeaf(Hive
, Leaf
, &SearchName
, &ChildCell
);
1836 if (LeafIndex
& 0x80000000) goto Exit
;
1837 ASSERT(ChildCell
!= HCELL_NIL
);
1839 /* Decrement key counts and check if this was the last leaf entry */
1840 Node
->SubKeyCounts
[Storage
]--;
1841 if (!(--Leaf
->Count
))
1844 HvFreeCell(Hive
, LeafCell
);
1846 /* Check if we were inside a root */
1849 /* Decrease the root count too, since the leaf is going away */
1850 if (!(--Root
->Count
))
1852 /* The root is gone too,n ow */
1853 HvFreeCell(Hive
, RootCell
);
1854 Node
->SubKeyLists
[Storage
] = HCELL_NIL
;
1856 else if (RootIndex
< Root
->Count
)
1858 /* Bring everything up by one */
1859 RtlMoveMemory(&Root
->List
[RootIndex
],
1860 &Root
->List
[RootIndex
+ 1],
1861 (Root
->Count
- RootIndex
) * sizeof(HCELL_INDEX
));
1866 /* Otherwise, just clear the cell */
1867 Node
->SubKeyLists
[Storage
] = HCELL_NIL
;
1870 else if (LeafIndex
< Leaf
->Count
)
1872 /* Was the leaf a normal index? */
1873 if (Leaf
->Signature
== CM_KEY_INDEX_LEAF
)
1875 /* Bring everything up by one */
1876 RtlMoveMemory(&Leaf
->List
[LeafIndex
],
1877 &Leaf
->List
[LeafIndex
+ 1],
1878 (Leaf
->Count
- LeafIndex
) * sizeof(HCELL_INDEX
));
1882 /* This is a fast index, bring everything up by one */
1883 Child
= (PCM_KEY_FAST_INDEX
)Leaf
;
1884 RtlMoveMemory(&Child
->List
[LeafIndex
],
1885 &Child
->List
[LeafIndex
+1],
1886 (Child
->Count
- LeafIndex
) * sizeof(CM_INDEX
));
1890 /* If we got here, now we're done */
1894 /* Release any cells we may have been holding */
1895 if (CellToRelease1
!= HCELL_NIL
) HvReleaseCell(Hive
, CellToRelease1
);
1896 if (CellToRelease2
!= HCELL_NIL
) HvReleaseCell(Hive
, CellToRelease2
);
1898 /* Check if the name was compressed and not inside our local buffer */
1899 if ((IsCompressed
) && (SearchName
.MaximumLength
> sizeof(Buffer
)))
1901 /* Free the buffer we allocated */
1902 CmpFree(SearchName
.Buffer
, 0);
1905 /* Return the result */