haiku.git

/*
 * Copyright 2017, Chế Vũ Gia Hy, cvghy116@gmail.com.
 * Copyright 2011, Jérôme Duval, korli@users.berlios.de.
 * Copyright 2001-2010, Axel Dörfler, axeld@pinc-software.de.
 * This file may be used under the terms of the MIT License.
 */
#ifndef B_TREE_H
#define B_TREE_H


#include "btrfs.h"
#include "Volume.h"


#define BTREE_NULL			-1LL
#define BTREE_FREE			-2LL

#define BTRFS_MAX_TREE_DEPTH		8


//! Tree traversal direction status, used by functions manipulating trees
enum btree_traversing {
	BTREE_FORWARD = 1,
	BTREE_EXACT = 0,
	BTREE_BACKWARD = -1,

	BTREE_BEGIN = 0,
	BTREE_END = -1
};


class Transaction;


//	#pragma mark - in-memory structures


template<class T> class Stack;
class TreeIterator;


// needed for searching (utilizing a stack)
struct node_and_key {
	off_t	nodeOffset;
	uint16	keyIndex;
};


class BTree {
public:
	class Path;
	class Node;

public:
								BTree(Volume* volume);
								BTree(Volume* volume,
									btrfs_stream* stream);
								BTree(Volume* volume,
									fsblock_t rootBlock);
								~BTree();

			status_t			FindExact(Path* path, btrfs_key& key,
									void** _value, uint32* _size = NULL,
									uint32* _offset = NULL) const;
			status_t			FindNext(Path* path, btrfs_key& key,
									void** _value, uint32* _size = NULL,
									uint32* _offset = NULL) const;
			status_t			FindPrevious(Path* path, btrfs_key& key,
									void** _value, uint32* _size = NULL,
									uint32* _offset = NULL) const;

			/*! Traverse from the root to fill in the path along the way
			 * \return Current slot at leaf if successful, error code (out of memory,
			 * no such entry, unmapped block) otherwise
			 */
			status_t			Traverse(btree_traversing type, Path* path,
									const btrfs_key& key) const;

			status_t			PreviousLeaf(Path* path) const;
			status_t			NextLeaf(Path* path) const;
			/*! Insert consecutive empty entries
			 * \param num Number of entries to be inserted
			 * \param startKey Slot to start inserting
			 * \return Starting slot on success, error code otherwise
			 */
			status_t			MakeEntries(Transaction& transaction,
									Path* path, const btrfs_key& startKey,
									int num, int length);
			//! MakeEntries and fill in them
			status_t			InsertEntries(Transaction& transaction,
									Path* path, btrfs_entry* entries,
									void** data, int num);
			/*! Like MakeEntries, but here entries are removed.
			 * \param _data Location to store removed data
			 */
			status_t			RemoveEntries(Transaction& transaction,
									Path* path, const btrfs_key& startKey,
									void** _data, int num);

			Volume*				SystemVolume() const { return fVolume; }
			status_t			SetRoot(off_t logical, fsblock_t* block);
			void				SetRoot(Node* root);
			fsblock_t			RootBlock() const { return fRootBlock; }
			off_t				LogicalRoot() const { return fLogicalRoot; }
			uint8				RootLevel() const { return fRootLevel; }

private:
								BTree(const BTree& other);
								BTree& operator=(const BTree& other);
									// no implementation

			/*! Search for key in the tree
			 * \param _value Location to store item if search successful
			 * \return B_OK when key found, error code otherwise
			 */
			status_t			_Find(Path* path, btrfs_key& key,
									void** _value, uint32* _size,
									uint32* _offset, btree_traversing type)
									const;
			void				_AddIterator(TreeIterator* iterator);
			void				_RemoveIterator(TreeIterator* iterator);
private:
			friend class TreeIterator;

			fsblock_t			fRootBlock;
			off_t				fLogicalRoot;
			uint8				fRootLevel;
			Volume*				fVolume;
			mutex				fIteratorLock;
			SinglyLinkedList<TreeIterator> fIterators;

public:
	class Node {
	public:
		Node(Volume* volume);
		Node(Volume* volume, off_t block);
		~Node();


		uint64	LogicalAddress() const
			{ return fNode->header.LogicalAddress(); }
		uint64	Flags() const
			{ return fNode->header.Flags(); }
		uint64	Generation() const
			{ return fNode->header.Generation(); }
		uint64	Owner() const
			{ return fNode->header.Owner(); }
		uint32	ItemCount() const
			{ return fNode->header.ItemCount(); }
		uint8	Level() const
			{ return fNode->header.Level(); }
		void	SetLogicalAddress(uint64 address)
			{ fNode->header.SetLogicalAddress(address); }
		void	SetGeneration(uint64 generation)
			{ fNode->header.SetGeneration(generation); }
		void	SetItemCount(uint32 itemCount)
			{ fNode->header.SetItemCount(itemCount); }

		btrfs_index*	Index(uint32 i) const
			{ return &fNode->index[i]; }

		btrfs_entry*	Item(uint32 i) const
			{ return &fNode->entries[i]; }
		uint8*	ItemData(uint32 i) const
			{ return (uint8*)Item(0) + Item(i)->Offset(); }

		//! Reset Node and decrements ref-count to the Node's block
		void	Unset();

