projects / reactos.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
Use memory wrappers instead of ExAllocatePool/ExFreePool directly
[reactos.git] / reactos / 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 /* Lookup the name in the root */
737 Found = CmpFindSubKeyInRoot(Hive,
738 IndexRoot,
739 SearchName,
740 &SubKey);
741
742 /* Release the previous cell */
743 ASSERT(CellToRelease != HCELL_NIL);
744 HvReleaseCell(Hive, CellToRelease);
745
746 /* Make sure we found something valid */
747 if (Found & 0x80000000) break;
748
749 /* Get the new Index Root and set the new cell to be released */
750 if (SubKey == HCELL_NIL) continue;
751 CellToRelease = SubKey;
752 IndexRoot = (PCM_KEY_INDEX)HvGetCell(Hive, SubKey);
753 }
754
755 /* Make sure the signature is what we expect it to be */
756 ASSERT((IndexRoot->Signature == CM_KEY_INDEX_LEAF) ||
757 (IndexRoot->Signature == CM_KEY_FAST_LEAF) ||
758 (IndexRoot->Signature == CM_KEY_HASH_LEAF));
759
760 /* Check if this isn't a hashed leaf */
761 if (IndexRoot->Signature != CM_KEY_HASH_LEAF)
762 {
763 /* Find the subkey in the leaf */
764 Found = CmpFindSubKeyInLeaf(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 a valid index */
774 if (Found & 0x80000000) break;
775 }
776 else
777 {
778 /* Find the subkey in the hash */
779 SubKey = CmpFindSubKeyByHash(Hive,
780 (PCM_KEY_FAST_INDEX)IndexRoot,
781 SearchName);
782
783 /* Release the previous cell */
784 ASSERT(CellToRelease != HCELL_NIL);
785 HvReleaseCell(Hive, CellToRelease);
786 }
787
788 /* Make sure we got a valid subkey and return it */
789 if (SubKey != HCELL_NIL) return SubKey;
790 }
791 }
792
793 /* If we got here, then we failed */
794 return HCELL_NIL;
795 }
796
797 BOOLEAN
798 NTAPI
799 CmpMarkIndexDirty(IN PHHIVE Hive,
800 IN HCELL_INDEX ParentKey,
801 IN HCELL_INDEX TargetKey)
802 {
803 PCM_KEY_NODE Node;
804 UNICODE_STRING SearchName;
805 BOOLEAN IsCompressed;
806 ULONG i, Result;
807 PCM_KEY_INDEX Index;
808 HCELL_INDEX IndexCell, Child = HCELL_NIL, CellToRelease = HCELL_NIL;
809
810 /* Get the target key node */
811 Node = (PCM_KEY_NODE)HvGetCell(Hive, TargetKey);
812 if (!Node) return FALSE;
813
814 /* Check if it's compressed */
815 if (Node->Flags & KEY_COMP_NAME)
816 {
817 /* Remember this for later */
818 IsCompressed = TRUE;
819
820 /* Build the search name */
821 SearchName.Length = CmpCompressedNameSize(Node->Name,
822 Node->NameLength);
823 SearchName.MaximumLength = SearchName.Length;
824 SearchName.Buffer = CmpAllocate(SearchName.Length,
825 TRUE,
826 TAG_CM);
827 if (!SearchName.Buffer)
828 {
829 /* Fail */
830 HvReleaseCell(Hive, TargetKey);
831 return FALSE;
832 }
833
834 /* Copy it */
835 CmpCopyCompressedName(SearchName.Buffer,
836 SearchName.MaximumLength,
837 Node->Name,
838 Node->NameLength);
839 }
840 else
841 {
842 /* Name isn't compressed, build it directly from the node */
843 IsCompressed = FALSE;
844 SearchName.Length = Node->NameLength;
845 SearchName.MaximumLength = Node->NameLength;
846 SearchName.Buffer = Node->Name;
847 }
848
849 /* We can release the target key now */
850 HvReleaseCell(Hive, TargetKey);
851
852 /* Now get the parent key node */
853 Node = (PCM_KEY_NODE)HvGetCell(Hive, ParentKey);
854 if (!Node) goto Quickie;
855
856 /* Loop all hive storage */
857 for (i = 0; i < Hive->StorageTypeCount; i++)
858 {
859 /* Check if any subkeys are in this index */
860 if (Node->SubKeyCounts[i])
861 {
862 /* Get the cell index */
863 //ASSERT(HvIsCellAllocated(Hive, Node->SubKeyLists[i]));
864 IndexCell = Node->SubKeyLists[i];
865
866 /* Check if we had anything to release from before */
867 if (CellToRelease != HCELL_NIL)
868 {
869 /* Release it now */
870 HvReleaseCell(Hive, CellToRelease);
871 CellToRelease = HCELL_NIL;
872 }
873
874 /* Get the key index for the cell */
875 Index = (PCM_KEY_INDEX)HvGetCell(Hive, IndexCell);
876 if (!Index) goto Quickie;
877
878 /* Release it at the next iteration or below */
879 CellToRelease = IndexCell;
880
881 /* Check if this is a root */
882 if (Index->Signature == CM_KEY_INDEX_ROOT)
883 {
884 /* Get the child inside the root */
885 Result = CmpFindSubKeyInRoot(Hive, Index, &SearchName, &Child);
886 if (Result & 0x80000000) goto Quickie;
887 if (Child == HCELL_NIL) continue;
888
889 /* We found it, mark the cell dirty */
890 HvMarkCellDirty(Hive, IndexCell, FALSE);
891
892 /* Check if we had anything to release from before */
893 if (CellToRelease != HCELL_NIL)
894 {
895 /* Release it now */
896 HvReleaseCell(Hive, CellToRelease);
897 CellToRelease = HCELL_NIL;
898 }
899
900 /* Now this child is the index, get the actual key index */
901 IndexCell = Child;
902 Index = (PCM_KEY_INDEX)HvGetCell(Hive, Child);
903 if (!Index) goto Quickie;
904
905 /* Release it later */
906 CellToRelease = Child;
907 }
908
909 /* Make sure this is a valid index */
910 ASSERT((Index->Signature == CM_KEY_INDEX_LEAF) ||
911 (Index->Signature == CM_KEY_FAST_LEAF) ||
912 (Index->Signature == CM_KEY_HASH_LEAF));
913
914 /* Find the child in the leaf */
915 Result = CmpFindSubKeyInLeaf(Hive, Index, &SearchName, &Child);
916 if (Result & 0x80000000) goto Quickie;
917 if (Child != HCELL_NIL)
918 {
919 /* We found it, free the name now */
920 if (IsCompressed) CmpFree(SearchName.Buffer, 0);
921
922 /* Release the parent key */
923 HvReleaseCell(Hive, ParentKey);
924
925 /* Check if we had a left over cell to release */
926 if (CellToRelease != HCELL_NIL)
927 {
928 /* Release it */
929 HvReleaseCell(Hive, CellToRelease);
930 }
931
932 /* And mark the index cell dirty */
933 HvMarkCellDirty(Hive, IndexCell, FALSE);
934 return TRUE;
935 }
936 }
937 }
938
939 Quickie:
940 /* Release any cells that we still hold */
941 if (Node) HvReleaseCell(Hive, ParentKey);
942 if (CellToRelease != HCELL_NIL) HvReleaseCell(Hive, CellToRelease);
943
944 /* Free the search name and return failure */
945 if (IsCompressed) CmpFree(SearchName.Buffer, 0);
946 return FALSE;
947 }
948
949 HCELL_INDEX
950 NTAPI
951 CmpAddToLeaf(IN PHHIVE Hive,
952 IN HCELL_INDEX LeafCell,
953 IN HCELL_INDEX NewKey,
954 IN PUNICODE_STRING Name)
955 {
956 PCM_KEY_INDEX Leaf;
957 PCM_KEY_FAST_INDEX FastLeaf;
958 ULONG Size, OldSize, EntrySize, i, j;
959 HCELL_INDEX NewCell, Child;
960 LONG Result;
961
962 /* Mark the leaf dirty */
963 HvMarkCellDirty(Hive, LeafCell, FALSE);
964
965 /* Get the leaf cell */
966 Leaf = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
967 if (!Leaf)
968 {
969 /* Shouldn't happen */
970 ASSERT(FALSE);
971 return HCELL_NIL;
972 }
973
974 /* Release it */
975 HvReleaseCell(Hive, LeafCell);
976
977 /* Check if this is an index leaf */
978 if (Leaf->Signature == CM_KEY_INDEX_LEAF)
979 {
980 /* This is an old-style leaf */
981 FastLeaf = NULL;
982 EntrySize = sizeof(HCELL_INDEX);
983 }
984 else
985 {
986 /* Sanity check */
987 ASSERT((Leaf->Signature == CM_KEY_FAST_LEAF) ||
988 (Leaf->Signature == CM_KEY_HASH_LEAF));
989
990 /* This is a new-style optimized fast (or hash) leaf */
991 FastLeaf = (PCM_KEY_FAST_INDEX)Leaf;
992 EntrySize = sizeof(CM_INDEX);
993 }
994
995 /* Get the current size of the leaf */
996 OldSize = HvGetCellSize(Hive, Leaf);
997
998 /* Calculate the size of the free entries */
999 Size = OldSize;
1000 Size -= EntrySize * Leaf->Count + FIELD_OFFSET(CM_KEY_INDEX, List);
1001
1002 /* Assume we'll re-use the same leaf */
1003 NewCell = LeafCell;
1004
1005 /* Check if we're out of space */
1006 if ((Size / EntrySize) < 1)
1007 {
1008 /* Grow the leaf by 1.5x, making sure we can at least fit this entry */
1009 Size = OldSize + OldSize / 2;
1010 if (Size < (OldSize + EntrySize)) Size = OldSize + EntrySize;
1011
1012 /* Re-allocate the leaf */
1013 NewCell = HvReallocateCell(Hive, LeafCell, Size);
1014 if (NewCell == HCELL_NIL) return HCELL_NIL;
1015
1016 /* Get the leaf cell */
1017 Leaf = (PCM_KEY_INDEX)HvGetCell(Hive, NewCell);
1018 if (!Leaf)
1019 {
1020 /* This shouldn't happen */
1021 ASSERT(FALSE);
1022 return HCELL_NIL;
1023 }
1024
1025 /* Release the cell */
1026 HvReleaseCell(Hive, NewCell);
1027
1028 /* Update the fast leaf pointer if we had one */
1029 if (FastLeaf) FastLeaf = (PCM_KEY_FAST_INDEX)Leaf;
1030 }
1031
1032 /* Find the insertion point for our entry */
1033 i = CmpFindSubKeyInLeaf(Hive, Leaf, Name, &Child);
1034 if (i & 0x80000000) return HCELL_NIL;
1035 ASSERT(Child == HCELL_NIL);
1036
1037 /* Check if we're not last */
1038 if (i != Leaf->Count)
1039 {
1040 /* Find out where we should go */
1041 Result = CmpCompareInIndex(Hive,
1042 Name,
1043 i,
1044 Leaf,
1045 &Child);
1046 if (Result == 2) return HCELL_NIL;
1047 ASSERT(Result != 0);
1048
1049 /* Check if we come after */
1050 if (Result > 0)
1051 {
1052 /* We do, insert us after the key */
1053 ASSERT(Result == 1);
1054 i++;
1055 }
1056
1057 /* Check if we're still not last */
1058 if (i != Leaf->Count)
1059 {
1060 /* Check if we had a fast leaf or not */
1061 if (FastLeaf)
1062 {
1063 /* Copy the fast indexes */
1064 RtlMoveMemory(&FastLeaf->List[i + 1],
1065 &FastLeaf->List[i],
1066 (FastLeaf->Count - i) * sizeof(CM_INDEX));
1067 }
1068 else
1069 {
1070 /* Copy the indexes themselves */
1071 RtlMoveMemory(&Leaf->List[i + 1],
1072 &Leaf->List[i],
1073 (Leaf->Count - i) * sizeof(HCELL_INDEX));
1074 }
1075 }
1076 }
1077
1078 /* Check if this is a new-style leaf */
1079 if (FastLeaf)
1080 {
1081 /* Set our cell */
1082 FastLeaf->List[i].Cell = NewKey;
1083
1084 /* Check if this is a hash leaf */
1085 if( FastLeaf->Signature == CM_KEY_HASH_LEAF )
1086 {
1087 /* Set our hash key */
1088 FastLeaf->List[i].HashKey = CmpComputeHashKey(0, Name, FALSE);
1089 }
1090 else
1091 {
1092 /* First, clear the name */
1093 FastLeaf->List[i].NameHint[0] = 0;
1094 FastLeaf->List[i].NameHint[1] = 0;
1095 FastLeaf->List[i].NameHint[2] = 0;
1096 FastLeaf->List[i].NameHint[3] = 0;
1097
1098 /* Now, figure out if we can fit */
1099 if (Name->Length / sizeof(WCHAR) < 4)
1100 {
1101 /* We can fit, use our length */
1102 j = Name->Length / sizeof(WCHAR);
1103 }
1104 else
1105 {
1106 /* We can't, use a maximum of 4 */
1107 j = 4;
1108 }
1109
1110 /* Now fill out the name hint */
1111 do
1112 {
1113 /* Look for invalid characters and break out if we found one */
1114 if ((USHORT)Name->Buffer[j - 1] > (UCHAR)-1) break;
1115
1116 /* Otherwise, copy the a character */
1117 FastLeaf->List[i].NameHint[j - 1] = (UCHAR)Name->Buffer[j - 1];
1118 } while (--j > 0);
1119 }
1120 }
1121 else
1122 {
1123 /* This is an old-style leaf, just set our index directly */
1124 Leaf->List[i] = NewKey;
1125 }
1126
1127 /* Update the leaf count and return the new cell */
1128 Leaf->Count += 1;
1129 return NewCell;
1130 }
1131
1132 HCELL_INDEX
1133 NTAPI
1134 CmpSplitLeaf(IN PHHIVE Hive,
1135 IN HCELL_INDEX RootCell,
1136 IN ULONG RootSelect,
1137 IN HSTORAGE_TYPE Type)
1138 {
1139 PCM_KEY_INDEX IndexKey, LeafKey, NewKey;
1140 PCM_KEY_FAST_INDEX FastLeaf;
1141 HCELL_INDEX LeafCell, NewCell;
1142 ULONG FirstHalf, LastHalf;
1143 ULONG EntrySize, TotalSize;
1144
1145 /* Get the cell */
1146 IndexKey = (PCM_KEY_INDEX)HvGetCell(Hive, RootCell);
1147
1148 /* Check if we've got valid IndexKey */
1149 if (!IndexKey) return HCELL_NIL;
1150
1151 /* Get the leaf cell and key */
1152 LeafCell = IndexKey->List[RootSelect];
1153 LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1154
1155 /* Check if we've got valid LeafKey */
1156 if (!LeafKey) return HCELL_NIL;
1157
1158 /* We are going to divide this leaf into two halves */
1159 FirstHalf = (LeafKey->Count / 2);
1160 LastHalf = LeafKey->Count - FirstHalf;
1161
1162 /* Now check what kind of hive we're dealing with,
1163 * and compute entry size
1164 */
1165 if (Hive->Version >= 5)
1166 {
1167 /* XP Hive: Use hash leaf */
1168 ASSERT(LeafKey->Signature == CM_KEY_HASH_LEAF);
1169 EntrySize = sizeof(CM_INDEX);
1170 }
1171 else
1172 {
1173 /* Use index leaf */
1174 ASSERT(LeafKey->Signature == CM_KEY_INDEX_LEAF);
1175 EntrySize = sizeof(HCELL_INDEX);
1176 }
1177
1178 /* Compute the total size */
1179 TotalSize = (EntrySize * LastHalf) + FIELD_OFFSET(CM_KEY_INDEX, List) + 1;
1180
1181 /* Mark the leaf cell dirty */
1182 HvMarkCellDirty(Hive, LeafCell, FALSE);
1183
1184 /* Make sure its type is the same */
1185 ASSERT(HvGetCellType(LeafCell) == Type);
1186
1187 /* Allocate the cell, fail in case of error */
1188 NewCell = HvAllocateCell(Hive, TotalSize, Type, LeafCell);
1189 if (NewCell == HCELL_NIL) return NewCell;
1190
1191 /* Get the key */
1192 NewKey = (PCM_KEY_INDEX)HvGetCell(Hive, NewCell);
1193 if (!NewKey)
1194 {
1195 /* Free the cell and exit - should not happen! */
1196 ASSERT(FALSE);
1197 HvFreeCell(Hive, NewCell);
1198 return HCELL_NIL;
1199 }
1200
1201 /* Release the newly created cell */
1202 HvReleaseCell(Hive, NewCell);
1203
1204 /* Set its signature according to the version of the hive */
1205 if (Hive->Version >= 5)
1206 {
1207 /* XP Hive: Use hash leaf signature */
1208 NewKey->Signature = CM_KEY_HASH_LEAF;
1209 }
1210 else
1211 {
1212 /* Use index leaf signature */
1213 NewKey->Signature = CM_KEY_INDEX_LEAF;
1214 }
1215
1216 /* Calculate the size of the free entries in the root key */
1217 TotalSize = HvGetCellSize(Hive, IndexKey) -
1218 (IndexKey->Count * sizeof(HCELL_INDEX)) -
1219 FIELD_OFFSET(CM_KEY_INDEX, List);
1220
1221 /* Check if we're out of space */
1222 if (TotalSize / sizeof(HCELL_INDEX) < 1)
1223 {
1224 /* Grow the leaf by one more entry */
1225 TotalSize = HvGetCellSize(Hive, IndexKey) + sizeof(HCELL_INDEX);
1226
1227 /* Re-allocate the root */
1228 RootCell = HvReallocateCell(Hive, RootCell, TotalSize);
1229 if (RootCell == HCELL_NIL)
1230 {
1231 /* Free the cell and exit */
1232 HvFreeCell(Hive, NewCell);
1233 return HCELL_NIL;
1234 }
1235
1236 /* Get the leaf cell */
1237 IndexKey = (PCM_KEY_INDEX)HvGetCell(Hive, RootCell);
1238 if (!IndexKey)
1239 {
1240 /* This shouldn't happen */
1241 ASSERT(FALSE);
1242 return HCELL_NIL;
1243 }
1244 }
1245
1246 /* Splitting is done, now we need to copy the contents,
1247 * according to the hive version
1248 */
1249 if (Hive->Version >= 5)
1250 {
1251 /* Copy the fast indexes */
1252 FastLeaf = (PCM_KEY_FAST_INDEX)LeafKey;
1253 RtlMoveMemory(&NewKey->List[0],
1254 &FastLeaf->List[FirstHalf],
1255 LastHalf * EntrySize);
1256 }
1257 else
1258 {
1259 /* Copy the indexes themselves */
1260 RtlMoveMemory(&NewKey->List[0],
1261 &LeafKey->List[FirstHalf],
1262 LastHalf * EntrySize);
1263 }
1264
1265 /* Shift the data inside the root key */
1266 if (RootSelect < (IndexKey->Count - 1))
1267 {
1268 RtlMoveMemory(&IndexKey->List[RootSelect + 2],
1269 &IndexKey->List[RootSelect + 1],
1270 IndexKey->Count -
1271 (RootSelect + 1) * sizeof(HCELL_INDEX));
1272 }
1273
1274 /* Make sure both old and new computed counts are valid */
1275 ASSERT(FirstHalf != 0);
1276 ASSERT(LastHalf != 0);
1277
1278 /* Update the count value of old and new keys */
1279 LeafKey->Count = FirstHalf;
1280 NewKey->Count = LastHalf;
1281
1282 /* Increase the count value of the root key */
1283 IndexKey->Count++;
1284
1285 /* Set the new cell in root's list */
1286 IndexKey->List[RootSelect + 1] = NewCell;
1287
1288 /* Return the root cell */
1289 return RootCell;
1290 }
1291
1292 HCELL_INDEX
1293 NTAPI
1294 CmpSelectLeaf(IN PHHIVE Hive,
1295 IN PCM_KEY_NODE KeyNode,
1296 IN PUNICODE_STRING Name,
1297 IN HSTORAGE_TYPE Type,
1298 IN PHCELL_INDEX *RootCell)
1299 {
1300 PCM_KEY_INDEX IndexKey, LeafKey;
1301 PCM_KEY_FAST_INDEX FastLeaf;
1302 HCELL_INDEX LeafCell, CurrentCell;
1303 ULONG SubKeyIndex;
1304 LONG Result;
1305
1306 /* Mark it as dirty */
1307 HvMarkCellDirty(Hive, KeyNode->SubKeyLists[Type], FALSE);
1308
1309 /* Get the cell */
1310 IndexKey = (PCM_KEY_INDEX)HvGetCell(Hive, KeyNode->SubKeyLists[Type]);
1311
1312 /* Check if we've got a valid key */
1313 if (!IndexKey)
1314 {
1315 /* Should not happen! */
1316 ASSERTMSG("IndexKey = NULL!, it should not happen!\n", FALSE);
1317 return HCELL_NIL;
1318 }
1319
1320 /* Sanity check */
1321 ASSERT(IndexKey->Signature == CM_KEY_INDEX_ROOT);
1322
1323 while (TRUE)
1324 {
1325 /* Find subkey */
1326 SubKeyIndex = CmpFindSubKeyInRoot(Hive, IndexKey, Name, &LeafCell);
1327
1328 /* Make sure we found something valid */
1329 if (SubKeyIndex & 0x80000000) return HCELL_NIL;
1330
1331 /* Try to fit it into the LeafCell, if it was found */
1332 if (LeafCell != HCELL_NIL)
1333 {
1334 /* Get the leaf key */
1335 LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1336
1337 /* Check for failure */
1338 if (!LeafKey) return HCELL_NIL;
1339
1340 /* Check if it fits into this leaf and break */
1341 if (LeafKey->Count < CmpMaxIndexPerHblock)
1342 {
1343 /* Fill in the result and return it */
1344 *RootCell = &IndexKey->List[SubKeyIndex];
1345 return LeafCell;
1346 }
1347 }
1348 else
1349 {
1350 /* Get the leaf cell at the very end */
1351 LeafCell = IndexKey->List[SubKeyIndex];
1352 LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1353
1354 /* Return an error in case of problems */
1355 if (!LeafKey) return HCELL_NIL;
1356
1357 /* Choose the cell to search from depending on the key type */
1358 if ((LeafKey->Signature == CM_KEY_FAST_LEAF) ||
1359 (LeafKey->Signature == CM_KEY_HASH_LEAF))
1360 {
1361 FastLeaf = (PCM_KEY_FAST_INDEX)LeafKey;
1362 CurrentCell = FastLeaf->List[0].Cell;
1363 }
1364 else
1365 {
1366 /* Make sure it's an index leaf */
1367 ASSERT(LeafKey->Signature == CM_KEY_INDEX_LEAF);
1368 CurrentCell = LeafKey->List[0];
1369 }
1370
1371 /* Do a name compare */
1372 Result = CmpDoCompareKeyName(Hive, Name, CurrentCell);
1373
1374 /* Check for failure */
1375 if (Result == 2) return HCELL_NIL;
1376
1377 /* Names can't be equal, ensure that */
1378 ASSERT(Result != 0);
1379
1380 /* Check if it's above */
1381 if (Result >= 0)
1382 {
1383 /* Get the first cell in the index */
1384 LeafCell = IndexKey->List[0];
1385 LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1386
1387 /* Return an error in case of problems */
1388 if (!LeafKey) return HCELL_NIL;
1389
1390 /* Check if it fits into this leaf and break */
1391 if (LeafKey->Count < CmpMaxIndexPerHblock)
1392 {
1393 /* Fill in the result and return the cell */
1394 *RootCell = &IndexKey->List[SubKeyIndex + 1];
1395 return LeafCell;
1396 }
1397
1398 /* No, it doesn't fit, check the other leaf */
1399 if (SubKeyIndex < (IndexKey->Count - 1))
1400 {
1401 /* Yes, there is space */
1402 LeafCell = IndexKey->List[SubKeyIndex + 1];
1403 LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1404
1405 /* Return an error in case of problems */
1406 if (!LeafKey) return HCELL_NIL;
1407
1408 /* Check if it fits and break */
1409 if (LeafKey->Count < CmpMaxIndexPerHblock)
1410 {
1411 /* Fill in the result and return the cell */
1412 *RootCell = &IndexKey->List[SubKeyIndex + 1];
1413 return LeafCell;
1414 }
1415 }
1416 }
1417 else
1418 {
1419 /* No, it's below, check the subkey index */
1420 if (SubKeyIndex > 0)
1421 {
1422 /* There should be space at the leaf one before that */
1423 LeafCell = IndexKey->List[SubKeyIndex - 1];
1424 LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1425
1426 /* Return an error in case of problems */
1427 if (!LeafKey) return HCELL_NIL;
1428
1429 /* Check if it fits and break */
1430 if (LeafKey->Count < CmpMaxIndexPerHblock)
1431 {
1432 /* Decrement the subkey index */
1433 SubKeyIndex--;
1434
1435 /* Fill in the result and return the cell */
1436 *RootCell = &IndexKey->List[SubKeyIndex];
1437 return LeafCell;
1438 }
1439 }
1440 else
1441 {
1442 /* Use the first leaf, if possible */
1443 LeafCell = IndexKey->List[0];
1444 LeafKey = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1445
1446 /* Return an error in case of problems */
1447 if (!LeafKey) return HCELL_NIL;
1448
1449 /* Check if it fits and break */
1450 if (LeafKey->Count < CmpMaxIndexPerHblock)
1451 {
1452 /* Fill in the result and return the cell */
1453 *RootCell = &IndexKey->List[0];
1454 return LeafCell;
1455 }
1456 }
1457
1458 /* It didn't fit into either, so proceed to splitting */
1459 }
1460 }
1461
1462 /* We need to split */
1463 CurrentCell = CmpSplitLeaf(Hive,
1464 KeyNode->SubKeyLists[Type],
1465 SubKeyIndex,
1466 Type);
1467
1468 /* Return failure in case splitting failed */
1469 if (CurrentCell == HCELL_NIL) return CurrentCell;
1470
1471 /* Set the SubKeyLists value with the new key */
1472 KeyNode->SubKeyLists[Type] = CurrentCell;
1473
1474 /* Get the new cell */
1475 IndexKey = (PCM_KEY_INDEX)HvGetCell(Hive, KeyNode->SubKeyLists[Type]);
1476
1477 /* Return in case of failure */
1478 if (!IndexKey) return HCELL_NIL;
1479
1480 /* Make sure the new key became index root */
1481 ASSERT(IndexKey->Signature == CM_KEY_INDEX_ROOT);
1482
1483 /* Now loop over with the new IndexKey value, which definately
1484 * has the space now
1485 */
1486 }
1487
1488 /* Shouldn't come here */
1489 return HCELL_NIL;
1490 }
1491
1492 BOOLEAN
1493 NTAPI
1494 CmpAddSubKey(IN PHHIVE Hive,
1495 IN HCELL_INDEX Parent,
1496 IN HCELL_INDEX Child)
1497 {
1498 PCM_KEY_NODE KeyNode;
1499 PCM_KEY_INDEX Index;
1500 PCM_KEY_FAST_INDEX OldIndex;
1501 UNICODE_STRING Name;
1502 HCELL_INDEX IndexCell = HCELL_NIL, CellToRelease = HCELL_NIL, LeafCell;
1503 PHCELL_INDEX RootPointer = NULL;
1504 ULONG Type, i;
1505 BOOLEAN IsCompressed;
1506 PAGED_CODE();
1507
1508 /* Get the key node */
1509 KeyNode = (PCM_KEY_NODE)HvGetCell(Hive, Child);
1510 if (!KeyNode)
1511 {
1512 /* Shouldn't happen */
1513 ASSERT(FALSE);
1514 return FALSE;
1515 }
1516
1517 /* Check if the name is compressed */
1518 if (KeyNode->Flags & KEY_COMP_NAME)
1519 {
1520 /* Remember for later */
1521 IsCompressed = TRUE;
1522
1523 /* Create the compressed name and allocate it */
1524 Name.Length = CmpCompressedNameSize(KeyNode->Name, KeyNode->NameLength);
1525 Name.MaximumLength = Name.Length;
1526 Name.Buffer = Hive->Allocate(Name.Length, TRUE, TAG_CM);
1527 if (!Name.Buffer)
1528 {
1529 /* Release the cell and fail */
1530 HvReleaseCell(Hive, Child);
1531 ASSERT(FALSE);
1532 return FALSE;
1533 }
1534
1535 /* Copy the compressed name */
1536 CmpCopyCompressedName(Name.Buffer,
1537 Name.MaximumLength,
1538 KeyNode->Name,
1539 KeyNode->NameLength);
1540 }
1541 else
1542 {
1543 /* Remember for later */
1544 IsCompressed = FALSE;
1545
1546 /* Build the unicode string */
1547 Name.Length = KeyNode->NameLength;
1548 Name.MaximumLength = KeyNode->NameLength;
1549 Name.Buffer = &KeyNode->Name[0];
1550 }
1551
1552 /* Release the cell */
1553 HvReleaseCell(Hive, Child);
1554
1555 /* Get the parent node */
1556 KeyNode = (PCM_KEY_NODE)HvGetCell(Hive, Parent);
1557 if (!KeyNode)
1558 {
1559 /* Not handled */
1560 ASSERT(FALSE);
1561 }
1562
1563 /* Find out the type of the cell, and check if this is the first subkey */
1564 Type = HvGetCellType(Child);
1565 if (!KeyNode->SubKeyCounts[Type])
1566 {
1567 /* Allocate a fast leaf */
1568 IndexCell = HvAllocateCell(Hive, sizeof(CM_KEY_FAST_INDEX), Type, HCELL_NIL);
1569 if (IndexCell == HCELL_NIL)
1570 {
1571 /* Not handled */
1572 ASSERT(FALSE);
1573 }
1574
1575 /* Get the leaf cell */
1576 Index = (PCM_KEY_INDEX)HvGetCell(Hive, IndexCell);
1577 if (!Index)
1578 {
1579 /* Shouldn't happen */
1580 ASSERT(FALSE);
1581 }
1582
1583 /* Now check what kind of hive we're dealing with */
1584 if (Hive->Version >= 5)
1585 {
1586 /* XP Hive: Use hash leaf */
1587 Index->Signature = CM_KEY_HASH_LEAF;
1588 }
1589 else if (Hive->Version >= 3)
1590 {
1591 /* Windows 2000 and ReactOS: Use fast leaf */
1592 Index->Signature = CM_KEY_FAST_LEAF;
1593 }
1594 else
1595 {
1596 /* NT 4: Use index leaf */
1597 Index->Signature = CM_KEY_INDEX_LEAF;
1598 }
1599
1600 /* Setup the index list */
1601 Index->Count = 0;
1602 KeyNode->SubKeyLists[Type] = IndexCell;
1603 }
1604 else
1605 {
1606 /* We already have an index, get it */
1607 Index = (PCM_KEY_INDEX)HvGetCell(Hive, KeyNode->SubKeyLists[Type]);
1608 if (!Index)
1609 {
1610 /* Not handled */
1611 ASSERT(FALSE);
1612 }
1613
1614 /* Remember to release the cell later */
1615 CellToRelease = KeyNode->SubKeyLists[Type];
1616
1617 /* Check if this is a fast leaf that's gotten too full */
1618 if ((Index->Signature == CM_KEY_FAST_LEAF) &&
1619 (Index->Count >= CmpMaxFastIndexPerHblock))
1620 {
1621 DPRINT("Doing Fast->Slow Leaf conversion\n");
1622
1623 /* Mark this cell as dirty */
1624 HvMarkCellDirty(Hive, CellToRelease, FALSE);
1625
1626 /* Convert */
1627 OldIndex = (PCM_KEY_FAST_INDEX)Index;
1628
1629 for (i = 0; i < OldIndex->Count; i++)
1630 {
1631 Index->List[i] = OldIndex->List[i].Cell;
1632 }
1633
1634 /* Set the new type value */
1635 Index->Signature = CM_KEY_INDEX_LEAF;
1636 }
1637 else if (((Index->Signature == CM_KEY_INDEX_LEAF) ||
1638 (Index->Signature == CM_KEY_HASH_LEAF)) &&
1639 (Index->Count >= CmpMaxIndexPerHblock))
1640 {
1641 /* This is an old/hashed leaf that's gotten too large, root it */
1642 IndexCell = HvAllocateCell(Hive,
1643 sizeof(CM_KEY_INDEX) +
1644 sizeof(HCELL_INDEX),
1645 Type,
1646 HCELL_NIL);
1647 if (IndexCell == HCELL_NIL)
1648 {
1649 /* Not handled */
1650 ASSERT(FALSE);
1651 }
1652
1653 /* Get the index cell */
1654 Index = (PCM_KEY_INDEX)HvGetCell(Hive, IndexCell);
1655 if (!Index)
1656 {
1657 /* Shouldn't happen */
1658 ASSERT(FALSE);
1659 }
1660
1661 /* Mark the index as a root, and set the index cell */
1662 Index->Signature = CM_KEY_INDEX_ROOT;
1663 Index->Count = 1;
1664 Index->List[0] = KeyNode->SubKeyLists[Type];
1665 KeyNode->SubKeyLists[Type] = IndexCell;
1666 }
1667 }
1668
1669 /* Now we can choose the leaf cell */
1670 LeafCell = KeyNode->SubKeyLists[Type];
1671
1672 /* Check if we turned the index into a root */
1673 if (Index->Signature == CM_KEY_INDEX_ROOT)
1674 {
1675 DPRINT("Leaf->Root Index Conversion\n");
1676
1677 /* Get the leaf where to add the new entry (the routine will do
1678 * the splitting if necessary)
1679 */
1680 LeafCell = CmpSelectLeaf(Hive, KeyNode, &Name, Type, &RootPointer);
1681 if (LeafCell == HCELL_NIL)
1682 {
1683 /* Not handled */
1684 ASSERT(FALSE);
1685 }
1686 }
1687
1688 /* Add our leaf cell */
1689 LeafCell = CmpAddToLeaf(Hive, LeafCell, Child, &Name);
1690 if (LeafCell == HCELL_NIL)
1691 {
1692 /* Not handled */
1693 ASSERT(FALSE);
1694 }
1695
1696 /* Update the key counts */
1697 KeyNode->SubKeyCounts[Type]++;
1698
1699 /* Check if caller wants us to return the leaf */
1700 if (RootPointer)
1701 {
1702 /* Return it */
1703 *RootPointer = LeafCell;
1704 }
1705 else
1706 {
1707 /* Otherwise, mark it as the list index for the cell */
1708 KeyNode->SubKeyLists[Type] = LeafCell;
1709 }
1710
1711 /* If the name was compressed, free our copy */
1712 if (IsCompressed) Hive->Free(Name.Buffer, 0);
1713
1714 /* Release all our cells */
1715 if (IndexCell != HCELL_NIL) HvReleaseCell(Hive, IndexCell);
1716 if (CellToRelease != HCELL_NIL) HvReleaseCell(Hive, CellToRelease);
1717 HvReleaseCell(Hive, Parent);
1718 return TRUE;
1719 }
1720
1721 BOOLEAN
1722 NTAPI
1723 CmpRemoveSubKey(IN PHHIVE Hive,
1724 IN HCELL_INDEX ParentKey,
1725 IN HCELL_INDEX TargetKey)
1726 {
1727 PCM_KEY_NODE Node;
1728 UNICODE_STRING SearchName;
1729 BOOLEAN IsCompressed;
1730 WCHAR Buffer[50];
1731 HCELL_INDEX RootCell = HCELL_NIL, LeafCell, ChildCell;
1732 PCM_KEY_INDEX Root = NULL, Leaf;
1733 PCM_KEY_FAST_INDEX Child;
1734 ULONG Storage, RootIndex = 0x80000000, LeafIndex;
1735 BOOLEAN Result = FALSE;
1736 HCELL_INDEX CellToRelease1 = HCELL_NIL, CellToRelease2 = HCELL_NIL;
1737
1738 /* Get the target key node */
1739 Node = (PCM_KEY_NODE)HvGetCell(Hive, TargetKey);
1740 if (!Node) return FALSE;
1741
1742 /* Make sure it's dirty, then release it */
1743 ASSERT(HvIsCellDirty(Hive, TargetKey));
1744 HvReleaseCell(Hive, TargetKey);
1745
1746 /* Check if the name is compressed */
1747 if (Node->Flags & KEY_COMP_NAME)
1748 {
1749 /* Remember for later */
1750 IsCompressed = TRUE;
1751
1752 /* Build the search name */
1753 SearchName.Length = CmpCompressedNameSize(Node->Name,
1754 Node->NameLength);
1755 SearchName.MaximumLength = SearchName.Length;
1756
1757 /* Do we need an extra bufer? */
1758 if (SearchName.MaximumLength > sizeof(Buffer))
1759 {
1760 /* Allocate one */
1761 SearchName.Buffer = CmpAllocate(SearchName.Length,
1762 TRUE,
1763 TAG_CM);
1764 if (!SearchName.Buffer) return FALSE;
1765 }
1766 else
1767 {
1768 /* Otherwise, use our local stack buffer */
1769 SearchName.Buffer = Buffer;
1770 }
1771
1772 /* Copy the compressed name */
1773 CmpCopyCompressedName(SearchName.Buffer,
1774 SearchName.MaximumLength,
1775 Node->Name,
1776 Node->NameLength);
1777 }
1778 else
1779 {
1780 /* It's not compressed, build the name directly from the node */
1781 IsCompressed = FALSE;
1782 SearchName.Length = Node->NameLength;
1783 SearchName.MaximumLength = Node->NameLength;
1784 SearchName.Buffer = Node->Name;
1785 }
1786
1787 /* Now get the parent node */
1788 Node = (PCM_KEY_NODE)HvGetCell(Hive, ParentKey);
1789 if (!Node) goto Exit;
1790
1791 /* Make sure it's dirty, then release it */
1792 ASSERT(HvIsCellDirty(Hive, ParentKey));
1793 HvReleaseCell(Hive, ParentKey);
1794
1795 /* Get the storage type and make sure it's not empty */
1796 Storage = HvGetCellType(TargetKey);
1797 ASSERT(Node->SubKeyCounts[Storage] != 0);
1798 //ASSERT(HvIsCellAllocated(Hive, Node->SubKeyLists[Storage]));
1799
1800 /* Get the leaf cell now */
1801 LeafCell = Node->SubKeyLists[Storage];
1802 Leaf = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1803 if (!Leaf) goto Exit;
1804
1805 /* Remember to release it later */
1806 CellToRelease1 = LeafCell;
1807
1808 /* Check if the leaf is a root */
1809 if (Leaf->Signature == CM_KEY_INDEX_ROOT)
1810 {
1811 /* Find the child inside the root */
1812 RootIndex = CmpFindSubKeyInRoot(Hive, Leaf, &SearchName, &ChildCell);
1813 if (RootIndex & 0x80000000) goto Exit;
1814 ASSERT(ChildCell != FALSE);
1815
1816 /* The root cell is now this leaf */
1817 Root = Leaf;
1818 RootCell = LeafCell;
1819
1820 /* And the new leaf is now this child */
1821 LeafCell = ChildCell;
1822 Leaf = (PCM_KEY_INDEX)HvGetCell(Hive, LeafCell);
1823 if (!Leaf) goto Exit;
1824
1825 /* Remember to release it later */
1826 CellToRelease2 = LeafCell;
1827 }
1828
1829 /* Make sure the leaf is valid */
1830 ASSERT((Leaf->Signature == CM_KEY_INDEX_LEAF) ||
1831 (Leaf->Signature == CM_KEY_FAST_LEAF) ||
1832 (Leaf->Signature == CM_KEY_HASH_LEAF));
1833
1834 /* Now get the child in the leaf */
1835 LeafIndex = CmpFindSubKeyInLeaf(Hive, Leaf, &SearchName, &ChildCell);
1836 if (LeafIndex & 0x80000000) goto Exit;
1837 ASSERT(ChildCell != HCELL_NIL);
1838
1839 /* Decrement key counts and check if this was the last leaf entry */
1840 Node->SubKeyCounts[Storage]--;
1841 if (!(--Leaf->Count))
1842 {
1843 /* Free the leaf */
1844 HvFreeCell(Hive, LeafCell);
1845
1846 /* Check if we were inside a root */
1847 if (Root)
1848 {
1849 /* Decrease the root count too, since the leaf is going away */
1850 if (!(--Root->Count))
1851 {
1852 /* The root is gone too,n ow */
1853 HvFreeCell(Hive, RootCell);
1854 Node->SubKeyLists[Storage] = HCELL_NIL;
1855 }
1856 else if (RootIndex < Root->Count)
1857 {
1858 /* Bring everything up by one */
1859 RtlMoveMemory(&Root->List[RootIndex],
1860 &Root->List[RootIndex + 1],
1861 (Root->Count - RootIndex) * sizeof(HCELL_INDEX));
1862 }
1863 }
1864 else
1865 {
1866 /* Otherwise, just clear the cell */
1867 Node->SubKeyLists[Storage] = HCELL_NIL;
1868 }
1869 }
1870 else if (LeafIndex < Leaf->Count)
1871 {
1872 /* Was the leaf a normal index? */
1873 if (Leaf->Signature == CM_KEY_INDEX_LEAF)
1874 {
1875 /* Bring everything up by one */
1876 RtlMoveMemory(&Leaf->List[LeafIndex],
1877 &Leaf->List[LeafIndex + 1],
1878 (Leaf->Count - LeafIndex) * sizeof(HCELL_INDEX));
1879 }
1880 else
1881 {
1882 /* This is a fast index, bring everything up by one */
1883 Child = (PCM_KEY_FAST_INDEX)Leaf;
1884 RtlMoveMemory(&Child->List[LeafIndex],
1885 &Child->List[LeafIndex+1],
1886 (Child->Count - LeafIndex) * sizeof(CM_INDEX));
1887 }
1888 }
1889
1890 /* If we got here, now we're done */
1891 Result = TRUE;
1892
1893 Exit:
1894 /* Release any cells we may have been holding */
1895 if (CellToRelease1 != HCELL_NIL) HvReleaseCell(Hive, CellToRelease1);
1896 if (CellToRelease2 != HCELL_NIL) HvReleaseCell(Hive, CellToRelease2);
1897
1898 /* Check if the name was compressed and not inside our local buffer */
1899 if ((IsCompressed) && (SearchName.MaximumLength > sizeof(Buffer)))
1900 {
1901 /* Free the buffer we allocated */
1902 CmpFree(SearchName.Buffer, 0);
1903 }
1904
1905 /* Return the result */
1906 return Result;
1907 }
A free Windows-compatible Operating System