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