file_corruption/fs/Directory.cpp

/*
 * Copyright 2010, Ingo Weinhold, ingo_weinhold@gmx.de.
 * Distributed under the terms of the MIT License.
 */


#include "Directory.h"

#include <algorithm>
#include <new>

#include <AutoDeleter.h>

#include "Block.h"
#include "BlockAllocator.h"
#include "DebugSupport.h"
#include "Transaction.h"
#include "Volume.h"


class DirEntryBlock {
public:
								DirEntryBlock();
								DirEntryBlock(
									checksumfs_dir_entry_block* entryBlock,
									size_t entryBlockSize);

			void				SetTo(checksumfs_dir_entry_block* entryBlock,
									size_t entryBlockSize);

	inline	int32				EntryCount() const;
	inline	size_t				BytesUsedFor(int32 entryCount) const;
	inline	size_t				BytesUsed() const;
	inline	size_t				FreeSpace() const;

	inline	uint64				BlockIndexAt(int32 index) const;
			const char*			NameAt(int32 index, size_t& _nameLength) const;

			int32				FindInsertionIndex(const char* name,
									size_t nameLength, bool& _exactMatch) const;

			int32				FindSplitIndex(int32 index,
									size_t bytesNeeded) const;

			void				InsertEntry(int32 index, const char* name,
									size_t nameLength, uint64 blockIndex);
			void				ReplaceEntryName(int32 index, const char* name,
									size_t nameLength);
			void				RemoveEntry(int32 index);

			void				SplitBlock(int32 splitIndex,
									DirEntryBlock& other);

			bool				Check() const;

private:
			checksumfs_dir_entry_block* fBlock;
			size_t				fBlockSize;
};


class DirEntryTree {
public:
								DirEntryTree(Directory* directory);

			status_t			LookupEntry(const char* name,
									uint64& _blockIndex);
			status_t			LookupNextEntry(const char* name,
									char* foundName, size_t& _foundNameLength,
									uint64& _blockIndex);

			status_t			InsertEntry(const char* name, uint64 blockIndex,
									Transaction& transaction);
			status_t			RemoveEntry(const char* name,
									Transaction& transaction);

			status_t			FreeTree(Transaction& transaction);

			bool				IsEmpty() const;

			bool				Check();

private:
			struct LevelInfo {
				Block			block;
				DirEntryBlock	entryBlock;
				int32			index;
				bool			exactMatch;
			};

private:
			status_t			_InitReadOnly();
			status_t			_InitWritable(Transaction& transaction);
			status_t			_InitCommon();

			status_t			_UpdateOrInsertKey(LevelInfo* infos,
									int32 level, const char* name,
									size_t nameLength, uint64 blockIndex,
									bool insertKey, Transaction& transaction);

			status_t			_InsertEntryIncrementDepth(LevelInfo* infos,
									Transaction& transaction);
			status_t			_InsertEntrySplitBlock(int32 level,
									LevelInfo& info, size_t needed,
									Transaction& transaction, Block& newBlock,
									int32& _splitIndex);

			bool				_Check(int32 level, uint64 blockIndex,
									const char* key, size_t keyLength,
									DirEntryBlock& entryBlock);

	inline	uint16				_Depth() const	{ return fTree->depth; }

private:
			Directory*			fDirectory;
			Block				fRootBlock;
			checksumfs_dir_entry_tree* fTree;
			checksumfs_dir_entry_block* fRootEntryBlock;
			size_t				fRootEntryBlockSize;
};


// #pragma mark -


static int
compare_names(const char* a, size_t lengthA, const char* b, size_t lengthB)
{
	int cmp = strncmp(a, b, std::min(lengthA, lengthB));
	if (cmp != 0)
		return cmp;

	return (int)lengthA - (int)lengthB;
		// assumes we don't overflow 31 bits
}


// #pragma mark - DirEntryBlock


DirEntryBlock::DirEntryBlock()
	:
	fBlock(NULL),
	fBlockSize(0)
{
}


DirEntryBlock::DirEntryBlock(checksumfs_dir_entry_block* entryBlock,
	size_t entryBlockSize)
	:
	fBlock(entryBlock),
	fBlockSize(entryBlockSize)
{
}


void
DirEntryBlock::SetTo(checksumfs_dir_entry_block* entryBlock,
	size_t entryBlockSize)
{
	fBlock = entryBlock;
	fBlockSize = entryBlockSize;
}


int32
DirEntryBlock::EntryCount() const
{
	return fBlock->entryCount;
}


size_t
DirEntryBlock::BytesUsedFor(int32 entryCount) const
{
	if (entryCount == 0)
		return sizeof(*fBlock);
	return sizeof(*fBlock) + 10 * entryCount
		+ fBlock->nameEnds[entryCount - 1];
}


size_t
DirEntryBlock::BytesUsed() const
{
	return BytesUsedFor(EntryCount());
}


size_t
DirEntryBlock::FreeSpace() const
{
	return fBlockSize - BytesUsed();
}


uint64
DirEntryBlock::BlockIndexAt(int32 index) const
{
	uint64* blockIndices
		= (uint64*)((uint8*)fBlock + fBlockSize) - 1;
	return blockIndices[-index];
}


const char*
DirEntryBlock::NameAt(int32 index, size_t& _nameLength) const
{
	int32 entryCount = EntryCount();
	if (index < 0 || index >= entryCount)
		return NULL;

	uint32 nameOffset = index > 0 ? fBlock->nameEnds[index - 1] : 0;
	_nameLength = fBlock->nameEnds[index] - nameOffset;
	return (const char*)(fBlock->nameEnds + entryCount) + nameOffset;
}


int32
DirEntryBlock::FindInsertionIndex(const char* name, size_t nameLength,
	bool& _exactMatch) const
{
	int32 entryCount = EntryCount();
	if (entryCount == 0) {
		_exactMatch = false;
		return 0;
	}

	const char* entryNames = (char*)(fBlock->nameEnds + entryCount);
	uint32 nameOffset = 0;

	int32 index = 0;
	int cmp = -1;

	// TODO: Binary search!
	for (; index < entryCount; index++) {
		const char* entryName = entryNames + nameOffset;
		size_t entryNameLength = fBlock->nameEnds[index] - nameOffset;

		cmp = compare_names(entryName, entryNameLength, name, nameLength);
		if (cmp >= 0)
			break;

		nameOffset += entryNameLength;
	}

	_exactMatch = cmp == 0;
	return index;
}


