haiku.git

// Tree.cpp
//
// Copyright (c) 2003, 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 <stdio.h>

#include "Tree.h"
#include "Block.h"
#include "BlockCache.h"
#include "Debug.h"
#include "DirItem.h"
#include "Iterators.h"
#include "StatItem.h"
#include "Volume.h"

const uint32 kMaxTreeHeight = 5;

/*!
	\class Tree
	\brief Represents the on-disk S+Tree.

	This class actually doesn't have that much functionality. GetBlock()
	and GetNode() are used to request a block/tree node from disk,
	FindDirEntry() searches an entry in a directory and FindStatItem()
	gets the stat data for an object. The mammoth part of the code is
	located in the iterator code (Iterators.{cpp,h}).
*/

// constructor
Tree::Tree()
	: fVolume(NULL),
	  fBlockCache(NULL),
	  fRootNode(NULL),
	  fTreeHeight(0)
{
}

// destructor
Tree::~Tree()
{
	if (fRootNode)
		fRootNode->Put();
}

// Init
status_t
Tree::Init(Volume *volume, Node *rootNode, uint32 treeHeight)
{
	status_t error = (volume && volume->GetBlockCache() && rootNode
					  ? B_OK : B_BAD_VALUE);
	if (error == B_OK) {
		if (treeHeight > kMaxTreeHeight) {
			// we don't need to fail, as we can deal with that gracefully
			INFORM(("WARNING: tree height greater maximal height: %" B_PRIu32
				"\n", treeHeight));
		}
		fVolume = volume;
		fBlockCache = fVolume->GetBlockCache();
		fRootNode = rootNode;
		fRootNode->Get();
		fTreeHeight = treeHeight;
	}
	return error;
}

// InitCheck
status_t
Tree::InitCheck() const
{
	return (fBlockCache && fRootNode && fTreeHeight ? B_OK : B_NO_INIT);
}

// GetTreeHeight
uint32
Tree::GetTreeHeight() const
{
	return fTreeHeight;
}

// GetBlockSize
uint32
Tree::GetBlockSize() const
{
	if (fBlockCache)
		return fBlockCache->GetBlockSize();
	return 0;
}


// GetBlockCache
BlockCache *
Tree::GetBlockCache() const
{
	return fBlockCache;
}

// GetRootNode
Node *
Tree::GetRootNode() const
{
	return fRootNode;
}

// GetBlock
status_t
Tree::GetBlock(uint64 blockNumber, Block **block)
{
	status_t error = (block ? InitCheck() : B_BAD_VALUE);
	if (error == B_OK)
		error = fBlockCache->GetBlock(blockNumber, block);
	return error;
}

// GetNode
status_t
Tree::GetNode(uint64 blockNumber, Node **node)
{
	status_t error = (node ? InitCheck() : B_BAD_VALUE);
	if (error == B_OK) {
		Block *block;
		error = fBlockCache->GetBlock(blockNumber, &block);
		if (error == B_OK) {
			if (block->GetKind() == Block::KIND_UNKNOWN)
				block->SetKind(Block::KIND_FORMATTED);
			if (block->GetKind() == Block::KIND_FORMATTED) {
				*node = block->ToNode();
				// check the node
				if (!(*node)->IsChecked()) {
					if ((*node)->IsInternal())
						error = (*node)->ToInternalNode()->Check();
					else if ((*node)->IsLeaf())
						error = (*node)->ToLeafNode()->Check();
					else
						error = B_BAD_DATA;
					if (error == B_OK)
						(*node)->SetChecked(true);
				}
			} else {
				block->Put();
				error = B_BAD_DATA;
			}
		}
	}
	return error;
}

// FindDirEntry
status_t
Tree::FindDirEntry(uint32 dirID, uint32 objectID, const char *name,
				   DirItem *foundItem, int32 *entryIndex)
{
	status_t error = (name && foundItem && entryIndex ? InitCheck()
													  : B_BAD_VALUE);
	if (error == B_OK) {
		error = FindDirEntry(dirID, objectID, name, strlen(name), foundItem,
							 entryIndex);
	}
	return error;
}

// FindDirEntry
status_t
Tree::FindDirEntry(uint32 dirID, uint32 objectID, const char *name,
				   size_t nameLen, DirItem *foundItem, int32 *entryIndex)
{
	status_t error = (name && foundItem && entryIndex ? InitCheck()
													  : B_BAD_VALUE);
	if (error == B_OK) {
		uint64 offset = 0;
		if (fVolume->GetKeyOffsetForName(name, nameLen, &offset) == B_OK) {
//PRINT(("Tree::FindDirEntry(): hash function: offset: %Lu (`%.*s', %lu)\n",
//offset, (int)nameLen, name, nameLen));
			// offset computed -- we can directly iterate only over entries
			// with that offset
			DirEntryIterator iterator(this, dirID, objectID, offset, true);
			DirItem dirItem;
			int32 index = 0;
			error = B_ENTRY_NOT_FOUND;
			while (iterator.GetPrevious(&dirItem, &index) == B_OK) {
				size_t itemNameLen = 0;
				if (const char *itemName
					= dirItem.EntryNameAt(index, &itemNameLen)) {
					if (itemNameLen == nameLen
						&& !strncmp(name, itemName, nameLen)) {
						// item found
						*foundItem = dirItem;
						*entryIndex = index;
						error = B_OK;
						break;
					}
				}
			}
		} else {
//PRINT(("Tree::FindDirEntry(): no hash function\n"));
			// no offset (no hash function) -- do it the slow way
			ObjectItemIterator iterator(this, dirID, objectID);
			DirItem dirItem;
			error = B_ENTRY_NOT_FOUND;
			while (iterator.GetNext(&dirItem, TYPE_DIRENTRY) == B_OK) {
				if (dirItem.Check() != B_OK) // bad data: skip item
					continue;
				int32 index = dirItem.IndexOfName(name);
				if (index >= 0) {
					// item found
					*foundItem = dirItem;
					*entryIndex = index;
					error = B_OK;
//PRINT(("  offset: %lu\n", dirItem.EntryAt(index)->GetOffset()));
					break;
				}
			}
		}
	}
	return error;
}

// FindStatItem
status_t
Tree::FindStatItem(uint32 dirID, uint32 objectID, StatItem *item)
{
	status_t error = (item ? InitCheck() : B_BAD_VALUE);
	if (error == B_OK) {
		ItemIterator iterator(this);
		error = iterator.InitCheck();
		VKey k(dirID, objectID, SD_OFFSET, V1_SD_UNIQUENESS, KEY_FORMAT_3_5);
		if (error == B_OK)
			error = iterator.FindRightMost(&k, item);
	}
	return error;
}