haiku.git

// Iterators.h
//
// Copyright (c) 2003-2010, Ingo Weinhold (bonefish@cs.tu-berlin.de)
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//
// You can alternatively use *this file* under the terms of the the MIT
// license included in this package.


#include "Iterators.h"

#include "Block.h"
#include "BlockCache.h"
#include "Key.h"
#include "IndirectItem.h"
#include "StatItem.h"
#include "Tree.h"


// min and max
// We don't want to include <algobase.h> otherwise we also get <iostream.h>
// and other undesired things.
template<typename C>
static inline C min(const C &a, const C &b) { return (a < b ? a : b); }
template<typename C>
static inline C max(const C &a, const C &b) { return (a > b ? a : b); }

/*!
	\class TreePath
	\brief Represents a path in the tree.

	It is composed of TreePath::Elements each one storing the block number
	of a node and the index of a child node.
*/

// constructor
TreePath::TreePath(uint32 maxLength)
	: fMaxLength(maxLength),
	  fLength(0),
	  fElements(NULL)
{
	fElements = new(nothrow) Element[fMaxLength];
}

// destructor
TreePath::~TreePath()
{
	if (fElements)
		delete[] fElements;
}

// InitCheck
status_t
TreePath::InitCheck() const
{
	return (fElements ? B_OK : B_NO_MEMORY);
}

// GetMaxLength
uint32
TreePath::GetMaxLength() const
{
	return fMaxLength;
}

// GetLength
uint32
TreePath::GetLength() const
{
	return fLength;
}

// ElementAt
const TreePath::Element *
TreePath::ElementAt(int32 index) const
{
	Element *element = NULL;
	if (InitCheck() == B_OK && index >= 0 && (uint32)index < GetLength())
		element = fElements + index;
	return element;
}

// GetTopElement
const TreePath::Element *
TreePath::GetTopElement() const
{
	return ElementAt(GetLength() - 1);
}

// PushElement
status_t
TreePath::PushElement(uint64 blockNumber, int32 index)
{
	status_t error = (fLength < fMaxLength ? InitCheck() : B_BAD_VALUE);
	if (error == B_OK) {
		error = fElements[fLength].SetTo(blockNumber, index);
		if (error == B_OK)
			fLength++;
	}
	return error;
}

// PopElement
status_t
TreePath::PopElement()
{
	status_t error = InitCheck();
	if (error == B_OK) {
		if (fLength > 0)
			fLength--;
		else
			error = B_ERROR;
	}
	return error;
}


/*!
	\class TreePath::Element
	\brief Store information about one element in a tree path.
*/

// SetTo
status_t
TreePath::Element::SetTo(uint64 blockNumber, int32 index)
{
	fBlockNumber = blockNumber;
	fIndex = index;
	return B_OK;
}

// GetBlockNumber
uint64
TreePath::Element::GetBlockNumber() const
{
	return fBlockNumber;
}

// GetIndex
int32
TreePath::Element::GetIndex() const
{
	return fIndex;
}


/*!
	\class TreeIterator
	\brief Class used to iterate and navigate in trees.

	A TreeIterator is usually initialized to the root node of the tree
	and can be used to navigate and search in the tree.
*/

// constructor
TreeIterator::TreeIterator(Tree *tree)
	: fTree(NULL),
	  fCurrentNode(NULL),
	  fPath(NULL)
{
	SetTo(tree);
}

// destructor
TreeIterator::~TreeIterator()
{
	Unset();
}

// SetTo
status_t
TreeIterator::SetTo(Tree *tree)
{
	Unset();
	fTree = tree;
	fCurrentNode = NULL;
	fPath = NULL;
	if (fTree) {
		fCurrentNode = fTree->GetRootNode();
		if (fCurrentNode)
			fCurrentNode->Get();
		fPath = new(nothrow) TreePath(tree->GetTreeHeight());
	}
	return InitCheck();
}

// Unset
void
TreeIterator::Unset()
{
	if (fPath) {
		delete fPath;
		fPath = NULL;
	}
	if (fCurrentNode) {
		fCurrentNode->Put();
		fCurrentNode = NULL;
	}
}

// InitCheck
status_t
TreeIterator::InitCheck() const
{
	return (fTree && fCurrentNode && fPath ? fPath->InitCheck() : B_NO_INIT);
}

// GetNode
Node *
TreeIterator::GetNode() const
{
	return fCurrentNode;
}

// GetLevel
int32
TreeIterator::GetLevel() const
{
	int32 level = 0;
	if (fCurrentNode)
		level = fCurrentNode->GetLevel();
	return level;
}

// GoTo
/*!	\brief Goes into a given direction.

	\a direction can be
	- \c FORWARD: Forward/to the right. Goes to the next child node of the
	  current node.
	- \c BACKWARDS: Forward/to the right. Goes to the previous child node of
	  the current node.
	- \c UP: Up one level (in root direction). Goes to the parent node of
	  the current node. The current node is the child node, it is pointed
	  to afterward.
	- \c DOWN: Down one level (in leaf direction). Goes to the child node of
	  the current node the iterator currently points at. Points afterwards to
	  the 0th child node of the new current node (unless it is a leaf node).

	\c FORWARD and \c BACKWARDS do not change the current node!

	\param direction \c FORWARD, \c BACKWARDS, \c UP or \c DOWN
	\return \c B_OK, if everything went fine
*/
status_t
TreeIterator::GoTo(uint32 direction)
{
	status_t error = InitCheck();
	if (error == B_OK) {
		switch (direction) {
			case FORWARD:
			{
				if (fCurrentNode->IsInternal()
					&& fIndex < fCurrentNode->CountItems()) {
					fIndex++;
				} else {
					error = B_ENTRY_NOT_FOUND;
				}
				break;
			}
			case BACKWARDS:
			{
				if (fCurrentNode->IsInternal() && fIndex > 0)
					fIndex--;
				else
					error = B_ENTRY_NOT_FOUND;
				break;
			}
			case UP:
			{
				error = _PopTopNode();
				break;
			}
			case DOWN:
			{
				if (fCurrentNode->IsInternal()) {
					InternalNode *internal = fCurrentNode->ToInternalNode();
					const DiskChild *child = internal->ChildAt(fIndex);
					if (child) {
						Node *node = NULL;
						error = fTree->GetNode(child->GetBlockNumber(), &node);
						if (error == B_OK)
							error = _PushCurrentNode(node, 0);
					} else
						error = B_ENTRY_NOT_FOUND;
				} else
					error = B_ENTRY_NOT_FOUND;
				break;
			}
		}
	}
	return error;
}

