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