file_systems/btrfs/BTree.cpp

/*
 * Copyright 2017, Chế Vũ Gia Hy, cvghy116@gmail.com.
 * Copyright 2011, Jérôme Duval, korli@users.berlios.de.
 * Copyright 2001-2010, Axel Dörfler, axeld@pinc-software.de.
 * This file may be used under the terms of the MIT License.
 */


//! BTree implementation


#include "BTree.h"
#include "Journal.h"

#include <algorithm>


//#define TRACE_BTRFS
#ifdef TRACE_BTRFS
#	define TRACE(x...) dprintf("\33[34mbtrfs:\33[0m " x)
#else
#	define TRACE(x...) ;
#endif
#	define ERROR(x...) dprintf("\33[34mbtrfs:\33[0m " x)


BTree::Node::Node(Volume* volume)
	:
	fNode(NULL),
	fVolume(volume),
	fBlockNumber(0),
	fWritable(false)
{
}


BTree::Node::Node(Volume* volume, off_t block)
	:
	fNode(NULL),
	fVolume(volume),
	fBlockNumber(0),
	fWritable(false)
{
	SetTo(block);
}


BTree::Node::~Node()
{
	Unset();
}


void
BTree::Node::Keep()
{
	fNode = NULL;
}

void
BTree::Node::Unset()
{
	if (fNode != NULL) {
		block_cache_put(fVolume->BlockCache(), fBlockNumber);
		fNode = NULL;
	}
}


void
BTree::Node::SetTo(off_t block)
{
	Unset();
	fBlockNumber = block;
	fNode = (btrfs_stream*)block_cache_get(fVolume->BlockCache(), block);
}


void
BTree::Node::SetToWritable(off_t block, int32 transactionId, bool empty)
{
	Unset();
	fBlockNumber = block;
	fWritable = true;
	if (empty) {
		fNode = (btrfs_stream*)block_cache_get_empty(fVolume->BlockCache(),
			block, transactionId);
	} else {
		fNode = (btrfs_stream*)block_cache_get_writable(fVolume->BlockCache(),
			block, transactionId);
	}
}


status_t
BTree::Node::SearchSlot(const btrfs_key& key, int* slot, btree_traversing type)
	const
{
	//binary search for item slot in a node
	int entrySize = sizeof(btrfs_entry);
	if (Level() != 0) {
		// internal node
		entrySize = sizeof(btrfs_index);
	}

	int high = ItemCount();
	int low = 0, mid = 0, comp = 0;
	uint8* base = (uint8*)fNode + sizeof(btrfs_header);
	const btrfs_key* other;
	while (low < high) {
		mid = (low + high) / 2;
		other = (const btrfs_key*)(base + mid * entrySize);
		comp = key.Compare(*other);
		if (comp < 0)
			high = mid;
		else if (comp > 0)
			low = mid + 1;
		else {
			*slot = mid;
			return B_OK; 		//if key is in node
		}
	}

	// |--item1--|--item2--|--item3--|--etc--|
	//     m-1        m        m+1
	//           k          		: comp < 0
	//                     k		: comp > 0
	if (type == BTREE_BACKWARD) {
		*slot = mid - 1;
		if (comp > 0)
			*slot = mid;
	} else if (type == BTREE_FORWARD) {
		*slot = mid;
		if (comp > 0)
			*slot = mid + 1;
	}

	if (type == BTREE_EXACT || *slot < 0)
		return B_ENTRY_NOT_FOUND;

	TRACE("SearchSlot() found slot %" B_PRId32 " comp %" B_PRId32 "\n",
		*slot, comp);
	return B_OK;
}


/*
 * calculate used space except the header.
 * type is only for leaf node
 * type 1: only item space
 * type 2: only item data space
 * type 3: both type 1 and 2
 */
int
BTree::Node::_CalculateSpace(uint32 from, uint32 to, uint8 type) const
{
	if (to < from || to >= ItemCount())
		return 0;

	if (Level() != 0)
		return sizeof(btrfs_index) * (to - from + 1);

	uint32 result = 0;
	if ((type & 1) == 1) {
		result += sizeof(btrfs_entry) * (to - from + 1);
	}
	if ((type & 2) == 2) {
		result += Item(from)->Offset() + Item(from)->Size()
			- Item(to)->Offset();
	}

	return result;
}


