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
42Block::Block()
43	: fCache(NULL),
44	  fNumber(0),
45	  fData(NULL),
46	  fFlags(KIND_UNKNOWN),
47	  fRefCount(0)
48{
49}
50
51// destructor
52Block::~Block()
53{
54	_Unset();
55}
56
57// GetCache
58BlockCache *
59Block::GetCache() const
60{
61	return fCache;
62}
63
64// GetBlockSize
65uint32
66Block::GetBlockSize() const
67{
68	return fCache->GetBlockSize();
69}
70
71// Get
72void
73Block::Get()
74{
75	if (fCache)
76		fCache->GetBlock(this);
77}
78
79// Put
80void
81Block::Put()
82{
83	if (fCache)
84		fCache->PutBlock(this);
85}
86
87// GetNumber
88uint64
89Block::GetNumber() const
90{
91	return fNumber;
92}
93
94// GetData
95void *
96Block::GetData() const
97{
98	return fData;
99}
100
101// SetKind
102void
103Block::SetKind(uint32 kind)
104{
105	fFlags = (fFlags & ~(uint32)KIND_MASK) | (kind & KIND_MASK);
106}
107
108// SetChecked
109void
110Block::SetChecked(bool checked)
111{
112	if (checked)
113		fFlags |= CHECKED;
114	else
115		fFlags &= ~(uint32)CHECKED;
116}
117
118// ToNode
119Node *
120Block::ToNode()
121{
122	Node *node = NULL;
123	if (IsFormatted())
124		node = static_cast<Node*>(this);
125	return node;
126}
127
128// ToInternalNode
129InternalNode *
130Block::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
141LeafNode *
142Block::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
153bool
154Block::IsFormatted() const
155{
156	return (GetKind() == KIND_FORMATTED);
157}
158
159// IsLeaf
160bool
161Block::IsLeaf() const
162{
163	if (Node *node = const_cast<Block*>(this)->ToNode())
164		return node->IsLeaf();
165	return false;
166}
167
168// IsInternal
169bool
170Block::IsInternal() const
171{
172	if (Node *node = const_cast<Block*>(this)->ToNode())
173		return node->IsInternal();
174	return false;
175}
176
177// _SetTo
178status_t
179Block::_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
196void
197Block::_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
210void
211Block::_Get()
212{
213	fRefCount++;
214}
215
216// _Put
217bool
218Block::_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
233Node::Node()
234	: Block()
235{
236}
237
238// GetLevel
239uint16
240Node::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*/
254uint16
255Node::CountItems() const
256{
257	return le2h(GetHeader()->blk_nr_item);
258}
259
260// FreeSpace
261uint16
262Node::GetFreeSpace() const
263{
264	return le2h(GetHeader()->blk_free_space);
265}
266
267// IsLeaf
268bool
269Node::IsLeaf() const
270{
271	return (GetLevel() == 1);
272}
273
274// IsInternal
275bool
276Node::IsInternal() const
277{
278	return (GetLevel() > 1);
279}
280
281// Check
282status_t
283Node::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
297block_head *
298Node::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
312const Key *
313InternalNode::GetKeys() const
314{
315	return (const Key*)((uint8*)fData + sizeof(block_head));
316}
317
318// KeyAt
319const Key *
320InternalNode::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
329const DiskChild *
330InternalNode::GetChilds() const
331{
332	return (DiskChild*)(GetKeys() + CountItems());
333}
334
335// ChildAt
336const DiskChild *
337InternalNode::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
346status_t
347InternalNode::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
375const ItemHeader *
376LeafNode::GetItemHeaders() const
377{
378	return (ItemHeader*)((uint8*)fData + sizeof(block_head));
379}
380
381// ItemHeaderAt
382const ItemHeader *
383LeafNode::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
392status_t
393LeafNode::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
406status_t
407LeafNode::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
420status_t
421LeafNode::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
440uint32
441LeafNode::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