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