int
BTree::Node::SpaceUsed() const
{
	if (Level() == 0)
		return _CalculateSpace(0, ItemCount() - 1, 3);
	return _CalculateSpace(0, ItemCount() - 1, 0);
}


int
BTree::Node::SpaceLeft() const
{
	return fVolume->BlockSize() - SpaceUsed() - sizeof(btrfs_header);
}


void
BTree::Node::_Copy(const Node* origin, uint32 at, uint32 from, uint32 to,
	int length) const
{
	TRACE("Node::_Copy() at: %d from: %d to: %d length: %d\n",
		at, from, to, length);

	if (Level() == 0) {
		memcpy(Item(at), origin->Item(from), origin->_CalculateSpace(from, to));
		// Item offset of copied node must be changed to get the
		// item data offset correctly. length can be zero
		// but let it there doesn't harm anything.
		for (uint32 i = at; i - at <= to - from; ++i)
			Item(i)->SetOffset(Item(i)->Offset() - length);

		memcpy(ItemData(at + to - from), origin->ItemData(to),
			origin->_CalculateSpace(from, to, 2));
	} else {
		memcpy(Index(at), origin->Index(from),
			origin->_CalculateSpace(from, to));
	}
}


status_t
BTree::Node::_SpaceCheck(int length) const
{
	// this is a little bit weird here because we can't find
	// any suitable error code
	if (length < 0 && std::abs(length) >= SpaceUsed())
		return B_DIRECTORY_NOT_EMPTY;	// not enough data to delete
	if (length > 0 && length >= SpaceLeft())
		return B_DEVICE_FULL;			// no spare space
	return B_OK;
}


/*
 * copy node header, items and items data
 * length is size to insert/remove
 * if node is a internal node, length isnt used
 * length = 0: Copy a whole
 * length < 0: removing
 * length > 0: inserting
 */
status_t
BTree::Node::Copy(const Node* origin, uint32 start, uint32 end, int length)
	const
{
	status_t status = origin->_SpaceCheck(length);
	if (status != B_OK)
		return status;

	memcpy(fNode, origin->fNode, sizeof(btrfs_header));
	if (length == 0) {
		// like removing [0, start - 1] and keeping [start, end]
		length = -origin->_CalculateSpace(0, start - 1, 2);
		_Copy(origin, 0, start, end, length);
	} else if (length < 0) {
		//removing all items in [start, end]
		if (start > 0)
			_Copy(origin, 0, 0, start - 1, 0);	// <-- [start,...
		if (end + 1 < origin->ItemCount()) {
			// ..., end] -->
			// we only care data size
			length += origin->_CalculateSpace(start, end);
			_Copy(origin, start, end + 1, origin->ItemCount() - 1, length);
		}
	} else {
		//inserting in [start, end] - make a hole for later
		if (start > 0)
			_Copy(origin, 0, 0, start - 1, 0);
		if (start < origin->ItemCount()) {
			length -= origin->_CalculateSpace(start, end);
			_Copy(origin, end + 1, start, origin->ItemCount() - 1, length);
		}
	}

	return B_OK;
}


/* Like copy but here we use memmove on current node.
 */
status_t
BTree::Node::MoveEntries(uint32 start, uint32 end, int length) const
{
	status_t status = _SpaceCheck(length);
	if (status != B_OK || length == 0/*B_OK*/)
		return status;

	int entrySize = sizeof(btrfs_entry);
	if (Level() != 0)
		entrySize = sizeof(btrfs_index);

	uint8* base = (uint8*)fNode + sizeof(btrfs_header);
	end++;
	if (length < 0) {
		// removing [start, end]
		TRACE("Node::MoveEntries() removing ... start %" B_PRIu32 " end %"
			B_PRIu32 " length %i\n", start, end, length);
		length += _CalculateSpace(start, end - 1);
	} else {
		// length > 0
		// inserting into [start, end] - make room for later
		TRACE("Node::MoveEntries() inserting ... start %" B_PRIu32 " end %"
			B_PRIu32 " length %i\n", start, end, length);
		length -= _CalculateSpace(start, end - 1);
		std::swap(start, end);
	}

	if (end >= ItemCount())
		return B_OK;

	int dataSize = _CalculateSpace(end, ItemCount() - 1, 2);
	// moving items/block pointers
	memmove(base + start * entrySize, base + end * entrySize,
		_CalculateSpace(end, ItemCount() - 1));
	if (Level() == 0) {
		// moving item data
		int num = start - end;
		for(uint32 i = start; i < ItemCount() + num; ++i)
			Item(i)->SetOffset(Item(i)->Offset() - length);

		memmove(ItemData(ItemCount() - 1) - length, ItemData(ItemCount() - 1),
			dataSize);
	}

	return B_OK;
}


