haiku.git

/*
 * Copyright 2008, Axel Dörfler, axeld@pinc-software.de.
 * This file may be used under the terms of the MIT License.
 */


#include "DirectoryIterator.h"

#include <string.h>

#include <AutoDeleter.h>
#include <util/VectorSet.h>

#include "CachedBlock.h"
#include "CRCTable.h"
#include "HTree.h"
#include "Inode.h"


#undef ASSERT

//#define TRACE_EXT2
#ifdef TRACE_EXT2
#	define TRACE(x...) dprintf("\33[34mext2:\33[0m " x)
#	define ASSERT(x) { if (!(x)) kernel_debugger("ext2: assert failed: " #x "\n"); }
#else
#	define TRACE(x...) ;
#	define ASSERT(x) ;
#endif


struct HashedEntry
{
	uint8*	position;
	uint32	hash;

	bool	operator<(const HashedEntry& other)	const
	{
		return hash <= other.hash;
	}

	bool	operator>(const HashedEntry& other)	const
	{
		return hash >= other.hash;
	}
};


DirectoryIterator::DirectoryIterator(Inode* directory, off_t start,
	HTreeEntryIterator* parent)
	:
	fDirectory(directory),
	fVolume(directory->GetVolume()),
	fBlockSize(fVolume->BlockSize()),
	fParent(parent),
	fNumBlocks(directory->Size() == 0 ? 0
		: (directory->Size() - 1) / fBlockSize + 1),
	fLogicalBlock(start / fBlockSize),
	fDisplacement(start % fBlockSize),
	fPreviousDisplacement(fDisplacement),
	fStartLogicalBlock(fLogicalBlock),
	fStartDisplacement(fDisplacement)
{
	TRACE("DirectoryIterator::DirectoryIterator() %" B_PRIdINO ": num blocks: "
		"%" B_PRIu32 "\n", fDirectory->ID(), fNumBlocks);
	fIndexing = parent != NULL;
	fInitStatus = fDirectory->FindBlock(start, fPhysicalBlock);
	fStartPhysicalBlock = fPhysicalBlock;
}


DirectoryIterator::~DirectoryIterator()
{
	TRACE("DirectoryIterator::~DirectoryIterator(): %p, parent: %p\n", this,
		fParent);
	delete fParent;
	TRACE("DirectoryIterator::~DirectoryIterator(): Deleted the parent\n");
}


status_t
DirectoryIterator::InitCheck()
{
	return fInitStatus;
}


status_t
DirectoryIterator::Get(char* name, size_t* _nameLength, ino_t* _id)
{
	TRACE("DirectoryIterator::Get() ID %" B_PRIdINO "\n", fDirectory->ID());
	if (_Offset() >= fDirectory->Size()) {
		TRACE("DirectoryIterator::Get() out of entries\n");
		return B_ENTRY_NOT_FOUND;
	}

	CachedBlock cached(fVolume);
	const uint8* block = cached.SetTo(fPhysicalBlock);
	if (block == NULL)
		return B_IO_ERROR;

	ASSERT(_CheckBlock(block) == B_OK);

	TRACE("DirectoryIterator::Get(): Displacement: %" B_PRIu32 "\n",
		fDisplacement);
	const ext2_dir_entry* entry = (const ext2_dir_entry*)&block[fDisplacement];

	if (entry->Length() == 0 || entry->InodeID() == 0)
		return B_BAD_DATA;

	if (entry->NameLength() != 0) {
		size_t length = entry->NameLength();

		TRACE("block %" B_PRIu32 ", displacement %" B_PRIu32 ": entry ino %"
			B_PRIu32 ", length %u, name length %" B_PRIuSIZE ", type %u\n",
			fLogicalBlock, fDisplacement, entry->InodeID(), entry->Length(),
			length,	entry->FileType());

		if (*_nameLength > 0) {
			if (length + 1 > *_nameLength)
				return B_BUFFER_OVERFLOW;

			memcpy(name, entry->name, length);
			name[length] = '\0';

			*_nameLength = length;
		}

		*_id = entry->InodeID();
	} else
		*_nameLength = 0;

	return B_OK;
}