// GoToPreviousLeaf
/*!	\brief Goes to the previous leaf node.

	This method operates only at leaf node level. It finds the next leaf
	node to the left. Fails, if the current node is no leaf node.

	\param node Pointer to a pre-allocated LeafNode pointer that shall be set
		   to the found node.
	\return \c B_OK, if everything went fine
*/
status_t
TreeIterator::GoToPreviousLeaf(LeafNode **node)
{
	status_t error = InitCheck();
	if (error == B_OK) {
		if (fCurrentNode->IsLeaf()) {
			// find downmost branch on our path, that leads further left
			bool found = false;
			while (error == B_OK && !found) {
				error = GoTo(UP);
				if (error == B_OK)
					found = (GoTo(BACKWARDS) == B_OK);
			}
			// descend the branch to the rightmost leaf
			if (error == B_OK) {
				// one level down
				error = GoTo(DOWN);
				// then keep right
				while (error == B_OK && fCurrentNode->IsInternal()) {
					fIndex = fCurrentNode->CountItems();
					error = GoTo(DOWN);
				}
			}
			// set the result
			if (error == B_OK && node)
				*node = fCurrentNode->ToLeafNode();
		} else
			error = B_ENTRY_NOT_FOUND;
	}
	return error;
}

// GoToNextLeaf
/*!	\brief Goes to the next leaf node.

	This method operates only at leaf node level. It finds the next leaf
	node to the right. Fails, if the current node is no leaf node.

	\param node Pointer to a pre-allocated LeafNode pointer that shall be set
		   to the found node.
	\return \c B_OK, if everything went fine
*/
status_t
TreeIterator::GoToNextLeaf(LeafNode **node)
{
	status_t error = InitCheck();
	if (error == B_OK) {
		if (fCurrentNode->IsLeaf()) {
			// find downmost branch on our path, that leads further right
			bool found = false;
			while (error == B_OK && !found) {
				error = GoTo(UP);
				if (error == B_OK)
					found = (GoTo(FORWARD) == B_OK);
			}
			// descend the branch to the leftmost leaf
			while (error == B_OK && fCurrentNode->IsInternal())
				error = GoTo(DOWN);
			// set the result
			if (error == B_OK && node)
				*node = fCurrentNode->ToLeafNode();
		} else
			error = B_ENTRY_NOT_FOUND;
	}
	return error;
}

// FindRightMostLeaf
/*!	\brief Finds the rightmost leaf node that may contain the supplied key.

	The method starts at the current node and only goes downwards.
	In the spanned subtree it finds the rightmost leaf node whose left
	delimiting key is not greater than the supplied key.

	\param key The key to be found.
	\param node Pointer to a pre-allocated LeafNode pointer that shall be set
		   to the found node.
	\return \c B_OK, if everything went fine.
*/
status_t
TreeIterator::FindRightMostLeaf(const VKey *k, LeafNode **node)
{
//printf("TreeIterator::FindRightMostLeaf()\n");
	status_t error = (k ? InitCheck() : B_BAD_VALUE);
	while (error == B_OK && fCurrentNode->IsInternal()) {
		int32 index = 0;
		error = _SearchRightMost(fCurrentNode->ToInternalNode(), k, &index);
		if (error == B_OK) {
			fIndex = index;
			error = GoTo(DOWN);
		}
	}
//if (error == B_OK)
//printf("found node: index: %ld\n", fIndex);
	// set the result
	if (error == B_OK && node)
		*node = fCurrentNode->ToLeafNode();
//printf("TreeIterator::FindRightMostLeaf() done: %s\n", strerror(error));
	return error;
}

// Suspend
/*!	\brief Suspends the iterator.

	This means, the current node is Put() and its block number and child node
	index pushed onto the tree path. This should be done, when the iteration
	is not to be continued immediately (or for the foreseeable future) and
	the node block shall not be locked in memory for that time.

	Resume() is to be called, before the iteration can be continued.

	\return \c B_OK, if everything went fine.
*/
status_t
TreeIterator::Suspend()
{
	status_t error = InitCheck();
	if (error == B_OK)
		error = _PushCurrentNode();
	if (error == B_OK)
		fCurrentNode = NULL;
	return error;
}

// Resume
/*!	\brief Resumes the iteration.

	To be called after a Suspend(), before the iteration can be continued.

	\return \c B_OK, if everything went fine.
*/
status_t
TreeIterator::Resume()
{
	status_t error
		= (fTree && !fCurrentNode && fPath ? fPath->InitCheck() : B_NO_INIT);
	if (error == B_OK)
		error = _PopTopNode();
	return error;
}

// _PushCurrentNode
status_t
TreeIterator::_PushCurrentNode(Node *newTopNode, int32 newIndex)
{
	status_t error = fPath->PushElement(fCurrentNode->GetNumber(), fIndex);
	if (error == B_OK) {
		fCurrentNode->Put();
		fCurrentNode = newTopNode;
		fIndex = newIndex;
	}
	return error;
}

