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 33 const 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 47 Tree::Tree() 48 : fVolume(NULL), 49 fBlockCache(NULL), 50 fRootNode(NULL), 51 fTreeHeight(0) 52 { 53 } 54 55 // destructor 56 Tree::~Tree() 57 { 58 if (fRootNode) 59 fRootNode->Put(); 60 } 61 62 // Init 63 status_t 64 Tree::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: %lu\n", 72 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 84 status_t 85 Tree::InitCheck() const 86 { 87 return (fBlockCache && fRootNode && fTreeHeight ? B_OK : B_NO_INIT); 88 } 89 90 // GetTreeHeight 91 uint32 92 Tree::GetTreeHeight() const 93 { 94 return fTreeHeight; 95 } 96 97 // GetBlockSize 98 uint32 99 Tree::GetBlockSize() const 100 { 101 if (fBlockCache) 102 return fBlockCache->GetBlockSize(); 103 return 0; 104 } 105 106 107 // GetBlockCache 108 BlockCache * 109 Tree::GetBlockCache() const 110 { 111 return fBlockCache; 112 } 113 114 // GetRootNode 115 Node * 116 Tree::GetRootNode() const 117 { 118 return fRootNode; 119 } 120 121 // GetBlock 122 status_t 123 Tree::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 132 status_t 133 Tree::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 165 status_t 166 Tree::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 179 status_t 180 Tree::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 235 status_t 236 Tree::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