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
7
8//! B+Tree implementation
9
10
11#include "BPlusTree.h"
12
13#include "CachedBlock.h"
14
15#include <stdlib.h>
16#include <string.h>
17#include <util/AutoLock.h>
18
19
20//#define TRACE_BTRFS
21#ifdef TRACE_BTRFS
22#	define TRACE(x...) dprintf("\33[34mbtrfs:\33[0m " x)
23#else
24#	define TRACE(x...) ;
25#endif
26#	define ERROR(x...) dprintf("\33[34mbtrfs:\33[0m " x)
27
28
29BPlusTree::BPlusTree(Volume* volume, struct btrfs_stream *stream)
30	:
31	fStream(stream),
32	fRootBlock(0),
33	fVolume(volume)
34{
35	mutex_init(&fIteratorLock, "btrfs b+tree iterator");
36}
37
38
39BPlusTree::BPlusTree(Volume* volume, fsblock_t rootBlock)
40	:
41	fStream(NULL),
42	fRootBlock(rootBlock),
43	fVolume(volume)
44{
45	mutex_init(&fIteratorLock, "btrfs b+tree iterator");
46}
47
48
49BPlusTree::~BPlusTree()
50{
51	// if there are any TreeIterators left, we need to stop them
52	// (can happen when the tree's inode gets deleted while
53	// traversing the tree - a TreeIterator doesn't lock the inode)
54	mutex_lock(&fIteratorLock);
55
56	SinglyLinkedList<TreeIterator>::Iterator iterator
57		= fIterators.GetIterator();
58	while (iterator.HasNext())
59		iterator.Next()->Stop();
60	mutex_destroy(&fIteratorLock);
61}
62
63
64int32
65BPlusTree::_CompareKeys(struct btrfs_key &key1, struct btrfs_key &key2)
66{
67	if (key1.ObjectID() > key2.ObjectID())
68		return 1;
69	if (key1.ObjectID() < key2.ObjectID())
70		return -1;
71	if (key1.Type() > key2.Type())
72		return 1;
73	if (key1.Type() < key2.Type())
74		return -1;
75	if (key1.Offset() > key2.Offset())
76		return 1;
77	if (key1.Offset() < key2.Offset())
78		return -1;
79	return 0;
80}
81
82
83/*!	Searches the key in the tree, and stores the allocated found item in
84	_value, if successful.
85	Returns B_OK when the key could be found, B_ENTRY_NOT_FOUND if not.
86	It can also return other errors to indicate that something went wrong.
87*/
88status_t
89BPlusTree::_Find(struct btrfs_key &key, void** _value, size_t* _size,
90	bplustree_traversing type)
91{
92	TRACE("Find() objectid %lld type %d offset %lld \n", key.ObjectID(),
93		key.Type(), key.Offset());
94	btrfs_stream *stream = fStream;
95	CachedBlock cached(fVolume);
96	fsblock_t physical;
97	if (stream == NULL) {
98		if (fVolume->FindBlock(fRootBlock, physical) != B_OK) {
99			ERROR("Find() unmapped block %lld\n", fRootBlock);
100			return B_ERROR;
101		}
102		stream = (btrfs_stream *)cached.SetTo(physical);
103	}
104
105	while (stream->header.Level() != 0) {
106		TRACE("Find() level %d\n", stream->header.Level());
107		uint32 i = 1;
108		for (; i < stream->header.ItemCount(); i++) {
109			int32 comp = _CompareKeys(stream->index[i].key, key);
110			TRACE("Find() found index %ld at %lld comp %ld\n", i,
111				stream->index[i].BlockNum(), comp);
112			if (comp < 0)
113				continue;
114			if (comp > 0 || type == BPLUSTREE_BACKWARD)
115				break;
116		}
117		TRACE("Find() getting index %ld at %lld\n", i - 1,
118			stream->index[i - 1].BlockNum());
119
120		if (fVolume->FindBlock(stream->index[i - 1].BlockNum(), physical)
121			!= B_OK) {
122			ERROR("Find() unmapped block %lld\n",
123				stream->index[i - 1].BlockNum());
124			return B_ERROR;
125		}
126		stream = (btrfs_stream *)cached.SetTo(physical);
127	}
128
129	uint32 i;
130#ifdef TRACE_BTRFS
131	TRACE("Find() dump count %ld\n", stream->header.ItemCount());
132	for (i = 0; i < stream->header.ItemCount(); i++) {
133		int32 comp = _CompareKeys(key, stream->entries[i].key);
134		TRACE("Find() dump %ld %ld offset %lld comp %ld\n",
135			stream->entries[i].Offset(),
136			stream->entries[i].Size(), stream->entries[i].key.Offset(), comp);
137	}
138#endif
139
140	for (i = 0; i < stream->header.ItemCount(); i++) {
141		int32 comp = _CompareKeys(key, stream->entries[i].key);
142		TRACE("Find() found %ld %ld oid %lld type %d offset %lld comp %ld\n",
143			stream->entries[i].Offset(), stream->entries[i].Size(),
144			stream->entries[i].key.ObjectID(), stream->entries[i].key.Type(),
145			stream->entries[i].key.Offset(), comp);
146		if (comp == 0)
147			break;
148		if (comp < 0 && i > 0) {
149			if (type == BPLUSTREE_EXACT)
150				return B_ENTRY_NOT_FOUND;
151			if (type == BPLUSTREE_BACKWARD)
152				i--;
153			break;
154		}
155	}
156
157	if (i == stream->header.ItemCount()) {
158		if (type == BPLUSTREE_BACKWARD)
159			i--;
160		else
161			return B_ENTRY_NOT_FOUND;
162	}
163
164	if (i < stream->header.ItemCount()
165		&& stream->entries[i].key.Type() == key.Type()) {
166		TRACE("Find() found %ld %ld\n", stream->entries[i].Offset(),
167			stream->entries[i].Size());
168		if (_value != NULL) {
169			*_value = malloc(stream->entries[i].Size());
170			memcpy(*_value, ((uint8 *)&stream->entries[0]
171				+ stream->entries[i].Offset()),
172				stream->entries[i].Size());
173			key.SetOffset(stream->entries[i].key.Offset());
174			if (_size != NULL)
175				*_size = stream->entries[i].Size();
176		}
177		return B_OK;
178	}
179
180
181	TRACE("Find() not found %lld %lld\n", key.Offset(), key.ObjectID());
182
183	return B_ENTRY_NOT_FOUND;
184}
185
186
187status_t
188BPlusTree::FindNext(struct btrfs_key &key, void** _value, size_t* _size)
189{
190	return _Find(key, _value, _size, BPLUSTREE_FORWARD);
191}
192
193
194status_t
195BPlusTree::FindPrevious(struct btrfs_key &key, void** _value, size_t* _size)
196{
197	return _Find(key, _value, _size, BPLUSTREE_BACKWARD);
198}
199
200
201status_t
202BPlusTree::FindExact(struct btrfs_key &key, void** _value, size_t* _size)
203{
204	return _Find(key, _value, _size, BPLUSTREE_EXACT);
205}
206
207
208void
209BPlusTree::_AddIterator(TreeIterator* iterator)
210{
211	MutexLocker _(fIteratorLock);
212	fIterators.Add(iterator);
213}
214
215
216void
217BPlusTree::_RemoveIterator(TreeIterator* iterator)
218{
219	MutexLocker _(fIteratorLock);
220	fIterators.Remove(iterator);
221}
222
223
224//	#pragma mark -
225
226
227TreeIterator::TreeIterator(BPlusTree* tree, struct btrfs_key &key)
228	:
229	fTree(tree),
230	fCurrentKey(key)
231{
232	Rewind();
233	tree->_AddIterator(this);
234}
235
236
237TreeIterator::~TreeIterator()
238{
239	if (fTree)
240		fTree->_RemoveIterator(this);
241}
242
243
244/*!	Iterates through the tree in the specified direction.
245*/
246status_t
247TreeIterator::Traverse(bplustree_traversing direction, struct btrfs_key &key,
248	void** value, size_t* size)
249{
250	if (fTree == NULL)
251		return B_INTERRUPTED;
252
253	fCurrentKey.SetOffset(fCurrentKey.Offset() + direction);
254	status_t status = fTree->_Find(fCurrentKey, value, size,
255		direction);
256	if (status != B_OK) {
257		TRACE("TreeIterator::Traverse() Find failed\n");
258		return B_ENTRY_NOT_FOUND;
259	}
260
261	return B_OK;
262}
263
264
265/*!	just sets the current key in the iterator.
266*/
267status_t
268TreeIterator::Find(struct btrfs_key &key)
269{
270	if (fTree == NULL)
271		return B_INTERRUPTED;
272	fCurrentKey = key;
273	return B_OK;
274}
275
276
277void
278TreeIterator::Stop()
279{
280	fTree = NULL;
281}
282
283