src/add-ons/kernel/file_systems/btrfs/BTree.cpp

   1 /*
   2  * Copyright 2011, Jérôme Duval, korli@users.berlios.de.
   3  * Copyright 2001-2010, Axel Dörfler, axeld@pinc-software.de.
   4  * This file may be used under the terms of the MIT License.
   5  */
   6
   7
   8 //! BTree implementation
   9
  10
  11 #include "BTree.h"
  12
  13
  14 //#define TRACE_BTRFS
  15 #ifdef TRACE_BTRFS
  16 #       define TRACE(x...) dprintf("\33[34mbtrfs:\33[0m " x)
  17 #else
  18 #       define TRACE(x...) ;
  19 #endif
  20 #       define ERROR(x...) dprintf("\33[34mbtrfs:\33[0m " x)
  21
  22
  23 BTree::Node::Node(Volume* volume)
  24         :
  25         fNode(NULL),
  26         fVolume(volume),
  27         fBlockNumber(0),
  28         fWritable(false)
  29 {
  30 }
  31
  32
  33 BTree::Node::Node(Volume* volume, off_t block)
  34         :
  35         fNode(NULL),
  36         fVolume(volume),
  37         fBlockNumber(0),
  38         fWritable(false)
  39 {
  40         SetTo(block);
  41 }
  42
  43
  44 BTree::Node::~Node()
  45 {
  46         Unset();
  47 }
  48
  49
  50 void
  51 BTree::Node::Keep()
  52 {
  53         fNode = NULL;
  54 }
  55
  56 void
  57 BTree::Node::Unset()
  58 {
  59         if (fNode != NULL) {
  60                 block_cache_put(fVolume->BlockCache(), fBlockNumber);
  61                 fNode = NULL;
  62         }
  63 }
  64
  65
  66 void
  67 BTree::Node::SetTo(off_t block)
  68 {
  69         Unset();
  70         fBlockNumber = block;
  71         fNode = (btrfs_stream*)block_cache_get(fVolume->BlockCache(), block);
  72 }
  73
  74
  75 void
  76 BTree::Node::SetToWritable(off_t block, int32 transactionId, bool empty)
  77 {
  78         Unset();
  79         fBlockNumber = block;
  80         fWritable = true;
  81         if (empty) {
  82                 fNode = (btrfs_stream*)block_cache_get_empty(fVolume->BlockCache(),
  83                         block, transactionId);
  84         } else {
  85                 fNode = (btrfs_stream*)block_cache_get_writable(fVolume->BlockCache(),
  86                         block, transactionId);
  87         }
  88 }
  89
  90
  91 status_t
  92 BTree::Node::SearchSlot(const btrfs_key& key, int* slot, btree_traversing type)
  93         const
  94 {
  95         //binary search for item slot in a node
  96         int entrySize = sizeof(btrfs_entry);
  97         if (Level() != 0) {
  98                 // internal node
  99                 entrySize = sizeof(btrfs_index);
 100         }
 101
 102         int high = ItemCount();
 103         int low = 0, mid = 0, comp = 0;
 104         uint8* base = (uint8*)fNode + sizeof(btrfs_header);
 105         const btrfs_key* other;
 106         while (low < high) {
 107                 mid = (low + high) / 2;
 108                 other = (const btrfs_key*)(base + mid * entrySize);
 109                 comp = key.Compare(*other);
 110                 if (comp < 0)
 111                         high = mid;
 112                 else if (comp > 0)
 113                         low = mid + 1;
 114                 else {
 115                         *slot = mid;
 116                         return B_OK;            //if key is in node
 117                 }
 118         }
 119
 120         // |--item1--|--item2--|--item3--|--etc--|
 121         //     m-1        m        m+1
 122         //           k                          : comp < 0
 123         //                     k                : comp > 0
 124         if (type == BTREE_BACKWARD) {
 125                 *slot = mid - 1;
 126                 if (comp > 0)
 127                         *slot = mid;
 128         } else if (type == BTREE_FORWARD) {
 129                 *slot = mid;
 130                 if (comp > 0)
 131                         *slot = mid + 1;
 132         }
 133
 134         if (type == BTREE_EXACT || *slot < 0)
 135                 return B_ENTRY_NOT_FOUND;
 136
 137         TRACE("SearchSlot() found slot %" B_PRId32 " comp %" B_PRId32 "\n",
 138                 *slot, comp);
 139         return B_OK;
 140 }
 141
 142
 143 /*
 144  * calculate used space except the header.
 145  * type is only for leaf node
 146  * type 1: only item space
 147  * type 2: only item data space
 148  * type 3: both type 1 and 2
 149  */
 150 int
 151 BTree::Node::_CalculateSpace(uint32 from, uint32 to, uint8 type) const
 152 {
 153         if (to < from || to >= ItemCount())
 154                 return 0;
 155
 156         if (Level() != 0)
 157                 return sizeof(btrfs_index) * (to - from + 1);
 158
 159         uint32 result = 0;
 160         if ((type & 1) == 1) {
 161                 result += sizeof(btrfs_entry) * (to - from + 1);
 162         }
 163         if ((type & 2) == 2) {
 164                 result += Item(from)->Offset() + Item(from)->Size()
 165                         - Item(to)->Offset();
 166         }
 167
 168         return result;
 169 }
 170
 171
 172 int
 173 BTree::Node::SpaceUsed() const
 174 {
 175         if (Level() == 0)
 176                 return _CalculateSpace(0, ItemCount() - 1, 3);
 177         return _CalculateSpace(0, ItemCount() - 1, 0);
 178 }
 179
 180
 181 int
 182 BTree::Node::SpaceLeft() const
 183 {
 184         return fVolume->BlockSize() - SpaceUsed() - sizeof(btrfs_header);
 185 }
 186
 187
 188 void
 189 BTree::Node::_Copy(const Node* origin, uint32 at, uint32 from, uint32 to,
 190         int length) const
 191 {
 192         TRACE("Node::_Copy() at: %d from: %d to: %d length: %d\n",
 193                 at, from, to, length);
 194
 195         if (Level() == 0) {
 196                 memcpy(Item(at), origin->Item(from), origin->_CalculateSpace(from, to));
 197                 // Item offset of copied node must be changed to get the
 198                 // item data offset correctly. length can be zero
 199                 // but let it there doesn't harm anything.
 200                 for (uint32 i = at; i - at <= to - from; ++i)
 201                         Item(i)->SetOffset(Item(i)->Offset() - length);
 202
 203                 memcpy(ItemData(at + to - from), origin->ItemData(to),
 204                         origin->_CalculateSpace(from, to, 2));
 205         } else {
 206                 memcpy(Index(at), origin->Index(from),
 207                         origin->_CalculateSpace(from, to));
 208         }
 209 }
 210
 211
 212 status_t
 213 BTree::Node::_SpaceCheck(int length) const
 214 {
 215         // this is a little bit weird here because we can't find
 216         // any suitable error code
 217         if (length < 0 && std::abs(length) >= SpaceUsed())
 218                 return B_DIRECTORY_NOT_EMPTY;   // not enough data to delete
 219         if (length > 0 && length >= SpaceLeft())
 220                 return B_DEVICE_FULL;                   // no spare space
 221         return B_OK;
 222 }
 223
 224
 225 /*
 226  * copy node header, items and items data
 227  * length is size to insert/remove
 228  * if node is a internal node, length isnt used
 229  * length = 0: Copy a whole
 230  * length < 0: removing
 231  * length > 0: inserting
 232  */
 233 status_t
 234 BTree::Node::Copy(const Node* origin, uint32 start, uint32 end, int length)
 235         const
 236 {
 237         status_t status = origin->_SpaceCheck(length);
 238         if (status != B_OK)
 239                 return status;
 240
 241         memcpy(fNode, origin->fNode, sizeof(btrfs_header));
 242         if (length == 0) {
 243                 // like removing [0, start - 1] and keeping [start, end]
 244                 length = -origin->_CalculateSpace(0, start - 1, 2);
 245                 _Copy(origin, 0, start, end, length);
 246         } else if (length < 0) {
 247                 //removing all items in [start, end]
 248                 if (start > 0)
 249                         _Copy(origin, 0, 0, start - 1, 0);      // <-- [start,...
 250                 if (end + 1 < origin->ItemCount()) {
 251                         // ..., end] -->
 252                         // we only care data size
 253                         length += origin->_CalculateSpace(start, end);
 254                         _Copy(origin, start, end + 1, origin->ItemCount() - 1, length);
 255                 }
 256         } else {
 257                 //inserting in [start, end] - make a hole for later
 258                 if (start > 0)
 259                         _Copy(origin, 0, 0, start - 1, 0);
 260                 if (start < origin->ItemCount()) {
 261                         length -= origin->_CalculateSpace(start, end);
 262                         _Copy(origin, end + 1, start, origin->ItemCount() - 1, length);
 263                 }
 264         }
 265
 266         return B_OK;
 267 }
 268
 269
 270 /* Like copy but here we use memmove on current node.
 271  */
 272 status_t
 273 BTree::Node::MoveEntries(uint32 start, uint32 end, int length) const
 274 {
 275         status_t status = _SpaceCheck(length);
 276         if (status != B_OK || length == 0/*B_OK*/)
 277                 return status;
 278
 279         int entrySize = sizeof(btrfs_entry);
 280         if (Level() != 0)
 281                 entrySize = sizeof(btrfs_index);
 282
 283         uint8* base = (uint8*)fNode + sizeof(btrfs_header);
 284         end++;
 285         if (length < 0) {
 286                 // removing [start, end]
 287                 TRACE("Node::MoveEntries() removing ... start %" B_PRIu32 " end %"
 288                         B_PRIu32 " length %i\n", start, end, length);
 289                 length += _CalculateSpace(start, end - 1);
 290         } else {
 291                 // length > 0
 292                 // inserting into [start, end] - make room for later
 293                 TRACE("Node::MoveEntries() inserting ... start %" B_PRIu32 " end %"
 294                         B_PRIu32 " length %i\n", start, end, length);
 295                 length -= _CalculateSpace(start, end - 1);
 296                 std::swap(start, end);
 297         }
 298
 299         if (end >= ItemCount())
 300                 return B_OK;
 301
 302         int dataSize = _CalculateSpace(end, ItemCount() - 1, 2);
 303         // moving items/block pointers
 304         memmove(base + start * entrySize, base + end * entrySize,
 305                 _CalculateSpace(end, ItemCount() - 1));
 306         if (Level() == 0) {
 307                 // moving item data
 308                 int num = start - end;
 309                 for(uint32 i = start; i < ItemCount() + num; ++i)
 310                         Item(i)->SetOffset(Item(i)->Offset() - length);
 311
 312                 memmove(ItemData(ItemCount() - 1) - length, ItemData(ItemCount() - 1),
 313                         dataSize);
 314         }
 315
 316         return B_OK;
 317 }
 318
 319
 320 //      #pragma mark - BTree::Path implementation
 321
 322
 323 BTree::Path::Path(BTree* tree)
 324         :
 325         fTree(tree)
 326 {
 327         for (int i = 0; i < BTRFS_MAX_TREE_DEPTH; ++i) {
 328                 fNodes[i] = NULL;
 329                 fSlots[i] = 0;
 330         }
 331 }
 332
 333
 334 BTree::Path::~Path()
 335 {
 336         for (int i = 0; i < BTRFS_MAX_TREE_DEPTH; ++i) {
 337                 delete fNodes[i];
 338                 fNodes[i] = NULL;
 339                 fSlots[i] = 0;
 340         }
 341 }
 342
 343
 344 BTree::Node*
 345 BTree::Path::GetNode(int level, int* _slot) const
 346 {
 347         if (_slot != NULL)
 348                 *_slot = fSlots[level];
 349         return fNodes[level];
 350 }
 351
 352
 353 BTree::Node*
 354 BTree::Path::SetNode(off_t block, int slot)
 355 {
 356         Node node(fTree->SystemVolume(), block);
 357         return SetNode(&node, slot);
 358 }
 359
 360
 361 BTree::Node*
 362 BTree::Path::SetNode(const Node* node, int slot)
 363 {
 364         uint8 level = node->Level();
 365         if (fNodes[level] == NULL) {
 366                 fNodes[level] = new Node(fTree->SystemVolume(), node->BlockNum());
 367                 if (fNodes[level] == NULL)
 368                         return NULL;
 369         } else
 370                 fNodes[level]->SetTo(node->BlockNum());
 371
 372         if (slot == -1)
 373                 fSlots[level] = fNodes[level]->ItemCount() - 1;
 374         else
 375                 fSlots[level] = slot;
 376         return fNodes[level];
 377 }
 378
 379
 380 int
 381 BTree::Path::Move(int level, int step)
 382 {
 383         fSlots[level] += step;
 384         if (fSlots[level] < 0)
 385                 return -1;
 386         if (fSlots[level] >= fNodes[level]->ItemCount())
 387                 return 1;
 388         return 0;
 389 }
 390
 391
 392 status_t
 393 BTree::Path::GetEntry(int slot, btrfs_key* _key, void** _value, uint32* _size,
 394         uint32* _offset)
 395 {
 396         BTree::Node* leaf = fNodes[0];
 397         if (slot < 0 || slot >= leaf->ItemCount())
 398                 return B_ENTRY_NOT_FOUND;
 399
 400         if (_key != NULL)
 401                 *_key = leaf->Item(slot)->key;
 402
 403         uint32 itemSize = leaf->Item(slot)->Size();
 404         if (_value != NULL) {
 405                 *_value = malloc(itemSize);
 406                 if (*_value == NULL)
 407                         return B_NO_MEMORY;
 408
 409                 memcpy(*_value, leaf->ItemData(slot), itemSize);
 410         }
 411
 412         if (_size != NULL)
 413                 *_size = itemSize;
 414
 415         if (_offset != NULL)
 416                 *_offset = leaf->Item(slot)->Offset();
 417
 418         return B_OK;
 419 }
 420
 421
 422 //      #pragma mark - BTree implementation
 423
 424
 425 BTree::BTree(Volume* volume)
 426         :
 427         fRootBlock(0),
 428         fVolume(volume)
 429 {
 430         mutex_init(&fIteratorLock, "btrfs b+tree iterator");
 431 }
 432
 433
 434 BTree::BTree(Volume* volume, btrfs_stream* stream)
 435         :
 436         fRootBlock(0),
 437         fVolume(volume)
 438 {
 439         mutex_init(&fIteratorLock, "btrfs b+tree iterator");
 440 }
 441
 442
 443 BTree::BTree(Volume* volume, fsblock_t rootBlock)
 444         :
 445         fRootBlock(rootBlock),
 446         fVolume(volume)
 447 {
 448         mutex_init(&fIteratorLock, "btrfs b+tree iterator");
 449 }
 450
 451
 452 BTree::~BTree()
 453 {
 454         // if there are any TreeIterators left, we need to stop them
 455         // (can happen when the tree's inode gets deleted while
 456         // traversing the tree - a TreeIterator doesn't lock the inode)
 457         mutex_lock(&fIteratorLock);
 458
 459         SinglyLinkedList<TreeIterator>::Iterator iterator
 460                 = fIterators.GetIterator();
 461         while (iterator.HasNext())
 462                 iterator.Next()->Stop();
 463         mutex_destroy(&fIteratorLock);
 464 }
 465
 466
 467 int32
 468 btrfs_key::Compare(const btrfs_key& key) const
 469 {
 470         if (ObjectID() > key.ObjectID())
 471                 return 1;
 472         if (ObjectID() < key.ObjectID())
 473                 return -1;
 474         if (Type() > key.Type())
 475                 return 1;
 476         if (Type() < key.Type())
 477                 return -1;
 478         if (Offset() > key.Offset())
 479                 return 1;
 480         if (Offset() < key.Offset())
 481                 return -1;
 482         return 0;
 483 }
 484
 485
 486 /* Traverse from root to fill in the path along way its finding.
 487  * Return current slot at leaf if successful.
 488  */
 489 status_t
 490 BTree::Traverse(btree_traversing type, Path* path, const btrfs_key& key)
 491         const
 492 {
 493         TRACE("BTree::Traverse() objectid %" B_PRId64 " type %d offset %"
 494                 B_PRId64 " \n", key.ObjectID(), key.Type(), key.Offset());
 495         fsblock_t physicalBlock = fRootBlock;
 496         Node node(fVolume, physicalBlock);
 497         int slot;
 498         status_t status = B_OK;
 499
 500         while (node.Level() != 0) {
 501                 TRACE("BTree::Traverse() level %d count %d\n", node.Level(),
 502                         node.ItemCount());
 503                 status = node.SearchSlot(key, &slot, BTREE_BACKWARD);
 504                 if (status != B_OK)
 505                         return status;
 506                 if (path->SetNode(&node, slot) == NULL)
 507                         return B_NO_MEMORY;
 508
 509                 TRACE("BTree::Traverse() getting index %" B_PRIu32 "\n", slot);
 510
 511                 status = fVolume->FindBlock(node.Index(slot)->LogicalAddress(),
 512                                 physicalBlock);
 513                 if (status != B_OK) {
 514                         ERROR("BTree::Traverse() unmapped block %" B_PRId64 "\n",
 515                                 node.Index(slot)->LogicalAddress());
 516                         return status;
 517                 }
 518                 node.SetTo(physicalBlock);
 519         }
 520
 521         TRACE("BTree::Traverse() dump count %" B_PRId32 "\n", node.ItemCount());
 522         status = node.SearchSlot(key, &slot, type);
 523         if (status != B_OK)
 524                 return status;
 525         if (path->SetNode(&node, slot) == NULL)
 526                 return B_NO_MEMORY;
 527
 528         TRACE("BTree::Traverse() found %" B_PRIu32 " %" B_PRIu32 "\n",
 529                 node.Item(slot)->Offset(), node.Item(slot)->Size());
 530         return slot;
 531 }
 532
 533
 534 /*!     Searches the key in the tree, and stores the allocated found item in
 535         _value, if successful.
 536         Returns B_OK when the key could be found, B_ENTRY_NOT_FOUND if not.
 537         It can also return other errors to indicate that something went wrong.
 538 */
 539 status_t
 540 BTree::_Find(Path* path, btrfs_key& wanted, void** _value, uint32* _size,
 541         uint32* _offset, btree_traversing type) const
 542 {
 543         status_t status = Traverse(type, path, wanted);
 544         if (status < B_OK)
 545                 return status;
 546
 547         btrfs_key found;
 548         status = path->GetCurrentEntry(&found, _value, _size, _offset);
 549         if (status != B_OK)
 550                 return status;
 551
 552         if (found.Type() != wanted.Type() && wanted.Type() != BTRFS_KEY_TYPE_ANY)
 553                 return B_ENTRY_NOT_FOUND;
 554
 555         wanted = found;
 556         return B_OK;
 557 }
 558
 559
 560 status_t
 561 BTree::FindNext(Path* path, btrfs_key& key, void** _value, uint32* _size,
 562         uint32* _offset) const
 563 {
 564         return _Find(path, key, _value, _size, _offset, BTREE_FORWARD);
 565 }
 566
 567
 568 status_t
 569 BTree::FindPrevious(Path* path, btrfs_key& key, void** _value, uint32* _size,
 570         uint32* _offset) const
 571 {
 572         return _Find(path, key, _value, _size, _offset, BTREE_BACKWARD);
 573 }
 574
 575
 576 status_t
 577 BTree::FindExact(Path* path, btrfs_key& key, void** _value, uint32* _size,
 578         uint32* _offset) const
 579 {
 580         return _Find(path, key, _value, _size, _offset, BTREE_EXACT);
 581 }
 582
 583
 584 status_t
 585 BTree::PreviousLeaf(Path* path) const
 586 {
 587         // TODO: use Traverse() ???
 588         int level = 0;
 589         int slot;
 590         Node* node = NULL;
 591         // iterate to the root until satisfy the condition
 592         while (true) {
 593                 node = path->GetNode(level, &slot);
 594                 if (node == NULL || slot != 0)
 595                         break;
 596                 level++;
 597         }
 598
 599         // the current leaf is already the left most leaf or
 600         // path was not initialized
 601         if (node == NULL)
 602                 return B_ENTRY_NOT_FOUND;
 603
 604         path->Move(level, BTREE_BACKWARD);
 605         fsblock_t physicalBlock;
 606         // change all nodes below this level and slot to the ending
 607         do {
 608                 status_t status = fVolume->FindBlock(
 609                         node->Index(slot)->LogicalAddress(), physicalBlock);
 610                 if (status != B_OK)
 611                         return status;
 612
 613                 node = path->SetNode(physicalBlock, -1);
 614                 if (node == NULL)
 615                         return B_NO_MEMORY;
 616                 slot = node->ItemCount() - 1;
 617                 level--;
 618         } while(level != 0);
 619
 620         return B_OK;
 621 }
 622
 623
 624 status_t
 625 BTree::NextLeaf(Path* path) const
 626 {
 627         int level = 0;
 628         int slot;
 629         Node* node = NULL;
 630         // iterate to the root until satisfy the condition
 631         while (true) {
 632                 node = path->GetNode(level, &slot);
 633                 if (node == NULL || slot < node->ItemCount() - 1)
 634                         break;
 635                 level++;
 636         }
 637
 638         // the current leaf is already the right most leaf or
 639         // path was not initialized
 640         if (node == NULL)
 641                 return B_ENTRY_NOT_FOUND;
 642
 643         path->Move(level, BTREE_FORWARD);
 644         fsblock_t physicalBlock;
 645         // change all nodes below this level and slot to the beginning
 646         do {
 647                 status_t status = fVolume->FindBlock(
 648                         node->Index(slot)->LogicalAddress(), physicalBlock);
 649                 if (status != B_OK)
 650                         return status;
 651
 652                 node = path->SetNode(physicalBlock, 0);
 653                 if (node == NULL)
 654                         return B_NO_MEMORY;
 655                 slot = 0;
 656                 level--;
 657         } while(level != 0);
 658
 659         return B_OK;
 660 }
 661
 662
 663 status_t
 664 BTree::SetRoot(off_t logical, fsblock_t* block)
 665 {
 666         if (block != NULL) {
 667                 fRootBlock = *block;
 668                 //TODO: mapping physical block -> logical address
 669         } else {
 670                 fLogicalRoot = logical;
 671                 if (fVolume->FindBlock(logical, fRootBlock) != B_OK) {
 672                         ERROR("Find() unmapped block %" B_PRId64 "\n", fRootBlock);
 673                         return B_ERROR;
 674                 }
 675         }
 676         return B_OK;
 677 }
 678
 679
 680 void
 681 BTree::_AddIterator(TreeIterator* iterator)
 682 {
 683         MutexLocker _(fIteratorLock);
 684         fIterators.Add(iterator);
 685 }
 686
 687
 688 void
 689 BTree::_RemoveIterator(TreeIterator* iterator)
 690 {
 691         MutexLocker _(fIteratorLock);
 692         fIterators.Remove(iterator);
 693 }
 694
 695
 696 //      #pragma mark -
 697
 698
 699 TreeIterator::TreeIterator(BTree* tree, const btrfs_key& key)
 700         :
 701         fTree(tree),
 702         fKey(key),
 703         fIteratorStatus(B_NO_INIT)
 704 {
 705         tree->_AddIterator(this);
 706         fPath = new(std::nothrow) BTree::Path(tree);
 707         if (fPath == NULL)
 708                 fIteratorStatus = B_NO_MEMORY;
 709 }
 710
 711
 712 TreeIterator::~TreeIterator()
 713 {
 714         if (fTree)
 715                 fTree->_RemoveIterator(this);
 716
 717         delete fPath;
 718         fPath = NULL;
 719 }
 720
 721
 722 void
 723 TreeIterator::Rewind(bool inverse)
 724 {
 725         if (inverse)
 726                 fKey.SetOffset(BTREE_END);
 727         else
 728                 fKey.SetOffset(BTREE_BEGIN);
 729         fIteratorStatus = B_NO_INIT;
 730 }
 731
 732
 733 /*!     Iterates through the tree in the specified direction.
 734 */
 735 status_t
 736 TreeIterator::_Traverse(btree_traversing direction)
 737 {
 738         status_t status = fTree->Traverse(direction, fPath, fKey);
 739         if (status < B_OK) {
 740                 ERROR("TreeIterator::Traverse() Find failed\n");
 741                 return status;
 742         }
 743
 744         return (fIteratorStatus = B_OK);
 745 }
 746
 747
 748 // Like GetEntry in BTree::Path but here we check the type and moving.
 749 status_t
 750 TreeIterator::_GetEntry(btree_traversing type, void** _value, uint32* _size,
 751         uint32* _offset)
 752 {
 753         status_t status;
 754         if (fIteratorStatus == B_NO_INIT) {
 755                 status = _Traverse(type);
 756                 if (status != B_OK)
 757                         return status;
 758                 type = BTREE_EXACT;
 759         }
 760
 761         if (fIteratorStatus != B_OK)
 762                 return fIteratorStatus;
 763
 764         int move = fPath->Move(0, type);
 765         if (move > 0)
 766                 status = fTree->NextLeaf(fPath);
 767         else if (move < 0)
 768                 status = fTree->PreviousLeaf(fPath);
 769         if (status != B_OK)
 770                 return status;
 771
 772         btrfs_key found;
 773         status = fPath->GetCurrentEntry(&found, _value, _size, _offset);
 774         if (status != B_OK)
 775                 return status;
 776
 777         fKey.SetObjectID(found.ObjectID());
 778         fKey.SetOffset(found.Offset());
 779         if (fKey.Type() != found.Type() && fKey.Type() != BTRFS_KEY_TYPE_ANY)
 780                 return B_ENTRY_NOT_FOUND;
 781
 782         return B_OK;
 783 }
 784
 785
 786 /*!     just sets the current key in the iterator.
 787 */
 788 status_t
 789 TreeIterator::Find(const btrfs_key& key)
 790 {
 791         if (fIteratorStatus == B_INTERRUPTED)
 792                 return fIteratorStatus;
 793
 794         fKey = key;
 795         fIteratorStatus = B_NO_INIT;
 796         return B_OK;
 797 }
 798
 799
 800 void
 801 TreeIterator::Stop()
 802 {
 803         fTree = NULL;
 804         fIteratorStatus = B_INTERRUPTED;
 805 }