// _PopTopNode
status_t
TreeIterator::_PopTopNode()
{
	status_t error = B_OK;
	if (fPath->GetLength() > 0) {
		const TreePath::Element *element = fPath->GetTopElement();
		Node *node = NULL;
		error = fTree->GetNode(element->GetBlockNumber(), &node);
		if (error == B_OK) {
			if (fCurrentNode)
				fCurrentNode->Put();
			fCurrentNode = node;
			fIndex = element->GetIndex();
			fPath->PopElement();
		}
	} else
		error = B_BAD_VALUE;
	return error;
}

// _SearchRightMost
status_t
TreeIterator::_SearchRightMost(InternalNode *node, const VKey *k, int32 *index)
{
//FUNCTION_START();
	// find the last node that may contain the key, i.e. the node with the
	// greatest index whose left delimiting key is less or equal the given key
	status_t error = (node && k && index ? B_OK : B_BAD_VALUE);
	if (error == B_OK) {
//PRINT(("  searching: "));
//k->Dump();
		// binary search: lower and upper are node indices, mid is a key index
		int32 lower = 0;
		int32 upper = node->CountItems();
		while (lower < upper) {
			int32 mid = (lower + upper) / 2;	// lower <= mid < upper <= count
			VKey midKey(node->KeyAt(mid));
//PRINT(("  mid: %3ld: ", mid));
//midKey.Dump();
			if (*k < midKey)			// => node index <= mid
				upper = mid;					// lower <= upper < count
			else								// => node index > mid
				lower = mid + 1;				// lower <= upper <= count
//PRINT(("  lower: %ld, upper: %ld\n", lower, upper));
		}
		if (error == B_OK)
			*index = lower;
	}
//RETURN_ERROR(error);
	return error;
}


/*!
	\class ItemIterator
	\brief Class used to iterate through leaf node items.

	A ItemIterator is usually initialized to the root node of the tree,
	and before it can be used for iteration, FindRightMostClose() or
	FindRightMost() must be invoked. They set the iterator to an item
	and afterwards one can use GoToPrevious() and GoToNext() to get the
	previous/next ones.
*/

// constructor
ItemIterator::ItemIterator(Tree *tree)
	: fTreeIterator(tree),
	  fIndex(0)
{
}

// SetTo
status_t
ItemIterator::SetTo(Tree *tree)
{
	status_t error = fTreeIterator.SetTo(tree);
	fIndex = 0;
	return error;
}

// InitCheck
status_t
ItemIterator::InitCheck() const
{
	return fTreeIterator.InitCheck();
}

// GetCurrent
status_t
ItemIterator::GetCurrent(Item *item)
{
	LeafNode *node = NULL;
	status_t error = (item ? _GetLeafNode(&node) : B_BAD_VALUE);
	if (error == B_OK) {
		if (fIndex >= 0 && fIndex < node->CountItems())
			error = item->SetTo(node, fIndex);
		else
			error = B_ENTRY_NOT_FOUND;
	}
	return error;
}

// GoToPrevious
status_t
ItemIterator::GoToPrevious(Item *item)
{
	LeafNode *node = NULL;
	status_t error = _GetLeafNode(&node);
	if (error == B_OK) {
		// get the leaf node on which the next item resides
		int32 newIndex = fIndex - 1;
		while (error == B_OK
			   && (newIndex < 0 || newIndex >= node->CountItems())) {
			error = fTreeIterator.GoToPreviousLeaf(&node);
			if (error == B_OK)
				newIndex = node->CountItems() - 1;
		}
		// got the node, get the item
		if (error == B_OK) {
			fIndex = newIndex;
			if (item)
				error = item->SetTo(node, fIndex);
		}
	}
	return error;
}

// GoToNext
status_t
ItemIterator::GoToNext(Item *item)
{
//PRINT(("ItemIterator::GoToNext()\n"));
	LeafNode *node = NULL;
	status_t error = _GetLeafNode(&node);
	if (error == B_OK) {
//PRINT(("  leaf node: %lld\n", node->GetNumber()));
		// get the leaf node on which the next item resides
		int32 newIndex = fIndex + 1;
		while (error == B_OK && newIndex >= node->CountItems()) {
			error = fTreeIterator.GoToNextLeaf(&node);
			newIndex = 0;
		}
		// got the node, get the item
		if (error == B_OK) {
//PRINT(("  leaf node now: %lld\n", node->GetNumber()));
			fIndex = newIndex;
//PRINT(("  index now: %ld\n", fIndex));
			if (item)
				error = item->SetTo(node, fIndex);
		}
	}
//PRINT(("ItemIterator::GoToNext() done: %s\n", strerror(error)));
	return error;
}

// FindRightMostClose
/*!	\brief Finds the rightmost item that may contain the supplied key.

	The method finds the rightmost item whose left delimiting key is not
	greater than the supplied key.

	\param key The key to be found.
	\param item Pointer to a pre-allocated Item that shall be set
		   to the found item.
	\return \c B_OK, if everything went fine.
*/
status_t
ItemIterator::FindRightMostClose(const VKey *k, Item *item)
{
//printf("ItemIterator::FindRightMostClose()\n");
	status_t error = (k ? InitCheck() : B_BAD_VALUE);
	// find rightmost leaf node with the given key
	if (error == B_OK)
		error = fTreeIterator.FindRightMostLeaf(k);
	// search the node for the key
	if (error == B_OK) {
		LeafNode *node = fTreeIterator.GetNode()->ToLeafNode();
		error = _SearchRightMost(node, k, &fIndex);
		if (error == B_OK && item)
{
			error = item->SetTo(node, fIndex);
//VKey itemKey;
//printf("  found item: ");
//item->GetKey(&itemKey)->Dump();
}
	}
//printf("ItemIterator::FindRightMostClose() done: %s\n", strerror(error));
	return error;
}

