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                                                                 BTree(Volume* volume);
  47                                                                 BTree(Volume* volume,
  48                                                                         btrfs_stream* stream);
  49                                                                 BTree(Volume* volume,
  50                                                                         fsblock_t rootBlock);
  51                                                                 ~BTree();
  52                         status_t                        FindExact(btrfs_key& key, void** value,
  53                                                                         uint32* size = NULL, bool read = true);
  54                         status_t                        FindNext(btrfs_key& key, void** value,
  55                                                                         uint32* size = NULL, bool read = true);
  56                         status_t                        FindPrevious(btrfs_key& key, void** value,
  57                                                                         uint32* size = NULL, bool read = true);
  58
  59                         Volume*                         SystemVolume() const { return fVolume; }
  60
  61                         status_t                        SetRoot(off_t logical, fsblock_t* block);
  62                         fsblock_t                       RootBlock() const { return fRootBlock; }
  63                         off_t                           LogicalRoot() const { return fLogicalRoot; }
  64
  65 private:
  66                                                                 BTree(const BTree& other);
  67                                                                 BTree& operator=(const BTree& other);
  68                                                                         // no implementation
  69
  70                         status_t                        _Find(btrfs_key& key, void** value, uint32* size,
  71                                                                         bool read, btree_traversing type);
  72                         void                            _AddIterator(TreeIterator* iterator);
  73                         void                            _RemoveIterator(TreeIterator* iterator);
  74 private:
  75                         friend class TreeIterator;
  76
  77                         fsblock_t                       fRootBlock;
  78                         off_t                           fLogicalRoot;
  79                         Volume*                         fVolume;
  80                         mutex                           fIteratorLock;
  81                         SinglyLinkedList<TreeIterator> fIterators;
  82
  83 public:
  84         class Node {
  85         public:
  86                 Node(Volume* volume);
  87                 Node(Volume* volume, off_t block);
  88                 ~Node();
  89
  90                         // just return from Header
  91                 uint64  LogicalAddress() const
  92                         { return fNode->header.LogicalAddress(); }
  93                 uint64  Flags() const
  94                         { return fNode->header.Flags(); }
  95                 uint64  Generation() const
  96                         { return fNode->header.Generation(); }
  97                 uint64  Owner() const
  98                         { return fNode->header.Owner(); }
  99                 uint32  ItemCount() const
 100                         { return fNode->header.ItemCount(); }
 101                 uint8   Level() const
 102                         { return fNode->header.Level(); }
 103
 104                 btrfs_index*    Index(uint32 i) const
 105                         { return &fNode->index[i]; }
 106
 107                 btrfs_entry*    Item(uint32 i) const
 108                         { return &fNode->entries[i]; }
 109                 uint8*  ItemData(uint32 i) const
 110                         { return (uint8*)Item(0) + Item(i)->Offset(); }
 111
 112                 void    Keep();
 113                 void    Unset();
 114
 115                 void    SetTo(off_t block);
 116                 void    SetToWritable(off_t block,
 117                                 int32 transactionId, bool empty);
 118
 119                 off_t   BlockNum() const { return fBlockNumber;}
 120                 bool    IsWritable() const { return fWritable; }
 121
 122                 status_t        SearchSlot(const btrfs_key& key, int* slot,
 123                                                 btree_traversing type) const;
 124                 private:
 125                 Node(const Node&);
 126                 Node& operator=(const Node&);
 127                         //no implementation
 128
 129                 btrfs_stream*           fNode;
 130                 Volume*                         fVolume;
 131                 off_t                           fBlockNumber;
 132                 uint32                          fCurrentSlot;
 133                 bool                            fWritable;
 134         };
 135
 136
 137         class Path {
 138         public:
 139                 Path();
 140         private:
 141                 Path(const Path&);
 142                 Path operator=(const Path&);
 143                 Node*   nodes[BTRFS_MAX_TREE_DEPTH];
 144         };
 145
 146 };      // class BTree
 147
 148
 149 class TreeIterator : public SinglyLinkedListLinkImpl<TreeIterator> {
 150 public:
 151                                                                 TreeIterator(BTree* tree, btrfs_key& key);
 152                                                                 ~TreeIterator();
 153
 154                         status_t                        Traverse(btree_traversing direction,
 155                                                                         btrfs_key& key, void** value,
 156                                                                         uint32* size = NULL);
 157                         status_t                        Find(btrfs_key& key);
 158
 159                         status_t                        Rewind();
 160                         status_t                        GetNextEntry(btrfs_key& key, void** value,
 161                                                                         uint32* size = NULL);
 162                         status_t                        GetPreviousEntry(btrfs_key& key, void** value,
 163                                                                         uint32* size = NULL);
 164
 165                         BTree*                  Tree() const { return fTree; }
 166
 167 private:
 168                         friend class BTree;
 169
 170                         // called by BTree
 171                         void                            Stop();
 172
 173 private:
 174                         BTree*                  fTree;
 175                         btrfs_key       fCurrentKey;
 176 };
 177
 178
 179 //      #pragma mark - TreeIterator inline functions
 180
 181
 182 inline status_t
 183 TreeIterator::Rewind()
 184 {
 185         fCurrentKey.SetOffset(BTREE_BEGIN);
 186         return B_OK;
 187 }
 188
 189
 190 inline status_t
 191 TreeIterator::GetNextEntry(btrfs_key& key, void** value, uint32* size)
 192 {
 193         return Traverse(BTREE_FORWARD, key, value, size);
 194 }
 195
 196
 197 inline status_t
 198 TreeIterator::GetPreviousEntry(btrfs_key& key, void** value,
 199         uint32* size)
 200 {
 201         return Traverse(BTREE_BACKWARD, key, value, size);
 202 }
 203
 204
 205 #endif  // B_TREE_H