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_PLUS_TREE_H 7#define B_PLUS_TREE_H 8 9 10#include "btrfs.h" 11 12#include <util/SinglyLinkedList.h> 13 14#include "Volume.h" 15 16 17#define BPLUSTREE_NULL -1LL 18#define BPLUSTREE_FREE -2LL 19 20 21enum bplustree_traversing { 22 BPLUSTREE_FORWARD = 1, 23 BPLUSTREE_EXACT = 0, 24 BPLUSTREE_BACKWARD = -1, 25 26 BPLUSTREE_BEGIN = 0, 27 BPLUSTREE_END = -1 28}; 29 30 31// #pragma mark - in-memory structures 32 33template<class T> class Stack; 34class TreeIterator; 35 36 37// needed for searching (utilizing a stack) 38struct node_and_key { 39 off_t nodeOffset; 40 uint16 keyIndex; 41}; 42 43 44class BPlusTree { 45public: 46 BPlusTree(Volume* volume, 47 struct btrfs_stream *stream); 48 BPlusTree(Volume* volume, 49 fsblock_t rootBlock); 50 ~BPlusTree(); 51 status_t FindExact(struct btrfs_key &key, void** value, 52 size_t* size = NULL); 53 status_t FindNext(struct btrfs_key &key, void** value, 54 size_t* size = NULL); 55 status_t FindPrevious(struct btrfs_key &key, void** value, 56 size_t* size = NULL); 57 58private: 59 BPlusTree(const BPlusTree& other); 60 BPlusTree& operator=(const BPlusTree& other); 61 // no implementation 62 63 int32 _CompareKeys(struct btrfs_key &key1, 64 struct btrfs_key &key2); 65 status_t _Find(struct btrfs_key &key, void** value, 66 size_t* size, bplustree_traversing type); 67 void _AddIterator(TreeIterator* iterator); 68 void _RemoveIterator(TreeIterator* iterator); 69private: 70 friend class TreeIterator; 71 72 struct btrfs_stream* fStream; 73 fsblock_t fRootBlock; 74 Volume* fVolume; 75 mutex fIteratorLock; 76 SinglyLinkedList<TreeIterator> fIterators; 77}; 78 79 80class TreeIterator : public SinglyLinkedListLinkImpl<TreeIterator> { 81public: 82 TreeIterator(BPlusTree* tree, struct btrfs_key &key); 83 ~TreeIterator(); 84 85 status_t Traverse(bplustree_traversing direction, 86 struct btrfs_key &key, void** value, 87 size_t *size = NULL); 88 status_t Find(struct btrfs_key &key); 89 90 status_t Rewind(); 91 status_t GetNextEntry(struct btrfs_key &key, void** value, 92 size_t *size = NULL); 93 status_t GetPreviousEntry(struct btrfs_key &key, void** value, 94 size_t *size = NULL); 95 96 BPlusTree* Tree() const { return fTree; } 97 98private: 99 friend class BPlusTree; 100 101 // called by BPlusTree 102 void Stop(); 103 104private: 105 BPlusTree* fTree; 106 struct btrfs_key fCurrentKey; 107}; 108 109 110// #pragma mark - TreeIterator inline functions 111 112 113inline status_t 114TreeIterator::Rewind() 115{ 116 fCurrentKey.SetOffset(BPLUSTREE_BEGIN); 117 return B_OK; 118} 119 120inline status_t 121TreeIterator::GetNextEntry(struct btrfs_key &key, void** value, size_t *size) 122{ 123 return Traverse(BPLUSTREE_FORWARD, key, value, size); 124} 125 126inline status_t 127TreeIterator::GetPreviousEntry(struct btrfs_key &key, void** value, 128 size_t *size) 129{ 130 return Traverse(BPLUSTREE_BACKWARD, key, value, size); 131} 132 133 134 135#endif // B_PLUS_TREE_H 136