status_t
DirectoryIterator::GetNext(char* name, size_t* _nameLength, ino_t* _id)
{
	status_t status;
	while ((status = Get(name, _nameLength, _id)) == B_BAD_DATA) {
		status = Next();
		if (status != B_OK)
			return status;
	}
	return status;
}


status_t
DirectoryIterator::Next()
{
	TRACE("DirectoryIterator::Next() fDirectory->ID() %" B_PRIdINO "\n",
		fDirectory->ID());

	if (_Offset() >= fDirectory->Size()) {
		TRACE("DirectoryIterator::Next() out of entries\n");
		return B_ENTRY_NOT_FOUND;
	}

	TRACE("DirectoryIterator::Next(): Creating cached block\n");

	CachedBlock cached(fVolume);
	ext2_dir_entry* entry;

	TRACE("DirectoryIterator::Next(): Loading cached block\n");
	const uint8* block = cached.SetTo(fPhysicalBlock);
	if (block == NULL)
		return B_IO_ERROR;

	ASSERT(_CheckBlock(block) == B_OK);

	entry = (ext2_dir_entry*)(block + fDisplacement);

	do {
		TRACE("Checking entry at block %" B_PRIu64 ", displacement %" B_PRIu32
			" entry inodeid %" B_PRIu32 "\n", fPhysicalBlock, fDisplacement,
			entry->InodeID());

		if (entry->Length() != 0) {
			if (!entry->IsValid()) {
				TRACE("invalid entry.\n");
				return B_BAD_DATA;
			}
			fPreviousDisplacement = fDisplacement;
			fDisplacement += entry->Length();
		} else 
			fDisplacement = fBlockSize;

		if (fDisplacement == fBlockSize) {
			TRACE("Reached end of block\n");

			fDisplacement = 0;

			status_t status = _NextBlock();
			if (status != B_OK)
				return status;
						
			if ((off_t)(_Offset() + ext2_dir_entry::MinimumSize())
					>= fDirectory->Size()) {
				TRACE("DirectoryIterator::Next() end of directory file\n");
				return B_ENTRY_NOT_FOUND;
			}
			status = fDirectory->FindBlock(_Offset(), fPhysicalBlock);
			if (status != B_OK)
				return status;

			block = cached.SetTo(fPhysicalBlock);
			if (block == NULL)
				return B_IO_ERROR;
			ASSERT(_CheckBlock(block) == B_OK);

		} else if (fDisplacement > fBlockSize) {
			TRACE("The entry isn't block aligned.\n");
			// TODO: Is block alignment obligatory?
			return B_BAD_DATA;
		}

		entry = (ext2_dir_entry*)(block + fDisplacement);

		TRACE("DirectoryIterator::Next() skipping entry %d %" B_PRIu32 "\n",
			entry->Length(), entry->InodeID());
	} while (entry->Length() == 0 || entry->InodeID() == 0);

	TRACE("DirectoryIterator::Next() entry->Length() %d entry->name %*s\n",
			entry->Length(), entry->NameLength(), entry->name);

	return B_OK;
}


status_t
DirectoryIterator::Rewind()
{
	fDisplacement = 0;
	fPreviousDisplacement = 0;
	fLogicalBlock = 0;

	return fDirectory->FindBlock(0, fPhysicalBlock);
}


void
DirectoryIterator::Restart()
{
	TRACE("DirectoryIterator::Restart(): (logical, physical, displacement): "
		"current: (%" B_PRIu32 ", %" B_PRIu64 ", %" B_PRIu32 "), start: (%"
		B_PRIu32 ", %" B_PRIu64 ", %" B_PRIu32 ")\n", fLogicalBlock,
		fPhysicalBlock, fDisplacement, fStartLogicalBlock, fStartPhysicalBlock,
		fStartDisplacement);
	fLogicalBlock = fStartLogicalBlock;
	fPhysicalBlock = fStartPhysicalBlock;
	fDisplacement = fPreviousDisplacement = fStartDisplacement;
}