//	#pragma mark - BTree::Path implementation


BTree::Path::Path(BTree* tree)
	:
	fTree(tree)
{
	for (int i = 0; i < BTRFS_MAX_TREE_DEPTH; ++i) {
		fNodes[i] = NULL;
		fSlots[i] = 0;
	}
}


BTree::Path::~Path()
{
	for (int i = 0; i < BTRFS_MAX_TREE_DEPTH; ++i) {
		delete fNodes[i];
		fNodes[i] = NULL;
		fSlots[i] = 0;
	}
}


BTree::Node*
BTree::Path::GetNode(int level, int* _slot) const
{
	if (_slot != NULL)
		*_slot = fSlots[level];
	return fNodes[level];
}


BTree::Node*
BTree::Path::SetNode(off_t block, int slot)
{
	Node node(fTree->SystemVolume(), block);
	return SetNode(&node, slot);
}


BTree::Node*
BTree::Path::SetNode(const Node* node, int slot)
{
	uint8 level = node->Level();
	if (fNodes[level] == NULL) {
		fNodes[level] = new Node(fTree->SystemVolume(), node->BlockNum());
		if (fNodes[level] == NULL)
			return NULL;
	} else
		fNodes[level]->SetTo(node->BlockNum());

	if (slot == -1)
		fSlots[level] = fNodes[level]->ItemCount() - 1;
	else
		fSlots[level] = slot;
	return fNodes[level];
}


int
BTree::Path::Move(int level, int step)
{
	fSlots[level] += step;
	if (fSlots[level] < 0)
		return -1;
	if (fSlots[level] >= fNodes[level]->ItemCount())
		return 1;
	return 0;
}


status_t
BTree::Path::GetEntry(int slot, btrfs_key* _key, void** _value, uint32* _size,
	uint32* _offset)
{
	BTree::Node* leaf = fNodes[0];
	if (slot < 0 || slot >= leaf->ItemCount())
		return B_ENTRY_NOT_FOUND;

	if (_key != NULL)
		*_key = leaf->Item(slot)->key;

	uint32 itemSize = leaf->Item(slot)->Size();
	if (_value != NULL) {
		*_value = malloc(itemSize);
		if (*_value == NULL)
			return B_NO_MEMORY;

		memcpy(*_value, leaf->ItemData(slot), itemSize);
	}

	if (_size != NULL)
		*_size = itemSize;

	if (_offset != NULL)
		*_offset = leaf->Item(slot)->Offset();

	return B_OK;
}


status_t
BTree::Path::SetEntry(int slot, const btrfs_entry& entry, void* value)
{
	if (slot < 0)
		return B_ENTRY_NOT_FOUND;

	memcpy(fNodes[0]->Item(slot), &entry, sizeof(btrfs_entry));
	memcpy(fNodes[0]->ItemData(slot), value, entry.Size());
	return B_OK;
}


/*
 * Allocate and copy block and do all the changes that it can.
 * for now, we only copy-on-write tree block,
 * file data is "nocow" by default.
 *
 * 	o	parent	o
 * 	|	 ===> 	 \
 * 	o	      	x o
 */
