text: // Block.cpp
  //
  // Copyright (c) 2003, Ingo Weinhold (bonefish@cs.tu-berlin.de)
  //
  // This program is free software; you can redistribute it and/or modify
  // it under the terms of the GNU General Public License as published by
  // the Free Software Foundation; either version 2 of the License, or
  // (at your option) any later version.
  // 
  // This program is distributed in the hope that it will be useful,
  // but WITHOUT ANY WARRANTY; without even the implied warranty of
  // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  // GNU General Public License for more details.
  // 
  // You should have received a copy of the GNU General Public License
  // along with this program; if not, write to the Free Software
  // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  //
  // You can alternatively use *this file* under the terms of the the MIT
  // license included in this package.
  
  #include <stdlib.h>
  
  #include "Block.h"
  #include "BlockCache.h"
  #include "cache.h"
  #include "Item.h"
  #include "Key.h"
  
  /*!
  	\class Block
  	\brief Represents a cached disk block.
  
  	A block can either be formatted, i.e. a node in the S+Tree, or
  	unformatted containing raw data. When formatted, it can be converted to
  	a Node via the ToNode() method.
  */
  
  // constructor
  Block::Block()
  	: fCache(NULL),
  	  fNumber(0),
  	  fData(NULL),
  	  fFlags(KIND_UNKNOWN),
  	  fRefCount(0),
  	  fAge(-1)
  {
  }
  
  // destructor
  Block::~Block()
  {
  	_Unset();
  }
  
  // GetCache
  BlockCache *
  Block::GetCache() const
  {
  	return fCache;
  }
  
  // GetBlockSize
  uint32
  Block::GetBlockSize() const
  {
  	return fCache->GetBlockSize();
  }
  
  // Get
  void
  Block::Get()
  {
  	if (fCache)
  		fCache->GetBlock(this);
  }
  
  // Put
  void
  Block::Put()
  {
  	if (fCache)
  		fCache->PutBlock(this);
  }
  
  // GetNumber
  uint64
  Block::GetNumber() const
  {
  	return fNumber;
  }
  
  // GetData
  void *
  Block::GetData() const
  {
  	return fData;
  }
  
  // SetKind
  void
  Block::SetKind(uint32 kind)
  {
  	fFlags = fFlags & ~(uint32)KIND_MASK | kind & KIND_MASK;
  }
  
  // SetChecked
  void
  Block::SetChecked(bool checked)
  {
  	if (checked)
  		fFlags |= CHECKED;
  	else
  		fFlags &= ~(uint32)CHECKED;
  }
  
  // ToNode
  Node *
  Block::ToNode()
  {
  	Node *node = NULL;
  	if (IsFormatted())
  		node = static_cast<Node*>(this);
  	return node;
  }
  
  // ToInternalNode
  InternalNode *
  Block::ToInternalNode()
  {
  	InternalNode *internalNode = NULL;
  	if (Node *node = ToNode()) {
  		if (node->IsInternal())
  			internalNode = static_cast<InternalNode*>(node);
  	}
  	return internalNode;
  }
  
  // ToLeafNode
  LeafNode *
  Block::ToLeafNode()
  {
  	LeafNode *leafNode = NULL;
  	if (Node *node = ToNode()) {
  		if (node->IsLeaf())
  			leafNode = static_cast<LeafNode*>(node);
  	}
  	return leafNode;
  }
  
  // IsFormatted
  bool
  Block::IsFormatted() const
  {
  	return (GetKind() == KIND_FORMATTED);
  }
  
  // IsLeaf
  bool
  Block::IsLeaf() const
  {
  	if (Node *node = const_cast<Block*>(this)->ToNode())
  		return node->IsLeaf();
  	return false;
  }
  
  // IsInternal
  bool
  Block::IsInternal() const
  {
  	if (Node *node = const_cast<Block*>(this)->ToNode())
  		return node->IsInternal();
  	return false;
  }
  
  // _SetTo
  status_t
  Block::_SetTo(BlockCache *cache, uint64 number)
  {
  	// unset
  	_Unset();
  	status_t error = (cache ? B_OK : B_BAD_VALUE);
  	// set to new values
  	fCache = cache;
  	fNumber = number;
  	if (error == B_OK) {
  //		fData = get_block(fCache->GetDevice(), fNumber,
  //						  fCache->GetBlockSize());
  fData = fCache->_GetBlock(fNumber);
  		if (!fData)
  			error = B_BAD_VALUE;
  	}
  	return error;
  }
  
  // _Unset
  void
  Block::_Unset()
  {
  	if (fCache && fData)
  //		release_block(fCache->GetDevice(), fNumber);
  fCache->_ReleaseBlock(fNumber, fData);
  	fData = NULL;
  	fCache = NULL;
  	fNumber = 0;
  	fData = NULL;
  	fFlags = KIND_UNKNOWN;
  	fRefCount = 0;
  	fAge = -1;
  }
  
  // _Get
  void
  Block::_Get()
  {
  	fRefCount++;
  }
  
  // _Put
  bool
  Block::_Put()
  {
  	return (--fRefCount == 0);
  }
  
  
  /*!
  	\class Node
  	\brief Represents a formatted cached disk block.
  
  	A Node can be converted to an InternalNode or LeafNode, depending on
  	its kind. Leaf nodes are located at level 1 only.
  */
  
  // dummy constructor
  Node::Node()
  	: Block()
  {
  }
  
  // GetLevel
  uint16
  Node::GetLevel() const
  {
  	return le2h(GetHeader()->blk_level);
  }
  
  // CountItems
  /*!	\brief Returns the number of child "items" the node contains/refers to.
  
  	If the node is a leaf node, this number is indeed the number of the
  	items it contains. For internal node it is the number of keys, as oposed
  	to the number of child nodes, which is CountItems() + 1.
  
  	\return The number of child "items" the node contains/refers to.
  */
  uint16
  Node::CountItems() const
  {
  	return le2h(GetHeader()->blk_nr_item);
  }
  
  // FreeSpace
  uint16
  Node::GetFreeSpace() const
  {
  	return le2h(GetHeader()->blk_free_space);
  }
  
  // IsLeaf
  bool
  Node::IsLeaf() const
  {
  	return (GetLevel() == 1);
  }
  
  // IsInternal
  bool
  Node::IsInternal() const
  {
  	return (GetLevel() > 1);
  }
  
  // Check
  status_t
  Node::Check() const
  {
  	// check the minimal size of the node against its declared free space
  	if (GetFreeSpace() + sizeof(block_head) > GetBlockSize()) {
  		FATAL(("WARNING: bad node %Ld: it declares more free space than "
  			   "possibly being available (%u vs %lu)!\n", GetNumber(),
  			   GetFreeSpace(), GetBlockSize() - sizeof(block_head)));
  		return B_BAD_DATA;
  	}
  	return B_OK;
  }
  
  // GetHeader
  block_head *
  Node::GetHeader() const
  {
  	return (block_head*)fData;
  }
  
  
  /*!
  	\class InternalNode
  	\brief Represents an internal tree node.
  
  	Internal tree node refer to its child nodes via DiskChilds.
  */
  
  // GetKeys
  const Key *
  InternalNode::GetKeys() const
  {
  	return (const Key*)((uint8*)fData + sizeof(block_head));
  }
  
  // KeyAt
  const Key *
  InternalNode::KeyAt(int32 index) const
  {
  	const Key *k = NULL;
  	if (index >= 0 && index < CountItems())
  		k = GetKeys() + index;
  	return k;
  }
  
  // GetChilds
  const DiskChild *
  InternalNode::GetChilds() const
  {
  	return (DiskChild*)(GetKeys() + CountItems());
  }
  
  // ChildAt
  const DiskChild *
  InternalNode::ChildAt(int32 index) const
  {
  	const DiskChild *child = NULL;
  	if (index >= 0 && index <= CountItems())
  		child = GetChilds() + index;
  	return child;
  }
  
  // Check
  status_t
  InternalNode::Check() const
  {
  	// check the minimal size of the node against its declared free space
  	// Note: This test is stricter than the that of the base class, so we
  	// don't need to invoke it.
  	uint32 size = (const uint8*)(GetChilds() + (CountItems() + 1))
  				  - (const uint8*)GetData();
  	if (size + GetFreeSpace() > GetBlockSize()) {
  		FATAL(("WARNING: bad internal node %Ld: it declares more free space "
  			   "than possibly being available (size: %lu, block size: %lu, "
  			   "free space: %u)!\n", GetNumber(), size, GetBlockSize(),
  			   GetFreeSpace()));
  		return B_BAD_DATA;
  	}
  	return B_OK;
  }
  
  
  /*!
  	\class LeafNode
  	\brief Represents an tree leaf node.
  
  	Leaf nodes contain items.
  */
  
  // GetItemHeaders
  const ItemHeader *
  LeafNode::GetItemHeaders() const
  {
  	return (ItemHeader*)((uint8*)fData + sizeof(block_head));
  }
  
  // ItemHeaderAt
  const ItemHeader *
  LeafNode::ItemHeaderAt(int32 index) const
  {
  	const ItemHeader *header = NULL;
  	if (index >= 0 && index < CountItems())
  		header = GetItemHeaders() + index;
  	return header;
  }
  
  // GetLeftKey
  status_t
  LeafNode::GetLeftKey(VKey *k) const
  {
  	status_t error = (k ? B_OK : B_BAD_VALUE);
  	if (error == B_OK) {
  		if (const ItemHeader *header = ItemHeaderAt(0))
  			header->GetKey(k);
  		else
  			error = B_ERROR;
  	}
  	return error;
  }
  
  // GetRightKey
  status_t
  LeafNode::GetRightKey(VKey *k) const
  {
  	status_t error = (k ? B_OK : B_BAD_VALUE);
  	if (error == B_OK) {
  		if (const ItemHeader *header = ItemHeaderAt(CountItems() - 1))
  			header->GetKey(k);
  		else
  			error = B_ERROR;
  	}
  	return error;
  }
  
  // Check
  status_t
  LeafNode::Check() const
  {
  	// check the minimal size of the node against its declared free space
  	// Note: This test is stricter than the that of the base class, so we
  	// don't need to invoke it.
  	uint32 size = GetItemSpaceOffset();
  	if (size + GetFreeSpace() > GetBlockSize()) {
  		FATAL(("WARNING: bad leaf node %Ld: it declares more free space "
  			   "than possibly being available (min size: %lu, block size: "
  			   "%lu, free space: %u)!\n", GetNumber(), size, GetBlockSize(),
  			   GetFreeSpace()));
  		return B_BAD_DATA;
  	}
  	return B_OK;
  }
  
  // GetItemSpaceOffset
  uint32
  LeafNode::GetItemSpaceOffset() const
  {
  	return sizeof(ItemHeader) * CountItems() + sizeof(block_head);
  }
  
  
  /*!
  	\class DiskChild
  	\brief A structure referring to a child node of an internal node.
  */
  
  