1 /* 2 * Copyright 2017, Chế Vũ Gia Hy, cvghy116@gmail.com. 3 * Copyright 2011, Jérôme Duval, korli@users.berlios.de. 4 * Copyright 2001-2010, Axel Dörfler, axeld@pinc-software.de. 5 * This file may be used under the terms of the MIT License. 6 */ 7 #ifndef B_TREE_H 8 #define B_TREE_H 9 10 11 #include "btrfs.h" 12 #include "Volume.h" 13 14 15 #define BTREE_NULL -1LL 16 #define BTREE_FREE -2LL 17 18 #define BTRFS_MAX_TREE_DEPTH 8 19 20 21 enum btree_traversing { 22 BTREE_FORWARD = 1, 23 BTREE_EXACT = 0, 24 BTREE_BACKWARD = -1, 25 26 BTREE_BEGIN = 0, 27 BTREE_END = -1 28 }; 29 30 31 class Transaction; 32 33 34 // #pragma mark - in-memory structures 35 36 37 template<class T> class Stack; 38 class TreeIterator; 39 40 41 // needed for searching (utilizing a stack) 42 struct node_and_key { 43 off_t nodeOffset; 44 uint16 keyIndex; 45 }; 46 47 48 class BTree { 49 public: 50 class Path; 51 class Node; 52 53 public: 54 BTree(Volume* volume); 55 BTree(Volume* volume, 56 btrfs_stream* stream); 57 BTree(Volume* volume, 58 fsblock_t rootBlock); 59 ~BTree(); 60 61 status_t FindExact(Path* path, btrfs_key& key, 62 void** _value, uint32* _size = NULL, 63 uint32* _offset = NULL) const; 64 status_t FindNext(Path* path, btrfs_key& key, 65 void** _value, uint32* _size = NULL, 66 uint32* _offset = NULL) const; 67 status_t FindPrevious(Path* path, btrfs_key& key, 68 void** _value, uint32* _size = NULL, 69 uint32* _offset = NULL) const; 70 71 status_t Traverse(btree_traversing type, Path* path, 72 const btrfs_key& key) const; 73 74 status_t PreviousLeaf(Path* path) const; 75 status_t NextLeaf(Path* path) const; 76 status_t MakeEntries(Transaction& transaction, 77 Path* path, const btrfs_key& startKey, 78 int num, int length); 79 status_t InsertEntries(Transaction& transaction, 80 Path* path, btrfs_entry* entries, 81 void** data, int num); 82 status_t RemoveEntries(Transaction& transaction, 83 Path* path, const btrfs_key& startKey, 84 void** _data, int num); 85 86 Volume* SystemVolume() const { return fVolume; } 87 status_t SetRoot(off_t logical, fsblock_t* block); 88 void SetRoot(Node* root); 89 fsblock_t RootBlock() const { return fRootBlock; } 90 off_t LogicalRoot() const { return fLogicalRoot; } 91 uint8 RootLevel() const { return fRootLevel; } 92 93 private: 94 BTree(const BTree& other); 95 BTree& operator=(const BTree& other); 96 // no implementation 97 98 status_t _Find(Path* path, btrfs_key& key, 99 void** _value, uint32* _size, 100 uint32* _offset, btree_traversing type) 101 const; 102 void _AddIterator(TreeIterator* iterator); 103 void _RemoveIterator(TreeIterator* iterator); 104 private: 105 friend class TreeIterator; 106 107 fsblock_t fRootBlock; 108 off_t fLogicalRoot; 109 uint8 fRootLevel; 110 Volume* fVolume; 111 mutex fIteratorLock; 112 SinglyLinkedList<TreeIterator> fIterators; 113 114 public: 115 class Node { 116 public: 117 Node(Volume* volume); 118 Node(Volume* volume, off_t block); 119 ~Node(); 120 121 // just return from Header 122 uint64 LogicalAddress() const 123 { return fNode->header.LogicalAddress(); } 124 uint64 Flags() const 125 { return fNode->header.Flags(); } 126 uint64 Generation() const 127 { return fNode->header.Generation(); } 128 uint64 Owner() const 129 { return fNode->header.Owner(); } 130 uint32 ItemCount() const 131 { return fNode->header.ItemCount(); } 132 uint8 Level() const 133 { return fNode->header.Level(); } 134 void SetLogicalAddress(uint64 address) 135 { fNode->header.SetLogicalAddress(address); } 136 void SetGeneration(uint64 generation) 137 { fNode->header.SetGeneration(generation); } 138 void SetItemCount(uint32 itemCount) 139 { fNode->header.SetItemCount(itemCount); } 140 141 btrfs_index* Index(uint32 i) const 142 { return &fNode->index[i]; } 143 144 btrfs_entry* Item(uint32 i) const 145 { return &fNode->entries[i]; } 146 uint8* ItemData(uint32 i) const 147 { return (uint8*)Item(0) + Item(i)->Offset(); } 148 149 void Keep(); 150 void Unset(); 151 152 void SetTo(off_t block); 153 void SetToWritable(off_t block, int32 transactionId, bool empty); 154 int SpaceUsed() const; 155 int SpaceLeft() const; 156 157 off_t BlockNum() const { return fBlockNumber;} 158 bool IsWritable() const { return fWritable; } 159 status_t Copy(const Node* origin, uint32 start, uint32 end, 160 int length) const; 161 status_t MoveEntries(uint32 start, uint32 end, int length) const; 162 163 status_t SearchSlot(const btrfs_key& key, int* slot, 164 btree_traversing type) const; 165 private: 166 Node(const Node&); 167 Node& operator=(const Node&); 168 // no implementation 169 170 void _Copy(const Node* origin, uint32 at, uint32 from, uint32 to, 171 int length) const; 172 status_t _SpaceCheck(int length) const; 173 int _CalculateSpace(uint32 from, uint32 to, uint8 type = 1) const; 174 175 btrfs_stream* fNode; 176 Volume* fVolume; 177 off_t fBlockNumber; 178 bool fWritable; 179 }; 180 181 182 class Path { 183 public: 184 Path(BTree* tree); 185 ~Path(); 186 187 Node* GetNode(int level, int* _slot = NULL) const; 188 Node* SetNode(off_t block, int slot); 189 Node* SetNode(const Node* node, int slot); 190 status_t GetCurrentEntry(btrfs_key* _key, void** _value, 191 uint32* _size = NULL, uint32* _offset = NULL); 192 status_t GetEntry(int slot, btrfs_key* _key, void** _value, 193 uint32* _size = NULL, uint32* _offset = NULL); 194 status_t SetEntry(int slot, const btrfs_entry& entry, void* value); 195 196 int Move(int level, int step); 197 198 status_t CopyOnWrite(Transaction& transaction, int level, 199 uint32 start, int num, int length); 200 status_t InternalCopy(Transaction& transaction, int level); 201 202 BTree* Tree() const { return fTree; } 203 private: 204 Path(const Path&); 205 Path operator=(const Path&); 206 private: 207 Node* fNodes[BTRFS_MAX_TREE_DEPTH]; 208 int fSlots[BTRFS_MAX_TREE_DEPTH]; 209 BTree* fTree; 210 }; 211 212 }; // class BTree 213 214 215 class TreeIterator : public SinglyLinkedListLinkImpl<TreeIterator> { 216 public: 217 TreeIterator(BTree* tree, const btrfs_key& key); 218 ~TreeIterator(); 219 220 void Rewind(bool inverse = false); 221 status_t Find(const btrfs_key& key); 222 status_t GetNextEntry(void** _value, 223 uint32* _size = NULL, 224 uint32* _offset = NULL); 225 status_t GetPreviousEntry(void** _value, 226 uint32* _size = NULL, 227 uint32* _offset = NULL); 228 229 BTree* Tree() const { return fTree; } 230 btrfs_key Key() const { return fKey; } 231 232 private: 233 friend class BTree; 234 235 status_t _Traverse(btree_traversing direction); 236 status_t _Find(btree_traversing type, btrfs_key& key, 237 void** _value); 238 status_t _GetEntry(btree_traversing type, void** _value, 239 uint32* _size, uint32* _offset); 240 // called by BTree 241 void Stop(); 242 243 private: 244 BTree* fTree; 245 BTree::Path* fPath; 246 btrfs_key fKey; 247 status_t fIteratorStatus; 248 }; 249 250 251 // #pragma mark - BTree::Path inline functions 252 253 254 inline status_t 255 BTree::Path::GetCurrentEntry(btrfs_key* _key, void** _value, uint32* _size, 256 uint32* _offset) 257 { 258 return GetEntry(fSlots[0], _key, _value, _size, _offset); 259 } 260 261 262 // #pragma mark - TreeIterator inline functions 263 264 265 inline status_t 266 TreeIterator::GetNextEntry(void** _value, uint32* _size, uint32* _offset) 267 { 268 return _GetEntry(BTREE_FORWARD, _value, _size, _offset); 269 } 270 271 272 inline status_t 273 TreeIterator::GetPreviousEntry(void** _value, uint32* _size, uint32* _offset) 274 { 275 return _GetEntry(BTREE_BACKWARD, _value, _size, _offset); 276 } 277 278 279 #endif // B_TREE_H 280