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