file_systems/btrfs/BTree.cpp

9 //! BTree implementation
12 #include "BTree.h"
25 BTree::Node::Node(Volume* volume)
35 BTree::Node::Node(Volume* volume, off_t block)
46 BTree::Node::~Node()
53 BTree::Node::Unset()
63 BTree::Node::SetTo(off_t block)
72 BTree::Node::SetToWritable(off_t block, int32 transactionId, bool empty)
88 BTree::Node::SearchSlot(const btrfs_key& key, int* slot, btree_traversing type)
136 BTree::Node::_CalculateSpace(uint32 from, uint32 to, uint8 type) const
158 BTree::Node::SpaceUsed() const
167 BTree::Node::SpaceLeft() const
174 BTree::Node::_Copy(const Node* origin, uint32 at, uint32 from, uint32 to,
198 BTree::Node::_SpaceCheck(int length) const
211 BTree::Node::Copy(const Node* origin, uint32 start, uint32 end, int length)
248 BTree::Node::MoveEntries(uint32 start, uint32 end, int length) const
297 //	#pragma mark - BTree::Path implementation
300 BTree::Path::Path(BTree* tree)
311 BTree::Path::~Path()
321 BTree::Node*
322 BTree::Path::GetNode(int level, int* _slot) const
330 BTree::Node*
331 BTree::Path::SetNode(off_t block, int slot)
338 BTree::Node*
339 BTree::Path::SetNode(const Node* node, int slot)
358 BTree::Path::Move(int level, int step)
370 BTree::Path::GetEntry(int slot, btrfs_key* _key, void** _value, uint32* _size,
373 	BTree::Node* leaf = fNodes[0];
400 BTree::Path::SetEntry(int slot, const btrfs_entry& entry, void* value)
412 BTree::Path::CopyOnWrite(Transaction& transaction, int level, uint32 start,
441 	fNodes[level] = new(std::nothrow) BTree::Node(fTree->SystemVolume());
475 BTree::Path::InternalCopy(Transaction& transaction, int level)
506 //	#pragma mark - BTree implementation
509 BTree::BTree(Volume* volume)
519 BTree::BTree(Volume* volume, btrfs_stream* stream)
529 BTree::BTree(Volume* volume, fsblock_t rootBlock)
538 BTree::~BTree()
573 BTree::Traverse(btree_traversing type, Path* path, const btrfs_key& key)
576 	TRACE("BTree::Traverse() objectid %" B_PRId64 " type %d offset %"
584 		TRACE("BTree::Traverse() level %d count %d\n", node.Level(),
592 		TRACE("BTree::Traverse() getting index %" B_PRIu32 "\n", slot);
597 			ERROR("BTree::Traverse() unmapped block %" B_PRId64 "\n",
604 	TRACE("BTree::Traverse() dump count %" B_PRId32 "\n", node.ItemCount());
611 	TRACE("BTree::Traverse() found %" B_PRIu32 " %" B_PRIu32 "\n",
618 BTree::_Find(Path* path, btrfs_key& wanted, void** _value, uint32* _size,
644 BTree::FindNext(Path* path, btrfs_key& key, void** _value, uint32* _size,
652 BTree::FindPrevious(Path* path, btrfs_key& key, void** _value, uint32* _size,
660 BTree::FindExact(Path* path, btrfs_key& key, void** _value, uint32* _size,
668 BTree::MakeEntries(Transaction& transaction, Path* path,
671 	TRACE("BTree::MakeEntries() num %i key (% " B_PRIu64 " %" B_PRIu8 " %"
697 BTree::InsertEntries(Transaction& transaction, Path* path,
715 	TRACE("BTree::InsertEntries() num: %i upper limit %" B_PRIu32 "\n", num,
728 BTree::RemoveEntries(Transaction& transaction, Path* path,
731 	TRACE("BTree::RemoveEntries() num %i key (% " B_PRIu64 " %" B_PRIu8 " %"
761 BTree::PreviousLeaf(Path* path) const
801 BTree::NextLeaf(Path* path) const
840 BTree::SetRoot(off_t logical, fsblock_t* block)
862 BTree::SetRoot(Node* root)
871 BTree::_AddIterator(TreeIterator* iterator)
879 BTree::_RemoveIterator(TreeIterator* iterator)
889 TreeIterator::TreeIterator(BTree* tree, const btrfs_key& key)
896 	fPath = new(std::nothrow) BTree::Path(tree);