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
Tree()47 Tree::Tree()
48 : fVolume(NULL),
49 fBlockCache(NULL),
50 fRootNode(NULL),
51 fTreeHeight(0)
52 {
53 }
54
55 // destructor
~Tree()56 Tree::~Tree()
57 {
58 if (fRootNode)
59 fRootNode->Put();
60 }
61
62 // Init
63 status_t
Init(Volume * volume,Node * rootNode,uint32 treeHeight)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: %" 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
84 status_t
InitCheck() const85 Tree::InitCheck() const
86 {
87 return (fBlockCache && fRootNode && fTreeHeight ? B_OK : B_NO_INIT);
88 }
89
90 // GetTreeHeight
91 uint32
GetTreeHeight() const92 Tree::GetTreeHeight() const
93 {
94 return fTreeHeight;
95 }
96
97 // GetBlockSize
98 uint32
GetBlockSize() const99 Tree::GetBlockSize() const
100 {
101 if (fBlockCache)
102 return fBlockCache->GetBlockSize();
103 return 0;
104 }
105
106
107 // GetBlockCache
108 BlockCache *
GetBlockCache() const109 Tree::GetBlockCache() const
110 {
111 return fBlockCache;
112 }
113
114 // GetRootNode
115 Node *
GetRootNode() const116 Tree::GetRootNode() const
117 {
118 return fRootNode;
119 }
120
121 // GetBlock
122 status_t
GetBlock(uint64 blockNumber,Block ** block)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
GetNode(uint64 blockNumber,Node ** node)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
FindDirEntry(uint32 dirID,uint32 objectID,const char * name,DirItem * foundItem,int32 * entryIndex)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
FindDirEntry(uint32 dirID,uint32 objectID,const char * name,size_t nameLen,DirItem * foundItem,int32 * entryIndex)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
FindStatItem(uint32 dirID,uint32 objectID,StatItem * item)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