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