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 %" 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 * 298 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 * 313 InternalNode::GetKeys() const 314 { 315 return (const Key*)((uint8*)fData + sizeof(block_head)); 316 } 317 318 // KeyAt 319 const Key * 320 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 * 330 InternalNode::GetChilds() const 331 { 332 return (DiskChild*)(GetKeys() + CountItems()); 333 } 334 335 // ChildAt 336 const DiskChild * 337 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 347 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 * 376 LeafNode::GetItemHeaders() const 377 { 378 return (ItemHeader*)((uint8*)fData + sizeof(block_head)); 379 } 380 381 // ItemHeaderAt 382 const ItemHeader * 383 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 393 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 407 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 421 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 441 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