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