1 /*
2 * PROJECT: ReactOS Registry Library
3 * LICENSE: GPL - See COPYING in the top level directory
4 * FILE: lib/cmlib/cmindex.c
5 * PURPOSE: Configuration Manager - Cell Indexes
6 * PROGRAMMERS: Alex Ionescu (alex.ionescu@reactos.org)
7 */
8
9 /* INCLUDES ******************************************************************/
10
11 #include "cmlib.h"
12 #define NDEBUG
13 #include <debug.h>
14
15 /* GLOBALS *******************************************************************/
16
17 #define INVALID_INDEX 0x80000000
18
19 #define CmpMaxFastIndexPerHblock \
20 ((HBLOCK_SIZE - (sizeof(HBIN) + sizeof(HCELL) + \
21 FIELD_OFFSET(CM_KEY_FAST_INDEX, List))) / sizeof(CM_INDEX))
22
23 #define CmpMaxIndexPerHblock \
24 ((HBLOCK_SIZE - (sizeof(HBIN) + sizeof(HCELL) + \
25 FIELD_OFFSET(CM_KEY_INDEX, List))) / sizeof(HCELL_INDEX) - 1)
26
27 /* FUNCTIONS *****************************************************************/
28
29 LONG
30 NTAPI
CmpDoCompareKeyName(IN PHHIVE Hive,IN PCUNICODE_STRING SearchName,IN HCELL_INDEX Cell)31 CmpDoCompareKeyName(IN PHHIVE Hive,
32 IN PCUNICODE_STRING SearchName,
33 IN HCELL_INDEX Cell)
34 {
35 PCM_KEY_NODE Node;
36 UNICODE_STRING KeyName;
37 LONG Result;
38
39 /* Get the node */
40 Node = (PCM_KEY_NODE)HvGetCell(Hive, Cell);
41 if (!Node) return 2;
42
43 /* Check if it's compressed */
44 if (Node->Flags & KEY_COMP_NAME)
45 {
46 /* Compare compressed names */
47 Result = CmpCompareCompressedName(SearchName,
48 Node->Name,
49 Node->NameLength);
50 }
51 else
52 {
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);
58 }
59
60 /* Release the cell and return the normalized result */
61 HvReleaseCell(Hive, Cell);
62 return (Result == 0) ? Result : ((Result > 0) ? 1 : -1);
63 }
64
65 LONG
66 NTAPI
CmpCompareInIndex(IN PHHIVE Hive,IN PCUNICODE_STRING SearchName,IN ULONG Count,IN PCM_KEY_INDEX Index,IN PHCELL_INDEX SubKey)67 CmpCompareInIndex(IN PHHIVE Hive,
68 IN PCUNICODE_STRING SearchName,
69 IN ULONG Count,
70 IN PCM_KEY_INDEX Index,
71 IN PHCELL_INDEX SubKey)
72 {
73 PCM_KEY_FAST_INDEX FastIndex;
74 PCM_INDEX FastEntry;
75 LONG Result;
76 ULONG i;
77 ULONG ActualNameLength = 4, CompareLength, NameLength;
78 WCHAR p, pp;
79
80 /* Assume failure */
81 *SubKey = HCELL_NIL;
82
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))
86 {
87 /* Get the Fast/Hash Index */
88 FastIndex = (PCM_KEY_FAST_INDEX)Index;
89 FastEntry = &FastIndex->List[Count];
90
91 /* Check if we are a hash leaf, in which case we skip all this */
92 if (Index->Signature == CM_KEY_FAST_LEAF)
93 {
94 /* Find out just how much of the name is there */
95 for (i = 0; i < 4; i++)
96 {
97 /* Check if this entry is empty */
98 if (!FastEntry->NameHint[i])
99 {
100 /* Only this much! */
101 ActualNameLength = i;
102 break;
103 }
104 }
105
106 /* How large is the name and how many characters to compare */
107 NameLength = SearchName->Length / sizeof(WCHAR);
108 CompareLength = min(NameLength, ActualNameLength);
109
110 /* Loop all the chars we'll test */
111 for (i = 0; i < CompareLength; i++)
112 {
113 /* Get one char from each buffer */
114 p = SearchName->Buffer[i];
115 pp = FastEntry->NameHint[i];
116
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;
121 }
122 }
123
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;
128 }
129 else
130 {
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];
135 }
136
137 /* Return the comparison result */
138 return Result;
139 }
140
141 ULONG
142 NTAPI
CmpFindSubKeyInRoot(IN PHHIVE Hive,IN PCM_KEY_INDEX Index,IN PCUNICODE_STRING SearchName,IN PHCELL_INDEX SubKey)143 CmpFindSubKeyInRoot(IN PHHIVE Hive,
144 IN PCM_KEY_INDEX Index,
145 IN PCUNICODE_STRING SearchName,
146 IN PHCELL_INDEX SubKey)
147 {
148 ULONG High, Low = 0, i = 0, ReturnIndex;
149 HCELL_INDEX LeafCell;
150 PCM_KEY_INDEX Leaf;
151 LONG Result;
152
153 /* Verify Index for validity */
154 ASSERT(Index->Count != 0);
155 ASSERT(Index->Signature == CM_KEY_INDEX_ROOT);
156
157 /* Set high limit and loop */
158 High = Index->Count - 1;
159 while (TRUE)
160 {
161 /* Choose next entry */
162 i = ((High - Low) / 2) + Low;
163
164 /* Get the leaf cell and then the leaf itself */
165 LeafCell = Index->List[i];
166 Leaf = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
167 if (Leaf)
168 {
169 /* Make sure the leaf is valid */
170 ASSERT((Leaf->Signature == CM_KEY_INDEX_LEAF) ||
171 (Leaf->Signature == CM_KEY_FAST_LEAF) ||
172 (Leaf->Signature == CM_KEY_HASH_LEAF));
173 ASSERT(Leaf->Count != 0);
174
175 /* Do the compare */
176 Result = CmpCompareInIndex(Hive,
177 SearchName,
178 Leaf->Count - 1,
179 Leaf,
180 SubKey);
181 if (Result == 2) goto Big;
182
183 /* Check if we found the leaf */
184 if (!Result)
185 {
186 /* We found the leaf */
187 *SubKey = LeafCell;
188 ReturnIndex = i;
189 goto Return;
190 }
191
192 /* Check for negative result */
193 if (Result < 0)
194 {
195 /* If we got here, we should be at -1 */
196 ASSERT(Result == -1);
197
198 /* Do another lookup, since we might still be in the right leaf */
199 Result = CmpCompareInIndex(Hive,
200 SearchName,
201 0,
202 Leaf,
203 SubKey);
204 if (Result == 2) goto Big;
205
206 /* Check if it's not below */
207 if (Result >= 0)
208 {
209 /*
210 * If the name was first below, and now it is above,
211 * then this means that it is somewhere in this leaf.
212 * Make sure we didn't get some weird result
213 */
214 ASSERT((Result == 1) || (Result == 0));
215
216 /* Return it */
217 *SubKey = LeafCell;
218 ReturnIndex = i;
219 goto Return;
220 }
221
222 /* Update the limit to this index, since we know it's not higher. */
223 High = i;
224 }
225 else
226 {
227 /* Update the base to this index, since we know it's not lower. */
228 Low = i;
229 }
230 }
231 else
232 {
233 Big:
234 /* This was some sort of special key */
235 ReturnIndex = INVALID_INDEX;
236 goto ReturnFailure;
237 }
238
239 /* Check if there is only one entry left */
240 if ((High - Low) <= 1) break;
241
242 /* Release the leaf cell */
243 HvReleaseCell(Hive, LeafCell);
244 }
245
246 /* Make sure we got here for the right reasons */
247 ASSERT((High - Low == 1) || (High == Low));
248
249 /* Get the leaf cell and the leaf */
250 LeafCell = Index->List[Low];
251 Leaf = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
252 if (!Leaf) goto Big;
253
254 /* Do the compare */
255 Result = CmpCompareInIndex(Hive,
256 SearchName,
257 Leaf->Count-1,
258 Leaf,
259 SubKey);
260 if (Result == 2) goto Big;
261
262 /* Check if we found it */
263 if (!Result)
264 {
265 /* We got lucky... return it */
266 *SubKey = LeafCell;
267 ReturnIndex = Low;
268 goto Return;
269 }
270
271 /* It's below, so could still be in this leaf */
272 if (Result < 0)
273 {
274 /* Make sure we're -1 */
275 ASSERT(Result == -1);
276
277 /* Do a search from the bottom */
278 Result = CmpCompareInIndex(Hive, SearchName, 0, Leaf, SubKey);
279 if (Result == 2) goto Big;
280
281 /*
282 * Check if it's above, which means that it's within the ranges of our
283 * leaf (since we were below before).
284 */
285 if (Result >= 0)
286 {
287 /* Sanity check */
288 ASSERT((Result == 1) || (Result == 0));
289
290 /* Yep, so we're in the right leaf; return it. */
291 *SubKey = LeafCell;
292 ReturnIndex = Low;
293 goto Return;
294 }
295
296 /* It's still below us, so fail */
297 ReturnIndex = Low;
298 goto ReturnFailure;
299 }
300
301 /* Release the leaf cell */
302 HvReleaseCell(Hive, LeafCell);
303
304 /* Well the low didn't work too well, so try the high. */
305 LeafCell = Index->List[High];
306 Leaf = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
307 if (!Leaf) goto Big;
308
309 /* Do the compare */
310 Result = CmpCompareInIndex(Hive,
311 SearchName,
312 Leaf->Count - 1,
313 Leaf,
314 SubKey);
315 if (Result == 2) goto Big;
316
317 /* Check if we found it */
318 if (Result == 0)
319 {
320 /* We got lucky... return it */
321 *SubKey = LeafCell;
322 ReturnIndex = High;
323 goto Return;
324 }
325
326 /* Check if we are too high */
327 if (Result < 0)
328 {
329 /* Make sure we're -1 */
330 ASSERT(Result == -1);
331
332 /*
333 * Once again... since we were first too low and now too high, then
334 * this means we are within the range of this leaf... return it.
335 */
336 *SubKey = LeafCell;
337 ReturnIndex = High;
338 goto Return;
339 }
340
341 /* If we got here, then we are too low, again. */
342 ReturnIndex = High;
343
344 /* Failure path */
345 ReturnFailure:
346 *SubKey = HCELL_NIL;
347
348 /* Return path...check if we have a leaf to free */
349 Return:
350 if (Leaf) HvReleaseCell(Hive, LeafCell);
351
352 /* Return the index */
353 return ReturnIndex;
354 }
355
356 ULONG
357 NTAPI
CmpFindSubKeyInLeaf(IN PHHIVE Hive,IN PCM_KEY_INDEX Index,IN PCUNICODE_STRING SearchName,IN PHCELL_INDEX SubKey)358 CmpFindSubKeyInLeaf(IN PHHIVE Hive,
359 IN PCM_KEY_INDEX Index,
360 IN PCUNICODE_STRING SearchName,
361 IN PHCELL_INDEX SubKey)
362 {
363 ULONG High, Low = 0, i;
364 LONG Result;
365
366 /* Verify Index for validity */
367 ASSERT((Index->Signature == CM_KEY_INDEX_LEAF) ||
368 (Index->Signature == CM_KEY_FAST_LEAF) ||
369 (Index->Signature == CM_KEY_HASH_LEAF));
370
371 /* Get the upper bound and middle entry */
372 High = Index->Count - 1;
373 i = High / 2;
374
375 /* Check if we don't actually have any entries */
376 if (!Index->Count)
377 {
378 /* Return failure */
379 *SubKey = HCELL_NIL;
380 return 0;
381 }
382
383 /* Start compare loop */
384 while (TRUE)
385 {
386 /* Do the actual comparison and check the result */
387 Result = CmpCompareInIndex(Hive, SearchName, i, Index, SubKey);
388 if (Result == 2)
389 {
390 /* Fail with special value */
391 *SubKey = HCELL_NIL;
392 return INVALID_INDEX;
393 }
394
395 /* Check if we got lucky and found it */
396 if (!Result) return i;
397
398 /* Check if the result is below us */
399 if (Result < 0)
400 {
401 /* Set the new bound; it can't be higher then where we are now. */
402 ASSERT(Result == -1);
403 High = i;
404 }
405 else
406 {
407 /* Set the new bound... it can't be lower then where we are now. */
408 ASSERT(Result == 1);
409 Low = i;
410 }
411
412 /* Check if this is the last entry, if so, break out and handle it */
413 if ((High - Low) <= 1) break;
414
415 /* Set the new index */
416 i = ((High - Low) / 2) + Low;
417 }
418
419 /*
420 * If we get here, High - Low = 1 or High == Low
421 * Simply look first at Low, then at High
422 */
423 Result = CmpCompareInIndex(Hive, SearchName, Low, Index, SubKey);
424 if (Result == 2)
425 {
426 /* Fail with special value */
427 *SubKey = HCELL_NIL;
428 return INVALID_INDEX;
429 }
430
431 /* Check if we got lucky and found it */
432 if (!Result) return Low;
433
434 /* Check if the result is below us */
435 if (Result < 0)
436 {
437 /* Return the low entry */
438 ASSERT(Result == -1);
439 return Low;
440 }
441
442 /*
443 * If we got here, then just check the high and return it no matter what
444 * the result is (since we're a leaf, it has to be near there anyway).
445 */
446 Result = CmpCompareInIndex(Hive, SearchName, High, Index, SubKey);
447 if (Result == 2)
448 {
449 /* Fail with special value */
450 *SubKey = HCELL_NIL;
451 return INVALID_INDEX;
452 }
453
454 /* Return the high */
455 return High;
456 }
457
458 ULONG
459 NTAPI
CmpComputeHashKey(IN ULONG Hash,IN PCUNICODE_STRING Name,IN BOOLEAN AllowSeparators)460 CmpComputeHashKey(IN ULONG Hash,
461 IN PCUNICODE_STRING Name,
462 IN BOOLEAN AllowSeparators)
463 {
464 LPWSTR Cp;
465 ULONG Value, i;
466
467 /* Make some sanity checks on our parameters */
468 ASSERT((Name->Length == 0) ||
469 (AllowSeparators) ||
470 (Name->Buffer[0] != OBJ_NAME_PATH_SEPARATOR));
471
472 /* If the name is empty, there is nothing to hash! */
473 if (!Name->Length) return Hash;
474
475 /* Set the buffer and loop every character */
476 Cp = Name->Buffer;
477 for (i = 0; i < Name->Length; i += sizeof(WCHAR), Cp++)
478 {
479 /* Make sure we don't have a separator when we shouldn't */
480 ASSERT(AllowSeparators || (*Cp != OBJ_NAME_PATH_SEPARATOR));
481
482 /* Check what kind of char we have */
483 if (*Cp >= L'a')
484 {
485 /* In the lower case region... is it truly lower case? */
486 if (*Cp < L'z')
487 {
488 /* Yes! Calculate it ourselves! */
489 Value = *Cp - L'a' + L'A';
490 }
491 else
492 {
493 /* No, use the API */
494 Value = RtlUpcaseUnicodeChar(*Cp);
495 }
496 }
497 else
498 {
499 /* Reuse the char, it's already upcased */
500 Value = *Cp;
501 }
502
503 /* Multiply by a prime and add our value */
504 Hash *= 37;
505 Hash += Value;
506 }
507
508 /* Return the hash */
509 return Hash;
510 }
511
512 HCELL_INDEX
513 NTAPI
CmpDoFindSubKeyByNumber(IN PHHIVE Hive,IN PCM_KEY_INDEX Index,IN ULONG Number)514 CmpDoFindSubKeyByNumber(IN PHHIVE Hive,
515 IN PCM_KEY_INDEX Index,
516 IN ULONG Number)
517 {
518 ULONG i;
519 HCELL_INDEX LeafCell = 0;
520 PCM_KEY_INDEX Leaf = NULL;
521 PCM_KEY_FAST_INDEX FastIndex;
522 HCELL_INDEX Result;
523
524 /* Check if this is a root */
525 if (Index->Signature == CM_KEY_INDEX_ROOT)
526 {
527 /* Loop the index */
528 for (i = 0; i < Index->Count; i++)
529 {
530 /* Check if this isn't the first iteration */
531 if (i)
532 {
533 /* Make sure we had something valid, and release it */
534 ASSERT(Leaf != NULL );
535 ASSERT(LeafCell == Index->List[i - 1]);
536 HvReleaseCell(Hive, LeafCell);
537 }
538
539 /* Get the leaf cell and the leaf for this index */
540 LeafCell = Index->List[i];
541 Leaf = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
542 if (!Leaf) return HCELL_NIL;
543
544 /* Check if the index may be inside it */
545 if (Number < Leaf->Count)
546 {
547 /* Check if this is a fast or hash leaf */
548 if ((Leaf->Signature == CM_KEY_FAST_LEAF) ||
549 (Leaf->Signature == CM_KEY_HASH_LEAF))
550 {
551 /* Get the fast index */
552 FastIndex = (PCM_KEY_FAST_INDEX)Leaf;
553
554 /* Look inside the list to get our actual cell */
555 Result = FastIndex->List[Number].Cell;
556 HvReleaseCell(Hive, LeafCell);
557 return Result;
558 }
559 else
560 {
561 /* Regular leaf, so just use the index directly */
562 Result = Leaf->List[Number];
563
564 /* Release and return it */
565 HvReleaseCell(Hive,LeafCell);
566 return Result;
567 }
568 }
569 else
570 {
571 /* Otherwise, skip this leaf */
572 Number = Number - Leaf->Count;
573 }
574 }
575
576 /* Should never get here */
577 ASSERT(FALSE);
578 }
579
580 /* If we got here, then the cell is in this index */
581 ASSERT(Number < Index->Count);
582
583 /* Check if we're a fast or hash leaf */
584 if ((Index->Signature == CM_KEY_FAST_LEAF) ||
585 (Index->Signature == CM_KEY_HASH_LEAF))
586 {
587 /* We are, get the fast index and get the cell from the list */
588 FastIndex = (PCM_KEY_FAST_INDEX)Index;
589 return FastIndex->List[Number].Cell;
590 }
591 else
592 {
593 /* We aren't, so use the index directly to grab the cell */
594 return Index->List[Number];
595 }
596 }
597
598 HCELL_INDEX
599 NTAPI
CmpFindSubKeyByNumber(IN PHHIVE Hive,IN PCM_KEY_NODE Node,IN ULONG Number)600 CmpFindSubKeyByNumber(IN PHHIVE Hive,
601 IN PCM_KEY_NODE Node,
602 IN ULONG Number)
603 {
604 PCM_KEY_INDEX Index;
605 HCELL_INDEX Result = HCELL_NIL;
606
607 /* Check if it's in the stable list */
608 if (Number < Node->SubKeyCounts[Stable])
609 {
610 /* Get the actual key index */
611 Index = (PCM_KEY_INDEX)HvGetCell(Hive, Node->SubKeyLists[Stable]);
612 if (!Index) return HCELL_NIL;
613
614 /* Do a search inside it */
615 Result = CmpDoFindSubKeyByNumber(Hive, Index, Number);
616
617 /* Release the cell and return the result */
618 HvReleaseCell(Hive, Node->SubKeyLists[Stable]);
619 return Result;
620 }
621 else if (Hive->StorageTypeCount > Volatile)
622 {
623 /* It's in the volatile list */
624 Number = Number - Node->SubKeyCounts[Stable];
625 if (Number < Node->SubKeyCounts[Volatile])
626 {
627 /* Get the actual key index */
628 Index = (PCM_KEY_INDEX)HvGetCell(Hive, Node->SubKeyLists[Volatile]);
629 if (!Index) return HCELL_NIL;
630
631 /* Do a search inside it */
632 Result = CmpDoFindSubKeyByNumber(Hive, Index, Number);
633
634 /* Release the cell and return the result */
635 HvReleaseCell(Hive, Node->SubKeyLists[Volatile]);
636 return Result;
637 }
638 }
639
640 /* Nothing was found */
641 return HCELL_NIL;
642 }
643
644 static HCELL_INDEX
645 NTAPI
CmpFindSubKeyByHash(IN PHHIVE Hive,IN PCM_KEY_FAST_INDEX FastIndex,IN PCUNICODE_STRING SearchName)646 CmpFindSubKeyByHash(IN PHHIVE Hive,
647 IN PCM_KEY_FAST_INDEX FastIndex,
648 IN PCUNICODE_STRING SearchName)
649 {
650 ULONG HashKey, i;
651 PCM_INDEX FastEntry;
652
653 /* Make sure it's really a hash */
654 ASSERT(FastIndex->Signature == CM_KEY_HASH_LEAF);
655
656 /* Compute the hash key for the name */
657 HashKey = CmpComputeHashKey(0, SearchName, FALSE);
658
659 /* Loop all the entries */
660 for (i = 0; i < FastIndex->Count; i++)
661 {
662 /* Get the entry */
663 FastEntry = &FastIndex->List[i];
664
665 /* Compare the hash first */
666 if (FastEntry->HashKey == HashKey)
667 {
668 /* Go ahead for a full compare */
669 if (!(CmpDoCompareKeyName(Hive, SearchName, FastEntry->Cell)))
670 {
671 /* It matched, return the cell */
672 return FastEntry->Cell;
673 }
674 }
675 }
676
677 /* If we got here then we failed */
678 return HCELL_NIL;
679 }
680
681 HCELL_INDEX
682 NTAPI
CmpFindSubKeyByName(IN PHHIVE Hive,IN PCM_KEY_NODE Parent,IN PCUNICODE_STRING SearchName)683 CmpFindSubKeyByName(IN PHHIVE Hive,
684 IN PCM_KEY_NODE Parent,
685 IN PCUNICODE_STRING SearchName)
686 {
687 ULONG i;
688 PCM_KEY_INDEX IndexRoot;
689 HCELL_INDEX SubKey, CellToRelease;
690 ULONG Found;
691
692 /* Loop each storage type */
693 for (i = 0; i < Hive->StorageTypeCount; i++)
694 {
695 /* Make sure the parent node has subkeys */
696 if (Parent->SubKeyCounts[i])
697 {
698 /* Get the Index */
699 IndexRoot = (PCM_KEY_INDEX)HvGetCell(Hive, Parent->SubKeyLists[i]);
700 if (!IndexRoot) return HCELL_NIL;
701
702 /* Get the cell we'll need to release */
703 CellToRelease = Parent->SubKeyLists[i];
704
705 /* Check if this is another index root */
706 if (IndexRoot->Signature == CM_KEY_INDEX_ROOT)
707 {
708 /* Lookup the name in the root */
709 Found = CmpFindSubKeyInRoot(Hive,
710 IndexRoot,
711 SearchName,
712 &SubKey);
713
714 /* Release the previous cell */
715 ASSERT(CellToRelease != HCELL_NIL);
716 HvReleaseCell(Hive, CellToRelease);
717
718 /* Make sure we found something valid */
719 if (Found & INVALID_INDEX) break;
720
721 /* Get the new Index Root and set the new cell to be released */
722 if (SubKey == HCELL_NIL) continue;
723 CellToRelease = SubKey;
724 IndexRoot = (PCM_KEY_INDEX)HvGetCell(Hive, SubKey);
725 }
726
727 /* Make sure the signature is what we expect it to be */
728 ASSERT((IndexRoot->Signature == CM_KEY_INDEX_LEAF) ||
729 (IndexRoot->Signature == CM_KEY_FAST_LEAF) ||
730 (IndexRoot->Signature == CM_KEY_HASH_LEAF));
731
732 /* Check if this isn't a hashed leaf */
733 if (IndexRoot->Signature != CM_KEY_HASH_LEAF)
734 {
735 /* Find the subkey in the leaf */
736 Found = CmpFindSubKeyInLeaf(Hive,
737 IndexRoot,
738 SearchName,
739 &SubKey);
740
741 /* Release the previous cell */
742 ASSERT(CellToRelease != HCELL_NIL);
743 HvReleaseCell(Hive, CellToRelease);
744
745 /* Make sure we found a valid index */
746 if (Found & INVALID_INDEX) break;
747 }
748 else
749 {
750 /* Find the subkey in the hash */
751 SubKey = CmpFindSubKeyByHash(Hive,
752 (PCM_KEY_FAST_INDEX)IndexRoot,
753 SearchName);
754
755 /* Release the previous cell */
756 ASSERT(CellToRelease != HCELL_NIL);
757 HvReleaseCell(Hive, CellToRelease);
758 }
759
760 /* Make sure we got a valid subkey and return it */
761 if (SubKey != HCELL_NIL) return SubKey;
762 }
763 }
764
765 /* If we got here, then we failed */
766 return HCELL_NIL;
767 }
768
769 BOOLEAN
770 NTAPI
CmpMarkIndexDirty(IN PHHIVE Hive,IN HCELL_INDEX ParentKey,IN HCELL_INDEX TargetKey)771 CmpMarkIndexDirty(IN PHHIVE Hive,
772 IN HCELL_INDEX ParentKey,
773 IN HCELL_INDEX TargetKey)
774 {
775 PCM_KEY_NODE Node;
776 UNICODE_STRING SearchName;
777 BOOLEAN IsCompressed;
778 ULONG i, Result;
779 PCM_KEY_INDEX Index;
780 HCELL_INDEX IndexCell, Child = HCELL_NIL, CellToRelease = HCELL_NIL;
781
782 /* Get the target key node */
783 Node = (PCM_KEY_NODE)HvGetCell(Hive, TargetKey);
784 if (!Node) return FALSE;
785
786 /* Check if it's compressed */
787 if (Node->Flags & KEY_COMP_NAME)
788 {
789 /* Remember this for later */
790 IsCompressed = TRUE;
791
792 /* Build the search name */
793 SearchName.Length = CmpCompressedNameSize(Node->Name,
794 Node->NameLength);
795 SearchName.MaximumLength = SearchName.Length;
796 SearchName.Buffer = Hive->Allocate(SearchName.Length, TRUE, TAG_CM);
797 if (!SearchName.Buffer)
798 {
799 /* Fail */
800 HvReleaseCell(Hive, TargetKey);
801 return FALSE;
802 }
803
804 /* Copy it */
805 CmpCopyCompressedName(SearchName.Buffer,
806 SearchName.MaximumLength,
807 Node->Name,
808 Node->NameLength);
809 }
810 else
811 {
812 /* Name isn't compressed, build it directly from the node */
813 IsCompressed = FALSE;
814 SearchName.Length = Node->NameLength;
815 SearchName.MaximumLength = Node->NameLength;
816 SearchName.Buffer = Node->Name;
817 }
818
819 /* We can release the target key now */
820 HvReleaseCell(Hive, TargetKey);
821
822 /* Now get the parent key node */
823 Node = (PCM_KEY_NODE)HvGetCell(Hive, ParentKey);
824 if (!Node) goto Quickie;
825
826 /* Loop all hive storage */
827 for (i = 0; i < Hive->StorageTypeCount; i++)
828 {
829 /* Check if any subkeys are in this index */
830 if (Node->SubKeyCounts[i])
831 {
832 /* Get the cell index */
833 //ASSERT(HvIsCellAllocated(Hive, Node->SubKeyLists[i]));
834 IndexCell = Node->SubKeyLists[i];
835
836 /* Check if we had anything to release from before */
837 if (CellToRelease != HCELL_NIL)
838 {
839 /* Release it now */
840 HvReleaseCell(Hive, CellToRelease);
841 CellToRelease = HCELL_NIL;
842 }
843
844 /* Get the key index for the cell */
845 Index = (PCM_KEY_INDEX)HvGetCell(Hive, IndexCell);
846 if (!Index) goto Quickie;
847
848 /* Release it at the next iteration or below */
849 CellToRelease = IndexCell;
850
851 /* Check if this is a root */
852 if (Index->Signature == CM_KEY_INDEX_ROOT)
853 {
854 /* Get the child inside the root */
855 Result = CmpFindSubKeyInRoot(Hive, Index, &SearchName, &Child);
856 if (Result & INVALID_INDEX) goto Quickie;
857 if (Child == HCELL_NIL) continue;
858
859 /* We found it, mark the cell dirty */
860 HvMarkCellDirty(Hive, IndexCell, FALSE);
861
862 /* Check if we had anything to release from before */
863 if (CellToRelease != HCELL_NIL)
864 {
865 /* Release it now */
866 HvReleaseCell(Hive, CellToRelease);
867 CellToRelease = HCELL_NIL;
868 }
869
870 /* Now this child is the index, get the actual key index */
871 IndexCell = Child;
872 Index = (PCM_KEY_INDEX)HvGetCell(Hive, Child);
873 if (!Index) goto Quickie;
874
875 /* Release it later */
876 CellToRelease = Child;
877 }
878
879 /* Make sure this is a valid index */
880 ASSERT((Index->Signature == CM_KEY_INDEX_LEAF) ||
881 (Index->Signature == CM_KEY_FAST_LEAF) ||
882 (Index->Signature == CM_KEY_HASH_LEAF));
883
884 /* Find the child in the leaf */
885 Result = CmpFindSubKeyInLeaf(Hive, Index, &SearchName, &Child);
886 if (Result & INVALID_INDEX) goto Quickie;
887 if (Child != HCELL_NIL)
888 {
889 /* We found it, free the name now */
890 if (IsCompressed) Hive->Free(SearchName.Buffer, 0);
891
892 /* Release the parent key */
893 HvReleaseCell(Hive, ParentKey);
894
895 /* Check if we had a left over cell to release */
896 if (CellToRelease != HCELL_NIL)
897 {
898 /* Release it */
899 HvReleaseCell(Hive, CellToRelease);
900 }
901
902 /* And mark the index cell dirty */
903 HvMarkCellDirty(Hive, IndexCell, FALSE);
904 return TRUE;
905 }
906 }
907 }
908
909 Quickie:
910 /* Release any cells that we still hold */
911 if (Node) HvReleaseCell(Hive, ParentKey);
912 if (CellToRelease != HCELL_NIL) HvReleaseCell(Hive, CellToRelease);
913
914 /* Free the search name and return failure */
915 if (IsCompressed) Hive->Free(SearchName.Buffer, 0);
916 return FALSE;
917 }
918
919 HCELL_INDEX
920 NTAPI
CmpAddToLeaf(IN PHHIVE Hive,IN HCELL_INDEX LeafCell,IN HCELL_INDEX NewKey,IN PCUNICODE_STRING Name)921 CmpAddToLeaf(IN PHHIVE Hive,
922 IN HCELL_INDEX LeafCell,
923 IN HCELL_INDEX NewKey,
924 IN PCUNICODE_STRING Name)
925 {
926 PCM_KEY_INDEX Leaf;
927 PCM_KEY_FAST_INDEX FastLeaf;
928 ULONG Size, OldSize, EntrySize, i, j;
929 HCELL_INDEX NewCell, Child;
930 LONG Result;
931
932 /* Mark the leaf dirty */
933 HvMarkCellDirty(Hive, LeafCell, FALSE);
934
935 /* Get the leaf cell */
936 Leaf = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
937 if (!Leaf)
938 {
939 /* Shouldn't happen */
940 ASSERT(FALSE);
941 return HCELL_NIL;
942 }
943
944 /* Release it */
945 HvReleaseCell(Hive, LeafCell);
946
947 /* Check if this is an index leaf */
948 if (Leaf->Signature == CM_KEY_INDEX_LEAF)
949 {
950 /* This is an old-style leaf */
951 FastLeaf = NULL;
952 EntrySize = sizeof(HCELL_INDEX);
953 }
954 else
955 {
956 /* Sanity check */
957 ASSERT((Leaf->Signature == CM_KEY_FAST_LEAF) ||
958 (Leaf->Signature == CM_KEY_HASH_LEAF));
959
960 /* This is a new-style optimized fast (or hash) leaf */
961 FastLeaf = (PCM_KEY_FAST_INDEX)Leaf;
962 EntrySize = sizeof(CM_INDEX);
963 }
964
965 /* Get the current size of the leaf */
966 OldSize = HvGetCellSize(Hive, Leaf);
967
968 /* Calculate the size of the free entries */
969 Size = OldSize;
970 Size -= EntrySize * Leaf->Count + FIELD_OFFSET(CM_KEY_INDEX, List);
971
972 /* Assume we'll re-use the same leaf */
973 NewCell = LeafCell;
974
975 /* Check if we're out of space */
976 if ((Size / EntrySize) < 1)
977 {
978 /* Grow the leaf by 1.5x, making sure we can at least fit this entry */
979 Size = OldSize + OldSize / 2;
980 if (Size < (OldSize + EntrySize)) Size = OldSize + EntrySize;
981
982 /* Re-allocate the leaf */
983 NewCell = HvReallocateCell(Hive, LeafCell, Size);
984 if (NewCell == HCELL_NIL) return HCELL_NIL;
985
986 /* Get the leaf cell */
987 Leaf = (PCM_KEY_INDEX)HvGetCell(Hive, NewCell);
988 if (!Leaf)
989 {
990 /* This shouldn't happen */
991 ASSERT(FALSE);
992 return HCELL_NIL;
993 }
994
995 /* Release the cell */
996 HvReleaseCell(Hive, NewCell);
997
998 /* Update the fast leaf pointer if we had one */
999 if (FastLeaf) FastLeaf = (PCM_KEY_FAST_INDEX)Leaf;
1000 }
1001
1002 /* Find the insertion point for our entry */
1003 i = CmpFindSubKeyInLeaf(Hive, Leaf, Name, &Child);
1004 if (i & INVALID_INDEX) return HCELL_NIL;
1005 ASSERT(Child == HCELL_NIL);
1006
1007 /* Check if we're not last */
1008 if (i != Leaf->Count)
1009 {
1010 /* Find out where we should go */
1011 Result = CmpCompareInIndex(Hive,
1012 Name,
1013 i,
1014 Leaf,
1015 &Child);
1016 if (Result == 2) return HCELL_NIL;
1017 ASSERT(Result != 0);
1018
1019 /* Check if we come after */
1020 if (Result > 0)
1021 {
1022 /* We do, insert us after the key */
1023 ASSERT(Result == 1);
1024 i++;
1025 }
1026
1027 /* Check if we're still not last */
1028 if (i != Leaf->Count)
1029 {
1030 /* Check if we had a fast leaf or not */
1031 if (FastLeaf)
1032 {
1033 /* Copy the fast indexes */
1034 RtlMoveMemory(&FastLeaf->List[i + 1],
1035 &FastLeaf->List[i],
1036 (FastLeaf->Count - i) * sizeof(CM_INDEX));
1037 }
1038 else
1039 {
1040 /* Copy the indexes themselves */
1041 RtlMoveMemory(&Leaf->List[i + 1],
1042 &Leaf->List[i],
1043 (Leaf->Count - i) * sizeof(HCELL_INDEX));
1044 }
1045 }
1046 }
1047
1048 /* Check if this is a new-style leaf */
1049 if (FastLeaf)
1050 {
1051 /* Set our cell */
1052 FastLeaf->List[i].Cell = NewKey;
1053
1054 /* Check if this is a hash leaf */
1055 if( FastLeaf->Signature == CM_KEY_HASH_LEAF )
1056 {
1057 /* Set our hash key */
1058 FastLeaf->List[i].HashKey = CmpComputeHashKey(0, Name, FALSE);
1059 }
1060 else
1061 {
1062 /* First, clear the name */
1063 FastLeaf->List[i].NameHint[0] = 0;
1064 FastLeaf->List[i].NameHint[1] = 0;
1065 FastLeaf->List[i].NameHint[2] = 0;
1066 FastLeaf->List[i].NameHint[3] = 0;
1067
1068 /* Now, figure out if we can fit */
1069 if (Name->Length / sizeof(WCHAR) < 4)
1070 {
1071 /* We can fit, use our length */
1072 j = Name->Length / sizeof(WCHAR);
1073 }
1074 else
1075 {
1076 /* We can't, use a maximum of 4 */
1077 j = 4;
1078 }
1079
1080 /* Now fill out the name hint */
1081 do
1082 {
1083 /* Look for invalid characters and break out if we found one */
1084 if ((USHORT)Name->Buffer[j - 1] > (UCHAR)-1) break;
1085
1086 /* Otherwise, copy the a character */
1087 FastLeaf->List[i].NameHint[j - 1] = (UCHAR)Name->Buffer[j - 1];
1088 } while (--j > 0);
1089 }
1090 }
1091 else
1092 {
1093 /* This is an old-style leaf, just set our index directly */
1094 Leaf->List[i] = NewKey;
1095 }
1096
1097 /* Update the leaf count and return the new cell */
1098 Leaf->Count += 1;
1099 return NewCell;
1100 }
1101
1102 HCELL_INDEX
1103 NTAPI
CmpSplitLeaf(IN PHHIVE Hive,IN HCELL_INDEX RootCell,IN ULONG RootSelect,IN HSTORAGE_TYPE Type)1104 CmpSplitLeaf(IN PHHIVE Hive,
1105 IN HCELL_INDEX RootCell,
1106 IN ULONG RootSelect,
1107 IN HSTORAGE_TYPE Type)
1108 {
1109 PCM_KEY_INDEX IndexKey, LeafKey, NewKey;
1110 PCM_KEY_FAST_INDEX FastLeaf;
1111 HCELL_INDEX LeafCell, NewCell;
1112 USHORT FirstHalf, LastHalf;
1113 ULONG EntrySize, TotalSize;
1114
1115 /* Get the cell */
1116 IndexKey = (PCM_KEY_INDEX)HvGetCell(Hive, RootCell);
1117
1118 /* Check if we've got valid IndexKey */
1119 if (!IndexKey) return HCELL_NIL;
1120
1121 /* Get the leaf cell and key */
1122 LeafCell = IndexKey->List[RootSelect];
1123 LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1124
1125 /* Check if we've got valid LeafKey */
1126 if (!LeafKey) return HCELL_NIL;
1127
1128 /* We are going to divide this leaf into two halves */
1129 FirstHalf = (LeafKey->Count / 2);
1130 LastHalf = LeafKey->Count - FirstHalf;
1131
1132 /* Now check what kind of hive we're dealing with,
1133 * and compute entry size
1134 */
1135 if (Hive->Version >= 5)
1136 {
1137 /* XP Hive: Use hash leaf */
1138 ASSERT(LeafKey->Signature == CM_KEY_HASH_LEAF);
1139 EntrySize = sizeof(CM_INDEX);
1140 }
1141 else
1142 {
1143 /* Use index leaf */
1144 ASSERT(LeafKey->Signature == CM_KEY_INDEX_LEAF);
1145 EntrySize = sizeof(HCELL_INDEX);
1146 }
1147
1148 /* Compute the total size */
1149 TotalSize = (EntrySize * LastHalf) + FIELD_OFFSET(CM_KEY_INDEX, List) + 1;
1150
1151 /* Mark the leaf cell dirty */
1152 HvMarkCellDirty(Hive, LeafCell, FALSE);
1153
1154 /* Make sure its type is the same */
1155 ASSERT(HvGetCellType(LeafCell) == Type);
1156
1157 /* Allocate the cell, fail in case of error */
1158 NewCell = HvAllocateCell(Hive, TotalSize, Type, LeafCell);
1159 if (NewCell == HCELL_NIL) return NewCell;
1160
1161 /* Get the key */
1162 NewKey = (PCM_KEY_INDEX)HvGetCell(Hive, NewCell);
1163 if (!NewKey)
1164 {
1165 /* Free the cell and exit - should not happen! */
1166 ASSERT(FALSE);
1167 HvFreeCell(Hive, NewCell);
1168 return HCELL_NIL;
1169 }
1170
1171 /* Release the newly created cell */
1172 HvReleaseCell(Hive, NewCell);
1173
1174 /* Set its signature according to the version of the hive */
1175 if (Hive->Version >= 5)
1176 {
1177 /* XP Hive: Use hash leaf signature */
1178 NewKey->Signature = CM_KEY_HASH_LEAF;
1179 }
1180 else
1181 {
1182 /* Use index leaf signature */
1183 NewKey->Signature = CM_KEY_INDEX_LEAF;
1184 }
1185
1186 /* Calculate the size of the free entries in the root key */
1187 TotalSize = HvGetCellSize(Hive, IndexKey) -
1188 (IndexKey->Count * sizeof(HCELL_INDEX)) -
1189 FIELD_OFFSET(CM_KEY_INDEX, List);
1190
1191 /* Check if we're out of space */
1192 if (TotalSize / sizeof(HCELL_INDEX) < 1)
1193 {
1194 /* Grow the leaf by one more entry */
1195 TotalSize = HvGetCellSize(Hive, IndexKey) + sizeof(HCELL_INDEX);
1196
1197 /* Re-allocate the root */
1198 RootCell = HvReallocateCell(Hive, RootCell, TotalSize);
1199 if (RootCell == HCELL_NIL)
1200 {
1201 /* Free the cell and exit */
1202 HvFreeCell(Hive, NewCell);
1203 return HCELL_NIL;
1204 }
1205
1206 /* Get the leaf cell */
1207 IndexKey = (PCM_KEY_INDEX)HvGetCell(Hive, RootCell);
1208 if (!IndexKey)
1209 {
1210 /* This shouldn't happen */
1211 ASSERT(FALSE);
1212 return HCELL_NIL;
1213 }
1214 }
1215
1216 /* Splitting is done, now we need to copy the contents,
1217 * according to the hive version
1218 */
1219 if (Hive->Version >= 5)
1220 {
1221 /* Copy the fast indexes */
1222 FastLeaf = (PCM_KEY_FAST_INDEX)LeafKey;
1223 RtlMoveMemory(&NewKey->List[0],
1224 &FastLeaf->List[FirstHalf],
1225 LastHalf * EntrySize);
1226 }
1227 else
1228 {
1229 /* Copy the indexes themselves */
1230 RtlMoveMemory(&NewKey->List[0],
1231 &LeafKey->List[FirstHalf],
1232 LastHalf * EntrySize);
1233 }
1234
1235 /* Shift the data inside the root key */
1236 if ((RootSelect + 1) < IndexKey->Count)
1237 {
1238 RtlMoveMemory(&IndexKey->List[RootSelect + 2],
1239 &IndexKey->List[RootSelect + 1],
1240 (IndexKey->Count -
1241 (RootSelect + 1)) * sizeof(HCELL_INDEX));
1242 }
1243
1244 /* Make sure both old and new computed counts are valid */
1245 ASSERT(FirstHalf != 0);
1246 ASSERT(LastHalf != 0);
1247
1248 /* Update the count value of old and new keys */
1249 LeafKey->Count = FirstHalf;
1250 NewKey->Count = LastHalf;
1251
1252 /* Increase the count value of the root key */
1253 IndexKey->Count++;
1254
1255 /* Set the new cell in root's list */
1256 IndexKey->List[RootSelect + 1] = NewCell;
1257
1258 /* Return the root cell */
1259 return RootCell;
1260 }
1261
1262 HCELL_INDEX
1263 NTAPI
CmpSelectLeaf(IN PHHIVE Hive,IN PCM_KEY_NODE KeyNode,IN PCUNICODE_STRING Name,IN HSTORAGE_TYPE Type,IN PHCELL_INDEX * RootCell)1264 CmpSelectLeaf(IN PHHIVE Hive,
1265 IN PCM_KEY_NODE KeyNode,
1266 IN PCUNICODE_STRING Name,
1267 IN HSTORAGE_TYPE Type,
1268 IN PHCELL_INDEX *RootCell)
1269 {
1270 PCM_KEY_INDEX IndexKey, LeafKey;
1271 PCM_KEY_FAST_INDEX FastLeaf;
1272 HCELL_INDEX LeafCell, CurrentCell;
1273 ULONG SubKeyIndex;
1274 LONG Result;
1275
1276 /* Mark it as dirty */
1277 HvMarkCellDirty(Hive, KeyNode->SubKeyLists[Type], FALSE);
1278
1279 /* Get the cell */
1280 IndexKey = (PCM_KEY_INDEX)HvGetCell(Hive, KeyNode->SubKeyLists[Type]);
1281
1282 /* Check if we've got a valid key */
1283 if (!IndexKey)
1284 {
1285 /* Should not happen! */
1286 ASSERT(IndexKey != NULL);
1287 return HCELL_NIL;
1288 }
1289
1290 /* Sanity check */
1291 ASSERT(IndexKey->Signature == CM_KEY_INDEX_ROOT);
1292
1293 while (TRUE)
1294 {
1295 /* Find subkey */
1296 SubKeyIndex = CmpFindSubKeyInRoot(Hive, IndexKey, Name, &LeafCell);
1297
1298 /* Make sure we found something valid */
1299 if (SubKeyIndex & INVALID_INDEX) return HCELL_NIL;
1300
1301 /* Try to fit it into the LeafCell, if it was found */
1302 if (LeafCell != HCELL_NIL)
1303 {
1304 /* Get the leaf key */
1305 LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1306
1307 /* Check for failure */
1308 if (!LeafKey) return HCELL_NIL;
1309
1310 /* Check if it fits into this leaf and break */
1311 if (LeafKey->Count < CmpMaxIndexPerHblock)
1312 {
1313 /* Fill in the result and return it */
1314 *RootCell = &IndexKey->List[SubKeyIndex];
1315 return LeafCell;
1316 }
1317
1318 /* It didn't fit, so proceed to splitting */
1319 }
1320 else
1321 {
1322 /* Get the leaf cell at the very end */
1323 LeafCell = IndexKey->List[SubKeyIndex];
1324 LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1325
1326 /* Return an error in case of problems */
1327 if (!LeafKey) return HCELL_NIL;
1328
1329 /* Choose the cell to search from depending on the key type */
1330 if ((LeafKey->Signature == CM_KEY_FAST_LEAF) ||
1331 (LeafKey->Signature == CM_KEY_HASH_LEAF))
1332 {
1333 FastLeaf = (PCM_KEY_FAST_INDEX)LeafKey;
1334 CurrentCell = FastLeaf->List[0].Cell;
1335 }
1336 else
1337 {
1338 /* Make sure it's an index leaf */
1339 ASSERT(LeafKey->Signature == CM_KEY_INDEX_LEAF);
1340 CurrentCell = LeafKey->List[0];
1341 }
1342
1343 /* Do a name compare */
1344 Result = CmpDoCompareKeyName(Hive, Name, CurrentCell);
1345
1346 /* Check for failure */
1347 if (Result == 2) return HCELL_NIL;
1348
1349 /* Names can't be equal, ensure that */
1350 ASSERT(Result != 0);
1351
1352 /* Check if it's above */
1353 if (Result >= 0)
1354 {
1355 /* Get the cell in the index */
1356 LeafCell = IndexKey->List[SubKeyIndex];
1357 LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1358
1359 /* Return an error in case of problems */
1360 if (!LeafKey) return HCELL_NIL;
1361
1362 /* Check if it fits into this leaf */
1363 if (LeafKey->Count < CmpMaxIndexPerHblock)
1364 {
1365 /* Fill in the result and return the cell */
1366 *RootCell = &IndexKey->List[SubKeyIndex];
1367 return LeafCell;
1368 }
1369
1370 /* No, it doesn't fit, check the next adjacent leaf */
1371 if ((SubKeyIndex + 1) < IndexKey->Count)
1372 {
1373 /* Yes, there is space */
1374 LeafCell = IndexKey->List[SubKeyIndex + 1];
1375 LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1376
1377 /* Return an error in case of problems */
1378 if (!LeafKey) return HCELL_NIL;
1379
1380 /* Check if it fits and break */
1381 if (LeafKey->Count < CmpMaxIndexPerHblock)
1382 {
1383 /* Fill in the result and return the cell */
1384 *RootCell = &IndexKey->List[SubKeyIndex + 1];
1385 return LeafCell;
1386 }
1387 }
1388
1389 /* It didn't fit, so proceed to splitting */
1390 }
1391 else
1392 {
1393 /* No, it's below, check the subkey index */
1394 if (SubKeyIndex > 0)
1395 {
1396 /* There should be space at the leaf one before that */
1397 LeafCell = IndexKey->List[SubKeyIndex - 1];
1398 LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1399
1400 /* Return an error in case of problems */
1401 if (!LeafKey) return HCELL_NIL;
1402
1403 /* Check if it fits and break */
1404 if (LeafKey->Count < CmpMaxIndexPerHblock)
1405 {
1406 /* Fill in the result and return the cell */
1407 *RootCell = &IndexKey->List[SubKeyIndex - 1];
1408 return LeafCell;
1409 }
1410 }
1411 else
1412 {
1413 /* Use the first leaf, if possible */
1414 LeafCell = IndexKey->List[0];
1415 LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1416
1417 /* Return an error in case of problems */
1418 if (!LeafKey) return HCELL_NIL;
1419
1420 /* Check if it fits and break */
1421 if (LeafKey->Count < CmpMaxIndexPerHblock)
1422 {
1423 /* Fill in the result and return the cell */
1424 *RootCell = &IndexKey->List[0];
1425 return LeafCell;
1426 }
1427 }
1428
1429 /* It didn't fit into either, so proceed to splitting */
1430 }
1431 }
1432
1433 /* We need to split */
1434 CurrentCell = CmpSplitLeaf(Hive,
1435 KeyNode->SubKeyLists[Type],
1436 SubKeyIndex,
1437 Type);
1438
1439 /* Return failure in case splitting failed */
1440 if (CurrentCell == HCELL_NIL) return CurrentCell;
1441
1442 /* Set the SubKeyLists value with the new key */
1443 KeyNode->SubKeyLists[Type] = CurrentCell;
1444
1445 /* Get the new cell */
1446 IndexKey = (PCM_KEY_INDEX)HvGetCell(Hive, KeyNode->SubKeyLists[Type]);
1447
1448 /* Return in case of failure */
1449 if (!IndexKey) return HCELL_NIL;
1450
1451 /* Make sure the new key became index root */
1452 ASSERT(IndexKey->Signature == CM_KEY_INDEX_ROOT);
1453
1454 /* Now loop over with the new IndexKey value, which definately
1455 * has the space now
1456 */
1457 }
1458
1459 /* Shouldn't come here */
1460 return HCELL_NIL;
1461 }
1462
1463 BOOLEAN
1464 NTAPI
CmpAddSubKey(IN PHHIVE Hive,IN HCELL_INDEX Parent,IN HCELL_INDEX Child)1465 CmpAddSubKey(IN PHHIVE Hive,
1466 IN HCELL_INDEX Parent,
1467 IN HCELL_INDEX Child)
1468 {
1469 PCM_KEY_NODE KeyNode;
1470 PCM_KEY_INDEX Index;
1471 PCM_KEY_FAST_INDEX OldIndex;
1472 UNICODE_STRING Name;
1473 HCELL_INDEX IndexCell = HCELL_NIL, CellToRelease = HCELL_NIL, LeafCell;
1474 PHCELL_INDEX RootPointer = NULL;
1475 ULONG Type, i;
1476 BOOLEAN IsCompressed;
1477 PAGED_CODE();
1478
1479 /* Get the key node */
1480 KeyNode = (PCM_KEY_NODE)HvGetCell(Hive, Child);
1481 if (!KeyNode)
1482 {
1483 /* Shouldn't happen */
1484 ASSERT(FALSE);
1485 return FALSE;
1486 }
1487
1488 /* Check if the name is compressed */
1489 if (KeyNode->Flags & KEY_COMP_NAME)
1490 {
1491 /* Remember for later */
1492 IsCompressed = TRUE;
1493
1494 /* Create the compressed name and allocate it */
1495 Name.Length = CmpCompressedNameSize(KeyNode->Name, KeyNode->NameLength);
1496 Name.MaximumLength = Name.Length;
1497 Name.Buffer = Hive->Allocate(Name.Length, TRUE, TAG_CM);
1498 if (!Name.Buffer)
1499 {
1500 /* Release the cell and fail */
1501 HvReleaseCell(Hive, Child);
1502 ASSERT(FALSE);
1503 return FALSE;
1504 }
1505
1506 /* Copy the compressed name */
1507 CmpCopyCompressedName(Name.Buffer,
1508 Name.MaximumLength,
1509 KeyNode->Name,
1510 KeyNode->NameLength);
1511 }
1512 else
1513 {
1514 /* Remember for later */
1515 IsCompressed = FALSE;
1516
1517 /* Build the unicode string */
1518 Name.Length = KeyNode->NameLength;
1519 Name.MaximumLength = KeyNode->NameLength;
1520 Name.Buffer = &KeyNode->Name[0];
1521 }
1522
1523 /* Release the cell */
1524 HvReleaseCell(Hive, Child);
1525
1526 /* Get the parent node */
1527 KeyNode = (PCM_KEY_NODE)HvGetCell(Hive, Parent);
1528 if (!KeyNode)
1529 {
1530 /* Not handled */
1531 ASSERT(FALSE);
1532 }
1533
1534 /* Find out the type of the cell, and check if this is the first subkey */
1535 Type = HvGetCellType(Child);
1536 if (!KeyNode->SubKeyCounts[Type])
1537 {
1538 /* Allocate a fast leaf */
1539 IndexCell = HvAllocateCell(Hive, sizeof(CM_KEY_FAST_INDEX), Type, HCELL_NIL);
1540 if (IndexCell == HCELL_NIL)
1541 {
1542 /* Not handled */
1543 ASSERT(FALSE);
1544 }
1545
1546 /* Get the leaf cell */
1547 Index = (PCM_KEY_INDEX)HvGetCell(Hive, IndexCell);
1548 if (!Index)
1549 {
1550 /* Shouldn't happen */
1551 ASSERT(FALSE);
1552 }
1553
1554 /* Now check what kind of hive we're dealing with */
1555 if (Hive->Version >= 5)
1556 {
1557 /* XP Hive: Use hash leaf */
1558 Index->Signature = CM_KEY_HASH_LEAF;
1559 }
1560 else if (Hive->Version >= 3)
1561 {
1562 /* Windows 2000 and ReactOS: Use fast leaf */
1563 Index->Signature = CM_KEY_FAST_LEAF;
1564 }
1565 else
1566 {
1567 /* NT 4: Use index leaf */
1568 Index->Signature = CM_KEY_INDEX_LEAF;
1569 }
1570
1571 /* Setup the index list */
1572 Index->Count = 0;
1573 KeyNode->SubKeyLists[Type] = IndexCell;
1574 }
1575 else
1576 {
1577 /* We already have an index, get it */
1578 Index = (PCM_KEY_INDEX)HvGetCell(Hive, KeyNode->SubKeyLists[Type]);
1579 if (!Index)
1580 {
1581 /* Not handled */
1582 ASSERT(FALSE);
1583 }
1584
1585 /* Remember to release the cell later */
1586 CellToRelease = KeyNode->SubKeyLists[Type];
1587
1588 /* Check if this is a fast leaf that's gotten too full */
1589 if ((Index->Signature == CM_KEY_FAST_LEAF) &&
1590 (Index->Count >= CmpMaxFastIndexPerHblock))
1591 {
1592 DPRINT("Doing Fast->Slow Leaf conversion\n");
1593
1594 /* Mark this cell as dirty */
1595 HvMarkCellDirty(Hive, CellToRelease, FALSE);
1596
1597 /* Convert */
1598 OldIndex = (PCM_KEY_FAST_INDEX)Index;
1599
1600 for (i = 0; i < OldIndex->Count; i++)
1601 {
1602 Index->List[i] = OldIndex->List[i].Cell;
1603 }
1604
1605 /* Set the new type value */
1606 Index->Signature = CM_KEY_INDEX_LEAF;
1607 }
1608 else if (((Index->Signature == CM_KEY_INDEX_LEAF) ||
1609 (Index->Signature == CM_KEY_HASH_LEAF)) &&
1610 (Index->Count >= CmpMaxIndexPerHblock))
1611 {
1612 /* This is an old/hashed leaf that's gotten too large, root it */
1613 IndexCell = HvAllocateCell(Hive,
1614 sizeof(CM_KEY_INDEX) +
1615 sizeof(HCELL_INDEX),
1616 Type,
1617 HCELL_NIL);
1618 if (IndexCell == HCELL_NIL)
1619 {
1620 /* Not handled */
1621 ASSERT(FALSE);
1622 }
1623
1624 /* Get the index cell */
1625 Index = (PCM_KEY_INDEX)HvGetCell(Hive, IndexCell);
1626 if (!Index)
1627 {
1628 /* Shouldn't happen */
1629 ASSERT(FALSE);
1630 }
1631
1632 /* Mark the index as a root, and set the index cell */
1633 Index->Signature = CM_KEY_INDEX_ROOT;
1634 Index->Count = 1;
1635 Index->List[0] = KeyNode->SubKeyLists[Type];
1636 KeyNode->SubKeyLists[Type] = IndexCell;
1637 }
1638 }
1639
1640 /* Now we can choose the leaf cell */
1641 LeafCell = KeyNode->SubKeyLists[Type];
1642
1643 /* Check if we turned the index into a root */
1644 if (Index->Signature == CM_KEY_INDEX_ROOT)
1645 {
1646 DPRINT("Leaf->Root Index Conversion\n");
1647
1648 /* Get the leaf where to add the new entry (the routine will do
1649 * the splitting if necessary)
1650 */
1651 LeafCell = CmpSelectLeaf(Hive, KeyNode, &Name, Type, &RootPointer);
1652 if (LeafCell == HCELL_NIL)
1653 {
1654 /* Not handled */
1655 ASSERT(FALSE);
1656 }
1657 }
1658
1659 /* Add our leaf cell */
1660 LeafCell = CmpAddToLeaf(Hive, LeafCell, Child, &Name);
1661 if (LeafCell == HCELL_NIL)
1662 {
1663 /* Not handled */
1664 ASSERT(FALSE);
1665 }
1666
1667 /* Update the key counts */
1668 KeyNode->SubKeyCounts[Type]++;
1669
1670 /* Check if caller wants us to return the leaf */
1671 if (RootPointer)
1672 {
1673 /* Return it */
1674 *RootPointer = LeafCell;
1675 }
1676 else
1677 {
1678 /* Otherwise, mark it as the list index for the cell */
1679 KeyNode->SubKeyLists[Type] = LeafCell;
1680 }
1681
1682 /* If the name was compressed, free our copy */
1683 if (IsCompressed) Hive->Free(Name.Buffer, 0);
1684
1685 /* Release all our cells */
1686 if (IndexCell != HCELL_NIL) HvReleaseCell(Hive, IndexCell);
1687 if (CellToRelease != HCELL_NIL) HvReleaseCell(Hive, CellToRelease);
1688 HvReleaseCell(Hive, Parent);
1689 return TRUE;
1690 }
1691
1692 BOOLEAN
1693 NTAPI
CmpRemoveSubKey(IN PHHIVE Hive,IN HCELL_INDEX ParentKey,IN HCELL_INDEX TargetKey)1694 CmpRemoveSubKey(IN PHHIVE Hive,
1695 IN HCELL_INDEX ParentKey,
1696 IN HCELL_INDEX TargetKey)
1697 {
1698 PCM_KEY_NODE Node;
1699 UNICODE_STRING SearchName;
1700 BOOLEAN IsCompressed;
1701 WCHAR Buffer[50];
1702 HCELL_INDEX RootCell = HCELL_NIL, LeafCell, ChildCell;
1703 PCM_KEY_INDEX Root = NULL, Leaf;
1704 PCM_KEY_FAST_INDEX Child;
1705 ULONG Storage, RootIndex = INVALID_INDEX, LeafIndex;
1706 BOOLEAN Result = FALSE;
1707 HCELL_INDEX CellToRelease1 = HCELL_NIL, CellToRelease2 = HCELL_NIL;
1708
1709 /* Get the target key node */
1710 Node = (PCM_KEY_NODE)HvGetCell(Hive, TargetKey);
1711 if (!Node) return FALSE;
1712
1713 /* Make sure it's dirty, then release it */
1714 ASSERT(HvIsCellDirty(Hive, TargetKey));
1715 HvReleaseCell(Hive, TargetKey);
1716
1717 /* Check if the name is compressed */
1718 if (Node->Flags & KEY_COMP_NAME)
1719 {
1720 /* Remember for later */
1721 IsCompressed = TRUE;
1722
1723 /* Build the search name */
1724 SearchName.Length = CmpCompressedNameSize(Node->Name,
1725 Node->NameLength);
1726 SearchName.MaximumLength = SearchName.Length;
1727
1728 /* Do we need an extra bufer? */
1729 if (SearchName.MaximumLength > sizeof(Buffer))
1730 {
1731 /* Allocate one */
1732 SearchName.Buffer = Hive->Allocate(SearchName.Length, TRUE, TAG_CM);
1733 if (!SearchName.Buffer) return FALSE;
1734 }
1735 else
1736 {
1737 /* Otherwise, use our local stack buffer */
1738 SearchName.Buffer = Buffer;
1739 }
1740
1741 /* Copy the compressed name */
1742 CmpCopyCompressedName(SearchName.Buffer,
1743 SearchName.MaximumLength,
1744 Node->Name,
1745 Node->NameLength);
1746 }
1747 else
1748 {
1749 /* It's not compressed, build the name directly from the node */
1750 IsCompressed = FALSE;
1751 SearchName.Length = Node->NameLength;
1752 SearchName.MaximumLength = Node->NameLength;
1753 SearchName.Buffer = Node->Name;
1754 }
1755
1756 /* Now get the parent node */
1757 Node = (PCM_KEY_NODE)HvGetCell(Hive, ParentKey);
1758 if (!Node) goto Exit;
1759
1760 /* Make sure it's dirty, then release it */
1761 ASSERT(HvIsCellDirty(Hive, ParentKey));
1762 HvReleaseCell(Hive, ParentKey);
1763
1764 /* Get the storage type and make sure it's not empty */
1765 Storage = HvGetCellType(TargetKey);
1766 ASSERT(Node->SubKeyCounts[Storage] != 0);
1767 //ASSERT(HvIsCellAllocated(Hive, Node->SubKeyLists[Storage]));
1768
1769 /* Get the leaf cell now */
1770 LeafCell = Node->SubKeyLists[Storage];
1771 Leaf = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1772 if (!Leaf) goto Exit;
1773
1774 /* Remember to release it later */
1775 CellToRelease1 = LeafCell;
1776
1777 /* Check if the leaf is a root */
1778 if (Leaf->Signature == CM_KEY_INDEX_ROOT)
1779 {
1780 /* Find the child inside the root */
1781 RootIndex = CmpFindSubKeyInRoot(Hive, Leaf, &SearchName, &ChildCell);
1782 if (RootIndex & INVALID_INDEX) goto Exit;
1783 ASSERT(ChildCell != FALSE);
1784
1785 /* The root cell is now this leaf */
1786 Root = Leaf;
1787 RootCell = LeafCell;
1788
1789 /* And the new leaf is now this child */
1790 LeafCell = ChildCell;
1791 Leaf = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1792 if (!Leaf) goto Exit;
1793
1794 /* Remember to release it later */
1795 CellToRelease2 = LeafCell;
1796 }
1797
1798 /* Make sure the leaf is valid */
1799 ASSERT((Leaf->Signature == CM_KEY_INDEX_LEAF) ||
1800 (Leaf->Signature == CM_KEY_FAST_LEAF) ||
1801 (Leaf->Signature == CM_KEY_HASH_LEAF));
1802
1803 /* Now get the child in the leaf */
1804 LeafIndex = CmpFindSubKeyInLeaf(Hive, Leaf, &SearchName, &ChildCell);
1805 if (LeafIndex & INVALID_INDEX) goto Exit;
1806 ASSERT(ChildCell != HCELL_NIL);
1807
1808 /* Decrement key counts and check if this was the last leaf entry */
1809 Node->SubKeyCounts[Storage]--;
1810 if (!(--Leaf->Count))
1811 {
1812 /* Free the leaf */
1813 HvFreeCell(Hive, LeafCell);
1814
1815 /* Check if we were inside a root */
1816 if (Root)
1817 {
1818 /* Decrease the root count too, since the leaf is going away */
1819 if (!(--Root->Count))
1820 {
1821 /* The root is gone too,n ow */
1822 HvFreeCell(Hive, RootCell);
1823 Node->SubKeyLists[Storage] = HCELL_NIL;
1824 }
1825 else if (RootIndex < Root->Count)
1826 {
1827 /* Bring everything up by one */
1828 RtlMoveMemory(&Root->List[RootIndex],
1829 &Root->List[RootIndex + 1],
1830 (Root->Count - RootIndex) * sizeof(HCELL_INDEX));
1831 }
1832 }
1833 else
1834 {
1835 /* Otherwise, just clear the cell */
1836 Node->SubKeyLists[Storage] = HCELL_NIL;
1837 }
1838 }
1839 else if (LeafIndex < Leaf->Count)
1840 {
1841 /* Was the leaf a normal index? */
1842 if (Leaf->Signature == CM_KEY_INDEX_LEAF)
1843 {
1844 /* Bring everything up by one */
1845 RtlMoveMemory(&Leaf->List[LeafIndex],
1846 &Leaf->List[LeafIndex + 1],
1847 (Leaf->Count - LeafIndex) * sizeof(HCELL_INDEX));
1848 }
1849 else
1850 {
1851 /* This is a fast index, bring everything up by one */
1852 Child = (PCM_KEY_FAST_INDEX)Leaf;
1853 RtlMoveMemory(&Child->List[LeafIndex],
1854 &Child->List[LeafIndex+1],
1855 (Child->Count - LeafIndex) * sizeof(CM_INDEX));
1856 }
1857 }
1858
1859 /* If we got here, now we're done */
1860 Result = TRUE;
1861
1862 Exit:
1863 /* Release any cells we may have been holding */
1864 if (CellToRelease1 != HCELL_NIL) HvReleaseCell(Hive, CellToRelease1);
1865 if (CellToRelease2 != HCELL_NIL) HvReleaseCell(Hive, CellToRelease2);
1866
1867 /* Check if the name was compressed and not inside our local buffer */
1868 if ((IsCompressed) && (SearchName.MaximumLength > sizeof(Buffer)))
1869 {
1870 /* Free the buffer we allocated */
1871 Hive->Free(SearchName.Buffer, 0);
1872 }
1873
1874 /* Return the result */
1875 return Result;
1876 }
1877