// FindRightMost
/*!	\brief Finds the rightmost item that starts with the supplied key.

	The method finds the rightmost item whose left delimiting key is equal
	to the supplied key.

	\param key The key to be found.
	\param item Pointer to a pre-allocated Item that shall be set
		   to the found item.
	\return \c B_OK, if everything went fine.
*/
status_t
ItemIterator::FindRightMost(const VKey *k, Item *item)
{
//TFUNCTION_START();
	// find the first item with a greater or equal key, and check whether the
	// key is equal
	Item closeItem;
	status_t error = FindRightMostClose(k, &closeItem);
//REPORT_ERROR(error);
	if (error == B_OK) {
		VKey itemKey;
		closeItem.GetHeader()->GetKey(&itemKey);
		if (*k == itemKey) {
			if (item)
				*item = closeItem;
		} else
{
//PRINT(("keys not equal: dirID: %lu, objectID: %lu, offset: %Lu, type: %hu\n",
//itemKey.GetDirID(), itemKey.GetObjectID(), itemKey.GetOffset(), itemKey.GetType()));
			error = B_ENTRY_NOT_FOUND;
}
	}
//REPORT_ERROR(error);
	return error;
}

// Suspend
/*! \brief Suspends the iterator.
	\see TreeIterator::Suspend().
	\return \c B_OK, if everything went fine.
*/
status_t
ItemIterator::Suspend()
{
	return fTreeIterator.Suspend();
}

// Resume
/*! \brief Resumes the iteration.
	\see TreeIterator::Resume().
	\return \c B_OK, if everything went fine.
*/
status_t
ItemIterator::Resume()
{
	return fTreeIterator.Resume();
}

// _GetLeafNode
status_t
ItemIterator::_GetLeafNode(LeafNode **leafNode) const
{
	status_t error = InitCheck();
	if (error == B_OK) {
		if (Node *node = fTreeIterator.GetNode()) {
			if (node->IsLeaf())
				*leafNode = node->ToLeafNode();
			else
				error = B_ENTRY_NOT_FOUND;
		} else
			error = B_ERROR;
	}
	return error;
}

// _SearchRightMost
status_t
ItemIterator::_SearchRightMost(LeafNode *node, const VKey *k,
							   int32 *index) const
{
//FUNCTION_START();
	status_t error = (node && k && index ? B_OK : B_BAD_VALUE);
	// find the first item with a less or equal key
	if (error == B_OK) {
//PRINT(("  searching: "));
//k->Dump();
/*
		// simple linear search backwards
		int32 foundIndex = -1;
		for (int32 i = node->CountItems() - 1; foundIndex < 0 && i >= 0; i--) {
			VKey itemKey;
			node->ItemHeaderAt(i)->GetKey(&itemKey);
			if (itemKey <= *k) {
				foundIndex = i;
				error = B_OK;
				break;
			}
		}
		// check whether all item keys are greater
		if (foundIndex < 0)
			error = B_ENTRY_NOT_FOUND;
		// set result
		if (error == B_OK)
			*index = foundIndex;
*/
		// binary search
		// check lower bound first
		VKey lowerKey;
		node->ItemHeaderAt(0)->GetKey(&lowerKey);
		if (lowerKey <= *k) {
			// pre-conditions hold
			int32 lower = 0;
			int32 upper = node->CountItems() - 1;
			while (lower < upper) {
				int32 mid = (lower + upper + 1) / 2;
				VKey midKey;
				node->ItemHeaderAt(mid)->GetKey(&midKey);
//PRINT(("  mid: %3ld: ", mid));
//midKey.Dump();
				if (midKey > *k)
					upper = mid - 1;
				else
					lower = mid;
//PRINT(("  lower: %ld, upper: %ld\n", lower, upper));
			}
			*index = lower;
		} else
			error = B_ENTRY_NOT_FOUND;
	}
//RETURN_ERROR(error);
	return error;
}


/*!
	\class ObjectItemIterator
	\brief Class used to iterate through leaf node items.

	This class basically wraps the ItemIterator class and provides a
	more convenient interface for iteration through items of one given
	object (directory, link or file). It finds only items of the object
	identified by the dir and object ID specified on initialization.
*/

// constructor
/*!	\brief Creates and initializes a ObjectItemIterator.

	The iterator is initialized to find only items belonging to the object
	identified by \a dirID and \a objectID. \a startOffset specifies the
	offset (key offset) at which the iteration shall begin.

	Note, that offsets don't need to be unique for an object, at least not
	for files -- all indirect (and direct?) items have the same offset (1).
	This has the ugly side effect, when iterating forward there may be items
	with the same offset on previous nodes that will be skipped at the
	beginning. The GetNext() does always find the item on the rightmost
	possible node. Therefore searching forward starting with FIRST_ITEM_OFFSET
	doesn't work for files!

	\param tree The tree.
	\param dirID The directory ID of the object.
	\param objectID The object ID of the object.
	\param startOffset The offset at which to begin the iteration.
*/
ObjectItemIterator::ObjectItemIterator(Tree *tree, uint32 dirID,
									   uint32 objectID, uint64 startOffset)
	: fItemIterator(tree),
	  fDirID(dirID),
	  fObjectID(objectID),
	  fOffset(startOffset),
	  fFindFirst(true),
	  fDone(false)
{
}

// SetTo
/*!	\brief Re-initializes a ObjectItemIterator.

	The iterator is initialized to find only items belonging to the object
	identified by \a dirID and \a objectID. \a startOffset specifies the
	offset (key offset) at which the iteration shall begin.

	\param tree The tree.
	\param dirID The directory ID of the object.
	\param objectID The object ID of the object.
	\param startOffset The offset at which to begin the iteration.
	\return \c B_OK, if everything went fine.
*/
status_t
ObjectItemIterator::SetTo(Tree *tree, uint32 dirID, uint32 objectID,
						  uint64 startOffset)
{
	status_t error = fItemIterator.SetTo(tree);
	fDirID = dirID;
	fObjectID = objectID;
	fOffset = startOffset;
	fFindFirst = true;
	fDone = false;
	return error;
}