/*!	Finds a good split index for an insertion of \a bytesNeeded bytes at
	index \a index.
*/
int32
DirEntryBlock::FindSplitIndex(int32 index, size_t bytesNeeded) const
{
	size_t splitSize = (BytesUsed() + bytesNeeded) / 2;

	int32 entryCount = EntryCount();
	for (int32 i = 0; i < entryCount; i++) {
		size_t bytesUsed = BytesUsedFor(i + 1);
		if (i == index)
			bytesUsed += bytesNeeded;
		if (bytesUsed > splitSize)
			return i;
	}

	// This should never happen.
	return entryCount;
}


void
DirEntryBlock::InsertEntry(int32 index, const char* name, size_t nameLength,
	uint64 blockIndex)
{
	uint64* blockIndices = (uint64*)((uint8*)fBlock + fBlockSize) - 1;
	int32 entryCount = fBlock->entryCount;
	char* entryNames = (char*)(fBlock->nameEnds + entryCount);

	uint32 nameOffset = index == 0 ? 0 : fBlock->nameEnds[index - 1];
	uint32 lastNameEnd = entryCount == 0
		? 0 : fBlock->nameEnds[entryCount - 1];

	if (index < entryCount) {
		// make room in the block indices array
		memmove(&blockIndices[-entryCount], &blockIndices[1 - entryCount],
			8 * (entryCount - index));

		// make room in the name array -- we also move 2 bytes more for the
		// new entry in the nameEnds array
		memmove(entryNames + nameOffset + nameLength + 2,
			entryNames + nameOffset, lastNameEnd - nameOffset);

		// move the names < index by 2 bytes
		if (index > 0)
			memmove(entryNames + 2, entryNames, nameOffset);

		// move and update the nameEnds entries > index
		for (int32 i = entryCount; i > index; i--)
			fBlock->nameEnds[i] = fBlock->nameEnds[i - 1] + nameLength;
	} else if (entryCount > 0) {
		// the nameEnds array grows -- move all names
		memmove(entryNames + 2, entryNames, lastNameEnd);
	}

	// we have made room -- insert the entry
	entryNames += 2;
	memcpy(entryNames + nameOffset, name, nameLength);
	fBlock->nameEnds[index] = nameOffset + nameLength;
	blockIndices[-index] = blockIndex;
	fBlock->entryCount++;
ASSERT(Check());
}


void
DirEntryBlock::ReplaceEntryName(int32 index, const char* name,
	size_t nameLength)
{
	int32 entryCount = fBlock->entryCount;
	char* entryNames = (char*)(fBlock->nameEnds + entryCount);

	ASSERT(index >= 0 && index < entryCount);

	uint32 nameOffset = index == 0 ? 0 : fBlock->nameEnds[index - 1];
	uint32 oldNameLength = fBlock->nameEnds[index] - nameOffset;
	uint32 lastNameEnd = fBlock->nameEnds[entryCount - 1];

	if (oldNameLength != nameLength) {
		int32 lengthDiff = (int32)nameLength - (int32)oldNameLength;

		ASSERT(lengthDiff <= (int32)FreeSpace());

		// move names after the changing name
		if (index + 1 < entryCount) {
			memmove(entryNames + nameOffset + nameLength,
				entryNames + nameOffset + oldNameLength,
				lastNameEnd - nameOffset - oldNameLength);
		}

		// update the name ends
		for (int32 i = index; i < entryCount; i++)
			fBlock->nameEnds[i] = (int32)fBlock->nameEnds[i] + lengthDiff;
	}

	// copy the name
	memcpy(entryNames + nameOffset, name, nameLength);
ASSERT(Check());
}


void
DirEntryBlock::RemoveEntry(int32 index)
{
	ASSERT(index >= 0 && index < EntryCount());

	int32 entryCount = EntryCount();
	if (entryCount == 1) {
		// simple case -- removing the last entry
		fBlock->entryCount = 0;
		return;
	}

	uint64* blockIndices = (uint64*)((uint8*)fBlock + fBlockSize) - 1;
	char* entryNames = (char*)(fBlock->nameEnds + entryCount);

	uint32 nameOffset = index == 0 ? 0 : fBlock->nameEnds[index - 1];
	uint32 nameEnd = fBlock->nameEnds[index];
	uint32 lastNameEnd = entryCount == 0
		? 0 : fBlock->nameEnds[entryCount - 1];

	if (index < entryCount - 1) {
		uint32 nameLength = nameEnd - nameOffset;

		// remove the element from the block indices array
		memmove(&blockIndices[-entryCount + 2], &blockIndices[-entryCount + 1],
			8 * (entryCount - index - 1));

		// move and update the nameEnds entries > index
		for (int32 i = index + 1; i < entryCount; i++)
			fBlock->nameEnds[i - 1] = fBlock->nameEnds[i] - nameLength;

		// move the names < index by 2 bytes
		if (index > 0)
			memmove(entryNames - 2, entryNames, nameOffset);

		// move the names > index
		memmove(entryNames - 2 + nameOffset, entryNames + nameEnd,
			lastNameEnd - nameEnd);
	} else {
		// the nameEnds array shrinks -- move all names
		memmove(entryNames - 2, entryNames, nameOffset);
	}

	// we have removed the entry
	fBlock->entryCount--;
ASSERT(Check());
}


/*!	Moves all entries beyond \a splitIndex (inclusively) to the empty block
	\a other.
*/
void
DirEntryBlock::SplitBlock(int32 splitIndex, DirEntryBlock& other)
{
	ASSERT(other.EntryCount() == 0);
	ASSERT(splitIndex <= EntryCount());

	int32 entryCount = EntryCount();
	if (splitIndex == entryCount)
		return;
	int32 otherEntryCount = entryCount - splitIndex;

	// copy block indices
	uint64* blockIndices = (uint64*)((uint8*)fBlock + fBlockSize);
	uint64* otherBlockIndices
		= (uint64*)((uint8*)other.fBlock + other.fBlockSize);
		// note: both point after the last entry, unlike in other methods
	memcpy(otherBlockIndices - otherEntryCount, blockIndices - entryCount,
		8 * otherEntryCount);

	// copy the name end offsets
	uint32 namesOffset = splitIndex > 0
		? fBlock->nameEnds[splitIndex - 1] : 0;
	for (int32 i = splitIndex; i < entryCount; i++) {
		other.fBlock->nameEnds[i - splitIndex] = fBlock->nameEnds[i]
			- namesOffset;
	}

	// copy the names
	char* entryNames = (char*)(fBlock->nameEnds + entryCount);
	char* otherEntryNames
		= (char*)(other.fBlock->nameEnds + otherEntryCount);
	memcpy(otherEntryNames, entryNames + namesOffset,
		fBlock->nameEnds[entryCount - 1] - namesOffset);

	// the name ends array shrinks -- move the names
	if (splitIndex > 0) {
		char* newEntryNames = (char*)(fBlock->nameEnds + splitIndex);
		memmove(newEntryNames, entryNames, namesOffset);
	}

	// update the entry counts
	fBlock->entryCount = splitIndex;
	other.fBlock->entryCount = otherEntryCount;
ASSERT(Check());
ASSERT(other.Check());
}