status_t
DirectoryIterator::AddEntry(Transaction& transaction, const char* name,
	size_t _nameLength, ino_t id, uint8 type)
{
	TRACE("DirectoryIterator::AddEntry(%s, ...)\n", name);

	uint8 nameLength = _nameLength > EXT2_NAME_LENGTH ? EXT2_NAME_LENGTH
		: _nameLength;

	status_t status = B_OK;
	while (status == B_OK) {
		uint16 pos = 0;
		uint16 newLength;

		status = _AllocateBestEntryInBlock(nameLength, pos, newLength);
		if (status == B_OK) {
			return _AddEntry(transaction, name, nameLength, id, type, newLength,
				pos);
		} else if (status != B_DEVICE_FULL)
			return status;
		
		fDisplacement = 0;
		status = _NextBlock();
		if (status == B_OK)
			status = fDirectory->FindBlock(_Offset(), fPhysicalBlock);
	}

	if (status != B_ENTRY_NOT_FOUND)
		return status;

	bool firstSplit = fNumBlocks == 1 && fVolume->IndexedDirectories();

	fNumBlocks++;

	if (fIndexing) {
		TRACE("DirectoryIterator::AddEntry(): Adding another HTree leaf\n");
		fNumBlocks += fParent->BlocksNeededForNewEntry();
	} else if (firstSplit) {
		// Allocate another block (fNumBlocks should become 3)
		TRACE("DirectoryIterator::AddEntry(): Creating index for directory\n");
		fNumBlocks++;
	} else
		TRACE("DirectoryIterator::AddEntry(): Enlarging directory\n");

	status = fDirectory->Resize(transaction, fNumBlocks * fBlockSize);
	if (status != B_OK)
		return status;

	if (firstSplit || fIndexing) {
		// firstSplit and fIndexing are mutually exclusive
		return _SplitIndexedBlock(transaction, name, nameLength, id, type,
			fNumBlocks - 1, firstSplit);
	}

	fLogicalBlock = fNumBlocks - 1;
	status = fDirectory->FindBlock(fLogicalBlock * fBlockSize, fPhysicalBlock);
	if (status != B_OK)
		return status;

	return _AddEntry(transaction, name, nameLength, id, type, fBlockSize, 0,
		false);
}


status_t
DirectoryIterator::FindEntry(const char* name, ino_t* _id)
{
	TRACE("DirectoryIterator::FindEntry(): %p %p\n", this, name);
	char buffer[EXT2_NAME_LENGTH + 1];
	ino_t id;

	status_t status = B_OK;
	size_t length = strlen(name);
	while (status == B_OK) {
		size_t nameLength = EXT2_NAME_LENGTH;
		status = Get(buffer, &nameLength, &id);
		if (status == B_OK) {
			if (length == nameLength 
				&& strncmp(name, buffer, nameLength) == 0) {
				if (_id != NULL)
					*_id = id;
				return B_OK;
			}
		} else if (status != B_BAD_DATA)
			break;
		status = Next();
	}

	return status;
}


