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 uint64 Blockno() 38 { return B_BENDIAN_TO_HOST_INT64(bb_blkno); } 39 40 uint64 Lsn() 41 { return B_BENDIAN_TO_HOST_INT64(bb_lsn); } 42 43 uuid_t* Uuid() 44 { return &bb_uuid; } 45 46 uint64 Owner() 47 { return B_BENDIAN_TO_HOST_INT64(bb_owner); } 48 49 uint32 bb_magic; 50 uint16 bb_level; 51 uint16 bb_numrecs; 52 uint64 bb_leftsib; 53 uint64 bb_rightsib; 54 55 // Version 5 fields start here 56 57 uint64 bb_blkno; 58 uint64 bb_lsn; 59 uuid_t bb_uuid; 60 uint64 bb_owner; 61 uint32 bb_crc; 62 uint32 bb_pad; 63 }; 64 65 #define XFS_LBLOCK_CRC_OFF offsetof(struct LongBlock, bb_crc) 66 67 /* We have an array of extent records in 68 * the leaf node along with above headers 69 * The behaviour is very much like node directories. 70 */ 71 72 73 struct ExtentMapUnwrap { 74 uint64 first; 75 uint64 second; 76 }; 77 78 79 /* 80 * Using the structure to prevent re-reading of already read blocks during 81 * a traversal of tree. 82 * 83 * type: 84 * 0, if its an unused node, 1 if blockData size is a single block, 85 * 2 if blockData size is directory block size. 86 */ 87 struct PathNode { 88 int type; 89 char* blockData; 90 uint32 blockNumber; 91 // This is the file system block number 92 }; 93 94 95 /* 96 * This class should handle B+Tree based directories 97 */ 98 class TreeDirectory { 99 public: 100 TreeDirectory(Inode* inode); 101 ~TreeDirectory(); 102 status_t InitCheck(); 103 status_t GetNext(char* name, size_t* length, 104 xfs_ino_t* ino); 105 status_t Lookup(const char* name, size_t length, 106 xfs_ino_t* id); 107 bool VerifyBlockHeader(LongBlock* header, char* buffer); 108 int EntrySize(int len) const; 109 uint32 BlockLen(); 110 size_t PtrSize(); 111 size_t KeySize(); 112 TreeKey* GetKeyFromNode(int pos, void* buffer); 113 TreePointer* GetPtrFromNode(int pos, void* buffer); 114 TreeKey* GetKeyFromRoot(int pos); 115 TreePointer* GetPtrFromRoot(int pos); 116 status_t SearchMapInAllExtent(uint64 blockNo, 117 uint32& mapIndex); 118 status_t GetAllExtents(); 119 size_t MaxRecordsPossibleRoot(); 120 size_t MaxRecordsPossibleNode(); 121 void FillMapEntry(int num, ExtentMapEntry** map, 122 int type, int pathIndex); 123 status_t FillBuffer(char* blockBuffer, 124 int howManyBlocksFurther, 125 ExtentMapEntry* targetMap = NULL); 126 size_t GetPtrOffsetIntoNode(int pos); 127 size_t GetPtrOffsetIntoRoot(int pos); 128 status_t SearchAndFillPath(uint32 offset, int type); 129 status_t SearchOffsetInTreeNode (uint32 offset, 130 TreePointer** pointer, int pathIndex); 131 void SearchForMapInDirectoryBlock (uint64 blockNo, 132 int entries, ExtentMapEntry** map, 133 int type, int pathIndex); 134 uint32 SearchForHashInNodeBlock(uint32 hashVal); 135 private: 136 inline status_t UnWrapExtents(ExtentMapUnwrap* extentsWrapped); 137 138 private: 139 Inode* fInode; 140 status_t fInitStatus; 141 BlockInDataFork* fRoot; 142 ExtentMapEntry* fExtents; 143 uint32 fCountOfFilledExtents; 144 char* fSingleDirBlock; 145 uint32 fOffsetOfSingleDirBlock; 146 uint32 fCurMapIndex; 147 uint64 fOffset; 148 uint32 fCurBlockNumber; 149 PathNode fPathForLeaves[MAX_TREE_DEPTH]; 150 PathNode fPathForData[MAX_TREE_DEPTH]; 151 }; 152 153 #endif 154