bool
DirEntryBlock::Check() const
{
	int32 entryCount = EntryCount();
	if (entryCount == 0)
		return true;

	// Check size: Both name ends and block index arrays must fit and we need
	// at least one byte per name.
	size_t size = sizeof(*fBlock) + entryCount * 10;
	if (size + entryCount > fBlockSize) {
		ERROR("Invalid dir entry block: entry count %d requires minimum size "
			"of %" B_PRIuSIZE " + %d bytes, but block size is %" B_PRIuSIZE
			"\n", (int)entryCount, size, (int)entryCount, fBlockSize);
		return false;
	}

	// check the name ends and block indices arrays and the names
	const char* entryNames = (char*)(fBlock->nameEnds + entryCount);
	const uint64* blockIndices = (uint64*)((uint8*)fBlock + fBlockSize) - 1;
	const char* previousName = NULL;
	uint16 previousNameLength = 0;
	uint16 previousEnd = 0;

	for (int32 i = 0; i < entryCount; i++) {
		// check name end
		uint16 nameEnd = fBlock->nameEnds[i];
		if (nameEnd <= previousEnd || nameEnd > fBlockSize - size) {
			ERROR("Invalid dir entry block: name end offset of entry %" B_PRId32
				": %u, previous: %u\n", i, nameEnd, previousEnd);
			return false;
		}

		// check name length
		uint16 nameLength = nameEnd - previousEnd;
		if (nameLength > kCheckSumFSNameLength) {
			ERROR("Invalid dir entry block: name of entry %" B_PRId32 " too "
				"long: %u\n", i, nameLength);
			return false;
		}

		// verify that the name doesn't contain a null char
		const char* name = entryNames + previousEnd;
		if (strnlen(name, nameLength) != nameLength) {
			ERROR("Invalid dir entry block: name of entry %" B_PRId32
				" contains a null char\n", i);
			return false;
		}

		// compare the name with the previous name
		if (i > 0) {
			int cmp = compare_names(previousName, previousNameLength, name,
				nameLength);
			if (cmp == 0) {
				ERROR("Invalid dir entry block: entries %" B_PRId32 "/%"
					B_PRId32 " have the same name: \"%.*s\"\n", i - 1, i,
					(int)nameLength, name);
				return false;
			} else if (cmp > 0) {
				ERROR("Invalid dir entry block: entries %" B_PRId32 "/%"
					B_PRId32 " out of order: \"%.*s\" > \"%.*s\"\n", i - 1, i,
					(int)previousNameLength, previousName, (int)nameLength,
					name);
				return false;
			}
		}

		// check the block index
		if (blockIndices[-i] < kCheckSumFSSuperBlockOffset / B_PAGE_SIZE) {
			ERROR("Invalid dir entry block: entry %" B_PRId32
				" has invalid block index: %" B_PRIu64, i, blockIndices[-i]);
			return false;
		}

		previousName = name;
		previousNameLength = nameLength;
		previousEnd = nameEnd;
	}

	return true;
}


// #pragma mark - DirEntryTree


DirEntryTree::DirEntryTree(Directory* directory)
	:
	fDirectory(directory)
{
}


status_t
DirEntryTree::LookupEntry(const char* name, uint64& _blockIndex)
{
	FUNCTION("name: \"%s\"\n", name);

	status_t error = _InitReadOnly();
	if (error != B_OK)
		RETURN_ERROR(error);

	size_t nameLength = strlen(name);
	if (nameLength > kCheckSumFSNameLength)
		RETURN_ERROR(B_ENTRY_NOT_FOUND);

	uint32 depth = _Depth();

	DirEntryBlock entryBlock(fRootEntryBlock, fRootEntryBlockSize);
ASSERT(entryBlock.Check());

	Block block;

	for (uint32 level = 0; level <= depth; level++) {
		if (entryBlock.EntryCount() == 0)
			RETURN_ERROR(level == 0 ? B_ENTRY_NOT_FOUND : B_BAD_DATA);

		bool exactMatch;
		int32 index = entryBlock.FindInsertionIndex(name, nameLength,
			exactMatch);

		// If we haven't found an exact match, the index points to the first
		// entry that is greater or after the last entry.
		if (!exactMatch) {
			if (index == 0) {
				// The first entry is already greater, so the branch doesn't
				// contain the entry we're looking for.
				RETURN_ERROR(B_ENTRY_NOT_FOUND);
			}

			index--;
		}

		PRINT("  level %" B_PRId32 " -> index: %" B_PRId32 " %sexact\n", level,
			index, exactMatch ? "" : " not ");

		uint64 blockIndex = entryBlock.BlockIndexAt(index);

		if (level == depth) {
			// final level -- here we should have an exact match
			if (!exactMatch)
				RETURN_ERROR(B_ENTRY_NOT_FOUND);

			_blockIndex = blockIndex;
			return B_OK;
		}

		// not the final level -- load the block and descend to the next
		// level
		if (!block.GetReadable(fDirectory->GetVolume(), blockIndex))
			RETURN_ERROR(B_ERROR);

		entryBlock.SetTo((checksumfs_dir_entry_block*)block.Data(),
			B_PAGE_SIZE);
ASSERT(entryBlock.Check());
	}

	// cannot get here, but keep the compiler happy
	RETURN_ERROR(B_ENTRY_NOT_FOUND);
}