status_t
BTree::Path::CopyOnWrite(Transaction& transaction, int level, uint32 start,
	int num, int length)
{
	Node* node = fNodes[level];
	if (node == NULL)
		return B_BAD_VALUE;

	status_t status;
	if (transaction.HasBlock(node->BlockNum())) {
		// cow-ed block can not be cow-ed again
		status = node->MoveEntries(start, start + num - 1, length);
		if (status != B_OK)
			return status;

		node->SetGeneration(transaction.SystemID());
		if (length < 0)
			node->SetItemCount(node->ItemCount() - num);
		else if (length > 0)
			node->SetItemCount(node->ItemCount() + num);

		return B_OK;
	}

	uint64 address;
	fsblock_t block;
	status = fTree->SystemVolume()->GetNewBlock(address, block);
	if (status != B_OK)
		return status;

	fNodes[level] = new(std::nothrow) BTree::Node(fTree->SystemVolume());
	if (fNodes[level] == NULL)
		return B_NO_MEMORY;

	fNodes[level]->SetToWritable(block, transaction.ID(), true);

	status = fNodes[level]->Copy(node, start, start + num - 1, length);
	if (status != B_OK)
		return status;

	fNodes[level]->SetGeneration(transaction.SystemID());
	fNodes[level]->SetLogicalAddress(address);
	if (length < 0)
		fNodes[level]->SetItemCount(node->ItemCount() - num);
	else if (length > 0)
		fNodes[level]->SetItemCount(node->ItemCount() + num);
	else
		fNodes[level]->SetItemCount(num);

	// change pointer of this node in parent
	int parentSlot;
	Node* parentNode = GetNode(level + 1, &parentSlot);
	if (parentNode != NULL)
		parentNode->Index(parentSlot)->SetLogicalAddress(address);

	if (level == fTree->RootLevel())
		fTree->SetRoot(fNodes[level]);

	delete node;
	return B_OK;
}


/* Copy-On-Write all internal nodes start from a specific level.
 * level > 0: to root
 * level <= 0: to leaf
 *
 *		path	cow-path       path    cow-path
 *	=================================================
 *		root	cow-root       root	level < 0
 *		 |  	|               |
 *		 n1 	cow-n1         ...______
 *		 |  	|               |       \
 *		 n2 	cow-n2          n1     cow-n1
 *		 |  	/               |        |
 *		...____/                n2     cow-n2
 *		 |  	                |        |
 *		leaf	level > 0      leaf    cow-leaf
 */
status_t
BTree::Path::InternalCopy(Transaction& transaction, int level)
{
	if (std::abs(level) >= fTree->RootLevel())
		return B_OK;

	TRACE("Path::InternalCopy() level %i\n", level);
	int from, to;
	if (level > 0) {
		from = level;
		to = fTree->RootLevel();
	} else {
		from = 0;
		to = std::abs(level);
	}

	Node* node = NULL;
	status_t status;
	while (from <= to) {
		node = fNodes[from];
		status = CopyOnWrite(transaction, from, 0, node->ItemCount(), 0);
		from++;
		if (status != B_OK)
			return status;
	}

	return B_OK;
}


//	#pragma mark - BTree implementation


BTree::BTree(Volume* volume)
	:
	fRootBlock(0),
	fRootLevel(0),
	fVolume(volume)
{
	mutex_init(&fIteratorLock, "btrfs b+tree iterator");
}


BTree::BTree(Volume* volume, btrfs_stream* stream)
	:
	fRootBlock(0),
	fRootLevel(0),
	fVolume(volume)
{
	mutex_init(&fIteratorLock, "btrfs b+tree iterator");
}


BTree::BTree(Volume* volume, fsblock_t rootBlock)
	:
	fRootBlock(rootBlock),
	fVolume(volume)
{
	mutex_init(&fIteratorLock, "btrfs b+tree iterator");
}


BTree::~BTree()
{
	// if there are any TreeIterators left, we need to stop them
	// (can happen when the tree's inode gets deleted while
	// traversing the tree - a TreeIterator doesn't lock the inode)
	mutex_lock(&fIteratorLock);

	SinglyLinkedList<TreeIterator>::Iterator iterator
		= fIterators.GetIterator();
	while (iterator.HasNext())
		iterator.Next()->Stop();
	mutex_destroy(&fIteratorLock);
}


int32
btrfs_key::Compare(const btrfs_key& key) const
{
	if (ObjectID() > key.ObjectID())
		return 1;
	if (ObjectID() < key.ObjectID())
		return -1;
	if (Type() > key.Type())
		return 1;
	if (Type() < key.Type())
		return -1;
	if (Offset() > key.Offset())
		return 1;
	if (Offset() < key.Offset())
		return -1;
	return 0;
}