status_t
DirectoryIterator::RemoveEntry(Transaction& transaction)
{
	TRACE("DirectoryIterator::RemoveEntry()\n");
	ext2_dir_entry* previousEntry;
	ext2_dir_entry* dirEntry;
	CachedBlock cached(fVolume);

	uint8* block = cached.SetToWritable(transaction, fPhysicalBlock);
	uint32 maxSize = _MaxSize();

	if (fDisplacement == 0) {
		previousEntry = (ext2_dir_entry*)&block[fDisplacement];

		fPreviousDisplacement = fDisplacement;
		fDisplacement += previousEntry->Length();

		if (fDisplacement == maxSize) {
			previousEntry->SetInodeID(0);
			fDisplacement = 0;
			return B_OK;
		} else if (fDisplacement > maxSize) {
			TRACE("DirectoryIterator::RemoveEntry(): Entry isn't aligned to "
				"block entry.");
			return B_BAD_DATA;
		}

		dirEntry = (ext2_dir_entry*)&block[fDisplacement];
		memcpy(&block[fPreviousDisplacement], &block[fDisplacement],
			dirEntry->Length());

		previousEntry->SetLength(fDisplacement - fPreviousDisplacement
			+ previousEntry->Length());

		fDirectory->SetDirEntryChecksum(block);

		ASSERT(_CheckBlock(block) == B_OK);

		return B_OK;
	}

	TRACE("DirectoryIterator::RemoveEntry() fDisplacement %" B_PRIu32 "\n",
		fDisplacement);

	if (fPreviousDisplacement == fDisplacement) {
		char buffer[EXT2_NAME_LENGTH + 1];

		dirEntry = (ext2_dir_entry*)&block[fDisplacement];

		memcpy(buffer, dirEntry->name, (uint32)dirEntry->name_length);

		fDisplacement = 0;
		status_t status = FindEntry(dirEntry->name);
		if (status == B_ENTRY_NOT_FOUND)
			return B_BAD_DATA;
		if (status != B_OK)
			return status;
	}

	previousEntry = (ext2_dir_entry*)&block[fPreviousDisplacement];
	dirEntry = (ext2_dir_entry*)&block[fDisplacement];

	previousEntry->SetLength(previousEntry->Length() + dirEntry->Length());

	memset(&block[fDisplacement], 0, 
		fPreviousDisplacement + previousEntry->Length() - fDisplacement);

	fDirectory->SetDirEntryChecksum(block);

	ASSERT(_CheckBlock(block) == B_OK);

	return B_OK;
}


status_t
DirectoryIterator::ChangeEntry(Transaction& transaction, ino_t id,
	uint8 fileType)
{
	CachedBlock cached(fVolume);

	uint8* block = cached.SetToWritable(transaction, fPhysicalBlock);
	if (block == NULL)
		return B_IO_ERROR;

	ext2_dir_entry* dirEntry = (ext2_dir_entry*)&block[fDisplacement];
	dirEntry->SetInodeID(id);
	dirEntry->file_type = fileType;

	fDirectory->SetDirEntryChecksum(block);

	ASSERT(_CheckBlock(block) == B_OK);

	return B_OK;
}


status_t
DirectoryIterator::_AllocateBestEntryInBlock(uint8 nameLength, uint16& pos,
	uint16& newLength)
{
	TRACE("DirectoryIterator::_AllocateBestEntryInBlock()\n");
	CachedBlock cached(fVolume);
	const uint8* block = cached.SetTo(fPhysicalBlock);

	ASSERT(_CheckBlock(block) == B_OK);

	uint16 requiredLength = EXT2_DIR_REC_LEN(nameLength);
	uint32 maxSize = _MaxSize();
	
	uint16 bestPos = maxSize;
	uint16 bestLength = maxSize;
	uint16 bestRealLength = maxSize;
	ext2_dir_entry* dirEntry;
	
	while (pos < maxSize) {
		dirEntry = (ext2_dir_entry*)&block[pos];
		if (!_CheckDirEntry(dirEntry, block)) {
			TRACE("DirectoryIterator::_AllocateBestEntryInBlock(): invalid "
				"dirEntry->Length() pos %d\n", pos);
			return B_BAD_DATA;
		}

		uint16 realLength = EXT2_DIR_REC_LEN(dirEntry->NameLength());
		uint16 emptySpace = dirEntry->Length();
		if (dirEntry->InodeID() != 0)
			emptySpace -= realLength;
		if (emptySpace == requiredLength) {
			// Found an exact match
			TRACE("DirectoryIterator::_AllocateBestEntryInBlock(): Found an "
				"exact length match\n");
			newLength = realLength;

			return B_OK;
		} else if (emptySpace > requiredLength && emptySpace < bestLength) {
			bestPos = pos;
			bestLength = emptySpace;
			bestRealLength = realLength;
		}

		pos += dirEntry->Length();
	}
	
	if (bestPos == maxSize)
		return B_DEVICE_FULL;

	TRACE("DirectoryIterator::_AllocateBestEntryInBlock(): Found a suitable "
		"location: %u\n", bestPos);
	pos = bestPos;
	newLength = bestRealLength;

	return B_OK;
}


