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
 132                 off_t   BlockNum() const { return fBlockNumber;}
 133                 bool    IsWritable() const { return fWritable; }
 134
 135                 status_t        SearchSlot(const btrfs_key& key, int* slot,
 136                                                 btree_traversing type) const;
 137                 private:
 138                 Node(const Node&);
 139                 Node& operator=(const Node&);
 140                         //no implementation
 141
 142                 btrfs_stream*           fNode;
 143                 Volume*                         fVolume;
 144                 off_t                           fBlockNumber;
 145                 bool                            fWritable;
 146         };
 147
 148
 149         class Path {
 150         public:
 151                 Path(BTree* tree);
 152                 ~Path();
 153
 154                 Node*           GetNode(int level, int* _slot = NULL) const;
 155                 Node*           SetNode(off_t block, int slot);
 156                 Node*           SetNode(const Node* node, int slot);
 157                 status_t        GetCurrentEntry(btrfs_key* _key, void** _value,
 158                                                 uint32* _size = NULL, uint32* _offset = NULL);
 159                 status_t        GetEntry(int slot, btrfs_key* _key, void** _value,
 160                                                 uint32* _size = NULL, uint32* _offset = NULL);
 161
 162                 int                     Move(int level, int step);
 163
 164                 BTree*          Tree() const { return fTree; }
 165         private:
 166                 Path(const Path&);
 167                 Path operator=(const Path&);
 168         private:
 169                 Node*   fNodes[BTRFS_MAX_TREE_DEPTH];
 170                 int             fSlots[BTRFS_MAX_TREE_DEPTH];
 171                 BTree*  fTree;
 172         };
 173
 174 };      // class BTree
 175
 176
 177 class TreeIterator : public SinglyLinkedListLinkImpl<TreeIterator> {
 178 public:
 179                                                                 TreeIterator(BTree* tree, btrfs_key& key);
 180                                                                 ~TreeIterator();
 181
 182                         status_t                        Traverse(btree_traversing direction,
 183                                                                         btrfs_key& key, void** value,
 184                                                                         uint32* size = NULL);
 185                         status_t                        Find(btrfs_key& key);
 186
 187                         status_t                        Rewind();
 188                         status_t                        GetNextEntry(btrfs_key& key, void** value,
 189                                                                         uint32* size = NULL);
 190                         status_t                        GetPreviousEntry(btrfs_key& key, void** value,
 191                                                                         uint32* size = NULL);
 192
 193                         BTree*                  Tree() const { return fTree; }
 194
 195 private:
 196                         friend class BTree;
 197
 198                         // called by BTree
 199                         void                            Stop();
 200
 201 private:
 202                         BTree*                  fTree;
 203                         btrfs_key       fCurrentKey;
 204 };
 205
 206
 207 //      #pragma mark - BTree::Path inline functions
 208
 209
 210 inline status_t
 211 BTree::Path::GetCurrentEntry(btrfs_key* _key, void** _value, uint32* _size,
 212         uint32* _offset)
 213 {
 214         return GetEntry(fSlots[0], _key, _value, _size, _offset);
 215 }
 216
 217
 218 //      #pragma mark - TreeIterator inline functions
 219
 220
 221 inline status_t
 222 TreeIterator::Rewind()
 223 {
 224         fCurrentKey.SetOffset(BTREE_BEGIN);
 225         return B_OK;
 226 }
 227
 228
 229 inline status_t
 230 TreeIterator::GetNextEntry(btrfs_key& key, void** value, uint32* size)
 231 {
 232         return Traverse(BTREE_FORWARD, key, value, size);
 233 }
 234
 235
 236 inline status_t
 237 TreeIterator::GetPreviousEntry(btrfs_key& key, void** value,
 238         uint32* size)
 239 {
 240         return Traverse(BTREE_BACKWARD, key, value, size);
 241 }
 242
 243
 244 #endif  // B_TREE_H