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 //      #pragma mark - in-memory structures
  31
  32
  33 template<class T> class Stack;
  34 class TreeIterator;
  35
  36
  37 // needed for searching (utilizing a stack)
  38 struct node_and_key {
  39         off_t   nodeOffset;
  40         uint16  keyIndex;
  41 };
  42
  43
  44 class BTree {
  45 public:
  46         class Path;
  47
  48 public:
  49                                                                 BTree(Volume* volume);
  50                                                                 BTree(Volume* volume,
  51                                                                         btrfs_stream* stream);
  52                                                                 BTree(Volume* volume,
  53                                                                         fsblock_t rootBlock);
  54                                                                 ~BTree();
  55
  56                         status_t                        FindExact(Path* path, btrfs_key& key,
  57                                                                         void** _value, uint32* _size = NULL,
  58                                                                         uint32* _offset = NULL) const;
  59                         status_t                        FindNext(Path* path, btrfs_key& key,
  60                                                                         void** _value, uint32* _size = NULL,
  61                                                                         uint32* _offset = NULL) const;
  62                         status_t                        FindPrevious(Path* path, btrfs_key& key,
  63                                                                         void** _value, uint32* _size = NULL,
  64                                                                         uint32* _offset = NULL) const;
  65
  66                         status_t                        Traverse(btree_traversing type, Path* path,
  67                                                                         const btrfs_key& key) const;
  68
  69                         status_t                        PreviousLeaf(Path* path) const;
  70                         status_t                        NextLeaf(Path* path) const;
  71
  72                         Volume*                         SystemVolume() const { return fVolume; }
  73                         status_t                        SetRoot(off_t logical, fsblock_t* block);
  74                         fsblock_t                       RootBlock() const { return fRootBlock; }
  75                         off_t                           LogicalRoot() const { return fLogicalRoot; }
  76
  77 private:
  78                                                                 BTree(const BTree& other);
  79                                                                 BTree& operator=(const BTree& other);
  80                                                                         // no implementation
  81
  82                         status_t                        _Find(Path* path, btrfs_key& key,
  83                                                                         void** _value, uint32* _size,
  84                                                                         uint32* _offset, btree_traversing type)
  85                                                                         const;
  86                         void                            _AddIterator(TreeIterator* iterator);
  87                         void                            _RemoveIterator(TreeIterator* iterator);
  88 private:
  89                         friend class TreeIterator;
  90
  91                         fsblock_t                       fRootBlock;
  92                         off_t                           fLogicalRoot;
  93                         Volume*                         fVolume;
  94                         mutex                           fIteratorLock;
  95                         SinglyLinkedList<TreeIterator> fIterators;
  96
  97 public:
  98         class Node {
  99         public:
 100                 Node(Volume* volume);
 101                 Node(Volume* volume, off_t block);
 102                 ~Node();
 103
 104                         // just return from Header
 105                 uint64  LogicalAddress() const
 106                         { return fNode->header.LogicalAddress(); }
 107                 uint64  Flags() const
 108                         { return fNode->header.Flags(); }
 109                 uint64  Generation() const
 110                         { return fNode->header.Generation(); }
 111                 uint64  Owner() const
 112                         { return fNode->header.Owner(); }
 113                 uint32  ItemCount() const
 114                         { return fNode->header.ItemCount(); }
 115                 uint8   Level() const
 116                         { return fNode->header.Level(); }
 117
 118                 btrfs_index*    Index(uint32 i) const
 119                         { return &fNode->index[i]; }
 120
 121                 btrfs_entry*    Item(uint32 i) const
 122                         { return &fNode->entries[i]; }
 123                 uint8*  ItemData(uint32 i) const
 124                         { return (uint8*)Item(0) + Item(i)->Offset(); }
 125
 126                 void    Keep();
 127                 void    Unset();
 128
 129                 void    SetTo(off_t block);
 130                 void    SetToWritable(off_t block, int32 transactionId, bool empty);
 131                 int             SpaceUsed() const;
 132                 int             SpaceLeft() const;
 133
 134                 off_t   BlockNum() const { return fBlockNumber;}
 135                 bool    IsWritable() const { return fWritable; }
 136
 137                 status_t        SearchSlot(const btrfs_key& key, int* slot,
 138                                                 btree_traversing type) const;
 139         private:
 140                 Node(const Node&);
 141                 Node& operator=(const Node&);
 142                         //no implementation
 143
 144                 status_t        _SpaceCheck(int length) const;
 145                 int             _CalculateSpace(uint32 from, uint32 to, uint8 type = 1) const;
 146
 147                 btrfs_stream*           fNode;
 148                 Volume*                         fVolume;
 149                 off_t                           fBlockNumber;
 150                 bool                            fWritable;
 151         };
 152
 153
 154         class Path {
 155         public:
 156                 Path(BTree* tree);
 157                 ~Path();
 158
 159                 Node*           GetNode(int level, int* _slot = NULL) const;
 160                 Node*           SetNode(off_t block, int slot);
 161                 Node*           SetNode(const Node* node, int slot);
 162                 status_t        GetCurrentEntry(btrfs_key* _key, void** _value,
 163                                                 uint32* _size = NULL, uint32* _offset = NULL);
 164                 status_t        GetEntry(int slot, btrfs_key* _key, void** _value,
 165                                                 uint32* _size = NULL, uint32* _offset = NULL);
 166
 167                 int                     Move(int level, int step);
 168
 169                 BTree*          Tree() const { return fTree; }
 170         private:
 171                 Path(const Path&);
 172                 Path operator=(const Path&);
 173         private:
 174                 Node*   fNodes[BTRFS_MAX_TREE_DEPTH];
 175                 int             fSlots[BTRFS_MAX_TREE_DEPTH];
 176                 BTree*  fTree;
 177         };
 178
 179 };      // class BTree
 180
 181
 182 class TreeIterator : public SinglyLinkedListLinkImpl<TreeIterator> {
 183 public:
 184                                                                 TreeIterator(BTree* tree, const btrfs_key& key);
 185                                                                 ~TreeIterator();
 186
 187                         void                            Rewind(bool inverse = false);
 188                         status_t                        Find(const btrfs_key& key);
 189                         status_t                        GetNextEntry(void** _value,
 190                                                                         uint32* _size = NULL,
 191                                                                         uint32* _offset = NULL);
 192                         status_t                        GetPreviousEntry(void** _value,
 193                                                                         uint32* _size = NULL,
 194                                                                         uint32* _offset = NULL);
 195
 196                         BTree*                          Tree() const { return fTree; }
 197                         btrfs_key                       Key() const { return fKey; }
 198
 199 private:
 200                         friend class BTree;
 201
 202                         status_t                        _Traverse(btree_traversing direction);
 203                         status_t                        _Find(btree_traversing type, btrfs_key& key,
 204                                                                         void** _value);
 205                         status_t                        _GetEntry(btree_traversing type, void** _value,
 206                                                                         uint32* _size, uint32* _offset);
 207                         // called by BTree
 208                         void                            Stop();
 209
 210 private:
 211                         BTree*                  fTree;
 212                         BTree::Path*    fPath;
 213                         btrfs_key               fKey;
 214                         status_t                fIteratorStatus;
 215 };
 216
 217
 218 //      #pragma mark - BTree::Path inline functions
 219
 220
 221 inline status_t
 222 BTree::Path::GetCurrentEntry(btrfs_key* _key, void** _value, uint32* _size,
 223         uint32* _offset)
 224 {
 225         return GetEntry(fSlots[0], _key, _value, _size, _offset);
 226 }
 227
 228
 229 //      #pragma mark - TreeIterator inline functions
 230
 231
 232 inline status_t
 233 TreeIterator::GetNextEntry(void** _value, uint32* _size, uint32* _offset)
 234 {
 235         return _GetEntry(BTREE_FORWARD, _value, _size, _offset);
 236 }
 237
 238
 239 inline status_t
 240 TreeIterator::GetPreviousEntry(void** _value, uint32* _size, uint32* _offset)
 241 {
 242         return _GetEntry(BTREE_BACKWARD, _value, _size, _offset);
 243 }
 244
 245
 246 #endif  // B_TREE_H