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 "Extent.h" 10 #include "Inode.h" 11 #include "LeafDirectory.h" 12 #include "Node.h" 13 #include "system_dependencies.h" 14 15 16 /* 17 * Headers(here, the LongBlock) are the "nodes" really and are called "blocks". 18 * The records, keys and ptrs are calculated using helpers 19 */ 20 struct LongBlock { 21 22 uint32 Magic() 23 { return B_BENDIAN_TO_HOST_INT32(bb_magic); } 24 25 uint16 Level() 26 { return B_BENDIAN_TO_HOST_INT16(bb_level); } 27 28 uint16 NumRecs() 29 { return B_BENDIAN_TO_HOST_INT16(bb_numrecs); } 30 31 TreePointer Left() 32 { return B_BENDIAN_TO_HOST_INT64(bb_leftsib); } 33 34 TreePointer Right() 35 { return B_BENDIAN_TO_HOST_INT64(bb_rightsib); } 36 37 uint32 bb_magic; 38 uint16 bb_level; 39 uint16 bb_numrecs; 40 uint64 bb_leftsib; 41 uint64 bb_rightsib; 42 }; 43 44 45 /* We have an array of extent records in 46 * the leaf node along with above headers 47 * The behaviour is very much like node directories. 48 */ 49 50 51 struct ExtentMapUnwrap { 52 uint64 first; 53 uint64 second; 54 }; 55 56 57 /* 58 * Using the structure to prevent re-reading of already read blocks during 59 * a traversal of tree. 60 * 61 * type: 62 * 0, if its an unused node, 1 if blockData size is a single block, 63 * 2 if blockData size is directory block size. 64 */ 65 struct PathNode { 66 int type; 67 char* blockData; 68 uint32 blockNumber; 69 // This is the file system block number 70 }; 71 72 73 /* 74 * This class should handle B+Tree based directories 75 */ 76 class TreeDirectory { 77 public: 78 TreeDirectory(Inode* inode); 79 ~TreeDirectory(); 80 status_t InitCheck(); 81 status_t GetNext(char* name, size_t* length, 82 xfs_ino_t* ino); 83 status_t Lookup(const char* name, size_t length, 84 xfs_ino_t* id); 85 int EntrySize(int len) const; 86 int BlockLen(); 87 size_t PtrSize(); 88 size_t KeySize(); 89 TreeKey* GetKeyFromNode(int pos, void* buffer); 90 TreePointer* GetPtrFromNode(int pos, void* buffer); 91 TreeKey* GetKeyFromRoot(int pos); 92 TreePointer* GetPtrFromRoot(int pos); 93 status_t SearchMapInAllExtent(int blockNo, 94 uint32& mapIndex); 95 status_t GetAllExtents(); 96 size_t MaxRecordsPossibleRoot(); 97 size_t MaxRecordsPossibleNode(); 98 void FillMapEntry(int num, ExtentMapEntry** map, 99 int type, int pathIndex); 100 status_t FillBuffer(char* blockBuffer, 101 int howManyBlocksFurther, 102 ExtentMapEntry* targetMap = NULL); 103 size_t GetPtrOffsetIntoNode(int pos); 104 size_t GetPtrOffsetIntoRoot(int pos); 105 status_t SearchAndFillPath(uint32 offset, int type); 106 status_t SearchOffsetInTreeNode (uint32 offset, 107 TreePointer** pointer, int pathIndex); 108 void SearchForMapInDirectoryBlock (int blockNo, 109 int entries, ExtentMapEntry** map, 110 int type, int pathIndex); 111 uint32 SearchForHashInNodeBlock(uint32 hashVal); 112 private: 113 inline status_t UnWrapExtents(ExtentMapUnwrap* extentsWrapped); 114 115 private: 116 Inode* fInode; 117 status_t fInitStatus; 118 BlockInDataFork* fRoot; 119 ExtentMapEntry* fExtents; 120 uint32 fCountOfFilledExtents; 121 char* fSingleDirBlock; 122 uint32 fOffsetOfSingleDirBlock; 123 uint32 fCurMapIndex; 124 uint64 fOffset; 125 uint32 fCurBlockNumber; 126 PathNode fPathForLeaves[MAX_TREE_DEPTH]; 127 PathNode fPathForData[MAX_TREE_DEPTH]; 128 }; 129 130 131 #endif 132