status_t
DirEntryTree::LookupNextEntry(const char* name, char* foundName,
	size_t& _foundNameLength, uint64& _blockIndex)
{
	FUNCTION("name: \"%s\"\n", name);

	status_t error = _InitReadOnly();
	if (error != B_OK)
		RETURN_ERROR(error);

	size_t nameLength = strlen(name);
	if (nameLength > kCheckSumFSNameLength)
		RETURN_ERROR(B_ENTRY_NOT_FOUND);

	int32 depth = _Depth();

	LevelInfo* infos = new(std::nothrow) LevelInfo[
		kCheckSumFSMaxDirEntryTreeDepth + 1];
	if (infos == NULL)
		RETURN_ERROR(B_NO_MEMORY);
	ArrayDeleter<LevelInfo> infosDeleter(infos);

	infos[0].entryBlock.SetTo(fRootEntryBlock, fRootEntryBlockSize);
ASSERT(infos[0].entryBlock.Check());

	// descend the tree
	for (int32 level = 0; level <= depth; level++) {
		LevelInfo& info = infos[level];

		if (info.entryBlock.EntryCount() == 0) {
			if (level == 0) {
				// directory is empty
				return B_ENTRY_NOT_FOUND;
			}

			RETURN_ERROR(B_BAD_DATA);
		}

		info.index = info.entryBlock.FindInsertionIndex(name, nameLength,
			info.exactMatch);

		PRINT("  level %" B_PRId32 " -> index: %" B_PRId32 " %sexact\n", level,
			info.index, info.exactMatch ? "" : " not ");

		if (level == depth)
			break;

		// If we haven't found an exact match, the index points to the first
		// entry that is greater or after the last entry.
		if (!info.exactMatch && info.index > 0)
			info.index--;

		uint64 nextBlockIndex = info.entryBlock.BlockIndexAt(info.index);

		// not the final level -- load the block and descend to the next
		// level
		LevelInfo& nextInfo = infos[level + 1];
		if (!nextInfo.block.GetReadable(fDirectory->GetVolume(),
				nextBlockIndex)) {
			RETURN_ERROR(B_ERROR);
		}

		nextInfo.entryBlock.SetTo(
			(checksumfs_dir_entry_block*)nextInfo.block.Data(),
			B_PAGE_SIZE);
ASSERT(nextInfo.entryBlock.Check());
	}

	if (infos[depth].exactMatch)
		infos[depth].index++;

	if (infos[depth].index >= infos[depth].entryBlock.EntryCount()) {
		// We're at the end of the last block -- we need to track back to find a
		// greater branch.
		PRINT("  searching for greater branch\n");

		int32 level;
		for (level = depth - 1; level >= 0; level--) {
			LevelInfo& info = infos[level];
			if (++info.index < info.entryBlock.EntryCount()) {
				PRINT("  found greater branch: level: %" B_PRId32 " -> index: %"
					B_PRId32 "\n", level, info.index);
				break;
			}
		}

		if (level < 0)
			return B_ENTRY_NOT_FOUND;

		// We've found a greater branch -- get the first entry in that branch.
		for (level++; level <= depth; level++) {
			LevelInfo& previousInfo = infos[level - 1];
			LevelInfo& info = infos[level];

			uint64 nextBlockIndex = previousInfo.entryBlock.BlockIndexAt(
				previousInfo.index);

			// load the block
			if (!info.block.GetReadable(fDirectory->GetVolume(),
					nextBlockIndex)) {
				RETURN_ERROR(B_ERROR);
			}

			info.entryBlock.SetTo(
				(checksumfs_dir_entry_block*)info.block.Data(), B_PAGE_SIZE);
ASSERT(info.entryBlock.Check());

			info.index = 0;
			if (info.entryBlock.EntryCount() == 0)
				RETURN_ERROR(B_BAD_DATA);
		}
	}

	// get and check the name
	LevelInfo& info = infos[depth];

	name = info.entryBlock.NameAt(info.index, nameLength);
	if (nameLength > kCheckSumFSNameLength
		|| strnlen(name, nameLength) != nameLength) {
		RETURN_ERROR(B_BAD_DATA);
	}

	// set the return values
	memcpy(foundName, name, nameLength);
	foundName[nameLength] = '\0';
	_foundNameLength = nameLength;
	_blockIndex = info.entryBlock.BlockIndexAt(info.index);

	PRINT("  found entry: \"%s\" -> %" B_PRIu64 "\n", foundName, _blockIndex);

	return B_OK;
}


status_t
DirEntryTree::InsertEntry(const char* name, uint64 blockIndex,
	Transaction& transaction)
{
	FUNCTION("name: \"%s\", blockIndex: %" B_PRIu64 "\n", name, blockIndex);

	status_t error = _InitWritable(transaction);
	if (error != B_OK)
		RETURN_ERROR(error);

	size_t nameLength = strlen(name);
	if (nameLength == 0)
		RETURN_ERROR(B_BAD_VALUE);
	if (nameLength > kCheckSumFSNameLength)
		RETURN_ERROR(B_NAME_TOO_LONG);

	int32 depth = _Depth();

	LevelInfo* infos = new(std::nothrow) LevelInfo[
		kCheckSumFSMaxDirEntryTreeDepth + 1];
	if (infos == NULL)
		RETURN_ERROR(B_NO_MEMORY);
	ArrayDeleter<LevelInfo> infosDeleter(infos);

	infos[0].entryBlock.SetTo(fRootEntryBlock, fRootEntryBlockSize);

	for (int32 level = 0; level <= depth; level++) {
		LevelInfo& info = infos[level];

		if (info.entryBlock.EntryCount() == 0) {
			if (level == 0) {
				PRINT("  directory is empty\n");
				// directory is empty
				info.index = 0;
				break;
			}

			RETURN_ERROR(B_BAD_DATA);
		}

		info.index = info.entryBlock.FindInsertionIndex(name, nameLength,
			info.exactMatch);

		PRINT("  level %" B_PRId32 ", block %" B_PRIu64 " -> index: %" B_PRId32
			" %sexact\n", level,
			level == 0 ? fDirectory->BlockIndex() : info.block.Index(),
			info.index, info.exactMatch ? "" : " not ");

		// Finding an exact match -- even in the non-final level -- means
		// that there's an entry with that name.
		if (info.exactMatch)
			RETURN_ERROR(B_FILE_EXISTS);

		if (level == depth) {
			// final level -- here we need to insert the entry
			break;
		}

		// Since we haven't found an exact match, the index points to the
		// first entry that is greater or after the last entry.
		info.index--;

		uint64 nextBlockIndex = info.entryBlock.BlockIndexAt(info.index);

		// not the final level -- load the block and descend to the next
		// level
		LevelInfo& nextInfo = infos[level + 1];
		if (!nextInfo.block.GetReadable(fDirectory->GetVolume(),
				nextBlockIndex)) {
			RETURN_ERROR(B_ERROR);
		}

		nextInfo.entryBlock.SetTo(
			(checksumfs_dir_entry_block*)nextInfo.block.Data(),
			B_PAGE_SIZE);
ASSERT(nextInfo.entryBlock.Check());
	}

	// We've found the insertion point. Insert the key and iterate backwards
	// to perform the potentially necessary updates. Insertion at index 0 of
	// the block changes the block's key, requiring an update in the parent
	// block. Insertion or key update can cause the block to be split (if
	// there's not enough space left in it), requiring an insertion in the
	// parent block. So we start with a pending insertion in the leaf block
	// and work our way upwards, performing key updates and insertions as
	// necessary.

	return _UpdateOrInsertKey(infos, depth, name, nameLength, blockIndex, true,
		transaction);
}


