1 // Block.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 "Block.h"
23
24 #include <stdlib.h>
25
26 //#include <fs_cache.h>
27
28 #include "BlockCache.h"
29 #include "Item.h"
30 #include "Key.h"
31
32 /*!
33 \class Block
34 \brief Represents a cached disk block.
35
36 A block can either be formatted, i.e. a node in the S+Tree, or
37 unformatted containing raw data. When formatted, it can be converted to
38 a Node via the ToNode() method.
39 */
40
41 // constructor
Block()42 Block::Block()
43 : fCache(NULL),
44 fNumber(0),
45 fData(NULL),
46 fFlags(KIND_UNKNOWN),
47 fRefCount(0)
48 {
49 }
50
51 // destructor
~Block()52 Block::~Block()
53 {
54 _Unset();
55 }
56
57 // GetCache
58 BlockCache *
GetCache() const59 Block::GetCache() const
60 {
61 return fCache;
62 }
63
64 // GetBlockSize
65 uint32
GetBlockSize() const66 Block::GetBlockSize() const
67 {
68 return fCache->GetBlockSize();
69 }
70
71 // Get
72 void
Get()73 Block::Get()
74 {
75 if (fCache)
76 fCache->GetBlock(this);
77 }
78
79 // Put
80 void
Put()81 Block::Put()
82 {
83 if (fCache)
84 fCache->PutBlock(this);
85 }
86
87 // GetNumber
88 uint64
GetNumber() const89 Block::GetNumber() const
90 {
91 return fNumber;
92 }
93
94 // GetData
95 void *
GetData() const96 Block::GetData() const
97 {
98 return fData;
99 }
100
101 // SetKind
102 void
SetKind(uint32 kind)103 Block::SetKind(uint32 kind)
104 {
105 fFlags = (fFlags & ~(uint32)KIND_MASK) | (kind & KIND_MASK);
106 }
107
108 // SetChecked
109 void
SetChecked(bool checked)110 Block::SetChecked(bool checked)
111 {
112 if (checked)
113 fFlags |= CHECKED;
114 else
115 fFlags &= ~(uint32)CHECKED;
116 }
117
118 // ToNode
119 Node *
ToNode()120 Block::ToNode()
121 {
122 Node *node = NULL;
123 if (IsFormatted())
124 node = static_cast<Node*>(this);
125 return node;
126 }
127
128 // ToInternalNode
129 InternalNode *
ToInternalNode()130 Block::ToInternalNode()
131 {
132 InternalNode *internalNode = NULL;
133 if (Node *node = ToNode()) {
134 if (node->IsInternal())
135 internalNode = static_cast<InternalNode*>(node);
136 }
137 return internalNode;
138 }
139
140 // ToLeafNode
141 LeafNode *
ToLeafNode()142 Block::ToLeafNode()
143 {
144 LeafNode *leafNode = NULL;
145 if (Node *node = ToNode()) {
146 if (node->IsLeaf())
147 leafNode = static_cast<LeafNode*>(node);
148 }
149 return leafNode;
150 }
151
152 // IsFormatted
153 bool
IsFormatted() const154 Block::IsFormatted() const
155 {
156 return (GetKind() == KIND_FORMATTED);
157 }
158
159 // IsLeaf
160 bool
IsLeaf() const161 Block::IsLeaf() const
162 {
163 if (Node *node = const_cast<Block*>(this)->ToNode())
164 return node->IsLeaf();
165 return false;
166 }
167
168 // IsInternal
169 bool
IsInternal() const170 Block::IsInternal() const
171 {
172 if (Node *node = const_cast<Block*>(this)->ToNode())
173 return node->IsInternal();
174 return false;
175 }
176
177 // _SetTo
178 status_t
_SetTo(BlockCache * cache,uint64 number)179 Block::_SetTo(BlockCache *cache, uint64 number)
180 {
181 // unset
182 _Unset();
183 status_t error = (cache ? B_OK : B_BAD_VALUE);
184 // set to new values
185 fCache = cache;
186 fNumber = number;
187 if (error == B_OK) {
188 fData = fCache->_GetBlock(fNumber);
189 if (!fData)
190 error = B_BAD_VALUE;
191 }
192 return error;
193 }
194
195 // _Unset
196 void
_Unset()197 Block::_Unset()
198 {
199 if (fCache && fData)
200 fCache->_ReleaseBlock(fNumber, fData);
201 fData = NULL;
202 fCache = NULL;
203 fNumber = 0;
204 fData = NULL;
205 fFlags = KIND_UNKNOWN;
206 fRefCount = 0;
207 }
208
209 // _Get
210 void
_Get()211 Block::_Get()
212 {
213 fRefCount++;
214 }
215
216 // _Put
217 bool
_Put()218 Block::_Put()
219 {
220 return (--fRefCount == 0);
221 }
222
223
224 /*!
225 \class Node
226 \brief Represents a formatted cached disk block.
227
228 A Node can be converted to an InternalNode or LeafNode, depending on
229 its kind. Leaf nodes are located at level 1 only.
230 */
231
232 // dummy constructor
Node()233 Node::Node()
234 : Block()
235 {
236 }
237
238 // GetLevel
239 uint16
GetLevel() const240 Node::GetLevel() const
241 {
242 return le2h(GetHeader()->blk_level);
243 }
244
245 // CountItems
246 /*! \brief Returns the number of child "items" the node contains/refers to.
247
248 If the node is a leaf node, this number is indeed the number of the
249 items it contains. For internal node it is the number of keys, as oposed
250 to the number of child nodes, which is CountItems() + 1.
251
252 \return The number of child "items" the node contains/refers to.
253 */
254 uint16
CountItems() const255 Node::CountItems() const
256 {
257 return le2h(GetHeader()->blk_nr_item);
258 }
259
260 // FreeSpace
261 uint16
GetFreeSpace() const262 Node::GetFreeSpace() const
263 {
264 return le2h(GetHeader()->blk_free_space);
265 }
266
267 // IsLeaf
268 bool
IsLeaf() const269 Node::IsLeaf() const
270 {
271 return (GetLevel() == 1);
272 }
273
274 // IsInternal
275 bool
IsInternal() const276 Node::IsInternal() const
277 {
278 return (GetLevel() > 1);
279 }
280
281 // Check
282 status_t
Check() const283 Node::Check() const
284 {
285 // check the minimal size of the node against its declared free space
286 if (GetFreeSpace() + sizeof(block_head) > GetBlockSize()) {
287 FATAL(("WARNING: bad node %" B_PRIu64
288 ": it declares more free space than "
289 "possibly being available (%u vs %lu)!\n", GetNumber(),
290 GetFreeSpace(), GetBlockSize() - sizeof(block_head)));
291 return B_BAD_DATA;
292 }
293 return B_OK;
294 }
295
296 // GetHeader
297 block_head *
GetHeader() const298 Node::GetHeader() const
299 {
300 return (block_head*)fData;
301 }
302
303
304 /*!
305 \class InternalNode
306 \brief Represents an internal tree node.
307
308 Internal tree node refer to its child nodes via DiskChilds.
309 */
310
311 // GetKeys
312 const Key *
GetKeys() const313 InternalNode::GetKeys() const
314 {
315 return (const Key*)((uint8*)fData + sizeof(block_head));
316 }
317
318 // KeyAt
319 const Key *
KeyAt(int32 index) const320 InternalNode::KeyAt(int32 index) const
321 {
322 const Key *k = NULL;
323 if (index >= 0 && index < CountItems())
324 k = GetKeys() + index;
325 return k;
326 }
327
328 // GetChilds
329 const DiskChild *
GetChilds() const330 InternalNode::GetChilds() const
331 {
332 return (DiskChild*)(GetKeys() + CountItems());
333 }
334
335 // ChildAt
336 const DiskChild *
ChildAt(int32 index) const337 InternalNode::ChildAt(int32 index) const
338 {
339 const DiskChild *child = NULL;
340 if (index >= 0 && index <= CountItems())
341 child = GetChilds() + index;
342 return child;
343 }
344
345 // Check
346 status_t
Check() const347 InternalNode::Check() const
348 {
349 // check the minimal size of the node against its declared free space
350 // Note: This test is stricter than the that of the base class, so we
351 // don't need to invoke it.
352 uint32 size = (const uint8*)(GetChilds() + (CountItems() + 1))
353 - (const uint8*)GetData();
354 if (size + GetFreeSpace() > GetBlockSize()) {
355 FATAL(("WARNING: bad internal node %" B_PRIu64
356 ": it declares more free space "
357 "than possibly being available (size: %" B_PRIu32 ", "
358 "block size: %" B_PRIu32 ", "
359 "free space: %u)!\n", GetNumber(), size, GetBlockSize(),
360 GetFreeSpace()));
361 return B_BAD_DATA;
362 }
363 return B_OK;
364 }
365
366
367 /*!
368 \class LeafNode
369 \brief Represents an tree leaf node.
370
371 Leaf nodes contain items.
372 */
373
374 // GetItemHeaders
375 const ItemHeader *
GetItemHeaders() const376 LeafNode::GetItemHeaders() const
377 {
378 return (ItemHeader*)((uint8*)fData + sizeof(block_head));
379 }
380
381 // ItemHeaderAt
382 const ItemHeader *
ItemHeaderAt(int32 index) const383 LeafNode::ItemHeaderAt(int32 index) const
384 {
385 const ItemHeader *header = NULL;
386 if (index >= 0 && index < CountItems())
387 header = GetItemHeaders() + index;
388 return header;
389 }
390
391 // GetLeftKey
392 status_t
GetLeftKey(VKey * k) const393 LeafNode::GetLeftKey(VKey *k) const
394 {
395 status_t error = (k ? B_OK : B_BAD_VALUE);
396 if (error == B_OK) {
397 if (const ItemHeader *header = ItemHeaderAt(0))
398 header->GetKey(k);
399 else
400 error = B_ERROR;
401 }
402 return error;
403 }
404
405 // GetRightKey
406 status_t
GetRightKey(VKey * k) const407 LeafNode::GetRightKey(VKey *k) const
408 {
409 status_t error = (k ? B_OK : B_BAD_VALUE);
410 if (error == B_OK) {
411 if (const ItemHeader *header = ItemHeaderAt(CountItems() - 1))
412 header->GetKey(k);
413 else
414 error = B_ERROR;
415 }
416 return error;
417 }
418
419 // Check
420 status_t
Check() const421 LeafNode::Check() const
422 {
423 // check the minimal size of the node against its declared free space
424 // Note: This test is stricter than the that of the base class, so we
425 // don't need to invoke it.
426 uint32 size = GetItemSpaceOffset();
427 if (size + GetFreeSpace() > GetBlockSize()) {
428 FATAL(("WARNING: bad leaf node %" B_PRIu64
429 ": it declares more free space "
430 "than possibly being available "
431 "(min size: %" B_PRIu32 ", block size: "
432 "%" B_PRIu32 ", free space: %u)!\n",
433 GetNumber(), size, GetBlockSize(), GetFreeSpace()));
434 return B_BAD_DATA;
435 }
436 return B_OK;
437 }
438
439 // GetItemSpaceOffset
440 uint32
GetItemSpaceOffset() const441 LeafNode::GetItemSpaceOffset() const
442 {
443 return sizeof(ItemHeader) * CountItems() + sizeof(block_head);
444 }
445
446
447 /*!
448 \class DiskChild
449 \brief A structure referring to a child node of an internal node.
450 */
451
452