// InitCheck
status_t
ObjectItemIterator::InitCheck() const
{
	return fItemIterator.InitCheck();
}

// GetNext
/*!	\brief Returns the next item belonging to the object.

	Note, that offsets don't need to be unique for an object, at least not
	for files -- all indirect (and direct?) items have the same offset (1).
	This has the ugly side effect, when iterating forward there may be items
	with the same offset on previous nodes that will be skipped at the
	beginning. The GetNext() does always find the item on the rightmost
	possible node. Therefore searching forward starting with FIRST_ITEM_OFFSET
	doesn't work for files!

	\param foundItem Pointer to a pre-allocated Item that shall be set
		   to the found item.
	\return \c B_OK, if everything went fine, \c B_ENTRY_NOT_FOUND, if we're
			through.
*/
status_t
ObjectItemIterator::GetNext(Item *foundItem)
{
//PRINT(("ObjectItemIterator::GetNext(): fDirID: %lu, fObjectID: %lu\n", fDirID, fObjectID));
	status_t error = (foundItem ? InitCheck() : B_BAD_VALUE);
	if (error == B_OK && fDone)
		error = B_ENTRY_NOT_FOUND;
	if (error == B_OK) {
		// get the next item
		Item item;
		if (fFindFirst) {
			// first invocation: find the item with the given IDs and offset
			VKey k(fDirID, fObjectID, fOffset, 0, KEY_FORMAT_3_5);
			error = fItemIterator.FindRightMostClose(&k, &item);
			fFindFirst = false;
		} else {
			// item iterator positioned, get the next item
			error = fItemIterator.GoToNext(&item);
//REPORT_ERROR(error);
		}
		// check whether the item belongs to our object
		if (error == B_OK) {
			VKey itemKey;
			if (item.GetDirID() == fDirID && item.GetObjectID() == fObjectID)
				*foundItem = item;
			else
{
//PRINT(("  found item for another object: (%lu, %lu)\n", item.GetDirID(), item.GetObjectID()));
				error = B_ENTRY_NOT_FOUND;
}
		}
		if (error != B_OK)
			fDone = true;
	}
//	return error;
RETURN_ERROR(error)
}

// GetNext
/*!	\brief Returns the next item belonging to the object.

	This version finds only items of the specified type.

	\param foundItem Pointer to a pre-allocated Item that shall be set
		   to the found item.
	\param type The type the found item must have.
	\return \c B_OK, if everything went fine, \c B_ENTRY_NOT_FOUND, if we're
			through.
*/
status_t
ObjectItemIterator::GetNext(Item *foundItem, uint32 type)
{
	status_t error = B_OK;
	do {
		error = GetNext(foundItem);
	} while (error == B_OK && foundItem->GetType() != type);
	return error;
}

// GetPrevious
/*!	\brief Returns the previous item belonging to the object.
	\param foundItem Pointer to a pre-allocated Item that shall be set
		   to the found item.
	\return \c B_OK, if everything went fine, \c B_ENTRY_NOT_FOUND, if we're
			through.
*/
status_t
ObjectItemIterator::GetPrevious(Item *foundItem)
{
//PRINT(("ObjectItemIterator::GetPrevious()\n"));
	status_t error = (foundItem ? InitCheck() : B_BAD_VALUE);
	if (error == B_OK && fDone)
		error = B_ENTRY_NOT_FOUND;
	if (error == B_OK) {
		// get the next item
		Item item;
		if (fFindFirst) {
			// first invocation: find the rightmost item of the object
			VKey k(fDirID, fObjectID, fOffset, 0xffffffffUL, KEY_FORMAT_3_5);
			error = fItemIterator.FindRightMostClose(&k, &item);
			fFindFirst = false;
		} else {
			// item iterator positioned, get the previous item
			error = fItemIterator.GoToPrevious(&item);
		}
		// check whether the item belongs to our object
		if (error == B_OK) {
			VKey itemKey;
			if (item.GetDirID() == fDirID && item.GetObjectID() == fObjectID) {
//PRINT(("  found item: %lu, %lu, %Lu\n", fDirID, fObjectID, item.GetOffset()));
				*foundItem = item;
			} else
{
//PRINT(("  item belongs to different object: (%lu, %lu)\n", item.GetDirID(), item.GetObjectID()));
				error = B_ENTRY_NOT_FOUND;
}
		}
		if (error != B_OK)
			fDone = true;
	}
//PRINT(("ObjectItemIterator::GetPrevious() done: %s\n", strerror(error)));
	return error;
}

// GetPrevious
/*!	\brief Returns the previous item belonging to the object.

	This version finds only items of the specified type.

	\param foundItem Pointer to a pre-allocated Item that shall be set
		   to the found item.
	\param type The type the found item must have.
	\return \c B_OK, if everything went fine, \c B_ENTRY_NOT_FOUND, if we're
			through.
*/
status_t
ObjectItemIterator::GetPrevious(Item *foundItem, uint32 type)
{
	status_t error = B_OK;
	do {
		error = GetPrevious(foundItem);
	} while (error == B_OK && foundItem->GetType() != type);
	return error;
}

// Suspend
/*! \brief Suspends the iterator.
	\see ItemIterator::Suspend().
	\return \c B_OK, if everything went fine.
*/
status_t
ObjectItemIterator::Suspend()
{
	return fItemIterator.Suspend();
}

// Resume
/*! \brief Resumes the iteration.
	\see ItemIterator::Resume().
	\return \c B_OK, if everything went fine.
*/
status_t
ObjectItemIterator::Resume()
{
	return fItemIterator.Resume();
}