status_t
DirEntryTree::RemoveEntry(const char* name, Transaction& transaction)
{
	FUNCTION("name: \"%s\"\n", name);

	status_t error = _InitWritable(transaction);
	if (error != B_OK)
		RETURN_ERROR(error);

	size_t nameLength = strlen(name);
	if (nameLength == 0)
		RETURN_ERROR(B_BAD_VALUE);
	if (nameLength > kCheckSumFSNameLength)
		RETURN_ERROR(B_ENTRY_NOT_FOUND);

	int32 depth = _Depth();

	LevelInfo* infos = new(std::nothrow) LevelInfo[
		kCheckSumFSMaxDirEntryTreeDepth + 1];
	if (infos == NULL)
		RETURN_ERROR(B_NO_MEMORY);
	ArrayDeleter<LevelInfo> infosDeleter(infos);

	infos[0].entryBlock.SetTo(fRootEntryBlock, fRootEntryBlockSize);

	for (int32 level = 0; level <= depth; level++) {
		LevelInfo& info = infos[level];

		if (info.entryBlock.EntryCount() == 0) {
			if (level == 0) {
				// directory is empty
				PRINT("  directory is empty\n");
				RETURN_ERROR(B_ENTRY_NOT_FOUND);
			}

			RETURN_ERROR(B_BAD_DATA);
		}

		info.index = info.entryBlock.FindInsertionIndex(name, nameLength,
			info.exactMatch);

		PRINT("  level %" B_PRId32 ", block %" B_PRIu64 " -> index: %" B_PRId32
			" %sexact\n", level,
			level == 0 ? fDirectory->BlockIndex() : info.block.Index(),
			info.index, info.exactMatch ? "" : " not ");

		if (level == depth) {
			// final level -- here the entry should be found
			if (!info.exactMatch)
				RETURN_ERROR(B_ENTRY_NOT_FOUND);
			break;
		}

		// If we haven't found an exact match, the index points to the first
		// entry that is greater or after the last entry.
		if (!info.exactMatch) {
			if (info.index == 0) {
				// The first entry is already greater, so the branch doesn't
				// contain the entry we're looking for.
				RETURN_ERROR(B_ENTRY_NOT_FOUND);
			}

			info.index--;
		}

		uint64 nextBlockIndex = info.entryBlock.BlockIndexAt(info.index);

		// not the final level -- load the block and descend to the next
		// level
		LevelInfo& nextInfo = infos[level + 1];
		if (!nextInfo.block.GetReadable(fDirectory->GetVolume(),
				nextBlockIndex)) {
			RETURN_ERROR(B_ERROR);
		}

		nextInfo.entryBlock.SetTo(
			(checksumfs_dir_entry_block*)nextInfo.block.Data(),
			B_PAGE_SIZE);
ASSERT(nextInfo.entryBlock.Check());
	}

	// We've found the entry. Insert the key and iterate backwards to perform
	// the potentially necessary updates. Removal at index 0 of the block
	// changes the block's key, requiring an update in the parent block.
	// Removal of the last entry will require removal of the block from its
	// parent. Key update can cause the block to be split (if there's not
	// enough space left in it), requiring an insertion in the parent block.
	// We start with a pending removal in the leaf block and work our way
	// upwards as long as the blocks become empty. As soon as a key update is
	// required, we delegate the remaining to the update/insert backwards loop.

	for (int32 level = depth; level >= 0; level--) {
		LevelInfo& info = infos[level];

		// make the block writable
		if (level > 0) {
			error = info.block.MakeWritable(transaction);
			if (error != B_OK)
				RETURN_ERROR(error);
		}

		PRINT("  level: %" B_PRId32 ", index: %" B_PRId32 ": removing key "
			"\"%.*s\" (%" B_PRIuSIZE ")\n", level, info.index, (int)nameLength,
			name, nameLength);

		if (info.entryBlock.EntryCount() == 1) {
			// That's the last key in the block. Unless that's the root level,
			// we remove the block completely.
			PRINT("  -> block is empty\n");
			if (level == 0) {
				info.entryBlock.RemoveEntry(info.index);
				return B_OK;
			}

			error = fDirectory->GetVolume()->GetBlockAllocator()->Free(
				info.block.Index(), 1, transaction);
			if (error != B_OK)
				RETURN_ERROR(error);
			fDirectory->SetSize(fDirectory->Size() - B_PAGE_SIZE);

			// remove the key (the same one) from the parent block
			continue;
		}

		// There are more entries, so just remove the entry in question. If it
		// is not the first one, we're done, otherwise we have to update the
		// block's key in the parent block.
		info.entryBlock.RemoveEntry(info.index);

		if (info.index > 0 || level == 0)
			return B_OK;

		name = info.entryBlock.NameAt(0, nameLength);
		return _UpdateOrInsertKey(infos, level - 1, name, nameLength, 0, false,
			transaction);
	}

	return B_OK;
}


status_t
DirEntryTree::FreeTree(Transaction& transaction)
{
	status_t error = _InitReadOnly();
	if (error != B_OK)
		RETURN_ERROR(error);

	int32 depth = _Depth();
	if (depth == 0)
		return B_OK;

	LevelInfo* infos = new(std::nothrow) LevelInfo[
		kCheckSumFSMaxDirEntryTreeDepth + 1];
	if (infos == NULL)
		RETURN_ERROR(B_NO_MEMORY);
	ArrayDeleter<LevelInfo> infosDeleter(infos);

	infos[0].entryBlock.SetTo(fRootEntryBlock, fRootEntryBlockSize);
	infos[0].index = 0;

	// Iterate through the tree in post order. We don't touch the content of
	// any block, we only free the blocks.
	int32 level = 0;
	while (true) {
		LevelInfo& info = infos[level];

		if (level == depth || info.index >= info.entryBlock.EntryCount()) {
			// we're through with the block
			if (level == 0)
				break;

			// free it
			error = fDirectory->GetVolume()->GetBlockAllocator()->Free(
				info.block.Index(), 1, transaction);

			// continue with the next sibling branch
			infos[--level].index++;
		}

		// descend to next level
		uint64 nextBlockIndex = info.entryBlock.BlockIndexAt(info.index);

		LevelInfo& nextInfo = infos[++level];
		if (!nextInfo.block.GetReadable(fDirectory->GetVolume(),
				nextBlockIndex)) {
			RETURN_ERROR(B_ERROR);
		}

		nextInfo.entryBlock.SetTo(
			(checksumfs_dir_entry_block*)nextInfo.block.Data(),
			B_PAGE_SIZE);
	}

	return B_OK;
}