status_t
DirectoryIterator::_AddEntry(Transaction& transaction, const char* name,
	uint8 nameLength, ino_t id, uint8 type, uint16 newLength, uint16 pos,
	bool hasPrevious)
{
	TRACE("DirectoryIterator::_AddEntry(%s, %d, %" B_PRIdINO ", %d, %d, %d, "
		"%c)\n", name, nameLength, id, type, newLength, pos,
		hasPrevious ? 't' : 'f');
	CachedBlock cached(fVolume);

	uint8* block = cached.SetToWritable(transaction, fPhysicalBlock);
	if (block == NULL)
		return B_IO_ERROR;

	ext2_dir_entry* dirEntry = (ext2_dir_entry*)&block[pos];

	if (hasPrevious) {
		uint16 previousLength = dirEntry->Length();
		dirEntry->SetLength(newLength);

		dirEntry = (ext2_dir_entry*)&block[pos + newLength];
		newLength = previousLength - newLength;
	}

	dirEntry->SetLength(newLength);
	dirEntry->name_length = nameLength;
	dirEntry->SetInodeID(id);
	dirEntry->file_type = type;
	memcpy(dirEntry->name, name, nameLength);

	fDirectory->SetDirEntryChecksum(block);

	ASSERT(_CheckBlock(block) == B_OK);

	TRACE("DirectoryIterator::_AddEntry(): Done\n");

	return B_OK;
}