/*!
	\class DirEntryIterator
	\brief Class used to iterate through DirEntries.
*/

// constructor
/*!	\brief Creates and initializes a DirEntryIterator.

	The iterator is initialized to find only entries belonging to the directory
	identified by \a dirID and \a objectID. \a startOffset specifies the
	offset (key offset) at which the iteration shall begin. If \a fixedHash
	is \c true, only items that have the same hash value as \a startOffset
	are found.

	\param tree The tree.
	\param dirID The directory ID of the object.
	\param objectID The object ID of the object.
	\param startOffset The offset at which to begin the iteration.
	\param fixedHash \c true to find only entries with the same hash as
		   \a startOffset
*/
DirEntryIterator::DirEntryIterator(Tree *tree, uint32 dirID, uint32 objectID,
								   uint64 startOffset, bool fixedHash)
	: fItemIterator(tree, dirID, objectID, startOffset),
	  fDirItem(),
	  fIndex(-1),
	  fFixedHash(fixedHash),
	  fDone(false)
{
}

// SetTo
/*!	\brief Re-initializes a DirEntryIterator.

	The iterator is initialized to find only entries belonging to the directory
	identified by \a dirID and \a objectID. \a startOffset specifies the
	offset (key offset) at which the iteration shall begin. If \a fixedHash
	is \c true, only items that have the same hash value as \a startOffset
	are found.

	\param tree The tree.
	\param dirID The directory ID of the object.
	\param objectID The object ID of the object.
	\param startOffset The offset at which to begin the iteration.
	\param fixedHash \c true to find only entries with the same hash as
		   \a startOffset
*/
status_t
DirEntryIterator::SetTo(Tree *tree, uint32 dirID, uint32 objectID,
						uint64 startOffset, bool fixedHash)
{
	fDirItem.Unset();
	status_t error = fItemIterator.SetTo(tree, dirID, objectID, startOffset);
	fIndex = -1;
	fFixedHash = fixedHash;
	fDone = false;
	return error;
}

// InitCheck
status_t
DirEntryIterator::InitCheck() const
{
	return fItemIterator.InitCheck();
}

// Rewind
/*!	\brief Rewinds the iterator.

	Simply re-initializes the iterator to the parameters of the last
	initialization.

	\return \c B_OK, if everything went fine.
*/
status_t
DirEntryIterator::Rewind()
{
	return SetTo(GetTree(), GetDirID(), GetObjectID(), GetOffset(),
				 fFixedHash);
}

// GetNext
/*!	\brief Returns the next entry belonging to the directory.
	\param foundItem Pointer to a pre-allocated Item that shall be set
		   to the found item.
	\param entryIndex Pointer to a pre-allocated int32 that shall be set
		   to the found entry index.
	\param _entry Pointer to a pre-allocated DirEntry pointer that shall be set
		   to the found entry. May be \c NULL.
	\return \c B_OK, if everything went fine, \c B_ENTRY_NOT_FOUND, if we're
			through.
*/
status_t
DirEntryIterator::GetNext(DirItem *foundItem, int32 *entryIndex,
						  DirEntry **_entry)
{
	status_t error = (foundItem && entryIndex ? InitCheck() : B_BAD_VALUE);
	// get the next DirItem, if necessary
	// the loop skips empty DirItems gracefully
	while (error == B_OK
		   && (fIndex < 0 || fIndex >= fDirItem.GetEntryCount())) {
		error = fItemIterator.GetNext(&fDirItem, TYPE_DIRENTRY);
		if (error == B_OK) {
			if (fDirItem.Check() == B_OK)
				fIndex = 0;
			else	// bad data: skip the item
				fIndex = -1;
		}
	}
	// get the next entry and check whether it has the correct offset
	if (error == B_OK) {
		DirEntry *entry = fDirItem.EntryAt(fIndex);
		if (!fFixedHash
			|| offset_hash_value(entry->GetOffset())
			   == offset_hash_value(GetOffset())) {
			*foundItem = fDirItem;
			*entryIndex = fIndex;
			if (_entry)
				*_entry = entry;
			fIndex++;
		} else
			error = B_ENTRY_NOT_FOUND;
	}
	return error;
}

// GetPrevious
/*!	\brief Returns the previous entry belonging to the directory.
	\param foundItem Pointer to a pre-allocated Item that shall be set
		   to the found item.
	\param entryIndex Pointer to a pre-allocated int32 that shall be set
		   to the found entry index.
	\param _entry Pointer to a pre-allocated DirEntry pointer that shall be set
		   to the found entry. May be \c NULL.
	\return \c B_OK, if everything went fine, \c B_ENTRY_NOT_FOUND, if we're
			through.
*/
status_t
DirEntryIterator::GetPrevious(DirItem *foundItem, int32 *entryIndex,
							  DirEntry **_entry)
{
//printf("DirEntryIterator::GetPrevious()\n");
	status_t error = (foundItem && entryIndex ? InitCheck() : B_BAD_VALUE);
	if (error == B_OK && fDone)
		error = B_ENTRY_NOT_FOUND;
	// get the next DirItem, if necessary
	// the loop skips empty DirItems gracefully
	while (error == B_OK
		   && (fIndex < 0 || fIndex >= fDirItem.GetEntryCount())) {
		error = fItemIterator.GetPrevious(&fDirItem, TYPE_DIRENTRY);
		if (error == B_OK) {
			if (fDirItem.Check() == B_OK)
				fIndex = fDirItem.GetEntryCount() - 1;
			else	// bad data: skip the item
				fIndex = -1;
		}
	}
//printf("  found dir item: %s\n", strerror(error));
	// skip entries with a greater offset
	while (error == B_OK && fIndex >= 0
		   && fDirItem.EntryAt(fIndex)->GetOffset() > GetOffset()) {
//printf("  skipping entry %ld: offset %lu\n", fIndex, fDirItem.EntryAt(fIndex)->GetOffset());
		fIndex--;
	}
	// get the entry and check whether it has the correct offset
	if (error == B_OK) {
//printf("  entries with greater offsets skipped: index: %ld\n", fIndex);
		if (fIndex >= 0
//&& (printf("  entry index %ld: offset %lu\n", fIndex, fDirItem.EntryAt(fIndex)->GetOffset()), true)
			&& (!fFixedHash
				|| offset_hash_value(fDirItem.EntryAt(fIndex)->GetOffset())
				   == offset_hash_value(GetOffset()))) {
//printf("  entry found\n");
			DirEntry *entry = fDirItem.EntryAt(fIndex);
			*foundItem = fDirItem;
			*entryIndex = fIndex;
			fDone = (fFixedHash
					 && offset_generation_number(entry->GetOffset()) == 0);
			if (_entry)
				*_entry = entry;
			fIndex--;
		} else
			error = B_ENTRY_NOT_FOUND;
	}
//printf("DirEntryIterator::GetPrevious() done: %s\n", strerror(error));
	return error;
}

