1/*
2 * Copyright 2017, Ch��� V�� Gia Hy, cvghy116@gmail.com.
3 * Copyright 2011, J��r��me Duval, korli@users.berlios.de.
4 * Copyright 2001-2010, Axel D��rfler, axeld@pinc-software.de.
5 * This file may be used under the terms of the MIT License.
6 */
7#ifndef B_TREE_H
8#define B_TREE_H
9
10
11#include "btrfs.h"
12#include "Volume.h"
13
14
15#define BTREE_NULL			-1LL
16#define BTREE_FREE			-2LL
17
18#define BTRFS_MAX_TREE_DEPTH		8
19
20
21//! Tree traversal direction status, used by functions manipulating trees
22enum btree_traversing {
23	BTREE_FORWARD = 1,
24	BTREE_EXACT = 0,
25	BTREE_BACKWARD = -1,
26
27	BTREE_BEGIN = 0,
28	BTREE_END = -1
29};
30
31
32class Transaction;
33
34
35//	#pragma mark - in-memory structures
36
37
38template<class T> class Stack;
39class TreeIterator;
40
41
42// needed for searching (utilizing a stack)
43struct node_and_key {
44	off_t	nodeOffset;
45	uint16	keyIndex;
46};
47
48
49class BTree {
50public:
51	class Path;
52	class Node;
53
54public:
55								BTree(Volume* volume);
56								BTree(Volume* volume,
57									btrfs_stream* stream);
58								BTree(Volume* volume,
59									fsblock_t rootBlock);
60								~BTree();
61
62			status_t			FindExact(Path* path, btrfs_key& key,
63									void** _value, uint32* _size = NULL,
64									uint32* _offset = NULL) const;
65			status_t			FindNext(Path* path, btrfs_key& key,
66									void** _value, uint32* _size = NULL,
67									uint32* _offset = NULL) const;
68			status_t			FindPrevious(Path* path, btrfs_key& key,
69									void** _value, uint32* _size = NULL,
70									uint32* _offset = NULL) const;
71
72			/*! Traverse from the root to fill in the path along the way
73			 * \return Current slot at leaf if successful, error code (out of memory,
74			 * no such entry, unmapped block) otherwise
75			 */
76			status_t			Traverse(btree_traversing type, Path* path,
77									const btrfs_key& key) const;
78
79			status_t			PreviousLeaf(Path* path) const;
80			status_t			NextLeaf(Path* path) const;
81			/*! Insert consecutive empty entries
82			 * \param num Number of entries to be inserted
83			 * \param startKey Slot to start inserting
84			 * \return Starting slot on success, error code otherwise
85			 */
86			status_t			MakeEntries(Transaction& transaction,
87									Path* path, const btrfs_key& startKey,
88									int num, int length);
89			//! MakeEntries and fill in them
90			status_t			InsertEntries(Transaction& transaction,
91									Path* path, btrfs_entry* entries,
92									void** data, int num);
93			/*! Like MakeEntries, but here entries are removed.
94			 * \param _data Location to store removed data
95			 */
96			status_t			RemoveEntries(Transaction& transaction,
97									Path* path, const btrfs_key& startKey,
98									void** _data, int num);
99
100			Volume*				SystemVolume() const { return fVolume; }
101			status_t			SetRoot(off_t logical, fsblock_t* block);
102			void				SetRoot(Node* root);
103			fsblock_t			RootBlock() const { return fRootBlock; }
104			off_t				LogicalRoot() const { return fLogicalRoot; }
105			uint8				RootLevel() const { return fRootLevel; }
106
107private:
108								BTree(const BTree& other);
109								BTree& operator=(const BTree& other);
110									// no implementation
111
112			/*! Search for key in the tree
113			 * \param _value Location to store item if search successful
114			 * \return B_OK when key found, error code otherwise
115			 */
116			status_t			_Find(Path* path, btrfs_key& key,
117									void** _value, uint32* _size,
118									uint32* _offset, btree_traversing type)
119									const;
120			void				_AddIterator(TreeIterator* iterator);
121			void				_RemoveIterator(TreeIterator* iterator);
122private:
123			friend class TreeIterator;
124
125			fsblock_t			fRootBlock;
126			off_t				fLogicalRoot;
127			uint8				fRootLevel;
128			Volume*				fVolume;
129			mutex				fIteratorLock;
130			SinglyLinkedList<TreeIterator> fIterators;
131
132public:
133	class Node {
134	public:
135		Node(Volume* volume);
136		Node(Volume* volume, off_t block);
137		~Node();
138
139
140		uint64	LogicalAddress() const
141			{ return fNode->header.LogicalAddress(); }
142		uint64	Flags() const
143			{ return fNode->header.Flags(); }
144		uint64	Generation() const
145			{ return fNode->header.Generation(); }
146		uint64	Owner() const
147			{ return fNode->header.Owner(); }
148		uint32	ItemCount() const
149			{ return fNode->header.ItemCount(); }
150		uint8	Level() const
151			{ return fNode->header.Level(); }
152		void	SetLogicalAddress(uint64 address)
153			{ fNode->header.SetLogicalAddress(address); }
154		void	SetGeneration(uint64 generation)
155			{ fNode->header.SetGeneration(generation); }
156		void	SetItemCount(uint32 itemCount)
157			{ fNode->header.SetItemCount(itemCount); }
158
159		btrfs_index*	Index(uint32 i) const
160			{ return &fNode->index[i]; }
161
162		btrfs_entry*	Item(uint32 i) const
163			{ return &fNode->entries[i]; }
164		uint8*	ItemData(uint32 i) const
165			{ return (uint8*)Item(0) + Item(i)->Offset(); }
166
167		//! Reset Node and decrements ref-count to the Node's block
168		void	Unset();
169
170		//! Load node at block offset from disk
171		void	SetTo(off_t block);
172		void	SetToWritable(off_t block, int32 transactionId, bool empty);
173		int		SpaceUsed() const;
174		int		SpaceLeft() const;
175
176		off_t	BlockNum() const { return fBlockNumber;}
177		bool	IsWritable() const { return fWritable; }
178
179		/*!
180		 * copy node header, items and items data
181		 * length is size to insert/remove
182		 * if node is a internal node, length isnt used
183		 * length = 0: Copy a whole
184		 * length < 0: removing
185		 * length > 0: inserting
186		 */
187		status_t	Copy(const Node* origin, uint32 start, uint32 end,
188						int length) const;
189		//! Shift data in items between start and end by offset length
190		status_t	MoveEntries(uint32 start, uint32 end, int length) const;
191
192		//! Searches for item slot in the node
193		status_t	SearchSlot(const btrfs_key& key, int* slot,
194						btree_traversing type) const;
195	private:
196		Node(const Node&);
197		Node& operator=(const Node&);
198			// no implementation
199
200		//! Internal function used by Copy
201		void	_Copy(const Node* origin, uint32 at, uint32 from, uint32 to,
202					int length) const;
203		status_t	_SpaceCheck(int length) const;
204
205		/*!
206		 * calculate used space except the header.
207		 * type is only for leaf node
208		 * type 1: only item space
209		 * type 2: only item data space
210		 * type 3: both type 1 and 2
211		 */
212		int		_CalculateSpace(uint32 from, uint32 to, uint8 type = 1) const;
213
214		btrfs_stream*		fNode;
215		Volume*				fVolume;
216		off_t				fBlockNumber;
217		bool				fWritable;
218	};
219
220
221	class Path {
222	public:
223		Path(BTree* tree);
224		~Path();
225
226
227		Node*		GetNode(int level, int* _slot = NULL) const;
228		Node*		SetNode(off_t block, int slot);
229		Node*		SetNode(const Node* node, int slot);
230		status_t	GetCurrentEntry(btrfs_key* _key, void** _value,
231						uint32* _size = NULL, uint32* _offset = NULL);
232		status_t	GetEntry(int slot, btrfs_key* _key, void** _value,
233						uint32* _size = NULL, uint32* _offset = NULL);
234		status_t	SetEntry(int slot, const btrfs_entry& entry, void* value);
235
236		int			Move(int level, int step);
237
238
239		/*!
240		* Allocate and copy block and do all the changes that it can.
241		* for now, we only copy-on-write tree block,
242		* file data is "nocow" by default.
243		*
244		*  o   parent  o
245		*  |    ===>    \
246		*  o           x o
247		*/
248		status_t	CopyOnWrite(Transaction& transaction, int level,
249						uint32 start, int num, int length);
250		/*!
251		* Copy-On-Write all internal nodes start from a specific level.
252		* level > 0: to root
253		* level <= 0: to leaf
254		*
255		*      path    cow-path       path    cow-path
256		*  =================================================
257		*      root    cow-root       root level < 0
258		*       |      |               |
259		*       n1     cow-n1         ...______
260		*       |      |               |       \
261		*       n2     cow-n2          n1     cow-n1
262		*       |      /               |        |
263		*      ...____/                n2     cow-n2
264		*       |                      |        |
265		*      leaf    level > 0      leaf    cow-leaf
266		*/
267		status_t	InternalCopy(Transaction& transaction, int level);
268		BTree*		Tree() const { return fTree; }
269	private:
270		Path(const Path&);
271		Path operator=(const Path&);
272	private:
273		Node*	fNodes[BTRFS_MAX_TREE_DEPTH];
274		int		fSlots[BTRFS_MAX_TREE_DEPTH];
275		BTree*	fTree;
276	};
277
278};	// class BTree
279
280
281class TreeIterator : public SinglyLinkedListLinkImpl<TreeIterator> {
282public:
283								TreeIterator(BTree* tree, const btrfs_key& key);
284								~TreeIterator();
285
286			void				Rewind(bool inverse = false);
287			//! Set current key in the iterator
288			status_t			Find(const btrfs_key& key);
289			status_t			GetNextEntry(void** _value,
290									uint32* _size = NULL,
291									uint32* _offset = NULL);
292			status_t			GetPreviousEntry(void** _value,
293									uint32* _size = NULL,
294									uint32* _offset = NULL);
295
296			BTree*				Tree() const { return fTree; }
297			btrfs_key			Key() const { return fKey; }
298
299private:
300			friend class BTree;
301
302			//! Iterates through the tree in the specified direction
303			status_t			_Traverse(btree_traversing direction);
304			status_t			_Find(btree_traversing type, btrfs_key& key,
305									void** _value);
306			//! Like GetEntry in BTree::Path but checks type and moving
307			status_t			_GetEntry(btree_traversing type, void** _value,
308									uint32* _size, uint32* _offset);
309			// called by BTree
310			void				Stop();
311
312private:
313			BTree*			fTree;
314			BTree::Path*	fPath;
315			btrfs_key		fKey;
316			status_t		fIteratorStatus;
317};
318
319
320//	#pragma mark - BTree::Path inline functions
321
322
323inline status_t
324BTree::Path::GetCurrentEntry(btrfs_key* _key, void** _value, uint32* _size,
325	uint32* _offset)
326{
327	return GetEntry(fSlots[0], _key, _value, _size, _offset);
328}
329
330
331//	#pragma mark - TreeIterator inline functions
332
333
334inline status_t
335TreeIterator::GetNextEntry(void** _value, uint32* _size, uint32* _offset)
336{
337	return _GetEntry(BTREE_FORWARD, _value, _size, _offset);
338}
339
340
341inline status_t
342TreeIterator::GetPreviousEntry(void** _value, uint32* _size, uint32* _offset)
343{
344	return _GetEntry(BTREE_BACKWARD, _value, _size, _offset);
345}
346
347
348#endif	// B_TREE_H
349