status_t
DirectoryIterator::_SplitIndexedBlock(Transaction& transaction,
	const char* name, uint8 nameLength, ino_t id, uint8 type,
	uint32 newBlocksPos, bool firstSplit)
{
	// Block is full, split required
	TRACE("DirectoryIterator::_SplitIndexedBlock(.., %s, %u, %" B_PRIdINO ", %"
		B_PRIu32 ", %c)\n", name, nameLength, id, newBlocksPos,
		firstSplit ? 't' : 'f');

	// Allocate a buffer for the entries in the block
	uint8* buffer = new(std::nothrow) uint8[fBlockSize];
	if (buffer == NULL)
		return B_NO_MEMORY;
	ArrayDeleter<uint8> bufferDeleter(buffer);

	fsblock_t firstPhysicalBlock = 0;
	uint32 maxSize = _MaxSize();

	// Prepare block to hold the first half of the entries and fill the buffer
	CachedBlock cachedFirst(fVolume);

	if (firstSplit) {
		// Save all entries to the buffer
		status_t status = fDirectory->FindBlock(0, firstPhysicalBlock);
		if (status != B_OK)
			return status;

		const uint8* srcBlock = cachedFirst.SetTo(firstPhysicalBlock);
		if (srcBlock == NULL)
			return B_IO_ERROR;

		memcpy(buffer, srcBlock, fBlockSize);

		status = fDirectory->FindBlock(fBlockSize, fPhysicalBlock);
		if (status != B_OK)
			return status;
	}

	uint8* firstBlock = cachedFirst.SetToWritable(transaction, fPhysicalBlock);
	uint8* secondBlock = NULL;
	if (firstBlock == NULL)
		return B_IO_ERROR;

	status_t status;

	if (!firstSplit) {
		// Save all entries to the buffer
		memcpy(buffer, firstBlock, fBlockSize);
	} else {
		// Initialize the root node
		fDirectory->Node().SetFlag(EXT2_INODE_INDEXED);
		HTreeRoot* root;

		secondBlock = cachedFirst.SetToWritable(transaction,
			firstPhysicalBlock, true);
		if (secondBlock == NULL)
			return B_IO_ERROR;

		status = fDirectory->WriteBack(transaction);
		if (status != B_OK)
			return status;

		memcpy(secondBlock, buffer, 2 * (sizeof(HTreeFakeDirEntry) + 4));

		root = (HTreeRoot*)secondBlock;

		HTreeFakeDirEntry* dotdot = &root->dotdot;
		dotdot->SetEntryLength(fBlockSize - (sizeof(HTreeFakeDirEntry) + 4));

		root->hash_version = fVolume->DefaultHashVersion();
		root->root_info_length = 8;
		root->indirection_levels = 0;
		uint32 rootMaxSize = fBlockSize;
		if (fVolume->HasMetaGroupChecksumFeature())
			rootMaxSize -= sizeof(ext2_htree_tail);

		root->count_limit->SetLimit((rootMaxSize
			- ((uint8*)root->count_limit - secondBlock)) / sizeof(HTreeEntry));
		root->count_limit->SetCount(2);
	}

	// Sort entries
	VectorSet<HashedEntry> entrySet;

	HTree htree(fVolume, fDirectory);
	status = htree.PrepareForHash();
	if (status != B_OK)
		return status;

	uint32 displacement = firstSplit ? 2 * (sizeof(HTreeFakeDirEntry) + 4) : 0;

	HashedEntry entry;
	ext2_dir_entry* dirEntry = NULL;

	while (displacement < maxSize) {
		entry.position = &buffer[displacement];
		dirEntry = (ext2_dir_entry*)entry.position;

		TRACE("DirectoryIterator::_SplitIndexedBlock(): pos: %p, name "
			"length: %u, entry length: %u\n", entry.position,
			dirEntry->name_length,
			dirEntry->Length());

		char cbuffer[256];
		memcpy(cbuffer, dirEntry->name, dirEntry->name_length);
		cbuffer[dirEntry->name_length] = '\0';
		entry.hash = htree.Hash(dirEntry->name, dirEntry->name_length);
		TRACE("DirectoryIterator::_SplitIndexedBlock(): %s -> %" B_PRIu32 "\n",
			cbuffer, entry.hash);

		status = entrySet.Insert(entry);
		if (status != B_OK)
			return status;

		displacement += dirEntry->Length();
	}

	// Prepare the new entry to be included as well
	ext2_dir_entry newEntry;

	uint16 newLength = EXT2_DIR_REC_LEN(nameLength);

	newEntry.name_length = nameLength;
	newEntry.SetLength(newLength);
	newEntry.SetInodeID(id);
	newEntry.file_type = type;
	memcpy(newEntry.name, name, nameLength);

	entry.position = (uint8*)&newEntry;
	entry.hash = htree.Hash(name, nameLength);
	TRACE("DirectoryIterator::_SplitIndexedBlock(): %s -> %" B_PRIu32 "\n",
		name, entry.hash);

	entrySet.Insert(entry);

	// Move first half of entries to the first block
	VectorSet<HashedEntry>::Iterator iterator = entrySet.Begin();
	int32 median = entrySet.Count() / 2;
	displacement = 0;
	TRACE("DirectoryIterator::_SplitIndexedBlock(): Count: %" B_PRId32
		", median: %" B_PRId32 "\n", entrySet.Count(), median);

	uint32 previousHash = (*iterator).hash;

	for (int32 i = 0; i < median; ++i) {
		dirEntry = (ext2_dir_entry*)(*iterator).position;
		previousHash = (*iterator).hash;

		uint32 realLength = EXT2_DIR_REC_LEN(dirEntry->name_length);

		dirEntry->SetLength((uint16)realLength);
		memcpy(&firstBlock[displacement], dirEntry, realLength);

		displacement += realLength;
		iterator++;
	}

	// Update last entry in the block
	uint16 oldLength = dirEntry->Length();
	dirEntry = (ext2_dir_entry*)&firstBlock[displacement - oldLength];
	dirEntry->SetLength(maxSize - displacement + oldLength);

	fDirectory->SetDirEntryChecksum(firstBlock);

	bool collision = false;

	while (iterator != entrySet.End() && (*iterator).hash == previousHash) {
		// Keep collisions on the same block
		TRACE("DirectoryIterator::_SplitIndexedBlock(): Handling collisions\n");

		// This isn't the ideal solution, but it is a rare occurance
		dirEntry = (ext2_dir_entry*)(*iterator).position;

		if (displacement + dirEntry->Length() > maxSize) {
			// Doesn't fit on the block
			collision = true;
			break;
		}

		memcpy(&firstBlock[displacement], dirEntry, dirEntry->Length());

		displacement += dirEntry->Length();
		iterator++;
	}

	// Save the hash to store in the parent
	uint32 medianHash = (*iterator).hash;

	// Update parent
	if (firstSplit) {
		TRACE("DirectoryIterator::_SplitIndexedBlock(): Updating root\n");
		HTreeRoot* root = (HTreeRoot*)secondBlock;
		HTreeEntry* htreeEntry = (HTreeEntry*)root->count_limit;
		htreeEntry->SetBlock(1);
		
		++htreeEntry;
		htreeEntry->SetBlock(2);
		htreeEntry->SetHash(medianHash);


		off_t start = (off_t)root->root_info_length
			+ 2 * (sizeof(HTreeFakeDirEntry) + 4);
		_SetHTreeEntryChecksum(secondBlock, start, 2);
		fParent = new(std::nothrow) HTreeEntryIterator(start, fDirectory);
		if (fParent == NULL)
			return B_NO_MEMORY;
		
		fLogicalBlock = 1;
		status = fDirectory->FindBlock(fLogicalBlock * fBlockSize,
			fPhysicalBlock);

		fPreviousDisplacement = fDisplacement = 0;

		status = fParent->Init();
	}
	else {
		status = fParent->InsertEntry(transaction, medianHash, fNumBlocks - 1,
			newBlocksPos, collision);
	}
	if (status != B_OK)
		return status;

	// Prepare last block to hold the second half of the entries
	TRACE("DirectoryIterator::_SplitIndexedBlock(): Preparing second leaf "
		"block\n");
	fDisplacement = 0;

	status = fDirectory->FindBlock(fDirectory->Size() - 1, fPhysicalBlock);
	if (status != B_OK)
		return status;

	CachedBlock cachedSecond(fVolume);
	secondBlock = cachedSecond.SetToWritable(transaction,
		fPhysicalBlock);
	if (secondBlock == NULL)
		return B_IO_ERROR;

	// Move the second half of the entries to the second block
	VectorSet<HashedEntry>::Iterator end = entrySet.End();
	displacement = 0;

	while (iterator != end) {
		dirEntry = (ext2_dir_entry*)(*iterator).position;

		uint32 realLength = EXT2_DIR_REC_LEN(dirEntry->name_length);

		dirEntry->SetLength((uint16)realLength);
		memcpy(&secondBlock[displacement], dirEntry, realLength);

		displacement += realLength;
		iterator++;
	}

	// Update last entry in the block
	oldLength = dirEntry->Length();
	dirEntry = (ext2_dir_entry*)&secondBlock[displacement - oldLength];
	dirEntry->SetLength(maxSize - displacement + oldLength);

	fDirectory->SetDirEntryChecksum(secondBlock);

	ASSERT(_CheckBlock(firstBlock) == B_OK);
	ASSERT(_CheckBlock(secondBlock) == B_OK);

	TRACE("DirectoryIterator::_SplitIndexedBlock(): Done\n");
	return B_OK;
}


