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