1/*
2 * Copyright 2020, Shubham Bhagat, shubhambhagat111@yahoo.com
3 * All rights reserved. Distributed under the terms of the MIT License.
4 */
5#ifndef _BPLUS_TREE_H_
6#define _BPLUS_TREE_H_
7
8
9#include "Directory.h"
10#include "Extent.h"
11#include "Inode.h"
12#include "LeafDirectory.h"
13#include "Node.h"
14#include "system_dependencies.h"
15
16
17/*
18 * Headers(here, the LongBlock) are the "nodes" really and are called "blocks".
19 * The records, keys and ptrs are calculated using helpers
20 */
21class LongBlock {
22public:
23
24			uint32				Magic()
25								{ return B_BENDIAN_TO_HOST_INT32(bb_magic); }
26
27			uint16				Level()
28								{ return B_BENDIAN_TO_HOST_INT16(bb_level); }
29
30			uint16				NumRecs()
31								{ return B_BENDIAN_TO_HOST_INT16(bb_numrecs); }
32
33			TreePointer			Left()
34								{ return B_BENDIAN_TO_HOST_INT64(bb_leftsib); }
35
36			TreePointer			Right()
37								{ return B_BENDIAN_TO_HOST_INT64(bb_rightsib); }
38
39			uint64				Blockno()
40								{ return B_BENDIAN_TO_HOST_INT64(bb_blkno); }
41
42			uint64				Lsn()
43								{ return B_BENDIAN_TO_HOST_INT64(bb_lsn); }
44
45			const uuid_t&		Uuid()
46								{ return bb_uuid; }
47
48			uint64				Owner()
49								{ return B_BENDIAN_TO_HOST_INT64(bb_owner); }
50
51	static  uint32				Offset_v5()
52								{ return offsetof(LongBlock, bb_blkno); }
53
54	static	uint32				ExpectedMagic(int8 WhichDirectory,
55										Inode* inode);
56
57	static	uint32				CRCOffset();
58
59private:
60
61			uint32				bb_magic;
62			uint16				bb_level;
63			uint16				bb_numrecs;
64			uint64				bb_leftsib;
65			uint64				bb_rightsib;
66
67			// Version 5 fields start here
68			uint64				bb_blkno;
69			uint64				bb_lsn;
70			uuid_t				bb_uuid;
71			uint64				bb_owner;
72			uint32				bb_crc;
73			uint32				bb_pad;
74};
75
76
77/* We have an array of extent records in
78 * the leaf node along with above headers
79 * The behaviour is very much like node directories.
80 */
81
82
83struct ExtentMapUnwrap {
84			uint64				first;
85			uint64				second;
86};
87
88
89/*
90 * Using the structure to prevent re-reading of already read blocks during
91 * a traversal of tree.
92 *
93 * type:
94 * 0, if its an unused node, 1 if blockData size is a single block,
95 * 2 if blockData size is directory block size.
96 */
97struct PathNode {
98			int					type;
99			char*				blockData;
100			uint32				blockNumber;
101				// This is the file system block number
102};
103
104
105/*
106 * This class should handle B+Tree based directories
107 */
108class TreeDirectory : public DirectoryIterator {
109public:
110								TreeDirectory(Inode* inode);
111								~TreeDirectory();
112			status_t			InitCheck();
113			status_t			GetNext(char* name, size_t* length,
114									xfs_ino_t* ino);
115			status_t			Lookup(const char* name, size_t length,
116									xfs_ino_t* id);
117			int					EntrySize(int len) const;
118			uint32				BlockLen();
119			size_t				PtrSize();
120			size_t				KeySize();
121			TreeKey*			GetKeyFromNode(int pos, void* buffer);
122			TreePointer*		GetPtrFromNode(int pos, void* buffer);
123			TreeKey*			GetKeyFromRoot(int pos);
124			TreePointer*		GetPtrFromRoot(int pos);
125			status_t			SearchMapInAllExtent(uint64 blockNo,
126									uint32& mapIndex);
127			status_t			GetAllExtents();
128			size_t				MaxRecordsPossibleRoot();
129			size_t				MaxRecordsPossibleNode();
130			void				FillMapEntry(int num, ExtentMapEntry** map,
131									int type, int pathIndex);
132			status_t			FillBuffer(char* blockBuffer,
133									int howManyBlocksFurther,
134									ExtentMapEntry* targetMap = NULL);
135			size_t				GetPtrOffsetIntoNode(int pos);
136			size_t				GetPtrOffsetIntoRoot(int pos);
137			status_t			SearchAndFillPath(uint32 offset, int type);
138			status_t			SearchOffsetInTreeNode (uint32 offset,
139									TreePointer** pointer, int pathIndex);
140			void				SearchForMapInDirectoryBlock (uint64 blockNo,
141									int entries, ExtentMapEntry** map,
142									int type, int pathIndex);
143			uint32				SearchForHashInNodeBlock(uint32 hashVal);
144private:
145	inline	status_t			UnWrapExtents(ExtentMapUnwrap* extentsWrapped);
146
147private:
148			Inode*				fInode;
149			status_t			fInitStatus;
150			BlockInDataFork*	fRoot;
151			ExtentMapEntry*		fExtents;
152			uint32				fCountOfFilledExtents;
153			char*				fSingleDirBlock;
154			uint32				fOffsetOfSingleDirBlock;
155			uint32				fCurMapIndex;
156			uint64				fOffset;
157			uint32				fCurBlockNumber;
158			PathNode			fPathForLeaves[MAX_TREE_DEPTH];
159			PathNode			fPathForData[MAX_TREE_DEPTH];
160};
161
162#endif
163