1// Tree.cpp
2//
3// Copyright (c) 2003, Ingo Weinhold (bonefish@cs.tu-berlin.de)
4//
5// This program is free software; you can redistribute it and/or modify
6// it under the terms of the GNU General Public License as published by
7// the Free Software Foundation; either version 2 of the License, or
8// (at your option) any later version.
9//
10// This program is distributed in the hope that it will be useful,
11// but WITHOUT ANY WARRANTY; without even the implied warranty of
12// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13// GNU General Public License for more details.
14//
15// You should have received a copy of the GNU General Public License
16// along with this program; if not, write to the Free Software
17// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
18//
19// You can alternatively use *this file* under the terms of the the MIT
20// license included in this package.
21
22#include <stdio.h>
23
24#include "Tree.h"
25#include "Block.h"
26#include "BlockCache.h"
27#include "Debug.h"
28#include "DirItem.h"
29#include "Iterators.h"
30#include "StatItem.h"
31#include "Volume.h"
32
33const uint32 kMaxTreeHeight = 5;
34
35/*!
36	\class Tree
37	\brief Represents the on-disk S+Tree.
38
39	This class actually doesn't have that much functionality. GetBlock()
40	and GetNode() are used to request a block/tree node from disk,
41	FindDirEntry() searches an entry in a directory and FindStatItem()
42	gets the stat data for an object. The mammoth part of the code is
43	located in the iterator code (Iterators.{cpp,h}).
44*/
45
46// constructor
47Tree::Tree()
48	: fVolume(NULL),
49	  fBlockCache(NULL),
50	  fRootNode(NULL),
51	  fTreeHeight(0)
52{
53}
54
55// destructor
56Tree::~Tree()
57{
58	if (fRootNode)
59		fRootNode->Put();
60}
61
62// Init
63status_t
64Tree::Init(Volume *volume, Node *rootNode, uint32 treeHeight)
65{
66	status_t error = (volume && volume->GetBlockCache() && rootNode
67					  ? B_OK : B_BAD_VALUE);
68	if (error == B_OK) {
69		if (treeHeight > kMaxTreeHeight) {
70			// we don't need to fail, as we can deal with that gracefully
71			INFORM(("WARNING: tree height greater maximal height: %" B_PRIu32
72				"\n", treeHeight));
73		}
74		fVolume = volume;
75		fBlockCache = fVolume->GetBlockCache();
76		fRootNode = rootNode;
77		fRootNode->Get();
78		fTreeHeight = treeHeight;
79	}
80	return error;
81}
82
83// InitCheck
84status_t
85Tree::InitCheck() const
86{
87	return (fBlockCache && fRootNode && fTreeHeight ? B_OK : B_NO_INIT);
88}
89
90// GetTreeHeight
91uint32
92Tree::GetTreeHeight() const
93{
94	return fTreeHeight;
95}
96
97// GetBlockSize
98uint32
99Tree::GetBlockSize() const
100{
101	if (fBlockCache)
102		return fBlockCache->GetBlockSize();
103	return 0;
104}
105
106
107// GetBlockCache
108BlockCache *
109Tree::GetBlockCache() const
110{
111	return fBlockCache;
112}
113
114// GetRootNode
115Node *
116Tree::GetRootNode() const
117{
118	return fRootNode;
119}
120
121// GetBlock
122status_t
123Tree::GetBlock(uint64 blockNumber, Block **block)
124{
125	status_t error = (block ? InitCheck() : B_BAD_VALUE);
126	if (error == B_OK)
127		error = fBlockCache->GetBlock(blockNumber, block);
128	return error;
129}
130
131// GetNode
132status_t
133Tree::GetNode(uint64 blockNumber, Node **node)
134{
135	status_t error = (node ? InitCheck() : B_BAD_VALUE);
136	if (error == B_OK) {
137		Block *block;
138		error = fBlockCache->GetBlock(blockNumber, &block);
139		if (error == B_OK) {
140			if (block->GetKind() == Block::KIND_UNKNOWN)
141				block->SetKind(Block::KIND_FORMATTED);
142			if (block->GetKind() == Block::KIND_FORMATTED) {
143				*node = block->ToNode();
144				// check the node
145				if (!(*node)->IsChecked()) {
146					if ((*node)->IsInternal())
147						error = (*node)->ToInternalNode()->Check();
148					else if ((*node)->IsLeaf())
149						error = (*node)->ToLeafNode()->Check();
150					else
151						error = B_BAD_DATA;
152					if (error == B_OK)
153						(*node)->SetChecked(true);
154				}
155			} else {
156				block->Put();
157				error = B_BAD_DATA;
158			}
159		}
160	}
161	return error;
162}
163
164// FindDirEntry
165status_t
166Tree::FindDirEntry(uint32 dirID, uint32 objectID, const char *name,
167				   DirItem *foundItem, int32 *entryIndex)
168{
169	status_t error = (name && foundItem && entryIndex ? InitCheck()
170													  : B_BAD_VALUE);
171	if (error == B_OK) {
172		error = FindDirEntry(dirID, objectID, name, strlen(name), foundItem,
173							 entryIndex);
174	}
175	return error;
176}
177
178// FindDirEntry
179status_t
180Tree::FindDirEntry(uint32 dirID, uint32 objectID, const char *name,
181				   size_t nameLen, DirItem *foundItem, int32 *entryIndex)
182{
183	status_t error = (name && foundItem && entryIndex ? InitCheck()
184													  : B_BAD_VALUE);
185	if (error == B_OK) {
186		uint64 offset = 0;
187		if (fVolume->GetKeyOffsetForName(name, nameLen, &offset) == B_OK) {
188//PRINT(("Tree::FindDirEntry(): hash function: offset: %Lu (`%.*s', %lu)\n",
189//offset, (int)nameLen, name, nameLen));
190			// offset computed -- we can directly iterate only over entries
191			// with that offset
192			DirEntryIterator iterator(this, dirID, objectID, offset, true);
193			DirItem dirItem;
194			int32 index = 0;
195			error = B_ENTRY_NOT_FOUND;
196			while (iterator.GetPrevious(&dirItem, &index) == B_OK) {
197				size_t itemNameLen = 0;
198				if (const char *itemName
199					= dirItem.EntryNameAt(index, &itemNameLen)) {
200					if (itemNameLen == nameLen
201						&& !strncmp(name, itemName, nameLen)) {
202						// item found
203						*foundItem = dirItem;
204						*entryIndex = index;
205						error = B_OK;
206						break;
207					}
208				}
209			}
210		} else {
211//PRINT(("Tree::FindDirEntry(): no hash function\n"));
212			// no offset (no hash function) -- do it the slow way
213			ObjectItemIterator iterator(this, dirID, objectID);
214			DirItem dirItem;
215			error = B_ENTRY_NOT_FOUND;
216			while (iterator.GetNext(&dirItem, TYPE_DIRENTRY) == B_OK) {
217				if (dirItem.Check() != B_OK) // bad data: skip item
218					continue;
219				int32 index = dirItem.IndexOfName(name);
220				if (index >= 0) {
221					// item found
222					*foundItem = dirItem;
223					*entryIndex = index;
224					error = B_OK;
225//PRINT(("  offset: %lu\n", dirItem.EntryAt(index)->GetOffset()));
226					break;
227				}
228			}
229		}
230	}
231	return error;
232}
233
234// FindStatItem
235status_t
236Tree::FindStatItem(uint32 dirID, uint32 objectID, StatItem *item)
237{
238	status_t error = (item ? InitCheck() : B_BAD_VALUE);
239	if (error == B_OK) {
240		ItemIterator iterator(this);
241		error = iterator.InitCheck();
242		VKey k(dirID, objectID, SD_OFFSET, V1_SD_UNIQUENESS, KEY_FORMAT_3_5);
243		if (error == B_OK)
244			error = iterator.FindRightMost(&k, item);
245	}
246	return error;
247}
248
249