/* Traverse from root to fill in the path along way its finding.
 * Return current slot at leaf if successful.
 */
status_t
BTree::Traverse(btree_traversing type, Path* path, const btrfs_key& key)
	const
{
	TRACE("BTree::Traverse() objectid %" B_PRId64 " type %d offset %"
		B_PRId64 " \n", key.ObjectID(),	key.Type(), key.Offset());
	fsblock_t physicalBlock = fRootBlock;
	Node node(fVolume, physicalBlock);
	int slot;
	status_t status = B_OK;

	while (node.Level() != 0) {
		TRACE("BTree::Traverse() level %d count %d\n", node.Level(),
			node.ItemCount());
		status = node.SearchSlot(key, &slot, BTREE_BACKWARD);
		if (status != B_OK)
			return status;
		if (path->SetNode(&node, slot) == NULL)
			return B_NO_MEMORY;

		TRACE("BTree::Traverse() getting index %" B_PRIu32 "\n", slot);

		status = fVolume->FindBlock(node.Index(slot)->LogicalAddress(),
				physicalBlock);
		if (status != B_OK) {
			ERROR("BTree::Traverse() unmapped block %" B_PRId64 "\n",
				node.Index(slot)->LogicalAddress());
			return status;
		}
		node.SetTo(physicalBlock);
	}

	TRACE("BTree::Traverse() dump count %" B_PRId32 "\n", node.ItemCount());
	status = node.SearchSlot(key, &slot, type);
	if (status != B_OK)
		return status;
	if (path->SetNode(&node, slot) == NULL)
		return B_NO_MEMORY;

	TRACE("BTree::Traverse() found %" B_PRIu32 " %" B_PRIu32 "\n",
		node.Item(slot)->Offset(), node.Item(slot)->Size());
	return slot;
}


/*!	Searches the key in the tree, and stores the allocated found item in
	_value, if successful.
	Returns B_OK when the key could be found, B_ENTRY_NOT_FOUND if not.
	It can also return other errors to indicate that something went wrong.
*/
status_t
BTree::_Find(Path* path, btrfs_key& wanted, void** _value, uint32* _size,
	uint32* _offset, btree_traversing type) const
{
	status_t status = Traverse(type, path, wanted);
	if (status < B_OK)
		return status;

	btrfs_key found;
	status = path->GetCurrentEntry(&found, _value, _size, _offset);
	if (status != B_OK)
		return status;

	if (found.Type() != wanted.Type() && wanted.Type() != BTRFS_KEY_TYPE_ANY)
		return B_ENTRY_NOT_FOUND;

	wanted = found;
	return B_OK;
}


status_t
BTree::FindNext(Path* path, btrfs_key& key, void** _value, uint32* _size,
	uint32* _offset) const
{
	return _Find(path, key, _value, _size, _offset, BTREE_FORWARD);
}


status_t
BTree::FindPrevious(Path* path, btrfs_key& key, void** _value, uint32* _size,
	uint32* _offset) const
{
	return _Find(path, key, _value, _size, _offset, BTREE_BACKWARD);
}


status_t
BTree::FindExact(Path* path, btrfs_key& key, void** _value, uint32* _size,
	uint32* _offset) const
{
	return _Find(path, key, _value, _size, _offset, BTREE_EXACT);
}


/*
 * Insert "num" of consecutive empty entries start with slot of "startKey"
 * if successful return the starting slot, otherwise return error code.
 */
status_t
BTree::MakeEntries(Transaction& transaction, Path* path,
	const btrfs_key& startKey, int num, int length)
{
	TRACE("BTree::MakeEntries() num %i key (% " B_PRIu64 " %" B_PRIu8 " %"
		B_PRIu64 ")\n", num, startKey.ObjectID(), startKey.Type(),
		startKey.Offset());

	status_t status = Traverse(BTREE_FORWARD, path, startKey);
	if (status < B_OK)
		return status;

	int slot = status;
	status = path->InternalCopy(transaction, 1);
	if (status != B_OK)
		return status;

	status = path->CopyOnWrite(transaction, 0, slot, num, length);
	if (status == B_DEVICE_FULL) {
		// TODO: push data or split node
		return status;
	}

	if (status != B_OK)
		return status;
	return slot;
}


