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 */ 21 class LongBlock { 22 public: 23 Magic()24 uint32 Magic() 25 { return B_BENDIAN_TO_HOST_INT32(bb_magic); } 26 Level()27 uint16 Level() 28 { return B_BENDIAN_TO_HOST_INT16(bb_level); } 29 NumRecs()30 uint16 NumRecs() 31 { return B_BENDIAN_TO_HOST_INT16(bb_numrecs); } 32 Left()33 TreePointer Left() 34 { return B_BENDIAN_TO_HOST_INT64(bb_leftsib); } 35 Right()36 TreePointer Right() 37 { return B_BENDIAN_TO_HOST_INT64(bb_rightsib); } 38 Blockno()39 uint64 Blockno() 40 { return B_BENDIAN_TO_HOST_INT64(bb_blkno); } 41 Lsn()42 uint64 Lsn() 43 { return B_BENDIAN_TO_HOST_INT64(bb_lsn); } 44 Uuid()45 const uuid_t& Uuid() 46 { return bb_uuid; } 47 Owner()48 uint64 Owner() 49 { return B_BENDIAN_TO_HOST_INT64(bb_owner); } 50 Offset_v5()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 59 private: 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 83 struct 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 */ 97 struct 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 */ 108 class TreeDirectory : public DirectoryIterator { 109 public: 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); 144 private: 145 inline status_t UnWrapExtents(ExtentMapUnwrap* extentsWrapped); 146 147 private: 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