1 #ifndef _BPLUS_TREE_H_ 2 #define _BPLUS_TREE_H_ 3 4 #include "system_dependencies.h" 5 6 /* Allocation B+ Tree Format */ 7 #define XFS_ABTB_MAGICNUM 0x41425442 // For block offset B+Tree 8 #define XFS_ABTC_MAGICNUM 0x41425443 // For block count B+ Tree 9 10 11 /* Header for Short Format btree */ 12 #define XFS_BTREE_SBLOCK_SIZE 18 13 14 /* 15 * Headers are the "nodes" really and are called "blocks". The records, keys and 16 * pts are calculated using helpers 17 */ 18 19 struct bplustree_short_block { 20 uint32 bb_magic; 21 uint16 bb_level; 22 uint16 bb_numrecs; 23 uint32 bb_leftsib; 24 uint32 bb_rightsib; 25 26 void SwapEndian(); 27 28 uint32 Magic() 29 { return bb_magic; } 30 31 uint16 Level() 32 { return bb_level; } 33 34 uint16 NumRecs() 35 { return bb_numrecs; } 36 37 xfs_alloc_ptr_t Left() 38 { return bb_leftsib; } 39 40 xfs_alloc_ptr_t Right() 41 { return bb_rightsib;} 42 } 43 44 45 /* Header for Long Format btree */ 46 #define XFS_BTREE_LBLOCK_SIZE 24 47 struct bplustree_long_block { 48 uint32 bb_magic; 49 uint16 bb_level; 50 uint16 bb_numrecs; 51 uint64 bb_leftsib; 52 uint64 bb_rightsib; 53 54 void SwapEndian(); 55 56 uint32 Magic() 57 { return bb_magic; } 58 59 uint16 Level() 60 { return bb_level; } 61 62 uint16 NumRecs() 63 { return bb_numrecs; } 64 65 xfs_alloc_ptr_t Left() 66 { return bb_leftsib; } 67 68 xfs_alloc_ptr_t Right() 69 { return bb_rightsib;} 70 } 71 72 73 /* Array of these records in the leaf node along with above headers */ 74 #define XFS_ALLOC_REC_SIZE 8 75 typedef struct xfs_alloc_rec { 76 uint32 ar_startblock; 77 uint32 ar_blockcount; 78 79 void SwapEndian(); 80 81 uint32 StartBlock() 82 { return ar_startblock; } 83 84 uint32 BlockCount() 85 { return ar_blockcount; } 86 87 } xfs_alloc_rec_t, xfs_alloc_key_t; 88 89 // Swap Endians while returning itself 90 typedef uint32 xfs_alloc_ptr_t; // Node pointers, AG relative block pointer 91 92 #define ALLOC_FLAG 0x1 93 94 #define LONG_BLOCK_FLAG 0x1 95 #define SHORT_BLOCK_FLAG 0x2 96 97 union btree_ptr { 98 bplustree_long_block fLongBlock; 99 bplustree_short_block fShortBlock; 100 } 101 102 union btree_key { 103 xfs_alloc_key_t fAlloc; 104 } 105 106 union btree_rec { 107 xfs_alloc_rec_t fAlloc; 108 } 109 110 class BPlusTree { 111 public: 112 uint32 BlockSize(); 113 int RecordSize(); 114 int MaxRecords(bool leaf); 115 int KeyLen(); 116 int BlockLen(); 117 int PtrLen(); 118 int RecordOffset(int pos); // get the pos'th record 119 int KeyOffset(int pos); // get the pos'th key 120 int PtrOffset(int pos); // get the pos'th ptr 121 122 private: 123 Volume* fVolume; 124 xfs_agnumber_t fAgnumber; 125 btree_ptr* fRoot; 126 int fRecType; 127 int fKeyType; 128 int fPtrType; 129 } 130 131 #endif 132