/* MakeEntries and then fill in them.
 */
status_t
BTree::InsertEntries(Transaction& transaction, Path* path,
	btrfs_entry* entries, void** data, int num)
{
	int totalLength = sizeof(btrfs_entry) * num;
	for (int i = 0; i < num; i++)
		totalLength += entries[i].Size();

	status_t slot = MakeEntries(transaction, path, entries[0].key, num,
		totalLength);
	if (slot < B_OK)
		return slot;

	uint32 upperLimit;
	if (slot > 0) {
		path->GetEntry(slot - 1, NULL, NULL, NULL, &upperLimit);
	} else
		upperLimit = fVolume->BlockSize() - sizeof(btrfs_header);

	TRACE("BTree::InsertEntries() num: %i upper limit %" B_PRIu32 "\n", num,
		upperLimit);
	for (int i = 0; i < num; i++) {
		upperLimit -= entries[i].Size();
		entries[i].SetOffset(upperLimit);
		path->SetEntry(slot + i, entries[i], data[i]);
	}

	return B_OK;
}


/* Like MakeEntries, but here we remove entries instead.
 * Removed data stored in _data
 * May merge those functions into one.
 */
status_t
BTree::RemoveEntries(Transaction& transaction, Path* path,
	const btrfs_key& startKey, void** _data, int num)
{
	TRACE("BTree::RemoveEntries() num %i key (% " B_PRIu64 " %" B_PRIu8 " %"
		B_PRIu64 ")\n", num, startKey.ObjectID(), startKey.Type(),
		startKey.Offset());

	status_t status = Traverse(BTREE_EXACT, path, startKey);
	if (status < B_OK)
		return status;

	int slot = status;
	int length = -sizeof(btrfs_entry) * num;
	for (int i = 0; i < num; i++) {
		uint32 itemSize;
		path->GetEntry(slot + i, NULL, &_data[i], &itemSize);
		length -= itemSize;
	}

	status = path->InternalCopy(transaction, 1);
	if (status != B_OK)
		return status;

	status = path->CopyOnWrite(transaction, 0, slot, num, length);
	if (status == B_DIRECTORY_NOT_EMPTY) {
		// TODO: merge node or push data
	}

	return status;
}


status_t
BTree::PreviousLeaf(Path* path) const
{
	// TODO: use Traverse() ???
	int level = 0;
	int slot;
	Node* node = NULL;
	// iterate to the root until satisfy the condition
	while (true) {
		node = path->GetNode(level, &slot);
		if (node == NULL || slot != 0)
			break;
		level++;
	}

	// the current leaf is already the left most leaf or
	// path was not initialized
	if (node == NULL)
		return B_ENTRY_NOT_FOUND;

	path->Move(level, BTREE_BACKWARD);
	fsblock_t physicalBlock;
	// change all nodes below this level and slot to the ending
	do {
		status_t status = fVolume->FindBlock(
			node->Index(slot)->LogicalAddress(), physicalBlock);
		if (status != B_OK)
			return status;

		node = path->SetNode(physicalBlock, -1);
		if (node == NULL)
			return B_NO_MEMORY;
		slot = node->ItemCount() - 1;
		level--;
	} while(level != 0);

	return B_OK;
}


status_t
BTree::NextLeaf(Path* path) const
{
	int level = 0;
	int slot;
	Node* node = NULL;
	// iterate to the root until satisfy the condition
	while (true) {
		node = path->GetNode(level, &slot);
		if (node == NULL || slot < node->ItemCount() - 1)
			break;
		level++;
	}

	// the current leaf is already the right most leaf or
	// path was not initialized
	if (node == NULL)
		return B_ENTRY_NOT_FOUND;

	path->Move(level, BTREE_FORWARD);
	fsblock_t physicalBlock;
	// change all nodes below this level and slot to the beginning
	do {
		status_t status = fVolume->FindBlock(
			node->Index(slot)->LogicalAddress(), physicalBlock);
		if (status != B_OK)
			return status;

		node = path->SetNode(physicalBlock, 0);
		if (node == NULL)
			return B_NO_MEMORY;
		slot = 0;
		level--;
	} while(level != 0);

	return B_OK;
}


