src/add-ons/kernel/file_systems/btrfs/BTree.h

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