status_t
DirectoryIterator::_NextBlock()
{
	TRACE("DirectoryIterator::_NextBlock()\n");
	if (fIndexing) {
		TRACE("DirectoryIterator::_NextBlock(): Indexing\n");
		if (!fParent->HasCollision()) {
			TRACE("DirectoryIterator::_NextBlock(): next block doesn't "
				"contain collisions from previous block\n");
#ifndef COLLISION_TEST
			return B_ENTRY_NOT_FOUND;
#endif
		}

		return fParent->GetNext(fLogicalBlock);
	}

	if (++fLogicalBlock > fNumBlocks)
		return B_ENTRY_NOT_FOUND;

	return B_OK;
}


bool
DirectoryIterator::_CheckDirEntry(const ext2_dir_entry* dirEntry, const uint8* buffer)
{
	const char *errmsg = NULL;
	if (dirEntry->Length() < EXT2_DIR_REC_LEN(1))
		errmsg = "Length is too small";
	else if (dirEntry->Length() % 4 != 0)
		errmsg = "Length is not a multiple of 4";
	else if (dirEntry->Length() < EXT2_DIR_REC_LEN(dirEntry->NameLength()))
		errmsg = "Length is too short for the name";
	else if (((uint8*)dirEntry - buffer) + dirEntry->Length()
	         > (ptrdiff_t)fBlockSize) {
		errmsg = "Length is too big for the blocksize";
	}

	if (errmsg != NULL) {
		TRACE("DirectoryIterator::_CheckDirEntry() %s\n", errmsg);
	}
	return errmsg == NULL;
}


