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