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