// Suspend
/*! \brief Suspends the iterator.
	\see ObjectItemIterator::Suspend().
	\return \c B_OK, if everything went fine.
*/
status_t
DirEntryIterator::Suspend()
{
	return fItemIterator.Suspend();
}

// Resume
/*! \brief Resumes the iteration.
	\see ObjectItemIterator::Resume().
	\return \c B_OK, if everything went fine.
*/
status_t
DirEntryIterator::Resume()
{
	return fItemIterator.Resume();
}


/*!
	\class StreamReader
	\brief Class used to read object streams (files, links).
*/

// constructor
/*!	\brief Creates and initializes a StreamReader.

	The reader is initialized to read the stream of the object
	identified by \a dirID and \a objectID.

	\param tree The tree.
	\param dirID The directory ID of the object.
	\param objectID The object ID of the object.
*/
StreamReader::StreamReader(Tree *tree, uint32 dirID, uint32 objectID)
	: fItemIterator(tree, dirID, objectID, SD_OFFSET),
	  fItem(),
	  fStreamSize(-1),
	  fItemOffset(-1),
	  fItemSize(0),
	  fBlockSize(0)
{
	fBlockSize = tree->GetBlockSize();
}

// SetTo
/*!	\brief Creates and initializes a StreamReader.

	The reader is initialized to read the stream of the object
	identified by \a dirID and \a objectID.

	\param tree The tree.
	\param dirID The directory ID of the object.
	\param objectID The object ID of the object.
	\return \c B_OK, if everything went fine.
*/
status_t
StreamReader::SetTo(Tree *tree, uint32 dirID, uint32 objectID)
{
	fItem.Unset();
	status_t error = fItemIterator.SetTo(tree, dirID, objectID, SD_OFFSET);
	fStreamSize = -1;
	fItemOffset = -1;
	fItemSize = 0;
	fBlockSize = tree->GetBlockSize();
	return error;
}

// InitCheck
status_t
StreamReader::InitCheck() const
{
	return fItemIterator.InitCheck();
}

// ReadAt
/*!	\brief Tries to read the specified number of bytes from the stream into
		   the supplied buffer.
	\param position Stream position at which to start reading.
	\param buffer Pointer to a pre-allocated buffer into which the read data
		   shall be written.
	\param bufferSize Number of bytes to be read.
	\param _bytesRead Pointer to a pre-allocated size_t which shall be set to
		   the number of bytes actually read.
	\return \c B_OK, if everything went fine.
*/
status_t
StreamReader::ReadAt(off_t position, void *buffer, size_t bufferSize,
					 size_t *_bytesRead)
{
//PRINT(("StreamReader::ReadAt(%lld, %p, %lu)\n", position, buffer, bufferSize));
	status_t error = (position >= 0 && buffer && _bytesRead ? InitCheck()
															: B_BAD_VALUE);
	// get the size of the stream
	if (error == B_OK)
		error = _GetStreamSize();
	// compute the number of bytes that acually have to be read
	if (error == B_OK) {
		if (position < fStreamSize) {
			if (position + (off_t)bufferSize > fStreamSize)
				bufferSize = fStreamSize - position;
		} else
			bufferSize = 0;
	}
	// do the reading
	if (error == B_OK) {
		size_t bytesRead = 0;
		while (error == B_OK && bufferSize > 0
			   && (error = _SeekTo(position)) == B_OK) {
//PRINT(("  seeked to %lld: fItemOffset: %lld, fItemSize: %lld\n", position,
//fItemOffset, fItemSize));
			off_t inItemOffset = max_c(0LL, position - fItemOffset);
			off_t toRead = min_c(fItemSize - inItemOffset, (off_t)bufferSize);
			switch (fItem.GetType()) {
				case TYPE_INDIRECT:
					error = _ReadIndirectItem(inItemOffset, buffer, toRead);
					break;
				case TYPE_DIRECT:
					error = _ReadDirectItem(inItemOffset, buffer, toRead);
					break;
				case TYPE_STAT_DATA:
				case TYPE_DIRENTRY:
				case TYPE_ANY:
				default:
					FATAL(("Neither direct nor indirect item! type: %u\n",
						   fItem.GetType()));
					error = B_IO_ERROR;
					break;
			}
			if (error == B_OK) {
				buffer = (uint8*)buffer + toRead;
				position += toRead;
				bufferSize -= toRead;
				bytesRead += toRead;
			}
		}
		*_bytesRead = bytesRead;
	}
//if (error == B_OK)
//PRINT(("StreamReader::ReadAt() done: read: %lu bytes\n", *_bytesRead))
//else
//PRINT(("StreamReader::ReadAt() done: %s\n", strerror(error)))
	return error;
}