bool
DirEntryTree::IsEmpty() const
{
	DirEntryBlock entryBlock(fRootEntryBlock, fRootEntryBlockSize);
	return entryBlock.EntryCount() == 0;
}


bool
DirEntryTree::Check()
{
	if (_InitReadOnly() != B_OK) {
		ERROR("DirEntryTree::Check(): Init failed!\n");
		return false;
	}

	DirEntryBlock entryBlock(fRootEntryBlock, fRootEntryBlockSize);
	return _Check(0, fDirectory->BlockIndex(), NULL, 0, entryBlock);
}


status_t
DirEntryTree::_InitReadOnly()
{
	if (!fRootBlock.GetReadable(fDirectory->GetVolume(),
			fDirectory->BlockIndex())) {
		RETURN_ERROR(B_ERROR);
	}

	return _InitCommon();
}


status_t
DirEntryTree::_InitWritable(Transaction& transaction)
{
	if (!fRootBlock.GetWritable(fDirectory->GetVolume(),
			fDirectory->BlockIndex(), transaction)) {
		RETURN_ERROR(B_ERROR);
	}

	return _InitCommon();
}


status_t
DirEntryTree::_InitCommon()
{
	fTree = (checksumfs_dir_entry_tree*)
		((uint8*)fRootBlock.Data() + sizeof(checksumfs_node));

	fRootEntryBlock = (checksumfs_dir_entry_block*)(fTree + 1);
	fRootEntryBlockSize = B_PAGE_SIZE
		- ((addr_t)fRootEntryBlock - (addr_t)fRootBlock.Data());

	if (_Depth() > kCheckSumFSMaxDirEntryTreeDepth)
		RETURN_ERROR(B_BAD_DATA);

	return B_OK;
}


status_t
DirEntryTree::_UpdateOrInsertKey(LevelInfo* infos, int32 level,
	const char* name, size_t nameLength, uint64 blockIndex, bool insertKey,
	Transaction& transaction)
{
	FUNCTION("level: %" B_PRId32 ": %s name: \"%.*s\" (%" B_PRIuSIZE "), "
		"blockIndex: %" B_PRIu64 "\n", level, insertKey ? "insert" : "update",
		(int)nameLength, name, nameLength, blockIndex);

	// Some temporary blocks: newBlock is used when a block is split. The
	// other three are used when a key update respectively insertion in the
	// parent block becomes necessary. We only need them, since the name
	// we update/insert is potentially from a block and instead of cloning
	// the name, we simple postpone putting the block until we don't need
	// the name anymore.
	Block newBlock;
	Block tempBlockUpdate;
	Block tempBlockUpdateInsert;
	Block tempBlockInsert;

	int32 depth = _Depth();
	status_t error;

	bool updateNextKey = !insertKey;
	bool insertNextKey = insertKey;
	const char* nameToUpdate = name;
	size_t nameToUpdateLength = nameLength;
	const char* nextNameToInsert = name;
	size_t nextNameToInsertLength = nameLength;
	uint64 nextBlockIndexToInsert = blockIndex;

	for (; level >= 0; level--) {
		LevelInfo& info = infos[level];

		bool updateThisKey = updateNextKey;
		bool insertThisKey = insertNextKey;

		if (!updateThisKey && !insertThisKey)
			return B_OK;

		updateNextKey = false;
		insertNextKey = false;

		blockIndex = nextBlockIndexToInsert;
		name = nextNameToInsert;
		nameLength = nextNameToInsertLength;

		// make the block writable
		if (level > 0) {
			error = info.block.MakeWritable(transaction);
			if (error != B_OK)
				RETURN_ERROR(error);
		}

		if (updateThisKey) {
			PRINT("  level: %" B_PRId32 ", index: %" B_PRId32 ": updating key "
				"to \"%.*s\" (%" B_PRIuSIZE ")\n", level, info.index,
				(int)nameToUpdateLength, nameToUpdate, nameToUpdateLength);

			size_t oldNameLength;
			info.entryBlock.NameAt(info.index, oldNameLength);
			size_t spaceNeeded = oldNameLength < nameToUpdateLength
				? nameToUpdateLength - oldNameLength : 0;

			if (spaceNeeded <= info.entryBlock.FreeSpace()) {
				info.entryBlock.ReplaceEntryName(info.index, nameToUpdate,
					nameToUpdateLength);
				if (info.index == 0) {
					// we updated at index 0, so we need to update this
					// block's key in the parent block
					updateNextKey = true;
					nameToUpdate = info.entryBlock.NameAt(0,
						nameToUpdateLength);

					// make sure the new block is kept until we no longer
					// use the name in the next iteration
					tempBlockUpdate.TransferFrom(info.block);
				}
			} else if (level == 0) {
				// We need to split the root block -- clone it first.
				error = _InsertEntryIncrementDepth(infos, transaction);
				if (error != B_OK)
					RETURN_ERROR(error);

				level = 2;
					// _InsertEntryIncrementDepth() moved the root block
					// content to level 1, where we want to continue.
				updateNextKey = true;
				insertNextKey = insertThisKey;
				continue;
			} else {
				// We need to split this non-root block.
				int32 splitIndex;
				error = _InsertEntrySplitBlock(level, info, spaceNeeded,
					transaction, newBlock, splitIndex);
				if (error != B_OK)
					RETURN_ERROR(error);

				nextBlockIndexToInsert = newBlock.Index();

				DirEntryBlock newEntryBlock(
					(checksumfs_dir_entry_block*)newBlock.Data(),
					B_PAGE_SIZE);
ASSERT(newEntryBlock.Check());

				if (info.index < splitIndex) {
					ASSERT(info.entryBlock.FreeSpace() >= spaceNeeded);

					info.entryBlock.ReplaceEntryName(info.index,
						nameToUpdate, nameToUpdateLength);
					if (info.index == 0) {
						// we updated at index 0, so we need to update this
						// block's key in the parent block
						updateNextKey = true;
						nameToUpdate = info.entryBlock.NameAt(0,
							nameToUpdateLength);

						// make sure the new block is kept until we no
						// longer use the name in the next iteration
						tempBlockUpdate.TransferFrom(info.block);
					}
				} else {
					ASSERT(newEntryBlock.FreeSpace() >= spaceNeeded);

					// we need to transfer the block to the info, in case we
					// also need to insert a key below
					info.block.TransferFrom(newBlock);
					info.entryBlock.SetTo(
						(checksumfs_dir_entry_block*)info.block.Data(),
						B_PAGE_SIZE);
ASSERT(info.entryBlock.Check());

					info.index -= splitIndex;

					info.entryBlock.ReplaceEntryName(info.index, nameToUpdate,
						nameToUpdateLength);
				}

				// the newly created block needs to be inserted in the
				// parent
				insertNextKey = true;
				nextNameToInsert = newEntryBlock.NameAt(0,
					nextNameToInsertLength);

				// make sure the new block is kept until we no longer use
				// the name in the next iteration (might already have been
				// transferred to entry.block)
				tempBlockUpdateInsert.TransferFrom(newBlock);
			}
		}

		if (insertThisKey) {
			// insert after the block we descended
			if (level < depth)
				info.index++;

			PRINT("  level: %" B_PRId32 ", index: %" B_PRId32 ": inserting key "
				"\"%.*s\" (%" B_PRIuSIZE "), blockIndex: %" B_PRIu64 "\n",
				level, info.index, (int)nameLength, name, nameLength,
				blockIndex);

			if (info.entryBlock.FreeSpace() >= nameLength + 10) {
				info.entryBlock.InsertEntry(info.index, name,
					nameLength, blockIndex);
				if (info.index == 0) {
					// we inserted at index 0, so we need to update this
					// block's key in the parent block
					updateNextKey = true;
					nameToUpdate = info.entryBlock.NameAt(0,
						nameToUpdateLength);

					// make sure the new block is kept until we no longer
					// use the name in the next iteration
					tempBlockUpdate.TransferFrom(info.block);
				}
				continue;
			}

			// Not enough space left in the block -- we need to split it.
			ASSERT(!insertNextKey);

			// for level == 0 we need to clone the block first
			if (level == 0) {
				error = _InsertEntryIncrementDepth(infos, transaction);
				if (error != B_OK)
					RETURN_ERROR(error);

				level = 2;
					// _InsertEntryIncrementDepth() moved the root block
					// content to level 1, where we want to continue.
				updateNextKey = false;
				insertNextKey = true;
				continue;
			}

			int32 splitIndex;
			error = _InsertEntrySplitBlock(level, info, nameLength + 10,
				transaction, newBlock, splitIndex);
			if (error != B_OK)
				RETURN_ERROR(error);

			DirEntryBlock newEntryBlock(
				(checksumfs_dir_entry_block*)newBlock.Data(),
				B_PAGE_SIZE);
ASSERT(newEntryBlock.Check());

			if (info.index < splitIndex) {
				ASSERT(info.entryBlock.FreeSpace() >= nameLength + 10);

				info.entryBlock.InsertEntry(info.index, name,
					nameLength, blockIndex);
				if (info.index == 0) {
					// we inserted at index 0, so we need to update this
					// block's key in the parent block
					updateNextKey = true;
					nameToUpdate = info.entryBlock.NameAt(0,
						nameToUpdateLength);

					// make sure the new block is kept until we no longer
					// use the name in the next iteration
					tempBlockUpdate.TransferFrom(info.block);
				}
			} else {
				ASSERT(newEntryBlock.FreeSpace() >= nameLength + 10);

				info.index -= splitIndex;

				newEntryBlock.InsertEntry(info.index, name, nameLength,
					blockIndex);
			}

			// the newly created block needs to be inserted in the parent
			insertNextKey = true;
			nextNameToInsert = newEntryBlock.NameAt(0, nextNameToInsertLength);
			nextBlockIndexToInsert = newBlock.Index();

			// make sure the new block is kept until we no longer use
			// the name in the next iteration
			tempBlockInsert.TransferFrom(newBlock);
		}
	}

	return B_OK;
}