/* Set root infomation, to use this function root must be valid and
 * exists on disk.
 */
status_t
BTree::SetRoot(off_t logical, fsblock_t* block)
{
	if (block != NULL) {
		fRootBlock = *block;
	} else {
		if (fVolume->FindBlock(logical, fRootBlock) != B_OK) {
			ERROR("Find() unmapped block %" B_PRId64 "\n", fRootBlock);
			return B_ERROR;
		}
	}

	btrfs_header header;
	read_pos(fVolume->Device(), fRootBlock * fVolume->BlockSize(), &header,
		sizeof(btrfs_header));
	fRootLevel = header.Level();
	fLogicalRoot = header.LogicalAddress();
	return B_OK;
}


void
BTree::SetRoot(Node* root)
{
	fRootBlock = root->BlockNum();
	fLogicalRoot = root->LogicalAddress();
	fRootLevel = root->Level();
}


void
BTree::_AddIterator(TreeIterator* iterator)
{
	MutexLocker _(fIteratorLock);
	fIterators.Add(iterator);
}


void
BTree::_RemoveIterator(TreeIterator* iterator)
{
	MutexLocker _(fIteratorLock);
	fIterators.Remove(iterator);
}


//	#pragma mark -


TreeIterator::TreeIterator(BTree* tree, const btrfs_key& key)
	:
	fTree(tree),
	fKey(key),
	fIteratorStatus(B_NO_INIT)
{
	tree->_AddIterator(this);
	fPath = new(std::nothrow) BTree::Path(tree);
	if (fPath == NULL)
		fIteratorStatus = B_NO_MEMORY;
}


TreeIterator::~TreeIterator()
{
	if (fTree)
		fTree->_RemoveIterator(this);

	delete fPath;
	fPath = NULL;
}


void
TreeIterator::Rewind(bool inverse)
{
	if (inverse)
		fKey.SetOffset(BTREE_END);
	else
		fKey.SetOffset(BTREE_BEGIN);
	fIteratorStatus = B_NO_INIT;
}


/*!	Iterates through the tree in the specified direction.
*/
status_t
TreeIterator::_Traverse(btree_traversing direction)
{
	status_t status = fTree->Traverse(direction, fPath, fKey);
	if (status < B_OK) {
		ERROR("TreeIterator::Traverse() Find failed\n");
		return status;
	}

	return (fIteratorStatus = B_OK);
}


// Like GetEntry in BTree::Path but here we check the type and moving.
status_t
TreeIterator::_GetEntry(btree_traversing type, void** _value, uint32* _size,
	uint32* _offset)
{
	status_t status;
	if (fIteratorStatus == B_NO_INIT) {
		status = _Traverse(type);
		if (status != B_OK)
			return status;
		type = BTREE_EXACT;
	}

	if (fIteratorStatus != B_OK)
		return fIteratorStatus;

	int move = fPath->Move(0, type);
	if (move > 0)
		status = fTree->NextLeaf(fPath);
	else if (move < 0)
		status = fTree->PreviousLeaf(fPath);
	if (status != B_OK)
		return status;

	btrfs_key found;
	status = fPath->GetCurrentEntry(&found, _value, _size, _offset);
	if (status != B_OK)
		return status;

	fKey.SetObjectID(found.ObjectID());
	fKey.SetOffset(found.Offset());
	if (fKey.Type() != found.Type() && fKey.Type() != BTRFS_KEY_TYPE_ANY)
		return B_ENTRY_NOT_FOUND;

	return B_OK;
}


/*!	just sets the current key in the iterator.
*/
status_t
TreeIterator::Find(const btrfs_key& key)
{
	if (fIteratorStatus == B_INTERRUPTED)
		return fIteratorStatus;

	fKey = key;
	fIteratorStatus = B_NO_INIT;
	return B_OK;
}


void
TreeIterator::Stop()
{
	fTree = NULL;
	fIteratorStatus = B_INTERRUPTED;
}