		//! Load node at block offset from disk
		void	SetTo(off_t block);
		void	SetToWritable(off_t block, int32 transactionId, bool empty);
		int		SpaceUsed() const;
		int		SpaceLeft() const;

		off_t	BlockNum() const { return fBlockNumber;}
		bool	IsWritable() const { return fWritable; }

		/*!
		 * copy node header, items and items data
		 * length is size to insert/remove
		 * if node is a internal node, length isnt used
		 * length = 0: Copy a whole
		 * length < 0: removing
		 * length > 0: inserting
		 */
		status_t	Copy(const Node* origin, uint32 start, uint32 end,
						int length) const;
		//! Shift data in items between start and end by offset length
		status_t	MoveEntries(uint32 start, uint32 end, int length) const;

		//! Searches for item slot in the node
		status_t	SearchSlot(const btrfs_key& key, int* slot,
						btree_traversing type) const;
	private:
		Node(const Node&);
		Node& operator=(const Node&);
			// no implementation

		//! Internal function used by Copy
		void	_Copy(const Node* origin, uint32 at, uint32 from, uint32 to,
					int length) const;
		status_t	_SpaceCheck(int length) const;

		/*!
		 * calculate used space except the header.
		 * type is only for leaf node
		 * type 1: only item space
		 * type 2: only item data space
		 * type 3: both type 1 and 2
		 */
		int		_CalculateSpace(uint32 from, uint32 to, uint8 type = 1) const;

		btrfs_stream*		fNode;
		Volume*				fVolume;
		off_t				fBlockNumber;
		bool				fWritable;
	};


	class Path {
	public:
		Path(BTree* tree);
		~Path();


		Node*		GetNode(int level, int* _slot = NULL) const;
		Node*		SetNode(off_t block, int slot);
		Node*		SetNode(const Node* node, int slot);
		status_t	GetCurrentEntry(btrfs_key* _key, void** _value,
						uint32* _size = NULL, uint32* _offset = NULL);
		status_t	GetEntry(int slot, btrfs_key* _key, void** _value,
						uint32* _size = NULL, uint32* _offset = NULL);
		status_t	SetEntry(int slot, const btrfs_entry& entry, void* value);

		int			Move(int level, int step);


		/*!
		* Allocate and copy block and do all the changes that it can.
		* for now, we only copy-on-write tree block,
		* file data is "nocow" by default.
		*
		*  o   parent  o
		*  |    ===>    \
		*  o           x o
		*/
		status_t	CopyOnWrite(Transaction& transaction, int level,
						uint32 start, int num, int length);
		/*!
		* Copy-On-Write all internal nodes start from a specific level.
		* level > 0: to root
		* level <= 0: to leaf
		*
		*      path    cow-path       path    cow-path
		*  =================================================
		*      root    cow-root       root level < 0
		*       |      |               |
		*       n1     cow-n1         ...______
		*       |      |               |       \
		*       n2     cow-n2          n1     cow-n1
		*       |      /               |        |
		*      ...____/                n2     cow-n2
		*       |                      |        |
		*      leaf    level > 0      leaf    cow-leaf
		*/
		status_t	InternalCopy(Transaction& transaction, int level);
		BTree*		Tree() const { return fTree; }
	private:
		Path(const Path&);
		Path operator=(const Path&);
	private:
		Node*	fNodes[BTRFS_MAX_TREE_DEPTH];
		int		fSlots[BTRFS_MAX_TREE_DEPTH];
		BTree*	fTree;
	};

};	// class BTree


class TreeIterator : public SinglyLinkedListLinkImpl<TreeIterator> {
public:
								TreeIterator(BTree* tree, const btrfs_key& key);
								~TreeIterator();

			void				Rewind(bool inverse = false);
			//! Set current key in the iterator
			status_t			Find(const btrfs_key& key);
			status_t			GetNextEntry(void** _value,
									uint32* _size = NULL,
									uint32* _offset = NULL);
			status_t			GetPreviousEntry(void** _value,
									uint32* _size = NULL,
									uint32* _offset = NULL);

			BTree*				Tree() const { return fTree; }
			btrfs_key			Key() const { return fKey; }

private:
			friend class BTree;

			//! Iterates through the tree in the specified direction
			status_t			_Traverse(btree_traversing direction);
			status_t			_Find(btree_traversing type, btrfs_key& key,
									void** _value);
			//! Like GetEntry in BTree::Path but checks type and moving
			status_t			_GetEntry(btree_traversing type, void** _value,
									uint32* _size, uint32* _offset);
			// called by BTree
			void				Stop();

private:
			BTree*			fTree;
			BTree::Path*	fPath;
			btrfs_key		fKey;
			status_t		fIteratorStatus;
};


//	#pragma mark - BTree::Path inline functions


inline status_t
BTree::Path::GetCurrentEntry(btrfs_key* _key, void** _value, uint32* _size,
	uint32* _offset)
{
	return GetEntry(fSlots[0], _key, _value, _size, _offset);
}


//	#pragma mark - TreeIterator inline functions


inline status_t
TreeIterator::GetNextEntry(void** _value, uint32* _size, uint32* _offset)
{
	return _GetEntry(BTREE_FORWARD, _value, _size, _offset);
}


inline status_t
TreeIterator::GetPreviousEntry(void** _value, uint32* _size, uint32* _offset)
{
	return _GetEntry(BTREE_BACKWARD, _value, _size, _offset);
}


#endif	// B_TREE_H