status_t
DirEntryTree::_InsertEntryIncrementDepth(LevelInfo* infos,
	Transaction& transaction)
{
	FUNCTION("depth: %u -> %u\n", _Depth(), _Depth() + 1);

	if (_Depth() >= kCheckSumFSMaxDirEntryTreeDepth)
		RETURN_ERROR(B_DEVICE_FULL);

	// allocate a new block
	AllocatedBlock allocatedBlock(
		fDirectory->GetVolume()->GetBlockAllocator(), transaction);

	status_t error = allocatedBlock.Allocate(fDirectory->BlockIndex());
	if (error != B_OK)
		RETURN_ERROR(error);
	fDirectory->SetSize(fDirectory->Size() + B_PAGE_SIZE);

	LevelInfo& newInfo = infos[1];
	if (!newInfo.block.GetZero(fDirectory->GetVolume(),
			allocatedBlock.Index(), transaction)) {
		RETURN_ERROR(B_ERROR);
	}

	allocatedBlock.Detach();

	newInfo.entryBlock.SetTo(
		(checksumfs_dir_entry_block*)newInfo.block.Data(), B_PAGE_SIZE);
ASSERT(newInfo.entryBlock.Check());

	// move the old root block contents to the new block
	LevelInfo& rootInfo = infos[0];
	rootInfo.entryBlock.SplitBlock(0, newInfo.entryBlock);

	// add an entry for the new block to the root block
	size_t nameLength;
	const char* name = newInfo.entryBlock.NameAt(0, nameLength);
	rootInfo.entryBlock.InsertEntry(0, name, nameLength,
		newInfo.block.Index());

	PRINT("  -> new block: %" B_PRIu64 "\n", newInfo.block.Index());

	newInfo.index = rootInfo.index;
	rootInfo.index = 0;
	fTree->depth++;

	return B_OK;
}


status_t
DirEntryTree::_InsertEntrySplitBlock(int32 level, LevelInfo& info,
	size_t needed, Transaction& transaction, Block& newBlock,
	int32& _splitIndex)
{
	int32 splitIndex = info.entryBlock.FindSplitIndex(info.index,
		needed);

	FUNCTION("level: %" B_PRId32 ", size needed: %" B_PRIuSIZE ", split index: "
		"%" B_PRId32 "/%" B_PRId32 "\n", level, needed, splitIndex,
		info.entryBlock.EntryCount());

	// allocate a new block
	AllocatedBlock allocatedBlock(
		fDirectory->GetVolume()->GetBlockAllocator(), transaction);

	status_t error = allocatedBlock.Allocate(fDirectory->BlockIndex());
	if (error != B_OK)
		RETURN_ERROR(error);
	fDirectory->SetSize(fDirectory->Size() + B_PAGE_SIZE);

	if (!newBlock.GetZero(fDirectory->GetVolume(), allocatedBlock.Index(),
			transaction)) {
		RETURN_ERROR(B_ERROR);
	}

	allocatedBlock.Detach();

	// split the old block
	DirEntryBlock newEntryBlock(
		(checksumfs_dir_entry_block*)newBlock.Data(), B_PAGE_SIZE);
ASSERT(newEntryBlock.Check());
	info.entryBlock.SplitBlock(splitIndex, newEntryBlock);

	PRINT("  -> new block: %" B_PRIu64 "\n", newBlock.Index());

	_splitIndex = splitIndex;
	return B_OK;
}


