src/add-ons/kernel/file_systems/reiserfs/Block.cpp

   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
  42 Block::Block()
  43         : fCache(NULL),
  44           fNumber(0),
  45           fData(NULL),
  46           fFlags(KIND_UNKNOWN),
  47           fRefCount(0)
  48 {
  49 }
  50
  51 // destructor
  52 Block::~Block()
  53 {
  54         _Unset();
  55 }
  56
  57 // GetCache
  58 BlockCache *
  59 Block::GetCache() const
  60 {
  61         return fCache;
  62 }
  63
  64 // GetBlockSize
  65 uint32
  66 Block::GetBlockSize() const
  67 {
  68         return fCache->GetBlockSize();
  69 }
  70
  71 // Get
  72 void
  73 Block::Get()
  74 {
  75         if (fCache)
  76                 fCache->GetBlock(this);
  77 }
  78
  79 // Put
  80 void
  81 Block::Put()
  82 {
  83         if (fCache)
  84                 fCache->PutBlock(this);
  85 }
  86
  87 // GetNumber
  88 uint64
  89 Block::GetNumber() const
  90 {
  91         return fNumber;
  92 }
  93
  94 // GetData
  95 void *
  96 Block::GetData() const
  97 {
  98         return fData;
  99 }
 100
 101 // SetKind
 102 void
 103 Block::SetKind(uint32 kind)
 104 {
 105         fFlags = (fFlags & ~(uint32)KIND_MASK) | (kind & KIND_MASK);
 106 }
 107
 108 // SetChecked
 109 void
 110 Block::SetChecked(bool checked)
 111 {
 112         if (checked)
 113                 fFlags |= CHECKED;
 114         else
 115                 fFlags &= ~(uint32)CHECKED;
 116 }
 117
 118 // ToNode
 119 Node *
 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 *
 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 *
 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
 154 Block::IsFormatted() const
 155 {
 156         return (GetKind() == KIND_FORMATTED);
 157 }
 158
 159 // IsLeaf
 160 bool
 161 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
 170 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
 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
 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
 211 Block::_Get()
 212 {
 213         fRefCount++;
 214 }
 215
 216 // _Put
 217 bool
 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
 233 Node::Node()
 234         : Block()
 235 {
 236 }
 237
 238 // GetLevel
 239 uint16
 240 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
 255 Node::CountItems() const
 256 {
 257         return le2h(GetHeader()->blk_nr_item);
 258 }
 259
 260 // FreeSpace
 261 uint16
 262 Node::GetFreeSpace() const
 263 {
 264         return le2h(GetHeader()->blk_free_space);
 265 }
 266
 267 // IsLeaf
 268 bool
 269 Node::IsLeaf() const
 270 {
 271         return (GetLevel() == 1);
 272 }
 273
 274 // IsInternal
 275 bool
 276 Node::IsInternal() const
 277 {
 278         return (GetLevel() > 1);
 279 }
 280
 281 // Check
 282 status_t
 283 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 %Ld: it declares more free space than "
 288                            "possibly being available (%u vs %lu)!\n", GetNumber(),
 289                            GetFreeSpace(), GetBlockSize() - sizeof(block_head)));
 290                 return B_BAD_DATA;
 291         }
 292         return B_OK;
 293 }
 294
 295 // GetHeader
 296 block_head *
 297 Node::GetHeader() const
 298 {
 299         return (block_head*)fData;
 300 }
 301
 302
 303 /*!
 304         \class InternalNode
 305         \brief Represents an internal tree node.
 306
 307         Internal tree node refer to its child nodes via DiskChilds.
 308 */
 309
 310 // GetKeys
 311 const Key *
 312 InternalNode::GetKeys() const
 313 {
 314         return (const Key*)((uint8*)fData + sizeof(block_head));
 315 }
 316
 317 // KeyAt
 318 const Key *
 319 InternalNode::KeyAt(int32 index) const
 320 {
 321         const Key *k = NULL;
 322         if (index >= 0 && index < CountItems())
 323                 k = GetKeys() + index;
 324         return k;
 325 }
 326
 327 // GetChilds
 328 const DiskChild *
 329 InternalNode::GetChilds() const
 330 {
 331         return (DiskChild*)(GetKeys() + CountItems());
 332 }
 333
 334 // ChildAt
 335 const DiskChild *
 336 InternalNode::ChildAt(int32 index) const
 337 {
 338         const DiskChild *child = NULL;
 339         if (index >= 0 && index <= CountItems())
 340                 child = GetChilds() + index;
 341         return child;
 342 }
 343
 344 // Check
 345 status_t
 346 InternalNode::Check() const
 347 {
 348         // check the minimal size of the node against its declared free space
 349         // Note: This test is stricter than the that of the base class, so we
 350         // don't need to invoke it.
 351         uint32 size = (const uint8*)(GetChilds() + (CountItems() + 1))
 352                                   - (const uint8*)GetData();
 353         if (size + GetFreeSpace() > GetBlockSize()) {
 354                 FATAL(("WARNING: bad internal node %Ld: it declares more free space "
 355                            "than possibly being available (size: %lu, block size: %lu, "
 356                            "free space: %u)!\n", GetNumber(), size, GetBlockSize(),
 357                            GetFreeSpace()));
 358                 return B_BAD_DATA;
 359         }
 360         return B_OK;
 361 }
 362
 363
 364 /*!
 365         \class LeafNode
 366         \brief Represents an tree leaf node.
 367
 368         Leaf nodes contain items.
 369 */
 370
 371 // GetItemHeaders
 372 const ItemHeader *
 373 LeafNode::GetItemHeaders() const
 374 {
 375         return (ItemHeader*)((uint8*)fData + sizeof(block_head));
 376 }
 377
 378 // ItemHeaderAt
 379 const ItemHeader *
 380 LeafNode::ItemHeaderAt(int32 index) const
 381 {
 382         const ItemHeader *header = NULL;
 383         if (index >= 0 && index < CountItems())
 384                 header = GetItemHeaders() + index;
 385         return header;
 386 }
 387
 388 // GetLeftKey
 389 status_t
 390 LeafNode::GetLeftKey(VKey *k) const
 391 {
 392         status_t error = (k ? B_OK : B_BAD_VALUE);
 393         if (error == B_OK) {
 394                 if (const ItemHeader *header = ItemHeaderAt(0))
 395                         header->GetKey(k);
 396                 else
 397                         error = B_ERROR;
 398         }
 399         return error;
 400 }
 401
 402 // GetRightKey
 403 status_t
 404 LeafNode::GetRightKey(VKey *k) const
 405 {
 406         status_t error = (k ? B_OK : B_BAD_VALUE);
 407         if (error == B_OK) {
 408                 if (const ItemHeader *header = ItemHeaderAt(CountItems() - 1))
 409                         header->GetKey(k);
 410                 else
 411                         error = B_ERROR;
 412         }
 413         return error;
 414 }
 415
 416 // Check
 417 status_t
 418 LeafNode::Check() const
 419 {
 420         // check the minimal size of the node against its declared free space
 421         // Note: This test is stricter than the that of the base class, so we
 422         // don't need to invoke it.
 423         uint32 size = GetItemSpaceOffset();
 424         if (size + GetFreeSpace() > GetBlockSize()) {
 425                 FATAL(("WARNING: bad leaf node %Ld: it declares more free space "
 426                            "than possibly being available (min size: %lu, block size: "
 427                            "%lu, free space: %u)!\n", GetNumber(), size, GetBlockSize(),
 428                            GetFreeSpace()));
 429                 return B_BAD_DATA;
 430         }
 431         return B_OK;
 432 }
 433
 434 // GetItemSpaceOffset
 435 uint32
 436 LeafNode::GetItemSpaceOffset() const
 437 {
 438         return sizeof(ItemHeader) * CountItems() + sizeof(block_head);
 439 }
 440
 441
 442 /*!
 443         \class DiskChild
 444         \brief A structure referring to a child node of an internal node.
 445 */
 446