status_t
DirectoryIterator::_CheckBlock(const uint8* buffer)
{
	uint32 maxSize = fBlockSize;
	if (fVolume->HasMetaGroupChecksumFeature())
		maxSize -= sizeof(ext2_dir_entry_tail);

	status_t err = B_OK;
	uint16 pos = 0;
	while (pos < maxSize) {
		const ext2_dir_entry *dirEntry = (const ext2_dir_entry*)&buffer[pos];

		if (!_CheckDirEntry(dirEntry, buffer)) {
			TRACE("DirectoryIterator::_CheckBlock(): invalid "
				"dirEntry pos %d\n", pos);
			err = B_BAD_DATA;
		}

		pos += dirEntry->Length();
	}
	return err;
}


ext2_htree_tail*
DirectoryIterator::_HTreeEntryTail(uint8* block, uint16 offset) const
{
	HTreeEntry* entries = (HTreeEntry*)block;
	uint16 firstEntry = offset % fBlockSize / sizeof(HTreeEntry);
	HTreeCountLimit* countLimit = (HTreeCountLimit*)&entries[firstEntry];
	uint16 limit = countLimit->Limit();
	TRACE("DirectoryIterator::_HTreeEntryTail() %p %p\n", block, &entries[firstEntry + limit]);
	return (ext2_htree_tail*)(&entries[firstEntry + limit]);
}


uint32
DirectoryIterator::_HTreeRootChecksum(uint8* block, uint16 offset, uint16 count) const
{
	uint32 number = fDirectory->ID();
	uint32 checksum = calculate_crc32c(fVolume->ChecksumSeed(),
		(uint8*)&number, sizeof(number));
	uint32 gen = fDirectory->Node().generation;
	checksum = calculate_crc32c(checksum, (uint8*)&gen, sizeof(gen));
	checksum = calculate_crc32c(checksum, block,
		offset + count * sizeof(HTreeEntry));
	TRACE("DirectoryIterator::_HTreeRootChecksum() size %" B_PRIu64 "\n",
		offset + count * sizeof(HTreeEntry));
	ext2_htree_tail dummy = {};
	checksum = calculate_crc32c(checksum, (uint8*)&dummy, sizeof(dummy));
	return checksum;
}


void
DirectoryIterator::_SetHTreeEntryChecksum(uint8* block, uint16 offset, uint16 count)
{
	TRACE("DirectoryIterator::_SetHTreeEntryChecksum()\n");
	if (fVolume->HasMetaGroupChecksumFeature()) {
		ext2_htree_tail* tail = _HTreeEntryTail(block, offset);
		tail->reserved = 0x0;
		tail->checksum = _HTreeRootChecksum(block, offset, count);
	}
}


uint32
DirectoryIterator::_MaxSize()
{
	uint32 maxSize = fBlockSize;
	if (fVolume->HasMetaGroupChecksumFeature())
		maxSize -= sizeof(ext2_dir_entry_tail);
	return maxSize;
}