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