// Suspend
/*! \brief Suspends the reader.
	\see ObjectItemIterator::Suspend().
	\return \c B_OK, if everything went fine.
*/
status_t
StreamReader::Suspend()
{
	return fItemIterator.Suspend();
}

// Resume
/*! \brief Resumes the reader.
	\see ObjectItemIterator::Resume().
	\return \c B_OK, if everything went fine.
*/
status_t
StreamReader::Resume()
{
	return fItemIterator.Resume();
}

// _GetStreamSize
status_t
StreamReader::_GetStreamSize()
{
	status_t error = B_OK;
	if (fStreamSize < 0) {
		// get the stat item
		error = fItemIterator.GetNext(&fItem, TYPE_STAT_DATA);
		if (error == B_OK) {
			StatData statData;
			error = (static_cast<StatItem*>(&fItem))->GetStatData(&statData);
			if (error == B_OK)
				fStreamSize = statData.GetSize();
		}
	}
	return error;
}

// _SeekTo
status_t
StreamReader::_SeekTo(off_t position)
{
	status_t error = _GetStreamSize();
	if (error == B_OK && fItemOffset < 0)
		fItemOffset = 0;	// prepare for the loop
	if (error == B_OK) {
		if (2 * position < fItemOffset) {
			// seek backwards
			// since the position is closer to the beginning of the file than
			// to the current position, we simply reinit the item iterator
			// and seek forward
			error = fItemIterator.SetTo(GetTree(), GetDirID(), GetObjectID(),
										SD_OFFSET);
			fStreamSize = -1;
			fItemOffset = -1;
			fItemSize = 0;
			if (error == B_OK)
				error = _SeekTo(position);
		} else if (position < fItemOffset) {
			// seek backwards
			// iterate through the items
			while (error == B_OK && position < fItemOffset
				   && (error = fItemIterator.GetPrevious(&fItem)) == B_OK) {
				fItemSize = 0;
				switch (fItem.GetType()) {
					case TYPE_INDIRECT:
					{
						IndirectItem &indirect
							= *static_cast<IndirectItem*>(&fItem);
						// Note, that it is assumed, that the existence of a
						// next item implies, that all blocks are fully used.
						// This is safe, since otherwise we would have never
						// come to the next item.
						fItemSize = indirect.CountBlocks() * (off_t)fBlockSize;
						break;
					}
					case TYPE_DIRECT:
						// See the comment for indirect items.
						fItemSize = fItem.GetLen();
						break;
					case TYPE_STAT_DATA:
					case TYPE_DIRENTRY:
					case TYPE_ANY:
					default:
						// simply skip items of other kinds
						break;
				}
				fItemOffset -= fItemSize;
			}
		} else if (position >= fItemOffset + fItemSize) {
			// seek forward
			// iterate through the items
			while (error == B_OK && position >= fItemOffset + fItemSize
				   && (error = fItemIterator.GetNext(&fItem)) == B_OK) {
				fItemOffset += fItemSize;
				fItemSize = 0;
				switch (fItem.GetType()) {
					case TYPE_INDIRECT:
					{
						IndirectItem &indirect
							= *static_cast<IndirectItem*>(&fItem);
						fItemSize = min(indirect.CountBlocks()
											* (off_t)fBlockSize,
										fStreamSize - fItemOffset);
						break;
					}
					case TYPE_DIRECT:
						fItemSize = min((off_t)fItem.GetLen(),
										fStreamSize - fItemOffset);
						break;
					case TYPE_STAT_DATA:
					case TYPE_DIRENTRY:
					case TYPE_ANY:
					default:
						// simply skip items of other kinds
						break;
				}
			}
		}
	}
//	return error;
RETURN_ERROR(error);
}

// _ReadIndirectItem
status_t
StreamReader::_ReadIndirectItem(off_t offset, void *buffer, size_t bufferSize)
{
//PRINT(("StreamReader::_ReadIndirectItem(%lld, %p, %lu)\n", offset, buffer, bufferSize));
	status_t error = B_OK;
	IndirectItem &indirect = *static_cast<IndirectItem*>(&fItem);
	// skip items until the offset is reached
	uint32 skipItems = 0;
	if (offset > 0) {
		skipItems = uint32(offset / fBlockSize);
		skipItems = min(skipItems, indirect.CountBlocks());	// not necessary
	}
//PRINT(("  skipItems: %lu\n", skipItems));
	for (uint32 i = skipItems;
		 error == B_OK && bufferSize > 0 && i < indirect.CountBlocks();
		 i++) {
//PRINT(("    child %lu\n", i));
		// get the block
		Block *block = NULL;
		error = GetTree()->GetBlock(indirect.BlockNumberAt(i), &block);
		if (error == B_OK) {
			// copy the data into the buffer
			off_t blockOffset = i * (off_t)fBlockSize;
			uint32 localOffset = max_c(0LL, offset - blockOffset);
			uint32 toRead = min_c(fBlockSize - localOffset, bufferSize);
			memcpy(buffer,
				reinterpret_cast<uint8*>(block->GetData()) + localOffset,
				toRead);

			block->Put();
			bufferSize -= toRead;
			buffer = (uint8*)buffer + toRead;
		} else {
			FATAL(("failed to get block %" B_PRIu64 "\n",
				indirect.BlockNumberAt(i)));
			error = B_IO_ERROR;
		}
	}
//PRINT(("StreamReader::_ReadIndirectItem() done: %s\n", strerror(error)))
	return error;
}

// _ReadDirectItem
status_t
StreamReader::_ReadDirectItem(off_t offset, void *buffer, size_t bufferSize)
{
//PRINT(("StreamReader::_ReadDirectItem(%lld, %p, %lu)\n", offset, buffer, bufferSize));
	// copy the data into the buffer
	memcpy(buffer,
		reinterpret_cast<uint8*>(fItem.GetData()) + offset, bufferSize);
	return B_OK;
}