bool
DirEntryTree::_Check(int32 level, uint64 blockIndex, const char* key,
	size_t keyLength, DirEntryBlock& entryBlock)
{
	// check block for validity
	if (!entryBlock.Check()) {
		ERROR("DirEntryTree::Check(): level %" B_PRIu32 ": block %"
			B_PRIu64 " not valid!\n", level, blockIndex);
		return false;
	}

	// The root block is allowed to be empty. For all other blocks that is an
	// error.
	uint32 entryCount = entryBlock.EntryCount();
	if (entryCount == 0) {
		if (level == 0)
			return true;

		ERROR("DirEntryTree::Check(): level %" B_PRIu32 ": block %"
			B_PRIu64 " empty!\n", level, blockIndex);
		return false;
	}

	// Verify that the block's first entry matches the key with which the
	// parent block refers to it.
	if (level > 0) {
		size_t nameLength;
		const char* name = entryBlock.NameAt(0, nameLength);
		if (nameLength != keyLength || strncmp(name, key, keyLength) != 0) {
			ERROR("DirEntryTree::Check(): level %" B_PRIu32 ": block %"
				B_PRIu64 " key mismatch: is \"%.*s\", should be \"%.*s\"\n",
				level, blockIndex, (int)keyLength, key, (int)nameLength, name);
			return false;
		}
	}

	if (level == _Depth())
		return true;

	// not the final level -- recurse
	for (uint32 i = 0; i < entryCount; i++) {
		size_t nameLength;
		const char* name = entryBlock.NameAt(i, nameLength);
		uint64 childBlockIndex = entryBlock.BlockIndexAt(i);

		Block childBlock;
		if (!childBlock.GetReadable(fDirectory->GetVolume(), childBlockIndex)) {
			ERROR("DirEntryTree::Check(): level %" B_PRIu32 ": block %"
				B_PRIu64 " failed to get child block %" B_PRIu64 " (entry %"
				B_PRIu32 ")\n", level, blockIndex, childBlockIndex, i);
		}

		DirEntryBlock childEntryBlock(
			(checksumfs_dir_entry_block*)childBlock.Data(), B_PAGE_SIZE);

		if (!_Check(level + 1, childBlockIndex, name, nameLength,
				childEntryBlock)) {
			return false;
		}
	}

	return true;
}


// #pragma mark - Directory


Directory::Directory(Volume* volume, uint64 blockIndex,
	const checksumfs_node& nodeData)
	:
	Node(volume, blockIndex, nodeData)
{
}


Directory::Directory(Volume* volume, mode_t mode)
	:
	Node(volume, mode)
{
}


Directory::~Directory()
{
}


void
Directory::DeletingNode()
{
	Node::DeletingNode();

	// iterate through the directory and remove references to all entries' nodes
	char* name = (char*)malloc(kCheckSumFSNameLength + 1);
	if (name != NULL) {
		name[0] = '\0';

		DirEntryTree entryTree(this);
		size_t nameLength;
		uint64 blockIndex;
		while (entryTree.LookupNextEntry(name, name, nameLength,
				blockIndex) == B_OK) {
			Node* node;
			if (GetVolume()->GetNode(blockIndex, node) == B_OK) {
				Transaction transaction(GetVolume());
				if (transaction.StartAndAddNode(node) == B_OK) {
					node->SetHardLinks(node->HardLinks() - 1);
					if (node->HardLinks() == 0)
						GetVolume()->RemoveNode(node);

					if (transaction.Commit() != B_OK) {
						ERROR("Failed to commit transaction for dereferencing "
							"entry node of deleted directory at %" B_PRIu64
							"\n", BlockIndex());
					}
				} else {
					ERROR("Failed to start transaction for dereferencing "
						"entry node of deleted directory at %" B_PRIu64 "\n",
						BlockIndex());
				}

				GetVolume()->PutNode(node);
			} else {
				ERROR("Failed to get node %" B_PRIu64 " referenced by deleted "
					"directory at %" B_PRIu64 "\n", blockIndex, BlockIndex());
			}
		}

		free(name);
	}

	// free the directory entry block tree
	Transaction transaction(GetVolume());
	if (transaction.Start() != B_OK) {
		ERROR("Failed to start transaction for freeing entry tree of deleted "
			"directory at %" B_PRIu64 "\n", BlockIndex());
		return;
	}

	DirEntryTree entryTree(this);
	if (entryTree.FreeTree(transaction) != B_OK) {
		ERROR("Failed to freeing entry tree of deleted directory at %" B_PRIu64
			"\n", BlockIndex());
		return;
	}

	if (transaction.Commit() != B_OK) {
		ERROR("Failed to commit transaction for freeing entry tree of deleted "
			"directory at %" B_PRIu64 "\n", BlockIndex());
	}
}


status_t
Directory::LookupEntry(const char* name, uint64& _blockIndex)
{
	DirEntryTree entryTree(this);
	return entryTree.LookupEntry(name, _blockIndex);
}


status_t
Directory::LookupNextEntry(const char* name, char* foundName,
	size_t& _foundNameLength, uint64& _blockIndex)
{
	DirEntryTree entryTree(this);
	return entryTree.LookupNextEntry(name, foundName, _foundNameLength,
		_blockIndex);
}


status_t
Directory::InsertEntry(const char* name, uint64 blockIndex,
	Transaction& transaction)
{
	DirEntryTree entryTree(this);

	status_t error = entryTree.InsertEntry(name, blockIndex, transaction);
	if (error == B_OK)
		ASSERT(entryTree.Check());
	return error;
}


status_t
Directory::RemoveEntry(const char* name, Transaction& transaction,
	bool* _lastEntryRemoved)
{
	DirEntryTree entryTree(this);

	status_t error = entryTree.RemoveEntry(name, transaction);
	if (error != B_OK)
		return error;

	ASSERT(entryTree.Check());

	if (_lastEntryRemoved != NULL)
		*_lastEntryRemoved = entryTree.IsEmpty();

	return B_OK;
}