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 447