1 /* 2 * Copyright 2008, Axel Dörfler, axeld@pinc-software.de. 3 * This file may be used under the terms of the MIT License. 4 */ 5 6 7 #include "DirectoryIterator.h" 8 9 #include <string.h> 10 11 #include <AutoDeleter.h> 12 #include <util/VectorSet.h> 13 14 #include "CachedBlock.h" 15 #include "HTree.h" 16 #include "Inode.h" 17 18 19 //#define TRACE_EXT2 20 #ifdef TRACE_EXT2 21 # define TRACE(x...) dprintf("\33[34mext2:\33[0m " x) 22 #else 23 # define TRACE(x...) ; 24 #endif 25 26 27 struct HashedEntry 28 { 29 uint8* position; 30 uint32 hash; 31 32 bool operator<(const HashedEntry& other) const 33 { 34 return hash <= other.hash; 35 } 36 37 bool operator>(const HashedEntry& other) const 38 { 39 return hash >= other.hash; 40 } 41 }; 42 43 44 DirectoryIterator::DirectoryIterator(Inode* directory, off_t start, 45 HTreeEntryIterator* parent) 46 : 47 fDirectory(directory), 48 fVolume(directory->GetVolume()), 49 fBlockSize(fVolume->BlockSize()), 50 fParent(parent), 51 fNumBlocks(directory->Size() == 0 ? 0 52 : (directory->Size() - 1) / fBlockSize + 1), 53 fLogicalBlock(start / fBlockSize), 54 fDisplacement(start % fBlockSize), 55 fPreviousDisplacement(fDisplacement), 56 fStartLogicalBlock(fLogicalBlock), 57 fStartDisplacement(fDisplacement) 58 { 59 TRACE("DirectoryIterator::DirectoryIterator() %" B_PRIdINO ": num blocks: " 60 "%" B_PRIu32 "\n", fDirectory->ID(), fNumBlocks); 61 fIndexing = parent != NULL; 62 fInitStatus = fDirectory->FindBlock(start, fPhysicalBlock); 63 fStartPhysicalBlock = fPhysicalBlock; 64 } 65 66 67 DirectoryIterator::~DirectoryIterator() 68 { 69 TRACE("DirectoryIterator::~DirectoryIterator(): %p, parent: %p\n", this, 70 fParent); 71 delete fParent; 72 TRACE("DirectoryIterator::~DirectoryIterator(): Deleted the parent\n"); 73 } 74 75 76 status_t 77 DirectoryIterator::InitCheck() 78 { 79 return fInitStatus; 80 } 81 82 83 status_t 84 DirectoryIterator::Get(char* name, size_t* _nameLength, ino_t* _id) 85 { 86 TRACE("DirectoryIterator::Get() ID %" B_PRIdINO "\n", fDirectory->ID()); 87 if (_Offset() >= fDirectory->Size()) { 88 TRACE("DirectoryIterator::Get() out of entries\n"); 89 return B_ENTRY_NOT_FOUND; 90 } 91 92 CachedBlock cached(fVolume); 93 const uint8* block = cached.SetTo(fPhysicalBlock); 94 if (block == NULL) 95 return B_IO_ERROR; 96 97 TRACE("DirectoryIterator::Get(): Displacement: %" B_PRIu32 "\n", 98 fDisplacement); 99 const ext2_dir_entry* entry = (const ext2_dir_entry*)&block[fDisplacement]; 100 101 if (entry->Length() == 0 || entry->InodeID() == 0) 102 return B_BAD_DATA; 103 104 if (entry->NameLength() != 0) { 105 size_t length = entry->NameLength(); 106 107 TRACE("block %" B_PRIu32 ", displacement %" B_PRIu32 ": entry ino %" 108 B_PRIu32 ", length %u, name length %" B_PRIuSIZE ", type %u\n", 109 fLogicalBlock, fDisplacement, entry->InodeID(), entry->Length(), 110 length, entry->FileType()); 111 112 if (*_nameLength > 0) { 113 if (length + 1 > *_nameLength) 114 return B_BUFFER_OVERFLOW; 115 116 memcpy(name, entry->name, length); 117 name[length] = '\0'; 118 119 *_nameLength = length; 120 } 121 122 *_id = entry->InodeID(); 123 } else 124 *_nameLength = 0; 125 126 return B_OK; 127 } 128 129 130 status_t 131 DirectoryIterator::GetNext(char* name, size_t* _nameLength, ino_t* _id) 132 { 133 status_t status; 134 while ((status = Get(name, _nameLength, _id)) == B_BAD_DATA) { 135 status = Next(); 136 if (status != B_OK) 137 return status; 138 } 139 return status; 140 } 141 142 143 status_t 144 DirectoryIterator::Next() 145 { 146 TRACE("DirectoryIterator::Next() fDirectory->ID() %" B_PRIdINO "\n", 147 fDirectory->ID()); 148 149 if (_Offset() >= fDirectory->Size()) { 150 TRACE("DirectoryIterator::Next() out of entries\n"); 151 return B_ENTRY_NOT_FOUND; 152 } 153 154 TRACE("DirectoryIterator::Next(): Creating cached block\n"); 155 156 CachedBlock cached(fVolume); 157 ext2_dir_entry* entry; 158 159 TRACE("DirectoryIterator::Next(): Loading cached block\n"); 160 const uint8* block = cached.SetTo(fPhysicalBlock); 161 if (block == NULL) 162 return B_IO_ERROR; 163 164 entry = (ext2_dir_entry*)(block + fDisplacement); 165 166 do { 167 TRACE("Checking entry at block %" B_PRIu64 ", displacement %" B_PRIu32 168 " entry inodeid %" B_PRIu32 "\n", fPhysicalBlock, fDisplacement, 169 entry->InodeID()); 170 171 if (entry->Length() != 0) { 172 if (!entry->IsValid()) { 173 TRACE("invalid entry.\n"); 174 return B_BAD_DATA; 175 } 176 fPreviousDisplacement = fDisplacement; 177 fDisplacement += entry->Length(); 178 } else 179 fDisplacement = fBlockSize; 180 181 if (fDisplacement == fBlockSize) { 182 TRACE("Reached end of block\n"); 183 184 fDisplacement = 0; 185 186 status_t status = _NextBlock(); 187 if (status != B_OK) 188 return status; 189 190 if ((off_t)(_Offset() + ext2_dir_entry::MinimumSize()) 191 >= fDirectory->Size()) { 192 TRACE("DirectoryIterator::Next() end of directory file\n"); 193 return B_ENTRY_NOT_FOUND; 194 } 195 status = fDirectory->FindBlock(_Offset(), fPhysicalBlock); 196 if (status != B_OK) 197 return status; 198 199 block = cached.SetTo(fPhysicalBlock); 200 if (block == NULL) 201 return B_IO_ERROR; 202 } else if (fDisplacement > fBlockSize) { 203 TRACE("The entry isn't block aligned.\n"); 204 // TODO: Is block alignment obligatory? 205 return B_BAD_DATA; 206 } 207 208 entry = (ext2_dir_entry*)(block + fDisplacement); 209 210 TRACE("DirectoryIterator::Next() skipping entry %d %" B_PRIu32 "\n", 211 entry->Length(), entry->InodeID()); 212 } while (entry->Length() == 0 || entry->InodeID() == 0); 213 214 TRACE("DirectoryIterator::Next() entry->Length() %d entry->name %*s\n", 215 entry->Length(), entry->NameLength(), entry->name); 216 217 return B_OK; 218 } 219 220 221 status_t 222 DirectoryIterator::Rewind() 223 { 224 fDisplacement = 0; 225 fPreviousDisplacement = 0; 226 fLogicalBlock = 0; 227 228 return fDirectory->FindBlock(0, fPhysicalBlock); 229 } 230 231 232 void 233 DirectoryIterator::Restart() 234 { 235 TRACE("DirectoryIterator::Restart(): (logical, physical, displacement): " 236 "current: (%" B_PRIu32 ", %" B_PRIu64 ", %" B_PRIu32 "), start: (%" 237 B_PRIu32 ", %" B_PRIu64 ", %" B_PRIu32 ")\n", fLogicalBlock, 238 fPhysicalBlock, fDisplacement, fStartLogicalBlock, fStartPhysicalBlock, 239 fStartDisplacement); 240 fLogicalBlock = fStartLogicalBlock; 241 fPhysicalBlock = fStartPhysicalBlock; 242 fDisplacement = fPreviousDisplacement = fStartDisplacement; 243 } 244 245 246 status_t 247 DirectoryIterator::AddEntry(Transaction& transaction, const char* name, 248 size_t _nameLength, ino_t id, uint8 type) 249 { 250 TRACE("DirectoryIterator::AddEntry(%s, ...)\n", name); 251 252 uint8 nameLength = _nameLength > EXT2_NAME_LENGTH ? EXT2_NAME_LENGTH 253 : _nameLength; 254 255 status_t status = B_OK; 256 while (status == B_OK) { 257 uint16 pos = 0; 258 uint16 newLength; 259 260 status = _AllocateBestEntryInBlock(nameLength, pos, newLength); 261 if (status == B_OK) { 262 return _AddEntry(transaction, name, nameLength, id, type, newLength, 263 pos); 264 } else if (status != B_DEVICE_FULL) 265 return status; 266 267 fDisplacement = 0; 268 status = _NextBlock(); 269 if (status == B_OK) 270 status = fDirectory->FindBlock(_Offset(), fPhysicalBlock); 271 } 272 273 if (status != B_ENTRY_NOT_FOUND) 274 return status; 275 276 bool firstSplit = fNumBlocks == 1 && fVolume->IndexedDirectories(); 277 278 fNumBlocks++; 279 280 if (fIndexing) { 281 TRACE("DirectoryIterator::AddEntry(): Adding another HTree leaf\n"); 282 fNumBlocks += fParent->BlocksNeededForNewEntry(); 283 } else if (firstSplit) { 284 // Allocate another block (fNumBlocks should become 3) 285 TRACE("DirectoryIterator::AddEntry(): Creating index for directory\n"); 286 fNumBlocks++; 287 } else 288 TRACE("DirectoryIterator::AddEntry(): Enlarging directory\n"); 289 290 status = fDirectory->Resize(transaction, fNumBlocks * fBlockSize); 291 if (status != B_OK) 292 return status; 293 294 if (firstSplit || fIndexing) { 295 // firstSplit and fIndexing are mutually exclusive 296 return _SplitIndexedBlock(transaction, name, nameLength, id, type, 297 fNumBlocks - 1, firstSplit); 298 } 299 300 fLogicalBlock = fNumBlocks - 1; 301 status = fDirectory->FindBlock(fLogicalBlock * fBlockSize, fPhysicalBlock); 302 if (status != B_OK) 303 return status; 304 305 return _AddEntry(transaction, name, nameLength, id, type, fBlockSize, 0, 306 false); 307 } 308 309 310 status_t 311 DirectoryIterator::FindEntry(const char* name, ino_t* _id) 312 { 313 TRACE("DirectoryIterator::FindEntry(): %p %p\n", this, name); 314 char buffer[EXT2_NAME_LENGTH + 1]; 315 ino_t id; 316 317 status_t status = B_OK; 318 size_t length = strlen(name); 319 while (status == B_OK) { 320 size_t nameLength = EXT2_NAME_LENGTH; 321 status = Get(buffer, &nameLength, &id); 322 if (status == B_OK) { 323 if (length == nameLength 324 && strncmp(name, buffer, nameLength) == 0) { 325 if (_id != NULL) 326 *_id = id; 327 return B_OK; 328 } 329 } else if (status != B_BAD_DATA) 330 break; 331 status = Next(); 332 } 333 334 return status; 335 } 336 337 338 status_t 339 DirectoryIterator::RemoveEntry(Transaction& transaction) 340 { 341 TRACE("DirectoryIterator::RemoveEntry()\n"); 342 ext2_dir_entry* previousEntry; 343 ext2_dir_entry* dirEntry; 344 CachedBlock cached(fVolume); 345 346 uint8* block = cached.SetToWritable(transaction, fPhysicalBlock); 347 348 if (fDisplacement == 0) { 349 previousEntry = (ext2_dir_entry*)&block[fDisplacement]; 350 351 fPreviousDisplacement = fDisplacement; 352 fDisplacement += previousEntry->Length(); 353 354 if (fDisplacement == fBlockSize) { 355 previousEntry->SetInodeID(0); 356 fDisplacement = 0; 357 return B_OK; 358 } else if (fDisplacement > fBlockSize) { 359 TRACE("DirectoryIterator::RemoveEntry(): Entry isn't aligned to " 360 "block entry."); 361 return B_BAD_DATA; 362 } 363 364 dirEntry = (ext2_dir_entry*)&block[fDisplacement]; 365 memcpy(&block[fPreviousDisplacement], &block[fDisplacement], 366 dirEntry->Length()); 367 368 previousEntry->SetLength(fDisplacement - fPreviousDisplacement 369 + previousEntry->Length()); 370 371 return B_OK; 372 } 373 374 TRACE("DirectoryIterator::RemoveEntry() fDisplacement %" B_PRIu32 "\n", 375 fDisplacement); 376 377 if (fPreviousDisplacement == fDisplacement) { 378 char buffer[EXT2_NAME_LENGTH + 1]; 379 380 dirEntry = (ext2_dir_entry*)&block[fDisplacement]; 381 382 memcpy(buffer, dirEntry->name, (uint32)dirEntry->name_length); 383 384 fDisplacement = 0; 385 status_t status = FindEntry(dirEntry->name); 386 if (status == B_ENTRY_NOT_FOUND) 387 return B_BAD_DATA; 388 if (status != B_OK) 389 return status; 390 } 391 392 previousEntry = (ext2_dir_entry*)&block[fPreviousDisplacement]; 393 dirEntry = (ext2_dir_entry*)&block[fDisplacement]; 394 395 previousEntry->SetLength(previousEntry->Length() + dirEntry->Length()); 396 397 memset(&block[fDisplacement], 0, 398 fPreviousDisplacement + previousEntry->Length() - fDisplacement); 399 400 return B_OK; 401 } 402 403 404 status_t 405 DirectoryIterator::ChangeEntry(Transaction& transaction, ino_t id, 406 uint8 fileType) 407 { 408 CachedBlock cached(fVolume); 409 410 uint8* block = cached.SetToWritable(transaction, fPhysicalBlock); 411 if (block == NULL) 412 return B_IO_ERROR; 413 414 ext2_dir_entry* dirEntry = (ext2_dir_entry*)&block[fDisplacement]; 415 dirEntry->SetInodeID(id); 416 dirEntry->file_type = fileType; 417 418 return B_OK; 419 } 420 421 422 status_t 423 DirectoryIterator::_AllocateBestEntryInBlock(uint8 nameLength, uint16& pos, 424 uint16& newLength) 425 { 426 TRACE("DirectoryIterator::_AllocateBestEntryInBlock()\n"); 427 CachedBlock cached(fVolume); 428 const uint8* block = cached.SetTo(fPhysicalBlock); 429 430 uint16 requiredLength = nameLength + 8; 431 if (requiredLength % 4 != 0) 432 requiredLength += 4 - requiredLength % 4; 433 434 uint16 bestPos = fBlockSize; 435 uint16 bestLength = fBlockSize; 436 uint16 bestRealLength = fBlockSize; 437 ext2_dir_entry* dirEntry; 438 439 while (pos < fBlockSize) { 440 dirEntry = (ext2_dir_entry*)&block[pos]; 441 442 uint16 realLength = dirEntry->NameLength() + 8; 443 444 if (realLength % 4 != 0) 445 realLength += 4 - realLength % 4; 446 447 uint16 emptySpace = dirEntry->Length() - realLength; 448 if (emptySpace == requiredLength) { 449 // Found an exact match 450 TRACE("DirectoryIterator::_AllocateBestEntryInBlock(): Found an " 451 "exact length match\n"); 452 newLength = realLength; 453 454 return B_OK; 455 } else if (emptySpace > requiredLength && emptySpace < bestLength) { 456 bestPos = pos; 457 bestLength = emptySpace; 458 bestRealLength = realLength; 459 } 460 461 pos += dirEntry->Length(); 462 } 463 464 if (bestPos == fBlockSize) 465 return B_DEVICE_FULL; 466 467 TRACE("DirectoryIterator::_AllocateBestEntryInBlock(): Found a suitable " 468 "location: %u\n", bestPos); 469 pos = bestPos; 470 newLength = bestRealLength; 471 472 return B_OK; 473 } 474 475 476 status_t 477 DirectoryIterator::_AddEntry(Transaction& transaction, const char* name, 478 uint8 nameLength, ino_t id, uint8 type, uint16 newLength, uint16 pos, 479 bool hasPrevious) 480 { 481 TRACE("DirectoryIterator::_AddEntry(%s, %d, %" B_PRIdINO ", %d, %d, %d, " 482 "%c)\n", name, nameLength, id, type, newLength, pos, 483 hasPrevious ? 't' : 'f'); 484 CachedBlock cached(fVolume); 485 486 uint8* block = cached.SetToWritable(transaction, fPhysicalBlock); 487 if (block == NULL) 488 return B_IO_ERROR; 489 490 ext2_dir_entry* dirEntry = (ext2_dir_entry*)&block[pos]; 491 492 if (hasPrevious) { 493 uint16 previousLength = dirEntry->Length(); 494 dirEntry->SetLength(newLength); 495 496 dirEntry = (ext2_dir_entry*)&block[pos + newLength]; 497 newLength = previousLength - newLength; 498 } 499 500 dirEntry->SetLength(newLength); 501 dirEntry->name_length = nameLength; 502 dirEntry->SetInodeID(id); 503 dirEntry->file_type = type; 504 memcpy(dirEntry->name, name, nameLength); 505 506 TRACE("DirectoryIterator::_AddEntry(): Done\n"); 507 508 return B_OK; 509 } 510 511 512 status_t 513 DirectoryIterator::_SplitIndexedBlock(Transaction& transaction, 514 const char* name, uint8 nameLength, ino_t id, uint8 type, 515 uint32 newBlocksPos, bool firstSplit) 516 { 517 // Block is full, split required 518 TRACE("DirectoryIterator::_SplitIndexedBlock(.., %s, %u, %" B_PRIdINO ", %" 519 B_PRIu32 ", %c)\n", name, nameLength, id, newBlocksPos, 520 firstSplit ? 't' : 'f'); 521 522 // Allocate a buffer for the entries in the block 523 uint8* buffer = new(std::nothrow) uint8[fBlockSize]; 524 if (buffer == NULL) 525 return B_NO_MEMORY; 526 ArrayDeleter<uint8> bufferDeleter(buffer); 527 528 fsblock_t firstPhysicalBlock = 0; 529 530 // Prepare block to hold the first half of the entries and fill the buffer 531 CachedBlock cachedFirst(fVolume); 532 533 if (firstSplit) { 534 // Save all entries to the buffer 535 status_t status = fDirectory->FindBlock(0, firstPhysicalBlock); 536 if (status != B_OK) 537 return status; 538 539 const uint8* srcBlock = cachedFirst.SetTo(firstPhysicalBlock); 540 if (srcBlock == NULL) 541 return B_IO_ERROR; 542 543 memcpy(buffer, srcBlock, fBlockSize); 544 545 status = fDirectory->FindBlock(fBlockSize, fPhysicalBlock); 546 if (status != B_OK) 547 return status; 548 } 549 550 uint8* firstBlock = cachedFirst.SetToWritable(transaction, fPhysicalBlock); 551 uint8* secondBlock = NULL; 552 if (firstBlock == NULL) 553 return B_IO_ERROR; 554 555 status_t status; 556 557 if (!firstSplit) { 558 // Save all entries to the buffer 559 memcpy(buffer, firstBlock, fBlockSize); 560 } else { 561 // Initialize the root node 562 fDirectory->Node().SetFlag(EXT2_INODE_INDEXED); 563 HTreeRoot* root; 564 565 secondBlock = cachedFirst.SetToWritable(transaction, 566 firstPhysicalBlock, true); 567 if (secondBlock == NULL) 568 return B_IO_ERROR; 569 570 status = fDirectory->WriteBack(transaction); 571 if (status != B_OK) 572 return status; 573 574 memcpy(secondBlock, buffer, 2 * (sizeof(HTreeFakeDirEntry) + 4)); 575 576 root = (HTreeRoot*)secondBlock; 577 578 HTreeFakeDirEntry* dotdot = &root->dotdot; 579 dotdot->SetEntryLength(fBlockSize - (sizeof(HTreeFakeDirEntry) + 4)); 580 581 root->hash_version = fVolume->DefaultHashVersion(); 582 root->root_info_length = 8; 583 root->indirection_levels = 0; 584 585 root->count_limit->SetLimit((fBlockSize 586 - ((uint8*)root->count_limit - secondBlock)) / sizeof(HTreeEntry)); 587 root->count_limit->SetCount(2); 588 } 589 590 // Sort entries 591 VectorSet<HashedEntry> entrySet; 592 593 HTree htree(fVolume, fDirectory); 594 status = htree.PrepareForHash(); 595 if (status != B_OK) 596 return status; 597 598 uint32 displacement = firstSplit ? 2 * (sizeof(HTreeFakeDirEntry) + 4) : 0; 599 600 HashedEntry entry; 601 ext2_dir_entry* dirEntry = NULL; 602 603 while (displacement < fBlockSize) { 604 entry.position = &buffer[displacement]; 605 dirEntry = (ext2_dir_entry*)entry.position; 606 607 TRACE("DirectoryIterator::_SplitIndexedBlock(): pos: %p, name " 608 "length: %u, entry length: %u\n", entry.position, 609 dirEntry->name_length, 610 dirEntry->Length()); 611 612 char cbuffer[256]; 613 memcpy(cbuffer, dirEntry->name, dirEntry->name_length); 614 cbuffer[dirEntry->name_length] = '\0'; 615 entry.hash = htree.Hash(dirEntry->name, dirEntry->name_length); 616 TRACE("DirectoryIterator::_SplitIndexedBlock(): %s -> %" B_PRIu32 "\n", 617 cbuffer, entry.hash); 618 619 status = entrySet.Insert(entry); 620 if (status != B_OK) 621 return status; 622 623 displacement += dirEntry->Length(); 624 } 625 626 // Prepare the new entry to be included as well 627 ext2_dir_entry newEntry; 628 629 uint16 newLength = (uint16)nameLength + 8; 630 if (newLength % 4 != 0) 631 newLength += 4 - newLength % 4; 632 633 newEntry.name_length = nameLength; 634 newEntry.SetLength(newLength); 635 newEntry.SetInodeID(id); 636 newEntry.file_type = type; 637 memcpy(newEntry.name, name, nameLength); 638 639 entry.position = (uint8*)&newEntry; 640 entry.hash = htree.Hash(name, nameLength); 641 TRACE("DirectoryIterator::_SplitIndexedBlock(): %s -> %" B_PRIu32 "\n", 642 name, entry.hash); 643 644 entrySet.Insert(entry); 645 646 // Move first half of entries to the first block 647 VectorSet<HashedEntry>::Iterator iterator = entrySet.Begin(); 648 int32 median = entrySet.Count() / 2; 649 displacement = 0; 650 TRACE("DirectoryIterator::_SplitIndexedBlock(): Count: %" B_PRId32 651 ", median: %" B_PRId32 "\n", entrySet.Count(), median); 652 653 uint32 previousHash = (*iterator).hash; 654 655 for (int32 i = 0; i < median; ++i) { 656 dirEntry = (ext2_dir_entry*)(*iterator).position; 657 previousHash = (*iterator).hash; 658 659 uint32 realLength = (uint32)dirEntry->name_length + 8; 660 if (realLength % 4 != 0) 661 realLength += 4 - realLength % 4; 662 663 dirEntry->SetLength((uint16)realLength); 664 memcpy(&firstBlock[displacement], dirEntry, realLength); 665 666 displacement += realLength; 667 iterator++; 668 } 669 670 // Update last entry in the block 671 uint16 oldLength = dirEntry->Length(); 672 dirEntry = (ext2_dir_entry*)&firstBlock[displacement - oldLength]; 673 dirEntry->SetLength(fBlockSize - displacement + oldLength); 674 675 bool collision = false; 676 677 while (iterator != entrySet.End() && (*iterator).hash == previousHash) { 678 // Keep collisions on the same block 679 TRACE("DirectoryIterator::_SplitIndexedBlock(): Handling collisions\n"); 680 681 // This isn't the ideal solution, but it is a rare occurance 682 dirEntry = (ext2_dir_entry*)(*iterator).position; 683 684 if (displacement + dirEntry->Length() > fBlockSize) { 685 // Doesn't fit on the block 686 collision = true; 687 break; 688 } 689 690 memcpy(&firstBlock[displacement], dirEntry, dirEntry->Length()); 691 692 displacement += dirEntry->Length(); 693 iterator++; 694 } 695 696 // Save the hash to store in the parent 697 uint32 medianHash = (*iterator).hash; 698 699 // Update parent 700 if (firstSplit) { 701 TRACE("DirectoryIterator::_SplitIndexedBlock(): Updating root\n"); 702 HTreeRoot* root = (HTreeRoot*)secondBlock; 703 HTreeEntry* htreeEntry = (HTreeEntry*)root->count_limit; 704 htreeEntry->SetBlock(1); 705 706 ++htreeEntry; 707 htreeEntry->SetBlock(2); 708 htreeEntry->SetHash(medianHash); 709 710 off_t start = (off_t)root->root_info_length 711 + 2 * (sizeof(HTreeFakeDirEntry) + 4); 712 fParent = new(std::nothrow) HTreeEntryIterator(start, fDirectory); 713 if (fParent == NULL) 714 return B_NO_MEMORY; 715 716 fLogicalBlock = 1; 717 status = fDirectory->FindBlock(fLogicalBlock * fBlockSize, 718 fPhysicalBlock); 719 720 fPreviousDisplacement = fDisplacement = 0; 721 722 status = fParent->Init(); 723 } 724 else { 725 status = fParent->InsertEntry(transaction, medianHash, fNumBlocks - 1, 726 newBlocksPos, collision); 727 } 728 if (status != B_OK) 729 return status; 730 731 // Prepare last block to hold the second half of the entries 732 TRACE("DirectoryIterator::_SplitIndexedBlock(): Preparing second leaf " 733 "block\n"); 734 fDisplacement = 0; 735 736 status = fDirectory->FindBlock(fDirectory->Size() - 1, fPhysicalBlock); 737 if (status != B_OK) 738 return status; 739 740 CachedBlock cachedSecond(fVolume); 741 secondBlock = cachedSecond.SetToWritable(transaction, 742 fPhysicalBlock); 743 if (secondBlock == NULL) 744 return B_IO_ERROR; 745 746 // Move the second half of the entries to the second block 747 VectorSet<HashedEntry>::Iterator end = entrySet.End(); 748 displacement = 0; 749 750 while (iterator != end) { 751 dirEntry = (ext2_dir_entry*)(*iterator).position; 752 753 uint32 realLength = (uint32)dirEntry->name_length + 8; 754 if (realLength % 4 != 0) 755 realLength += 4 - realLength % 4; 756 757 dirEntry->SetLength((uint16)realLength); 758 memcpy(&secondBlock[displacement], dirEntry, realLength); 759 760 displacement += realLength; 761 iterator++; 762 } 763 764 // Update last entry in the block 765 oldLength = dirEntry->Length(); 766 dirEntry = (ext2_dir_entry*)&secondBlock[displacement - oldLength]; 767 dirEntry->SetLength(fBlockSize - displacement + oldLength); 768 769 TRACE("DirectoryIterator::_SplitIndexedBlock(): Done\n"); 770 return B_OK; 771 } 772 773 774 status_t 775 DirectoryIterator::_NextBlock() 776 { 777 TRACE("DirectoryIterator::_NextBlock()\n"); 778 if (fIndexing) { 779 TRACE("DirectoryIterator::_NextBlock(): Indexing\n"); 780 if (!fParent->HasCollision()) { 781 TRACE("DirectoryIterator::_NextBlock(): next block doesn't " 782 "contain collisions from previous block\n"); 783 #ifndef COLLISION_TEST 784 return B_ENTRY_NOT_FOUND; 785 #endif 786 } 787 788 return fParent->GetNext(fLogicalBlock); 789 } 790 791 if (++fLogicalBlock > fNumBlocks) 792 return B_ENTRY_NOT_FOUND; 793 794 return B_OK; 795 } 796